Кириш. Чизиқли программалаштириш (1-маъруза машғулоти)

Динамик программалаш усули

• Динамик программалашнинг оптималлик принципига асосан ҳар бир қадамда топилган ечим фақат шу қадам нуқтаи назаридан эмас, балки сўнги, туб мақсад нуқтаи назаридан оптимал бўлиши керак эканлигини кўрган эдик. Динамик программалаш масалаларини ечиш усуллари учун ана шу принцип асос қилиб олинган.
• Фараз қилайлик, биринчи қадамдаги бошқариш u1 бўлсин. Бунинг таъсирида система xo ҳолатдан x1 ҳолатга ўтади ва натижада Z1(xo, u1) ютуқ келтиради. Иккинчи қадамда u2 бошқариш системани x1 ҳолатдан x2 ҳолатга ўткизади ва натижада Z2(x1, u2) фойда келтиради ва ҳакозо. k қадамда u2 бошқариш системани xk-1 ҳолатдан xk ҳолатга кўчиради ва Zk(xk-1, uk) ютуқ келтиради.

• Демак, системани xo ҳолатдан xT ҳолатга кўчиришиш учун шундай U=(u1, u2,…, uT) бошқариш (стратегияни) танлаш керакки, ундаги ZT(xo,U) ютуқ (zаrаr) максимал (минимал) бўлсин, яъни fT(xo)=Z(xo,U)max(min).
• Агар ZT(xo,U) ни ZT(xo,U)=Z1(xo, u1)+Z2(x1, u2)+…+ZT(xT-1, uT) йиғинди кўринишида ифодаласак, динамик программалаш масаласи
• fT(xo)=Z(xo,U)=Z1(xo,u1)+Z2(x1, u2)+…+ZT(xT-1, uT)
• функцияга максимум (минимум) қиймат берувчи
• U=(u1, u2,…, uT)
• бошқаришни топишга келтирилади.

Бундай бошқаришни топиш жараёни эса, қуйидагича амалга оширилади: Энг аввал жараённи тескари йўналишда (xT-1 дан xo га tоmоn) таҳлил қиламиз. Бунинг учун охирги T босқич учун функциянал тенглама ёзамиз. Охирги T босқичнинг бошида жараён xT-1,1, xT-1,2, …, xT-1,k ҳолатларда бўлиши мумкин бўлсин деб фараз қиламиз. Соддалик учун фақат бутун сонли xT-1,kXT-1 ҳолатларни кўрамиз. Бу ҳолатларнинг ҳар бир i учун T босқичдаги шартли оптимал uT,1, uT,2,…, uT,k ечимлар ва уларга мос келувчи ZT,1, ZT,2,…, ZT,k даромад (чиқим)лар топилади. uT,1, uT,2,…, uT,k ечимлар орасида f1(xT-1) функцияга максимум (минимум) қиймат берувчи ва оптимал u* стратегиянинг таркибига кирувчи u*T ечим топилади. Лекин бу ечим масалани ечиш жараёнининг иккинчи босқичида, яъни жараён тўғри йўналишда (xо дан xT- tоmоn) текширилганда топилади. Шундай қилиб, охирги қадам оптималлаштирилади, яъни бу қадамнинг бошида система қандай бўлишидан қатъий назар қабул қилинадиган ечим аниқланади.

• 3

Сўнгра T-1 босқичга ўтилади. Бу қадам учун функционал тенглама тузилади. Бу босқичда ҳам, худди юқоридагидек ҳар бир мумкин бўлган xT-2,k XT-2 ҳолат учун мумкин бўлган uT-1,kGT-1 ечим ва унга мос келувчи ZT-1,k даромад (чиқим) топилади. Сўнгра ZT-1,k+f1 йиғиндиларни ўзаро солиштириб, ҳар бир xT-2,k ҳолатга мос келувчи йиғинди ва унга мос келувчи шартли оптимал ечим uT-1,k топилади. Бу ечимлар орасида f2(xT-2) функцияга экстремал қиймат берувчи ва оптимал u* стратегиянинг таркибига кирувчи u*T-1 топилади. Шундай йўл билан давом этиб, жараённинг биринчи босқичига ўтилади. Бу қадамда жараён фақат битта аниқ ҳолатда бўлиши мумкин. Шунинг учун бу босқичда олдинги босқичларда топилган барча шартли оптимал ечимларни назарга олувчи ва xo ҳолатга мос келувчи оптимал ечим топилади.

Шундай қилиб, ҳамма мумкин бўлган ҳолатлар учун бирин-кетин f1, f2,…, fT- функцияларнинг қийматлари ва турли босқич ва ҳолатларга тегишли ечимлар, шу жумладан u* оптимал стратегиянинг таркибига кирувчи оптимал u*T, u*T-1,…, u*1 ечимлар топилади. Бу ечимлар асосида тузилган u* стратегия fT(xo) функцияга экстремал қиймат беради. Оптимал U*=(u*1, u*2,…, u*T-1, u*T) стратегияни аниқлаш учун жараённи тўғри йўналишда (xo дан xT- томон) яна бир бор текшириб чиқиш керак. Бунда, энг аввал аниқ бошланғич xo ҳолатдан ва топилган fT(xo) функциянинг қийматидан фойдаланиб, u*1 топилади. Сўнгра u*1 ва fT-1(x1) функциянинг қиймати орқали u*2 топилади ва ҳакозо. Энг охирида u*T-1 ва fT-1(x1) орқали u*T топилади.