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

(УОВ). Теперь мы можем оптимизировать управление на предпоследнем, (N 1)-м шаге. Сделаем все возможные предположения о том, чем кончился предпредпоследпий, то есть (N 2)-й шаг, и для каждого из этих предположений найдем такое управление на (N 1)-м шаге, чтобы выигрыш за последние два шага (из которых последний уже оптимизирован) был максимален. Далее оптимизируется управ чение на (N 2)-м шаге, и т.д. Одним словом, на каждом шаге ищется такое управление, которое обеспечивает оптимальное продолжение процесса относительно достигнутого в данный момент состояния. Этот принцип выбора управления , называется принципом оптимальности. Само управление, обеспечивающее оптимальное продолжение процесса относительно заданного состояния, называется УОУ на данном шаге. Теперь предположим, что УОУ на каждом шаге нам известно: мы знаем, что делать дальше, в каком бы состоянии ни был процесс к началу каждого шага. Тогда мы можем найти уже не "условное", а дейсгвительно оптимальное управление на каждом шаге. | Действительно, пусть нам известно начальное состояние процесса. Теперь мы уже знаем, что делать на первом шаге: надо применить УОУ, найденное для первого шага и начального сосюяния. В результате этого управления после первого шага система перейдет в другое состояние; но для этого состояния мы знаем УОУ и г д. Таким образом, мы найдем оптимальное управление процессом, приводящее к максимально возможному выигрышу. Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс "проходится" дважды: первый раз от конца к началу, в результате чего находятся УОУ| на каждом шаге и оптимальный выигрыш (тоже условный) на всех шагах, начиная с данного и до конца процесса; — второй раз от начала к концу, в результате чего находятся оптимальные управления на всех шагах процесса. Можно сказать, что процедура построения оптимального управления методом динамического программирования распадается на две стадии: предварительную и окончательную. На предварительной стадии для каждого шага определяется УОУ, зависящее от состояния системы (достигнутого в результате предыдущих шагов), и условно оптимальный выигрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния. На окончательной стадии определяется (безусловное) оптимальное управление для каждого шага. Предварительная (условная) оптимизация производится по шагам в обратном порядке: от последнего шага к первому; окончательная (безусловная) оптимизация также по шагам, но в естественном порядке: от первого шага к последнему. Из двух стадий оптимизации несравненно более важной и трудоемкой является первая. После окончания первой стадии выполнение второй трудности не представляет: остается только "прочесть" рекомендации, уже заготовленные на первой стадии.

III. Пример задачи динамического программирования Выбор состава оборудования технологической линии. Есть технологическая линия , то есть цепочка, последовательность операций. На каждую операцию можно назначить оборудование только каго-то одного вида, а оборудования, способного работать на данной операции, - несколько видов. Исходные данные для примера i123j121212108458912846992018681012 Стоимость сырья Расходы , связанные с использованием единицы оборудования 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.