Исследование операций. Линейное, динамическое программирование




Исследование операций - часть 75


Тогда нам тоже известно условное оптимальное управление
,

которое к концу второго шага переводит систему в состояние

, и т. д. Что касается оптимального выигрыша W* за всю операцию, то он нам уже известен: ведь именно на основе его максимальности мы выбирали управленце на первом шаге.

Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс «проходится» дважды: первый раз — от конца к началу, в результате чего находятся условные оптимальные управления и условные оптимальные выигрыши за оставшийся «хвост» процесса; второй раз — от начала к концу, когда нам остается только «прочитать» уже готовые рекомендации и найти безусловное оптимальное управление х*,

состоящее из оптимальных шаговых управлений

Первый этап — условной оптимизации — несравненно сложнее и длительнее второго. Второй этап почти не требует дополнительных вычислений.

Автор не льстит себя надеждой, что из такого описания метода динамического программирования читатель, не встречавшийся с ним до сих пор, поймет по-настоящему его идею. Истинное понимание возникает при рассмотрении конкретных примеров, к которым мы и перейдем.

§ 13. Примеры решения задач динамического программирования

В этом параграфе мы рассмотрим (и даже решим до конца) несколько простых (до крайности упрощенных) примеров задач динамического программирования

1. Прокладка наивыгоднейшего пути между двумя пунктами. Вспомним задачу 4 предыдущего параграфа и решим ее до конца в крайне (и намеренно) упрощенных условиях. Нам нужно соорудить путь, соединяющий

Рис. 13.1.

два пункта А и В, из которых второй лежит к северо-востоку от первого. Для простоты допустим,. что прокладка пути состоит из ряда шагов, и на каждом шаге мы можем двигаться либо строго на восток, либо строго на север; любой путь из А

в В представляет собой ступенчатую ломаную линию, отрезки которой параллельны одной из координатных осей (рис. 13.1). Затраты на сооружение каждого из таких отрезков известны. Требуется проложить такой путь из А




Содержание  Назад  Вперед