1.13. Метод динамического программирования

-----

 

-----

 

Глава 14
Метод динамического программирования как алгоритмическое выражение достаточно общей теории управления

 

В изложении существа метода динамического программирова-ния мы опираемся на книгу “Курс теории автоматического управ-ления” (автор Палю де Ла Барьер: французское издание 1966 г., русское издание — “Машиностроение”, 1973 г.), хотя и не повто-ряем его изложения. Отдельные положения взяты из курса “Ис-следование операций” Ю.П.Зайченко (Киев, “Вища школа”, 1979 г.).

Метод динамического программирования работоспособен, ес-ли формальная интерпретация реальной задачи позволяет выпол-нить следующие условия:

1. Рассматриваемая задача может быть представлена как N шаговый процесс, описываемый соотношением:
Xn + 1 = f(Xn, Un, n), где n — номер одного из множества воз-можных состояний системы, в которое она переходит по завер-шении n-ного шага; Xn — вектор состояния системы, принадлежа-щий упомянутому n-ному множеству; Un — управление, вырабо-танное на шаге n (шаговое управление), переводящее систему из возможного её состояния в n-ном множестве в одно из состояний (n + 1) го множества. Чтобы это представить наглядно, следует обратиться к рис. 4, о котором речь пойдет далее.

2. Структура задачи не должна изменяться при изменении рас-четного количества шагов N.

3. Размерность пространства параметров, которыми описыва-ется состояние системы, не должна изменяться в зависимости от количества шагов N.