Dinamik dasturlash uchun optimallashtirish usullari

Misol 1. Quyidagi optimallashtirish masalasini ko'p bosqichli optimallashtirish muammosi sifatida shakllantiring.
Berilgan boshlang'ich massasi M bo'lgan iV-bosqichli raketa yordamida, massasi bo'lgan sayyoralararo stansiya. m . Paytida, raketa har bir bosqichi qo'shimcha tezligini qabul
A V = F (y, z),
qayerda y - bu bosqichda tezlashtirilgan massa; z - sahnaning o'zi massasi.
Raketa massasining shunday taqsimotini toping ( M) uning bosqichlari orasidagi oxirgi tezligi maksimal bo'ladi.
Bo'lsin d ^k (k =, N ) ommaviy bo'lishi saralanmaydi aro stantsiyasi boshlab th bosqichida, masalan, ommaviy g bilan sahna / ^L boshida faoliyat , va u oxirida .
Biz x ^k (k = O ... A0) bilan sayyoralararo stansiyaning massalari yig'indisini va unga tutash k qadamlarni belgilaymiz .
Keyin

Ko'p bosqichli optimallashtirish masalalari nazariyasi 50-yillarda amerikalik matematik R.Vellman tomonidan ishlab chiqilgan. Bunday muammoni hal qilish usuli dinamik protramming usuli deb ataladi va Vellmanning optimallik printsipiga asoslanadi.
Optimal traektoriyasi xususiyatiga ega ekanligini har bir butun final qismi bilan boshlanadigan KTH qadam (& = 1, N - 1), jarayonning qolgan qadamlar uchun optimal hisoblanadi. Boshqacha qilib aytganda, yechimning har bir bosqichida, butun jarayonning rivojlanishini hisobga olgan holda, faqat bitta qadam optimallashtiriladi. Va shunday qilib, qaror qabul qilishda kelajak hisobga olinadi. Biroq, har bir jarayonda kelajakka bog'liq bo'lmagan yakuniy k- bosqich mavjud. Shuning uchun, ushbu bosqichda nazorat maksimal ta'sirni olish imkonini beradi. K- qadamni rejalashtirib , ular unga ( - 1 ga), keyin ( - 2 ga) va hokazolarni biriktiradilar. Dinamik dasturlash jarayoni oxiridan boshigacha davom etayotganga o'xshaydi.
K-bosqichni rejalashtirish uchun siz (/: - 1) bosqichda tizim holatini bilishingiz kerak. Agar (k - 1) qadamdagi holat noma'lum bo'lsa, u holda bu bosqichda tizimning mumkin bo'lgan holatlari haqida turli xil taxminlar mavjud. Har bir taxmin uchun oxirgi optimal nazorat tanlash uchun qadam k. Bunday optimal nazorat shartli optimal deb ataladi.
^ -bosqichli jarayonni ko'rib chiqing (4.6-rasm). Keling, (k - 1) bosqichdagi jarayonning mumkin bo'lgan holatlari haqida bir qancha taxminlar qilaylik . Bu holatlarni S _k _i ,, S _k _ _] 2, ..., S _k ^ _r deb belgilaymiz . Ikkinchisi, biz bu davlatlar har bir uchun shartli optimal nazorat topish , ham _k , (x _t _ ,,), va _{K 2} (x _A ._ ,,), ..., va _{k r} (x ₄ , _ _r ).
Shunday qilib, KTH qadam rejalashtirilgan. Darhaqiqat, (k - 1) bosqichda tizim qanday holatni qabul qilsa, & -da qanday davom etishi allaqachon ma'lum.
Biz (k - 1) bosqichda xuddi shunday harakat qilamiz , k-bosqichda allaqachon tanlangan shartli optimal boshqaruvlarni hisobga olgan holda faqat shartli optimal boshqaruvlarni tanlash kerak . Natijada, barcha o'tishlarni tugatgandan so'ng, biz x ° koordinatasini olamiz.
Birinchi qadam uchun biz taxminlar qilmaymiz, chunki x ° qiymati berilgan, keyin biz allaqachon topilganlarni hisobga olgan holda optimal boshqaruvlarni topamiz. X ° dan x * gacha o'tib, biz butun jarayon uchun kerakli optimal boshqaruvni olamiz. Optimallik tamoyilidan foydalanib, optimal boshqariladigan u ,, ..., m _v _ , ketma-ketligi bilan qanoatlantirilishi kerak bo'lgan zarur shartlarni topamiz .

Guruch. 4.6. R.Vellman tomonidan dinamik dasturlash usuli sxemasi