Рефераты Динамическое программирование

Вернуться в Экономико-математическое моделирование

Динамическое программирование
Курсовая работа по теории оптимального управления экономическими системами.
Тема : Задача динамического программирования.

I.Основные понятия и обозначения.

Динамическое программирование – это математический метод поиска
оптимального управления, специально приспособленный к многошаговым
процессам. Рассмотрим пример такого процесса.
Пусть планируется деятельность группы предприятий на N лет. Здесь шагом
является один год. В начале 1-го года на развитие предприятий выделяются
средства, которые должны быть как-то распределены между этими
предприятиями. В процессе их функционирования выделенные средства частично
расходуются. Каждое предприятие за год приносит некоторый доход, зависящий
от вложенных средств. В начале года имеющиеся средства могут
перераспределяться между предприятиями : каждому из них выделяется какая-то
доля средств.
Ставится вопрос : как в начале каждого года распределять имеющиеся
средства между предприятиями, чтобы суммарный доход от всех предприятий за
N лет был максимальным?
Перед нами типичная задача динамического программирования, в которой
рассматривается управляемый процесс – функционирование группы предприятий.
Управление процессом состоит в распределении (и перераспределении) средств.
Управляющим воздействием (УВ) является выделене каких-то средств каждому из
предприятий в начале года.
УВ на каждом шаге должно выбираться с учетом всех его последствий в
будущем. УВ должно быть дальновидным, с учетом перспективы. Нет смысла
выбирать на рассматриваемом шаге наилучшее УВ, если в дальнейшем это
помешает получить наилучшие результаты других шагов. УВ на каждом шаге надо
выбирать “c заглядыванием в будущее”, иначе возможны серьезные ошибки.
Действительно, предположим, что в рассмотренной группе предприятий одни
заняты выпуском предметов потребления, а другие производят для этого
машины. Причем целью является получение за N лет максимального объема
выпуска предметов потребления. Пусть планируются капиталовложения на первый
год. Исходя их узких интересов данного шага (года), мы должны были бы все
средства вложить в производство предметов потребления, пустить имеющиеся
машины на полную мощность и добиться к концу года максимального объема
продукции. Но правильным ли будет такое решение в целом? Очевидно, нет.
Имея в виду будущее, необходимо выделить какую-то долю средств и на
производство машин. При этом объем продукции за первый год, естественно,
снизится, зато будут созданы условия, позволяющие увеличивать ее
производство в последующие годы.
В формализме решения задач методом динамического программирования будут
использоваться следующие обозначения:
N – число шагов.
[pic]– вектор,описывающий состояние системы на k-м шаге.
[pic]– начальное состояние, т. е. cостояние на 1-м шаге.
[pic]– конечное состояние, т. е. cостояние на последнем шаге.
Xk – область допустимых состояний на k-ом шаге.
[pic]– вектор УВ на k-ом шаге, обеспечивающий переход системы из
состояния xk-1 в состояние xk.
Uk – область допустимых УВ на k-ом шаге.
Wk – величина выигрыша, полученного в результате реализации k-го шага.
S – общий выигрыш за N шагов.
[pic]– вектор оптимальной стратегии управления или ОУВ за N шагов.
Sk+1([pic]) – максимальный выигрыш, получаемый при переходе из любого
состояния [pic][pic]в конечное состояние [pic] при оптимальной стратегии
управления начиная с (k+1)-го шага.
S1([pic]) – максимальный выигрыш, получаемый за N шагов при переходе
системы из начального состояния [pic] в конечное [pic] при реализации
оптимальной стратегии управления [pic]. Очевидно, что S = S1([pic]), если
[pic] –фиксировано.
Метод динамического программирования опирается на условие отсутствия
последействия и условие аддитивности целевой функции.
Условие отсутствия последействия. Состояние [pic], в которое перешла
система за один k-й шаг, зависит от состояния [pic] и выбранного УВ [pic] и
не зависит от того, каким образом система пришла в состояние [pic], то есть
[pic]

Аналогично, величина выигрыша Wk зависит от состояния [pic] и выбранного
УВ [pic], то есть
[pic]

Условие аддитивности целевой функции
Добавить в Одноклассники    

 

Rambler's Top100