Ishlab chiquvchining ishi ko'pincha jumboqlarni hal qilish bilan taqqoslanishi mumkin

Bellman Funksiyalari va Tneglamalari

Bellman funktsiyalari. Bellman tenglamalari. Shartli ravishda optimal boshqaruvlar.

Dinamik dasturlash usuli optimallik tamoyiliga asoslanadi, birinchi marta 1953 yilda tuzilgan. Amerikalik matematik R. E. Bellman: har qanday bosqichlar natijasida tizim qanday holatda bo'lishidan qat'i nazar, keyingi bosqichda siz boshqaruvni tanlashingiz kerak, shunda keyingi barcha bosqichlarda optimal boshqaruv bilan birga u optimal daromadga olib keladi. qolgan barcha bosqichlarda, shu jumladan ushbu bosqichda g'alaba qozonish.
Muammoni hal qilishda har bir bosqichda optimal daromad keltirishi kerak bo'lgan nazorat tanlanadi. Agar biz barcha bosqichlar mustaqil deb hisoblasak, u holda optimal boshqaruv ushbu aniq bosqichda maksimal daromadni ta'minlaydigan hisoblanadi. Biroq, masalan, eskirgan asbob-uskunalarni almashtirish uchun yangi asbob-uskunalar sotib olayotganda, uni sotib olishga ma'lum mablag'lar sarflanadi, shuning uchun uni ishlatishdan keladigan daromad boshida kichik bo'lishi mumkin va keyingi yillarda yangi jihozlar ko'proq daromad keltiradi. Aksincha, agar joriy yilda daromad olish uchun eski uskunani qoldirish to'g'risida qaror qabul qilinsa, kelajakda bu katta yo'qotishlarga olib keladi. Ushbu misol quyidagi haqiqatni ko'rsatadi: ko'p bosqichli jarayonlarda har bir aniq bosqichda boshqaruv uning butun jarayonga kelajakdagi ta'sirini hisobga olgan holda tanlanishi kerak. Bundan tashqari, ushbu bosqichda boshqaruvni tanlashda, avvalgi bosqichning holati uchun mumkin bo'lgan variantlarni hisobga olish kerak. Masalan, i-yilda korxonaga qo'yilgan mablag'lar miqdorini aniqlashda i-yilgacha fondda qancha mablag' qolganligini va oldingi yilda qanday daromad olinganligini bilish kerak (i ​​- 1). )-chi yil.
Shunday qilib, qadam boshqaruvini tanlashda quyidagi talablarni hisobga olish kerak:

1. 
   oldingi bosqichning mumkin bo'lgan natijalari
   

;
. jarayonning oxirigacha qolgan barcha bosqichlarga boshqaruvning ta'siri (n-k).

Dinamik dasturlash masalalarida birinchi talab har bir bosqichda oldingi bosqichni yakunlashning mumkin bo'lgan variantlari to'g'risida shartli taxminlar qilish va har bir variant uchun shartli optimallashtirishni amalga oshirish orqali hisobga olinadi.

Ikkinchi talabning bajarilishi shu bilan ta'minlanadiki, bu masalalarda shartli optimallashtirish jarayonning oxiridan boshigacha amalga oshiriladi.
Shartli optimallashtirish.
Shartli optimallashtirish deb ataladigan muammoni yechishning birinchi bosqichida orqaga surish algoritmiga muvofiq har bir bosqichda oxirgidan boshlab barcha mumkin bo‘lgan holatlar uchun Bellman funksiyasi va optimal boshqaruv elementlari aniqlanadi.
Oxirgi, n-bosqichda optimal boshqaruv hisoblanadi Bellman funktsiyasi bilan aniqlanadi:

unga ko'ra maksimal barcha mumkin bo'lgan qiymatlardan tanlanadi

Keyingi hisob-kitoblar Bellman funktsiyasini har bir bosqichda bir xil funktsiya bilan bog'laydigan takrorlanish munosabati bo'yicha amalga oshiriladi, lekin oldingi bosqichda hisoblanadi.
Umuman olganda, bu tenglama quyidagi shaklga ega:

Bu maksimal (yoki minimal) k va S uchun nazorat o'zgaruvchisining barcha mumkin bo'lgan qiymatlari bilan aniqlanadi.

Shartsiz optimallashtirish.
Bellman funksiyasi va mos keladigan optimal boshqaruv elementlari n-dan birinchigacha bo'lgan barcha bosqichlar uchun topilgandan so'ng, muammoni hal qilishning cheklanmagan optimallashtirish deb ataladigan ikkinchi bosqichi amalga oshiriladi. Birinchi bosqichda (k = 1) tizimning holati ma'lum bo'lganligidan foydalanib, bu uning boshlang'ich holati S0 , biz barcha n bosqichlar uchun optimal natijani va birinchi bosqichda ushbu natija beradigan optimal boshqaruvni topishimiz mumkin. . Ushbu boshqaruvni qo'llaganingizdan so'ng, tizim shartli optimallashtirish natijalaridan foydalanib, biz ikkinchi bosqichda optimal boshqaruvni topishimiz mumkinligini bilib, boshqa holatga o'tadi va oxirgi n-bosqichgacha davom etadi. Dinamik dasturlashning hisoblash sxemasi tarmoq modellarida, shuningdek, oldinga siljish (boshidan) va teskari surish (oxiridan boshigacha) algoritmlari asosida tuzilishi mumkin.
46. ​​Optimal yo'llar uchun Bellman printsipi.
Bosqichli optimallashtirish metodologiyasiga asoslangan dinamik dasturlashning matematik apparati eng qisqa masofalarni topish uchun, masalan, tarmoq sifatida tasvirlangan geografik xaritada ishlatilishi mumkin. Mavjud transport tarmog'i bo'ylab jo'nash punktlari va mahsulotlarni qabul qilish punktlari o'rtasidagi eng qisqa masofalarni aniqlash muammosini hal qilish iste'molchilarni etkazib beruvchilarga maqbul bog'lash, samarasiz yuklarni kamaytirish orqali transport samaradorligini oshirish kabi iqtisodiy muammolarni hal qilishning dastlabki bosqichidir. kilometr va boshqalar.
Transport tarmog'i 10 ta tugundan iborat bo'lsin, ularning bir qismi avtomobil yo'llari bilan bog'langan. Rasmda yo'l tarmog'i va tegishli chekkalarda belgilangan tarmoqning alohida nuqtalari o'rtasida yuk birligini tashish narxi ko'rsatilgan. 1-banddan 10-bandga qadar tovarlarni etkazib berish yo'nalishini aniqlash kerak, bu esa eng kam transport xarajatlarini ta'minlaydi.