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 – число шагов.
- Технологическая линия.
= ( )
–выбор оборудования для i-ой операции.
Ui – область допустимых УВ на i-м шаге.
т.е.
Wi – оценка минимальной себестоимости, полученная в результате реализации i-го шага.
S – функция общего выигрыша т. е. минимальная себестоимость .
- вектор УВ на i-ом шаге, обеспечивающий переход системы из состояния xi-1 в состояние xi , т.е. оптимальный выбор оборудования за N шагов.
Si+1() – максимальный выигрыш ( в нашем случае минимальная себестоимость), получаемый при переходе из любого состояния в конечное состояниепри оптимальной стратегии управления начиная с (k+1)-го шага.
S1() – максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния в конечноепри реализации оптимальной стратегии управления. Очевидно, чтоS = S1(), если = 0.
Запишем вектора допустимых значений
Запишем вектора допустимых управляющих воздействий
З
З
1) Обратный проход
Д
Учитывая то, что этот шаг у нас последний и следующей операции
у
возьмем стоимость сырья
при =
при =
т. е.
Для i=2
115,2
при =
138,04
при =
102,8
при =
123,1
при =
т. е.
Д
140,2
при =
125,3
при =
п
125,3
125,3
при ==
125,3
при =
125,3
при =
125,3
при =
125,3
при =
т. е.
П
Учитывая то, что и = (0,0,0) имеем
i
Таким образом оптимальный выбор состава оборудования технологической линии предполагает следующее:
На 1-ую операцию назначим оборудование 2-го вида
На 2-ую операцию назначим оборудование 1-го вида
На 3-ью операцию назначим оборудование 2-го вида
Оценка минимальной себестоимости составит 105,5.