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

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

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

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

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

x_i = x_i(y_i, x_i-1).

Т. о., управление у₁, у₂, ..., у_m переводит систему из начального состояния x₀ в конечное х_m. Требуется выбрать x₀ и у₁, ..., у_m таким образом, чтобы целевая функция F = ∑^m_i=1 φ_i (x_i-1, y_i) достигла максимального значения F*. Основным методом Д. п. является сведение общей задачи к ряду более простых экстремальных задач. Пользуясь так называемым принципом оптимальности, сформулированным американским математиком Р. Беллманом, легко получить основное функциональное уравнение:

и (k = 2, ..., m - 1)

f₁(x₀) = F*,

где

(k = 1, ..., m).

Т. о., метод Д. п. приводит к необходимости решения этой рекуррентной системы функциональных уравнений. В процессе решения последовательность этапов проходится дважды: в приведённом варианте рекуррентной системы в первый раз от конца к началу (находятся оптимальные значения F* и х*₀), второй раз — от начала к концу (находятся оптимальные управления y*₁, ..., у*_m).

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

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

Лит.: Беллман Р., Динамическое программирование, пер. с англ., М., 1960; Хедли Дж., Нелинейное и динамическое программирование, пер. с англ., М., 1967.

В. Г. Карманов.

dynamic programming

dynamic programming матем.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

dynamic programming матем.

* * *

dynamic programing

динамі́чне програмува́ння

динамі́чне програмува́ння