Динамическое программирование

Динамическое программирование - один из мощных методов решения задач математического программирования, разработанный американским математиком Р. Беллманом в конце 50-х годов. Он изначально ориентирован на оптимизацию так называемых многошаговых (многостадийных, многоэтапных) процессов и использование ЭВМ.

Концепция метода проистекает из следующего свойства оптимального решения. Пусть оптимальный путь из точки A в точку E проходит через точки B, С и D (рис. 9.1). Тогда любая часть этого пути является оптимальным путем. Действительно, если бы, например, оптимальный путь из C в E не проходил через D, то и полный путь A,B,C,D,E не был бы оптимальным (его можно было бы улучшить за счет изменения перехода из C в E), что противоречит исходной посылке.

Рис. 9.1

Фундаментальной основой метода динамического программирования (ДП) является сформулированный Беллманом принцип оптимальности, согласно которому оптимальное управление определяется конечной целью управления и состоянием системы в рассматриваемый момент, независимо от того, каким образом она пришла в это состояние. Иначе говоря, при фиксированном состоянии системы последующее оптимальное решение не зависит от ее предыстории. Ввиду важности принципа приведем его полную формулировку.

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

Этот принцип является конструктивным, он позволяет существенно повысить эффективность решения определенного класса задач математического программирования путем их разложения на ряд задач значительно меньшей размерности. Как уже отмечалось выше, здесь имеются в виду задачи, которые могут быть представлены как многошаговые. Во многих случаях это свойство задачи очевидно, в других - требуется некоторое умение, чтобы выделить шаги. Такие задачи описываются математической моделью, в которой и критерий, и ограничения являются составными. Под составной понимается функция f, образованная частными функциями (подфункциями) f_i, к которым применен один и тот же оператор вхождения (например, оператор сложения), т.е.

f =(<оператор> < f ₁, f ₂,..., f_m >).

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

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

При разбиении задачи на шаги состояние служит связующим звеном между смежными шагами. Состояние зависит от предшествующих решений, но зная его, можно принимать решения на последующих шагах без учета решений, предшествовавших данному состоянию. Обратим внимание на важный момент: чтобы принять очередное решение, достаточно знать состояние, а не решения, приведшие к этому состоянию. Так, например, при корректировке траектории некоторого летательного аппарата (в однородной среде) достаточно знать его координаты на момент принятия решения, и не нужны решения, приведшие его в данную точку пространства. Значит, координаты и определяют состояние системы. Если же выбор решения зависит также от количества топлива на борту аппарата, то состояние системы будет определяться как координатами, так и весом оставшегося топлива. Итак, состояние описывается теми переменными системы, которые зависят от решения на предшествующем шаге и знание которых достаточно для принятия решения на очередном шаге. Чтобы отличать переменные состояния от искомых переменных (управлений), в дальнейшем будем называть их параметрами состояния.

Как работает метод ДП

Для первоначального представления метода ДП не будем прибегать к математическим выкладкам и рассмотрим его сущность на описательном уровне. Представим себе лабиринт без петель, в котором между любыми входами и выходами встречается одинаковое число развилок (узлов), например 3. Во всех узлах пересекается более одной дороги. Каждому переходу в лабиринте соответствует определенное время. Необходимо найти путь от одного из входов к любому выходу, на который требуется минимальное время.

Эту задачу можно решить методом полного перебора всех маршрутов, ведущих от фиксированного входа к выходу из лабиринта. При этом число вариантов может оказаться весьма большим, а изменение входа потребует повторного перебора. Принципиально другой подход дает метод ДП. Он предлагает конструировать оптимальный путь по частям, для чего нужно представить задачу как многошаговую. Разместим условно все входы на одной вертикальной прямой, все узлы, которые встречаются первыми на пути от входов к выходам, - на другой прямой. Также поступим со второй и другими группами узлов и, наконец, с выходами. Получим схему лабиринта в виде, показанном на рис.9.2.

 

Рис. 9.2

В данном случае мы говорим, что задача представлена как 4-шаговая. Построение оптимального пути можно начинать с 1-го или 4-го шага, но предпочтительнее с 4-го. Такой порядок решения иногда называют обратной прогонкой в отличие от прямой, при которой идут с 1-го шага. Следует сразу заметить, что для некоторых задач возможен только один порядок прогонки, обусловливаемый спецификой задачи.

