Метод динамического программирования
Зависимость оптимальной прибыли от величины распределяемого ресурса. Оптимальное решение модели с помощью метода динамического программирования. Изображение ациклической сети распределения ресурса, соответствующей модели. Рекуррентное соотношения метода.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 28.09.2017 |
| Размер файла | 143,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
9
Размещено на http://www.allbest.ru/
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
КОНТРОЛЬНАЯ РАБОТА № 4
по дисциплине "Автоматизированные информационно-управляющие системы"
г. Ноябрьск 2012
Динамическое программирование
1. Сформулировать по заданному 24-хзначному числу математическую модель вида:
где все параметры модели должны быть определены на основе таблиц 3, 4, 5 приведенных в контрольной работе №1, а также из следующего условия:
Примечание. Если a1j = 1, то следует принять a1j = 2. (Это делается для уменьшения размера таблиц, получаемых при решении данной модели.)
2. Придумать оригинальную содержательную постановку задачи, которой соответствует модель из п.1.
Примечание. Данная задача относится к классу задач распределения ресурса.
3. Найти оптимальное решение модели, сформированной в п.1, используя метод динамического программирования.
4. Построить график зависимости оптимальной прибыли от величины распределяемого ресурса.
5. Требуется графически изобразить ациклическую сеть распределения ресурса, соответствующую модели из п.1.
Примечание. Константу в правой части ограничения модели следует заменить на
1. Формулировка модели.
Исходные данные:
|
а11 |
а12 |
а13 |
а14 |
c1 |
c2 |
c3 |
c4 |
b1 |
||
|
i |
1 |
2 |
3 |
4 |
3 |
6 |
9 |
12 |
- |
|
|
5 |
8 |
4 |
5 |
4 |
5 |
6 |
4 |
18 |
2. Постановка задачи.
Частная клиника получила решением города грант в размере 18 миллионов рублей на закупку нового оборудования, так как в некоторых отделениях оборудование изношено. Главный врач клиники изучил ситуацию по отделениям и выяснил, что наиболее нуждающиеся отделения в замене оборудования - это реанимационное, хирургическое, диагностическое и акушерское. Так как клиника частная, то, соответственно, все услуги в ней платные и каждое из рассматриваемых отделений приносит свой определенный доход. Главврачу необходимо выяснить, какое из отделений принесет наибольший доход на новом оборудовании.
По условию задачи мы имеем информацию о затратах на приобретение оборудования для каждого отделения, а также последующую предполагаемую прибыль, то есть для закупки оборудования для:
реанимационного отделения (1) необходимо будет потратить 5 млн рублей и в будущем получить 4 млн рублей прибыли от одного комплекта оборудования;
хирургического отделения (2) необходимо будет потратить 8 млн рублей и в будущем получить 5 млн рублей прибыли от одного комплекта оборудования;
диагностического отделения (3) необходимо будет потратить 4 млн рублей и в будущем получить 6 млн рублей прибыли от одного комплекта оборудования;
акушерского отделения (4) необходимо будет потратить 5 млн рублей и в будущем получить 4 млн рублей прибыли от одного комплекта оборудования;
Решение.
Запишем рекуррентное соотношение динамического программирования:
Допустим, что мы рассматриваем вложение средств только в производство 1:
Возьмем для рассмотрения последний объект
Составляем таблицу:
динамическое программирование ациклическая сеть
Таблица 3. Расчет оптимального вложения средств в производство 1 (с конца), n=1.
|
S |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
|
|
x4 (S) |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
2 |
3 |
3 |
3 |
3 |
|
|
f4 (S) |
0 |
0 |
0 |
0 |
0 |
4 |
4 |
4 |
4 |
4 |
8 |
8 |
8 |
8 |
8 |
12 |
12 |
12 |
12 |
Возьмем для рассмотрения третий объект
Составляем таблицу:
Таблица 4.
Расчет оптимального вложения средств в производство 2 (с конца), n=2.
|
S |
0 |
1 |
2 |
3 |
4 |
x3 (S) |
f3 (S) |
|
|
0 |
0 |
x |
x |
x |
x |
0 |
0 |
|
|
1 |
0 |
x |
x |
x |
x |
0 |
0 |
|
|
2 |
0 |
x |
x |
x |
x |
0 |
0 |
|
|
3 |
0 |
x |
x |
x |
x |
0 |
0 |
|
|
4 |
0 |
6 |
x |
x |
x |
1 |
6 |
|
|
5 |
4 |
6 |
x |
x |
x |
1 |
6 |
|
|
6 |
4 |
6 |
x |
x |
x |
1 |
6 |
|
|
7 |
4 |
6 |
x |
x |
x |
1 |
6 |
|
|
8 |
4 |
6 |
12 |
x |
x |
2 |
12 |
|
|
9 |
4 |
10 |
12 |
x |
x |
2 |
12 |
|
|
10 |
8 |
10 |
12 |
x |
x |
2 |
12 |
|
|
11 |
8 |
10 |
12 |
x |
x |
2 |
12 |
|
|
12 |
8 |
10 |
12 |
18 |
x |
3 |
18 |
|
|
13 |
8 |
10 |
16 |
18 |
x |
3 |
18 |
|
|
14 |
8 |
14 |
16 |
18 |
x |
3 |
18 |
|
|
15 |
12 |
14 |
16 |
18 |
x |
3 |
18 |
|
|
16 |
12 |
14 |
16 |
18 |
24 |
4 |
24 |
|
|
17 |
12 |
14 |
16 |
22 |
24 |
4 |
24 |
|
|
18 |
12 |
14 |
20 |
22 |
24 |
4 |
24 |
Возьмем для рассмотрения второй объект
Составляем таблицу:
Таблица 5.
Расчет оптимального вложения средств в производство 3 (с конца), n=3.
|
x S |
0 |
1 |
2 |
x2 (S) |
f2 (S) |
|
|
0 |
0 |
x |
x |
0 |
0 |
|
|
1 |
0 |
x |
x |
0 |
0 |
|
|
2 |
0 |
x |
x |
0 |
0 |
|
|
3 |
0 |
x |
x |
0 |
0 |
|
|
4 |
6 |
x |
x |
0 |
6 |
|
|
5 |
6 |
x |
x |
0 |
6 |
|
|
6 |
6 |
x |
x |
0 |
6 |
|
|
7 |
6 |
x |
x |
0 |
6 |
|
|
8 |
12 |
5 |
x |
0 |
12 |
|
|
9 |
12 |
5 |
x |
0 |
12 |
|
|
10 |
12 |
5 |
x |
0 |
12 |
|
|
11 |
12 |
5 |
x |
0 |
12 |
|
|
12 |
18 |
11 |
x |
0 |
18 |
|
|
13 |
18 |
11 |
x |
0 |
18 |
|
|
14 |
18 |
11 |
x |
0 |
18 |
|
|
15 |
18 |
11 |
x |
0 |
18 |
|
|
16 |
24 |
17 |
10 |
0 |
24 |
|
|
17 |
24 |
17 |
10 |
0 |
24 |
|
|
18 |
24 |
17 |
10 |
0 |
24 |
Возьмем для рассмотрения первый объект
Составляем таблицу:
Таблица 6. Расчет оптимального вложения средств в производство 4 (с конца), n=4.
|
X S |
0 |
1 |
2 |
3 |
|||
|
0 |
0 |
x |
x |
x |
0 |
0 |
|
|
1 |
0 |
x |
x |
x |
0 |
0 |
|
|
2 |
0 |
x |
x |
x |
0 |
0 |
|
|
3 |
0 |
x |
x |
x |
0 |
0 |
|
|
4 |
6 |
x |
x |
x |
0 |
6 |
|
|
5 |
6 |
4 |
x |
x |
0 |
6 |
|
|
6 |
6 |
4 |
x |
x |
0 |
6 |
|
|
7 |
6 |
4 |
x |
x |
0 |
6 |
|
|
8 |
12 |
4 |
x |
x |
0 |
12 |
|
|
9 |
12 |
10 |
x |
x |
0 |
12 |
|
|
10 |
12 |
10 |
8 |
x |
0 |
12 |
|
|
11 |
12 |
10 |
8 |
x |
0 |
12 |
|
|
12 |
18 |
10 |
8 |
x |
0 |
18 |
|
|
13 |
18 |
16 |
8 |
x |
0 |
18 |
|
|
14 |
18 |
16 |
14 |
x |
0 |
18 |
|
|
15 |
18 |
16 |
14 |
12 |
0 |
18 |
|
|
16 |
24 |
16 |
14 |
12 |
0 |
24 |
|
|
17 |
24 |
22 |
14 |
12 |
0 |
24 |
|
|
18 |
24 |
22 |
20 |
12 |
0 |
24 |
Определяем оптимальное решение. При =18 в таблице 4 видно, что 4 млн рублей наиболее оптимально потратить на приобретение оборудования для диагностического отделения, то есть . Далее , , . Общая прибыль от приобретения будет равна 24 млн рублей.
Строим график зависимости оптимальной прибыли от величины распределяемого ресурса:
Изображаем ациклическую сеть распределения ресурса:
Список литературы
1. Автоматизированное управление в технических системах. Исследование операций (детерменированные методы).
2. Учебное пособие "Автоматизированное управление в технических системах", автор Одиноков В.В., 2005 г.
Размещено на Allbest.ru
...Подобные документы
Обзор задач, решаемых методом динамического программирования. Составление маршрута оптимальной длины. Перемножение цепочки матриц. Задача "Лестницы". Анализ необходимости использования специальных методов вероятностного динамического программирования.
курсовая работа [503,3 K], добавлен 28.06.2015Сущность и особенности выполнения метода динамического программирования. Решение математической задачи, принцип оптимальности по затратам, ручной счёт и листинг программы. Применение метода ветвей и границ, его основные преимущества и недостатки.
курсовая работа [38,9 K], добавлен 15.11.2009Класс задач, к которым применяются методы динамического программирования. Решения задачи распределения капитальных вложений между предприятиями путем построения математической модели. Программа "Максимизации капиталовложений" на базе Microsoft Excel.
курсовая работа [1,4 M], добавлен 28.10.2014Методы решения задачи оптимального резервирования технической системы. Решение задачи методами неопределенных множителей Лагранжа и динамического программирования. Построение оптимальной схемы системы при нагруженном резервировании ее элементов.
лабораторная работа [31,5 K], добавлен 10.06.2009Основы программирования с использованием библиотеки OpenGL. Приложение для построения динамического изображения модели объекта "Батискаф": разработка процедуры визуализации трехмерной схемы, интерфейса пользователя и подсистемы управления событиями.
курсовая работа [1,4 M], добавлен 26.06.2011Постановка задачи динамического программирования. Составление основного функционального управления динамического программирования, определяющего условный оптимальный выигрыш для данного состояния. Выбор оптимальной стратегии замены оборудования.
курсовая работа [873,9 K], добавлен 02.07.2014Преобразование формулы и решение ее с помощью Метода Эйлера. Моделирование метода оптимизации с функцией Розенброка. Поиск модели зашумленного сигнала. Нахождение минимума заданной целевой функции методом покоординатного спуска нулевого порядка.
курсовая работа [1,2 M], добавлен 21.12.2013Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.
курсовая работа [100,0 K], добавлен 31.10.2014Постановка задачи динамического программирования. Поведение динамической системы как функция начального состояния. Математическая формулировка задачи оптимального управления. Метод динамического программирования. Дискретная форма вариационной задачи.
реферат [59,9 K], добавлен 29.09.2008Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Обеспечение наибольшей прибыли от реализации выпускаемой продукции мебельной фабрики. Решение задачи в среде MS Excel. Выполнение преобразования симплексной таблицы методом Жордана-Гаусса. Применение метода динамического программирования и сечения Гомори.
курсовая работа [58,9 K], добавлен 28.10.2014Форма организации основного переменно-поточного производства. Особенности переналадки станков как задача динамического программирования. Общая характеристика алгоритма формирования метода ветвей и границ. Сущность понятия комбинаторная конфигурация.
курсовая работа [3,2 M], добавлен 20.12.2008Модель динамического программирования для решения задач оптимального распределения ресурсов. Принцип оптимальности, уравнение Беллмана. Двумерная и дискретная динамическая модель. Значение метода в решении прикладных задач различных областей науки.
курсовая работа [400,2 K], добавлен 01.10.2009Особенности метода неопределенных множителей Лагранжа, градиентного метода и метода перебора и динамического программирования. Конструирование алгоритма решения задачи. Структурная схема алгоритма сценария диалога и описание его программной реализации.
курсовая работа [1010,4 K], добавлен 10.08.2014Определение совокупности шаговых управлений. Решение задач динамического программирования двухэтапным способом. Решение последовательности задач условной оптимизации. Оптимальное распределение памяти, политика замены оборудования, замена форвардера.
презентация [674,9 K], добавлен 30.10.2013Анализ разработки информационных систем для деятельности учебных курсов. Поиск и анализ языков программирования для реализации разработки. Разработка модели web-ресурса "Агрегатор учебных курсов". Создания основных функциональных назначений web-ресурса.
отчет по практике [558,9 K], добавлен 25.05.2023Достижения математики в теории полумарковских процессов. Связь управляемых полумарковских процессов и динамического программирования. Разработка программы модели управляемого полумарковского процесса, реализованной на языке программирования СИ++.
курсовая работа [356,7 K], добавлен 10.09.2017Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.
курсовая работа [88,9 K], добавлен 11.02.2011Понятие Web-сайта и его типы, основы классификации. Достоинства и недостатки сайтов динамического наполнения. Языки программирования серверного выполнения, которые используются для их создания. Проектирование динамического сайта со справочным материалом.
курсовая работа [959,8 K], добавлен 05.03.2014
