ОБЩИЕ ПОНЯТИЯ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

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

Обозначим через х_k, управление на k-м шаге . Переменные х_k, удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (х_k может быть числом, точкой в n-мерном пространстве, качественным признаком).

Пусть - управление, переводящее систему s из состояния s₀ в состояние . Обозначим через s_k состояние системы после k-го шага управления. Получаем последовательность состояний которую изобразим кружками (рис. 5).

Рис. 5

Показатель эффективности рассматриваемой управляемой операции - целевая функция - зависит от начального состояния и управления:

(26)

Сделаем несколько предположений.

1. Состояние s_k системы в конце k-го шага зависит только от предшествующего состояния s_k-1 и управления на k-м шаге х_k, (и не зависит от предшествующих состояний и управлений). Это требование называется “отсутствием последействия”. Сформулированное положение записывается в виде уравнений

которые называются уравнениями состояний.

2. Целевая функция (26) является аддитивной от показателя эффективности каждого шага. Обозначим показатель эффективности k-го шага через тогда

(27)

Задача пошаговой оптимизации (задача ДП) формулируется так: определить такое допустимое управление х, переводящее систему s из состояния в s₀ в состояние , при котором целевая функция (27) принимает наибольшее (наименьшее) значение.

Выделим особенности модели ДП:

1. Задача оптимизации интерпретируется как n-шаговый процесс управления.

2. Целевая функция равна сумме целевых функций каждого шага.

3. Выбор управления на k-м шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (нет обратной связи).

4. Состояние s_k после k-го шага управления зависит только от предшествующего состояния s_k-1 и управления х_k (отсутствие последействия).

5. На каждом шаге управление х_k, зависит от конечного числа управляющих переменных, а состояние s_k - от конечного числа параметров.