Тема 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)

Дата добавления: 2014-01-20