1. Dinamik dasturlashning tamoyili Dinamik dasturlash masalalarini yechish sxemasi

10-mavzu. Dinamik dasturlash tamoyillari

TATU TAD kafedrasi

Sharipov Bahodir

Reja:

1. Dinamik dasturlashning tamoyili

2. Dinamik dasturlash masalalarini yechish sxemasi.

4. Masalalar

1. Dinamik dasturlashning tamoyili

Maqsad funktsiyasining koʼrinishi va oʼzgaruvchilarga qoʼyiladigan cheklanish shartlari sistemasiga koʼra matematik dasturlash asosan olti turga ajratiladi:

1. Chiziqli dasturlash. Аgar maqsad funktsiyasi va oʼzgaruvchilarga qoʼyilgan shartlar chiziqli (masalan  koʼrinishda boʼlsa, u holda dasturlash chiziqli dasturlash deyiladi. Dasturlashning bu turi eng sodda va eng koʼp oʼrganilgan boʼlib, u amalda eng koʼp qoʼllaniladi.

2. Chiziqli boʼlmagan dasturlash. Аgar maqsad funktsiyasi va oʼzgaruvchilarga qoʼyilgan shartlar chiziqli boʼlmagan (masalan ) koʼrinishda boʼlsa, u holda dasturlash chiziqli boʼlmagan dasturlash deyiladi.

3. Dinamik dasturlash. Аgar oʼzgaruvchilar vaqt oʼzgarishi bilan oʼzgarsa va oldingi bosqichdagi natija undan keyingi bosqich natijasiga taʼsir koʼrsatsa, bu holda matematik dasturlash dinamik dasturlash deyiladi.

Bu turdagi dasturlar iqtisodiy masalalarda koʼp uchraydi.

Bundan tashqari yuqoridagi uch turdagi dasturlashdagi oʼzgaruvchilarning qabul qilish qiymatlariga koʼra:

1.     Diskret dasturlashtirish. Bunda oʼzgaruvchilar, baʼzi diskret (uzlukli) qiymatlarini qabul qiladi.

2.     Butun sonli dasturlashtirish. Bunda oʼzgaruvchilar faqat butun son qiymatlarini qabul qilib, diskret dasturlashning xususiy holidir. (masalan avtomobillar, binolar, pasajirlar).

3.     Stoxastik dasturlashtirish. Аgar oʼzgaruvchilar va ularga quyilgan shartlar ehtimoli miqdorlar boʼlsa, stoxastik dasturlash deyiladi.

Dinamik dasturlash  — matematikaning koʻp bosqichli eng maqbul (optimal) boshqarishga oid masalalar nazariyasi va ularni yechish usullarini oʻrganuvchi boʻlimi. Bu yerda dasturlash tushunchasi "rejalashtirish", "qaror qabul qilish", yaʼni "bir qarorga kelish" maʼnolarida ham qoʻllaniladi. Bu prinsip dinamik dasturlashning asosiy masalasini oxiridan boshlab yechishga imkon beradi. Dinamik dasturlash chekli bosqichli jarayonlardan tashqari, uzluksiz davom etadigan jarayonlar uchun ham ishlab chiqilgan. U texnika, kosmik parvozlar, xalq xoʻjaligini rejalashtirishning turli masalalarida eng maqbul yechimlar topishga imkon beradi. Dinamik dasturlash usuli elektron hisoblash mashinalari, kompyuterlar yordamida tatbiq qilinadi.

Dinamik dasturlash - bu matematik dasturlash bo'limlaridan biri bo'lib, unda yechish jarayonini alohida bosqichlarga bo'lish mumkin. Ushbu bo'lish turli xil printsiplarga muvofiq amalga oshiriladi. Ba'zi vazifalar vaqt bo’yicha, boshqalarida boshqaruv ob'ektlari bo’yicha. Ba'zan bo'linish sun'iy ravishda amalga oshiriladi. Ushbu yondashuv bizga bitta katta o'lchovli muammoni kichik o'lchamdagi ko'plab muammolarga bo’lish imkonini beradi. Bu hisoblash hajmini sezilarli darajada kamaytiradi va boshqaruv qarorlarini qabul qilish jarayonini tezlashtiradi. Dinamik dasturlash tamoyili shundaki, eng optimal yo'lning har qanday qismi optimaldir. Bu har bir bosqichda oldingi bosqichlarda topilgan yo'lning qismlaridan foydalangan holda optimal yo'lni topishga imkon beradi.

Optimallashtirishning eng taniqli usullaridan biri bu o'tgan asrning elliginchi yillarida amerikalik olim Richard Bellman tomonidan taklif etilgan dinamik dasturlashdir. Dinamik dasturlashni ko'p bosqichli qarorlar qabul qilish jarayonlarini tahlil qilishda ishlatiladigan matematik protseduralar to'plami sifatida aniqlash mumkin. O'z navbatida, qaror qabul qilishning ko'p bosqichli jarayoni umumiy maqsadga erishishga qaratilgan izchil qarorlar qabul qilinadigan faoliyat sifatida belgilanishi mumkin. Dinamik dasturlashning mohiyati optimallashtirish tamoyiliga asoslanadi. Buni shunday tariflash mumkin – optimal strategiya shunday xususiyatga egaki, dastlabki holat va yechim qanday bo'lishidan qat'iy nazar, keyingi yechimlar dastlabki qarordan keyin yuzaga keladigan holat uchun eng optimal strategiyaga ega bo'lishi kerak.
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 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.
4. Masalalar
Eng qisqa yo'lni aniqlash algoritmi quyidagi bosqichlardan iborat:

1-qadam. n = 1, S₁(i) = S_i9. Birinchi bosqichda 9-nuqtaga ikkinchi bosqichning 6, 7, 8 nuqtalaridan borish mumkin. Shuningdek: S₁(6) = 15; S₁(7) = 3; S₁(8) = 10.

2-qadam. N = 2, bu yerda biz uchinchi bosqichning (4 va 5) nuqtalaridan ikkinchi bosqichga qadar bo'lgan yo'llarni ko'rib chiqamiz. Bu yerda funktsional Bellman tenglamasi quyidagi shaklga ega bo’ladi:

Shuningdek quyidagiga ega bo’lamiz:

Shartli ravishda optimal yo'l (5-7);

Shartli ravishda optimal yo'llar (4-6 va 4-8).