7-мавзу. Динамик дастурлаш элементлари режа

7-мавзу. ДИНАМИК ДАСТУРЛАШ ЭЛЕМЕНТЛАРИ


Режа:

1. 
   Динамик дастурлаш ќаљида тушунчалар.
   
2. 
   Ресурсларнинг оптимал таљсимоти.
   
3. 
   Беллман функционал-экстремал тенгламаси.
   
4. 
   Динамик дастурлаш усули.
   
5. 
   Иљтисодиётга оид баъзи масалаларни динамик дастурлаш усули ёрдамида ечиш.
   

1. Динамик дастурлаш оптимал ечимни топишнинг књп босљичли тузилишдаги масалаларни ечиш усулидир. Динамик дастурлаш усулларини ќар хил турдаги математик моделларни ечишга љњлланилиши мумкин.

Чизиљли ва чизиљли бњлмаган дастурлаш масалаларида иљтисодий жараёнлар статик (ваљтга бођлиљ бњлмаган) ќолда љаралади ва оптимал ечим бир босљичда топилади.
Иљтисодий жараёнлар табиий ќолда бир неча босљичларга бњлинади. Масалан, режалаштириш ва бошљариш жараёнлари, бу ерда босљичлар: 3 йил, 1 йил, квартал, ой, хафта бњлиши мумкин. Лекин, бу усуллардан ваљт љатнашмаган жараёнларда ќам фойдаланилади. Бу ерда динамика ечилаётган масалаларда эмас, унинг ечиш усулидадир.
Шундай љилиб, динамик дастурлаш (ДД) мавзуси оптимал режалаштириш масалалари бњлиб, бунда динамика ечимни топишда ваљтнинг ёки амаллар кетма-кетлигида ифодаланади.
ДД моќияти шундан иборатки, масаланинг оптимал ечимини топиш књп босљичли (љадамли) жараёнга келтирилади. Бу шундан иборатки, оптимал ечимни топишда, нисбатан катта бњлмаган, ечиш осонрољ бњлган босљичларга бњлинади.
ДД усуллари билан капитал маблађларни оптимал таљсимлашда заќиралардан (ресурслардан) оптимал фойдаланишда жиќозларни оптимал алмаштиришда ва бошља књп соќаларда фойдаланилади.
ДД љуйидаги хусусиятларга эга:
1) ДД књп босљичли жараённинг ягона ечими эмас, балки ќар бир даврга мос келувчи ва якуний манфаатни књзловчи ечимлар кетма-кетлиги топилади;
2) ДД масалани ечиш жараёни ќар бир босљичида якуний маљсадни књзловчи ечимни аниклаш керак бњлади, яъни ечимлар орасида якуний маљсадга эришишга максимал хисса кушувчи ечим топилиши керак бњлади.
Шундай љилиб, маълум љадамдаги оптимал ечим фаљат шу љадам нуљтаи назаридан эмас, балки бутун жараённинг якуний маљсади нуљтаи назаридан оптимал ечим бњлиши керак. Бундай принцип ДД нинг оптималлик принципи деб аталади.
Оптималлик принципига амал љилиш, ќар бир љадамда љабул љилинган ечимни келгусида љандай натижаларга олиб келишини эътиборга олиб бориш демакдир.
2. Ресурсларнинг оптимал таљсимоти ќаљидаги масала. N та корхонани њз ичига олган бирлашма, Т йиллик режасини тузиш масаласи љњйилган бњлсин. Режалаштирилаётган Т даврнинг бошида бирлашма М миљдорда маблађга эга бњлсин. Бу маблађлар корхоналар њртасида таљсимланади. Корхоналар ажратилган маблађларни тњла ёки љисман ишлатади ва шунга мос маълум миљдорда даромад олади. Кейинги босљичларда маблађлар корхоналараро љайта таљсимланиши мумкин. Шундай љилиб, ушбу масала ќосил бњлади: корхоналараро маблађларни шундай таљсимлаш ва љайта таљсимлаш керакки, натижада бирлашманинг Т йил давомида олган даромадлар йиђиндиси максимал бњлсин.
Бунда ишлаб чиљаришнинг бошљарилувчи жараёни келиб чиљади ва унинг ривожланишига маблађлар орљали таъсир этиш мумкинлиги юзага келади.
Ќар йилнинг бошида бирлашмадаги ќар бир корхонага ажратилган маблађ ва ечим љабул љилинади. Бу ечимлар тњплами бошљариш бњлади.
билан - йил бошида, - корхонага ажратилган маблађ миљдори бњлсин ( ). Фараз љилайлик, маблађ - босљичга таљсимланган, яъни бирор бошљариш љабул љилинган бњлсин. Демак, - йил бошида K₁ корхонага , K₂ корхонага ва ќакозо K_n корхонага миљдорда маблађлар ажратилган бњлсин. Шундай љилиб, маблађнинг - босљичдаги таљсимотини ифодалайди. k босљичдаги бошљариш мажмуаси

