Задача динамического программирования в общем виде. Принцип оптимальности

Рассмотренные выше простейшие задачи динамического программирования дают понятие об общей идее метода: пошаговая оптимизация, проходимая в одном направлении «условно», в другом — «безусловно». Метод динамического программирования является очень мощным и плодотворным методом оптимизации управления; ему не страшны ни целочисленность решения, ни нелинейность целевой функции, ни вид ограничений, накладываемых на решение. Но в отличие от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре; оно может быть передано на машину только после того, как записаны соответствующие формулы, а это часто бывает не так-то легко.

В этом параграфе мы дадим нечто вроде «сводки советов начинающим» — как ставить задачи динамического программирования, в каком порядке их решать, как записывать и т. д.

Первый вопрос, на который нужно ответить ставящему задачу: какими параметрами характеризуется состояние управляемой системы S перед каждым шагом? От удачного выбора набора этих параметров часто зависит возможность успешно решить задачу оптимизации. В трех конкретных примерах, которые мы решали в предыдущем параграфе, состояние системы характеризовалось очень небольшим числом параметров: двумя координатами — в первом примере, одним числом — во втором и третьем. Но такие ультрапростые задачи не так уже часто встречаются на практике. Если, как это обычно и бывает, состояние системы описывается многими параметрами (так называемыми «фазовыми координатами»), то становится трудно перед каждым шагом перебрать все их варианты и для каждого найти оптимальное условное управление. Последнее еще больше затрудняется в случае, когда число возможных вариантов управления велико. В этих случаях над нами повисает, по меткому выражению Р. Беллмана, «проклятие многомерности» — бич не только метода динамического программирования, но и всех других методов оптимизации. Обычно задачи динамического программирования решаются не вручную, а на ЭВМ, однако многие такие задачи не под силу даже современным машинам. Поэтому очень важно уметь правильно и «скромно» поставить задачу, не переобременяя ее лишними подробностями, упрощая елико возможно описание управляемой системы и вариантов управления. Так что в методе динамического программирования очень многое зависит от искусства и опыта исследователя.

Вторая задача после описания системы и перечня управлений — это членение на шаги (этапы). Иногда (на счастье) оно бывает задано в самой постановке задачи (например, хозяйственные годы в экономических задачах), но часто членение на шаги приходится вводить искусственно как мы сделали, например, в задаче 1 § 13. Если бы мы в этой задаче не ограничились самым примитивным случаем всего двух управлений («с» и «в»), то было бы удобнее членение на шаг произвести иначе, например, считая за «шаг» переход с одной прямой, параллельной оси ординат, на другую. Можно было бы вместо прямых рассмотреть окружности с центром в точке А или же другие кривые. Все такие способы выбора наивыгоднейшего пути неизбежно ограничивают выбор возможных направлений. Если за «шаги» считать переходы с одной прямой, параллельной оси ординат, на другую, то здесь множество возможных управлений не предусматривает «пути назад», т. е. с более восточной прямой на более западную. В большинстве задач практики такие ограничения естественны (например, трудно себе представить, чтобы наивыгоднейшая траектория космической ракеты, пущенной с Земли, на каких-то участках включала движение «назад», ближе к Земле). Но бывает и другая обстановка. Например, путь по сильно пересеченной местности («серпантинная» дорога в горах) часто «петляет» и возвращается ближе к исходному пункту. При постановке задачи динамического программирования, в частности при выборе системы координат и способа членения на шаги, должны быть учтены все разумные ограничения, накладываемые на управление.

Как быть с числом шагов те? С первого взгляда может показаться, что чем больше т, тем лучше. Это не совсем так. При увеличении те возрастает объем расчетов, а это не всегда оправдано. Число шагов нужно выбирать с учетом двух обстоятельств: 1) шаг должен быть достаточно мелким для того, чтобы процедура оптимизации шагового управления была достаточно проста, и 2) шаг должен быть не слишком мелким, чтобы не производить ненужных расчетов, только усложняющих процедуру поиска оптимального решения, но не приводящих к существенному изменению оптимума целевой функции. В любом случае практики нас интересует не строго оптимальное, а «приемлемое» решение, не слишком отличающееся от оптимального по значению выигрыша W*.