Итак, начнем с построения пути на 4-м шаге. Но мы тут же сталкиваемся с проблемой: как принимать решение, если не известен узел, в котором мы окажемся после оптимального прохождения первых трех этапов? Чтобы обойти эту проблему, будем искать оптимальное решение для каждого из узлов, в котором можем оказаться перед 4-м шагом (это узлы 8,9 и 10). Фиксируем узел 8 и из четырех значений времени перехода из него к выходам выбираем наименьшее. Соответствующий переход может принадлежать оптимальному пути. Узлу 8 приписываем этот переход и найденное минимальное время, которое обозначим как t ₈. Аналогично поступаем, фиксируя узел 9, а затем 10. В результате получим t ₉ и t ₁₀ соответственно и переходы, на которых достигаются эти минимальные значения времени. Тем самым завершается первый этап построения оптимального пути. Результат представлен на рис.9.3, где жирными линиями выделены оптимальные переходы.

Теперь полагаем, что осталось совершить 3-й и 4-й переходы. Но как и ранее, мы не знаем узел, с которого будем двигаться. Это снова вынуждает нас искать решение не для одного, а для всех узлов, в которые можем прийти после первых двух шагов. Фиксируем узел 4 и определяем минимальный путь из него к выходам. При полном переборе пришлось бы сопоставлять 12 вариантов (столько путей связывает узел 4 с выходами). Однако нам достаточно сравнить только три: 1)время на переходе 4-8 плюс t ₈; 2)время на переходе 4-9 плюс t ₉; 3)время на переходе 4-10 плюс t ₁₀. Минимальное значение приписываем узлу 4 (t ₄) и выделяем жирной линией соответствующий переход на третьем шаге. Здесь уже проявилась принципиальная особенность ДП: оптимальный переход на шаге 3 определялся не как самый короткий среди переходов этого шага, а как такой, который обеспечивает минимум времени от данного узла к выходу. Это значит, что выбирая решение на 3-м шаге, мы учитывали его последствия. Точно так же находим решения для узлов 5, 6 и 7. Возможные результаты после второго этапа решения приведены на рис.9.4.

Рис. 9.4

Опираясь на них, можно переходить к третьему этапу построения оптимального пути, охватывающему 2, 3 и 4-й шаги. Рассуждения аналогичны вышеприведенным. Например, оптимальный переход на 2-м шаге из узла 1 определяется по минимуму из четырех значений:

 

.

 

Переход, которому соответствует t ₁, и будет наилучшим для узла 1. И снова отметим: выбор перехода на одном 2-м шаге проводился с учетом влияния на последующие шаги вплоть до выхода! Нетрудно подсчитать, что при полном переборе путей из узла 1 к выходам пришлось бы сравнить 48 значений, каждое из которых вычисляется как сумма трех чисел. После завершения третьего этапа расчетов будут определены оптимальные пути из узлов 1-3 (рис.9.5).

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

 

 

Рис. 9.5

 

Найдя решение для 1-го шага, мы тем самым завершаем построение оптимальных путей (рис.9.6). Непрерывная жирная линия, соединяющая заданный вход с выходом, и есть оптимальный путь, а соответствующее ему минимальное время равно t _вх. Двигаясь по нему от входа к выходу, то есть в прямом направлении (или, иначе говоря, в направлении, обратномпорядку расчета), последовательно находим переходы, составляющие оптимальный путь.

 

 

Рис. 9.6

 

Этот пример иллюстрирует основные черты метода ДП:

1. Вместо одной задачи решается 4 однотипных задачи меньшей размерности. Если каждому шагу поставить в соответствие одну переменную, а переходу - ее значение, то исходная задача - это задача оптимизации с четырьмя переменными. В рассмотренной процедуре расчета она заменяется последовательностью четырех задач с одной переменной, что существенно облегчает решение.

