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

Динамическое программирование - метод оптимизации, основанный на операциях, в которых процесс принятия решения может быть разбит на этапы (шаги). Такие операции называются многошаговыми. Начало развития динамического программирования относится к 50-м годам XX в. Оно связано с именем Р. Беллмана (Беллман Р.Э. (род. 1920 г.) – американский математик).

БЕЛЛМАН  Ричард Эрнст  (р. 26.08.1920) американский математик, один из ведущих специалистов в области математики и вычислительной техники. Род. в Нью-Йорке. Работает в Калифорнийском ун-те. Получил многочисленные результаты, связанные с применением динамического программирования в разных областях математики (вариационное исчисление, автоматическое регулирование, теория аппроксимации, исследование операций и др.). В вариационном исчислении важную роль играет функциональное уравнение Беллмана. В математических методах оптимального управления известны Беллмана функция и уравнение. Многие его книги и написанные им совместно с другими авторами переведены на русск. язык.

Модели динамического программирования применяются в экономике при решении задач небольшого масштаба, например, при разработке планов управления запасами, устанавливающими момент пополнения запасов и размер пополняющего запаса; при разработке календарных планов производства и занятости в условиях колеблющегося спроса на продукцию; при распределении капитальных вложений между возможными новыми направлениями их использования; при составлении календарных планов ремонта сложного оборудования и его замены; при разработке долгосрочных планов замены выбывающих из эксплуатации основных фондов и т. п.

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

Обозначим через Х_к управление на K^-том шаге (К=1, 2,..., n). Переменные X_к удовлетворяют некоторым ограничениям, т.е. являются допустимыми (X_к может быть числом, точкой в n-мерном пространстве, качественным признаком).

Пусть Х(Х₁ Х₂, ..., Х_n) - управление, переводящее систему S из состояния S_o в состояние S_i. Обозначим через S_k состояние системы после K^-того шага управления. Получаем последовательность состояний S₀, S₁ ..., S_k-1 S_k, ..., S_n-1, S_n=S_i

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

Z=F(S₀,X) (1)

Сделаем два предположения.

1. Состояние (S_k) системы в конце K^-го шага зависит только от предшествующего состояния S_k-1 и управления на K^-м шаге Х_к (и не зависит от предшествующих состояний и управлений). Это требование называется "отсутствием последействия". Сформулированное положение записывается в виде уравнений

, (2)

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

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

, (3)

тогда

(4)

Задача динамического программирования пошаговой оптимизации формулируется так: определить такое допустимое управление X, переводящее систему S из состояния S₀ в состояние S₁, при котором целевая функция (4) принимает наибольшее (наименьшее) значение.