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