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

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

Задача динамического программирования
Задача динамического программирования



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

Динамическое программирование – это математический метод поиска оптимального управления, специально приспособленный к многошаговым процессам. Рассмотрим пример такого процесса.

Пусть планируется деятельность группы предприятий на N лет. Здесь шагом является один год. В начале 1-го года на развитие предприятий выделяются средства, которые должны быть как-то распределены между этими предприятиями. В процессе их функционирования выделенные средства частично расходуются. Каждое предприятие за год приносит некоторый доход, зависящий от вложенных средств. В начале года имеющиеся средства могут перераспределяться между предприятиями : каждому из них выделяется какая-то доля средств.

Ставится вопрос : как в начале каждого года распределять имеющиеся средства между предприятиями, чтобы суммарный доход от всех предприятий за N лет был максимальным?

Перед нами типичная задача динамического программирования, в которой рассматривается управляемый процесс – функционирование группы предприятий. Управление процессом состоит в распределении (и перераспределении) средств. Управляющим воздействием (УВ) является выделене каких-то средств каждому из предприятий в начале года.

УВ на каждом шаге должно выбираться с учетом всех его последствий в будущем. УВ должно быть дальновидным, с учетом перспективы. Нет смысла выбирать на рассматриваемом шаге наилучшее УВ, если в дальнейшем это помешает получить наилучшие результаты других шагов. УВ на каждом шаге надо выбирать “c заглядыванием в будущее”, иначе возможны серьезные ошибки.

Действительно, предположим, что в рассмотренной группе предприятий одни заняты выпуском предметов потребления, а другие производят для этого машины. Причем целью является получение за N лет максимального объема выпуска предметов потребления. Пусть планируются капиталовложения на первый год. Исходя их узких интересов данного шага (года), мы должны были бы все средства вложить в производство предметов потребления, пустить имеющиеся машины на полную мощность и добиться к концу года максимального объема продукции. Но правильным ли будет такое решение в целом? Очевидно, нет. Имея в виду будущее, необходимо выделить какую-то долю средств и на производство машин. При этом объем продукции за первый год, естественно, снизится, зато будут созданы условия, позволяющие увеличивать ее производство в последующие годы.

В формализме решения задач методом динамического программирования будут использоваться следующие обозначения:

N – число шагов.

– вектор,описывающий состояние системы на k-м шаге.

– начальное состояние, т. е. cостояние на 1-м шаге.

– конечное состояние, т. е. cостояние на последнем шаге.

Xk – область допустимых состояний на k-ом шаге.

– вектор УВ на k-ом шаге, обеспечивающий переход системы из состояния xk-1 в состояние xk.

Uk – область допустимых УВ на k-ом шаге.

Wk – величина выигрыша, полученного в результате реализации k-го шага.

S – общий выигрыш за N шагов.

– вектор оптимальной стратегии управления или ОУВ за N шагов.

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

S1() – максимальный выигрыш, получаемый за N шагов при переходе системы из начального состояния в конечное

10 11 
Добавить в Одноклассники    

 

Rambler's Top100