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

Динамическим программированием называют разработанный Р. Веллманом в начале 50-х годов прошлого столетия метод оптимизации многошаговых процессов различной природы. Основу динамического программирования как метода оптимизации составляют [8, 19]: 1) принцип оптимальности; 2) инвариантное погружение, т. е. включение исходной задачи в семейство аналогичных задач; 3) функциональное уравнение, получаемое на основе принципа оптимальности и инвариантного погружения.

Инвариантное погружение и функциональное уравнение.

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

Проиллюстрируем сказанное на простейшем примере [19). Пусть требуется найти минимум функции /(х) специального вида:

Здесь Gⁿ — прямое произведение областей (множеств) Gi определения функций fi (xi):

Рассмотрим семейство задач.

где x*^m) = (xi Х2 … х_т)^т и G^m = G х G₂ * • • • х G_m. Исходная задача погружена (инвариантное погружение) в построенное семейство задач в том смысле, что она входит в это семейство как частный случай при m = п. В задаче (9.42) параметр m можно рассматривать как дискретное время. Введем в рассмотрение функцию

Эту функцию называют функцией Веллмана.

Очевидно, справедливо следующее соотношение:

Но второе слагаемое в последнем выражении есть В_т, поэтому получаем следующее функциональное уравнение:

или, так как в данном случае В_т не зависит от i_m+i, причем Уравнение (9.43) называют уравнением Веллмана. Решая его с учетом последнего условия, получим В, В₂, • •., В_п и х, xj,…, х*_п. Решением исходной задачи являются В_п и х* = (zj хJ … х*)^г.

Как видно, метод динамического программирования сводит задачу минимизации скалярной функции от п переменных к п задачам минимизации скалярных функций от одной переменной. В результате при числовом решении задачи существенно сокращается объем вычислений. Действительно, пусть G, (i = 1,2,…, п) — конечные множества и каждое из них состоит из I точек. Тогда при решении исходной задачи методом перебора без использования метода динамического программирования потребуется рассмотреть 1^п вариантов, а с использованием метода динамического программирования — всего /•п вариантов.

При использовании уравнения (9.43) вычисление В_т происходит в направлении возрастания аргумента, т. е. в прямом «времени», поэтому это уравнение называют прямым уравнением Веллмана в отличие от обратного уравнения Веллмана, при использовании которого вычисление В_т производится в направлении убывания времени.

Для получения обратного уравнения Веллмана произведем инвариантное погружение исходной задачи в семейство задач.

где.

Очевидно, имеем или.

Последнее уравнение есть обратное уравнение Веллмана.