Режа: Динамик дастурлаш ҳақида асосий тушунчалар

У-мумкин бўлган бошқарувлар тўплами бўлсин, у ҳолда, масала Х системани х_оХ_о^* ҳолатдан х_кХ_к^* ҳолатга ўтказишга имкон берувчи шундай у^*У бошқарувни топишдан иборатки, бунда W(у) мезон ўзининг W^*=W(у^*) оптимал қийматига эришсин.
Одатда системанинг х_о ҳолатини сонли параметрлар билан, масалан, ажратилган фондлар миқдори, жалб қилинган инвестисиялар миқдори, сарфланган ёқилғи миқдори ва ҳ.к. билан ифодалаш мумкин. Бу параметрларни системанинг координаталари деб атаймиз. У ҳолда системанинг ҳолатини х нуқта билан ва унинг Х₀ ҳолатдан Х_к ҳолатга ўтишини х нуқтанинг траекторияси билан тасвирлаш мумкин (1-шакл).







0


x₂


x₁


X₀^*


X_k^*

1- шакл.
(10)-(11) масалани ечишдан аввал
Г_Т, Г_Т-1,Т, …, Г_1,2,…,Т=Г
белгилашлар киритамиз. Бу йерда Г_Т – масаланинг охирги Т босқичдаги аниқланиш соҳаси, Г_Т-1,Т – Т ва Т-1 босқичлардаги аниқланиш соҳа, Г_1,2,…,Т=Г – берилган масаланинг аниқланиш соҳаси.
М
ақсад функсиянинг охирги босқичдаги оптимал қийматини ф₁(х_Т-1) билан белгилаймиз:
Х
удди шунингдек, Т-1 қадамдаги шартли оптимал қийматни ф₂(х_Т-2) билан белгилаймиз. У ҳолда

Худди шунингдек,

Б
у йерда (12)-(16) ифодалар оптималлик принсипининг математик формадаги ёзилишидан иборат бўлиб, улар «Беллманнинг функсионал тенгламалари» ёки «динамик дастурлашнинг асосий функсионал тенгламалари» деб аталади.

Бу тенгламалар ёрдамида динамик дастурлашнинг Т-1 босқичдаги ечимини сўнгги Т босқичдаги ечим орқали топилади. Шунинг учун юқоридаги муносабатлар Беллманнинг реккурент муносабатлари деб аталади.

2. Динамик дастурлаш усули

Динамик дастурлашнинг оптималлик принсипига асосан ҳар бир қадамда топилган ечим фақат шу қадам нуқтаи назаридан эмас, балки сўнгги, туб мақсад нуқтаи назаридан оптимал бўлиши керак эканлигини кўрган эдик. Динамик дастурлаш масалаларини ечиш усуллари учун ана шу принсип асос қилиб олинган.

