T. M. Magrupov, B. M. Mirshaxodjayev

Dinamik dasturlash masalasining umumiy ko‘rinishi. Op- 
tim allik tam oyili. Yuqoridagi ko‘rilgan sodda dinamik dasturlash 
masalalari dinamik dasturlash usuli haqida umumiy shunday 
tushunchaga kelishga undaydi: qadamli optimallash bir yo‘nalishda 
«shartli» ikkinchi yo‘nalishda «shartsiz». Dinamik dasturlash usuli 
juda qudratli va foydali optimal boshqaruv usuli hisoblanadi, uning 
uchun yechim butunligi ham, maqsad funksiyaning chiziqsizligi 
ham, yechimga qo‘yiladigan chegaralar ko'rinishlari ham murakkab 
emas. Lekin chiziqli dasturlashdan farqli ravishda dinamik 
dasturlash qandaydir hisoblash prosedurasiga keltirilmaydi, u mos 
formulalar yozib bo‘lingandan so‘nggina mashinaga uzatilishi 
mumkin, lekin ko‘pincha bu oson ish emas.
Bu m a’ruzada biz boshlovchilar uchun maslahatlar tariqasida, 
dinamik dasturlash masalalarini qanday qo‘yish, ulami qanday 
tartibda yechish kabi umumiy ko‘rsatmalarni keltiramiz.
Birinchi savol, S boshqarish tizimning holati har bir qadam 
oldidan 
qanday 
parametrlar 
bilan 
xarakterlanadi? 
Shu 
parametrlaming muvaffaqiyatli tanlovidan optimillash masalasining 
muvaffaqiyatli yechimi bog‘liq. Yuqorida ko‘rgan misollarimizda 
tizimning holati juda ko'p bo‘lmagan parametrlar soni bilan 
xarakterlanadi, ya’ni birinchi misolda ikkita koordinata orqali, 
ikkinchi va uchinchi misollarda bitta son bilan xarakterlanadi. Lekin 
1
hayotda bunday juda sodda misollar kam uchraydi.
Tizimlar ko‘pincha juda k o 'p paramertlar orqali xarakterlanadi 
va mos ravishda har bir qadam oldidan barcha variantlami qarab 
chiqish va optimal shartli boshqaruv topish * juda qiyinchilik 
tug‘diradi. Ko'pincha dinamik dasturlash masalalari kompyu-
121

---

terlarda, EHM yechiladi, shuning uchun masalani to ‘g ‘ri qo‘yilishi 
juda katta ahamiyatga ega.
Ikkinchi masala tizimni ifodalash va boshqaruvni tartiblashdan 
so‘ng - bu qadamlarga bo‘lishdir. Ba’zi hollarda bu masalaning 
qo‘yilishida beriladi, masalan iqtisodiy masalalarda (xo‘jalik 
yillari), lekin ko‘pincha qadamlarga bo‘lishni sun’iy ravishda 
kiritishga to‘g ‘ri keladi. Bu yerda qadamlar soni ikkita holatni 
hisobga olgan holda boMinadi: 1) qadam yetarli darajada kichik 
b o lish i kerakki, qadamli boshqaruv sodda bo‘lsin uchun; 2) qadam 
juda ham kichik bo‘lishi kerak emas, chunki juda ko‘p foydasiz, 
faqat optimal yechim prosedurasini murakkablashtiradigan, lekin 
maqsad funksiyaning optimumiga ta ’sir ko‘rsatmaydigan hisob- 
kitoblami amalga oshirmaslik uchun;
Dinamik dasturlash masalalari 
asosida 
yotgan 
umumiy 
tamoyilni ifodalaymiz, uni ko‘pincha optimallik tamoyili deb 
ataladi. Navbatdagi qadam oldidan S tizimning holati qanday 
boMishidan qat’i nazar, shu qadamda boshqaruvni shunday tanlash 
kerakki, shu qadamdagi yutuq va qolgan qadamlardagi optimal 
yutuqlar yig‘indisi maksimal bo‘lishi kerak.
Endi boshlovchilar uchun dinamik dasturlash masalalarini 
qo‘yilishidagi bir necha amaliy ko‘rsatmalarni beramiz:
l.S boshqaruv tizimining holatini xarakterlovchi parametrlarni 
har bir qadam oldidan tanlash.
2. Amalni etaplarga (qadamlarga) bo‘lib chiqish.
3.Наг bir qadam uchun Xi qadam boshqaruvlari to'plam ini va 
ularga qo‘yilgan chegaralami aniqlash.
4 .Agar tizim bundan oldin S holatda boMganda Xj qadam 
boshqaruvi i-qadamda qanday yutuq keltirishini aniqlash, ya’ni 
yutuq funksiyasini quyidagicha yozish:
Wj=fj(S, Xj) 
(37)
5
.S tizimning holati x, qadam boshqaruvida i-chi qadamda 
qanday o ‘zgarishini aniqlang. U yangi holatga o ‘tadi.
S”= (»i(S, x,) 
(38)
122

---

6
.Dinamik dasturlashning asosiy shartli optimal yutuqni W,(s) 
ifodalaydigan rekkurent tenglamalarini (i-qadamdan oxirigacha) 
yozib chiqish.
Wj(s) = max { fi(S, Xi) + W,+
i
(<
d
j(S, Xi) )} 
(39)
x
7. Oxirgi (m) qadamning shartli optimumini S tizimning 
holatiga qarab har bir qadam uchun shartli optimallik yutuqni 
quyidagi formula bo‘yicha hisoblab,