Динамічне програмування, розділ математики, присвячений теорії і методам вирішення багатокрокових завдань оптимального управління .
В Д. п. для керованих процесів серед всіх можливих управлінь шукається те, яке доставляє екстремальне (найменше або найбільше) значення цільової функції, — деякій числовій характеристиці процесу. Під многошаговостью розуміють або багатоступінчасту структуру процесу, або розбиття управління на ряд послідовних етапів (кроків), відповідних, як правило, різним моментам часу. Т. о., в назві «Д. п.» під «програмуванням» розуміють «ухвалення рішень», «планерування», а слово «динамічне» вказує на істотну роль часу і порядку виконання операції в даних процесах і методах.
Методи Д. п. є складеній частиною методів, використовуваних в дослідженні операцій (див. Операцій дослідження ), і застосовуються як в завданнях оптимального планерування, так і при вирішенні різних технічних проблем (наприклад, в завданнях визначення оптимальних розмірів рівнів багатоступінчастих ракет, в завданнях оптимального проектування прокладки доріг і ін.).
Хай, наприклад, процес управління деякою системою складається з m кроків (етапів), на i -м кроку управління y i переводить систему із стану x i-1 в новий стан x i , яке залежить від x i-1 і y i :
x i = x i ( y i , x i-1 ).
Т. о., управління в 1 , в 2 ..., у m переводить систему з початкового стану x 0 в кінцеве х m . Потрібно вибрати x 0 і в 1 ..., у m так, щоб цільова функція F = å m i=1 j i ( x i-1 , y i ) досягла максимального значення F* . Основним методом Д. п. є зведення загального завдання до ряду простіших екстремальних завдань. Користуючись так званим принципом оптимальності, сформульованим американським математиком Р. Беллманом, легко отримати основне функціональне рівняння:
і ( до = 2 ..., m - 1)
f 1 ( x 0 ) = F* ,
де
( до = 1 ..., m ).
Т. о., метод Д. п. приводить до необхідності вирішення цієї рекурентної системи функціональних рівнянь. У процесі рішення послідовність етапів проходітся двічі: у приведеному варіанті рекурентної системи вперше від кінця до початку (знаходяться оптимальні значення F* і х* 0 ), другий раз — від початку до кінця (знаходяться оптимальні управління в * 1 ..., у* m ).
Методи Д. п. знаходять вживання не лише в дискретних, але і в безперервних керованих процесах, наприклад в таких процесах, коли рішення треба приймати в кожен момент деякого інтервалу часу. Д. п. дало новий підхід до завдань варіаційного числення .
Хоча метод Д. п. істотно спрощує вихідні завдання, проте безпосереднє його вживання, як правило, зв'язане з громіздкими обчисленнями. Для подолання цих труднощів розробляються наближені методи Д. п.
Літ.: Беллман Р., Динамічне програмування, пер.(переведення) з англ.(англійський), М., 1960; Хедлі Дж., Нелінійне і динамічне програмування, пер.(переведення) з англ.(англійський), М., 1967.
