Динамическое программирование

до¬стигнутого в результате предыдущих шагов), и условно оптимальный вы¬игрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния. На окончательной стадии определяется (безусловное) опти¬мальное управление для каждого шага. Предварительная (условная) оптимизация производится по шагам в обратном порядке: от последне¬го шага к первому; окончательная (безусловная) оптимизация — также по шагам, но в естественном порядке: от первого шага к последнему. Из двух стадий оптимизации несравненно более важной и трудоемкой является первая. После окончания первой стадии выполнение второй трудности не представляет: остается только "прочесть" рекомендации, уже заготовленные на первой стадии.

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

при =

при =

при =

при ==

при =

при =

при =

при =

т. е.

2) Прямой проход

Учитывая то, что и = (0,0,0) имеем

i=1

i=2

i=3

Таким образом оптимальный выбор составаоборудования технологической линии предполагает следующее:

На 1-ую операцию назначим оборудование 2-го вида

На 2-ую операцию назначим оборудование 1-го вида

На 3-ью операцию назначим оборудование 2-го вида

Оценка минимальной себестоимости составит 105,5.