Insoniyat, jamiyat tashkil eta boshlanganidan beri, boshqaruvning samarali usullari izlanib, tashkillashtirilib kelinmoqda

2.2-Dinamik programmalashtirish yordamida optimal yechimni aniqlash algoritmi.

Dinamik dasturlash algoritmi yoki metodi (usuli) masalani ketma-ket optimallashtirish pirinstipidan foydalanishga asoslangan, bunda umumiy masalaning yechimi alohida qism masalalarining qator yechimlariga bo’laklanadi, so’ngra yagona yechimga yig’iladi. 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. Ko’p hollarda alohida qism masalalar bir hil bo’ladi va bitta mumiy yechim hisoblash vaqtini sezilarli qisqartiradi.
Dinamik optimizastiyalash yordamida eng qisqa yo’lni topish yoki optimizastiyalash bo’yicha keng masallar sinfini yechish mumkin va boshqa masalalarda yechishning mumkin bo’lgan variantlarni tanlash “klassik”usul hisob-kitob vaqtining ortib ketishiga olib keladi, ba’zida umuman maqbul emas. Dinamik dasturlashning klassik masalasi-bu ryukzak haqida masala: ma’lum bir narxdagi va og’irlikdagi bir necha predmet (narsa)ning miqdori (soni) berilgan va ryukzak hajmidan oshmaydigan maksimal narx va og’irlikdagi predmetlar to’plamini tanlash kerak. Optimal yechimni izlashda barcha variantlarni klassik tanlash sezilarli vaqtni oladi, dinamik usullar yordamida esa masala maqbul muddatda yechiladi.Mahalliy optimallashtirishga murojaat qilingan greedy algoritmlardan farqli oʻlaroq, dinamik algoritmlar muammoni umumiy optimallashtirishga asoslanadi.Umumiy yechimga erishish uchun yechimlar birlashtiriladigan algoritmlarni boʻlish va yengishdan farqli oʻlaroq, dinamik algoritmlar kichikroq masalaning natijasini ishlatadi va undan keyin katta-kichik masalani optimallashtirishga harakat qiladi. Dinamik algoritmlar Memoizatsiyadan foydalanib, yechilgan muammolarning natijasini eslaydi.
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.
Matematik optimallashtirish (alternativ ravishda imlo optimallashtirish) yoki matematik dasturlash bu ba'zi mavjud alternativalar orasidan eng yaxshi elementni tanlash (ba'zi mezonlar bo'yicha). Turlarni optimallashtirish muammolari informatika va muhandislikdan tortib amaliy tadqiqotlar va iqtisodiyotgacha bo'lgan barcha miqdoriy fanlarda yuzaga keladi va hal qilish usullarini ishlab chiqish asrlar davomida matematikada qiziqish uyg'otdi.
Eng oddiy holatda, optimallashtirish muammosi ruxsat berilgan to'plam ichidan kirish qiymatlarini muntazam tanlash va funktsiyaning qiymatini hisoblash orqali real funktsiyani maksimal darajaga ko'tarish yoki kamaytirishdan iborat. Optimallashtirish nazariyasi va texnikasini boshqa formulalarga umumlashtirish amaliy matematikaning katta qismini tashkil etadi. Umuman olganda, optimallashtirish turli xil ob'ektiv funktsiyalar va domenlarning har xil turlarini o'z ichiga olgan aniqlangan domen (yoki kirish) berilgan ba'zi ob'ektiv funktsiyalarning "eng yaxshi mavjud" qiymatlarini topishni o'z ichiga oladi.
Richard E. Bellman nomli Bellman tenglamasi dinamik dasturlash deb nomlanuvchi matematik optimallashtirish usuli bilan bog'liq optimizm uchun zaruriy shartdir. U ba'zi bir boshlang'ich tanlovlar natijalarini qaytarish nuqtai nazaridan ma'lum bir vaqt ichida qarorning "qiymatini" va qolgan dastlabki echimlarning natijasi bo'lgan "echimning" qiymatini yozadi. Bellmanning "optimizm printsipi" da ta'kidlaganidek, optimallashtirish muammosi sodda dasturlarning ketma-ketligiga aylantirildi.Bellman tenglamasi dastlab muhandislik nazorati nazariyasi va amaliy matematikadagi boshqa mavzularga qo'llanildi va keyinchalik iqtisodiy nazariyada muhim vosita bo'ldi; dinamik dasturlashning asosiy tushunchalari Jon Von Neumann va Oskar Morgensternning O'yinlar va iqtisodiy xulq-atvor nazariyasi va Avraam Voldning ketma-ket tahlilida keltirilgan.
Optimal boshqaruv ma'lum bir tizim uchun nazorat qonunini topish muammosi bilan shug'ullanadi maqbullik mezonlari erishildi. Boshqarish muammosi quyidagilarni o'z ichiga oladi xarajat funktsional bu funktsiya holat va boshqaruv o'zgaruvchilari. An optimal nazorat to'plamidir differentsial tenglamalar xarajatlar funktsiyasini minimallashtiradigan boshqaruv o'zgaruvchilarining yo'llarini tavsiflash. Optimal boshqaruv yordamida olish mumkin Pontryaginning maksimal printsipi (a zarur shart Pontryaginning minimal printsipi yoki oddiygina Pontryaginning printsipi deb ham ataladi),[6] yoki hal qilish orqali Xemilton-Jakobi-Bellman tenglamasi (a etarli shart).
Biz oddiy misol bilan boshlaymiz. Tepalikli yo'lda tekis chiziqda sayohat qilayotgan mashinani ko'rib chiqing. Savol shuki, haydovchi qanday qilib gaz pedalini bosishi kerak minimallashtirish umumiy sayohat vaqti? Ushbu misolda atama nazorat qonuni haydovchining tezlatgichni bosishi va vitesni almashtirish usuliga tegishli. The tizim ham mashinadan, ham yo'ldan iborat va maqbullik mezonlari umumiy sayohat vaqtini minimallashtirishdir. Boshqarish muammolari odatda yordamchini o'z ichiga oladi cheklovlar. Masalan, mavjud yoqilg'ining miqdori cheklangan bo'lishi mumkin, gaz pedalini avtoulov polidan itarib bo'lmaydi, tezlik chegaralari va boshqalar.
Tegishli xarajat funktsiyasi matematik ifoda bo'lib, sayohat vaqtini tezlik, geometrik mulohazalar va dastlabki shartlar tizimning. Cheklovlar ko'pincha xarajat funktsiyasi bilan almashtiriladi. Bu bilan bog'liq yana bir maqbul boshqaruv muammosi, ma'lum bir kursni ma'lum miqdordan oshmagan vaqt ichida bajarishi kerakligini hisobga olib, avtomobilni yonilg'i sarfini minimallashtirish uchun haydash yo'lini topish bo'lishi mumkin. Shunga qaramay, yana bir bog'liq nazorat muammosi, vaqt va yoqilg'i uchun taxmin qilingan pul narxlarini hisobga olgan holda, sayohatni yakunlash uchun umumiy pul xarajatlarini minimallashtirish bo'lishi mumkin.
Ko'plab optimal boshqarish muammolari bo'yicha umumiy echim strategiyasi - bu xarajat uchun echim topish (ba'zan shunday deb ham ataladi) soya narxi . Xarajat navbatdagi holat o'zgaruvchisini kengaytirish yoki qisqartirishning chegara qiymatini bitta raqamda umumlashtiradi. Cheklangan qiymat nafaqat keyingi navbatda unga tegishli bo'lgan yutuqlar, balki dasturning davomiyligi bilan bog'liq. Qachon yaxshi analitik usulda echilishi mumkin, ammo odatda, sezgi yechimning xarakterini anglashi va tenglama echuvchisi qiymatlar uchun sonli echim topishi uchun uni etarlicha yaxshi tasvirlash mumkin.
Olingan , boshqarish uchun eng maqbul qiymatni o'zgartirish, odatda, bilish shartli differentsial tenglama sifatida echilishi mumkin . Shunga qaramay, kamdan-kam holatlarda, ayniqsa doimiy muammolarda, nazoratning yoki davlatning qiymatini aniq olish mumkin. Odatda, strategiya eng maqbul boshqaruvni tavsiflovchi chegaralar va mintaqalar uchun echim topadi va haqiqiy tanlov qiymatlarini o'z vaqtida ajratish uchun raqamli echimdan foydalanadi.
Optimal boshqaruv nazariyasi yordamida echilishi mumkin bo'lgan deyarli har qanday muammoni tegishli Bellman tenglamasini tahlil qilish orqali hal qilish mumkin. vaqtni optimallashtirish muammolari. Uzluksiz optimallashtirish muammolarida shunga o'xshash tenglama qisman differentsial tenglama bo'lib, uni Hamilton-Yakobi-Bellman tenglamasi deyiladi.
Bellman tenglamasini tushunish uchun bir nechta asosiy tushunchalarni tushunish kerak. Birinchidan, har qanday optimallashtirish muammosi bir nechta maqsadga ega: sayohat vaqtini minimallashtirish, xarajatlarni minimallashtirish, foydani ko'paytirish, foydali xizmatlarni ko'paytirish va boshqalar. Ushbu maqsadni tavsiflovchi matematik funktsiya ob'ektiv funktsiya deb ataladi. Dinamik dasturlash ko'p bosqichli rejalashtirish muammosini turli bosqichlarda sodda qadamlarga aylantiradi. Shuning uchun, qaror qabul qilingan vaziyat vaqt o'tishi bilan qanday o'zgarishini kuzatib borishni talab qiladi. To'g'ri qaror qabul qilish uchun zarur bo'lgan hozirgi vaziyat haqida ma'lumot "davlat" deb nomlanadi.] Masalan, har bir vaqtda qancha iste'mol qilish va sarflashni hal qilish uchun odamlar o'zlarining dastlabki boyliklarini (boshqa narsalar qatorida) bilishlari kerak. Shuning uchun, boylik {\ displaystyle (W)} ularning holatlaridan biri bo'lar edi, lekin boshqalar ham bo'lishi mumkin.
Vaqtning istalgan vaqtida tanlangan o'zgaruvchilar ko'pincha boshqaruv o'zgaruvchilari deb ataladi. Masalan, hozirgi mavjud boyliklarini hisobga olgan holda, odamlar hozir qancha iste'mol qilishni hal qilishlari mumkin. Endi boshqaruv parametrlarini tanlash keyingi holatni tanlashga teng bo'lishi mumkin; Umuman olganda, keyingi holatga joriy nazoratdan tashqari boshqa omillar ham ta'sir qiladi. Masalan, eng oddiy holatda, bugungi boylik (davlat) va iste'mol (boshqarish) ertangi kunning boyligini (yangi davlat) aniq belgilashi mumkin, ammo odatda boshqa omillar ertangi kunning boyligiga ham ta'sir qiladi. Dinamik dasturlash usuli davlatning har qanday mumkin bo'lgan qiymatini hisobga olgan holda boshqarish kerak bo'lgan narsalarni ko'rsatadigan maqbul rejani tavsiflaydi. Masalan, agar iste'mol (c) faqat boylikka bog'liq bo'lsa (W), biz boylikning funktsiyasi sifatida iste'molni beradigan {\ displaystyle c (W)} qoidasini qidiramiz. Boshqarish holatini davlatlar funktsiyasi sifatida belgilaydigan bunday qoida siyosat funktsiyasi deb nomlanadi (Qarang: Bellman, 1957, III.2). Va nihoyat, ta'rifga ko'ra, maqbul bo'lgan eng yaxshi qiymatga erishadigan maqbul qaror. Misol uchun, agar kimdir baxtni maksimal darajada oshirish uchun iste'molni, boylikni tanlasa (faraz qilsangiz, H baxtni foydali funktsiya kabi matematik funktsiya bilan ifodalanishi mumkin va boylik bilan belgilanadigan narsadir), unda har bir boylik darajasi bog'liq bo'ladi. baxtning eng yuqori darajasi, {\ displaystyle H (W)}. Davlatning funktsiyasi sifatida yozilgan maqsadning mumkin bo'lgan eng yaxshi qiymati qiymat funktsiyasi deb ataladi.
Richard Bellman, diskret vaqtdagi dinamik optimallashtirish muammosi bir davrdagi qiymat funktsiyasi va keyingi davrdagi qiymat funktsiyasi o'rtasidagi munosabatni yozib, orqaga induksiya deb nomlanadigan rekursiv, bosqichma-bosqich shaklda ifodalanishi mumkinligini ko'rsatdi. Ushbu ikki qiymat funktsiyalari o'rtasidagi munosabatlar "Bellman tenglamasi" deb nomlanadi. Ushbu yondashuvda oxirgi vaqt oralig'idagi eng maqbul siyosat o'sha vaqtdagi davlat o'zgaruvchisining qiymatining funktsiyasi sifatida oldindan belgilanadi va ob'ektiv funktsiyaning natijaviy maqbul qiymati shu tarzda davlat o'zgaruvchisining qiymati bilan ifodalanadi. Keyingi, keyingi davrni optimallashtirish ushbu davrning davriy ob'ekti funktsiyasining yig'indisini va kelgusidagi ob'ekt funktsiyasining optimal qiymatini ko'paytirishni o'z ichiga oladi, bu davrning maqbul siyosati keyingi davrdagi davlat o'zgaruvchisining qiymatiga qarab belgilanadi. So'nggi davr qarori. [aniqlashtirish kerak] Ushbu mantiq birinchi davrga xos bo'lgan ob'ektiv funktsiyaning yig'indisini optimallashtirish orqali dastlabki holat o'zgaruvchan qiymatining funktsiyasi sifatida qaror qabul qilingan birinchi davrga qadar vaqt o'tishi bilan qaytariladi. va kelgusi barcha davrlar uchun qiymat beradigan ikkinchi davrning qiymat funktsiyasining qiymati. Shunday qilib, har bir davrning qarori kelajakdagi barcha qarorlar maqbul ravishda qabul qilinishini aniq tan olish orqali amalga oshiriladi.
Yechilish usullari:
Agar optimal yaqin yo'llarning p% klassi kerak bo'lsa, u holda e (p/100)f(l) ga teng. Barcha yo'llar f(l)+ e miqdoridan kichik yoki unga teng keyin algoritm yordamida topiladi. Bu muammolar uchun qulaydir mos keladigan K noma'lum va/yoki katta. F(i) tugun belgilarini rekursiv hisoblashda hech qanday "ko'rsatgich" yoki qaror ma'lumotlarini saqlash kerak emas. Ushbu tugun belgilari ishlash orqali topiladi N tugunidan 1 tugun etiketlanmaguncha orqaga. Keyin yangi algoritm 1-tugundan boshlab va davom etuvchi stacking bilan birinchi chuqur qidiruvni amalga oshiradi barcha yaqin optimal yo'llar chiqmaguncha. Belgilangan joyga teng bo'lmagan x tugunini ko'rib chiqing. Ba'zi yo'l P bilan kumulyativ masofa d bizni 1-tugundan x tuguniga olib keldi. Kirish uchun test yoy (x, y) va stekga masofa d endi umumiy shaklni oladi, uchun hammasi (x, y) E A, Bu erda d - P yo'li bo'yicha 1-tugundan x tugungacha bo'lgan umumiy masofa (yo'q albatta eng qisqa yo'l bilan), t (x, y) - x tugundan y tugungacha bo'lgan masofa, f(y) esa y tugunidan N tugungacha optimal qolgan masofa. Algoritm oxir-oqibat 1-tugundan uzunligi d bo'lgan P yo'lni quradi tugun N. Keyin P va d chiqariladi va stek boshqa yoki yo'qligini tekshirish uchun tekshiriladi Optimalga yaqin yo'llar mavjud. Demak, algoritm oxirgi kirish, birinchi chiqish yoki bajarishni amalga oshiradi chuqurlik - birinchi qidiruv. Algoritmni asoslash uchun algoritm P ning yo‘lini yaratdi deylik d uzunligi 1 tugundan x tugungacha. P yo'liga qo'shilgan yoy (x, y) da yoqilgan d + t(x,y)+f(y) ~f(l)+ e bo'lsa, kamida bitta optimalga yaqin yo'l y dan N gacha bo'lgan eng yaxshi yo'l f(y) uzunligiga ega. E'tibor bering, yo'l uzunligidagi bog'lanishlar alohida muammolarga olib kelmaydi. Bu muhim Agar yoy eng maqbul yo'lda yotmasa, u to'planmaganligini ko'rish uchun. Bundan tashqari, test (*) hech qachon har bir tugun uchun bir martadan ortiq bajarilmaydi maxsus yaqin optimal yo'l.
A dan I gacha bo'lgan tugunlar, bu erda A va I tugunlari kelib chiqish va maqsadni ifodalaydi.Har bir tugun ustidagi raqamlar [ f( i)] tugunning eng qisqa uzunligini bildiradi. Faraz qilaylik, foydalanuvchi optimal yo'lning 20% ​​doirasidagi barcha yo'llarni so'raydi uzunligi 13, bu A tugunidagi tugun yorlig'i. Bu foiz a degan ma'noni anglatadi, 15.6 ning yuqori chegarasi P tartiblangan yo'l massivida tugunlar mavjud.
Optimalga yaqin yo'l hozirda aniqlanmoqda va A tugun bilan ishga tushirilgan.
Stack elementi uchta ma'lumotni o'z ichiga oladi:
№1: Joriy tugun.
№2: Keyingi tugun.
№3: boshlang'ich (A tugun) dan №2 tugungacha bo'lgan masofa d.
Algoritm quyidagicha davom etadi:
Qadam 1. A tugunida, d = 0.
t( A, B) + f( B) = 14;
t( A, C) +f( C) = 13;
Yig'ish uchun elementni PUSH.
Yig'ish uchun elementni PUSH.
Stack tarkibiga quyidagilar kiradi:
#1 #2 #3
A B 2
A C 0
2-qadam. Stackning oxirgi elementini POP va №2 da saqlangan “keyingi tugunni” P ga qo'ying
massiv = (A, C). C tugunida d # 3 yoki da saqlangan masofaga teng
d = 0.
d + t( C, E) +f( E) =16;
d+t(C,F)+f(F)=13; PUSHelement.
hech qanday chora ko'rilmagan.
Stack tarkibiga quyidagilar kiradi:
#1 #2 #3
A B 2
C F 3
3-qadam. POP oxirgi elementi. P = (A, C, F). F tugunida d = 3.
d + f( F, H) + f ( H) = 13; PUSH elementi.
Stack tarkibiga quyidagilar kiradi:
#1 #2 #3
A B 2
F H 7
4-qadam. POP oxirgi elementi. P = (A, C, F, H). H tugunida d = 7.
d + f( H, I) +f( I) = 13; PUSH elementi.
Stack tarkibiga quyidagilar kiradi:
#1 #2 #3
A B 2
H I 13
5-qadam. POP oxirgi elementi. P = (A, C, F, H, I). Tugun I erishildi, shuning uchun
d = 13 bilan P yo'li chiqariladi. Stack hozir quyidagilarni o'z ichiga oladi:
#1 #2 #3
A B 2
6-qadam. POP elementi. P = (A, B), d = 2.
d + t( B, D)+f( D) =14; PUSH elementi.
d + t( B, E) +f( E) = 16; hech qanday chora ko'rilmagan.
Stack tarkibiga quyidagilar kiradi:
#1 #2 #3
B D 4
7-qadam. POP elementi. P = (A, B, D), d = 4.
d + t( D, G) + f( G) = 14; PUSH elementi.
Stack tarkibiga quyidagilar kiradi:
#1 #2 #3
D G 9
8-qadam. POP elementi. P = (A, B, D, G), d = 9.
d + t( G, I) + f( I) = 14; PUSH elementi.
Stack tarkibiga quyidagilar kiradi:
#1 #2 #3
G I 14
9-qadam.
shuning uchun d = 14 bo'lgan P yo'l chiqariladi. Stack bo'sh, shuning uchun to'xtating.
POP elementi. P = (A, B, D, G, I). I tugunga erishildi,
Xulosa qilib aytadigan bo'lsak, A tugunidan I tugunga yaqin optimal yo'llar:
A+C+F+H+I, uzunlik13,
A + B + D + G -, I, uzunligi 14.
Bellman tenglamasi orqaga indüksiyon tomonidan hal qilinishi mumkin, yoki bir necha maxsus holatlarda analitik usulda, yoki kompyuterda raqamli ravishda. Orqaga sonli indüksiya turli xil muammolar uchun qo'llaniladi, ammo o'lchov o'lchovi la'nati tufayli juda ko'p davlat o'zgaruvchisi mavjud bo'lganda bu mumkin emas. Bellman funktsiyasini yaqinlashtirish uchun sun'iy neyron tarmoqlari (ko'p qavatli idroklar) yordamida D.P. Bertsekas va J. N. Tsitsiklis tomonidan taxminiy dinamik dasturlash joriy etilgan. Bu butun kosmik domen uchun funktsiyalarning to'liq xaritasini eslab qolishni yagona neyron tarmoq parametrlarini eslab qolish bilan almashtirish orqali o'lchamlilik ta'sirini kamaytirish uchun samarali yumshatish strategiyasidir. Bellman tenglamasi bilan bog'liq birinchi tartib shartlarini hisoblash va keyin qiymat funktsiyasining hosilalarini yo'q qilish uchun konvert teoremasidan foydalanib, "Eyler tenglamalari" deb nomlangan farq tenglamalari yoki differentsial tenglamalar tizimini olish mumkin. Farqli yoki differentsial tenglamalarni yechishning standart usullaridan keyin holat o'zgaruvchilarining dinamikasini va optimallashtirish muammosining boshqarish parametrlarini hisoblash uchun foydalanish mumkin.