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

Метод динамического программирования был разработан Р. Беллманом в начале 50-х годов [4, 8] для решения довольно широкого круга оптимизационных задач в различных областях применения – технике, экономике и др. Этод метод развивался в процессе решения вариационных задач на цифровых вычислительных машинах. Поэтому в первоначальном варианте он содержал элементы дискретности.

Метод применим к таким системам, для которых справедлив принцип оптимальности. Система удовлетворяет принципу оптимальности, если она обладает марковским свойством: ее поведение на любом конечном отрезке времени t₀ ≤ t ≤ t_T полностью определяется управлением на этом отрезке и состоянием системы в начальный для этого отрезка момент времени t₀.

Поясним принцип оптимальности геометрически.

Пусть для системы, описываемой дифференциальными уравнениями, найдено оптимальное управление U^*(t), переводящее узображающую точку из положения x⁰=x(t₀) в положение x^T=x(t_T) при заданных ограничениях и доставляющее при этом минимум функционалу:

,

где x – вектор состояния системы; U – вектор управлений; t – время.

Изобразим на рисунке 2.1 оптимальную траекторию, соответствующую этому управлению.

Рис. 2.1. Оптимальная траектория.

Рассмотрим некоторый произвольный момент t₁ в интервале . Выберем точку x(t₁) в качестве начального состояния для дальнейшего определения оптимального управления на данной оптимальной траектории. Принцип оптимальности утверждает, что при отыскании оптимального управления можно не рассматривать отрезок 1 оптимальной траектории, а принять x(t₁) за начальное состояние для решения задачи оптимизации. Тогда экстремаль 2 совпадает с участком 2 экстремали 1 – 2, найденном из условия, что начальное состояние было принято x⁰, а конечное то же самое x^T.

2.1. Геометрическая интерпретация метода динамического программирования

Рассмотрим пример решения статической вариационной задачи.

Рис. 2.2. Пример геометрической интерпретации метода динамического программирования (пример 2.1).

Пример 2.1. Между пунктами А и В (рис. 2.2) необходимо провести железную или шоссейную дорогу так, чтобы стоимость строительства была минимальной.

Путь между пунктами А и В разобъем на три горизонтальных и три вертикальных участка. Условно обозначим стоимость строительства на каждом горизонтальном и вертикальном участке (стоимость строительсва можно подсчитать заранее). Обозначим узловые точки через C_i, M_i, N_i, L_i и K_i. Решение задачи начинается с конечного пункта, точки В.

В точку В можно попасть за один шаг или из точки С₁ или из С₂. Предположим, что каким-либо способом удалось попасть в С₁ или С₂. Затраты на последний шаг равны 12 либо 10 единицам. Поставим величину затрат в кружки и укажем направление последнего шага стрелками.

Теперь рассмотрим точки М_i. Опять считаем, что каким-то образом эти точки уже достигнуты. Исследуем возможные пути в В.

Из М₁ есть один путь через С₁. Затраты при этом будут равны 25. Наметим кружок и поставим стрелку. Из М₂ имеется уже два пути: через С₁ и через С₂. Один путь дает затраты 28, а другой – 26. Через С₁ в В путь менее рационален, поэтому его из дальнейших рассуждений исключаем. Ставим в М₂ кружок с затратами и стрелку оптимального направления. Сразу обратим внимание, что второе направление из точки М₂ в точку С₁ исключается как неоптимальное. В этом и заключается весь смысл динамического программирования.

Далее анализируем точку М₃. Из М₃ имеется только одно направление в сторону пункта В через С₂. Поэтому ставим в М₃ кружок с затратами и стрелку возможного оптимального направления. Перейдем к точкам N_i. Точки N₁ и N₄ дают по одной возможной траектории. Поэтому эти точки сохраняем, обводим кружками и указываем от них стрелки. Точки N₂ и N₃ дают по две траектории каждая, из которых выбираем оптимальные, обводим кружками, указываем затраты и стрелки. Из всех возможных путей точек N₁ ÷ N₄ остаются только четыре (вместо 6). Анализируя, таким же образом оставшиеся точки L_i и K_i мы, наконец, попадаем в исходную точку А и тем самым получаем оптимальную траекторию, которая на рис. 2.2 отмечена жирной линией. Затраты оптимального пути равны 59. Еще раз обратим внимание на то, что по мере продвижения от В к А последовательно исключались неоптимальные траектории. Это исключение значительно упрощает нахождение оптимальной траектории. При простом переборе пришлось бы рассчитать все траектории от А к В, которых всего 25. Заметим еще, что на каждом шаге траектория может быть и неоптимальной относительно других шагов, но вся траектория в целом является оптимальной.

Метод динамического програмирования учитывает эффект всего процесса. После этих рассуждений становится ясным принцип оптимальности, который гласит, что любой отрезок оптимальной траектории также является оптимальным, а будущее поведение процесса не зависит от его предыстории.