Фараз қилайлик, биринчи қадамдаги бошқариш у₁ бўлсин. Бунинг таъсирида система х_о ҳолатдан х₁ ҳолатга ўтади ва натижада З₁(х_о, у₁) ютуқ келтиради. Иккинчи қадамда у₂ бошқариш системани х₁ ҳолатдан х₂ ҳолатга ўткизади ва натижада З₂(х₁, у₂) фойда келтиради ва ҳоказо. к қадамда у₂ бошқариш системани х_к-1 ҳолатдан х_к ҳолатга кўчиради ва З_к(х_к-1, у_к) ютуғ келтиради.
Демак, системани х_о ҳолатдан х_Т ҳолатга кўчириш учун шундай У=(у₁, у₂,…, у_Т) бошқариш (стратегияни) танлаш керакки, ундаги З_Т(х_о,У) ютуқ (зарар) максимал (минимал) бўлсин, яъни
ф_Т(х_о)=З(х_о,У)мах(мин).
Агар З_Т(х_о,У) ни З_Т(х_о,У)=З₁(х_о, у₁)+З₂(х₁, у₂)+…+З_Т(х_Т-1, у_Т)
йиғинди кўринишида ифодаласак, динамик дастурлаш масаласи
ф_Т(х_о)=З(х_о,У)=З₁(х_о, у₁)+З₂(х₁, у₂)+…+З_Т(х_Т-1, у_Т)
функсияга максимум (минимум) қиймат берувчи
У=(у₁, у₂,…, у_Т)
бошқаришни топишга келтирилади.
Бундай бошқаришни топиш жараёни эса, қуйидагича амалга оширилади:
Энг аввал жараённи тескари йўналишда (х_Т-1 дан х_о га томон) таҳлил қиламиз. Бунинг учун охирги Т босқич учун функсионал тенглама
ё
замиз.
Охирги Т босқичнинг бошида жараён х_Т-1,1, х_Т-1,2, …, х_Т-1,к ҳолатларда бўлиши мумкин бўлсин деб фараз қиламиз. Соддалик учун фақат бутун сонли
х_Т-1,кХ_Т-1 ҳолатларни кўрамиз.
Бу ҳолатларнинг ҳар бири учун Т босқичдаги шартли оптимал у_Т,1, у_Т,2,…, у_Т,к ечимлар ва уларга мос келувчи З_Т,1, З_Т,2,…, З_Т,к даромад (чиқим)лар топилади. у_Т,1, у_Т,2,…, у_Т,к ечимлар орасида ф₁(х_Т-1) функсияга максимум (минимум) қиймат берувчи ва оптимал у* стратегиянинг таркибига кирувчи у*_Т ечим топилади. Лекин бу ечим масалани ечиш жараёнининг иккинчи босқичида, яъни жараён тўғри йўналишда (х_о дан х_Т-1 га томон) текширилганда топилади.
Шундай қилиб, охирги қадам оптималлаштирилади, яъни бу қадамнинг бошида система қандай бўлишидан қатъий назар қабул қилинадиган ечим аниқланади.
Сўнгра Т-1 босқичга ўтилади. Бу қадам учун функсионал тенглама
т
узилади.
Бу босқичда ҳам, худди юқоридагидек ҳар бир мумкин бўлган х_Т-2,к Х_Т-2 ҳолат учун мумкин бўлган у_Т-1,кГ_Т-1 ечим ва унга мос келувчи З_Т-1,к даромад (чиқим) топилади. Сўнгра З_Т-1,к+ф₁ йиғиндиларни ўзаро солиштириб, ҳар бир х_Т-2,к ҳолатга мос келувчи йиғинди ва унга мос келувчи шартли оптимал ечим у_Т-1,к топилади. Бу ечимлар орасида ф₂(х_Т-2) функсияга экстремал қиймат берувчи ва оптимал у* стратегиянинг таркибига кирувчи у*_Т-1 топилади.
Шундай йўл билан давом этиб, жараённинг биринчи босқичига ўтилади. Бу қадамда жараён фақат битта аниқ ҳолатда бўлиши мумкин. Шунинг учун бу босқичда олдинги босқичларда топилган барча шартли оптимал ечимларни назарга олувчи ва х_о ҳолатга мос келувчи оптимал ечим топилади.
Шундай қилиб, ҳамма мумкин бўлган ҳолатлар учун бирин-кетин ф₁, ф₂,…, ф_Т-1, ф_Т функсияларнинг қийматлари ва турли босқич ва ҳолатларга тегишли ечимлар, шу жумладан у* оптимал стратегиянинг таркибига кирувчи оптимал у*_Т, у*_Т-1,…, у*₁ ечимлар топилади. Бу ечимлар асосида тузилган у* стратегия ф_Т(х_о) функсияга экстремал қиймат беради. Оптимал
У*=(у*₁, у*₂,…, у*_Т-1, у*_Т)
стратегияни аниқлаш учун жараённи тўғри йўналишда (х_о дан х_Т-1 га томон) яна бир бор текшириб чиқиш керак. Бунда, энг аввал аниқ бошланғич х_о ҳолатдан ва топилган ф_Т(х_о) функсиянинг қийматидан фойдаланиб, у*₁ топилади. Сўнгра у*₁ ва ф_Т-1(х₁) функсиянинг қиймати орқали у*₂ топилади ва ҳоказо. Энг охирида у*_Т-1 ва ф_Т-1(х₁) орқали у*_Т топилади.
Динамик дастурлаш масаласини ечиш жараёнини қуйидаги мисолда яққол кўрсатиш мумкин.
Мисол. Энг қисқа йўлни танлаш масаласи.
Фараз қилайлик, А ва Б пунктларни ўзаро боғловчи темир йўллар тўри берилган бўлсин (2-шакл). Бу пунктлар орасида темир йўл билан боғланган жуда кўп пунктлар мавжуд бўлиши мумкин. Бунда ҳар қандай икки пункт орасидаги масофа маълум деб фараз қиламиз. Масалан, бу масофанинг узунлиги 2-шаклдаги ҳар икки нуқтани туташтирувчи кесма устига ёзилган сонлардан иборат бўлсин. А ва Б пунктларни энг қисқа йўл билан туташтирувчи маршрутни аниқлаш масаласи қўйилади.
2
-шакл
Масалани ечиш учун (1-1), (2-2), (3-3) чизиқлар ёрдамида берилган темир йўллар тўрини айрим қисмларга (босқичларга) ажратамиз (3-шакл).
3
-шакл
(2-2) чизиқнинг транспорт йўллари тўри билан кесишган нуқталарини Д₁, Д₂, Д₃ лар билан, (3.3) чизиқнинг кесишган нуқталарини эса C₁, C₂, C₃ лар билан белгилаймиз. Биринчи қадамда Б нуқтадан Д₁, Д₂, ва Д₃ нуқталаргача бўлган энг қисқа масофани аниқлаймиз.
Б–Д₁: мин (10, 8+4, 5+3+8)=10,
Б–Д₂: мин (10+8+5, 4+5, 5+3+5)=9,
Б–Д₃: мин (5+2,5, 4+3+2,5)=7,5.
3-шаклда Д₁, Д₂, Д₃ нуқталардан сўнгги Б пунктгача бўлган энг қисқа масофа қавс ичида ёзилган. Сўнгра (3-3) чизиқнинг транспорт йўллари тўри билан кесишган C₁, C₂, C₃ нуқталарни кўрамиз. Бу нуқталардан Б нуқтагача бўлган энг қисқа масофани аниқлаймиз. Бу масофа
C₁ нуқта учун мин (1+8+10, 1+7+4+2+9, 1+7+2+3+2+9, 1+7+2+2,5+7,5)= мин(19,23,24,20)=19;
C₂ нуқта учун мин(7+8+10, 9+10, 4+2+9, 4+3+2+9, 4+2,5+7,5)=
=мин(25, 19, 15, 18, 14)=14;
C₃ нуқта учун мин(2+2,5+7,5, 2+3+2+9)=12.
Бу масофалар шаклда қавс ичида ёзилган. 3 босқичда А нуқтадан Б гача бўлган энг қисқа масофа топилади. Бу масофа қуйидагича аниқланади:
мин(6+9+19, 6+5+14, 8+6+14, 8+3+12)=23.
Сўнгра А нуқтадан энг қисқа масофа бўйлаб Б нуқтага борадиган йўлни белгилаймиз:

