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

Динамик программалаштириш масаласининг умумий қўйилиши.

• Вақтга боғлик равишда ўзгарувчан ва бошқариш мумкин бўлган системани кўрамиз. Бу системани T та босқичларга ажратиш мумкин деб фараз қиламиз, яъни t=1,…,T. Ҳар бир босқичнинг бошидаги системанинг ҳолаtини xt билан белгилаймиз.
• xt=(x1t, x2t,…, xmt).
• Тараққиёт жараёнида системанинг ҳолати ўзгаради. Унинг xt-1 ҳолатдан xt ҳолатга ўтишга ut бошқариш таъсир қилади. Демак, xt xt-1 ва ut ўзгарувчиларнинг функциясидан иборат бўлади, яъни
• xt=(xt-1, ut).
• Бу ерда ut мумкин бўлган бошқаришлар тўплами Gt га тегишли, яъни
• utGt

• Бундай аниқлашларда системанинг бутун [0,T] давр ичидаги тараққиёти x0, x1,…, xT-1, xT векторлар кетма-кетлиги орқали аниқланади. (xt

• )

• –системанинг t босқичда мумкин бўлган ҳолатлар тўплами. Системани бошланғич X0 ҳолатдан XT ҳолатга ўтказиш учун u0, u1,…, uT-1, uT бошқаришлар кетма-кетлиги, яъни стратегиялар ҳизмат қилади. Системани энг яхши xT ҳолатга ўтишини таъминлаш учун fT(x) мақсад функцияни киритамиз:

• бу ерда Zt=(xt-1, xt) системанинг xt-1 ҳолатдан xt ҳолатига ўтишида ҳисобланадиган ва бу ҳолатларни солиштириб баҳоловчи функциядир.
• Агар системанинг t босқичдаги ҳолатлар тўплами Xt, мумкин бўлган бошқаришлар тўплами G, ҳамда системани бир ҳолатдан иккинчи ҳолатга ўтказиш қоидаси, ҳамда бу ҳолатларни солиштирувчи функция Zt=(xt-1, xt) берилган бўлса, T босқичи система тўла аниқланган бўлади. Бундай системани ифодаловчи динамик программалаш масаласи қуйидагича ёзилади.
• Системани бошланғич ҳолати x0 маълум бўлганда шундай
• ut=(u1, u2,…, uT)
• стратегияни танлаш керакки, у
• xt=(xt-1, ut), xt , utGt, (t=1,…,T )

• шартларни қаноатлантириб,

• функцияга экстремал қиймат берсин.
• Ушбу муносабатлардан кўринадики, динамик программалаш масаласи кўп босқичли танлаш масаласи бўлиб, унинг u оптимал ечими бир нечта босқичларда топилган мумкин бўлган ut бошқаришлар асосида танланади.