2. Решение каждой из этих задач опирается на результаты решения предшествующей (в смысле порядка расчета) задачи. Связь задач осуществляется через состояние, которое есть, с одной стороны, результат выбора конкретного перехода на данном шаге, с другой - исходная информация для извлечения результата решения непосредственно предшествующей задачи. Из такого смысла состояния следует, что каждая задача должна решаться для всехсостояний, с которых может начаться рассматриваемый шаг. В нашем примере состояние полностью описывается номером узла или входа, и на каждом этапе мы искали решение для всех возможных узлов, так как иначе нельзя было бы приступить к следующему этапу расчета. Такую схему расчета называют условной оптимизацией. Это название подчеркивает, что на каждом шаге при выборе оптимального решения оговаривается условие, а именно, состояние, относительно которого ищется решение.

3. При заданном исходном состоянии, то есть для известного входа, выделение оптимальных переходов на каждом шаге не требует оговаривать условия: заданный вход определяет оптимальный переход на 1-м шаге, его результатом будет состояние накануне 2-го шага, по которому определяется оптимальный переход на 2-м шаге, приводящий в состояние, из которого совершается оптимальный переход на 3-м шаге и так до выхода. Определение оптимального решения для заданного исходного состояния по результатам условной оптимизации, осуществляемое в направлении, обратном условной оптимизации, в динамическом программировании называют безусловной оптимизацией.

4. Как видно из рис.9.6, значительная часть выделенных жирной линией переходов не входит в оптимальные пути, что на первый взгляд кажется существенным недостатком метода, так как соответствующие расчеты сделаны впустую. Однако более глубокий анализ показывает, что этот недостаток метода оборачивается его достоинством. Действительно, при реализации оптимальных решений нередки отклонения от первоначальных условий, что приводит систему в состояние, отличное от предусмотренного найденным решением. В этом случае при любом другом методе пришлось бы решать задачу заново, в то время как в результатах условной оптимизации ДП уже содержатся оптимальные решения для всех возможных состояний и поэтому достаточно выполнить лишь безусловную оптимизацию для нового состояния.

Уяснение рассмотренного примера и выводов по нему очень важно для понимания всего последующего материала.

Функциональное уравнение ДП

Теперь от описательного представления метода перейдем к формализованному. Рассмотрим достаточно общую многошаговую задачу, к которой применим метод ДП. Чтобы не путаться с различной нумерацией шагов и этапов расчета, пронумеруем шаги в порядке проведения условной оптимизации, в данной задаче с конца к началу. Эффективность i -го шага описывается функцией Z_i ( S_i,U_i ), где S_i - состояние к i -му шагу (точнее - вектор параметров состояния), U_i - управление на i -м шаге (точнее - вектор управляемых переменных или решение). Тогда структуру задачи можно представить так, как показано на рис.9.7.

 

Рис. 9.7

 

Модель задачи ДП включает целевую функцию

, (9.1)

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

Формализация вычислительной процедуры метода ДП базируется на принципе оптимальности. Напомним, что суть его состоит в том, что последующие решения должны быть оптимальными относительно состояния, сложившегося в результате предшествующих, пусть и не оптимальных, решений. Для описания этого свойства введем после­довательность функций { f_k ( S_k )}, так, что каждая из них есть зависимость экстремального значения критерия за k оставшихся шагов от состояния на начало k -го шага:

. (9.2)

Какие шаги охватывает каждая функция введенной последовательности, видно также на рис.9.7. Если бы мы использовали прямую нумерацию шагов, то в формуле (9.2) суммирование должно быть от k до N, и функция f_k охватывала бы N-k шагов, что, на наш взгляд, менее предпочтительно при интерпретации ее смысла. Важно уяснить, что функции (9.2) зависят только от состояния и не могут зависеть от искомых переменных (управлений), так как по ним ищется экстремум. Отсюда также следует еще один способ определения состояния: состояние - это то, от чего зависит экстремум критерия.

Теперь построим рассуждения на основе принципа оптимальности. Предположим, что осталось k шагов (k і2), на которых предстоит принять решение, и S_k - состояние, сложившееся к k -му шагу (см. рис.9.7). Выделим один k -й шаг и из допустимых управлений на этом шаге возьмем произвольное U_k. Тогда эффективность шага составит Z_k (S_k, U_k), а состояние, в которое придем в результате такого выбора, будет S_{k -1}. Согласно принципу оптимальности не имеет значения, как мы попали в это состояние - последующие решения, то есть решения на оставшихся (k -1) шагах, должны быть оптимальны относительно этого состояния. Но при оптимальных решениях на (k -1) шагах будет достигаться экстремальное значение критерия за все эти шаги, которое по определению (9.2) равно f_{k - 1} ( S_{k -1}). Следовательно, эффективность k шагов составит

