Dinamik programmalashtirish usuli

Dinamik programmalashtirish usuli Reja: Dinamik programmalashtirish masalalariga misollar. Optimallik prinsipi. Masalani o'xshash turkum masalalarga ajratish. Optimal planlashtirish masalasi. Bellmaning rekkurent tenglamalari. ko'p iqtisodiy jarayonlar o'z-uzidan bosqichlarga bulingan bo'ladi. Masalan, vaqtga bog'liq bo'lgan iqtisodiy jarayonlarni planlashtirish va boshqarishda xar bir kadam 5 yil, 1 yil, kvartal, oy va dekadadan iborat bo'lishi mumkin. Lekin dinamik programmalash fakat vaqtga bog'liq bo'lgan ko'p bosqichli masalarni yechish uchun ishlatiladi deb tushunmaslik kerak. iqtisodiy praktikada uchraydigan va vaqtga bog'liq bo'lmagan jarayonlarni ifodalovchi ko'p masalalarni dinamik programmalash usullari bilan yechish mumkin. Bunga misol sifatida eng qisqa yulni aniqlash masalasini, samolyotning optimal tezligi hamda uchish balandligini aniqlash masalasi va butun sonli programmalash va boshqalarni ko'rsatish mumkin. Bu masalalar vaqtga bog'liq bo'lmagan jarayonlarni ifodalaydi. Lekin ularni turli vositalar yordamida ko'p bosqichli masalalarga aylantirish, sungra ularga dinamik programmalash usullarini kullab yechish mumkin. Dinamik programmalash quyidagi xususiyatlarga ega bo'ladi: Dinamik programmalash ko'p bosqichli jarayonning birdan-bir yagona yechimini emas, balki xar bir davrga mos keluvchi va tub manfaatni kuzlovchi yechimlar ketma-ketligini topishga yordam beradi; Dinamik programmalash yordami bilan echilayotgan ko'p bosqichli masalaning malum bir bosqichi uchun topilgan yechimi undan oldingi bosqichlarda topilgan yechimga bog'liq bulmaydi. Unda fakat shu bosqichni ifodalovchi faktlar nazarga olinadi; Dinamik programmalash yordami bilan ko'p bosqichli masalani yechish jarayonining xar bir bosqichida tub maqsadni kuzlovchi yechimni aniqlash kerak, yani yechimlar orasida tub maqsadga erishishda maksimal xissa kushuvchi yechimni topish kerak. Optimal planlashtirish masalasi Faraz kilaylik n-ta korxonani o'z ichiga olgan sanoat birlashmasining T yillik planini tuzish masalasi qo'yilgan bulsin. Planlashtirilayotgan T davrning boshida birlashma uchun k0 miqdorda mablag ajratilgan bulsin. Bu mablag korxonalararo taksimlanadi. Korxonalar ajratilgan mablaglarni tula yoki kismani ishlatadi va shunga karab malum miqdorda daromad oladi. Keyingi bosqichlarda mablaglar korxonalararo qayta taksimlanishi mumkin. Shunday qilib, quyidagi masala hosil bo'ladi: korxonalararo mablaglarni taksimlash va qayta taksimlashni shunday tashkil etish kerakki, natijada birlashmaning T yil davomida olgan daromadlar yig'indisi maksimal bulsin. Xar yilning boshida birlashmadagi xar bir korxonaga ajratiladigan xom-ashyo, kapital mablag va yangilanishi kerak bo'lgan uskunalarning soni haqida yechim kabul kilinadi. Bu yechimlar to'plami boshqarish bo'ladi. Demak, t kadamdagi boshqarish vektor orqali ifodalanadi. Butun birlashmaning T davr ichida boshqarishini vektor orqali ifodalash mumkin. Bundan tashqari birlashmadagi korxonalar sistemasining taraqqiyot dinamikasini ifodalash uchun, ularni holat darajasini kursatuvchi vektor kiritamiz. Demak, yuqoridagidan xulosa qilib aytish mumkinki, boshqarish vektori sistemaning t kadamning boshidagi holatini kursatuvchi vektordir, yani . Sistemaning boshlang'ich holati X0 berilgan bo'ladi. maqsad funksiya sifatida birlashmaning T davr ichida oladigan daromadlar yig'indisini ifodalovchi funksiyani kiritamiz. Xar bir t kadamning ...