Тема 6. Динамическое программирование

В реальных экономических задачах условия могут меняться. Поэтому возникает потребность влиять на меняющуюся ситуацию в течение всего процесса. Задачи оптимизации при данном условии называются задачами динамического программирования.

Принципы динамического программирования.

1. Весь процесс можно разбить на m шагов, будем говорить i-й шаг (i= ).

2. Известен критерий эффективности процесса за все m шагов - W, значение этого критерия будем называть выигрышем.

Известны выигрыши на i-м шаге - , (i= ).

3. Выигрыш - аддитивная функция, т.е.

Управляющие переменные. Обозначим через D - множество возможных управлений; X_i - управление на i -м шаге. Управлением процесса X, называется множество управлений на каждом шаге x₁, х₂,..., х_m, т.е.

4. Можно описать состояние процесса (системы) - S.

Пусть S - состояние системы перед i -м шагом, - функция перехода из состояния S под воздействием управления х_i, в новое состояние , т.е. .

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