Значение ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ в Большой советской энциклопедии, БСЭ

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

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

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

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

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

xi xi ( yi , xi-1 ).

Т. о., управление у 1, у 2, ..., уm переводит систему из начального состояния x 0 в конечное хm . Требуется выбрать x 0 и у 1, ..., уm таким образом, чтобы целевая функция F åmi1 j i ( x i-1, yi ) достигла максимального значения F* . Основным методом Д. п. является сведение общей задачи к ряду более простых экстремальных задач. Пользуясь так называемым принципом оптимальности, сформулированным американским математиком Р. Беллманом, легко получить основное функциональное уравнение:

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

f1 ( x0 ) F* ,

где

( k 1, ..., m ).

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

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

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

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

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

Большая советская энциклопедия, БСЭ.