змест | назад | далей | Гласарый паняццяў
Дынамічнае праграмаванне - гэта вылічальны метад для вырашэння задач пэўнай структуры. Паўстала і сфарміравалася ў 1950-1953 гг. дзякуючы працам Р. Беллмана над дынамічнымі задачамі кіравання запасамі. У простай фармулёўцы дынамічнае праграмаванне ўяўляе сабой накіраваны паслядоўны перабор варыянтаў, які абавязкова прыводзіць да глабальнага максімуму.
Асноўныя неабходныя ўласцівасці задач, да якіх магчыма ўжыць гэты прынцып:
- Задача павінна дапускаць інтэрпрэтацыю як n -шаговый працэс прыняцця рашэнняў.
- Задача павінна быць вызначана для любога ліку крокаў і мець структуру, не якая залежыць ад іх ліку.
Пры разглядзе k -шаговой задачы павінна быць зададзена некаторы мноства параметраў, якія апісваюць стан сістэмы, ад якіх залежаць аптымальныя значэння зменных. Прычым гэта мноства не павінна змяняцца пры павелічэнні колькасці крокаў.
Выбар рашэнні (кіравання) на k -м кроку не павінен аказваць ўплыву на папярэднія рашэньні, акрамя неабходнага пераліку зменных.
Задача аб выбары траекторыі, задача паслядоўнага прыняцця рашэння, задача аб выкарыстанні працоўнай сілы, задача кіравання запасамі - класічныя задачы дынамічнага праграмавання.
Пастаноўка задачы дынамічнага праграмавання.
Пастаноўку задачы дынамічнага праграмавання разгледзім на прыкладзе інвеставання, звязанага з размеркаваннем сродкаў паміж прадпрыемствамі. У выніку кіравання інвестыцыямі сістэма паслядоўна перакладаецца з пачатковага стану S0 У канчатковае Sn. Выкажам здагадку, што кіраванне можна разбіць на n крокаў і рашэнне прымаецца паслядоўна на кожным кроку, а кіраванне ўяўляе сабой сукупнасць n пакрокавых упраўленняў. На кожным кроку неабходна вызначыць два тыпу зменных - зменную стану сістэмы Sk зменную кіравання xk. Пераменная Sk вызначае, у якіх станах можа апынуцца сістэма на разгляданым k -м кроку. У залежнасці ад стану S на гэтым кроку можна прымяніць некаторыя кіравання, якія характарызуюцца зменнай xk якія задавальняюць вызначаным абмежаванням і называюцца дапушчальнымі. Дапусцім. 
= (X 1, x 2, ..., x k, ..., xn) - кіраванне, якое перакладае сістэму на стану S0 ў стан Sn, a Sk - ёсць стан сістэмы на k -м кроку кіравання. Тады паслядоўнасць станаў сістэмы можна прадставіць у выглядзе графа, прадстаўленага на мал. 2.11.
мал. 2.11
Прымяненне кіраўніка ўздзеянні xk на кожным кроку перакладае сістэму ў новы стан S1 (S, xk) і прыносіць некаторы вынік Wk (S, xk). Для кожнага магчымага стану на кожным кроку сярод усіх магчымых упраўленняў выбіраецца аптымальнае кіраванне x * k, такое, каб вынік, які дасягаецца за крокі з k -га па апошні n -й, апынуўся б аптымальным. Лікавая характарыстыка гэтага выніку называецца функцыяй Беллмана Fk (S) і залежыць ад нумара кроку k і стану сістэмы S. Задача дынамічнага праграмавання фармулюецца наступным чынам: патрабуецца вызначыць такое кіраванне 
, Якое перакладае сістэму з пачатковага стану S0 ў канчатковае стан Sn, пры якім мэтавая функцыя прымае найбольшую (найменшая) значэнне F (S 0, ) => Extr.
Разгледзім больш падрабязна асаблівасці матэматычнай мадэлі дынамічнага праграмавання:
- задача аптымізацыі фармулюецца як канчатковы шматкрокавая працэс кіравання;
- мэтавая функцыя (выйгрыш) з'яўляецца адытыўная і роўная суме мэтавых функцый кожнага кроку:
выбар кіравання xk на кожным кроку залежыць толькі ад стану сістэмы k гэтага кроку Sk-1, і не ўплывае на папярэднія крокі (няма зваротнай сувязі);
стан сістэмы Sk пасля кожнага кроку кіравання залежыць толькі ад папярэдняга стану сістэмы Sk-1 і гэтага кіраўніка ўздзеянні xh (адсутнасць паслядзеяння) і можа быць запісана ў выглядзе ўраўненні стану: Sk = fk (S k-1, xk), k = 1, n;
на кожным кроку кіраванне xk залежыць ад канчатковага ліку кіраўнікоў зменных, а стан сістэмы залежыць Sk - ад канчатковага ліку параметраў;
Прынцып аптымальнасці і матэматычнае апісанне дынамічнага працэсу кіравання.
У аснове метаду ДП ляжыць прынцып аптымальнасці, упершыню сфармуляваны ў 1953 г. амерыканскім матэматыкам Р.Э.Беллманом: якое б ні было стан сістэмы ў выніку якога-небудзь колькасці крокаў, на бліжэйшым кроку трэба выбіраць кіраванне так, каб яно ў сукупнасці з аптымальным кіраваннем на ўсіх наступных кроках прыводзіла да аптымальнага выйгрышу на ўсіх пакінутых кроках, уключаючы выйгрыш на дадзеным этапе. Пры вырашэнні задачы на кожным кроку выбіраецца кіраванне, якое павінна прывесці да аптымальнага выйгрышу. Калі лічыць усе крокі незалежнымі, тады аптымальным кіраваннем будзе тое кіраванне, якое забяспечыць максімальны выйгрыш менавіта на дадзеным этапе. Аднак, напрыклад, пры куплі новай тэхнікі ўзамен састарэлай на яе набыццё затрачваюцца пэўныя сродкі, таму даход ад яе эксплуатацыі ў пачатку можа быць невялікі, а ў наступныя гады новая тэхніка будзе прыносіць большы даход. І наадварот, калі прынята рашэнне пакінуць старую тэхніку для атрымання прыбытку ў бягучым годзе, то ў далейшым гэта прывядзе да значных страт. Гэты прыклад дэманструе наступны факт: у шматкрокавая працэсах кіраванне на кожным канкрэтным кроку трэба выбіраць з улікам яго будучых уздзеянняў на ўвесь працэс. Акрамя таго, пры выбары кіравання на дадзеным этапе варта ўлічваць магчымыя варыянты стану папярэдняга кроку. Напрыклад, пры вызначэнні колькасці сродкаў, якія ўкладаюцца ў прадпрыемства ў i -м годзе, неабходна ведаць, колькі сродкаў засталося ў наяўнасці да атаму годзе і які прыбытак атрыманы ў папярэднім (i - 1) -м годзе. Такім чынам, пры выбары крокавага кіравання неабходна ўлічваць наступныя патрабаванні:
- магчымыя зыходы папярэдняга кроку Sk-1;
- ўплыў кіравання xk на ўсе, што засталіся да канца працэсу крокі (nk).
У задачах дынамічнага праграмавання першае патрабаванне ўлічваюць, робячы на кожным кроку ўмоўныя здагадкі аб магчымых варыянтах заканчэння папярэдняга кроку і праводзячы для кожнага з варыянтаў ўмоўную аптымізацыю. Выкананне другога патрабаванні забяспечваецца тым, што ў гэтых задачах умоўная аптымізацыя праводзіцца ад канца працэсу да пачатку.
умоўная аптымізацыя
На першым этапе рашэння задачы, званым ўмоўнай аптымізацыяй, вызначаюцца функцыя Беллмана і аптымальныя кіравання для ўсіх магчымых станаў на кожным кроку, пачынаючы з апошняга ў адпаведнасці з алгарытмам зваротнай прагонку. На апошнім, n -м кроку аптымальнае кіраванне - х * n вызначаецца функцыяй Беллмана: F (S) = max {W n (S, xn)}, у адпаведнасці з якой максімум выбіраецца з усіх магчымых значэнняў xn, прычым xn € X.
Далейшыя вылічэнні вырабляюцца згодна рэкурэнтнага суадносінах, які злучае функцыю Беллмана на кожным кроку з гэтай жа функцыяй, але вылічанай на папярэднім кроку. У агульным выглядзе гэта раўнанне мае выгляд Fn (S) = max {W n (S, xn) + F k + 1 (S n (S, xk)} xk € X.
Гэты максімум (або мінімум) вызначаецца па ўсіх магчымых для k і S значэнняў зменнай кіравання X.
безумоўная аптымізацыя
Пасля таго, як функцыя Беллмана і адпаведныя аптымальныя кіравання знойдзены для ўсіх крокаў з n -га па першы, ажыццяўляецца другі этап рашэння задачы, званы безумоўнай аптымізацыяй. Карыстаючыся тым, што на першым кроку (k = 1) стан сістэмы вядома - гэта яе зыходны стан S0, можна знайсці аптымальны вынік за ўсё n крокаў і аптымальнае кіраванне на першым кроку x1, якое гэты вынік дастаўляе. Пасля ўжывання гэтага ўпраўлення сістэма пяройдзе ў іншы стан S1 (S, x * 1), ведаючы якое, можна, карыстаючыся вынікамі ўмоўнай аптымізацыі, знайсці аптымальнае кіраванне на другім кроку x * 2, і гэтак далей да апошняга n -га кроку. Вылічальную схему дынамічнага праграмавання можна будаваць на сеткавых мадэлях, а таксама па алгарытмах прамой прагонку (ад пачатку) і зваротнай прагонку (ад канца да пачатку). Разгледзім прыклады рашэння розных па сваёй прыродзе задач, змест якіх патрабуе выбару зменных стану і кіравання.
змест | назад | далей | Гласарый паняццяў