n њлчовли векторлар системасидан иборат бњлади.
Z – даромадлар йиђиндиси бошљаришлар мажмуаси функцияси бњлади, яъни
.
Демак, ќар бир босљичда шундай ечимни љабул љилиш (бошљариш) керакки, бутун корхоналар системаси (бирлашма) нинг даромадлар йиђиндиси максимал бњлсин.
Умумий ќолда ДД масаласи љуйидагича бњлади. Бошљариладиган S система S₀ бошланђич ќолатда бњлсин. Ваљт њтиши билан система њзгаради ва охирги S_k ќолатга келади. Системанинг њзгариш жараёни билан бирор сонли Z мезон критерия билан бођлиљ бњлсин.
Мумкин бњлган бошљаришлар тњпламини билан белгилайлик. Масала, мумкин бњлган бошљаришлар мажмуидан шундай ни топиш керакки, S системани S₀ ќолатдан S_k якуний ќолатга њтказиш билан функция оптимал љийматни љабул љилсин.
Демак, t љадамдаги бошљаришни

вектор билан аниклаш мумкин, бу ерда j корхона учун љадамнинг бошида ажратилган хом ашё, капитал маблађ ва хоказоларнинг миљдорини билдиради.
Бутун бирлашманинг Т давр ичидаги бошљаришни

вектор билан ифодалаш мумкин. Бирлашмадаги корхоналар системасининг ривожланиш динамикасини ифодалаш учун уларнинг ќолати даражасини курсатувчи

векторни киритамиз, бу ерда t љадамнинг бошида системанинг моддий-ашёвий, молиявий ќолати даражасини курсатувчи вектор бњлиб, унинг компонентлари корхонадаги меќнат ресурслари, асосий фондлар молиявий ахвол даражасини курсатади, яъни
.
Демак, бошљариш вектори, системанинг T бошидаги ќолатини курсатувчи вектордир, яъни
.
Системанинг бошлангич ќолати берилган бњлади. Маљсад функция сифатида бирлашманинг Т давр ичида оладиган даромадлар йиђиндисини ифодаловчи
.
функцияни киритамиз. Ќар бир t љадамнинг бошида системанинг ќолат даражасига ва бошљариш векторига маълум бир чегараловчи шартлар љњйилиши мумкин. Бу шартлар системаси тњпламини билан белгилаймиз ва уни мумкин бњлган бошљаришлар тњплами деб караймиз.
Шундай љилиб, ушбу ДД масаласи келиб чиљади:
, (1)
. (2)
(1)-(2) моделга ишлаб чиљаришнинг динамик модели деб аталади. Бунга асосан, ќар бир t љадамдаги бошљаришни шандай аниклаш керакки, натижада системанинг режалаштирилаётган даврдаги эришган даромадлар йиђиндиси максимал бњлган.
ДД масаласининг умумий ќолда љњйилиши. Бошљариш мумкин бњлган жараённи караймиз. Бу жараённи t та босљичга ажратиш мумкин бњлсин. Жараённинг ќар бир t босљичи бошидаги ќолатини вектор билан белгилаймиз:
.
Жараён давомида системанинг ќолати узгаради. Унинг ќолатдан ќолатга утишига бошљариш таъсир килади. Демак, ни ва узгарувчиларнинг функцияси сифатида ифодалаш мумкин, яъни
.
Бунда, бошљаришни ихтиёрий равишда эмас, уни мумкин бњлган бошљаришлар тњпламидан, яъни

