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

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

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

Рисунок 4.1

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

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

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

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

. (4.1)

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

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

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

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