Глава 4. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

ПРОГРАММИРОВАНИЯ

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

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

(4.1.1)

Это и есть задача динамического программирования. В задаче (4.1.1) предполагается, что каждое из множеств и состоит из одной точки (из одного вектора), при этом целевая функция интерпретируется как суммарная прибыль, получаемая в результате функционирования системы на протяжении рассматриваемого отрезка времени. Отметим, что применение некоторых управлений может оказаться весьма дорогостоящим. Переменная в задаче (4.1.1) представляет собой вектор определяющий траекторию системы. Вектор определяет траекторию состояния системы, а вектор – траекторию управлений системой. Все переменные упорядочены (разнесены по времени) и это отражено в ограничениях задачи. Кроме того, рассматриваемая система является системой без последействия, так как очередное состояние, в которое она переходит, определяется только предыдущим шагом. При решении подобных задач важным является вид целевой функции. Использование сепарабельной целевой функции позволяет вместо решения задачи от большого числа переменных несколько раз решить задачу от одной переменной. Рассмотрим некоторые примеры задач, допускающих постановку в виде задачи динамического программирования.