Bellman funktsiyalari. Bellman tenglamalari. Shartli ravishda optimal boshqaruvlar

​​ O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi

islom karimov nomidagi toshkent davlat texnika universiteti

“elektronika va avtomatika” fakulteti

“ishlab chiqarish jarayonlarni avtomatlashtirish” kafedrasi

“Avtomatik Boshqarish Nazariyasi” fanidan

“Belman Funksiyasi va Tenglamasi” mavzuda

MUSTAQIL ISH

Bajardi: 2-kurs Talabasi
Gr: 11S-21 TJA
Xamrayev Sohib Abduxamidovich

Qabul qildi: ………………………………………………..

Toshkent - 2022

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.

Muammoda cheklov mavjud - diagrammada ko'rsatilgan marshrutlar bo'ylab faqat chapdan o'ngga harakat qilishingiz mumkin, ya'ni. Masalan, 7-bandni olganimizdan so'ng, biz faqat 10-bandga o'tish huquqiga egamiz va 5 yoki 6-bandga qaytolmaymiz. Transport tarmog'ining bu xususiyati o'nta nuqtaning har birini kamarlardan biriga bog'lash huquqini beradi. Agar biz undan yakuniy nuqtaga aynan k qadamda borsak, nuqta k-kamarga tegishli deb hisoblaymiz, ya'ni. aniq (k - 1)-chi oraliq nuqtaga kelishi bilan. Shunday qilib, 7, 8 va 9-bandlar birinchi zonaga, 5 va 6 - ikkinchi, 2, 3 va 4 - uchinchi va 1 - to'rtinchi zonaga tegishli. Keyin, k-bosqichda biz yuklarni k-belbog'ning nuqtalaridan yakuniy nuqtaga tashishning optimal yo'llarini topamiz. Biz jarayonning oxiridan boshlab optimallashtiramiz va shuning uchun k-bosqichga etib borgach, k-belbog'ning qaysi nuqtalari birinchi nuqtadan tashilgan yuk bo'lishi noma'lum.

Keling, belgi bilan tanishamiz:
k - qadam raqami (k = 1, 2,3,4);
i - tashish amalga oshiriladigan nuqta (i = 1,2,..., 9);
j - yuk yetkaziladigan nuqta (j = 2,3,.., 10);
Si,j - i nuqtadan j nuqtagacha yuk tashish narxi.
Fk (i) - i nuqtadan yakuniy nuqtagacha bo'lgan muammoni hal qilishning k-bosqichida yuk tashishning minimal qiymati.
Shubhasiz, yukni k-belbog'ning punktlaridan 10-bandga etkazib berishning minimal qiymati ushbu kamarning qaysi nuqtasida ekanligimizga bog'liq bo'ladi. K-kamarga tegishli bo'lgan elementning i soni k-bosqichda tizim holatining o'zgaruvchisi bo'ladi. Optimallashtirish jarayonning oxiridan boshlab amalga oshirilganligi sababli, u holda, k-kamarning i nuqtasida bo'lgan holda, yukni (k - 1)-chi kamarning nuqtalaridan biriga o'tkazish to'g'risida qaror qabul qilinadi, va keyingi harakat yo'nalishi oldingi bosqichlardan ma'lum. (k - 1) belbog'ning j raqami k-bosqichda boshqaruv o'zgaruvchisi bo'ladi.
Birinchi nazorat bosqichi uchun (k - 1) Bellman funktsiyasi yukni 1-belbog'ning nuqtalaridan yakuniy nuqtaga tashishning minimal qiymati, ya'ni. F1(i) = Si,10. Keyingi bosqichlar uchun xarajatlar ikki komponentdan iborat - yukni k-belbog'ning i nuqtasidan (k - 1)-chi tasmaning j nuqtasiga tashish narxi va punktdan tashishning minimal mumkin bo'lgan narxi. j oxirgi nuqtaga, ya'ni. - Fk - 1 (i). Shunday qilib, funktsional Bellman tenglamasi shaklga ega bo'ladi

Minimal xarajat i nuqtadan yakuniy nuqtagacha bo'lgan harakatning optimal yo'nalishi bo'lgan j* ma'lum bir qiymatda erishiladi. To'rtinchi bosqichda biz 4-belbog'ga o'tamiz va tizimning holati aniq i=1 bo'ladi. F4(1) funksiyasi yukni 1-nuqtadan 10-gachasigacha olib oʻtishning mumkin boʻlgan minimal qiymati. Optimal marshrut barcha bosqichlarni teskari tartibda tahlil qilish natijasida aniqlanadi va k-bosqichda ba'zi j boshqaruvchini tanlash (k - 1) bosqichda tizim holatining aniq bo'lishiga olib keladi. .

men bosqich. Shartli optimallashtirish

1. 
   usul. k = 1 .
   

10-bandga birinchi qadamda yuk 7,8 yoki 9-bandlardan etkazib berilishi mumkin.

2-qadam. k = 2.

Ikkinchi bosqichdagi funktsional tenglama quyidagi shaklni oladi:


Ikkinchi bosqichda yukning barcha mumkin bo'lgan harakatlari va hisoblash natijalari quyidagi 33.2-jadvalda ko'rsatilgan:

3. 
   - qadam k = 3
   

4-qadam k = 4

II bosqich. Shartsiz optimallashtirish.

Shartli optimallashtirish bosqichida 1-banddan 10-bandgacha yuk tashishning minimal qiymati F4(1) = 20 ekanligi aniqlandi. Bu natijaga tovar 1-banddan 3-bandga oʻtganda erishiladi. Jadvalga ko'ra. 52.3, 3-banddan 6-bandga, keyin 7-bandga (52.2-jadvalga qarang) va undan yakuniy nuqtaga o'tish kerak (52.1-jadvalga qarang). Shunday qilib, yuklarni yetkazib berishning optimal marshruti: 1 => 3 => 6 => 7 => 10. U rasmda qalin strelkalar bilan ko'rsatilgan.