Сформулируем общий принцип, лежащий в основе решения всех задач динамического программирования (его часто называют «принципом оптимальности»):

Каково бы ни было состояние системы S перед очередным шагом, надо выбирать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.

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

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

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

2. Расчленить операцию на этапы (шаги).

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

4. Определить, какой выигрыш приносит на i -м шаге управление х_i, если перед этим система была в состоянии S, т. е. записать «функции выигрыша»:

 

w_i = f_i(S,x_i). (14.1)

 

5. Определить, как изменяется состояние S системы S под влиянием управления х_i на i-м шаге: оно переходит в новое состояние

 

S ^’= (S,x_i). (14.2)

 

«Функции изменения состояния» (14.2) тоже должны быть записаны¹).

6. Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш W<(S) (начиная с i -го шага и до конца) через уже известную функцию W_i+1 (S):

 

. (14.3)

 

Этому выигрышу соответствует условное оптимальное управление на i -м шаге х_i (S) (подчеркнем, что в уже известную функцию W_i+1 (S) надо вместо S подставить измененное состояние S ^’ = (S, x).

7. Произвести условную оптимизацию последнего (m -го) шага, задаваясь гаммой состояний S, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условный оптимальный выигрыш по формуле

(14.4)

и находя условное оптимальное управление x _m (S), для которого этот максимум достигается.

8. Произвести условную оптимизацию (m - 1)-го, (m - 2)-го и т. д. шагов по формуле (14.3), полагая в ней i = (m - 1), (m - 2),..., и для каждого из шагов указать условное оптимальное управление x _i(S), при котором максимум* достигается.

Заметим, что если состояние системы в начальный момент известно (а это обычно бывает так), то на первом шаге варьировать состояние системы не нужно — прямо находим оптимальный выигрыш для данного начального состояния S _o. Это и есть оптимальный выигрыш за всю операцию

W* = W_i(S_o).

9. Произвести безусловную оптимизацию управления, «читая» соответствующие рекомендации на каждом шаге. Взять найденное оптимальное управление на первом шаге ; изменить состояние системы по формуле (14.2); для вновь найденного состояния найти оптимальное управление на втором шаге x.i и т. д. до конца.

* * *

Сделаем несколько дополнительных замечаний общего характера. До сих пор мы рассматривали только аддитивные задачи динамического программирования, в которых выигрыш за всю операцию равен сумме выигрышей на отдельных шагах. Но метод динамического программирования применим также и к задачам с так называемым «мультипликативным» критерием, имеющим вид произведения:

(14.5)

(если только выигрыши ω_i положительны). Эти задачи решаются точно так же, как задачи с аддитивным критерием, с той единственной разницей, что в основном уравнении (14.3) вместо знака «плюс» ставится знак умножения X:

 

(14.6)

В заключение — несколько слов о так называемых «бесконечно шаговых» задачах динамического программирования. На практике встречаются случаи, когда планировать операцию приходится не на строго определенный, а на неопределенно долгий промежуток времени, и нас может интересовать решение задачи оптимального управления безотносительно 'к тому, на каком именно шаге операция заканчивается. В таких случаях бывает удобно рассмотреть в качестве модели явления бесконечно шаговый управляемый процесс, где не существует «особенного» по сравнению с другими последнего шага (все шаги равноправны). Для этого, разумеется, нужно, чтобы функции fi выигрыша и функции φ_i изменения состояния не зависели от номера шага. Интересующегося этим случаем читателя отошлем к руководству [10]. Вообще, для более подробного ознакомления с методом динамического программирования полезно обратиться к руководствам [6, 10, 11, 71].