ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
Динамическое программирование (ДП) – это метод нахождения оптимальных решений в задачах с многошаговой (многоэтапной) структурой.
Приведем общую постановку задачи ДП. Рассматривается управляемый процесс (распределение средств между предприятиями, использование ресурсов в течение ряда лет и т.п.). В результате управления система (объект управления) переводится из начального состояния в состояние . Предположим, что управление можно разбить на шагов. На каждом шаге выбирается одно из множества допустимых управлений , переводящее систему в одно из состояний множества . Элементы множества и определяются из условий конкретной задачи. Последовательность состояний системы можно изобразить в виде графа состояний, представленного на рис. 2.
Рис. 2
На каждом шаге n достигается эффект . Предположим, что общий эффект является суммой эффектов, достигнутых на каждом шаге. Тогда задача ДП формулируется так: определить такое допустимое управление , переводящее систему из состояния в состояние , при котором функция цели принимает наибольшее (наименьшее) значение, т.е.
Решение задач методом ДП осуществляется на основе принципа оптимальности, который был сформулирован американским ученым Р.Беллманом: каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.
|
|
Обозначим через условно-оптимальное значение целевой функции на интервале от шага n до последнего -го шага включительно, при условии, что перед n-ым шагом система находилась в одном из состояний множества , а на n-ом шаге было выбрано такое управление из множества , которое обеспечило целевой функции условно-оптимальное значение, тогда условно-оптимальное значение целевой функции в интервале от (n +1)-го до -го шага включительно.
В принятых обозначениях принцип оптимальности Беллмана можно записать в математической форме следующим образом
. (4.1)
Равенство (4.1) называется основным функциональным уравнением динамического программирования. Для каждой конкретной задачи уравнение имеет особый вид.
Вычислительная процедура метода ДП распадается на два этапа: условную и безусловную оптимизацию.
На этапе условной оптимизации в соответствии с функциональным уравнением определяются оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего.
На этапе безусловной оптимизации шаги рассматриваются, начиная с первого. Поскольку исходное состояние известно, выбирается оптимальное управление из множества . Выбранное оптимальное управление приводит систему во вполне определенное состояние . Благодаря тому, что исходное состояние в начале второго шага известно, становится возможным выбрать оптимальное управление на втором шаге и т.д. Таким образом, строится цепь взаимосвязанных решений безусловной оптимизации.
|
|
Рассмотрим интерпретацию приведенного выше итерационного процесса на следующем примере.
Дата добавления: 2018-09-20; просмотров: 316; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!