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

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

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

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

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

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

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

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

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

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

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

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

Можно сказать, что процедура построения оптимального управления

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

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

< Предыдущая		Следующая >