3. Мустақил ечиш учун масалалар.

1. 
   Берилган масалаларни динамик дастурлаш масаласи сифатида ифодаланг.
   

А. Бирлашма м та корхонани ўз ичига олади. Бу корхоналарни техник жиҳатдан таъмирлаш мақсадида марказлаштирилган жамғарма ташкил этилган. Бу жамғармага биринчи йили А минг сўм маблағ ажратилган. Кейинги йилларда эса, бу жамғарма корхоналар даромадида ажратилган маблағлар ҳисобига тўлдириб борилади. Ушбу жамғармадан и-корхонага ажратилган х_и маблағ унга ф_и(х_и) миқдорда қўшимча даромад келтиради. н йил ичида корхоналарнинг топган қўшимча даромадлари максимал бўлиши учун жамғармадаги маблағ қандай тақсимланиши керак?
Б. Бирлашма иккита корхонани ўз ичига олади.
Бу корхоналарни техник жиҳатдан таъмирлаш учун инвестор С миқдорда капитал маблағни Н йил давомида сарф қилмоқчи. Ҳар бир и – корхонага К – йилнинг бошида миқдорда маблағ ажратилади.
Н йил ичидаги капитал маблағни корхоналар орасида шундай тақсимлаш керакки, натижада инвесторнинг оладиган даромади максимал бўлсин.