9-ma’ruza: Dinamik dasturlash usuli. Bellmanning funksional tenglamasi
Reja:
Masalaning qo’yilishi.
Masalaning yechilishi.
Algoritm.
Algoritmdan jadval yordamida foydalanish.
Tayanch ibora va so’zlar: dinamik dasturlash, jarayon, dinamik jarayonlar, matematik dasturlash, maqsad funksiyasi, resurs miqdori, resurs taqsimoti, xom ashyo, masalalar oilasi, Bellman tenglamasi, Bellman funksiyasi.
Dinamik dasturlash usuli
Dinamik dasturlash – ko’p bosqichli va dinamik jarayonlarni matematik dasturlash hamda optimal boshqarishning maxsus masalalarini yechish usulidir. Quyida bu usulning matematik dasturlash masalalaridan bir tipiga qo’llanilishini ko’ramiz.
1. Masalaning qo’yilishi. Matematik dasturlashning quyidagi
(1)
masalasini qaraymiz. Bu masalaning o’ziga xos xususiyati shundan iboratki, uning maqsad funksiyasi separabeldir, ya’ni bir o’zgaruvchili , funksiyalar yig’indisidan iborat.
Bir qator iqtisodiy masalalarni (1) masala ko’rinishida matematik modellashtirish mumkin. Shunday masalalardan biri-resurslar taqsimoti haqidagi masaladir. U miqdordagi xom ashyo (resurs) va ta texnologik jarayonlar berilgan bo’lsin; agar xom ashyoning x miqdorini - texnologik jarayonda foydalansak, miqdordagi foyda olinishi ma’lum bo’lsa, maksimal umumiy foyda olish uchun xom ashyoni jarayonlar o’rtasida qanday taqsimlash kerak?
Agar orqali -jarayon uchun ajratilgan resurs miqdorini belgilasak, – jami foyda, bo’ladi. Natijada resurslar taqsimoti haqidagi masala quyidagicha matematik modellashtiriladi:
(2)
2. Masalaning yechilishi. Amerikalik olim R. Bellman tomonidan asoslangan sxemaga ko’ra, (1) masalani dinamik dasturlash usuli bilan yechish quyidagi bosqichlarda amalga oshiriladi.
|