Тема 4 динамическое программирование

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

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

Рисунок 2 – Граф состояний

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

Решение задач методом ДП осуществляется на основе принципа оптимальности, который был сформулирован американским ученым

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

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

В принятых обозначениях принцип оптимальности Беллмана можно записать в математической форме следующим образом:

, (4.1)

Равенство (4.1) называется основным функциональным уравнением динамического программирования. Для каждой конкретной задачи уравнение имеет особый вид.

Вычислительная процедура метода ДП распадается на два этапа: условную и безусловную оптимизацию.

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

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

Рассмотрим интерпретацию приведенного выше итерационного процесса на следующем примере.

Пример 9 Задача оптимального распределения капиталовложений

Для увеличения объемов выпуска пользующейся повышенным спросом продукции трем предприятиям выделены капиталовложения в размере 700 млн. руб. Каждому из предприятий может быть выделено капиталовложений в размере 0, 100, 200, 300, 400, 500, 600, 700 млн. руб. При этом прирост выпуска продукции каждым из предприятий в зависимости от капиталовложений известно и приведено в таблице 21.

Таблица 21

Объем капиталовложений (млн. руб.)	Прирост выпуска продукции (млн. руб.) в зависимости от объема капиталовложений
Предприятие 1	Предприятие 2	Предприятие 3

Найти распределение капиталовложений между предприятиями, обеспечивающее максимальное увеличение выпуска продукции.

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