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




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


А как его спланировать, если мы не знаем, чем кончился предпоследний? Т. е. не знаем условий, в которых мы приступаем к последнему шагу?

Вот тут-то и начинается самое главное. Планируя последний шаг, нужно сделать разные предположения о том, чем кончился предпоследний, (т -

1)-й шаг, и для каждого из этих предположений найти условное оптимальное управление на m-м шаге («условное» потому, что оно выбирается исходя из условия, что предпоследний шаг кончился так-то и так-то).

Предположим, что мы это сделали, и для каждого из возможных исходов предпоследнего шага знаем условное оптимальное управление и соответствующий ему условный оптимальный выигрыш на m-м шаге. Отлично! Теперь мы можем оптимизировать управление на предпоследнем, (т-1)-м шаге. Снова сделаем все возможные предположения о том, чем кончился предыдущий, (m

- 2)-й шаг, и для каждого из этих предположений найдем такое управление на (m- 1)-м шаге, при котором выигрыш за последние два шага (из которых m-й уже оптимизирован!) максимален. Так мы найдем для каждого исхода (m - 2)- шага условное оптимальное управление на (т - 1)-м шаге и условный оптимальный выигрыш на двух последних шагах. Далее, «пятясь назад», оптимизируем управление на (m

- 2)-м шаге и т. д., пока не дойдем до первого.

Предположим, что все условные оптимальные управления и условные оптимальные выигрыши за весь «хвост» процесса (на всех шагах, начиная от данного и до конца) нам известны. Это значит: мы знаем, что надо делать, как управлять на данном шаге и что мы за это получим на «хвосте», в каком бы состоянии ни был процесс к началу шага. Теперь мы можем построить уже не условно оптимальное, а просто оптимальное управление х* и найти не условно оптимальный, а просто оптимальный выигрыш W*.

В самом деле, пусть мы знаем, в каком состоянии S0 была управляемая система (объект управления S) в начале первого шага. Тогда мы можем выбрать оптимальное управление

 на первом шаге. Применив его, мы изменим, состояние системы на некоторое новое
; в этом состоянии мы подошли ко второму шагу.


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