DINAMIK PROGRAM (Динамическое программирование), страница 2
Описание файла
Документ из архива "Динамическое программирование", который расположен в категории "". Всё это находится в предмете "экономико-математическое моделирование" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "экономико-математическое моделирование" в общих файлах.
Онлайн просмотр документа "DINAMIK PROGRAM"
Текст 2 страницы из документа "DINAMIK PROGRAM"
III. Пример задачи динамического программирования
Выбор состава оборудования технологической линии.
Есть технологическая линия , то есть цепочка, последовательность операций.
На каждую операцию можно назначить оборудование только каго-то одного вида, а оборудования, способного работать на данной операции, - несколько видов.
Исходные данные для примера
i | 1 | 2 | 3 | |||
j | 1 | 2 | 1 | 2 | 1 | 2 |
| 10 | 8 | 4 | 5 | 8 | 9 |
12 | 8 | 4 | 6 | 9 | 9 | |
| 20 | 18 | 6 | 8 | 10 | 12 |
Стоимость сырья
Расходы , связанные с использованием единицы оборудования j-го типа на i-ой операции
Производительности, соответственно, по выходу и входу и для j-готипа оборудования, претендующего на i-ую операцию.
Решение:
Для того, чтобы решить данную задачу методом динамического программирования введем следующие обозначения:
N = 3 – число шагов.
= (0,0,0)– выбор оборудования для i-ой операции.
Ui – область допустимых УВ на i-м шаге.
Wi – оценка минимальной себестоимости, полученная в результате реализации i-го шага.
S – функция общего выигрыша т. е. минимальная себестоимость .
- вектор – функция, описывающая переход системы из состояния в состояние под действием УВ.
- вектор УВ на i-ом шаге, обеспечивающий переход системы из состояния xi-1 в состояние xi , т.е. оптимальный выбор оборудования за N шагов.
Si+1( ) – максимальный выигрыш ( в нашем случае минимальная себестоимость), получаемый при переходе из любого состояния в конечное состояние при оптимальной стратегии управления начиная с (k+1)-го шага.
S1( ) – максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния в конечное при реализации оптимальной стратегии управления . Очевидно, что S = S1( ), если = 0.
Запишем вектора допустимых значений
Запишем вектора допустимых управляющих воздействий
З
апишем вектор – функцию, описывающую переход системы из состояния в состояние под действием УВ.
З
апишем основное функциональное уравнение
1) Обратный проход
Д
ля i=3Учитывая то, что этот шаг у нас последний и следующей операции
у
же не будет, а также то, что мы на обратном проходе, вместо функциивозьмем стоимость сырья
т. е.
Для i=2
т. е.
Д
ля i=1
п
ри =
т. е.
Учитывая то, что и = (0,0,0) имеем
i=1
i=2
i
=3
Таким образом оптимальный выбор составаоборудования технологической линии предполагает следующее:
На 1-ую операцию назначим оборудование 2-го вида
На 2-ую операцию назначим оборудование 1-го вида
На 3-ью операцию назначим оборудование 2-го вида
Оценка минимальной себестоимости составит 105,5.
13