Operatsion tadqiqotlarning asosiy tushunchalari. Operatsion tadqiqotlar Aralash strategiyalarda o'yin yechimi
I.N. Slinkin
Pedagogika universitetlari talabalari uchun darslik
Informatika mutaxassisligi
Shadrinsk, 2003 yil
Slinkina I.N.
Operatsion tadqiqotlar. O'quv yordami. - Shadrinsk: Shadrinsk davlat pedagogika instituti nashriyoti, 2002. - 106 p.
Slinkina I.N. – pedagogika fanlari nomzodi
Darslikda “Operatsion tadqiqotlar” kursining nazariy qismi berilgan. “Informatika” ixtisosligini amalga oshiruvchi fakultetlarning kunduzgi va sirtqi bo‘limlari talabalari uchun mo‘ljallangan.
© Shadrinskiy davlat pedagogika instituti
© Slinkina I.N., 2002 yil
"Operatsiyalarni tadqiq qilish" kursida bloklarga savollar 5
1.1. Operatsion tadqiqot predmeti va vazifalari 7
1.2. Operatsion tadqiqotlarning asosiy tushunchalari va tamoyillari 8
1.3. Amaliyotlarning matematik modellari 10
1.4. Chiziqli dasturlashni tushunish 12
1.5. Chiziqli dasturlashning iqtisodiy muammolariga misollar. Resurslardan samarali foydalanish muammosi 13
1.6. Chiziqli dasturlashning iqtisodiy muammolariga misollar. Optimal texnologiyalarni tanlash muammosi 15
1.7. Chiziqli dasturlashning iqtisodiy muammolariga misollar. Aralash muammosi 16
1.8. Chiziqli dasturlashning iqtisodiy muammolariga misollar. Transport vazifasi 17
1.9. Chiziqli dasturlash masalalarini yozishning asosiy turlari 19
1.10. Konvertatsiya qilish usullari 21
1.11. Kanonik shaklga o'tish 22
1.12. Simmetrik belgilarga o'tish 25
2.1. Chiziqli dasturlash masalasining geometrik talqini 28
2.2. Chiziqli dasturlash masalalarini grafik usulda yechish 29
2.3. Chiziqli dasturlash masalasi yechimlarining xossalari 34
2.4. Simpleks usuli haqida umumiy tushuncha 35
2.5. Simpleks usuli yordamida chiziqli dasturlash masalalarini yechish uchun dastlabki mos yozuvlar rejasini qurish 36
2.6. Asosiy rejaning optimalligi belgisi. Simpleks jadvallar 40
2.7. Eng yomon bo'lmagan mos yozuvlar rejasiga o'tish. 44
2.8. Simpleks o'zgarishlar 46
2.9. Alternativ optimal (ma'lumotnoma rejalari to'plamining cheksizligi belgisi) 51
2.10. Maqsad funksiyasining cheksizligi belgisi 52
2.11. Degeneratsiya tushunchasi. Simpleks usulining monotonligi va chekliligi. Loop 53
2.12. Simmetrik chiziqli dasturlash masalalari uchun ikkilik tushunchasi 54
3.1. Asimmetrik ikkilamchi masalalar 57
3.2. Transport muammosining ochiq va yopiq modellari 61
3.3. Dastlabki asosiy rejani qurish. Shimoli-g'arbiy burchak qoidasi 63
3.4. Dastlabki asosiy rejani qurish. Minimal element qoidasi 64
3.5. Dastlabki asosiy rejani qurish. Vogel usuli 64
3.6. Potensial usul 65
3.7. Tarmoqli kengligi cheklovlari bilan transport muammolarini hal qilish 69
3.8. Diskret dasturlash masalalariga misollar. Konteynerlarni tashish muammosi. Topshiriq muammosi 71
3.9. Diskret optimallashtirish usullarining mohiyati 72
3.10. Qavariq dasturlash masalasi 74
3.11. Lagranj ko'paytmalari usuli 75
3.12. Gradient usullari 77
4.1. Jazo usullari va to'siq funktsiyalari 78
4.2. Dinamik dasturlash. Asosiy tushunchalar. Yechish usullarining mohiyati 79
4.3. Stokastik dasturlash. Asosiy tushunchalar 81
4.4. Nol yig'indisi matritsali o'yinlar 83
4.5. Sof va aralash strategiyalar va ularning xossalari 85
4.6. Sof va aralash strategiyalarning xususiyatlari 88
4.7. Matritsali o'yinni ZLP 92 ga qisqartirish
4.8. Navbat nazariyasi vazifalari. Navbat tizimlarining tasnifi 94
4.9. Voqealar oqimi 96
4.10. O'lim va ko'payish sxemasi 97
4.11. Kichik formula 99
4.12. Eng oddiy navbat tizimlari 101
"Operatsion tadqiqotlar" kursi bloklariga savollar
Blok 1
1. Operatsion tadqiqotning predmeti va vazifalari.
2. Operatsion tadqiqotlarning asosiy tushunchalari va tamoyillari.
3. Amallarning matematik modellari.
4. Chiziqli dasturlash tushunchasi.
5. Chiziqli dasturlashning iqtisodiy masalalariga misollar. Vazifa
6. Chiziqli dasturlashning iqtisodiy masalalariga misollar. Optimal texnologiyalarni tanlash muammosi.
7. Chiziqli dasturlashning iqtisodiy masalalariga misollar. Aralash muammosi.
8. Chiziqli dasturlashning iqtisodiy masalalariga misollar. transport vazifasi.
9. Chiziqli dasturlash masalalarini yozishning asosiy turlari.
10. Transformatsiya qilish usullari.
11. Kanonik shaklga o'tish.
12. Simmetrik yozuvga o'tish.
Blok 2
1. Chiziqli dasturlash masalasining geometrik talqini.
2. Chiziqli dasturlash masalalarini grafik usulda yechish.
3. Chiziqli dasturlash masalasi yechimlarining xossalari.
4. Simpleks usuli haqida umumiy tushuncha.
5. Simpleks usulida chiziqli dasturlash masalalarini yechishning dastlabki asosiy rejasini qurish.
6. Asosiy rejaning optimalligi belgisi. Simpleks jadvallar.
7. Eng yomon bo'lmagan mos yozuvlar rejasiga o'tish.
8. Simpleks transformatsiyalar.
9. Alternativ optimal (tayanch rejalar majmuasining cheksizligi belgisi).
10. Maqsad funksiyasining cheksizligi belgisi.
11. Degeneratsiya haqida tushuncha. Simpleks usulining monotonligi va chekliligi. Loop.
12. Simmetrik chiziqli dasturlash masalalari uchun ikkilik tushunchasi.
Blok 3
1. Asimmetrik ikkilamchi masalalar.
2. Transport muammosining ochiq va yopiq modellari.
3. Dastlabki asosiy rejani qurish. Shimoli-g'arbiy burchak qoidasi.
4. Dastlabki asosiy rejani qurish. Minimal element qoidasi.
5. Dastlabki asosiy rejani qurish. Vogel usuli.
6. Potentsiallar usuli.
7. Cheklangan tarmoqli kengligi bilan transport muammolarini hal qilish.
8. Diskret dasturlash masalalariga misollar. Konteynerlarni tashish muammosi. Topshiriq vazifasi.
9. Diskret optimallashtirish usullarining mohiyati.
10. Qavariq dasturlash masalasi.
11. Lagranj ko'paytiruvchilari usuli.
12. Gradient usullari.
Blok 4
1. Jarima va to'siq funktsiyalari usuli.
2. Dinamik dasturlash. Asosiy tushunchalar. Yechish usullarining mohiyati.
3. Stokastik dasturlash. Asosiy tushunchalar.
4. Nol summali matritsali o'yinlar.
5. Sof va aralash strategiyalar.
6. Sof va aralash strategiyalarning xossalari.
7. Matritsa o'yinini LLP ga qisqartirish
8. Navbat nazariyasi muammolari. Navbat tizimlarining tasnifi.
9. Voqealarning oqimlari.
10. O'lim va ko'payish sxemasi.
11. Kichik formula.
12. Eng oddiy navbat tizimlari.
Blok 1.
Operatsion tadqiqotning predmeti va vazifalari
Fan va texnikaning hozirgi holati, xususan, nazariyalarni hisoblash va matematik asoslash uchun kompyuter vositalarining rivojlanishi fanning turli sohalari oldiga qo'yilgan ko'plab muammolarni hal qilishni sezilarli darajada soddalashtirish imkonini berdi. Ko'pgina muammolar ishlab chiqarishni optimallashtirish, jarayonni optimal boshqarish masalasini hal qilishga to'g'ri keladi.
Amaliyot ehtiyojlari maxsus ilmiy usullarni hayotga tatbiq etdi, ular qulay tarzda "operatsion tadqiqotlar" nomi ostida guruhlangan.
Ta'rif: Operatsion tadqiqotlar deganda biz maqsadli inson faoliyatining barcha sohalarida qarorlarni asoslash uchun matematik, miqdoriy usullarni qo'llashni tushunamiz.
Muayyan maqsadga erishish uchun qandaydir harakatlar amalga oshirilsin. Tadbirni tashkil etuvchi shaxs (yoki shaxslar guruhi) har doim tanlash erkinligiga ega: u yoki bu tarzda tashkil etilishi mumkin. Qaror tashkilotchi uchun mavjud bo'lgan bir qator variantlardan ba'zi bir tanlovdir.
Qaror qabul qilish va taklif qilingan qaror gipotezasini sinab ko'rish zarurati quyidagi misollar bilan matematik jihatdan tasdiqlangan:
Vazifa 1. Resurslardan eng yaxshi foydalanish haqida.
Korxona bir necha turdagi mahsulotlar ishlab chiqaradi. Ularni ishlab chiqarish uchun ba'zi resurslar (shu jumladan inson, energiya va boshqalar) ishlatiladi. Resurslar qiymati minimal bo'lishi va foyda maksimal bo'lishi uchun korxona ishini qanday rejalashtirish kerakligini hisoblash kerak.
Vazifa 2. Aralashmalar haqida.
Muayyan xususiyatlarga ega aralashmani tayyorlash kerak. Buning uchun siz ba'zi "mahsulotlar" dan foydalanishingiz mumkin (dietlarni hisoblash uchun - oziq-ovqat, ozuqa aralashmalari uchun - hayvonlar uchun oziq-ovqat, texnik aralashmalar uchun - qotishmalar, texnik maqsadlar uchun suyuqliklar). vazifa aralashmaning optimal miqdorini olish uchun mahsulotlarning maqbul miqdorini (narx uchun) tanlashdir.
Vazifa 3. transport vazifasi.
Bir xil turdagi bir xil sifatdagi mahsulotlarni ishlab chiqaruvchi korxonalar tarmog'i va bu mahsulotlarni iste'molchilar tarmog'i mavjud. Iste'molchilar va etkazib beruvchilar aloqa vositalari (avtomobil, temir yo'l, havo yo'llari) orqali bog'langan. Transport tariflari belgilanadi. Tashish xarajatlari minimal bo'lishi, barcha iste'molchilarning talablari qondirilishi va barcha tovarlar etkazib beruvchilardan eksport qilinishi uchun mahsulotlarni tashishning optimal rejasini hisoblash kerak.
Yuqoridagi misollarning har birida biz aniq maqsadni ko'zlagan qandaydir hodisa haqida gapiramiz. Vaziyatni tavsiflovchi ba'zi shartlar (xususan, yo'q qilinishi mumkin bo'lgan vositalar) berilgan. Ushbu shartlar doirasida rejalashtirilgan tadbir qaysidir ma'noda foydaliroq bo'lishi uchun shunday qaror qabul qilish talab etiladi.
Ushbu umumiy xususiyatlarga muvofiq, bunday muammolarni hal qilishning umumiy usullari ham ishlab chiqilgan bo'lib, ular birgalikda operatsiyalarni tadqiq qilishning uslubiy sxemasi va apparatini tashkil qiladi.
Hozirgi vaqtda kompyuter texnologiyalaridan foydalanishga asoslangan avtomatlashtirilgan boshqaruv tizimlari (AKS) keng qo'llanilmoqda. Matematik modellashtirish usullari bilan boshqariladigan jarayonni dastlabki tekshirishsiz avtomatlashtirilgan boshqaruv tizimini yaratish mumkin emas. Voqealarning ko'lami va murakkabligining o'sishi bilan qarorlarni asoslashning matematik usullari tobora muhim ahamiyat kasb etmoqda.
Operatsion tadqiqotlarning asosiy tushunchalari va tamoyillari
Ta'rif: Operatsiya - bu bitta reja bilan birlashtirilgan va biron bir maqsadga erishishga qaratilgan har qanday hodisa (harakatlar tizimi).
Operatsiya har doim boshqariladigan hodisadir, ya'ni. uning tashkil etilishini tavsiflovchi parametrlarni qanday tanlash kerakligi hisob-kitoblarga bog'liq. Bu erda "tashkilot" so'zning keng ma'nosida, shu jumladan operatsiyada qo'llaniladigan texnik vositalar majmui tushuniladi.
Ta'rif: Qaror parametrlariga qarab har qanday aniq tanlov qaror deyiladi.
Ta'rif: Optimal echimlar - bu yoki boshqa sabablarga ko'ra boshqalardan ustun bo'lganlar.
Operatsion tadqiqotlar maqsadi– optimal yechimlarni dastlabki miqdoriy asoslash.
Ba'zan, o'rganish natijasida yagona, qat'iy belgilangan yechimni ko'rsatish mumkin; ko'pincha, yakuniy tanlovni amalga oshirish mumkin bo'lgan amaliy ekvivalent optimal echimlar sohasini aniqlash mumkin.
Qaror qabul qilishning o'zi operatsion tadqiqotlar doirasidan tashqariga chiqadi va mas'ul shaxsning, ko'pincha yakuniy tanlov qilish huquqiga ega bo'lgan va bu tanlov uchun mas'ul bo'lgan odamlar guruhining vakolatiga kiradi.
Ta'rif: Jami yechimni tashkil etuvchi parametrlarga eritma elementlari deyiladi.
Yechim elementlari sifatida turli sonlar, vektorlar, funktsiyalar, fizik belgilar va boshqalar paydo bo'lishi mumkin. Oddiylik uchun yechimning barcha elementlari to'plami x bilan belgilanadi.
Operatsiyalarni tadqiq qilishning har qanday vazifasida yechim elementlaridan tashqari, muammoning holatida o'rnatiladigan va buzilmasligi mumkin bo'lgan shartlar ham mavjud. Xususan, bunday shartlarga utilizatsiya qilinishi mumkin bo'lgan vositalar (moddiy, texnik, insoniy) va yechimga qo'yilgan boshqa cheklovlar kiradi. Ularning umumiyligida ular "mumkin bo'lgan echimlar to'plami" ni tashkil qiladi. Bu X to'plamni belgilaymiz va x yechim bu to'plamga tegishli ekanligini yozamiz: xOX.
Turli xil echimlarni samaradorlik nuqtai nazaridan solishtirish uchun siz ishlash ko'rsatkichi (maqsadli funktsiya) deb ataladigan qandaydir miqdoriy mezonga ega bo'lishingiz kerak. Ushbu ko'rsatkich operatsiyaning maqsadli yo'nalishini aks ettiradigan tarzda tanlanadi. Maqsadga maksimal darajada erishishga hissa qo'shadigan eng yaxshi yechim hisoblanadi. Z samaradorlik ko'rsatkichini tanlash uchun siz birinchi navbatda muammoni hal qilish nimaga olib kelishi kerakligini aniqlashingiz kerak. Yechimni tanlashda Z samaradorlik ko'rsatkichini maksimal yoki minimal darajaga aylantiradigan afzallik beriladi. Masalan, men operatsiyadan keladigan daromadni maksimal darajada oshirishni xohlayman; agar xarajatlar samaradorlik ko'rsatkichi bo'lsa, ularni minimallashtirish maqsadga muvofiqdir.
Ko'pincha operatsiya tasodifiy omillarning ta'siri bilan birga keladi: tabiatning "injiqliklari", talab va taklifning o'zgarishi, texnik qurilmalarning ishdan chiqishi va boshqalar. Bunday hollarda, odatda, samaradorlik ko'rsatkichi sifatida biz maksimal darajaga ko'tarmoqchi bo'lgan qiymatning o'zi emas, balki o'rtacha qiymat (matematik kutish) olinadi.
Ishlash ko'rsatkichini tanlash vazifasi har bir muammo uchun alohida hal qilinadi.
Vazifa 1. Resurslardan eng yaxshi foydalanish haqida.
Operatsiyaning vazifasi maksimal miqdorda mahsulot ishlab chiqarishdir. Samaradorlik ko'rsatkichi Z - resurslarning minimal qiymatida (max Z) tovarlarni sotishdan olingan foyda.
Vazifa 2. Aralashmalar haqida.
Muammoni shakllantirish bilan taklif qilingan samaradorlikning tabiiy ko'rsatkichi aralashmaning belgilangan xususiyatlarini (min Z) saqlanishi sharti bilan aralashma uchun zarur bo'lgan mahsulotlarning narxidir.
Vazifa 3. transport vazifasi.
Operatsiyaning vazifasi iste'molchilarga minimal transport xarajatlari bilan tovarlarni etkazib berishni ta'minlashdir. Samaradorlik ko'rsatkichi Z - vaqt birligi uchun tovarlarni tashish uchun umumiy xarajatlar (min Z).
1. Iqtisodiyotdagi operatsiyalarni o'rganishning predmeti va vazifalari. Operatsion tadqiqotlar nazariyasining asosiy tushunchalari.
Operatsion tadqiqotning predmeti har doim ham bir-biriga mos kelmaydigan va qarama-qarshi bo'lishi mumkin bo'lgan ko'p sonli o'zaro ta'sir qiluvchi birliklardan tashkil topgan tashkiliy boshqaruv tizimlari yoki tashkilotlardir.
Operatsion tadqiqotlarning maqsadi tashkilotlarni boshqarish bo'yicha qabul qilingan qarorlarni miqdoriy jihatdan asoslashdir
Butun tashkilot uchun eng foydali bo'lgan yechim optimal deb ataladi va bir yoki bir nechta bo'limlar uchun eng foydali bo'lgan yechim suboptimal bo'ladi.
Operatsion tadqiqotlar - bu tashkiliy tizimlarni eng maqbul boshqarish usullarini ishlab chiqish va amaliy qo'llash bilan shug'ullanadigan fan.
Operatsiya - bu bitta reja bilan birlashtirilgan va biron bir maqsadga erishishga qaratilgan har qanday hodisa (harakatlar tizimi).
Operatsion tadqiqotlarning maqsadi - optimal echimlarni dastlabki miqdoriy asoslash.
Bizga bog'liq bo'lgan har qanday aniq parametrlar qaror deb ataladi. Yechimlar u yoki bu sabablarga ko'ra boshqalardan ustun qo'yilgan taqdirda optimal deb ataladi.
Jami yechimni tashkil etuvchi parametrlarga eritma elementlari deyiladi.
Ruxsat etilgan echimlar to'plamiga qat'iy belgilangan va buzilmasligi mumkin bo'lgan shartlar berilgan.
Ishlash ko'rsatkichi - turli xil echimlarni samaradorlik nuqtai nazaridan solishtirish imkonini beruvchi miqdoriy o'lchov.
2. Tarmoqni rejalashtirish va boshqarish tushunchasi. Jarayonning tarmoq modeli va uning elementlari.
Tarmoq grafiklari bilan ishlash usuli - tarmoqni rejalashtirish - grafiklar nazariyasiga asoslanadi. Yunon tilidan tarjima qilingan grafik (graffo - yozaman) nuqtalar tizimini ifodalaydi, ularning ba'zilari chiziqlar - yoylar (yoki qirralar) bilan bog'langan. Bu o'zaro ta'sir qiluvchi tizimlarning topologik (matematik) modeli. Grafiklar yordamida nafaqat tarmoqni rejalashtirish masalalarini, balki boshqa masalalarni ham hal qilish mumkin. Tarmoqni rejalashtirish usuli bir-biriga bog'langan ishlar majmuasini rejalashtirishda qo'llaniladi. Bu ishning tashkiliy va texnologik ketma-ketligini tasavvur qilish va ular o'rtasidagi munosabatlarni o'rnatish imkonini beradi. Bundan tashqari, u turli darajadagi murakkablikdagi operatsiyalarni muvofiqlashtirish va butun ishning davomiyligi (ya'ni tashkiliy tadbir) bog'liq bo'lgan operatsiyalarni aniqlashga, shuningdek, har bir operatsiyani o'z vaqtida bajarishga e'tibor berishga imkon beradi.
Tarmoqni rejalashtirish va boshqarishning asosini aniq maqsadga erishish jarayonini aks ettiruvchi o‘zaro bog‘liq faoliyat va hodisalar majmuasini modellashtiruvchi tarmoq modeli (SM) tashkil etadi. U grafik yoki jadval shaklida taqdim etilishi mumkin.
Tarmoq modelining asosiy tushunchalari:
Voqea, ish, yo'l.
Voqealar bir yoki bir nechta faoliyatning bajarilishi natijalaridir. Ularning muddati uzaytirilmaydi.
Yo'l - bu boshlang'ich va oxirgi cho'qqilarni bog'laydigan birin-ketin davom etadigan ish zanjiri.
Yo'lning davomiyligi uni tashkil etuvchi ishlarning davomiyligi yig'indisi bilan belgilanadi.
3. Tarmoq sxemasini qurish va tartibga solish.
Tarmoqni rejalashtirish va boshqarish tizimlarida (SPU) qurilish-montaj ishlari jarayonining texnologik va tashkiliy aloqalarini aks ettiruvchi model sifatida tarmoq modeli qo'llaniladi.
Tarmoq modeli - bu jarayonlarning grafik tasviri bo'lib, ularni amalga oshirish bir yoki bir nechta maqsadlarga erishishga olib keladi, bu jarayonlar o'rtasidagi o'rnatilgan munosabatlarni ko'rsatadi. Tarmoq diagrammasi hisoblangan vaqt parametrlariga ega tarmoq modelidir.
Ish va hodisalarning o'zaro bog'liqligini belgilovchi tarmoq diagrammasining tuzilishi uning topologiyasi deb ataladi.
Ish - bu vaqt, mehnat va moddiy resurslarni talab qiladigan ishlab chiqarish jarayoni bo'lib, u bajarilganda ma'lum natijalarga erishishga olib keladi.
Vaqtni talab qilmaydigan qaramlik (fikrli ish) nuqtali o'q bilan tasvirlangan. Hodisalar va harakatlar o'rtasidagi munosabatlarni ko'rsatish uchun tarmoq diagrammasida qo'g'irchoq ish qo'llaniladi.
Tarmoq jadvalida ishning vaqti, narxi va boshqa xususiyatlari qo'llaniladi.
Ishning davomiyligi - tarmoqdagi barcha ishlar uchun bir xil bo'lgan ish kunlari yoki boshqa vaqt birliklarida ushbu ishni bajarish vaqti. Ishning davomiyligi ma'lum (deterministik) yoki uni taqsimlash qonuni bilan belgilangan tasodifiy o'zgaruvchi bo'lishi mumkin.
Ishning qiymati - bu ishning davomiyligi va shartlariga qarab, uni amalga oshirish uchun zarur bo'lgan bevosita xarajatlar.
Resurslar ushbu ishni bajarish uchun zarur bo'lgan jismoniy birliklarga bo'lgan ehtiyoj bilan tavsiflanadi.
Ishning sifati, ishonchliligi va boshqa ko'rsatkichlari ishning qo'shimcha xususiyatlari sifatida xizmat qiladi.
Voqea - bu bir yoki bir nechta keyingi ishlarni boshlash uchun zarur va etarli bo'lgan bir yoki bir nechta ishni bajarish faktidir. Har bir hodisaga kod deb ataladigan raqam beriladi. Har bir ish ikkita hodisa bilan belgilanadi: i bilan belgilangan boshlanish hodisasi kodi va j bilan belgilangan tugatish hodisasi kodi.
Oldingi faoliyatga ega bo'lmagan hodisalar boshlang'ich hodisalar deb ataladi; keyingi bo'lmagan voqealar - yakuniy.
1 Tarmoqni qurish yo'nalishi boshqa xarakterga ega bo'lishi mumkin. Tarmoq grafigi boshlang'ich hodisadan yakuniygacha va yakuniy voqeadan boshlang'ich (boshlang'ich)gacha, shuningdek, har qanday hodisadan dastlabki yoki yakuniygacha tuzilishi mumkin.
2 Tarmoqni qurishda quyidagi savollar hal qilinadi:
Ushbu ishni boshlash uchun qanday ish (ish) qilish kerak;
Bu ish bilan parallel ravishda qanday ishlarni bajarish kerak;
3 Dastlabki tarmoq jadvali tarmoqni tashkil etuvchi faoliyatning davomiyligini hisobga olmasdan tuziladi.
4 Grafikning shakli sodda va vizual tarzda idrok etilishi oson bo'lishi kerak.
5 Ikki voqea o'rtasida faqat bitta ish bo'lishi mumkin. Bino va inshootlarni qurishda ishlar ketma-ket, parallel yoki bir vaqtda, ba'zilari ketma-ket va ba'zilari parallel ravishda bajarilishi mumkin, buning natijasida alohida ishlar o'rtasida turli bog'liqliklar hosil bo'ladi.
Hodisalarni raqamlash (kodlash) tarmoq qurilishi tugagandan so'ng, boshlang'ich hodisadan boshlab yakuniy voqeaga qadar amalga oshiriladi.
4. Tarmoq diagrammasining kritik yo'li. Vaqt zaxiralari. Tarmoq diagrammasidagi voqealar va tadbirlarning erta va kech sanalari.
Tarmoq diagrammasida boshlang'ich va tugatish hodisalari o'rtasida bir nechta yo'llar bo'lishi mumkin. Eng uzun davomiy yo'l kritik yo'l deb ataladi. Kritik yo'l faoliyatning umumiy davomiyligini belgilaydi. Boshqa barcha yo'llar qisqaroq davomiylikka ega va shuning uchun ularda bajarilgan ish vaqt zaxirasiga ega.
Kritik yo'l tarmoq diagrammasida qalinlashgan yoki qo'sh chiziqlar (strelkalar) bilan ko'rsatilgan.
Tarmoq diagrammasini tuzishda ikkita tushuncha alohida ahamiyatga ega:
Ishning erta boshlanishi - qabul qilingan texnologik ketma-ketlikni buzmasdan ushbu ishni boshlash mumkin bo'lmagan davr. Bu boshlang'ich hodisadan bu ishning boshlanishigacha bo'lgan eng uzun yo'l bilan belgilanadi.
Kechiktirilgan tugatish - bu ishning umumiy davomiyligini oshirmaydigan ishning oxirgi tugash sanasi. U berilgan hodisadan barcha ishlarni yakunlashgacha bo'lgan eng qisqa yo'l bilan belgilanadi.
Erta tugatish - bu ishni tugatib bo'lmaydigan muddat. Bu erta boshlash va ushbu ishning davomiyligiga teng.
Kechiktirilgan boshlanish - qurilishning umumiy davomiyligini oshirmasdan, bu ishni boshlash mumkin bo'lmagan davr. Bu berilgan ishning davomiyligini olib tashlagan holda kech tugatishga teng.
Agar voqea faqat bitta ishning oxiri bo'lsa (ya'ni, faqat bitta o'q unga yo'naltirilgan bo'lsa), unda bu ishning erta tugashi keyingi ishning erta boshlanishiga to'g'ri keladi.
Umumiy (to'liq) zaxira - bu ishning umumiy davomiyligini oshirmasdan, ushbu ishni bajarish kechiktirilishi mumkin bo'lgan maksimal vaqt. Bu kech va erta boshlash (yoki kech va erta tugatish - bu bir xil) o'rtasidagi farq bilan belgilanadi.
Xususiy (bepul) zaxira - bu keyingi ishning erta boshlanishini o'zgartirmasdan, ushbu ishni bajarishni kechiktirishingiz mumkin bo'lgan maksimal vaqt. Ushbu qayta tiklash faqat hodisa ikki yoki undan ortiq faoliyatni (qaramlikni) o'z ichiga olgan taqdirdagina mumkin bo'ladi, ya'ni. ikki yoki undan ortiq strelkalar (qattiq yoki nuqta) unga ishora qiladi. Shunda bu ishlardan faqat bittasi keyingi ishning erta boshlanishiga to'g'ri keladigan erta tugashga ega bo'ladi, qolganlari uchun esa bu boshqa qiymatlarga ega bo'ladi. Har bir ish uchun bu farq uning shaxsiy zaxirasi bo'ladi.
5. Dinamik dasturlash. Bellmanning optimallik va boshqarish printsipi.
Dinamik dasturlash optimallashtirishning eng kuchli usullaridan biridir. Ratsional qarorlar qabul qilish, eng yaxshi variantlarni tanlash, optimal nazorat qilish vazifalari turli profil mutaxassislari tomonidan hal qilinadi. Optimallashtirish usullari orasida dinamik dasturlash alohida o'rin tutadi. Ushbu usul o'zining asosiy printsipi - optimallik tamoyilining soddaligi va ravshanligi tufayli juda jozibali. Optimallik printsipini qo'llash doirasi juda keng, uni qo'llash mumkin bo'lgan muammolar doirasi hali to'liq belgilanmagan. Dinamik dasturlash boshidanoq optimallashtirish masalalarini amaliy hal qilish vositasi sifatida ishlaydi.
Dinamik dasturlash apparatida tadqiqotning asosiy usuli bo'lgan optimallik printsipiga qo'shimcha ravishda ma'lum bir optimallashtirish muammosini o'xshash muammolar oilasiga kiritish g'oyasi muhim rol o'ynaydi. Uni boshqa optimallashtirish usullaridan ajratib turuvchi uchinchi xususiyati yakuniy natija shaklidir. Optimallik printsipini va ko'p bosqichli, diskret jarayonlarga botish printsipini qo'llash sifat mezonining optimal qiymatiga nisbatan takroriy funktsional tenglamalarga olib keladi. Olingan tenglamalar dastlabki masala uchun optimal boshqaruv elementlarini ketma-ket yozish imkonini beradi. Bu erda afzallik shundaki, butun jarayon uchun boshqaruvni hisoblash vazifasi jarayonning alohida bosqichlari uchun nazoratni hisoblashning bir qancha sodda vazifalariga bo'linadi.
Usulning asosiy kamchiligi, Bellmanning so'zlariga ko'ra, "o'lchovlilik la'nati" - uning murakkabligi muammoning o'lchovliligi oshishi bilan halokatli darajada oshadi.
6. Mablag'larni korxonalar o'rtasida taqsimlash muammosi.
Aytish mumkinki, optimal boshqaruvni dinamik dasturlash usuli bilan qurish tartibi ikki bosqichga bo'linadi: dastlabki va yakuniy. Dastlabki bosqichda har bir qadam uchun SOC tizimning holatiga qarab aniqlanadi (oldingi qadamlar natijasida erishilgan) va bundan boshlab qolgan barcha bosqichlarda shartli optimal daromad ham bog'liq. davlat. Yakuniy bosqichda har bir bosqich uchun (shartsiz) optimal nazorat aniqlanadi. Dastlabki (shartli) optimallashtirish teskari tartibda bosqichma-bosqich amalga oshiriladi: oxirgi bosqichdan birinchisiga; yakuniy (shartsiz) optimallashtirish - ham bosqichlar bo'yicha, lekin tabiiy tartibda: birinchi qadamdan oxirgi bosqichgacha. Optimallashtirishning ikki bosqichidan birinchisi beqiyos muhimroq va vaqt talab etadi. Birinchi bosqich tugagandan so'ng, ikkinchi bosqichni amalga oshirish hech qanday qiyinchilik tug'dirmaydi: faqat birinchi bosqichda tayyorlangan tavsiyalarni "o'qish" qoladi.
7. Chiziqli dasturlash masalasining bayoni.
Chiziqli dasturlash - bu bitta mezon mavjudligi bilan tavsiflangan iqtisodiy muammolarni hal qilishning mashhur vositasi (masalan, ishlab chiqarish dasturini optimal tanlash orqali ishlab chiqarishdan olinadigan daromadni oshirish yoki, masalan, transport xarajatlarini minimallashtirish va boshqalar). . Iqtisodiy vazifalar resurslarning cheklanganligi (moddiy va/yoki moliyaviy) bilan tavsiflanadi. Ular tengsizliklar tizimi sifatida, ba'zan esa tenglik sifatida yoziladi.
Umumlashtirilgan parametrik bo'lmagan usul doirasida maqbul narxlar oralig'ini (yoki sotish hajmini) prognoz qilish nuqtai nazaridan chiziqli dasturlash vositalaridan foydalanish:
Mezon f qiziqish guruhidan keyingi mahsulotning MAX narxidir.
Boshqariladigan o'zgaruvchilar - bu f guruhidagi barcha mahsulotlarning narxi.
Umumlashtirilgan parametrik bo'lmagan usul yordamida prognozlash muammomizdagi cheklovlar:
a) tengsizliklar tizimi (iste'molchi xatti-harakatlarining mantiqiyligini cheklash) (4.2-bandga qarang. Umumlashtirilgan parametrik bo'lmagan usul doirasida prognozlash);
b) boshqariladigan o'zgaruvchilarning manfiy emasligi talabi (bizning prognozlash muammomizda f guruhidagi mahsulotlar narxi oxirgi vaqt nuqtasida narxlarning 80% dan past bo'lmasligini talab qilamiz);
v) tenglik ko'rinishidagi byudjet cheklovi - f guruhidan mahsulotlarni sotib olish uchun xarajatlar miqdori doimiy bo'lishi talabi (masalan, 15% inflyatsiyani hisobga olgan holda).
8. Chiziqli dasturlash masalalarini echishning grafik usuli.
Grafik usul chiziqli dasturlash masalasining geometrik talqiniga asoslanadi va asosan ikki o'lchovli fazoga oid masalalarni va faqat uch o'lchovli fazoga oid ba'zi masalalarni hal qilishda qo'llaniladi, chunki u sifatida shakllanadigan politopning yechimini qurish juda qiyin. yarim bo'shliqlarning kesishishi natijasi. Uchdan kattaroq o'lchamdagi fazoning vazifasini grafik jihatdan umuman tasvirlab bo'lmaydi.
Chiziqli dasturlash masalasi ikki o'lchovli fazoda berilsin, ya'ni cheklovlar ikkita o'zgaruvchini o'z ichiga oladi.
Funksiyaning minimal qiymatini toping
(2.1) Z = S1x1+S2x2
a11x1 + a22x2 b1
(2.2)a21x1 + a22x2 b2
aM1x1 + aM2x2 bM
(2.3) x1 0, x2 0
Faraz qilaylik, (2.3) shartdagi (2.2) sistema izchil va uning yechim ko‘pburchagi chegaralangan. (2.2) va (2.3) tengsizliklarning har biri, yuqorida qayd etilganidek, chegara chiziqlari bilan yarim tekislikni belgilaydi: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), x1=0 , x2=0 . Z ning belgilangan qiymatlari uchun chiziqli funktsiya (2.1) to'g'ri chiziq tenglamasi: C1x1 + C2x2 = const. Cheklash sistemasi (2.2) yechimlari poligonini va Z = 0 uchun chiziqli funktsiyaning (2.1) grafigini tuzamiz (2.1-rasm). U holda berilgan chiziqli dasturlash masalasiga quyidagi talqinni berish mumkin. C1x1 + C2x2 = const to'g'ri chiziq tayanch chizig'i bo'lgan va Z funksiyasi minimumga yetadigan yechim ko'pburchak nuqtasini toping.
Z = C1x1 + C2x2 qiymatlari N = (C1, C2) vektor yo'nalishi bo'yicha ortadi, shuning uchun Z = 0 chizig'ini X vektor yo'nalishi bo'yicha o'ziga parallel ravishda siljitamiz. 2.1 shundan kelib chiqadiki, chiziq ikki marta yechimlar ko‘pburchagiga (A va C nuqtalarda) nisbatan mos yozuvlarga aylanadi va minimal qiymat A nuqtada bo‘ladi. A nuqtaning koordinatalari (x1, x2) ni yechish orqali topiladi. AB va AE chiziqlar tenglamalar tizimi.
Agar qaror ko'pburchak chegaralanmagan ko'pburchak maydoni bo'lsa, u holda ikkita holat mumkin.
1-holat. N vektor yo'nalishi bo'yicha yoki unga qarama-qarshi harakatlanuvchi C1x1 + C2x2 = const to'g'ri chiziq yechim ko'pburchagini doimo kesib o'tadi va hech qanday nuqtada unga havola emas. Bunda chiziqli funksiya yechim ko‘pburchagida ham yuqorida, ham pastda chegaralanmagan bo‘ladi (2.2-rasm).
2-holat. Harakatlanuvchi to'g'ri chiziq shunga qaramay, yechimlar ko'pburchagiga nisbatan tayanchga aylanadi (2.2-rasm, a - 2.2, v). Keyin, maydon turiga qarab, chiziqli funktsiya yuqoridan chegaralangan va pastdan chegaralanmagan (2.2-rasm, a), pastdan chegaralangan va yuqoridan chegaralanmagan (2.2-rasm, b) yoki pastdan va ikkala tomondan chegaralangan bo'lishi mumkin. yuqoridan (2.2-rasm, v).
9. Simpleks usuli.
Simpleks usuli chiziqli dasturlashda asosiy hisoblanadi. Masalani yechish ko`pburchak shartlar cho`qqilaridan birini ko`rib chiqishdan boshlanadi. Agar o'rganilayotgan cho'qqi maksimal (minimal) ga to'g'ri kelmasa, ular qo'shnisiga o'tadilar, masalani hal qilishda maqsad funktsiyasining qiymatini maksimal darajaga oshiradi va masalani echishda esa kamayadi. Shunday qilib, bir cho'qqidan ikkinchisiga o'tish maqsad funktsiyasining qiymatini yaxshilaydi. Ko'pburchakning uchlari soni cheklanganligi sababli, cheklangan miqdordagi qadamlarda optimal qiymatni topish yoki muammoni hal qilib bo'lmaydigan faktni aniqlash kafolatlanadi.
Bu usul universal bo'lib, kanonik shakldagi har qanday chiziqli dasturlash masalasiga qo'llaniladi. Bu yerda cheklovlar tizimi chiziqli tenglamalar tizimi bo'lib, unda noma'lumlar soni tenglamalar sonidan kattaroqdir. Agar tizimning darajasi r bo'lsa, biz r noma'lumlarni tanlashimiz mumkin, biz qolgan noma'lumlar bilan ifodalaymiz. Aniqlik uchun birinchi navbatdagi X1, X2, ..., Xr noma'lumlar tanlangan deb faraz qilamiz. Shunda bizning tenglamalar sistemamiz quyidagicha yozilishi mumkin
Simpleks usuli simpleks usulining asosiy teoremasi deb ataladigan teoremaga asoslanadi. Chiziqli dasturlash muammosining kanonik ko'rinishdagi optimal rejalari orasida uning cheklovlar tizimiga mos yozuvlar yechimi bo'lishi shart. Agar muammoning optimal rejasi noyob bo'lsa, u qandaydir mos yozuvlar yechimiga to'g'ri keladi. Cheklov tizimi uchun juda ko'p turli xil qo'llab-quvvatlash echimlari mavjud. Demak, masalaning kanonik ko’rinishdagi yechimini mos yozuvlar yechimlarini sanab, ular orasidan F qiymati eng katta bo’lganini tanlash orqali izlash mumkin. Lekin, birinchidan, barcha mos yozuvlar echimlari noma'lum va ularni topish kerak, ikkinchidan, haqiqiy muammolarda bunday echimlar juda ko'p va to'g'ridan-to'g'ri sanab o'tish deyarli mumkin emas. Simpleks usuli - bu mos yozuvlar echimlarini yo'naltirilgan sanab o'tishning ma'lum bir protsedurasi. Simpleks usulining ma'lum algoritmidan foydalangan holda ilgari topilgan ba'zi bir mos yozuvlar yechimiga asoslanib, biz F maqsad funktsiyasining qiymati eskisidan kam bo'lmagan yangi mos yozuvlar yechimini hisoblaymiz. Bir qator qadamlardan so'ng, biz maqbul reja bo'lgan mos yozuvlar yechimiga kelamiz.
10. Transport muammosining bayoni. Asosiy rejalarni aniqlash usullari.
Ayrim bir xil mahsulotning m ta jo‘nash nuqtasi ("etkazib beruvchilar") va n ta iste'mol nuqtasi ("iste'molchilar") mavjud. Har bir element uchun quyidagilar belgilanadi:
ai - i-chi yetkazib beruvchining ishlab chiqarish hajmlari, i = 1, …, m;
vj - j-chi iste'molchining talabi, j= 1,…,n;
cij - bir mahsulot birligini Ai nuqtadan - i-etkazib beruvchidan, Bj nuqtadan - j-iste'molchiga o'tkazish xarajatlari.
Aniqlik uchun ma'lumotlarni jadval ko'rinishida taqdim etish qulay bo'lib, u transport xarajatlari jadvali deb ataladi.
Barcha iste'molchilarning talabini to'liq qondiradigan transport rejasini topish talab etiladi, shu bilan birga etkazib beruvchilar etarli miqdorda bo'ladi va umumiy transport xarajatlari minimal bo'ladi.
Tashish rejasi ostida transport hajmi tushuniladi, ya'ni. i-etkazib beruvchidan j-iste'molchiga olib o'tiladigan tovarlar miqdori. Masalaning matematik modelini qurish uchun xij, i= 1,…, n, j= 1, …, m m n o‘zgaruvchini kiritish kerak, har bir xij o‘zgaruvchisi Ai nuqtadan Bj nuqtagacha bo‘lgan harakat hajmini bildiradi. X = (xij) o'zgaruvchilar to'plami muammo bayoni asosida topilishi kerak bo'lgan reja bo'ladi.
Bu yopiq va ochiq transport vazifalarini (ZTZ) hal qilish uchun shartdir.
Shubhasiz, 1-muammoni hal qilish uchun umumiy talab etkazib beruvchilar tomonidan ishlab chiqarilgan mahsulot hajmidan oshmasligi kerak:
Agar bu tengsizlik qat'iy bajarilsa, u holda masala "ochiq" yoki "muvozanatsiz" deb ataladi, lekin agar bo'lsa, u holda masala "yopiq" transport muammosi deb ataladi va (2) ko'rinishga ega bo'ladi:
Balans holati.
Bu yopiq transport vazifalarini (ZTZ) hal qilish uchun shartdir.
11. Transport masalasini yechish algoritmi.
Algoritmni qo'llash bir qator shartlarga rioya qilishni talab qiladi:
1. Mahsulot birligini har bir ishlab chiqarish punktidan har bir manzilga olib o’tish xarajatlari ma’lum bo’lishi kerak.
2. Har bir ishlab chiqarish punktida mahsulot zaxirasi ma'lum bo'lishi kerak.
3. Har bir iste'mol nuqtasida oziq-ovqat talablari ma'lum bo'lishi kerak.
4. Umumiy taklif umumiy talabga teng bo'lishi kerak.
Transport muammosini hal qilish algoritmi to'rt bosqichdan iborat:
I bosqich. Ma'lumotlarni standart jadval ko'rinishida taqdim etish va resurslarning har qanday maqbul taqsimotini qidirish. Resurslarning maqbul taqsimlanishi shunday bo'ladiki, u belgilangan manzillarda barcha talabni qondiradi va ishlab chiqarish punktlaridan mahsulot yetkazib berishni to'liq olib tashlaydi.
Bosqich 2. Olingan resurs taqsimotining optimalligini tekshirish
3-bosqich. Agar natijada resurslarni taqsimlash optimal bo'lmasa, u holda resurslar qayta taqsimlanadi, transport xarajatlari kamayadi.
4-bosqich. Olingan resurslarni taqsimlashning optimalligini qayta tekshirish.
Bu takrorlanuvchi jarayon optimal yechim olinmaguncha takrorlanadi.
12. Inventarizatsiyani boshqarish modellari.
Har qanday inventarizatsiyani boshqarish modeli ikkita asosiy savolga (qachon va qancha) javob berishga mo'ljallangan bo'lishiga qaramay, qurish uchun turli xil matematik vositalardan foydalanadigan sezilarli miqdordagi modellar mavjud.
Bu holat dastlabki shartlardagi farq bilan izohlanadi. Inventarizatsiyani boshqarish modellarini tasniflashning asosiy asosi - bu saqlangan mahsulotlarga bo'lgan talabning tabiati (esda tutingki, umumiy gradatsiya nuqtai nazaridan biz faqat mustaqil talabga ega bo'lgan holatlarni ko'rib chiqamiz).
Shunday qilib, talabning tabiatiga qarab, inventarizatsiyani boshqarish modellari bo'lishi mumkin
deterministik;
ehtimollik.
O'z navbatida, deterministik talab iste'mol intensivligi vaqt o'tishi bilan o'zgarmasa statik yoki ishonchli talab vaqt o'tishi bilan o'zgarishi mumkin bo'lgan dinamik bo'lishi mumkin.
Talabning ehtimollik zichligi vaqt o'tishi bilan o'zgarmasa, ehtimolli talab statsionar va ehtimollik zichligi funksiyasi vaqt o'tishi bilan o'zgarib turadigan statsionar bo'lishi mumkin. Yuqoridagi tasnif rasmda ko'rsatilgan.
Eng oddiy holat - mahsulotlarga deterministik statik talab. Biroq, bu iste'mol turi amalda juda kam uchraydi. Eng murakkab modellar statsionar bo'lmagan turdagi modellardir.
Inventarizatsiyani boshqarish modellarini yaratishda mahsulotlarga bo'lgan talabning tabiatiga qo'shimcha ravishda, boshqa ko'plab omillarni hisobga olish kerak, masalan:
buyurtmalarni bajarish shartlari. O'rim-yig'im davrining davomiyligi doimiy yoki tasodifiy o'zgaruvchan bo'lishi mumkin;
to'ldirish jarayoni. Bir zumda yoki vaqt o'tishi bilan taqsimlanishi mumkin;
aylanma mablag'lar, saqlash joylari va boshqalar bo'yicha cheklovlar mavjudligi.
13. Navbat tizimlari (QS) va ularning samaradorligi ko'rsatkichlari.
Navbat tizimlari (QS) - bir xil turdagi vazifalarni takroriy bajarilishini amalga oshiradigan maxsus turdagi tizimlar. Bunday tizimlar iqtisodiyot, moliya, ishlab chiqarish va kundalik hayotning ko'plab sohalarida muhim rol o'ynaydi. Moliyaviy va iqtisodiy sohadagi CMOlarga misol sifatida; Sohada har xil turdagi banklar (tijorat, investitsiya, ipoteka, innovatsion, jamg'arma), sug'urta tashkilotlari, davlat aktsiyadorlik jamiyatlari, shirkatlar, firmalar, uyushmalar, kooperativlar, soliq inspektsiyalari, auditorlik xizmatlari, turli aloqa tizimlari (shu jumladan telefon stansiyalari) ), yuk ortish-tushirish majmualari (portlar, yuk stansiyalari), yoqilgʻi quyish shoxobchalari, xizmat koʻrsatish sohasidagi turli korxona va tashkilotlar (doʻkonlar, maʼlumotlar, sartaroshxonalar, chiptalar, valyuta ayirboshlash shoxobchalari, taʼmirlash ustaxonalari, shifoxonalar). Kompyuter tarmoqlari, ma'lumotlarni yig'ish, saqlash va qayta ishlash tizimlari, transport tizimlari, avtomatlashtirilgan ishlab chiqarish maydonchalari, ishlab chiqarish liniyalari, turli xil harbiy tizimlar, xususan, havo mudofaasi yoki raketaga qarshi mudofaa tizimlari kabi tizimlar ham QSning bir turi sifatida qaralishi mumkin.
Har bir QS o'z tarkibiga ma'lum miqdordagi xizmat ko'rsatish moslamalarini o'z ichiga oladi, ular xizmat ko'rsatish kanallari (qurilmalar, liniyalar) deb ataladi. Kanallarning rolini turli xil qurilmalar, muayyan operatsiyalarni bajaruvchi shaxslar (kassirlar, operatorlar, sartaroshlar, sotuvchilar), aloqa liniyalari, avtomobillar, kranlar, ta'mirlash guruhlari, temir yo'llar, yoqilg'i quyish shoxobchalari va boshqalar o'ynashi mumkin.
Navbat tizimlari bir kanalli yoki ko'p kanalli bo'lishi mumkin.
Har bir QS tizimning kirish qismiga ko'pincha muntazam ravishda emas, balki tasodifiy vaqtda keladigan ma'lum ilovalar (talablar) oqimiga xizmat qilish (bajarish) uchun mo'ljallangan. Xizmat ko'rsatish so'rovlari, bu holda, doimiy, ma'lum vaqt emas, balki tasodifiy vaqt davom etadi, bu ko'plab tasodifiy, ba'zan bizga noma'lum sabablarga bog'liq. So'rovga xizmat ko'rsatgandan so'ng, kanal chiqariladi va keyingi so'rovni qabul qilishga tayyor. So'rovlar oqimining tasodifiy tabiati va ularga xizmat ko'rsatish vaqti QSning notekis ish yukiga olib keladi: boshqa paytlarda xizmat ko'rsatilmagan so'rovlar QS kirishida to'planishi mumkin, bu esa QSning ortiqcha yuklanishiga olib keladi va ba'zan, bepul kanallar bilan QS ning kiritilishida hech qanday so'rov bo'lmaydi, bu esa QS ning kam yuklanishiga olib keladi, ya'ni e. o'z kanallarini bekor qilish. QSga kirishda to'plangan ilovalar navbatga "tushadi" yoki navbatda turishning iloji yo'qligi sababli QSni xizmat ko'rsatmasdan qoldiradi.
"QS - iste'molchi" juftligining ishlashi uchun samaradorlik ko'rsatkichlari, bunda iste'molchi deganda barcha ilovalar to'plami yoki ularning ba'zi manbalari tushuniladi (masalan, QS tomonidan vaqt birligiga olib keladigan o'rtacha daromad va boshqalar). Ushbu ko'rsatkichlar guruhi xizmat ko'rsatish so'rovlaridan olingan ba'zi daromadlar va xizmat ko'rsatish xarajatlari bir xil birliklarda o'lchanadigan hollarda foydalidir. Ushbu ko'rsatkichlar odatda juda o'ziga xosdir va QS, xizmat so'rovlari va xizmat ko'rsatish intizomining o'ziga xos xususiyatlari bilan belgilanadi.
14. Ehtimoliy holatlar uchun dinamika tenglamalari (Kolmogorov tenglamalari). Shtatlarning ehtimolliklarini cheklash.
Kolmogorov-Chepman tenglamasini s ga nisbatan s = 0 da formal ravishda differensiatsiya qilib, to'g'ridan-to'g'ri Kolmogorov tenglamasini olamiz:
Kolmogorov-Chepman tenglamasini t = 0 da t ga nisbatan formal ravishda differensiatsiya qilib, teskari Kolmogorov tenglamasini olamiz.
Shuni ta'kidlash kerakki, cheksiz o'lchovli bo'shliqlar uchun operator endi uzluksiz bo'lishi shart emas va hamma joyda ham aniqlanmasligi mumkin, masalan, taqsimotlar fazosida differentsial operator.
Agar S tizimning holatlar soni chekli bo'lsa va har bir holatdan (u yoki bu bosqichlar soni uchun) bir-biriga o'tish mumkin bo'lsa, u holda holatlarning cheklovchi ehtimolliklari mavjud bo'ladi va ular ham bog'liq emas. tizimning dastlabki holati.
Shaklda. shartni qanoatlantiradigan holatlar va oʻtishlar grafigini koʻrsatadi: istalgan holatdan sistema ertami kechmi istalgan boshqa holatga oʻtishi mumkin. Shakldagi grafikdagi 4-3 o'qning yo'nalishi teskari bo'lganda shart bajarilmaydi.
Faraz qilaylik, belgilangan shart bajarildi va shuning uchun marjinal ehtimollar mavjud:
Cheklovchi ehtimolliklar holatlar ehtimoli bilan bir xil harflar bilan belgilanadi, ular esa o'zgaruvchilarni emas, balki raqamlarni bildiradi (vaqt funktsiyalari).
Ko'rinib turibdiki, holatlarning cheklovchi ehtimollari birlikka qo'shilishi kerak: Demak, tizimda ma'lum bir cheklovchi statsionar rejim o'rnatiladi: tizim o'z holatlarini tasodifiy ravishda o'zgartirsin, lekin bu holatlarning har birining ehtimoli bog'liq emas. vaqt bo'yicha va ularning har biri qandaydir doimiy ehtimollik bilan amalga oshiriladi, bu tizimning ushbu holatda o'tkazadigan o'rtacha nisbiy vaqti.
15. O'lim va ko'payish jarayoni.
Markovning uzluksiz vaqtli o'lim va ko'payish jarayoni deganda biz faqat manfiy bo'lmagan butun sonlarni qabul qila oladigan s.p.ni tushunamiz; bu jarayondagi o'zgarishlar istalgan vaqtda t da sodir bo'lishi mumkin, har qanday vaqtda esa u bittaga ko'payishi yoki o'zgarishsiz qolishi mumkin.
Ko'paytirish oqimlari li(t) - bu X(t) funksiyasining oshishiga olib keladigan Puasson oqimlari. Shunga ko'ra, mki (t) - X (t) funktsiyasining pasayishiga olib keladigan o'lim oqimlari.
Grafik bo'yicha Kolmogorov tenglamalarini tuzamiz:
Agar chekli sonli holatlarga ega bo'lgan ip:
Cheklangan holatlar bilan o'lim va ko'payish jarayoni uchun Kolmogorov tenglamalari tizimi quyidagi shaklga ega:
Sof ko'payish jarayoni shunday o'lim va ko'payish jarayoni bo'lib, unda barcha o'lim oqimlarining intensivligi nolga teng.
Sof o'lim jarayoni shunday o'lim va ko'payish jarayoni bo'lib, unda barcha ko'payish oqimlarining intensivligi nolga teng.
16. Ishlamay qolgan navbat tizimlari.
Navbat nazariyasi doirasida ko'rib chiqiladigan muammolardan eng oddiyi, nosozliklar yoki yo'qotishlar bilan bitta kanalli QS modelidir.
Shuni ta'kidlash kerakki, bu holda kanallar soni 1 (). Bu kanal intensivligi ga teng bo'lgan Puasson so'rovlar oqimini oladi. Vaqt intensivlikka ta'sir qiladi:
Agar ariza hozircha bepul bo'lmagan kanalga tushsa, u rad etiladi va endi tizimda ro'yxatga olinmaydi. Ilovalarga tasodifiy vaqt davomida xizmat ko'rsatiladi, ularning taqsimlanishi eksponensial qonunga muvofiq parametr bilan amalga oshiriladi:
17. Kutish bilan navbatga turish tizimlari.
Kanal band boʻlgan vaqtda kelgan soʻrov navbatga qoʻyilgan va xizmatni kutmoqda.
Cheklangan navbat uzunligiga ega tizim. Faraz qilaylik, navbatdagi o'rindiqlar soni m soni bilan cheklangan, ya'ni mijoz navbatda allaqachon m mijoz bo'lgan vaqtda kelsa, u tizimni xizmat qilmasdan qoldiradi. Kelajakda, agar m cheksizlikka moyil bo'lsa, biz navbat uzunligi bo'yicha cheklovlarsiz bir kanalli QS xarakteristikalarini olamiz.
Biz QS holatini tizimdagi so'rovlar soniga qarab raqamlaymiz (xizmat ko'rsatilgan va kutilayotgan xizmat):
— kanal bepul;
— kanal band, navbat yo‘q;
— kanal band, bitta so‘rov navbatda;
— kanal band, k - 1 ta so‘rov navbatda;
- kanal band, tonnalab arizalar navbatda.
18. Konflikt sharoitida qaror qabul qilish usullari. Matritsa o'yinlar. Sof va aralash strategiya o'yinlari.
Matritsali o'yin - bu ikki o'yinchining nol yig'indili yakuniy o'yini bo'lib, unda 1-o'yinchining to'lovi matritsa ko'rinishida beriladi (matritsa qatori 2-o'yinchining qo'llanilgan strategiyasi soniga to'g'ri keladi, ustun mos keladi). 2-o'yinchining qo'llaniladigan strategiyasi soniga; matritsaning satri va ustuni kesishmasida 1-o'yinchining qo'llaniladigan strategiyalarga tegishli to'lovi ko'rsatiladi).
Matritsali o'yinlar uchun ularning har qandayida yechim borligi isbotlangan va uni o'yinni chiziqli dasturlash muammosiga qisqartirish orqali osongina topish mumkin.
Ikki o'yinchi nol yig'indili matritsa o'yinini quyidagi mavhum ikki o'yinchi o'yini sifatida ko'rish mumkin.
Birinchi o'yinchida m ta strategiya i = 1,2,...,m, ikkinchisida n ta strategiya j = 1,2,...,n. Har bir juft strategiyaga (i, j) aij raqami beriladi, u birinchi o'yinchi o'zining i-strategiyasini qabul qilsa, 2-o'yinchi hisobiga 1-o'yinchining to'lovini ifodalaydi va 2 - uning j-strategiyasini.
O'yinchilarning har biri bitta harakatni amalga oshiradi: 1-o'yinchi o'zining i-strategiyasini (i=), 2-o'zining j-strategiyasini (j=) tanlaydi, shundan so'ng 1-o'yinchi 2-o'yinchi hisobiga aij to'lovini oladi (agar aij bo'lsa).
O'yinchining har bir strategiyasi i=; j = ko'pincha sof strategiya deb ataladi.
Ta'rif. O'yinchining aralash strategiyasi uning sof strategiyalarini qo'llash ehtimolining to'liq to'plamidir.
Shunday qilib, agar 1-o'yinchida m sof strategiyalar 1,2,...,m bo'lsa, uning x aralash strategiyasi munosabatlarni qanoatlantiruvchi x = (x1,..., xm) sonlar to'plamidir.
xi³ 0 (i= 1,m), =1.
Xuddi shunday, n ta sof strategiyaga ega bo‘lgan 2-o‘yinchi uchun aralash strategiya y raqamlar to‘plamidir.
y = (y1, ..., yn), yj ³ 0, (j = 1,n), = 1.
O'yinchi har safar bitta sof strategiyadan foydalansa, boshqasidan foydalanishni istisno qilganligi sababli, sof strategiyalar mos kelmaydigan hodisalardir. Bundan tashqari, ular yagona mumkin bo'lgan hodisalardir.
Sof strategiya aralash strategiyaning alohida holatidir. Haqiqatan ham, agar aralash strategiyada 1-ehtimol bilan har qanday i-sof strategiya qo'llanilsa, boshqa barcha sof strategiyalar qo'llanilmaydi. Va bu i-sof strategiya aralash strategiyaning alohida holatidir. Maxfiylikni saqlash uchun har bir o'yinchi boshqa o'yinchining tanlovidan qat'i nazar, o'z strategiyasini qo'llaydi.
19. Matritsali o‘yinni yechishning geometrik usuli.
2xn yoki nx2 o'lchamli o'yinlarning yechimi aniq geometrik talqin qilish imkonini beradi. Bunday o'yinlarni grafik tarzda hal qilish mumkin.
XY tekisligida, abscissa bo'ylab, biz bitta A1A2 segmentini chetga qo'yamiz (5.1-rasm). Segmentning har bir nuqtasi U = (u1, u2) aralash strategiyasi bilan bog'langan. Bundan tashqari, ba'zi bir oraliq nuqta U dan ushbu segmentning o'ng uchigacha bo'lgan masofa A1 strategiyasini tanlash ehtimoli u1, chap uchigacha bo'lgan masofa A2 strategiyasini tanlash ehtimoli u2. A1 nuqtasi sof A1 strategiyasiga, A2 nuqtasi sof A2 strategiyasiga mos keladi.
A1 va A2 nuqtalarida biz perpendikulyarlarni tiklaymiz va ulardagi o'yinchilarning to'lovlarini kechiktiramiz. Birinchi perpendikulyarda (OY o'qiga to'g'ri keladi) biz A1 strategiyasidan foydalanganda, ikkinchisida - A2 strategiyasidan foydalanganda A o'yinchisining foydasini ko'rsatamiz. Agar A o'yinchisi A1 strategiyasidan foydalansa, u holda uning B o'yinchining B1 strategiyasi bilan to'lovi 2 ga, B2 strategiyasi bilan esa 5 ga teng. OY o'qidagi 2 va 5 raqamlari B1 va B2 nuqtalariga to'g'ri keladi. Xuddi shunday, ikkinchi perpendikulyarda biz B "1 va B" 2 nuqtalarini topamiz (6 va 4 to'lovlar).
B1 va B"1, B2 va B"2 nuqtalarini bog'lab, biz ikkita to'g'ri chiziqni olamiz, undan OX o'qiga masofa mos keladigan strategiyalarning har qanday kombinatsiyasi uchun o'rtacha daromadni aniqlaydi.
Masalan, B1B"1 segmentining istalgan nuqtasidan OX o'qigacha bo'lgan masofa A o'yinchisining A1 va A2 strategiyalari (u1 va u2 ehtimolliklari bilan) va B o'yinchining B1 strategiyasining har qanday kombinatsiyasi uchun o'rtacha daromadini aniqlaydi.
B1MB"2 siniq chizig'iga tegishli nuqtalarning ordinatalari A o'yinchisi har qanday aralash strategiyalarni qo'llaganida minimal to'lovini aniqlaydi. Bu minimal qiymat M nuqtada eng katta hisoblanadi, shuning uchun bu nuqta U* = optimal strategiyasiga mos keladi. (,), va uning ordinatasi o'yin narxiga teng v .
M nuqtaning koordinatalarini B1B"1 va B2B"2 chiziqlarning kesishish nuqtasining koordinatalari sifatida topamiz.
Buning uchun siz chiziqlar tenglamalarini bilishingiz kerak. Ikki nuqtadan o'tuvchi to'g'ri chiziq tenglamasi formulasidan foydalanib, bunday tenglamalarni yaratishingiz mumkin:
Muammomiz uchun chiziqlar tenglamalarini tuzamiz.
B1B"1 qatori: = yoki y = 4x + 2.
To'g'ridan-to'g'ri B2B "2: = yoki y = -x + 5.
Biz tizimni olamiz: y = 4x + 2,
Keling, buni hal qilaylik: 4x + 2 = -x + 5,
x = 3/5, y = -3/5 + 5 = 22/5.
Shunday qilib, U = (2/5, 3/5), v = 22/5.
20. Bimatrix o'yinlari.
Bimatritsali o'yin - bu nolga teng bo'lmagan yig'indiga ega ikkita o'yinchining cheklangan o'yini bo'lib, unda har bir o'yinchining to'lovlari tegishli o'yinchi uchun matritsalar bo'yicha alohida beriladi (har bir matritsada qator 1-o'yinchining strategiyasiga, ustunga mos keladi. 2-o'yinchining strategiyasiga mos keladi, birinchi matritsadagi qator va ustunning kesishmasida 1-o'yinchining to'lovi, ikkinchi matritsada - 2-o'yinchining to'lovi.)
Bimatritsali o'yinlar uchun o'yinchilarning optimal xatti-harakatlari nazariyasi ham ishlab chiqilgan, ammo bunday o'yinlarni hal qilish odatiy matritsali o'yinlarga qaraganda qiyinroq.
21. Statistik o'yinlar. To'liq va qisman noaniqlik sharoitida qaror qabul qilish tamoyillari va mezonlari.
Operatsion tadqiqotlarda noaniqlikning uch turini ajratish odatiy holdir:
maqsadlarning noaniqligi;
atrof-muhit haqidagi bilimlarimizning noaniqligi va bu hodisaga ta'sir qiluvchi omillar (tabiatning noaniqligi);
faol yoki passiv sherik yoki raqibning harakatlarining noaniqligi.
Yuqoridagi tasnifda noaniqliklar turi matematik modelning u yoki bu elementi nuqtai nazaridan ko'rib chiqiladi. Masalan, maqsadlarning noaniqligi muammoni shakllantirishda individual mezonlarni yoki foydali ta'sirning butun vektorini tanlashda namoyon bo'ladi.
Boshqa tomondan, boshqa ikki turdagi noaniqliklar asosan cheklash tenglamalarining maqsad funktsiyasini shakllantirishga va qaror qabul qilish usuliga ta'sir qiladi. Albatta, yuqoridagi bayonot har qanday tasnif kabi juda shartli. Biz buni faqat qaror qabul qilish jarayonida yodda tutish kerak bo'lgan noaniqliklarning yana bir qancha xususiyatlarini ta'kidlash uchun taqdim etamiz.
Gap shundaki, noaniqliklarning yuqoridagi tasnifiga qo'shimcha ravishda, ularning tasodifiylikka bo'lgan munosabati nuqtai nazaridan ularning turini (yoki "turini") hisobga olish kerak.
Shu asosda, noma'lum omillar statistik jihatdan barqaror bo'lgan va shuning uchun ehtimollik nazariyasining oddiy ob'ektlari - tasodifiy o'zgaruvchilar (yoki tasodifiy funktsiyalar, hodisalar va boshqalar) bo'lgan stoxastik (ehtimollik) noaniqlikni ajratish mumkin. Bunday holda, muammoni qo'yishda barcha kerakli statistik xarakteristikalar (tarqatish qonunlari va ularning parametrlari) ma'lum bo'lishi yoki aniqlanishi kerak.
Bunday vazifalarga misol qilib, xususan, har qanday turdagi asbob-uskunalarga texnik xizmat ko'rsatish va ta'mirlash tizimi, suyultirishni tashkil qilish tizimi va boshqalar bo'lishi mumkin.
Yana bir ekstremal holat stokastik bo'lmagan noaniqlik bo'lishi mumkin (E.S. Wentzel bo'yicha - "yomon noaniqlik"), unda stokastik barqarorlik haqida hech qanday taxminlar mavjud emas. Nihoyat, tasodifiy o'zgaruvchilarning taqsimlanish qonunlari haqidagi ba'zi farazlar asosida qaror qabul qilinganda, noaniqlikning oraliq turi haqida gapirish mumkin. Shu bilan birga, qaror qabul qiluvchi uning natijalari va real sharoitlar o'rtasidagi nomuvofiqlik xavfini yodda tutishi kerak. Ushbu nomuvofiqlik xavfi xavf koeffitsientlari yordamida rasmiylashtiriladi.
Xavf haqida qaror qabul qilish quyidagi mezonlardan biriga asoslanishi mumkin:
kutilayotgan qiymat mezoni;
kutilgan qiymat va dispersiyaning kombinatsiyasi;
ma'lum chegara darajasi;
kelajakda sodir bo'lishi mumkin bo'lgan voqea.
operatsiya yagona reja bilan birlashtirilgan va aniq maqsadga erishishga qaratilgan har qanday hodisa (harakatlar tizimi) deyiladi. Operatsiya har doim boshqargan voqea, ya'ni. uni tashkil etishni tavsiflovchi ba'zi parametrlarni tanlash usulini tasarruf etish mumkin. Ushbu variantlar deyiladi nazorat o'zgaruvchilari.
Bunday o'zgaruvchilarning har qanday aniq tanlovi deyiladi qaror. Qarorlar muvaffaqiyatli va muvaffaqiyatsiz, oqilona va asossiz bo'lishi mumkin. Optimal ba'zi mezonlarga ko'ra boshqalardan afzalroq bo'lgan bunday echimlarni nomlang.
Operatsion tadqiqotlarning maqsadi - bir nechta bo'lishi mumkin bo'lgan optimal echimlarni dastlabki miqdoriy asoslash. Qarorning yakuniy tanlovi operatsiyalarni tadqiq qilish doirasidan tashqariga chiqadi va qaror nazariyasi deb ataladigan vosita yordamida amalga oshiriladi.
Operatsion tadqiqotlarning har qanday vazifasi dastlabki "intizomiy" shartlarga ega, ya'ni. boshidanoq belgilangan va buzilmasligi mumkin bo'lgan bunday dastlabki ma'lumotlar. Birgalikda ular mumkin bo'lgan echimlar to'plamini tashkil qiladi.
Turli xil echimlarning samaradorligini solishtirish uchun siz nomli miqdoriy mezonga ega bo'lishingiz kerak ishlash ko'rsatkichi(yoki maqsad funktsiyasi). Ushbu ko'rsatkich operatsiyaning maqsadli yo'nalishini aks ettirish uchun tanlanadi.
Ko'pincha operatsiya tasodifiy omillarning ta'siri bilan birga keladi. Keyin samaradorlik ko'rsatkichi sifatida biz optimallashtirishni xohlagan qiymatning o'zi emas, balki uning o'rtacha qiymati (yoki matematik kutish) olinadi.
Ba'zida tasodifiy omillar bilan birga bo'lgan operatsiya shunday maqsadni ko'zlaydi. A, bunga to'liq erishish mumkin yoki umuman erishilmaydi (masalan, "ha - yo'q"). Keyin samaradorlik ko'rsatkichi sifatida ushbu maqsadga erishish ehtimoli tanlanadi. p(A). (Agar p(A) = 0 yoki 1, keyin biz kibernetikadagi mashhur "qora quti" muammosiga kelamiz.)
Ishlash ko'rsatkichini noto'g'ri tanlash juda xavflidir. Muvaffaqiyatsiz tanlangan mezon bo'yicha tashkil etilgan operatsiyalar asossiz xarajatlar va yo'qotishlarga olib kelishi mumkin. (Masalan, korxonaning iqtisodiy faoliyatini baholashning asosiy mezoni sifatida "shaft".)
1.3. Operatsion tadqiqot vazifasining umumiy bayoni
Operatsion tadqiqot vazifalari ikki toifaga bo'linadi: a) to'g'ridan-to'g'ri va b) teskari.
To'g'ridan-to'g'ri vazifalar savolga javob bering: samaradorlik ko'rsatkichi qanday bo'ladi Z agar ma'lum sharoitlarda y Y qandaydir qaror qabul qilinadi x X. Bunday muammoni hal qilish uchun berilgan shartlar va yechim orqali samaradorlik ko'rsatkichini ifodalashga imkon beruvchi matematik model quriladi, xususan:
Qayerda 
berilgan omillar (dastlabki ma'lumotlar),
nazorat o'zgaruvchilari (yechim),
Z- samaradorlik ko'rsatkichi (maqsadli funktsiya),
F– o‘zgaruvchilar orasidagi funksional bog‘liqlik.
Turli modellardagi bu qaramlik turli yo'llar bilan ifodalanadi. O'rtasidagi munosabat 
Va 
odatda chegaralar sifatida ifodalanadi 
Agar qaramlik turi bo'lsa F ma'lum, keyin ko'rsatkich Z to'g'ridan-to'g'ri almashtirish orqali topiladi 
Va 
ushbu funksionallikka.
Teskari muammolar savolga javob bering: qanday qilib, berilgan sharoitlarda 
yechimni tanlang 
shuning uchun ishlash ko'rsatkichi Z maksimal (minimal) ga aylantirildi. Bunday muammo yechimni optimallashtirish muammosi deb ataladi.
To'g'ridan-to'g'ri muammo hal qilinsin, ya'ni. operatsiya modeli o'rnatiladi va qaramlik turi F mashhur. Keyin teskari masalani (ya'ni optimallashtirish masalasini) quyidagicha shakllantirish mumkin.
topmoqchi edi bunday qaror 
unda samaradorlik ko'rsatkichi Z
= opt:
Ushbu formula quyidagicha o'qiydi: Z optimal qiymat mavjud 
mumkin bo'lgan echimlar to'plamiga kiritilgan barcha echimlarni qabul qildi X.
Samaradorlik ko'rsatkichining ekstremumini izlash usuli Z va tegishli optimal yechim 
har doim funksiyaning xususiyatlaridan kelib chiqqan holda tanlanishi kerak F va yechimga qo'yilgan cheklovlar turi. (Masalan, klassik chiziqli dasturlash muammosi.)
Operatsion tadqiqotlar- inson faoliyatining barcha sohalarida (samarali tashkiliy boshqaruv) qarorlarni asoslashning matematik, miqdoriy usullarini ishlab chiqish va amaliy qo'llash bilan shug'ullanadigan fan.
Operatsion tadqiqotlarning umumiy xususiyatlari
Har bir vazifada biz ma'lum bir maqsadni ko'zlagan qandaydir hodisa haqida gapiramiz.
Vaziyatni tavsiflovchi ba'zi shartlar (shu jumladan, biz yo'q qila oladigan vositalar) o'rnatiladi.
Ushbu shartlar doirasida rejalashtirilgan tadbir qaysidir ma'noda eng foydali bo'lishi uchun shunday qaror qabul qilish kerak.
Operatsion tadqiqotlarning xususiyatlari
Qo'yilgan muammoni tahlil qilishga tizimli yondashish ma'lum bir vazifani butun tizimning ishlashi mezoniga ta'siri nuqtai nazaridan ko'rib chiqish kerakligini anglatadi.
Eng katta samaraga faqat oldingi vazifani hal qilish jarayonida yuzaga keladigan bir vazifadan ikkinchisiga o'tishda uzluksizlikni ta'minlaydigan doimiy tadqiqot bilan erishish mumkin.
Operatsion tadqiqotlarning maqsadi optimal echimni topish bo'lsa-da, lekin hisoblash kombinatoryal masalalarning murakkabligi tufayli ular "etarlicha yaxshi" yechim topish bilan cheklanadi.
Operatsion tadqiqotlar kompleksda, ko'plab sohalarda amalga oshiriladi. Tadqiqotni o'tkazish uchun operatsion guruhlar tuziladi:
Operatsion tadqiqotlarning asosiy tushunchalari
FOYDALANISh - yagona reja bilan birlashtirilgan va biron bir maqsadga erishishga qaratilgan har qanday boshqariladigan (ya'ni parametrlarni tanlashga bog'liq) hodisa.
SOLUTION - parametrlarning har qanday aniq tanlovi bizga bog'liq.
OPTIMAL YECHIMLAR - u yoki bu sabablarga ko'ra qarorlar boshqalardan afzalroqdir.
FOYDALANIShI TADQIQATNING MAQSADI - optimal yechimlarni dastlabki miqdoriy asoslash.
ECHIM Elementlari - parametrlar, ularning yig'indisi yechimni tashkil qiladi.
ISHLAB CHIQISH INDIKATORI (MAQSADLI FUNKSIYA) - bu turli yechimlarni samaradorlik nuqtai nazaridan solishtirish imkonini beruvchi va operatsiyaning maqsadli yo'nalishini aks ettiruvchi miqdoriy mezon (W => max yoki W => min).
Maqsadga erishishga maksimal darajada hissa qo'shadigan eng yaxshi echimdir.
Amaliyotning matematik modeli haqida tushuncha
Operatsiyaning eng muhim xususiyatlarini, operatsiyaning muvaffaqiyati asosan bog'liq bo'lgan barcha muhim omillarni aks ettiruvchi, u yoki bu matematik apparatlar yordamida operatsiyaning sxematik, soddalashtirilgan tavsifi.
Operatsion tadqiqotlarning bevosita va teskari muammolari
To'g'ridan-to'g'ri MUAMMOLAR, agar berilgan sharoitlarda biz x X qaror qabul qilsak, nima bo'ladi, degan savolga javob beradi, ya'ni. samaradorlik ko'rsatkichi W (yoki bir qator ko'rsatkichlar) qanday bo'ladi.
Bunday muammoni hal qilish uchun mat quriladi. berilgan shartlar va yechim elementlari orqali bir yoki bir nechta ishlash ko'rsatkichlarini ifodalash imkonini beruvchi model.
teskari MUAMMOLAR samaradorlik ko'rsatkichi W maksimal (minimal) ga aylanishi uchun x yechimni qanday tanlash kerakligi haqidagi savolga javob beradi.
Bu vazifalar yanada qiyinroq. Ularni to'g'ridan-to'g'ri muammolarning echimlarini oddiy sanab o'tish orqali hal qilish mumkin.
Ammo yechimlar soni ko'p bo'lsa, yo'naltirilgan sanab o'tish usullari qo'llaniladi, bunda optimal echim ketma-ket "sinovlar" yoki yaqinlashish orqali topiladi, ularning har biri bizni kerakli optimalga yaqinlashtiradi.
1-bob. Operatsion tadqiqot predmeti va vazifalari.
§ 1. Operatsion tadqiqot nima va u nima qiladi.
§ 2. Operatsion tadqiqotlarning asosiy tushunchalari va tamoyillari.
§ 3. Amallarning matematik modellari.
2-bob. Operatsion tadqiqotlardagi vazifalarning xilma-xilligi va ularni hal qilish usullari.
§ 4. Operatsion tadqiqotlarning bevosita va teskari muammolari. Deterministik vazifalar.
§ 5. Noaniqlik sharoitida yechim tanlash muammosi.
§ 6. Operatsion tadqiqotlarning ko'p mezonli muammolari. "Tizimli yondashuv".
3-bob. Chiziqli dasturlash.
§ 7. Chiziqli dasturlash masalalari.
§ 8. Chiziqli dasturlashning asosiy muammosi.
§ 9. 03LP yechimining mavjudligi va uni topish usullari.
§ 10. Chiziqli dasturlashning transport muammosi.
§ 11. Butun sonli dasturlash masalalari. Chiziqli bo'lmagan dasturlash tushunchasi.
4-bob. Dinamik dasturlash.
§ 12. Dinamik dasturlash usuli.
§ 13. Dinamik dasturlash masalalarini yechish misollari.
§ 14. Umumiy shakldagi dinamik dasturlash muammosi. Optimallik printsipi.
5-bob Markov tasodifiy jarayonlar.
§ 15. Markov jarayoni tushunchasi.
§ 16. Voqealarning oqimlari.
§ 17. Holat ehtimollari uchun Kolmogorov tenglamalari. Shtatlarning yakuniy ehtimoli.
6-bob
§ 18. Navbat nazariyasining vazifalari. Navbat tizimlarining tasnifi.
§ 19. O'lim va ko'payish sxemasi. Kichik formula.
§ 20. Eng oddiy navbat tizimlari va ularning xususiyatlari.
§ 21. Navbat nazariyasidagi murakkabroq muammolar.
7-bob. Tasodifiy jarayonlarni statistik modellashtirish (Monte-Karlo usuli).
§ 22. Usulning g'oyasi, maqsadi va ko'lami.
§ 23. Yagona lot va uni tashkil etish shakllari.
§ 24. Bir amalga oshirishdan statsionar tasodifiy jarayonning xususiyatlarini aniqlash.
8-bob
§ 25. O'yin nazariyasining predmeti va muammolari.
§ 26. Antagonistik matritsali o'yinlar.
§ 27. Cheklangan o'yinlarni echish usullari.
§ 28. Statistik yechimlar nazariyasi muammolari.
AMALIYATLARNI TADQIQOTLARNING MAVZU VA MAQSADLARI
Operatsion tadqiqotlarning asosiy tushunchalari va tamoyillari
Ushbu bo'limda biz "operatsiyalarni tadqiq qilish" fanining terminologiyasi, asosiy tushunchalari va tamoyillari bilan tanishamiz.
Operatsiya - bu bitta g'oya bilan birlashtirilgan va qandaydir maqsadga erishishga qaratilgan har qanday hodisa (harakatlar tizimi) (oldingi bandning 1 - 8-bandlarida ko'rib chiqilgan barcha hodisalar "operatsiyalar").
Operatsiya har doim boshqariladigan hodisadir, ya'ni uning tashkil etilishini tavsiflovchi ba'zi parametrlarni qanday tanlash bizga bog'liq. Bu erda "tashkilot" so'zning keng ma'nosida, shu jumladan operatsiyada qo'llaniladigan texnik vositalar majmui tushuniladi.
Bizga bog'liq bo'lgan har qanday aniq parametrlar qaror deb ataladi. Qarorlar muvaffaqiyatli va muvaffaqiyatsiz, oqilona va asossiz bo'lishi mumkin. Yechimlar u yoki bu sabablarga ko'ra boshqalardan ustun qo'yilgan taqdirda optimal deb ataladi. Operatsion tadqiqotlarning maqsadi - optimal echimlarni dastlabki miqdoriy asoslash.
Ba'zan (nisbatan kamdan-kam hollarda) o'rganish natijasida bitta qat'iy optimal echimni ko'rsatish mumkin, ko'pincha - yakuniy tanlovni amalga oshirish mumkin bo'lgan amaliy ekvivalent optimal (oqilona) echimlar sohasini aniqlash.
E'tibor bering, qaror qabul qilishning o'zi operatsiyani o'rganish doirasidan tashqariga chiqadi va mas'ul shaxsning vakolatiga kiradi, ko'pincha - yakuniy tanlov qilish huquqi berilgan va ular uchun javobgar bo'lgan shaxslar guruhi. bu tanlov. Tanlashda ular matematik hisob-kitobdan kelib chiqadigan tavsiyalar bilan bir qatorda, ushbu hisob-kitobda hisobga olinmagan bir qator fikrlarni (miqdoriy va sifat jihatidan) hisobga olishlari mumkin.
Shaxsning ajralmas mavjudligi (yakuniy qaror qabul qiluvchi organ sifatida) hatto inson ishtirokisiz qaror qabul qiladigan to'liq avtomatlashtirilgan boshqaruv tizimi mavjud bo'lganda ham bekor qilinmaydi. Shuni unutmasligimiz kerakki, boshqaruv algoritmini yaratish, uning mumkin bo'lgan variantlaridan birini tanlash ham qaror va juda mas'uliyatli ishdir. Boshqaruv avtomatlarining rivojlanishi bilan inson funktsiyalari bekor qilinmaydi, balki oddiygina bir elementar darajadan boshqasiga, yuqori darajaga ko'chiriladi. Bundan tashqari, bir qator avtomatlashtirilgan boshqaruv tizimlari boshqariladigan jarayon davomida insonning faol aralashuvini ta'minlaydi.
Jami yechimni tashkil etuvchi parametrlar yechim elementlari deb ataladi. Yechim elementlari sifatida turli raqamlar, vektorlar, funksiyalar, fizik belgilar va boshqalar paydo bo'lishi mumkin.Masalan, agar jo'nash nuqtalaridan bir hil yuklarni tashish rejasi tuzilsa. A 1, A 2, ..., A m manzillarga IN 1,V 2 , ..., V n , u holda yechimning elementlari x ij sonlari bo'ladi , 1-chi jo'nash punktidan qancha yuk jo'natilishi ko'rsatilgan A i V j- mo'ljal j yilda. Raqamlar to'plami x 11 , x 12, …, x 1 n , …, x m 1, x m 2, …, xmn yechim hosil qiladi.
Operatsion tadqiqotlarning eng oddiy muammolarida yechim elementlari soni nisbatan kichik bo'lishi mumkin. Ammo amaliy ahamiyatga ega bo'lgan ko'pgina muammolarda yechim elementlari soni juda ko'p bo'lib, o'quvchi buni mustaqil ravishda tanlash va oldingi paragrafning 1 - 8 misollarida yechim elementlarini "nomi bilan nomlash" orqali tekshirishi mumkin. Oddiylik uchun biz yechimning barcha elementlari to'plamini bitta harf bilan belgilaymiz x va "qaror" deb ayting X".
Operatsion tadqiqotlarning har qanday topshirig'ida biz ma'lum darajada tasarruf etishimiz mumkin bo'lgan yechim elementlariga qo'shimcha ravishda, boshidanoq belgilangan va buzilmasligi mumkin bo'lgan "intizomli" shartlar ham berilgan (masalan, yuk ko'tarish qobiliyati). mashinaning o'lchami, rejalashtirilgan ish hajmi;
uskunaning og'irlik xususiyatlari va boshqalar). Xususan, bunday shartlarga biz tasarruf etish huquqiga ega bo'lgan vositalar (moddiy, texnik, insoniy) va yechimga qo'yilgan boshqa cheklovlar kiradi. Ularning umumiyligida ular "mumkin bo'lgan echimlar to'plami" ni tashkil qiladi.
Keling, bu to'plamni yana bitta harf bilan belgilaymiz x, lekin haqiqat bu yechim X ushbu to'plamga tegishli bo'lsa, biz uni formula sifatida yozamiz: X X(o'qing: element X to'plamga kiritilgan x).
Bu mumkin bo'lgan echimlarning ko'pligi haqida X ushbu yechimlarni ta'kidlang X(ba'zan - bitta, va tez-tez - yechimlarning butun majmuasi), bu yoki boshqa nuqtai nazardan boshqalarga qaraganda samaraliroq (muvaffaqiyatliroq, afzalroq). Turli xil echimlarni samaradorlik nuqtai nazaridan solishtirish uchun siz samaradorlik ko'rsatkichi deb ataladigan qandaydir miqdoriy mezonga ega bo'lishingiz kerak (u ko'pincha "maqsadli funktsiya" deb ataladi). Ushbu ko'rsatkich operatsiyaning maqsadli yo'nalishini aks ettiradigan tarzda tanlanadi. Maqsadga maksimal darajada erishishga hissa qo'shadigan "eng yaxshi" yechim hisoblanadi. "Ism bilan ayting" ishlash ko'rsatkichini tanlash uchun V, Avvalo, o'zingizga savol berishingiz kerak: biz nima xohlaymiz Operatsiyani amalga oshirish orqali biz nimaga intilamiz? Yechimni tanlashda biz tabiiy ravishda samaradorlik ko'rsatkichini o'zgartiradigan variantni afzal ko'ramiz V maksimal (yoki minimal). Masalan, men operatsiyadan keladigan daromadni maksimal darajada oshirishni xohlayman; agar xarajatlar samaradorlik ko'rsatkichi bo'lsa, ularni minimallashtirish maqsadga muvofiqdir. Agar samaradorlik ko'rsatkichini maksimal darajada oshirish kerak bo'lsa, biz uni shaklda yozamiz W => maksimal, va agar minimallashtirilsa - W => min.
Ko'pincha operatsiya tasodifiy omillarning ta'siri bilan birga keladi (ob-havoning injiqliklari, talab va taklifning o'zgarishi, texnik qurilmalarning ishdan chiqishi va boshqalar). Bunday hollarda, odatda, samaradorlik ko'rsatkichi sifatida biz maksimal darajaga ko'tarmoqchi bo'lgan qiymatning o'zi emas, balki uning o'rtacha qiymati (matematik kutish) olinadi.
Ba'zi hollarda, tasodifiy omillar bilan birgalikda operatsiya juda aniq maqsadni ko'zlagan holda sodir bo'ladi. A, faqat to'liq erishish mumkin yoki umuman erishilmaydi ("ha-yo'q" sxemasi) va biz hech qanday oraliq natijalarga qiziqmaymiz. Keyin samaradorlik ko'rsatkichi sifatida ushbu maqsadga erishish ehtimoli tanlanadi. R(A). Misol uchun, agar biron bir ob'ektni yo'q qilish uchun ajralmas shart bilan o'qqa tutilgan bo'lsa, unda samaradorlik ko'rsatkichi ob'ektni yo'q qilish ehtimoli bo'ladi.
Ishlash ko'rsatkichini noto'g'ri tanlash juda xavflidir. Muvaffaqiyatsiz tanlangan mezon nuqtai nazaridan tashkil etilgan operatsiyalar asossiz xarajatlar va yo'qotishlarga olib kelishi mumkin (masalan, korxonalarning iqtisodiy faoliyatini baholashning asosiy mezoni sifatida mashhur "val" ni eslang).
Samaradorlik ko'rsatkichini tanlash tamoyillarini tasvirlash uchun keling, 1-§ ning 1-8 misollariga yana qaytaylik, ularning har biri uchun samaradorlikning tabiiy ko'rsatkichini tanlaymiz va uni maksimal yoki minimallashtirish zarurligini ko'rsatamiz. Misollarni o'rganayotganda, ularning hammasi ham vazifaning og'zaki tavsifi bilan aniq belgilab qo'yilgan samaradorlik ko'rsatkichini tanlash imkoniyatiga ega emasligini yodda tutish kerak, shuning uchun bu masala bo'yicha o'quvchi va muallif o'rtasida farqlar bo'lishi mumkin.
1. Korxonalarni yetkazib berish rejasi. Operatsiyaning vazifasi xom ashyoni minimal transport xarajatlari bilan ta'minlashdir. Ishlash ko'rsatkichi R- vaqt birligi uchun xom ashyoni tashishning umumiy qiymati, masalan, bir oy ( R => min).
2. Magistral yo'l uchastkasining qurilishi. Qurilishni imkon qadar tezroq tugatish uchun rejalashtirish talab qilinadi. Samaradorlikning tabiiy ko'rsatkichi, agar u tasodifiy omillar bilan bog'liq bo'lmasa (uskunaning ishdan chiqishi, individual ishlarni bajarishda kechikishlar) bo'lmasa, qurilishni yakunlash vaqti bo'ladi. Shuning uchun, samaradorlik ko'rsatkichi sifatida siz o'rtacha kutilgan vaqtni tanlashingiz mumkin T qurilishni yakunlash (T => min).
3. Mavsumiy tovarlarni sotish. Samaradorlik ko'rsatkichi sifatida biz mavsum uchun tovarlarni sotishdan kutilayotgan o'rtacha foyda P ni olishimiz mumkin (P => max).
4. Yo'llarni qordan himoya qilish. Bu iqtisodiy jihatdan eng foydali qordan himoya qilish rejasi, shuning uchun samaradorlik ko'rsatkichi sifatida siz vaqt birligi uchun o'rtacha xarajatlarni tanlashingiz mumkin (masalan, yiliga) R yo'llarni saqlash va ulardan foydalanish uchun, shu jumladan himoya vositalarini qurish, yo'lni tozalash va harakatni kechiktirish bilan bog'liq xarajatlar (R => min).
5. Suv osti kemalariga qarshi reyd. Chunki reyd juda aniq maqsadga ega A - qayiqning yo'q qilinishi, keyin samaradorlik ko'rsatkichi sifatida siz ehtimollikni tanlashingiz kerak R(A) qayiq vayron bo'ladi.
6. Mahsulotlarni tanlab nazorat qilish. Muammo bayonotida tavsiya etilgan tabiiy samaradorlik o'lchovi o'rtacha kutilgan xarajatdir. R vaqt birligi uchun nazorat qilish uchun, agar nazorat tizimi ma'lum bir sifat darajasini ta'minlasa, masalan, rad etishlarning o'rtacha foizi belgilanganidan yuqori bo'lmasa ( R=> min).
7. Tibbiy ko'rik. Samaradorlik ko'rsatkichi sifatida siz o'rtacha foizni (ulushni) tanlashingiz mumkin. Q bemorlar va infektsiya tashuvchilari aniqlangan (Q=> tekshiring).
8. Kutubxona xizmati. Muammoni shakllantirishda ba'zi noaniqliklar ataylab tan olingan:
"mijozlarga eng yaxshi xizmat ko'rsatish" yoki "ularning ehtiyojlarini maksimal darajada qondirish" deganda nimani anglatishi aniq emas. Agar xizmat sifati kitobni so‘ragan abonent uni olishni kutayotgan vaqtiga qarab baholansa, samaradorlik ko‘rsatkichi sifatida o‘rtacha vaqtni olish mumkin. T kitobga murojaat qilgan o'quvchi tomonidan kutilgan kitob ( T=> min). Samaradorlik ko'rsatkichi sifatida o'rtacha raqamni tanlab, masalaga biroz boshqacha nuqtai nazardan yondashishingiz mumkin. M vaqt birligi uchun chiqarilgan kitoblar (M => maksimal).
Ko'rib chiqilgan misollar shunchalik sodda tarzda tanlanganki, samaradorlik ko'rsatkichini tanlash nisbatan oson va vazifaning og'zaki tuzilishi, uning (deyarli har doim) aniq maqsadga yo'naltirilganligi bilan bevosita bog'liq. Biroq, amalda bu har doim ham shunday emas. O'quvchi bunga, masalan, shahar transporti samaradorligi ko'rsatkichini tanlashga harakat qilib, ishonch hosil qilishi mumkin. Bunday ko'rsatkich sifatida nimani qabul qilish kerak? Shaharda yo'lovchilar harakatining o'rtacha tezligi? Yoki tashilgan yo'lovchilarning o'rtacha soni? Yoki transport kerakli joyga yetkaza olmaydigan odam yurishi kerak bo'lgan o'rtacha kilometrlar sonimi? Bu erda o'ylash kerak bo'lgan narsa bor!
Afsuski, amaliy ahamiyatga ega bo'lgan aksariyat muammolarda samaradorlik ko'rsatkichini tanlash oddiy emas va noaniq hal qilinadi. Har qanday murakkab vazifa uchun operatsiyaning samaradorligini bitta raqam bilan to'liq tavsiflab bo'lmaydigan holat odatiy holdir - unga yordam berish uchun boshqalarni jalb qilish kerak. Biz bunday "ko'p mezonli" muammolar bilan 6-bandda tanishamiz.
Dinamik dasturlash masalalarini yechish misollari
Ushbu bo'limda biz dinamik dasturlash muammolarining bir nechta oddiy (juda soddalashtirilgan) misollarini ko'rib chiqamiz (va hatto oxirigacha hal qilamiz)
1. Ikki nuqta o'rtasida eng foydali marshrutni yotqizish. Oldingi bandning 4-muammosini eslaylik va uni nihoyatda (va ataylab) soddalashtirilgan sharoitlarda oxirigacha hal qilaylik. Biz ulanish yo'lini qurishimiz kerak
ikki nuqta A Va IN, ulardan ikkinchisi birinchisining shimoli-sharqida joylashgan. Oddiylik uchun, aytaylik. yo'lni yotqizish bir qator qadamlardan iborat va har bir qadamda biz sharqqa yoki shimolga qarab harakat qilishimiz mumkin; har qanday yo'l bilan A V IN pog'onali siniq chiziq bo'lib, uning segmentlari koordinata o'qlaridan biriga parallel (13.1-rasm). Ushbu segmentlarning har birining qurilish xarajatlari ma'lum. dan bunday yo'lni yotqizish talab qilinadi A V IN, bu erda umumiy xarajat minimal bo'ladi.
Buni qanday qilish kerak? Siz ikkita usuldan birini qilishingiz mumkin: yoki barcha mumkin bo'lgan yo'l variantlarini ko'rib chiqing va xarajatlar minimal bo'lganini tanlang (va ko'p sonli segmentlar bilan bu juda, juda qiyin!); yoki o'tish jarayonini ajrating A V IN individual bosqichlarga (bir qadam - bir segment) va boshqaruvni bosqichma-bosqich optimallashtirish. Ma'lum bo'lishicha, ikkinchi usul beqiyos qulayroq! Bu yerga, Operatsion tadqiqotlarning boshqa joylarida bo'lgani kabi, sodda "ko'r" ro'yxatga olishdan ko'ra, maqsadli, uyushgan yechim qidirishning afzalliklari bor.
Keling, bu qanday amalga oshirilishini aniq bir misol bilan ko'rsatamiz. dan masofani ajrating A oldin IN sharqiy yo'nalishda, aytaylik, 7 qismga va shimoliy yo'nalishda - 5 qismga (asosan, parchalanish o'zboshimchalik bilan kichik bo'lishi mumkin). Keyin har qanday yo'l A V IN dan tashkil topgan T\u003d 7 + 5 \u003d= Sharq yoki shimolga yo'naltirilgan 12 ta segment (13.2-rasm). Keling, har bir segmentga ushbu segment bo'ylab yo'l yotqizish narxini (ba'zi ixtiyoriy birliklarda) ifodalovchi raqamni yozamiz. Bunday yo'lni tanlash talab qilinadi A V IN, buning uchun segmentlardagi raqamlar yig'indisi minimaldir.
Biz qurilgan yo'lni boshqariladigan tizim sifatida ko'rib chiqamiz S, dastlabki holatdan nazorat ta'sirida harakat qilish A finalgacha IN. Har bir qadam boshlanishidan oldin ushbu tizimning holati ikkita koordinata bilan tavsiflanadi: sharq (X) va shimoliy (y), ikkalasi ham butun son (0 X 5 7, 0 da 5). Tizimning har bir holati uchun (13.2-rasmdagi to'rtburchaklar panjaraning tugun nuqtasi) biz shartli optimal boshqaruvni topishimiz kerak: biz bu nuqtadan shimolga (boshqaruv "c") yoki sharqqa (nazorat) boramiz. "c"). Ushbu nazorat qolgan barcha bosqichlarning narxi (shu jumladan, bu) minimal bo'lishi uchun tanlangan. Biz ushbu xarajatni tizimning ma'lum bir holati uchun "shartli optimal daromad" deb atashni davom ettiramiz (garchi bu holda bu "daromad" emas, balki "yo'qotish"). S keyingi bosqichni boshlashdan oldin.
Biz shartli optimallashtirish protsedurasini teskari yo'nalishda - oxiridan boshigacha ochamiz. Avvalo, biz oxirgi, 12-bosqichni shartli optimallashtirishni amalga oshiramiz. To'rtburchaklar panjaramizning yuqori o'ng burchagini alohida ko'rib chiqing (13.3-rasm). 11-bosqichdan keyin qayerda bo'lishimiz mumkin? Faqat
 |
bir (oxirgi) qadamda qayerga borishingiz mumkin IN, ya'ni nuqtalardan birida IN 1 yoki AT 2. Agar biz nuqtada bo'lsak IN 1, bizda boshqa tanlov yo'q (majburiy nazorat): biz sharqqa borishimiz kerak va bu bizga 10 birlik turadi. Keling, ushbu 10 raqamini nuqtaga yaqin aylanaga yozamiz IN 1, va optimal boshqaruv dan chiqadigan qisqa o'q bilan ko'rsatiladi IN 1 va sharqqa yo'naltirilgan. Nuqta uchun AT 2 nazorat ham majburiy (shimoliy), oxirigacha oqim 14 ga teng, biz uni nuqtada aylana shaklida yozamiz AT 2. Shunday qilib, oxirgi bosqichni shartli optimallashtirish amalga oshiriladi va har bir nuqta uchun shartli optimal daromad olinadi B 1 , B 2 topilgan va tegishli krujkada qayd etilgan.
Endi oxirgi (11-chi) qadamni optimallashtiramiz. Oxirgidan oldingi (10-chi) bosqichdan so'ng biz nuqtalardan biriga tushishimiz mumkin edi C 1, C 2, C 3(13.4-rasm). Keling, ularning har biri uchun shartli optimal nazorat va shartli optimal to'lovni topamiz. Nuqta uchun 1 dan majburiy boshqaruv: sharqqa boring;
oxirigacha bizga 21 birlik turadi (bu bosqichda 11, plyus 10, aylanada yozilgan IN 1). 21 raqami doira ichida nuqtada yozilgan 1 dan. Nuqta uchun 2 dan boshqaruv endi majbur emas: biz sharqqa ham, shimolga ham borishimiz mumkin. Birinchi holda, biz ushbu bosqichda va undan boshlab 14 birlik sarflaymiz AT 2 oxirigacha - yana 14 ta, atigi 28 birlik. Agar shimolga borsak, biz 13 + 10, jami 23 birlik sarflaymiz. Demak, nuqtada shartli optimal nazorat 2 dan - shimolga boring (buni o'q bilan belgilang va yaqin atrofdagi aylanaga 23 raqamini yozing C 2), Nuqta uchun 3 dan boshqaruv yana majburlanadi ("c"), oxirigacha 22 birlik turadi (o'qni shimolga qo'ying, 22 raqamini aylanaga yozing. 3 dan).
Xuddi shunday, oxirgidan oldingi qadamdan orqaga chekinib, butun koordinatali har bir nuqta uchun shartli optimal nazoratni ("c" yoki "b") topamiz, biz o'q bilan belgilaymiz va shartli optimal daromadni (xarajat) topamiz. yo'lning oxiri), biz aylanada yozamiz. U quyidagicha hisoblab chiqiladi: ma'lum bir qadamdagi oqim tezligi allaqachon optimallashtirilgan oqim tezligiga qo'shiladi, strelka olib boradigan doira ichida yoziladi. Shunday qilib, har bir qadamda biz faqat ushbu bosqichni optimallashtiramiz va undan keyingilar allaqachon optimallashtirilgan. Optimallashtirish jarayonining yakuniy natijasi rasmda ko'rsatilgan. 13.5.
Shunday qilib, shartli optimallashtirish allaqachon amalga oshirilgan: biz qayerda bo'lishimizdan qat'iy nazar, biz qaerga borishni (o'q) va oxirigacha (aylanadagi raqam) erishish uchun bizga nima kerakligini bilamiz. Bir nuqtada aylanada A dan yo'lning butun qurilishi uchun optimal to'lov A V IN:
W* = 118.
Endi so'zsiz optimal boshqaruvni - undan keladigan traektoriyani qurish qoladi A Va IN eng arzon usulda. Buning uchun siz faqat "otishmachilarga bo'ysunishingiz", ya'ni har bir qadamda nima qilishni buyurganlarini o'qishingiz kerak. Bunday optimal traektoriya rasmda ko'rsatilgan. 13,5 ikki marta aylantirildi. Tegishli shartsiz optimal nazorat quyidagicha bo'ladi:
x* =(s, s, s, s, in, in, s, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, s, s, s, s, s, s, s, s, s, s, in, in, s, s, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, in, s, s, s, s, s, s, s, s, s, s, s, s, s, s, s.
ya'ni birinchi to'rt qadamni shimolga, keyingi ikkitasini sharqqa, keyin yana bittasini shimolga va qolgan beshtasini sharqqa qo'yishimiz kerak. Muammo hal qilindi.
E'tibor bering, shartli optimallashtirish jarayonida biz tekislikning qaysidir nuqtasi uchun ikkala boshqaruv ham optimal bo'lgan holatga duch kelishimiz mumkin, ya'ni shu nuqtadan oxirigacha bir xil mablag' sarflanishiga olib keladi.Masalan, koordinatali nuqtada. (5; 1) ikkala boshqaruv "c" va "b" optimal va oxirigacha 62 ga teng oqim beradi. tanlangan "c"). Optimal boshqaruvni noaniq tanlashning bunday holatlari dinamik dasturlashda doimo uchrab turadi; kelajakda biz ularni maxsus belgilamaymiz, balki o'zboshimchalik bilan ekvivalent variantlardan birini tanlaymiz. Albatta, butun jarayonning optimal nazorati bu o'zboshimchalik bilan bog'liq bo'lishi mumkin, ammo optimal daromad emas. Umuman olganda, dinamik dasturlash masalalarida (shuningdek, chiziqli dasturlash masalalarida) yechim har doim ham yagona emas.
Va endi boshiga qaytaylik va muammoni "sodda" yo'l bilan hal qilishga harakat qilaylik, har bir qadamda birinchisidan boshlab, eng foydali (bu bosqich uchun) yo'nalishni tanlaymiz (agar ulardan ikkitasi bo'lsa, biz tanlaymiz. har qanday). Shu tarzda biz nazoratni qo'lga kiritamiz
x = (s, s, in, in, in, in, in, in, in, in, in, s, s).
Keling, ushbu traektoriya uchun xarajatlarni hisoblab chiqamiz. Ular teng bo'ladi V=10 +12 +8+10 +11 +13 +15+8 + +10+9+8+14=128, bu albatta ko'proq. W* = 118. Bu holda farq juda katta emas, lekin boshqalarda bu sezilarli bo'lishi mumkin.
Yuqorida hal qilingan masalada shartlar ataylab o'ta soddalashtirilgan. Albatta, hech kim temir yo'lni "zinapoyada" olib bormaydi, faqat shimolga yoki sharqqa qarab harakatlanadi. Biz har bir nuqtada faqat ikkita boshqaruvdan birini tanlash uchun shunday soddalashtirdik: "dan" yoki "dan". Ikki mumkin bo'lgan yo'nalish o'rniga ulardan bir nechtasini kiritish va qo'shimcha ravishda kichikroq qadamlarni qo'yish mumkin edi; bu fundamental ahamiyatga ega emas, lekin, albatta, hisob-kitoblarni murakkablashtiradi va uzaytiradi.
E'tibor bering, yuqorida ko'rib chiqilganlarga o'xshash vazifalar amalda juda tez-tez uchrab turadi: masalan, ikkita nuqta orasidagi eng tez yo'lni tanlashda yoki samolyot tomonidan tezlik va balandlikda eng tejamkor (yonilg'i sarfi bo'yicha) ortish.
Keling, bir o'tkinchi fikr bildiraylik. Diqqatli o'quvchi, ehtimol, bizning muammomizdagi fikrlarni payqagandir A Va IN(boshi va oxiri) printsipial jihatdan bir-biridan farq qilmaydi: shartli optimal boshqaruvlarni oxiridan boshigacha emas, balki boshidan oxirigacha va shartsiz - qarama-qarshi yo'nalishda qurish mumkin edi. Darhaqiqat, bu shunday: har qanday dinamik dasturlash muammosida "boshlanishi" va "oxiri" almashtirilishi mumkin. Bu hisoblash nuqtai nazaridan ilgari tavsiflangan usulga to'liq mos keladi, ammo bu usul g'oyasini og'zaki tushuntirishda biroz qulayroqdir: buning boshida "allaqachon o'rnatilgan" shartlarga murojaat qilib, bahslashish osonroq. qadam, bu qadamdan keyin hali ham "kelayotgan"larga qaraganda. Aslini olganda, ikkala yondashuv ham mutlaqo ekvivalentdir.
2. Resurslarni taqsimlash muammosi. Dinamik dasturlash usuli ko'plab iqtisodiy muammolarni muvaffaqiyatli hal qilish imkonini beradi (masalan, qarang). Bunday eng oddiy muammolardan birini ko'rib chiqing. Bizning ixtiyorimizda bir qancha mablag'lar (resurslar) mavjud TO, o'rtasida taqsimlanishi kerak T korxonalar P 1, P 2, ..., P m. Korxonalarning har biri i unga investitsiya qilganda X asosida daromad keltiradi x, ya'ni qandaydir funksiyani ifodalaydi ( x). Barcha funksiyalar ( x) (i = 1, 2, ..., T) berilgan (albatta, bu funksiyalar kamaymaydi). Mablag'larni qanday taqsimlash masalasi TO. korxonalar o'rtasida, shuning uchun ular jami maksimal daromad beradi?
Bu muammoni dinamik dasturlash usuli bilan osonlikcha hal qilish mumkin.Uni shakllantirishda u vaqtni nazarda tutmasa ham, P 1 korxonasiga mablag'larni investitsiya qilishni hisobga olgan holda, pul mablag'larini qandaydir ketma-ketlikda taqsimlash operatsiyasini aqliy ravishda ochishingiz mumkin. birinchi qadam va P 2 da va boshqalar.
Boshqariladigan tizim S bu holda, taqsimlanadigan mablag'lar yoki resurslar. Tizimning holati S har bir qadam oldin bitta raqam bilan tavsiflanadi S- naqd pul zaxirasi hali investitsiya qilinmagan. Ushbu muammoda "qadam boshqaruvlari" vositadir x 1, x 2, ..., x 3, korxonalarga ajratilgan. Optimal boshqaruvni, ya'ni bunday raqamlar to'plamini topish talab qilinadi x 1, x 2, ..., xm, bunda umumiy daromad maksimal bo'ladi:
(13.1)
Biz bu muammoni birinchi navbatda umumiy, formulali shaklda, keyin esa - aniq raqamli ma'lumotlar uchun hal qilamiz. Hamma uchun toping i-chi bosqich - shartli optimal to'lov (ushbu bosqichdan oxirigacha), agar biz ushbu bosqichga mablag'lar chegarasi bilan yondashsak S. Shartli optimal to'lovni belgilang W i (S), va tegishli shartli optimal nazorat investitsiya qilingan mablag'lardir i korxona, - x i (S).
Optimallashtirishni oxirgisidan boshlaylik, T - qadam. Keling, qolgan mablag' bilan bu bosqichga kelaylik S. Nima qilishimiz kerak? Shubhasiz, butun miqdorni investitsiya qiling S butunlay korxona P m. Shuning uchun, shartli optimal nazorat bo'yicha m-chi qadam: oxirgi korxonaga barcha mavjud mablag'larni bering S, ya'ni
va shartli optimal to'lov
W m (S) = (S).
Qadriyatlarning butun gamutini hisobga olgan holda S(ularni etarlicha yaqinroq joylashtirish), biz har bir qiymat uchun S bilib olamiz x m (S) Va Vt m (S). Oxirgi bosqich optimallashtirildi.
Keling, so'nggiga o'tamiz (T- 1) qadam. Keling, unga mablag' zaxirasi bilan murojaat qilaylik S. Belgilamoq Vt m -1 (S) oxirgi ikki bosqichda shartli optimal to'lov: ( m- 1)-m va m-m (bu allaqachon optimallashtirilgan). Agar biz ajratsak ( m- 1) qadam ( m- 1) korxona degan ma'noni anglatadi X, keyin oxirgi qadam bo'ladi S-x. Oxirgi ikki qadamdagi to'lovimiz teng bo'ladi
,
va uni topish kerak X, bunda daromad maksimal bo'ladi:
Belgisi maksimal qiymat hamma uchun olinganligini anglatadi X, nima mumkin (ko'proq sarmoya kiritish S, qila olmaymiz) jingalak qavs ichidagi ifodadan. Bu maksimal oxirgi ikki qadam uchun shartli optimal to'lov, keyin esa qiymat X, bu maksimalga erishilganda, shartli optimal nazorat yoqilgan (T- 1) qadam.
va tegishli shartli optimal nazorat x i (S) - bu qiymat X, bu maksimalga erishiladi.
Shu tarzda davom etib, nihoyat 1-korxona P 1 ga yetib boramiz. Bu erda biz qiymatlarni o'zgartirishimiz shart emas S; birinchi qadamdan oldin aktsiya teng ekanligini aniq bilamiz KIMGA:
Shunday qilib, barcha korxonalardan maksimal daromad (daromad) topiladi. Endi faqat "tavsiyalarni o'qish" qoladi. Bu ma'no X, maksimal (13.4) ga erishiladi va 1-bosqichda optimal nazorat mavjud. Ushbu mablag'larni 1-korxonaga kiritganimizdan so'ng, bizda bo'ladi TO- . Ushbu qiymat bo'yicha tavsiyani "o'qish" S, biz ikkinchi korxonaga optimal mablag'larni ajratamiz:
,
va hokazo oxirigacha.
Endi raqamli misolni hal qilaylik. Mablag'larning dastlabki zaxirasi K = 10 (odatiy birliklar) va uni beshta korxona o'rtasida optimal taqsimlash talab qilinadi (t = 5). Oddiylik uchun biz faqat butun sonli mablag'lar investitsiya qilinganligini taxmin qilamiz. daromad funktsiyalari ( X) 13.1-jadvalda keltirilgan.
13.1-jadval
| X | |||||
| 0,5 1,0 1,4 2,0 2,5 2,8 3,0 3,0 | 0,1 0,5 1,2 1,8 2,5 2,9 3,5 3,5 | 0,6 1,1 1,2 1,4 1,6 1,7 1,8 1,8 | 0,3 0,6 1,3 1,4 1,5 1,5 1,5 1,5 | 1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3 |
Har bir ustunda ma'lum miqdordagi investitsiyalardan boshlab daromadlar o'sishni to'xtatadi (aslida bu har bir korxona faqat cheklangan miqdordagi mablag'larni "o'zlashtirish" imkoniga ega ekanligiga mos keladi).
Shartli optimallashtirishni oxirgi, 5-bosqichdan boshlab yuqorida ta'riflanganidek bajaramiz. Har safar biz zaxiraga ega bo'lgan holda keyingi bosqichga o'tamiz S, biz ushbu bosqich uchun u yoki bu miqdordagi mablag'ni ajratishga harakat qilamiz, 13.1-jadvalga muvofiq ushbu bosqichda daromadni olamiz, uni oxirigacha barcha keyingi bosqichlarda allaqachon optimallashtirilgan daromadga qo'shamiz (bizda allaqachon kamroq mablag' qolganligini hisobga olsak, shunchaki Biz ajratgan mablag'lar miqdori bo'yicha) va ushbu summa maksimal darajaga etgan sarmoyani toping. Ushbu investitsiyalar ushbu bosqichda shartli optimal nazoratdir va maksimalning o'zi shartli optimal daromad hisoblanadi.
13.2-jadvalda barcha bosqichlar uchun shartli optimallashtirish natijalari keltirilgan. Jadval quyidagicha tuzilgan: birinchi ustunda mablag'lar zaxirasining qiymatlari ko'rsatilgan S, bilan bu bilan biz bu bosqichga yaqinlashamiz. Bundan tashqari, jadval qadam raqamiga mos keladigan besh juft ustunga bo'lingan. Har bir juftlikning birinchi ustunida qiymat mavjud
13.2-jadval
| S | i=5 | i=4 | i=3 | i=2 | i=1 | |||||
| x5(S) | V 5(S) | x4(S) | W4(S) | x 3(S) | V 3(S) | x2(S) | W2(S) | x 1(S) | V 1(S) | |
| 1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3 1,3 1,3 | 1,0 1,3 1,6 2,3 2,5 2,6 2,7 2,8 2,8 2,8 | 1,0 1,6 2,1 2,4 2,9 3,4 3,6 3,7 3,9 4,1 | 1,0 1,6 2,1 2,4 2,9 3,5 4,1 4,6 5,1 5,6 | 5,6 |
shartli optimal nazorat, ikkinchisida - shartli optimal to'lov. Jadval chapdan o'ngga, yuqoridan pastga to'ldirilgan. Beshinchi - oxirgi bosqichda qaror majburiydir: barcha mablag'lar ajratiladi;
Boshqa barcha bosqichlarda yechim optimallashtirilishi kerak. 5, 4, 3, 2 va 1-bosqichlarni ketma-ket optimallashtirish natijasida biz optimal nazorat va so'zsiz optimal daromad uchun barcha tavsiyalarning to'liq ro'yxatini olamiz. W* butun operatsiya uchun - bu holda, u 5,6 ga teng. 13.2-jadvalning oxirgi ikkita ustunida faqat bitta qator to'ldiriladi, chunki biz birinchi bosqich boshlanishidan oldin tizimning holatini aniq bilamiz:
S0 = K = 10. Barcha bosqichlarda optimal boshqaruvlar hoshiyalangan. Shunday qilib, biz yakuniy xulosaga keldik: birinchi korxonaga o'ntadan ikkitasini, ikkinchisiga beshtasini, uchinchisiga ikkitasini, to'rtinchisiga hech kimni, beshinchisiga bittasini ajratishimiz kerak. Ushbu taqsimot bilan daromad maksimal va 5,6 ga teng bo'ladi.
O'quvchiga 13.2-jadval qanday to'ldirilganligini tushunish uchun biz buni bitta hisoblash namunasida ko'rsatamiz. Keling, masalan, biz yechimni optimallashtirishimiz kerak x 3(7)- uchinchi bosqichda nima qilish kerak, agar biz unga mablag' zaxirasi bilan murojaat qilsak S= 7 va qolgan hamma narsada biz maksimal yutishimiz mumkin
13.3-jadval
| x | 7 - x | W4(7 - x) | +V 4 (7 - x) | |
| 1,8 1,7 1,6 1,4 1,2 1,1 0,6 | 1,0 1,3 1,6 2,3 2,5 2,6 2,7 | 1,8 2,7 2,9 3,0 3,5 3,2 2,7 |
qadamlar, shu jumladan uchinchi? Faraz qilaylik, uchinchidan (4 va 5-chi) keyingi barcha qadamlar allaqachon optimallashtirilgan, ya'ni 13.2-jadvalning birinchi ikki juft ustunlari to'ldirilgan. Keling, topamiz x 3 (7) va V 3(7). Buning uchun biz yordamchi plastinani tuzamiz (13.3-jadvalga qarang). Birinchi ustunda barcha mumkin bo'lgan qo'shimchalar ro'yxati keltirilgan. X uchinchi bosqichda, oshmaydi S = 7. Ikkinchi ustunda - mablag'lar zaxirasidan bunday investitsiyadan keyin nima qoladi S = 7. Uchinchi ustunda - sarmoya kiritishdan uchinchi bosqichdagi daromad X uchinchi korxonada ustun bo'yicha to'ldiriladi (13.1-jadval). To'rtinchi ustunda - qolgan barcha bosqichlar (to'rtinchi va beshinchi) bo'yicha optimal to'lov, agar biz qolgan mablag'lar bilan to'rtinchi bosqichga yaqinlashgan bo'lsak (ustunda to'ldirilgan). i = 4-jadval 13.2). Beshinchi ustunda - ikkita to'lovning yig'indisi: ma'lum bir investitsiya uchun qadam va optimallashtirilgan X uchinchi bosqichda.
Oxirgi ustunning barcha to'lovlaridan maksimali tanlanadi (13.3-jadvalda u tengdir V 3(7) = 3,6 va tegishli boshqaruv X(7) = 2).
Savol tug'iladi: agar 13.3 tipidagi yordamchi jadvalda maksimal bir nechtasiga erishilsa nima bo'ladi? x, va ikki yoki undan ortiqmi? Biz javob beramiz: qaysi birini tanlash muhim emas; daromad unga bog'liq emas. Umuman olganda, dinamik dasturlash masalalarida yechim umuman yagona bo'lmasligi kerak (bu haqda yuqorida aytib o'tgan edik).
3. Mashinani yuklash muammosi. Dinamik dasturlash usulidan foydalanib, siz 3-bobda tasvirlangan bir qator optimallashtirish masalalarini, xususan, ba'zi bir butun sonli dasturlash masalalarini muvaffaqiyatli hal qilishingiz mumkin. E'tibor bering, chiziqli dasturlash masalalarini shunchalik qiyinlashtiradigan yechimlarning yaxlitligi bu holda murakkablashtirmaydi, aksincha, protsedurani soddalashtiradi (biz uchun avvalgi masalada joylashtirishlar yaxlitligi bilan soddalashtirilganidek).
Misol tariqasida, mashinani yuklash muammosini ko'rib chiqing (biz buni avvalgi bobda aytib o'tgan edik): P 1 , P 2 ,..., P n ob'ektlarning ma'lum bir to'plami mavjud (har biri bitta nusxada); ularning vazni ma'lum q 1 , q 2 , ..., q n va xarajat 1 dan, 2, ..., n bilan. Mashinaning yuk ko'tarish qobiliyati Q. Savol shundaki, buyumlarning qaysi birini mashinaga olib borish kerak, shunda ularning umumiy qiymati (umumiy og'irlik bilan). Q) maksimal edi?