дан танлаш керак. Демак, бундай аниклашларда жараённинг бутун каралаётган давр [0, Т] ичидаги ривожланиши векторлар кетма-кетлиги орљали аникланади ( мумкин бњлган ќолатлар тњплами).
Жараённи бошлангич ќолатдан сунгги ќолатга утказувчи бошљаришлар кетма-кетлиги стратегия деб аталади. Бундай стратегиялар ичида жараённи энг яхши ќолатга утказувчи стратегияни танлаш керак. Буни амалга ошириш учун

маљсад функцияни критамиз, бунда системанинг ќолатдан ќолатга утганда хисобланадиган ва бу ќолатларни солиштиришда ишлатиладиган “баќоловчи” функциядир.
Шундай љилиб, ДД масаласи умумий ќолда љуйидагича љњйилади: системанинг бошлангич ќолати маълум бњлганда шундай

стратегияни танлаш керакки, у
(3)
шартларни каноатлантириб
(4)
функция экстремал љийматга эга бњлсин.
3. Беллманнинг функционал экстремал тенгламаси. Биринчи љадамдаги бошљариш бњлсин, бунинг натижасида жараён ќолатдан ќолатга њтади ва ютуљ (зарар) келтиради. Иккинчи љадам бошљариш жараёни ќолатдан ќолатга књчиради ва натижада ютуљ (зарар) келтиради ва ќоказо k - љадамда бошљариш жараёни ќолатдан ќолатга књчади ва ютуљ (зарар) келтиради.
Демак, жараённи ќолатдан ќолатга књчириш учун шундай бошљаришни (стратегияни) танлаш керакки, ундаги ютуљ (зарар) максимал (минимал) бњлсин, яъни
,

йиђинди књринишда ёзсак, ДД масаласи љуйидагича ифодаланади:
(5)
функция максимумга эга бњладиган

стратегияни топиш керак. Ушбу белгилашларни киритамиз:

бу ерда D_T масаланинг охирги босљичидаги аниљланиш соќаси, Т ва Т-1 босљичлардаги аниљланиш соќаси, берилган масаланинг аниљланиш соќаси бњлсин.
Маљсадли функциянинг охирги босљичдаги оптимал љийматини билан белгилаймиз:
. (6)
Шунингдек, Т ва Т-1 љадамдаги шартли оптимал љийматини билан белгиласак
, (7)

бњлади. Худди шундай љилиб
, (8)

………………………………………………….
, (9)
, (10)

эга бњламиз. (9), (10) ифодалар оптималлик принципининг математик ифодаланиши бњлиб, уларга Беллман функционал-экстремал тенгламалари ёки ДД нинг асосий функционал тенгламалари дейилади. ДД назариясига америкалик олим Р.Беллман катта ќисса љњшди. Асосий функционал-экстремал тенгламаларни ишлаб чиљиш, унга тегишлидир.
Функционал-экстремал тенгламалар ёрдамида ДД нинг Т босљичдаги ечимини Т-1 босљичдаги ечим орљали топилади. Шунинг учун (9), (10) ифодаларни Беллман рекуррент муносабатлари деб ќам юритилади. Бунда дастлаб охирги Т љадамдаги бошљариш топилади. Бу бошљариш жараённи ќолатдан ќолатга књчиради. Демак, га бођлиљ бњлади, яъни
. (11)
(11) шартни каноатлантирувчи бошљаришни Т босљичдаги шартли оптимал ечим деймиз. Охирги иккита Т-1 ва Т љадамлардаги масаланинг шартли оптимал ечими

топилади. Сњнгра масаланинг охирги учта босљичдаги шартли оптимал ечими

аниљланади ва ќоказо. Шундай усул билан биринчи љадамдаги масалага етиб борилади ва

