§ 10.4. Метод динамического программирования. Теорема Болтянского. Метод Кротова

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

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

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

где — прямое произведение областей (множеств) определения функций

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

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

Очевидно,

Но второе слагаемое в последнем выражении есть поэтому функция Беллмана удовлетворяет функциональному уравнению

или, так как в данном случае не зависит от

причем

Решая (10.61) с учетом последнего условия, получим Решением исходной задачи будут

Как видно, метод динамического программирования сводит задачу минимизации скалярной функции от переменных к задачам минимизации скалярных функций от одной переменной. В результате при числовом решении задачи существенно сокращается объем вычислений. Действительно, пусть — конечные множества и каждое из них состоит из точек. Тогда при решении исходной задачи методом перебора без использования метода динамического программирования потребуется рассмотреть вариантов, а с использованием метода динамического программирования — всего вариантов.

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

изведем инвариантное погружение исходном задачи в семейство задач

где

При имеем . Введем функцию Беллмана

Очевидно,

или

Уравнение (10.62) есть обратное уравнение Беллмана, В рассмотренном простейшем примере вывод уравнения Беллмана основывался на очевидных соотношениях. В более сложном случае при выводе уравнения Беллмана используется принцип оптимальности.