Dinamik programmalashtirish. Bellman funksiyasi va tenglamasi

Dinamik programmalashtirish. Bellman funksiyasi va tenglamasi. Bellman funksiyasini hisoblash. Diskret jarayonlarini optimal boshqaruvi. Diskret maksimum prinsipi Reja: Dinamik programmalashtirish. Bellman funksiyasi va tenglamasi. Bellman funksiyasini hisoblash Diskret jarayonlarini optimal boshqaruvi. Diskret maksimum prinsipi Dinamik programmalashtirish. Bellman funksiyasi va tenglamasi. Bellman funksiyasini hisoblash Dinamik programmalashtirish deb matematik modellari ko'p bosqichli va dinamik jarayonli xarakterga ega bo'lgan chiziqsiz programmalashtrishning maxsus masalalari (I-IV) va optimal boshqaruv masalalarin yechishning hisoblash usuliga aytiladi. Bu usul jarayonlarning ketma-ket tahliliga asoslangan bo'lib, ekstremal masalalarn yechishda amerikalik olim R. Bellman tomonidan XX asrning 50-yillaridan boshlab dastlab sistematik va pirntsipial keng qo'llanila boshlandi. Mazkur ma'ruzada bu usulning asosiy qoidalari chiziqsiz programmalashtirishning qator maxsus masalalari uchun bayon qilinadi. Dinamik programmalashtirishning optimal boshqaruv masalalariga tatbiqlari beriladi. 1-§. Resurslarni tahminlash masalasi Aytaylik, s hajmli xomashyo va n ta texnologik jarayon mavjud bo'lsin. Agar xomashyoning x miqdorini x texnologik jarayonda sarflansa, foyda olinadi. Maksimal foyda olish uchun xom ashyoni jarayonlar o'rtasida qanday taqsimlash kerak? Faraz qilaylik, - jarayon uchun ajratilgan xom ashyo miqdori bo'lsin. U holda qo'yilgan resurslarni taqsimlanish masalasining matematik modeli (1) ko'rinishini oladi. (1) chiziqsiz programmalash masalasining o'ziga xoslgi shundan iboratki, uning maqsad funksiyasi va asosiy cheklash funksiyasi separabeldir, yani ular bir o'zgaruvchili funksiyalar yig'indisi shaklida ifodalangan. Elektremal masalani dinamik programmalash usuli bilan yechishning birinchi bosqichi-berilgan masalani unga o'xshash masalalar oilasiga invariant turkumlashdan iboratdir. Bu bosqich malum manoda san'at bo'lib, har bir muayyan holda tadqqotchining tajribasi, sezgisi va mahoratiga bog'liqdir. U (1) masala uchun ixtiyoriy sondagi texnologik jarayonlarga va xom ashyo g'amlamasiga ega bo'lgan resurslarni taqsimlashning ushbu (2) masalalarni qarashdan iboratdir. bo'lganda (2) masalalar oiladan boshlang'ich (1) masala olinadi. Bellman funksiyasi va tenglamasi (2) masalalar oilasidan olingan ixtiyoriy masala maqsad funksiyasining optimal qiymati Bellman funksiyasi deyiladi va kuydagicha belgilash kiritiladi (3) Masalani dinamik programmalash usuli bilan yechishning ikkinchi bosqichi-Bellman funksiyasi uchun tenglamani olishdan iboratdir. Bu bosqichda bellmanning optimallik prinsipi umumiy holda qo'llaniladi. (1) masala uchun uning mohiyati quyida keltirilgan mulohazalar orqali beriladi. Bu mulohazalar oddiy matematik faktlarga asoslangan va etarlicha universal. Izlanayotgan tenglamani tuzishda invariant joylashning to'g'riligi namoyon bo'ladi. Ikkinchi tomondan, joylashtirish usuli tenglamaning ko'rinishida ham seziladi, k jarayonli va u xom ashyo g'amlamasiga ega bo'lgan (2) masalada k-jarayonga miqdordagi xomashyo ajratamiz. Bunda k jarayondan olinadigan joyda ga teng bo'ladi. 1, 2, ,k-1 nomerli jarayonlar uchun esa y-z miqdordagi xomashyo qoldi. Aytaylik, bu xomashyo qolgan jarayonlarga optimal taqsimlangan bo'lsin. (3) ning aniqlanishiga ko'ra k-1 ta jarayondan keladigan foydaning maksimal miqdori ga teng bo'ladi. Shunday qilib, k jarayonga z miqdorda xomashyo ajratilganda ...