шартли оптимал ечимлар кетма-кетлиги ќосил љилинади. Кейин бу жараённи олдингига нисбатан тескари йњналишда, яъни биринчи босљичдан-якуний босљичга томон яна бир такрорлаб, ќар бир босљичдаги оптимал бошљариш аниљланади.
4. Динамик дастурлаш усули. Т босљичли масалани ечиш жараёнини љараймиз. Олдин жараённи тескари йњналишда яъни дан га томон таќлил љиламиз. Бунинг учун Т босљич учун функционал-экстремал тенгламани тузамиз, бу тенглама (6) књринишда бњлади. Т босљичнинг бошида жараён ќолатларда бњлиши мумкин. Соддалик учун бутун сонли ќолатларни љараймиз. Бу ќолатларнинг ќар бири учун Т босљичдаги шартли оптимал ечимлар (12) ва уларга мос келувчи
(13)
даромад (зарар) лар топилади. (12) ечимлар орасида функцияга максимум (минимум) љиймат берувчи ва оптимал стратегиянинг таркибига кирувчи ечим бњлади. Шундай љилиб, охирги љадам оптималлашади, яъни бу љадамнинг бошида жараён љандай бњлишидан катъий назар љабул љилинадиган ечим аниљланади.
Кейин Т-1 њтилади. Бу љадам учун функционал-экстремал тенглама (7) књринишда бњлади. Бу љадамда ќам, юкоридагидек ќар бир мумкин бњлган ќолат учун мумкин бњлган ечим ва унга мос келувчи даромад (зарар) топилади. Сунгра йиђиндиларни њзаро солиштириб, ќар бир ќолатга мос келувчи йиђиндини, шу билан унга мос келувчи шартли оптимал ечим топилади. Бу ечимлар орасида функцияга экстремал љиймат берувчи ва оптимал стратегиянинг таркибига кирувчи ечим бњлади.
Бу усулни давом эттириб, жараённинг биринчи љадамига етиб келамиз. Бу љадамда жараён фаљат битта аниљ ќолатда бњлиши мумкин. Шунинг учун биринчи љадамда олдинги босљичларда топилган барча шартли оптимал ечимларни назарга олувчи ва х₀ ќолатга мос келувчи оптимал ечим топилади.
Шундай љилиб, ќамма мумкин бњлган ќолатлар учун кетма-кет функцияларнинг љийматлари ва турли босљич ва ќолатларга тегишли ечимлар, шу жумладан оптимал стратегиянинг таркибига кирувчи оптимал ечимлар топилади. Бу ечимлар асосида тузилган стратегия функцияга экстремал љиймат беради. Оптимал

стратегияни аниљлаш учун жараённи тњђри йњналишда ( дан га томон) яна бир текшириб чиљилади. Бунда, энг аввал аниљ бошланђич х₀ ќолатдан ва топилган функциянинг љийматидан фойдаланиб, топилади. Кейин ва орљали топилади ва ќоказо. Энг охирида ва орљали топилади.
5. Динамик дастурлаш усуллари билан ечиладиган иљтисодий масалалар. 1) Самолёт ёљилђиси харажатининг минимумини топиш масаласи [7, 238 бет]. Н₀ баландликда ва V₀ тезлик билан ќаракатланаётган самолёт Н_к баландликка књтарилиб, V_k тезликкка эга бњлиши керак бњлсин.
Самолётнинг бирор Н₁ баландликдан Н₂ баландликка њтиши учун кетадиган ёљилђи харажати маълум, бунда тезлик њзгармас, ќамда V₁ тезликдан ихтиёрий V₂ тезликка утиши учун ќам кетадиган ёљилђи харажати маълум, бу ќолда баландлик њзгармас.
Самолётни бошљаришнинг шундай оптимал режасини тузиш керакки, ёљилђи учун кетган харажат минимал бњлсин.
Ечиш. S системанинг ќолати иккита параметрга: V тезлик ва Н баландликка бођлиљ. Системани VOH координатлар текислигида ифодалаш мумкин. V=V₀, V=V_k ва Н=Н₀, Н=Н_к чизиклар билан чегараланган тњђри тњртбурчакни љараймиз.