Identifikatsiyalash
Dinamik programmalash masalasining umumiy qoʻyilishi
Download 1.5 Mb.
|
ОПТИМАЛЛАШТИРИШ (2)
- Bu sahifa navigatsiya:
- Bellmanning funksional tenglamalari
|
6.2.Dinamik programmalash masalasining umumiy qoʻyilishi.
Vaqtga bogʻlik ravishda oʻzgaruvchan va boshqarish mumkin boʻlgan jarayonni koʻramiz. Bu jarayonni t -ta bosqichga ajratish mumkin boʻlsin deb faraz qilamiz. Jarayonning xar bir t-bosqichining boshidagi xolatini xi vektor orqali belgilaymiz: Taraqqiyot jarayonida sistemaning xolati uzgaradi. Uning xolatdan xolatga oʻtishiga boshqarish ta’sir qiladi. Demak, xt ni xt-1 va ut oʻzgaruvchilarning funksiyasi sifatida ifodalash mumkin: = va funksiyaning ekstremal qiymati aniqlanishi talab qilinadi. Biz yuqorida dinamik programmalash masalasi uchun optimallik prinsipi bilan tanishgan edik. Bu prinsipga asosan dinamik programmalashning har bir qadamda topilgan echimi fakat shu qadam nuqtai nazaridan emas, balki soʻngi, tub maqsad nuqtai nazaridan optimal boʻlishi kerak. Ana shu prinsip dinamik programmalash masalalarini echish usullariga asos qilib olinadi. Bu prinsipni matematik formada ifodalaymiz. Faraz qilaylik, birinchi qadamdagi boshqarish u1 boʻlsin. Buning ta’sirida jarayon x0 xolatdan x1 xolatga oʻtadi va natijada Z1(x0,u1) yutuq (zarar) keltiradi va xakazo k- qadamda uk boshqarish jarayoni xk-1 xolatdan xk xolatga koʻchiradi va Zk(x0,uk) yutuq (zarar) keltiradi. Demak, jarayonni x0 xolatdan xT xolatga koʻchirish uchun shunday =(u1, u2,..., uT) boshqarishni tanlash kerakki, undagi ZT(x0, ) yutuq maksimal boʻlsin, ya’ni fT(x)=Z(x0, )®max(min). Agar Z(x0, )= Z1(x0,u1)+ Z2(x1,u2)+...+ ZT(xT-1,uT) Yigʻindi koʻrinishda ifodalasak, dinamik programmalash masalasi fT(x)=Z(x0,u)=Z(x0, )= Z1(x0,u1)+ Z2(x1,u2)+...+ ZT(xT-1,uT) (6.1.3) funksiyaga maksimum qiymat beruvchi u=(u1, u2,..., uT) strategiyani topishga keltiriladi. Bu masalani echishdan avval GT, GT-1,T,..., G1,2,...,T=G belgilashlar kiritamiz. Maqsad funksiyaning oxirgi bosqichdagi optimal qiymatini f1(xT-1) bilan belgilaymiz: f1(xT-1)=max(min) ZT(xT-1,uT). (6.1.4) UT-1Î GT Xuddi shuningdek maqsad funksiyaning oxirgi ikki T va T-1 qadamdagi shartli optimal qiymatini f2(xT-2) bilan belgilaymiz. U xolda (6.1.5) T-2Î GT-1,T Xuddi shuningdek (6.1.6) T-3Î GT-2,T-1,T fk(xT-k)=max(min)[ZT-k+1(xT-k,uT-k+1)+al-1(chE-l+1) ‘b(lÎ ), (6.1.7) (6.1.8) 1Î G Bu tenglamalar dinamik programmalashning prinsipi yoki Bellmanning funksional tenglamalari deyiladi. Bu tenglamalar yordamida dinamik programmalashtirish T bosqichdagi echimini soʻngi T-1 bosqichdagi echim orqali topiladi. SHuning uchun (6.1.7)-(6.1.8) ifodalarni Bellmanning rekkurent munosabatlari deb xam ataladi (6.1.5),( 6.1.6), (6.1.7) tenglamalardan foydalanib, dinamik programmalash masalasini echish prinsipini quyidagicha bayon qilish mumkin. Dastlab oxirgi uT boshqarish topiladi. Bu boshqarish jarayonni xT-1 xolatdan xT xolatga koʻchiradi. Demak uT xT-1 ga bogʻlik boʻladi, ya’ni uT =uT (xT-1) (6.1.9) shartni qanoatlantiruvchi boshqarishni T bosqichdagi shartli optimal echim deb ataymiz. Oxirgi ikkita T-1 va T qadamlardagi masalaning shartli optimal echimi uT-1 =uT-1 (xT-2) topiladi. Soʻngra masalaning oxirgi uchta bosqichidagi shartli optimal echimi uT-2 =uT-2 (xT-3) aniqlanadi va xakazo. Shunday yoʻl bilan birinchi qadamdagi masalaga etib boriladi va u1(x0), u2(x2),...,uT-1 (xT-2),uT(xT-1) shartli optimal echimlar ketma-ketligi xosil qilinadi. Soʻngra bu jarayonni oldingiga nisbatan teskari yoʻnalishda, ya’ni birinchi bosqichdan oxirgi bosqichga tomon yana bir takrorlab, xar bir bosqichdagi optimal u*1,u*2,...,u*T boshqarish aniqlanadi. Dinamik programmalash masalasini echish prinsipini quyidagi misolda yaqqol koʻrsatish mumkin. Dinamik programmalashtirish koʻp bosqichli masalalarning optimal echimini topish uchun qoʻllaniladi. Oʻrganilayotgan masala tabiiy jihatdan koʻp bosqichli oʻlishi mumkin yoki uni sun’iy ravishda koʻp bosqichli shaklga keltirish mumkin. Bunday masalani echishda Bellmanning optimallik prinsipini qoʻllaydi. Bunda sistemaning optimal echimi boshlangʻich shart va holatlardan qat’iy nazar keyingi holati ……Matematik jihatdan ushbu shart quyidagicha yoziladi: . Bu yarda Uℓ – ℓ-qadamda tanlangan echim, Sℓ - sistemaning ℓ-qadamdagi holati, Rℓ - ℓ-qadamda erishilgan samara, fℓ - samaraning optimal qiymati, optimum – maksimum yoki minimum. Download 1.5 Mb. Do'stlaringiz bilan baham: 
|