Jarayonlar tadqiqoti va optimal boshqaruv fanidan mustaqil ishi

Dinamik dasturlashning asosiy masalasi:
Ma’lum bir boshqaruv jarayoni boshlang’ich vector bilan harakterlanuvchi 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 bosqichdagi holati mafaqat holatlar vektori, balki i-bosqichdagi topilgan yechimi orqali aniqlanadi. Bundan kelib chiqib, keying bosqich holatlarining vektorini orqali ifodalash mumkin. Yechim esa har bir bosqichda mavjud yechimlarning to’plamidan olinib va maqsad funksiyasining qiymatini aniqlaydi. maqsad funksiyasini funksiyalar yig’indisi ko’rinishida tasvirlaymiz, ularning qiymati bosqichdan bosqichga o’tganda o’zgaradi:

U holda dinamik dasturlashning asosiy masalasi shundan iborat bo’ladiki, u mavjud yechimlarning to’plamidan shunday 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 dasturlashning asosiy 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, keying bosqichlar haqida unuymaslik kerak.
Oxirgi bosqich, -si kelajakka bog’liq emas, shuning uchun bu bosqichda maqsad funksiyasining ekstremal qiymatini beruvchi yechim olinadi. N-bosqichda optimal yechimi olish uchun tizimning -bosqichdagi holatini bilish kerak. -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 topiladi. Endilikda, bosqichda olingan optimal yechimni hisobga olib, 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 harakterlanuvchi hususiy 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 dagi funksional tenglama quydagi ko’rinishga ega:

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 quyidagi ko’rinishda yoziladi:

Bu yerda holatdan boshlab hamma N bosqichlar uchun maqsad funksiyasining ekstremal qiymatidir; holatdan boshlab hamma N-1 bosqichlar uchun maqsad funksiyasining ekstremal qiymatidir; -qabul qilingan yechim natijasida holatdan boshlab N-bosqichda olingan maqsad funksiyasining qiymati.
Dinamik dasturlash masalasi funksional tenglamalar usulida quyidagi ketma ketlik bo’yicha yechiladi:

1. 
   Yakuniy holat (N-1 bosqich uchun) funksional tenglama yozib olinadi. bo’lgani uchun Belgilangan holatlar va yechimlar hamda ularga javob beruvchi qiymatlar ko’rib chiqiladi. Yechimlar orasida shunday tanlansinki, u ni taminlaydi;
   
2. 
   Keyingi, oxirgidan bitta oldingi (N=2) bosqichga o’tiladi. Berilgan bosqich uchun funksional tenglama quyidagi qiymat qabul qiladi.
   

Har bir mavjud holat uchun yechimga qarab qiymat topiladi. So’ngra yig’indi (unda oxirgi bosqichning qiymatlari hisobga olingan) lar solishtiriladi va har bir uchun ekstremal yig’indi va optimal yechim topiladi, ya’ni funksiya ekstremal qiymat qabul qiluvchi yechim topiladi. Huddi shu tarzda (N=3, N=4, va h.k) bosqichdan (N=N) bosqichgacha o’tiladi;

3. 
   funksional tenglamani birinchi N=N bosqich uchun yozib olishadi. Berilgan bosqichda jarayonning mavjud holatlari haqida faraz qilinmaydi, chunki holat ma’lum. Bu holat uchun optimal qiymatni ikkinchi bosqichning hamma shartli-optimal yechimlarini hisobga olgan holda aniqlash kerak;
   
4. 
   Butun jarayonni to’g’ri yo’l bo’ylab dan ga qarab o’tiladi va butun jarayon uchun maqsad funksiyasiga ekstremal qiymat beruvchi optimal qiymat tanlashadi.
   

Xulosa. Dinamik dasturlash deb matematik modellari ko’p bosqichli va dinamik jarayonli harakterga ega bo’lgan chiziqsiz dasturlashning maxsus masalalari va optimal boshqaruv masalalarini yechishning hisoblash usuliga aytiladi. Bu usul jarayonlarning ketma-ket tahliliga asoslangandir. Shunday tahlil qilinadigan maxsus masalalardan biri resurslarni taqsimlash masalasidir. Bu maxsus masala muhim ahamiyatga ega bo’lib, uni dinamik dasturlash masalasi sifatida qarab o’rganamiz.