ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ - раздел математики, посвященный теории и методам решения многошаговых задач оптимального управления.

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

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

Проиллюстрируем основную идею. Пусть процесс управления нек-рой системой X состоит из m шагов (этапов); на i-м шаге управление y_i переводит систему из состояния x_i-1, достигнутого в результате (i-1)-го

шага, в новое состояние x_i. Этот процесс перехода осуществляет заданная функция f_i(x, у), и новое состояние определяется значениями x_i-1, y_i:

x_i = f_i(x_i-1, y_i),

Таким образом, управления у₁, у₂, ... , у_m переводят систему из начального состояния х₀ ∈ Х₀ в конечное - х_m ∈ X_m, где Х₀ и Х_m - совокупности допустимых начальных и конечных состояний системы X. Опишем одну из возможных постановок экстремальной задачи. Начальное состояние х₀ задано. Требуется выбрать управления у₁, у₂, ..., у_m таким образом, чтобы система X перешла в допустимое конечное состояние и при этом заданная целевая функция F(x₀, y₁, x₁, у₂, ... , у_m, х_m) достигла максимального значения F*, т. е.

F* = max_y1,y2,...,ym F(х₀, у₁, x₁, у₂, ..., у_m, х_m).

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

F = φ_i(x_i-1, y_i).

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

x_i = f_i (x_i-1, y_i, x_i-2, y_i-1, ..., y₁, x₀),

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

Для решения задач Д. п. обычные методы математического анализа либо вообще неприменимы, либо приводят к огромному числу вычислений. В основе метода Д. п. лежит принцип оптимальности, сформулированный Р. Беллманом (R. Bellman): предположим, что осуществляя управление дискретной системой X, мы уже выбрали некоторые управления дискретной системой у₁, у₂, ..., y_k и тем самым траекторию состояний х₀, х₁, ... , х_k, и хотим завершить процесс, т. е. выбрать y_k+1, y_k+2, ..., y_m (а значит и x_k+1, x_k+2, ..., x_m); тогда, если завершающая часть

процесса не будет оптимальной в смысле достижения максимума функции

F_k = φ_i(x_i-1, y_i),

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

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

ω_m(х) = 0, ω_k-1(х) = max_y [φ_k(х, у) + ω_k(f_k(х, у))],

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

ω₀(х₀) = F*, y₁, х₁, y₂, ..., у_m, х_m.

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

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

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

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

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

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

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

Источники:

1. Математическая энциклопедия: Гл. ред. И. М. Виноградов, т. 2 Д - Коо.-М.: «Советская Энциклопедия», 1979.-1104 стб., ил.