Dinamik dasturlash

Dinamik dasturlash Reja: 1.Dinamik dasturlashning asosiy masalasi 2 Investitsiyani optimal taqsimlash masalasi 1.Dinamik dasturlashning asosiy masalasi Ma'lum bir boshqaruv jarayoni boshlang'ich vektor bilan xarakterlanuvchi boshlang'ich holatda turibdi deb faraz qilaylik. Boshlang'ich holatlar to'plamini orqali belgilaymiz. Vaqt o'tishi bilan jarayon o'zgaradi va oxirgi holatga o'tadi. Oxirgi holatlar to'plamini orqali belgilaymiz. holatdan ga o'tish jarayoni N ta bosqichga bo'linib ketadi. Jumladan, agar jarayon i-bosqichda holatda bo'lsa, uning i+1 bosg'ichdagi holati nafaqat holatlar vektori, balki i-bosqichdagi topilgan yechimi orqali aniqlanadi. Bundan kelib chiqib, keyingi bosqich holatlarining vektorini orqali ifodalash mumkin. yechim esa har bir bosqichda mavjud yechimlarning to'plamidan olinib va maqsad funksiyasining qiymatini aniqlaydi. f(S) maqsad funksiyasini funksiyalar yig'indisi ko'rinishida tasvirlaymiz, ularning qiymati bosqichdan bosqichiga o'tganda o'zgaradi: ' (6.1) U holda dinamik dasturlashning asosiy masalasi shundan iborat bo'ladiki, u mavjud yechimlarning to'plamidan shunday U* yechimni topishi kerakki, bu yechim jarayonni boshlang'ich holatdan ga o'tkazganda, maqsad funksiyasi shartlar bajarilganda ekstremal qiymatlar qabul qilishiga imkon yaratishi kerak. yechish paytida dinamik dasturlash masalasi soddaroq bo'lgan masalalarga ajratib yuboriladi (tabiiy yoki sun'iy usulda). Har bir bosqichda ushbu masalalarning biron biri yechiladi, jumladan optimal yechim kelajakni hisobga olgan holda tanlanadi, ya'ni har bir bosqichda jarayonni optimallashtirib, keyingi bosqichlar haqida unutmaslik kerak. Oxirgi bosqich, (N-1)-si kelajakka bog'liq emas, shuning uchun bu bosqichda maqsad funksiyasining ekstremal qiymatini beruvchi yechim olinadi. N-bosqichda optimal yechimni olish uchun tizimning (N-1)-bosqichdagi holatini bilish kerak. (N-1)-bosqichda jarayonning holati noma'lum bo'lgani uchun, jarayonlarning berilgan bosqichdagi mumkin bo'lgan holatlari haqida turli xil farazlar qilinadi va har bir faraz uchun N-bosqichdagi optimal yechim tanlanadi. Shunday qilib, N-bosqichdagi optimal yechim topildi. Endilikda, bosqichda olingan optimal yechimni hisobga olib, (N-1) bosqichdagi optimal yechim topiladi va h.k. Natijada jarayonning boshlang'ich holatiga kelinadi. Birinchi bosqich uchun jarayonning mavjud holatlari haqida farazlar qilinmaydi, chunki holat ma'lum. Birinchi bosqichning optimal yechimi ikkinchi bosqichda olingan optimal yechimdan kelib chiqqan holda topiladi. Butun jarayonning optimal yechimi hamma bosqichlarda ( dan gacha) olingan optimal yechimlarni ko'rib chiqilib xulosa qilish orqali olinadi. Dinamik dasturlash masalalarini yechishning asosiy usuli funksional tenglamalar usulidir. Dinamik dasturlashning funksional tenglamasi har bir masalasi uchun W funksiyaning o'ziga xos ko'rinishi va S,U kattaliklar bilan xarakterlanuvchi xususiy ko'rinishga ega. Dinamik dasturlash masalasining funksional tenglamasini umumiy ko'rinishda ham yozib olish mumkin. Dinamik dasturlash masalalari oxiridan qarab boshiga yechilgani uchun, oxirgi bosqich (N=1) dagi funksional tenglama quyidagi ko'rinishga ega: . (6.2) Bu yerda - - oxirgi holatdan boshlab maqsad funksiyasining nol bosqichlaridagi ekstremal qiymati. Yakuniy holat chegaralaridan tashqarida jarayon ko'rib chiqilmagani uchun, . N-bosqich uchun funksional tenglama ...