Тема 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
0	0	0	0
100	30	50	40
200	50	80	50
300	90	90	110
400	110	150	120
500	170	190	180
600	180	210	220
700	210	220	240

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

Решение

Сначала поставленную задачу нужно рассмотреть как многошаговую. Будем рассматривать эффективность вложения средств на одном (например, первом предприятии), на двух предприятиях (первое и второе) и, наконец, на трех предприятиях вместе. Если млн. руб. – это капиталовложения в j-ое предприятие (j = 1,2,3), то задача состоит в определении наибольшего значения функции при условии .

Рекуррентное соотношение Беллмана в нашем случае приводит к следующим функциональным уравнениям:

Здесь функция определяет максимальный прирост выпуска продукции при выделении X млн. рублей капиталовложений первому предприятию. определяет максимальный выпуск продукции при распределении X млн. рублей между первым и вторым предприятиями. – максимальный прирост при выделении всем трем предприятиям  млн. рублей.