|
Динамик программалаштириш усули
|
| bet | 2/3 | | Sana | 18.02.2024 | | Hajmi | 241,03 Kb. | | #158458 |
Bog'liq 7-ma’ruza Dinamik programmalashtirish usuliBirinchi bosqichda (1) masalani unga o’xshash masalalar oilasiga invariant kiritamiz, ya’ni
(3)
masalalar oilasini qaraymiz. (3) masala maqsad funksiyasining optimal qiymatini Bk(y) kabi belgilaymiz:
(4)
– Bellman funksiyasi deyiladi.
Ikkinchi bosqichda rekurrent
Bellman tenglamasidan va (asosiy bog’lanish tenglik shaklda bo’lgan holda boshlang’ich shartdan foydalanib ketma-ket funksiyalarini topamiz.
Oxirgi, uchinchi bosqichda (1) masalaning yechimini quramiz: ni funksiyaga maksimum beruvchi nuqta sifatida aniqlaymiz, ya’ni ni ham shunga o’xshash shartdan aniqlaymiz, bu yerda .
Shunday davom etib, nuqtalarni
shartdan topamiz, bu yerda
ni esa, shartdan topamiz (asosiy bog’lanish tenglik ko’rinishda bo’lganda esa, bo’ladi). (1) masala maqsad funksiyasining maksimal qiymati ga teng.
Eslatma. Agar (1) masalada funksiyalar ham qavariq bo’lsa, funksiyalar ham qavariq bo’ladilar va demak qavariq funksiyalarning xossalariga ko’ra (4) tenglamaning o’ng tomonida maksimumga yo , yoki nuqtada erishiladi.
1-misol. Resurslar taqsimoti haqidagi (2) masalada
bo’lsin. Shu masalani yechamiz.
Demak, quyidagi masala berilgan:
Unga o’xshash masalalar oilasi quyidagicha bo’ladi:
Bellman funksiyasi
uchun Bellman tenglamasini yozamiz:
Bu tenglama uchun boshlang’ich shart bo’ladi. Bellman tenglamasidan ketma-ket va funksiyalarni topamiz:
Endi optimal taqsimotni aniqlaymiz.
bu yerda maksimumga da erishiladi. Demak,
,
bu yerda maksimumga da erishiladi. Demak, . U vaqtda .
Shunday qilib, optimal taqsimot quyidagicha bo’ladi: : maksimal foyda ga teng.
3. Algoritm. Faraz qilaylik, (1) masalada butun sonlar bo’lsin hamda o’zgaruvchilar faqat manfiy bo’lmagan butun qiymatlar qabul qilinsin. Bu holda Bellman tenglamasi
(5)
va uning uchun boshlang’ich shart
(6)
(asosiy bog’lanish tenglik ko’rinishida bo’lganda ) bo’ladi, bu yerda sonning butun qismini ifodalaydi.
Qaralayotgan holda (1) masalani dinamik dasturlash usuli bilan yechishni quyidagi algoritm bo’yicha amalga oshirish mumkin:
1) deb olamiz;
2) funksiyaning nuqtalardagi qiymatlarini hisoblaymiz ( bo’lganda. hisoblanadi).
3) ni hisoblaymiz hamda va ni eslab qolamiz;
4) agar bo’lsa, deb 2) punktga qaytamiz; aks holda navbatdagi punktga o’tamiz;
5) deb olamiz;
6) uchun qiymatlarni hisoblaymiz;
7) ni hisoblaymiz hamda va ni eslab qolamiz;
8) agar bo’lsa, deb 6) punktga qaytamiz; aks holda navbatdagi punktga o’tamiz;
9) agar bo’lsa. , deb 6) bandga qaytamiz; aks holda navbatdagi bandga o’tamiz;
10) (1) masalani yechimi ni aniqlaymiz:
(7)
-(1) masala maqsad funksiyasining optimal qiymati bo’ladi.
Eslatma. Agar (7) formulada biror uchun bo’lsa, bo’ladi.
|
| |
