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

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

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

Методы Д. п. являются составной частью методов, используемых в исследовании операций, и применяются в задачах оптимального планирования (напр., в задачах об оптимальных распределениях ресурсов, в теории управления запасами, в задачах замены оборудования и т. д.) и при решении многих технических проблем (напр., в задачах управления последовательными химическими процессами, в задачах оптимального проектирования прокладки дорог и др.).

Проиллюстрируем основную идею. Пусть процесс управления нек-рой системой Xсостоит из тшагов (этапов); на i-м шаге управление yi переводит систему из состояния xi-1, достигнутого в результате (i-1)-го шага, в новое состояние ж,-. Этот процесс перехода осуществляет заданная функция fi(x, у), и новое состояние определяется значениями xi-1, yi :

Таким образом, управления у 1, у 2,... , у т переводят систему из начального состояния в конечное где Х 0 и Х тсовокупности допустимых начальных и конечных состояний системы X. Опишем одну из возможных постановок экстремальной задачи. Начальное состояние х 0 задано. Требуется выбрать управления у 1, у 2, ..., у т таким образом, чтобы система Xперешла в допустимое конечное состояние и при этом заданная целевая функция F(x0, у1,x1, у 2, ... , у т, х т )достигла максимального значения F*, т. е.

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

Кроме того, в методе Д. п. требуется, чтобы задача характеризовалась отсутствием "последействия": решения (управления), принимаемые на шаге, оказывают влияние только на состояние х i системы в момент i. Другими словами, процессы, описываемые функциями вида не рассматриваются. Оба упомянутых ограничительных условия можно ослабить, но только за счет существенного усложнения метода.

Для решения задач Д. п. обычные методы математического анализа либо вообще неприменимы, либо приводят к огромному числу вычислений. В основе метода Д. п. лежит принцип оптимальности, сформулированный Р. Беллманом (R. Bellman): предположим, что осуществляя управление дискретной системой X, мы уже выбрали некоторые управления дискретной системой у 1, у 2, ... , у k тем самым траекторию состояний х 0, х 1, . . . , xk, и хотим завершить процесс, т. е. выбрать yk+ 1, yk+2,... , у т (а значит и xk+ 1,xk+ 2, ...,xm);тогда, если завершающая часть процесса не будет оптимальной в смысле достижения максимума функции

то и весь процесс не будет оптимальным.

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

k=1,2, ... , т. Здесь максимум берется по всем управлениям, допустимым на шаге к. Соотношение, определяющее зависимость wk-1 от wk, принято называть Беллмана уравнением. Смысл функций wk-1 (х). нагляден: если система на шаге k-1 оказалась в состоянии х, то wk-1(x) есть максимально возможное значение функции F. Одновременно с построением функций wk-1 (х). находятся условные оптимальные управления yk (х)на каждом шаге (т. е. значения оптимального управления при всевозможных предположениях о состоянии хсистемы на шаге k-1). Окончательно оптимальные управления находятся последовательным вычислением величин

Из сказанного очевидна следующая особенность метода Д. п.с его помощью решается не одна конкретная задача при определенном х 0, а сразу все подобные однотипные задачи при любом начальном состоянии. Поскольку численная реализация метода Д. п. весьма сложна, т. к. требует большого объема памяти ЭВМ, то его целесообразно применять в тех случаях, когда необходимо многократно решать типовые задачи (скажем, определение оптимального режима полета самолета при меняющихся погодных условиях). Несмотря на то, что задача Д. п. формулируется для дискретных процессов, в ряде случаев метод Д. п. с успехом применяется для решения динамических задач с непрерывными параметрами.

Д. п. дало новый подход ко многим задачам вариационного исчисления..

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

Метод Д. п. был предложен Р. Беллманом. Строгое обоснование метода Д. п. было получено в результате работ Л. С. Понтрягина и его учеников по математической теории управляемых процессов (см. Оптимального управления математическая теория).

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

Лит.:[1] Беллман Р., Динамическое программирование, пер. с англ., М., 1960; [2] Болтянский В. Г., Математические методы оптимального управления, М., 1966; [3] Xедли Д т.. Нелинейное и динамическое программирование, пер. с англ., М., 1967; [4] Xедли Д ж., Уайтин Т., Анализ систем управления запасами, пер. с англ., М., 1969; [5] Xовард Р. А., Динамическое программирование и марковские процессы, пер. с англ., М., 1964.

С. А. Ашманов, В. Г. Карманов.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985