Идеи метода динамического программирования

Планируя многошаговый процесс, необходимо выбирать УВ на каждом шаге с учетом его будущих последствий на еще предстоящих шагах. Однако, из этого правила есть исключение. Среди всех шагов существует один, который может планироватьсябез "заглядывания в будущее". Какой это шаг? Очевидно, последний —после него дру­гих шагов нет. Этот шаг, единственный из всех, можно планировать так, чтобы он как таковой принес наибольшую выгоду. Спланировав опти­мально этот последний шаг, можно к нему пристраивать предпоследний, к предпоследнему — предпредпоследний и т.д.

Поэтому процесс динамического программирования на 1-м этапе разворачивается от конца к началу, то есть раньше всех планируется послед­ний,

N -й шаг. А как его спланировать, если мы не знаем,чем кончился предпоследний? Очевидно, нужно сделать все возможные предположения о том, чем кончился предпоследний, (N — 1)-й шаг, и для каждого из них найти такое управление, при котором выигрыш (доход) на послед­нем шаге был бы максимален. Решив эту задачу, мы найдем условно оптимальное управление (УОУ) на N -м шаге, т.е. управление, которое надо применить, если (N — 1)-й шаг закончился определенным образом.

Предположим, что эта процедура выполнена, то есть для каждого исхода

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

Одним словом, на каждом шаге ищется такое управление, которое обеспечивает оптимальное продолжение процесса относительно достигнутого в данный момент состояния. Этот принцип выбора управления, называется принципом оптимальности. Само управление, обеспечивающее оптимальное продолжение процесса относительно заданного состояния, называется УОУ на данном шаге.

Теперь предположим, что УОУ на каждом шаге нам известно: мы знаем, что делать дальше, в каком бы состоянии ни был процесс к началу каждого шага. Тогда мы можем найти уже не "условное", а действительно оптимальное управление на каждом шаге.

Действительно, пусть нам известно начальное состояние процесса. Теперь мы уже знаем, что делать на первом шаге: надо применить УОУ, найденное для первого шага и начального состояния. В результате это­го управления после первого шага система перейдет в другое состояние; но для этого состояния мы знаем УОУ и г д. Таким образом, мы найдем оптимальное управление процессом, приводящее к максимально возможному выигрышу.

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

- первый раз — от конца к началу, в результате чего находятся УОУ на каждом шаге и оптимальный выигрыш (тоже условный) на всех шагах, начиная с данного и до конца процесса;

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

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

Дата добавления: 2014-01-15