Динамическое программирование

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

S_k+1(

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

S₁(

)– максимальныйвыигрыш, получаемыйза Nшагов припереходе системыиз начальногосостояния в конечное при реализацииоптимальнойстратегииуправления .Очевидно, чтоS = S₁( ),если –фиксировано.

Методдинамическогопрограммированияопирается наусловие отсутствияпоследействияи условиеаддитивностицелевой функции.

Условиеотсутствияпоследействия.Состояние

,в которое перешласистема за одинk-йшаг, зависитот состояния и выбранногоУВ и не зависитот того, какимобразом системапришла в состояние ,то есть

Аналогично,величина выигрышаW_kзависитот состояния

и выбранногоУВ ,то есть

Условиеаддитивностицелевой функции.Общий выигрышза Nшагов вычисляетсяпо формуле

Определение.Оптимальнойстратегиейуправления

называетсясовокупностьУВ ,то есть ,в результатереализациикоторых системаза Nшаговпереходит изначальногосостояния в конечное и при этом общийвыигрыш Sпринимаетнаибольшеезначение.

Условиеотсутствияпоследействияпозволяетсформулироватьпринцип оптимальностиБелмана.

Принципоптимальности.Каково бы нибыло допустимоесостояниесистемы

передочереднымi-мшагом, надовыбрать допустимоеУВ на этомшаге так, чтобывыигрыш W_iна i-мшаге плюс оптимальныйвыигрыш на всехпоследующихшагах былмаксимальным.

В качествепримера постановкизадачи оптимальногоуправленияпродолжимрассмотрениезадачи управленияфинансированиемгруппы предприятий.Пусть вначале i-гогода группепредприятий

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

Управлениеможет бытьхорошим илиплохим, эффективнымили неэффективным.Эффективностьуправления

оцениваетсяпоказателемS.Возникаетвопрос: каквыбрать шаговыеуправления ,чтобы величинаSобратиласьв максимум?

Поставленнаязадача являетсязадачей оптимальногоуправления,а управление,при которомпоказательSдостигаетмаксимума,называетсяоптимальным.Оптимальноеуправление

многошаговымпроцессомсостоит изсовокупностиоптимальныхшаговых управлений:

Таким образом,перед намистоит задача:определитьоптимальноеуправлениена каждом шаге

(i=1,2,...N)и, значит, оптимальноеуправлениевсем процессом .

II.Идеи методадинамическогопрограммирования

Мы отметили,что планируямногошаговыйпроцесс, необходимовыбирать УВна каждом шагес учетом егобудущих последствийна еще предстоящихшагах. Однако,из этого правилаесть исключение.Среди всехшагов существуетодин, которыйможет планироватьсябез "заглядыва-нияв будущее".Какой это шаг?Очевидно, последний— посленего другихшагов нет. Этотшаг, единственныйиз всех, можнопланироватьтак, чтобы онкак таковойпринес наибольшуювыгоду. Спланировавоптимальноэтот последнийшаг, можно кнему пристраиватьпредпоследний,к предпоследнему— предпредпоследнийи т.д.

Поэтому процессдинамическогопрограммированияна 1-м этаперазворачиваетсяот конца к началу,то есть раньшевсех планируетсяпоследний,

N-йшаг. А как егоспланировать,если мы не знаем,чем кончилсяпредпоследний?Очевидно, нужносделать всевозможныепредположенияо том, чем кончилсяпредпоследний,(N— 1)-й шаг, идля каждогоиз них найтитакое управление,при которомвыигрыш (доход)на последнемшаге был бымаксимален.Решив эту задачу,мы найдем условнооптимальноеуправление(УОУ) на N-мшаге, т.е. управление,которое надоприменить, если(N —1)-й шаг закончилсяопределеннымобразом.

Предположим,что эта процедуравыполнена, тоесть для каждогоисхода

(N— 1)-го шагамы знаем УОУна N-мшаге и соответствующийему условнооптимальныйвыигрыш (УОВ).Теперь мы можемоптимизироватьуправлениена предпоследнем,(N— 1)-м шаге. Сделаемвсе возможныепредположенияо том, чем кончилсяпредпредпоследпий,то есть(N— 2)-й шаг, идля каждогоиз этих предположенийнайдем такоеуправлениена (N —1)-м шаге, чтобывыигрыш запоследние двашага (из которыхпоследний ужеоптимизирован)был максимален.Далее оптимизируетсяуправ чениена (N —2)-м шаге, и т.д.

Одним словом,на каждом шагеищется такоеуправление,которое обеспечиваетоптимальноепродолжениепроцесса относительнодостигнутогов данный моментсостояния. Этотпринцип выборауправления, называетсяпринципомоптимальности.Само управление,обеспечивающееоптимальноепродолжениепроцесса относительнозаданногосостояния,называетсяУОУ на данномшаге.

Теперьпредположим,что УОУ на каждомшаге нам известно:мы знаем, чтоделать дальше,в каком бы состояниини был процесск началу каждогошага. Тогдамы можем найтиуже не "условное",а дейсгвительнооптимальноеуправлениена каждом шаге. |

Действительно,пусть нам известноначальноесостояниепроцесса. Теперьмы уже знаем,что делать напервом шаге:надо применитьУОУ, найденноедля первогошага и начальногососюяния. Врезультатеэтого управленияпосле первогошага системаперейдет вдругое состояние;но для этогосостояния мызнаем УОУ и гд. Таким образом,мы найдем оптимальноеуправлениепроцессом,приводящеек максимальновозможномувыигрышу.

Такимобразом, в процессеоптимизацииуправленияметодом динамическогопрограммированиямногошаговыйпроцесс "проходится"дважды:

— первыйраз — от концак началу, врезультатечего находятсяУОУ| на каждомшаге и оптимальныйвыигрыш (тожеусловный) навсех шагах, начиная с данногои до конца процесса;

• второйраз — от началак концу, в результатечего находятсяоптимальныеуправленияна всех шагахпроцесса.

Можносказать, чтопроцедурапостроенияоптимальногоуправления

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

предварительнуюи окончательную.На предварительнойстадии длякаждого шагаопределяетсяУОУ, зависящееот состояниясистемы (достигнутогов результатепредыдущихшагов), и условнооптимальныйвыигрыш навсех оставшихсяшагах, начинаяс данного, такжезависящий отсостояния. Наокончательнойстадии определяется(безусловное)оптимальноеуправлениедля каждогошага. Предварительная(условная)оптимизацияпроизводитсяпо шагам в обратномпорядке: отпоследнегошага к первому;окончательная(безусловная)оптимизация— также по шагам,но в естественномпорядке: отпервого шагак последнему.Из двух стадийоптимизациинесравненноболее важнойи трудоемкойявляется первая.После окончанияпервой стадиивыполнениевторой трудностине представляет:остается только"прочесть"рекомендации,уже заготовленныена первой стадии.

III. Примерзадачи динамическогопрограммирования

Выборсостава оборудованиятехнологическойлинии.

Естьтехнологическаялиния ,то есть цепочка,последовательностьопераций.

На каждуюоперацию можноназначитьоборудованиетолько каго-тоодного вида,а оборудования,способногоработать наданной операции, - нескольковидов.

Исходныеданные дляпримера

i	1		2		3
j	1	2	1	2	1	2
	10	8	4	5	8	9
	12	8	4	6	9	9
	20	18	6	8	10	12

Стоимостьсырья

Расходы, связанныес использованиемединицы оборудованияj-го типана i-ойоперации

Производительности,соответственно,по выходу ивходу

и для j-готипаоборудования,претендующегона i-уюоперацию.

Решение:

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

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

- Технологическаялиния.

= (0,0,0)

=( )

– выбороборудованиядля i-ойоперации.

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

т.е.

W_i– оценкаминимальнойсебестоимости,полученнаяв результатереализацииi-гошага.

S –функцияобщего выигрыша т.е. минимальнаясебестоимость.

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

- векторУВ на i-омшаге, обеспечивающийпереход системыиз состоянияx_i-1в состояниеx_{i ,}т.е.оптимальныйвыбор оборудованияза N шагов.

S_i+1(

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

S₁(

)– максимальныйвыигрыш, получаемыйза Nшагов припереходе системыиз начальногосостояния в конечное при реализацииоптимальнойстратегииуправления .Очевидно, чтоS = S₁( ),если =0.

Запишемвекторадопустимыхзначений

Запишемвектора допустимыхуправляющихвоздействий

З

апишем вектор– функцию,описывающуюпереход системыиз состояния всостояние под действиемУВ.

З

апишем основноефункциональноеуравнение

1)Обратныйпроход

Д

ля i=3

Учитываято, чтоэтот шаг у наспоследнийи следующейоперации

у

же не будет,а также то,что мы на обратномпроходе,вместо функции

возьмемстоимость сырья

при

=

при

=

т.е.

Для i=2

115,2

при

=

138,04

при

=

102,8

при

=

123,1

при

=

т.е.

Д

ля i=1

140,2

при

=

125,3

при

=

п

125,3

ри =

125,3

при

==

125,3

при

=

125,3

при

=

125,3

при

=

125,3

при

=

т.е.

2. П

   рямой проход

Учитываято,что и

=(0,0,0) имеем

i=1

i=2

i

=3

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

На 1-уюоперацию назначимоборудование2-го вида

На 2-уюоперацию назначимоборудование1-го вида

На 3-ьюоперацию назначимоборудование2-го вида

Оценкаминимальнойсебестоимостисоставит 105,5.

13

Разделколлекции :Экономико-математическоемоделирование

Автор: РодионовД.А.

Контактныесведения :dimarik@chel.ru

Наименованияработы :Динамическоепрограммирование

Видработы :курсовая работа

Пожелания: -