. (9.3)

Очевидно, что она не является экстремальной для k шагов, так как U_k взято произвольно. Если воспользоваться уравнением состояния, то (9.3) примет вид

, (9.4)

из чего следует, что при фиксированном состоянии S_k эффективность k шагов зависит только от управления на одном k -м шаге (здесь полезно найти аналогию с задачей о лабиринте). В этом главный смысл метода ДП. Значит, варьируя U_k в допустимой области, можно найти экстремум выражения (9.4). Но экстремальное значение за k шагов по определению (9.2) есть f_k (S_k). Таким образом, окончательно получаем

(9.5)

 

Выражение (9.5) называется основным функциональным уравнением динамического программирования. Чтобы подчеркнуть специфическую структуру этого выражения, его также называют рекуррентным соотношением. Действительно, согласно (9.5) одна функция последовательности вычисляется через другую, непосредственно ей предшествующую. Поэтому вычисления f_k возможны только после того, как будут известны значения f_{k -1} для всех возможных состояний S_{k -1}. Чтобы начать рекуррентные вычисления, необходимо иметь первую функцию последовательности. Она находится непосредственно по определению (9.2) для k =1:

. (9.6)

После вычисления f ₁, используя (9.5), последовательно находим f ₂, f ₃,..., f_N. При этом каждая функция f_k () вычисляется для всех возможных состояний S_k. Результаты вычислений представляются в таблицах одинаковой структуры, включающей состояние, условно оптимальные значения переменных (компоненты вектора U_k ^*) и значение функции. Число строк в таблице равно числу состояний, возможных к данному шагу. Следует заметить, что в процессе расчета f_k допустимое множество D_k изменяется, так как оно зависит от состояния S_k, на что будет обращено внимание в следующих задачах.

Теперь по заданному состоянию S_N ^{^}входим в N -ю таблицу и из нее извлекаем U_N ^* и f_N (S_N ^{^}). Зная S_N ^{^} и U_N ^*, по уравнению состояния находим S_{N -1}^{^} и по нему входим в (N -1)-ю таблицу, откуда берем U_{N -1}^* и f (S_{N -1}^{^}). Этот прямой ход, соответствующий безусловной оптимизации, продолжаем аналогичным образом вплоть до 1-й таблицы, из которой найдем U_i ^* и f_i (S_i ^{^}). Очевидно, что f_N (S_N ^{^}) - это и есть оптимум нашей задачи, а соответствующие U ₁^*, U ₂^*,..., U _n^* - ее оптимальное решение. Таким образом, метод ДП позволил заменить задачу с N векторами переменных N задачами с одним искомым вектором каждая, что существенно облегчило решение.

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

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

2. Определяем параметры состояния и вводим последовательность функций { f_k (S_k)}, , в которой каждая функция f_k (S_k) есть наилучшее значение критерия за k оставшихся шагов относительно состояния S_k.

3. На основе принципа оптимальности составляем функциональное уравнение ДП и отдельно выражение для f ₁.

9. Проводим условную оптимизацию, последовательно вычисляя f ₁, f ₂,..., f_N. При этом на каждом шаге для всех возможных значений состояния S_k запоминаются значения U_k ^* и f_k (в таблице или файле).

5.Исходя из заданного состояния S_N ^{^}, проводим безусловную оптимизацию по схеме:

S_N ^{^}®табл. N ® U_N ^*®у.с.® S_{N -1}^{^}®табл. N -1® U_{N -1}^*®у.с.®...® S ₁^{^}®табл.1® U ₁^*,

где у.с. - уравнение состояния. Значение f_N (S_N) из N -й таблицы есть оптимальное значение критерия задачи.

Отметим, что при прямой нумерации шагов рекуррентная формула (9.5) связывала бы f_k с f_{k +1}, а в процедуре ДП следовало бы заменить нумерацию элементов и таблиц на обратную.