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

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

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

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

Пусть, напр., процесс управления нек-рой
системой состоит из т шагов (этапов), на i-м шагу управление
упереводит
систему из состояния xв новое состояние
xк-рое зависит oт хи у

Т. о., управление y,
у..., yпереводит систему из начального состояния хв
конечное хТребуется выбрать х..., утаким образом, чтобы целевая



макс, значения F*. Осн. методом Д. п.
является сведение общей задачи к ряду более простых экстремальных задач.
Пользуясь т. н. принципом оптимальности, сформулированным амер. математиком
Р. Беллманом, легко получить осн. функциональное ур-ние:

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

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

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

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

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