Mavzu: Statistik modellashtirishda eng kichik kvadratlar usuli. Dinamik dasturlashning tamoyili

2. Dinamik dasturlash masalalarini yechish sxemasi. 
Ko'p bosqichli qarorlarni qabul qilish jarayonlari turli xil vaziyatlarda 
uchrashi mumkin, masalan, zaxiralarni boshqarish, resurslarni taqsimlash yoki 
kosmik kemalarni boshqarish vazifalari. Har bir ko'p bosqichli qarorlarni qabul 
qilish jarayonini yo'naltirilgan tarmoqdagi eng qisqa yo'lni topishning eng 
tushunarli ko'p bosqichli jarayonini ishlab chiqish deb hisoblsh mumkin (10.1-
rasm). Ushbu misoldan foydalanib, R. Bellmanning optimallashtirish tamoyili 
mohiyatini namoyish etish mumkin. 
10.1-rasm. Yo'naltirilgan tarmoq 
Yo'naltirilgan tarmoq N qaror bosqichlariga ega bo'lsin. 10.1-rasmdan 
ko’rinib turibdiki N = 5 ga teng. Quyidagi belgilashni kiritamiz: 
n - bosqich raqami (n = 1, 2, 3, 4,5); 
i - harakat amalga oshirilgan joy (i = 1, 2, ..., 8); 
j - harakat yo'naltirilgan nuqta (j = 2, 3, ..., 9); 
Sij - i nuqtadan j nuqtagacha bo'lgan masofa; 
Sn (i) - bu masalani yechishning n-bosqichida i nuqtadan oxirgi nuqtagacha 
bo'lgan minimal masofa. 
Nuqta n-bosqichga tegishli deb taxmin qilinadi, agar undan aniq n bosqichda 
yakuniy nuqtaga o'tish mumkin bo'lsa. Ko’rinib turibdiki, n-bosqichning biror 

---

3 
nuqtasidan 9-nuqtagacha bo’lgan minimal yo’l shu bosqichning qaysi nuqtasida 
ekanligimizga bog'liq bo'ladi. N-bosqichga tegishli bo'lgan n-elementning raqami 
tizimning n-bosqich holat o'zgaruvchisi bo'ladi. Optimallashtirish odatda jarayon 
oxiridan boshlanadi, chunki n-bosqichning ba'zi nuqtalarida bo'lganligi sababli (n - 
1) - bosqichning nuqtalaridan biriga o'tish to'g'risida qaror qabul qilinadi va 
keyingi harakat yo'nalishi oldingi bosqichlardan ma'lum bo’ladi. (N - 1) 
bosqichning j raqami n bosqichda boshqarish o'zgaruvchisi bo'ladi. 
Birinchi bosqich (n = 1) uchun maqsad funktsiya (Bellman funktsiyasi) 
birinchi bosqich (6, 7, 8) nuqtalaridan 9 oxirgi nuqtaga qadar bo'lgan minimal 
yo'ldir, ya'ni S1 (i) = si9. Keyingi bosqichlar uchun yo'l uzunligi ikki yig’indidan 
iborat –n-bosqichning i nuqtasidan j (n - 1)-bosqichning j nuqtasigacha bo’lgan Sij 
yo’li va j nuqtadan oxirgi nuqtagacha bo'lgan yo'lning minimal uzunligi, ya'ni Sn - 
1 (j). Shunday qilib, funktsional Bellman tenglamasi quyidagi shaklga ega bo'ladi: 
Minimal uzunlik ma'lum bir qiymat j* da erishiladi, bu i nuqtadan oxirgi 
nuqtaga harakatning optimal yo'nalishidir. Beshinchi bosqichda biz boshlang'ich 
nuqtaga etib boramiz va tizimning holati i = 1 bo’lib aniqlangan bo’ladi. S5(1) 
funktsiyasi 1-chi nuqtadan 9-nuqtagacha bo’lgan minimal yo’lni ifodalaydi. 
Optimal yo'nalish barcha bosqichlarni teskari tartibda tahlil qilish orqali 
aniqlanadi.