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 yechim 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 shu qadar sodda bo'lishi uchun maxsus 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 boshqaruv 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 mablag'lar zaxirasi 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?

Operatsion tadqiqotlarning asosiy tushunchalari va ta'riflarini o'rganishingiz kerak.

Operatsiya - bu maqsadga erishishga qaratilgan har qanday boshqariladigan faoliyat. Operatsiya natijasi uni amalga oshirish usuliga, tashkil etishga, aks holda - ma'lum parametrlarni tanlashga bog'liq. Parametrlarning har qanday aniq tanlovi yechim deb ataladi. Optimal echimlar, u yoki bu sabablarga ko'ra boshqalardan afzalroq bo'lganlar deb hisoblanadi. Shuning uchun operatsion tadqiqotning asosiy vazifasi optimal echimlarni dastlabki miqdoriy asoslashdir.

Izoh 1

Muammoni shakllantirishga e'tibor qaratish lozim: qaror qabul qilishning o'zi operatsion tadqiqotlar doirasidan tashqariga chiqadi va mas'ul shaxs yoki shaxslar guruhining vakolatiga kiradi, ular matematik jihatdan asoslanmagan boshqa mulohazalarni hisobga olishlari mumkin.

Izoh 2

Agar operativ tadqiqotlarning ba'zi vazifalarida tanlangan samaradorlik mezoni maksimal yoki minimal qiymatga ega bo'lgan optimal echim bo'lsa, boshqa vazifalarda bu umuman kerak emas. Shunday qilib, muammoda biz optimal, masalan, mijozlarga xizmat ko'rsatishning o'rtacha vaqti, masalan, 5 daqiqadan oshmaydigan va har qanday vaqtda o'rtacha navbat uzunligi bo'lgan shunday miqdordagi savdo nuqtalari va xodimlarni ko'rib chiqishimiz mumkin. 3 kishidan oshmasligi kerak (1, .10-11-bet).

Ishlab chiqarish va tijorat faoliyatining samaradorligi asosan turli darajadagi menejerlar tomonidan har kuni qabul qilinadigan qarorlarning sifati bilan belgilanadi. Shu munosabat bilan operatsion tadqiqotlar hal qilishga imkon beradigan qaror qabul qilish jarayonlarini takomillashtirish vazifalari katta ahamiyatga ega. "Operatsion tadqiqotlar" atamasi birinchi marta 1939-1940 yillarda qo'llanilgan. harbiy sohada. Bu vaqtga kelib harbiy texnika va uni boshqarish ilmiy-texnikaviy inqilob natijasida tubdan murakkablashdi. Shu sababli, Ikkinchi Jahon urushi boshlanishiga kelib, yangi harbiy texnikadan samarali foydalanish, qo'mondonlik tomonidan qabul qilingan qarorlarni miqdoriy baholash va optimallashtirish sohasida ilmiy tadqiqotlar olib borish zarurati tug'ildi. Urushdan keyingi davrda yangi ilmiy fanning muvaffaqiyatlari tinch hududlarda: sanoatda, tadbirkorlik va tijorat faoliyatida, davlat muassasalarida va ta'lim muassasalarida talabga ega edi.

Operatsion tadqiqotlar - bu inson faoliyatining barcha sohalarida muammolarni hal qilishni asoslash uchun matematik miqdoriy usullarni qo'llash metodologiyasi. Operatsion tadqiqot usullari va modellari tashkilotning maqsadlariga eng mos keladigan echimlarni olish imkonini beradi.

Operatsion tadqiqotlar - bu tashkiliy tizimlarni eng samarali (yoki optimal) boshqarish usullarini ishlab chiqish va amaliy qo'llash bilan bog'liq fan.

Operatsion tadqiqotlarning asosiy postulati quyidagilardan iborat: optimal yechim (nazorat) - bu operatsiya samaradorligi mezonining (maqsadli funktsiyasi) optimal (maksimal yoki minimal) qiymatiga erishadigan va o'zgaruvchilar qiymatlari to'plamidir. belgilangan cheklovlar.

Operatsion tadqiqotning predmeti uning faoliyati samaradorligini baholashga asoslangan boshqaruv tizimida maqbul qarorlarni qabul qilish muammosidir. Operatsion tadqiqotning xarakterli tushunchalari quyidagilardir: model, o'zgaruvchan o'zgaruvchilar, cheklovlar, maqsad funktsiyasi.

Haqiqatda operatsiyalarni tadqiq qilish ob'ekti ko'p sonli o'zaro ta'sir qiluvchi bo'limlardan iborat bo'lgan tashkiliy boshqaruv tizimlari (tashkilotlar) bo'lib, bo'limlarning manfaatlari har doim ham bir-biriga mos kelmaydi va qarama-qarshi bo'lishi mumkin.

Operatsion tadqiqotlarning maqsadi tashkilotlarni boshqarish bo'yicha qabul qilingan qarorlarni miqdoriy jihatdan asoslashdir.

Butun tashkilot uchun eng foydali bo'lgan yechim optimal yechim deb ataladi va bir yoki bir nechta bo'limlar uchun eng foydali bo'lgan yechim suboptimal bo'ladi.

Bo'limlarning qarama-qarshi manfaatlari to'qnash keladigan tashkiliy boshqaruvning odatiy vazifasiga misol sifatida korxonaning inventarizatsiyasini boshqarish muammosini ko'rib chiqing.

Ishlab chiqarish bo'limi eng kam xarajat bilan imkon qadar ko'proq mahsulot ishlab chiqarishga intiladi. Shuning uchun u eng uzoq va uzluksiz ishlab chiqarishga, ya'ni mahsulotlarni katta partiyalarda ishlab chiqarishga qiziqadi, chunki bunday ishlab chiqarish uskunani qayta konfiguratsiya qilish xarajatlarini va shuning uchun umumiy ishlab chiqarish xarajatlarini kamaytiradi. Biroq, ko'p miqdorda mahsulot ishlab chiqarish katta hajmdagi materiallar, butlovchi qismlar va boshqalar zahiralarini yaratishni talab qiladi.

Savdo bo'limi, shuningdek, istalgan vaqtda xaridorlarning har qanday talabini qondirish uchun tayyor mahsulotlarning katta zaxiralariga qiziqish bildiradi. Savdo bo'limi har bir shartnomani tuzib, iloji boricha ko'proq mahsulotni sotishga intilib, iste'molchiga eng keng turdagi mahsulotlarni taklif qilishi kerak. Natijada, ko'pincha ishlab chiqarish bo'limi va savdo bo'limi o'rtasida mahsulot assortimenti bo'yicha ziddiyat yuzaga keladi. Shu bilan birga, savdo bo'limi kichik hajmda ishlab chiqarilgan ko'plab mahsulotlarni, hatto katta foyda keltirmasa ham, rejaga kiritishni talab qiladi, ishlab chiqarish bo'limi esa bunday mahsulotlarni assortimentdan chiqarib tashlashni talab qiladi.

Moliya bo'limi korxona faoliyati uchun zarur bo'lgan kapital miqdorini minimallashtirishga intilib, "bog'liq" aylanma mablag'lar miqdorini kamaytirishga harakat qilmoqda. Shuning uchun u aktsiyalarni minimal darajaga tushirishdan manfaatdor. Ko'rib turganingizdek, tashkilotning turli bo'limlari uchun zaxiralar hajmiga qo'yiladigan talablar har xil. Qaysi inventarizatsiya strategiyasi butun tashkilot uchun eng foydali bo'ladi degan savol tug'iladi. Bu tashkiliy boshqaruvning odatiy vazifasidir. Bu butun tizimning ishlashini optimallashtirish muammosi bilan bog'liq va uning bo'linmalarining qarama-qarshi manfaatlariga ta'sir qiladi.

Operatsion tadqiqotlarning asosiy xususiyatlari:

1. Qo'yilgan muammoni tahlil qilishga tizimli yondashish. Tizimli yondashuv yoki tizimli tahlil operatsiyalarni tadqiq qilishning asosiy metodologik printsipi bo'lib, u quyidagicha. Har qanday vazifa, bir qarashda qanchalik shaxsiy bo'lib ko'rinmasin, uning butun tizimning ishlashi mezoniga ta'siri nuqtai nazaridan ko'rib chiqiladi. Yuqorida tizimli yondashuv inventarizatsiyani boshqarish muammosi misolida tasvirlangan.

2. Operatsion tadqiqotlar uchun har bir muammoni yechishda tobora ko'proq yangi vazifalar paydo bo'lishi odatiy holdir. Shuning uchun, agar dastlab tor, cheklangan maqsadlar qo'yilsa, operativ usullarni qo'llash samarali bo'lmaydi. Eng katta ta'sirga faqat bir vazifadan ikkinchisiga o'tishda uzluksizlikni ta'minlaydigan doimiy izlanishlar bilan erishish mumkin.

3. Operatsion tadqiqotlarning muhim xususiyatlaridan biri bu muammoning optimal yechimini topishga intilishdir. Biroq, bunday yechim mavjud resurslar (pul, kompyuter vaqti) yoki zamonaviy ilm-fan darajasi tomonidan qo'yilgan cheklovlar tufayli ko'pincha erishib bo'lmaydigan bo'lib chiqadi. Masalan, ko'pgina kombinatoriy masalalar, xususan, mashinalar soni n > 4 bo'lgan jadval tuzish masalalari uchun matematikaning zamonaviy rivojlanishi bilan faqat variantlarni oddiy sanab o'tish orqali optimal echim topish mumkin. Keyin odam o'zini "etarlicha yaxshi" yoki suboptimal yechim izlash bilan cheklashi kerak. Shuning uchun uni yaratuvchilardan biri T.Saati operativ tadqiqotlarni “...boshqa usullar bilan undan ham yomonroq javob beradigan amaliy savollarga yomon javob berish sanʼati” deb taʼriflagan.

4. Operatsion tadqiqotning o‘ziga xos xususiyati shundaki, u kompleks tarzda, ko‘p sohalarda olib boriladi. Bunday tadqiqot o‘tkazish uchun tezkor guruh tuzilmoqda. U turli bilim sohalari mutaxassislaridan iborat: muhandislar, matematiklar, iqtisodchilar, sotsiologlar, psixologlar. Bunday operativ guruhlarni yaratish vazifasi muammoni hal qilishga ta'sir etuvchi omillarning butun majmuasini har tomonlama o'rganish, turli fanlarning g'oyalari va usullarini qo'llashdir.

Har bir operatsion tadqiqot ketma-ketlikda quyidagi asosiy bosqichlardan o'tadi:

1) rejalashtirish vazifasining tavsifi;

2) matematik modelni yaratish;

3) yechim topish;

4) modelni tekshirish va tuzatish;

5) topilgan yechimni amaliyotga tatbiq etish.

Rejalashtirish vazifasining tavsifi:

Tarmoqni rejalashtirish va boshqarish vazifalari

katta kompleks operatsiyalarni (ishlarni) bajarish muddatlari va kompleksning barcha operatsiyalarini boshlash momentlari o'rtasidagi munosabatni ko'rib chiqing. Ushbu vazifalar operatsiyalar to'plamining minimal davomiyligini, xarajatlarning optimal nisbati va ularni amalga oshirish muddatlarini topishdan iborat.

Navbatga qo'yish vazifalari ilovalar yoki talablar navbatlari bilan navbat tizimlarini o'rganish va tahlil qilishga bag'ishlangan bo'lib, tizimlarning ishlash ko'rsatkichlarini, ularning optimal xususiyatlarini, masalan, xizmat ko'rsatish kanallari sonini, xizmat ko'rsatish vaqtini va boshqalarni aniqlashdan iborat.

Inventarizatsiyani boshqarish vazifalari inventar darajalarining (buyurtma nuqtalari) va buyurtma o'lchamlarining optimal qiymatlarini topishdir. Bunday vazifalarning o'ziga xos xususiyati shundaki, zaxiralar darajasining oshishi bilan bir tomondan ularni saqlash xarajatlari oshadi, ikkinchi tomondan, zaxiradagi mahsulotning etishmasligi tufayli yo'qotishlar kamayadi.

Resurslarni taqsimlash muammolari cheklangan mavjud resurslar bilan bajarilishi kerak bo'lgan ma'lum operatsiyalar (ishlar) to'plami bilan yuzaga keladi va operatsiyalar o'rtasida resurslarni optimal taqsimlash yoki operatsiyalar tarkibini topish talab etiladi.

Uskunalarni ta'mirlash va almashtirish vazifalari jihozlarning eskirishi va vaqt o'tishi bilan uni almashtirish zarurati tufayli dolzarbdir. Vazifalar optimal vaqtni, profilaktik ta'mirlash va tekshirishlar sonini, shuningdek jihozlarni modernizatsiya qilinganlarga almashtirish vaqtlarini aniqlashga qisqartiriladi.

Rejalashtirish (rejalashtirish) vazifalari har xil turdagi uskunalarda operatsiyalarning optimal ketma-ketligini (masalan, qismlarga ishlov berish) aniqlashdan iborat.

Rejalashtirish va joylashtirish vazifalari yangi ob'ektlarning soni va joylashishini, ularning mavjud ob'ektlar bilan va o'zaro ta'sirini hisobga olgan holda aniqlashdan iborat.

Yo'nalish tanlash muammolari yoki tarmoq muammolari ko'pincha transport va aloqa tizimidagi turli muammolarni o'rganishda uchraydi va eng tejamkor yo'nalishlarni aniqlashdan iborat (1, 15-bet).

ostida operatsiya muayyan maqsadga erishish uchun yagona g‘oya va yo‘nalish bilan birlashgan har qanday hodisa tushuniladi.

Operatsiya har doim boshqariladigan hodisadir, ya'ni. tashkil etilishini tavsiflovchi parametrlarni tanlash o'zimizga bog'liq.

Bizga qarab parametrlarning har qanday aniq tanlovi chaqiriladi qaror.

Optimal echimlar - bu yoki boshqa sabablarga ko'ra boshqalardan afzalroq bo'lganlar.

Operatsion tadqiqotlarning asosiy maqsadi optimal yechimlarning dastlabki miqdoriy asoslanishi. Operatsion tadqiqotlar qaror qabul qilishni to'liq avtomatlashtirishga qaratilgan emas. Qaror har doim shaxs tomonidan qabul qilinadi. Operatsion tadqiqotlarning maqsadi odamga qaror qabul qilishni osonlashtiradigan miqdoriy ma'lumotlar va tavsiyalarni ishlab chiqarishdir.

Asosiy vazifa bilan bir qatorda - optimal echimlarni asoslash - Operatsion tadqiqotlar doirasi boshqa vazifalarni ham o'z ichiga oladi:

Operatsiyani tashkil qilishning turli xil variantlarini qiyosiy baholash,

Turli parametrlarning ishlashiga ta'sirini baholash,

"Bortbog'larni" tekshirish, ya'ni. buzilishi operatsiyaning muvaffaqiyatiga ayniqsa kuchli ta'sir ko'rsatadigan elementlar va boshqalar.

Ushbu yordamchi vazifalar berilgan operatsiyani alohida emas, balki butunning ajralmas elementi sifatida ko'rib chiqishda alohida ahamiyatga ega. tizimlari operatsiyalar. Operatsiyalarni tadqiq qilish vazifalariga "tizimli" yondashuv faoliyatning butun majmuasining o'zaro bog'liqligi va shartliligini hisobga olishni talab qiladi, ya'ni. ushbu operatsiyaning tizimdagi roli va o'rnini hisobga olgan holda yakuniy qaror qabul qilish.

ostida samaradorlik operatsiya deganda uning oldida turgan vazifani bajarishga moslashish darajasi tushuniladi.

Operatsiyaning samaradorligini baholash va turli xil tashkil etilgan operatsiyalar samaradorligini solishtirish uchun bir nechta raqamli ma'lumotlar bo'lishi kerak. baholash mezoni yoki ishlash ko'rsatkichi.

Operatsion tadqiqotlarda harakatlar ketma-ketligi.

1. Tadqiqot maqsadi shakllantiriladi va muammo bayoni ishlab chiqiladi.

2. Har qanday sohada miqdoriy usullarni qo'llash uchun doimo hodisaning matematik modelini qurish kerak. Asl nusxaning xususiyatlarini tahlil qilish asosida ushbu model qurilgan.

3. Modelni qurib bo'lgach, u bo'yicha natijalar olinadi

4. Ular asl nusxada talqin qilinadi va asl nusxaga o‘tkaziladi.

5. Taqqoslash yordamida simulyatsiya natijalari asl nusxani bevosita o'rganish natijasida olingan natijalar bilan taqqoslanadi.

Agar model yordamida olingan natijalar asl nusxani o'rganishda olingan natijalarga yaqin bo'lsa, u holda ushbu xususiyatlar bo'yicha modelni asl nusxaga adekvat deb hisoblash mumkin.

Avtomatlashtirilgan boshqaruv tizimlarini loyihalash va ishlatishda ko'pincha ularning ishlashining miqdoriy va sifat ko'rsatkichlarini tahlil qilish, ularning optimal tuzilishini aniqlash va boshqalar bilan bog'liq vazifalar paydo bo'ladi.

Ushbu muammolarni hal qilish uchun ob'ektlarda to'g'ridan-to'g'ri tajriba o'tkazish bir qator muhim kamchiliklarga ega:

1. Ob'ektning belgilangan ish rejimi buzilgan.

2. To'liq miqyosli eksperimentda tizimni qurishning barcha muqobil variantlarini tahlil qilish mumkin emas va hokazo.

Bu masalalarni obyektdan ajratilgan va kompyuterda amalga oshirilgan modelda yechish maqsadga muvofiqdir.

Axborot tizimlarini modellashtirishda matematik modellardan keng foydalaniladi.

Matematik modellashtirish usuli - tegishli matematik tavsifni tuzish va uning asosida o'rganilayotgan ob'ektning xususiyatlarini hisoblash orqali turli ob'ektlarni o'rganish usuli.

Matematik modelni qurish kerak. U asl nusxaning ishlashini rasmiy ravishda aks ettiradi va uning xatti-harakatlarining asosiy naqshlarini tavsiflaydi. Bunday holda, barcha ikkinchi darajali, ahamiyatsiz omillar hisobga olinmaydi.

Matematik modellashtirish ob'ekti murakkab tizimlardir. Murakkab tizim - bu tashqi omillar ta'siri ostida axborot bilan bog'liq va o'zaro ta'sir qiluvchi ko'p sonli elementlarning ma'lum bir tarzda tashkil etilgan va maqsadli faoliyat ko'rsatadigan majmui.

Kompyuterda modellashtirish tizimlarining 4 asosiy bosqichi mavjud:

Tizimning kontseptual modelini qurish va uni rasmiylashtirish;

Tizim modelini algoritmlash va modellashtirish dasturini ishlab chiqish;

Simulyatsiyaning dastlabki natijalarini olish va sharhlash;

Model va tizimning muvofiqligini tekshirish; modelni sozlash

Modellashtirish, modelni amalga oshirish natijalari bo'yicha tizim faoliyatining sifat ko'rsatkichlarining asosiy hisobi.

Ma'ruza 3. Ekspert baholash usulining asosiy tushunchalari. Ekspert guruhlarini shakllantirish. ovoz berish tartiblari. Reyting, juftlik taqqoslash, nisbiy shkalada baholash usullari.

1. IO haqida asosiy tushunchalar

VA HAQIDA – turli tashkiliy tizimlarni eng samarali boshqarish usullarini ishlab chiqish va amaliy qo'llash bilan shug'ullanadigan ilmiy intizom.

IO quyidagi bo'limlarni o'z ichiga oladi:

1) matematik dastur. (xo'jalik faoliyati rejalari, dasturlarini asoslash); u bo'limlarni o'z ichiga oladi: chiziqli dastur, chiziqli bo'lmagan dastur, dinamik dastur

2) tasodifiy jarayonlar nazariyasiga asoslangan navbat nazariyasi;

3) ma'lumotlarning to'liq emasligi sharoitida qabul qilingan qarorlarni asoslash imkonini beruvchi o'yin nazariyasi.

Muayyan boshqaruv muammosini hal qilishda IO usullaridan foydalanish quyidagilarni o'z ichiga oladi:

Murakkab vaziyatlarda yoki noaniqlik sharoitida qarorlar qabul qilishning iqtisodiy va matematik modellarini qurish;

Keyingi qarorlarni qabul qilishni belgilovchi o'zaro bog'liqliklarni o'rganish va u yoki bu harakat yo'nalishining afzalliklarini baholashga imkon beruvchi samaradorlik mezonlarini belgilash.

IO ning asosiy tushunchalari va ta'riflari.

Operatsiya – maqsadga erishishga qaratilgan har qanday boshqariladigan faoliyat. Operatsiya natijasi uni amalga oshirish usuliga, tashkil etishga, aks holda - ma'lum parametrlarni tanlashga bog'liq. 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.

Parametrlarning har qanday berilgan tanlovi chaqiriladi qaror . Qarorlar muvaffaqiyatli va muvaffaqiyatsiz, oqilona va asossiz bo'lishi mumkin. Optimal u yoki bu sabablarga ko'ra boshqalardan afzalroq bo'lgan echimlarni ko'rib chiqing. Operatsion tadqiqotlarning asosiy vazifasi optimal echimlarni dastlabki miqdoriy asoslashdir.

Operatsion modeli – Bu matematik apparatlar (har xil turdagi funktsiyalar, tenglamalar, tenglamalar va tengsizliklar tizimlari va boshqalar) yordamida amalga oshiriladigan operatsiyaning juda aniq tavsifidir. Operatsion modelni yaratish tasvirlangan hodisaning mohiyatini tushunishni va matematik apparatni bilishni talab qiladi.

Operatsion samaradorligi – uning vazifani bajarishga moslashish darajasi samaradorlik mezoni - maqsad funktsiyasi shaklida miqdoriy jihatdan ifodalanadi. Samaradorlik mezonini tanlash tadqiqotning amaliy ahamiyatini belgilaydi. (Noto'g'ri tanlangan mezon zararli bo'lishi mumkin, chunki bunday samaradorlik mezoni ostida tashkil etilgan operatsiyalar ba'zan asossiz xarajatlarga olib keladi.)

Tarmoqni rejalashtirish va boshqarish vazifalari katta kompleks operatsiyalarni (ishlarni) bajarish muddatlari va kompleksning barcha operatsiyalarini boshlash momentlari o'rtasidagi munosabatni ko'rib chiqing. Bu vazifalar operatsiyalar majmuasining minimal davomiyligini, xarajatlarning optimal nisbati va ularni amalga oshirish muddatlarini topishdan iborat.

Navbatdagi vazifalar ilovalar yoki talablar navbatlari bilan navbat tizimlarini o'rganish va tahlil qilishga bag'ishlangan va tizimlarning ishlash ko'rsatkichlarini, ularning optimal xususiyatlarini, masalan, xizmat ko'rsatish kanallari sonini, xizmat ko'rsatish vaqtini va boshqalarni aniqlashdan iborat.

Inventarizatsiyani boshqarish vazifalari zaxira darajasi (qayta buyurtma nuqtasi) va buyurtma hajmining optimal qiymatlarini topishdan iborat. Bunday vazifalarning o'ziga xos xususiyati shundaki, zaxiralar darajasining oshishi bilan bir tomondan ularni saqlash xarajatlari oshadi, ikkinchi tomondan, zaxiradagi mahsulotning mumkin bo'lgan etishmasligi tufayli yo'qotishlar kamayadi.

Resurslarni taqsimlash vazifalari cheklangan mavjud resurslar bilan bajarilishi kerak bo'lgan muayyan operatsiyalar (ishlar) to'plami bilan yuzaga keladi va operatsiyalar o'rtasida resurslarning optimal taqsimlanishi yoki operatsiyalar tarkibini topish talab etiladi.

Uskunalarni ta'mirlash va almashtirish vazifalari uskunalarning eskirishi va vaqt o'tishi bilan uni almashtirish zarurati bilan bog'liq. Vazifalar optimal vaqtni, profilaktik ta'mirlash va tekshirishlar sonini, shuningdek jihozlarni modernizatsiya qilinganlarga almashtirish vaqtlarini aniqlashga qisqartiriladi.

Rejalashtirish (rejalashtirish) vazifalari har xil turdagi uskunalarda operatsiyalarning optimal ketma-ketligini (masalan, qismlarga ishlov berish) aniqlashdan iborat.

Rejalashtirish va joylashtirish vazifalari nia yangi ob'ektlarning maqbul soni va joylashishini, ularning mavjud ob'ektlar bilan va o'zaro ta'sirini hisobga olgan holda aniqlashdan iborat.

Marshrut tanlash vazifalari, yoki tarmoq transport va aloqa tizimidagi turli muammolarni o'rganishda eng ko'p uchraydigan vazifalar va eng tejamkor yo'nalishlarni aniqlashdan iborat.

2. Chiziqli dasturning umumiy vazifasi. Optimal yechim

Iqtisodiy va matematik model

LP - bu chiziqli cheklovlar, ya'ni ushbu o'zgaruvchilarni bog'laydigan tenglik yoki tengsizliklar mavjud bo'lganda ko'p o'zgaruvchilarning chiziqli funktsiyasining ekstremumini (maksimal yoki minimal) topish muammolarini hal qilish nazariyasi va raqamli usullarini ishlab chiqadigan matematika sohasi.

LP usullari amaliy masalalarga qo'llaniladi, bunda: 1) mumkin bo'lganlar to'plamidan eng yaxshi echimni (optimal rejani) tanlash kerak; 2) yechim ba'zi kattalik o'zgaruvchilari qiymatlari to'plami sifatida ifodalanishi mumkin; a) muammoning o'ziga xos shartlari bo'yicha amalga oshirilishi mumkin bo'lgan echimlarga qo'yilgan cheklovlar chiziqli tenglamalar yoki tengsizliklar shaklida shakllantiriladi; 4) maqsad asosiy o‘zgaruvchilarning chiziqli funksiyasi sifatida ifodalanadi. Turli xil echimlarni solishtirishga imkon beruvchi maqsad funktsiyasining qiymatlari yechim sifati uchun mezon bo'lib xizmat qiladi.

Iqtisodiy masalani matematik usullar bilan amaliy yechish uchun birinchi navbatda uni iqtisodiy-matematik model yordamida yozish kerak. Iqtisodiy-matematik model - o'rganilayotgan iqtisodiy jarayon yoki ob'ektning matematik tavsifi. Bu model iqtisodiy jarayonning qonuniyatlarini matematik munosabatlar yordamida mavhum shaklda ifodalaydi.

Modelni shakllantirishning umumiy sxemasi: I

1) tayinlanishi - raqamli qiymatlari o'rganilayotgan hodisaning mumkin bo'lgan holatlaridan birini aniq belgilaydigan ma'lum miqdordagi o'zgaruvchilarni tanlash;

2) o‘rganilayotgan hodisaga xos bo‘lgan munosabatlarning matematik munosabatlar (tenglamalar, tengsizliklar) ko‘rinishida ifodalanishi. Bu munosabatlar muammoli cheklovlar tizimini tashkil qiladi;

3) tanlangan optimallik mezonining maqsad funksiya ko'rinishidagi miqdoriy ifodasi; I

4) o'zgaruvchilarga qo'yilgan cheklovlarni hisobga olgan holda, masalani maqsad funksiyaning ekstremumini topish muammosi sifatida matematik tarzda shakllantirish.

Chiziqli dasturlashning umumiy muammosi kabi ko'rinadi:

n ta o‘zgaruvchili m chiziqli tenglamalar va tengsizliklar tizimi berilgan

va chiziqli funksiya

X=(x1,x2,…,xj,…,xn) sistemaga shunday yechim topish kerak, bunda F chiziqli funksiya optimal (ya’ni maksimal yoki minimal) qiymatni oladi.

(1) sistema cheklovchi sistema, F funksiya esa chiziqli funksiya, chiziqli shakl, maqsad funksiya yoki maqsad funksiya deb ataladi.

Qisqacha aytganda, umumiy chiziqli dasturlash muammosi quyidagicha ifodalanishi mumkin:

cheklovlar bilan:

Optimal yechim (yoki optimal reja) LP muammosi (3) shartni qanoatlantiradigan (1) cheklash tizimining X=(x1,x2,…,xj,…,xn) yechimidir, bunda chiziqli funktsiya (2) optimalni (maksimal yoki maksimal) oladi. minimal) qiymat.

Barcha o'zgaruvchilar manfiy bo'lmagan taqdirda, cheklovlar tizimi (1) faqat tengsizliklardan iborat - bunday chiziqli dasturlash muammosi standart (simmetrik) deb ataladi; agar cheklovlar tizimi faqat tenglamalardan iborat bo'lsa, u holda masala kanonik deyiladi.

Kanonik muammoning alohida holati bu asosiy ko'rinishdagi masala bo'lib, u cheklash vektorining barcha koeffitsientlari bilan farqlanadi. b manfiy emas va har bir tenglamada 1 koeffitsientli o'zgaruvchi mavjud bo'lib, u boshqa tenglamalarning birortasiga kirmaydi. Bu xususiyatga ega bo'lgan o'zgaruvchiga asosiy o'zgaruvchi deyiladi.

Standart va kanonik masalalar umumiy masalalarning alohida holatlaridir. Ularning har biri o'ziga xos sohada qo'llaniladi. Bundan tashqari, barcha uchta formulalar bir-biriga ekvivalentdir: har qanday chiziqli dasturlash muammosi oddiy matematik transformatsiyalar yordamida kanonik, standart yoki umumiy masalaga qisqartirilishi mumkin.

4 . Chiziqli algebraning elementlari

n ta o'zgaruvchili m chiziqli tenglamalar tizimi shaklga ega

yoki qisqacha

n ta o'zgaruvchiga ega m chiziqli tenglamalar tizimining istalgan m o'zgaruvchisi (m< n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Такой определитель часто называют базисным минором матрицы А. Тогда остальные m–n переменных называются неосновными (или свободными).

(2.1) sistemani m shartda yechish uchun< n сформулируем утверждение.

Bayonot 2.1. Agar tizim uchunmbilan chiziqli tenglamalarno'zgaruvchilar (m < n) o'zgaruvchilar uchun koeffitsientlar matritsasi darajasi m ga teng, ya'ni. kamida bitta asosiy o'zgaruvchilar guruhi mavjud bo'lsa, unda bu tizim noaniqdir va asosiy bo'lmagan o'zgaruvchilarning har bir ixtiyoriy qiymatlari to'plami tizimning bitta yechimiga mos keladi.

Yechim(2.1) sistemaning X=(x1,x2,…,xn) tizimi faqat manfiy bo'lmagan komponentlarni o'z ichiga olsa, joiz deb ataladi, ya'ni. har qanday j=1,n uchun xj>=0. Aks holda, yechim yaroqsiz deb ataladi.

Tizimning cheksiz yechimlari orasida asosiy yechimlar deb ataladiganlar ajralib turadi.

Asosiy yechim n ta o‘zgaruvchiga ega bo‘lgan m chiziqli tenglamalar sistemasiga barcha n–m asosiy bo‘lmagan o‘zgaruvchilar nolga teng bo‘lgan yechim deyiladi.

Chiziqli dasturlash muammolarida ruxsat etilgan asosiy echimlar yoki ular ham deyilganidek, qo'llab-quvvatlash rejalari alohida qiziqish uyg'otadi. Asosiy o'zgaruvchilardan kamida bittasi nolga teng bo'lgan asosiy yechim degenerativ deb ataladi.

Qavariq nuqtalar to'plami

Qavariq ko'pburchakni qavariq bo'lmagandan ajratib turadigan umumiy belgilovchi xususiyat shundan iboratki, agar siz uning istalgan ikkita nuqtasini olib, ularni segment bilan bog'lasangiz, butun segment ushbu ko'pburchakga tegishli bo'ladi. Bu xususiyatni konveks nuqtalar to'plamining ta'rifi sifatida qabul qilish mumkin.

Nuqtalar to'plami qavariq deb ataladi agar u har qanday ikkita nuqta bilan birga ushbu nuqtalarni bog'laydigan butun segmentni o'z ichiga oladi.

Qavariq to'plamlar muhim ahamiyatga ega mulk: har qanday miqdordagi qavariq to'plamlarning kesishishi (umumiy qismi) qavariq to'plamdir.

Qavariq to'plamning nuqtalari orasida ichki, chegara va burchak nuqtalarini ajratib ko'rsatish mumkin.

To'plamning nuqtasi ichki deyiladi, agar uning ba'zi qo'shnilarida faqat shu to'plamning nuqtalari bo'lsa.

To'plamning nuqtasi chegara deb ataladi, agar uning qo'shnilaridan birortasi berilgan to'plamga tegishli nuqtalarni ham, unga tegishli bo'lmagan nuqtalarni ham o'z ichiga oladi.

Burchak nuqtalari chiziqli dasturlash masalalarida alohida qiziqish uyg'otadi. To'plamning nuqtasi deyiladi burchakli(yoki ekstremal), agar u berilgan to'plamga to'liq tegishli bo'lgan biron bir segment uchun ichki bo'lmasa.

Shaklda. 2.4 ko'pburchakning turli nuqtalariga misollar ko'rsatilgan: ichki (M nuqtasi), chegara (N nuqta) va burchak (A, B, C, D, E nuqtalari). A nuqtasi burchakli, chunki butunlay ko'pburchakka tegishli bo'lgan har qanday segment uchun, masalan, AP segmenti, u ichki emas; A nuqta KL segmentining ichki qismidir, lekin bu segment butunlay ko'pburchakka tegishli emas.

Qavariq to'plam uchun burchak nuqtalari har doim ko'pburchakning (ko'p yuzli) uchlari bilan mos keladi, bu esa qavariq bo'lmagan to'plam uchun kerak emas. Nuqtalar to'plami, agar u barcha chegara nuqtalarini o'z ichiga olsa, yopiq deyiladi. Nuqtalar to'plami deyiladi cheklangan, agar to'plamning istalgan nuqtasida markazlashtirilgan, berilgan to'plamni to'liq o'z ichiga olgan cheklangan uzunlikdagi radiusli shar (aylana) bo'lsa; aks holda to'plam cheklanmagan deb ataladi.

Cheklangan sonli burchak nuqtalariga ega boʻlgan tekislikdagi qavariq yopiq nuqtalar toʻplami chegaralangan boʻlsa, qavariq koʻpburchak, chegaralanmagan boʻlsa, qavariq koʻpburchak mintaqasi deyiladi.

Tengsizliklar, tenglamalar va ularning sistemalari yechimlarining geometrik ma'nosi

Tengsizliklarning yechimlarini ko'rib chiqamiz.

Bayonot 1. Ikki o‘zgaruvchili a11x1+a12x2 tengsizlikning yechimlari to‘plami.<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1 , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравен­ства a11x1+a12x2>=b1.

Kerakli yarim tekislikni (yuqori yoki pastki) aniqlash uchun uning chegarasida yotmaydigan o'zboshimchalik bilan nazorat nuqtasini - qurilgan chiziqni o'rnatish tavsiya etiladi. Agar tengsizlik nazorat nuqtasida qondirilsa, u nazorat nuqtasini o'z ichiga olgan yarim tekislikning barcha nuqtalarida ham qondiriladi va boshqa yarim tekislikning barcha nuqtalarida qondirilmaydi. Va aksincha, agar tengsizlik nazorat nuqtasida qoniqtirilmasa, u nazorat nuqtasini o'z ichiga olgan yarim tekislikning barcha nuqtalarida qondirilmaydi va boshqa yarim tekislikning barcha nuqtalarida qondiriladi. Boshqarish nuqtasi sifatida tuzilgan chiziqda yotmaydigan O (0; 0) koordinatalarining kelib chiqishini olish qulay.

Tengsizliklar sistemalarining yechimlari to'plamini ko'rib chiqing.

Tasdiqlash 2. Ikki o'zgaruvchidagi chiziqli tengsizliklar m mos keluvchi sistemaning yechimlari to'plami qavariq ko'pburchak (yoki qavariq ko'pburchak mintaqasi).

Tengsizliklarning har biri 1-bandga muvofiq, konveks nuqtalar to'plami bo'lgan yarim tekisliklardan birini belgilaydi. Chiziqli tengsizliklarning qo'shma tizimining yechimlari to'plami barcha tengsizliklar yechimlarining yarim tekisliklariga tegishli nuqtalardir, ya'ni. ularning kesishgan joyiga tegishlidir. Qavariq to'plamlarning kesishishi haqidagi bayonotga ko'ra, bu to'plam qavariq bo'lib, chekli sonli burchak nuqtalarini o'z ichiga oladi, ya'ni. qavariq ko'pburchak (qavariq ko'pburchak maydoni).

Burchak nuqtalarining koordinatalari - ko'pburchakning uchlari mos keladigan chiziqlarning kesishish nuqtalarining koordinatalari sifatida topiladi.

Tengsizliklar sistemalari uchun yechimlar sohalarini qurishda boshqa holatlar ham yuz berishi mumkin: yechimlar to'plami qavariq ko'pburchak mintaqadir (2.9-rasm, a); bir nuqta (2.9-rasm, b); tengsizliklar sistemasi mos kelmaganda bo'sh to'plam (2.9-rasm, v).

5 . LP masalalarini echishning geometrik usuli

LP muammosining optimal yechimi

Teorema 1. Agar LP masalasi optimal yechimga ega bo'lsa, u holda chiziqli funktsiya o'zining maksimal qiymatini yechim ko'pburchakning burchak nuqtalaridan birida oladi. Agar chiziqli funktsiya bir nechta burchak nuqtalarida maksimal qiymatni qabul qilsa, u uni shu nuqtalarning qavariq chiziqli birikmasi bo'lgan istalgan nuqtada oladi.

Teorema LP muammolarini hal qilishning asosiy usulini ko'rsatadi. Haqiqatan ham, bu teoremaga ko'ra, mumkin bo'lgan echimlarning cheksiz to'plamini o'rganish o'rniga, ular orasida kerakli optimal echimni topish uchun faqat eritma ko'pburchakning chekli sonli burchak nuqtalarini o'rganish kerak.

Quyidagi teorema burchak nuqtalarini topishning analitik usuliga bag'ishlangan.

Teorema 2. LP masalasining har bir ruxsat etilgan asosiy yechimi eritma ko'pburchakning burchak nuqtasiga to'g'ri keladi va aksincha, eritma ko'pburchakning har bir burchak nuqtasiga ruxsat etilgan asosiy yechim mos keladi.

1 va 2 teoremalardan darhol muhim xulosa kelib chiqadi: agar LP muammosi optimal yechimga ega bo'lsa, u kamida uning ruxsat etilgan asosiy echimlaridan bittasiga to'g'ri keladi.

Shunday qilib, LP muammosining chiziqli funktsiyasining optimalini uning ruxsat etilgan asosiy echimlarining cheklangan sonidan izlash kerak.

Demak, LP masalasining ruxsat etilgan yechimlar to‘plami (yechim poliedri) qavariq ko‘pburchak (yoki qavariq ko‘pburchak mintaqasi) bo‘lib, masalaning optimal yechimi hech bo‘lmaganda yechim ko‘pburchakning burchak nuqtalaridan birida joylashgan.

Ikki o'zgaruvchiga ega standart shakldagi muammoni ko'rib chiqing (P = 2).

Cheklash tizimining geometrik tasviri ko'pburchak bo'lsin ABCDE(4.1-rasm). Bu ko'pburchakning nuqtalari orasidan F=c1x1+c2x2 chiziqli funksiya maksimal (yoki minimal) qiymat oladigan nuqtani topish kerak.

Deb nomlangan narsani ko'rib chiqing daraja chizig'i chiziqli funksiya F, ya'ni. Bu funktsiya bir xil sobit qiymatni qabul qiladigan chiziq A, ya'ni. F = A, yoki c1x1+c2x2=a.

Yechim ko‘pburchagida funksiyaning sath chizig‘i o‘tadigan nuqtani toping F eng katta (chiziqli funktsiya maksimallashtirilgan bo'lsa) yoki eng kichik (agar u minimallashtirilgan bo'lsa) darajasi bilan.

c1x1+c2x2=a funksiyaning sath chizig‘i tenglamasi to‘g‘ri chiziq tenglamasidir. Turli darajalarda A sath chiziqlari parallel, chunki ularning qiyaliklari faqat c1 va c2 koeffitsientlari orasidagi nisbat bilan belgilanadi va shuning uchun tengdir. Shunday qilib, xususiyat darajasidagi chiziqlar F – bu odatda koordinata o'qlariga burchak ostida joylashgan o'ziga xos "parallellar".

Chiziqli funktsiyaning daraja chizig'ining muhim xususiyati shundaki, chiziqning bir yo'nalishda parallel siljishi bilan sath faqat oshadi va boshqa yo'nalishda siljish bilan u faqat kamayadi. Koordinata boshidan boshlab c=(c1,c2) ​​vektor F funksiyaning eng tez ortish yo‘nalishini ko‘rsatadi. Chiziqli funksiyaning sath chizig‘i c=(c1,c2) ​​vektorga perpendikulyar.

LP muammosini grafik hal qilish tartibi:

1. Yechim ko‘pburchagini tuzing.

2. c = (c1, c2) vektorini tuzing va u uchun chiziqli funktsiya darajasining chizig'ini chizing. F, masalan, F=0.

3. Amax(Bmin) nuqtani topish uchun F=0 to'g'ri chiziqni c(-c) vektor yo'nalishi bo'yicha parallel siljishi, bu erda F maksimal (minimum) ga etadi.

1. Optimal nuqtada kesishgan chiziqlar tenglamalarini birgalikda yechish, uning koordinatalarini toping.

2. Fmax(Fmin) ni hisoblang.

Izoh. Minimal nuqta qaror ko‘pburchagiga “kirish” nuqtasi, maksimal nuqta esa ko‘pburchakdan “chiqish” nuqtasidir.

6. Simpleks usuli haqida umumiy tushuncha. Geometrik talqin

Grafik usul chiziqli dasturlash muammolarining juda tor sinfiga nisbatan qo'llaniladi: u ikkitadan ko'p bo'lmagan o'zgaruvchilarni o'z ichiga olgan muammolarni samarali hal qilishi mumkin. Chiziqli dasturlashning asosiy teoremalari ko'rib chiqildi, shundan kelib chiqadiki, agar chiziqli dasturlash muammosi optimal echimga ega bo'lsa, u yechim ko'pburchakning kamida bitta burchak nuqtasiga to'g'ri keladi va hech bo'lmaganda bitta chiziqli dasturlashning ruxsat etilgan asosiy echimlaridan bittasiga to'g'ri keladi. cheklash tizimi. Har qanday chiziqli dasturlash muammosini hal qilish usuli ko'rsatilgan: cheklovlar tizimining cheklangan miqdordagi amalga oshirilishi mumkin bo'lgan asosiy echimlarini sanab o'tish va ular orasidan maqsad funktsiyasi optimal qaror qabul qiladigan birini tanlash. Geometrik jihatdan, bu eritma ko'pburchakning barcha burchak nuqtalarini sanab o'tishga mos keladi. Bunday sanab o'tish oxir-oqibat optimal echimga olib keladi (agar u mavjud bo'lsa), lekin uni amaliy amalga oshirish juda katta qiyinchiliklar bilan bog'liq, chunki haqiqiy muammolar uchun amalga oshirilishi mumkin bo'lgan asosiy echimlar soni cheklangan bo'lsa-da, juda ko'p bo'lishi mumkin.

Agar ro'yxatga olish tasodifiy emas, balki chiziqli funktsiyadagi o'zgarishlarni hisobga olgan holda amalga oshirilsa, sanab o'tiladigan ruxsat etilgan asosiy echimlar soni kamayishi mumkin, ya'ni. Har bir keyingi yechim chiziqli funktsiya qiymatlari bo'yicha oldingisidan "yaxshiroq" (yoki hech bo'lmaganda "yomon emas") bo'lishini ta'minlashga intilish (maksimalni topishda uni oshirish, minimalni topishda uni kamaytirish) . Bunday ro'yxatga olish optimalni topishda qadamlar sonini kamaytirishga imkon beradi. Buni grafik misol bilan tushuntiramiz.

Mumkin echimlar maydoni ko'pburchak bilan ifodalansin ABCDE. Aytaylik, uning burchak nuqtasi A asl ruxsat etilgan asosiy yechimga mos keladi. Tasodifiy ro'yxatga olish uchun ko'pburchakning beshta burchak nuqtasiga mos keladigan beshta asosiy echimni sinab ko'rish kerak bo'ladi. Biroq, chizma yuqoridan keyin ekanligini ko'rsatadi A keyingi cho'qqiga chiqish foydalidir IN, va keyin optimal nuqtaga BILAN. Beshta o'rniga faqat uchta cho'qqi kesib o'tildi, bu chiziqli funktsiyani doimiy ravishda yaxshilaydi.

Yechimni ketma-ket takomillashtirish g'oyasi chiziqli dasturlash muammolarini hal qilishning universal usulining asosini tashkil etdi - simpleks usuli yoki rejani ketma-ket takomillashtirish usuli.

Simpleks usulining geometrik ma'nosi cheklovchi ko'pburchakning bir cho'qqisidan (boshlang'ich deb ataladi) qo'shnisiga ketma-ket o'tishdan iborat bo'lib, bunda chiziqli funktsiya eng yaxshi (hech bo'lmaganda eng yomon emas) qiymatni oladi. muammoning maqsadi; optimal yechim topilgunga qadar - maqsad funksiyasining optimal qiymatiga erishiladigan cho'qqi (agar masala cheklangan optimalga ega bo'lsa).

Simpleks usuli birinchi marta 1949 yilda amerikalik olim J. Danzig tomonidan taklif qilingan bo'lsa, 1939 yildayoq usul g'oyalari rus olimi L.V. Kantorovich.

Har qanday chiziqli dasturlash masalasini hal qilishga imkon beruvchi simpleks usuli universaldir. Hozirgi vaqtda u kompyuter hisob-kitoblari uchun ishlatiladi, ammo simpleks usuli yordamida oddiy misollarni qo'lda ham hal qilish mumkin.

Simpleks usulini amalga oshirish uchun - yechimni ketma-ket takomillashtirish - o'zlashtirish kerak uchta asosiy element:

muammoning har qanday boshlang'ich mumkin bo'lgan asosiy echimini aniqlash usuli;

eng yaxshi (aniqrog'i, eng yomon emas) yechimga o'tish qoidasi;

topilgan yechimning optimalligini tekshirish mezoni.

Simpleks usulidan foydalanish uchun chiziqli dasturlash masalasini kanonik shaklga keltirish kerak, ya'ni. cheklovlar tizimi tenglamalar shaklida taqdim etilishi kerak.

Adabiyotda yetarlicha batafsil tavsiflangan: boshlang'ich tayanch rejasini topish (dastlabki amalga oshirilishi mumkin bo'lgan asosiy yechim), shuningdek, sun'iy asos usulidan foydalanish, optimal mos yozuvlar rejasini topish, simpleks jadvallari yordamida muammolarni hal qilish.

7 . Simpleks usulining algoritmi.

LLP ning simpleks usuli bilan yechilishini ko'rib chiqamiz va uni maksimallashtirish masalasiga bog'liq holda taqdim etamiz.

1. Masalaning shartiga ko'ra uning matematik modeli tuziladi.

2. Tuzilgan model kanonik shaklga o'tkaziladi. Bunday holda, dastlabki mos yozuvlar rejasiga ega bo'lgan asos ajralib turishi mumkin.

3. Masalaning kanonik modeli barcha erkin atamalar manfiy bo‘lmasligi uchun simpleks jadvali ko‘rinishida yozilgan. Agar dastlabki mos yozuvlar rejasi tanlangan bo'lsa, 5-bosqichga o'ting.

Simpleks jadvali: cheklovchi tenglamalar tizimi va maqsad funktsiyasi boshlang'ich asosga nisbatan echilgan ifodalar shaklida kiritiladi. Maqsad funksiyasi F koeffitsientlari kiritilgan chiziq F-chiziq yoki maqsad funksiya chizig'i deyiladi.

4. Dastlabki mos yozuvlar rejasi F qatori elementlarining belgilarini hisobga olmagan holda, minimal simpleks nisbatlariga mos keladigan ijobiy ruxsat elementlari bilan simpleks o'zgarishlarni amalga oshirish orqali topiladi. Agar o'zgartirishlar jarayonida 0 qator bo'lsa, uning barcha elementlari, erkin haddan tashqari, nolga teng bo'lsa, u holda masalaning cheklovchi tenglamalari tizimi mos kelmaydi. Agar 0-qator bo'lsa, unda erkin termindan tashqari, boshqa ijobiy elementlar bo'lmasa, cheklovchi tenglamalar tizimi manfiy bo'lmagan echimlarga ega emas.

(2.55), (2.56) tizimini yangi asosga qisqartirish chaqiriladi simpleks transformatsiyasi . Agar simpleks o'zgartirish rasmiy algebraik operatsiya deb hisoblansa, unda ko'rish mumkinki, bu operatsiya natijasida rollar ma'lum bir chiziqli funktsiyalar tizimiga kiritilgan ikkita o'zgaruvchi o'rtasida qayta taqsimlanadi: bir o'zgaruvchi bog'liqdan mustaqilga o'tadi va ikkinchisi aksincha - mustaqildan qaramlikka. Bu operatsiya algebrada ma'lum Iordaniyani yo'q qilish bosqichi.

5. Topilgan dastlabki asosiy reja optimalligi uchun tekshiriladi:

a) agar F qatorida salbiy elementlar bo'lmasa (erkin atama hisobga olinmasa), unda reja optimal hisoblanadi. Agar nol bo'lmasa, optimal reja noyobdir; agar kamida bitta nol bo'lsa, unda cheksiz ko'p optimal rejalar mavjud;

b) agar F qatorida musbat bo'lmagan elementlar ustuniga mos keladigan kamida bitta manfiy element bo'lsa, u holda;

v) agar F qatorida kamida bitta salbiy element va uning ustunida kamida bitta musbat element bo'lsa, biz optimalga yaqinroq bo'lgan yangi mos yozuvlar rejasiga o'tishimiz mumkin. Buning uchun ko'rsatilgan ustunni minimal simpleks nisbati bo'yicha hal qiluvchi sifatida belgilash kerak, hal qiluvchi qatorni toping va simpleks o'zgartirishni amalga oshiring. Olingan asosiy reja optimalligi uchun qayta ko'rib chiqiladi. Ta'riflangan jarayon optimal reja olinmaguncha yoki muammoni hal qilib bo'lmaguncha takrorlanadi.

Bazisga kiritilgan o'zgaruvchi uchun koeffitsientlar ustuni hal qiluvchi deb ataladi. Shunday qilib, F-qatorning salbiy elementi tomonidan asosga kiritilgan o'zgaruvchini tanlash (yoki hal qiluvchi ustunni tanlash), biz F funktsiyasining oshishini ta'minlaymiz. .

Bazisdan chiqarib tashlanadigan o'zgaruvchini aniqlash biroz qiyinroq. Buning uchun ular bo'sh a'zolarning hal qiluvchi ustunning musbat elementlariga nisbatlarini tuzadilar (bunday munosabatlar simpleks deb ataladi) va ular orasidan eng kichigini topadilar, bu esa chiqarib tashlangan o'zgaruvchini o'z ichiga olgan qatorni (yechish) aniqlaydi. Minimal simpleks nisbati bo'yicha bazadan chiqarib tashlanishi kerak bo'lgan o'zgaruvchini tanlash (yoki hal qiluvchi qatorni tanlash), allaqachon belgilanganidek, yangi mos yozuvlar dizaynida bazaviy komponentlarning ijobiyligini kafolatlaydi.

Algoritmning 3-bosqichida erkin atamalar ustunining barcha elementlari manfiy emas deb hisoblanadi. Bu talab majburiy emas, lekin agar u bajarilsa, keyingi barcha simpleks o'zgarishlar faqat hisob-kitoblar uchun qulay bo'lgan ijobiy ruxsat elementlari bilan amalga oshiriladi. Agar erkin a'zolar ustunida manfiy raqamlar mavjud bo'lsa, u holda hal qiluvchi element quyidagicha tanlanadi:

1) ba'zi bir manfiy erkin a'zoga, masalan, t qatoriga mos keladigan qatorga qarang va undagi istalgan salbiy elementni tanlang va unga mos ustun ruxsat beruvchi sifatida qabul qilinadi (biz muammoning cheklovlari mos keladi deb taxmin qilamiz) );

2) erkin a'zolar ustuni elementlarining bir xil belgilarga ega bo'lgan echuvchi ustunning mos keladigan elementlariga nisbatlarini tashkil qiladi (simpleks nisbatlar);

3) simpleks munosabatlardan eng kichigini tanlang. Bu ruxsat qatorini aniqlaydi. Bo'lsin, masalan, R- chiziq;

4) yechish ustunlari va satrlari kesishmasida hal qiluvchi element topiladi. Agar y-satrning elementi hal qiluvchi bo'lib chiqsa, u holda simpleks o'zgartirilgandan so'ng bu satrning erkin a'zosi musbat bo'ladi. Aks holda, keyingi bosqichda t qatoriga yana murojaat qilinadi. Agar muammoni hal qilish mumkin bo'lsa, unda ma'lum miqdordagi qadamlardan so'ng erkin atamalar ustunida salbiy elementlar bo'lmaydi.

8. Teskari matritsa usuli

Shaklning LP ni ko'rib chiqing:

A - cheklash matritsasi;

C=(c1,c2,…,cn)–vektor–qator;

X=(x1,x2,…,xn) – o‘zgaruvchilar;

o'ng tomonning vektoridir.

Biz barcha tenglamalar chiziqli mustaqil deb faraz qilamiz, ya'ni daraja(a)=m. Bunda bazis A matritsa tartibining minoridir.Ya’ni, kamida bitta m tartibli B submatritsasi borki, shundayki |B|<>0. B ga mos keladigan barcha noma'lumlar asosiy deyiladi. Qolganlarning hammasi bepul.

B bazis bo'lsin. Keyin, A matritsasining ustunlarini almashtirib, har doim A ni A=(B|N) ko'rinishga keltirish mumkin,

bu erda N - A matritsaning bazisga tegishli bo'lmagan ustunlaridan tashkil topgan submatritsa. Xuddi shu tarzda, x vektorini - asosiy o'zgaruvchilar vektori va ga bo'lish mumkin.

(1) masalaning har qanday yechimi A*x=b shartni qanoatlantiradi va demak, sistema quyidagi shaklni oladi:

Chunki |B|<>0 bo'lsa, teskari matritsa mavjud. Chapdagi teskari ko'paytirilsa, biz quyidagilarni olamiz:

- umumiy qaror.

Asosiy yechim (B asosiga nisbatan) shart bo'yicha olingan (2) muammoning muayyan yechimidir. Keyin u o'ziga xos tarzda aniqlanadi.

Asosiy yechim deyiladi amalga oshirish mumkin, Agar.

Amalga oshirilgan asosiy yechimga mos keladigan asos. chaqirdi amalga oshiriladigan asos. Agar vektor nol komponentlarga ega bo'lsa, asosiy yechim degenerativ deb ataladi.

Umumiy yechim mavjud bo'lgan barcha echimlarni o'z ichiga oladi. Keling, maqsad funksiyasiga qaytaylik. Biz asosiy o'zgaruvchilar oldida Cb-koeffitsientlarni kiritamiz, Cn-qolganlari.

Shunday qilib, biz olamiz. Biz umumiy yechimni almashtiramiz:

Bayonot. Asosiy yechim uchun optimallik mezoni.

Aytaylik. Keyin asosiy yechim optimal bo'ladi. Agar, u holda asosiy yechim optimal emas.

Hujjat: Bo'lsin. Asosiy yechimni ko'rib chiqing, .

Demak, asosiy yechim uchun maqsad funksiyaning qiymati.

Boshqa yechim bo'lsin: (Xb, Xn).

Keyin qaraymiz

Shunday qilib, asosiy yechim min. Aksincha, ushlab turmasin, ya'ni. mavjud.

Keyin maqsad funksiyasining qiymati asosiy yechim uchun maqsad funktsiyasi qiymatidan kichik bo'lgan yechim mavjud.

Xi:Xj erkin o'zgaruvchiga mos kelsin, qiymat belgilang va uni bazisga kiriting va boshqa o'zgaruvchini chiqaring va uni erkin deb nomlang.

Qanday aniqlash mumkin? Bundan tashqari barcha erkin o'zgaruvchilar hali ham 0 dir.

Keyin umumiy yechimda, qaerda.

Biz chiqaramiz: - zarur shart.

Asosiy yechim muntazam if deyiladi. Biz o'zgaruvchini bazisdan olamiz. Yangi yechim bilan maqsad funksiyasi kamayadi, chunki

Algoritm:

1. Standart shakldagi LP muammosi.

2. Chiziqli mustaqil tenglamalarni qoldiramiz.

3. |B| bo'ladigan B matritsasini toping<>0 va asosiy yechim.

Biz hisoblaymiz:

agar, u holda optimal yechim bor - bu asosiy yechim;

agar, agar komponentni topsak, uni biriktiramiz, shuning uchun biz boshqa yechim topamiz; – asosiy o'zgaruvchilardan qaysi biri =0 bo'lsa. Biz bu o'zgaruvchini asosdan olib tashlaymiz, xi kiritamiz. Biz B1 asosiga yangi B2 konjugat asosini oldik. Keyin yana hisoblaymiz.

1. Agar optimal yechim mavjud bo'lsa, unda cheklangan miqdordagi qadamlardan so'ng biz uni olamiz.

Geometrik jihatdan protsedura X to'plamning chegarasi bo'ylab burchak nuqtasidan konjugat burchak nuqtasiga o'tish, masalaning yechimlari to'plami sifatida talqin qilinadi. Chunki chekli sonli burchak nuqtalari mavjud va F(x) funktsiyasining qat'iy kamayishi bir xil ekstremal nuqtadan ikki marta o'tishni taqiqlaydi, agar optimal yechim mavjud bo'lsa, unda chekli qadamlardan keyin biz uni olamiz.

9. Muammoning iqtisodiy talqini, resurslardan foydalanishning ikkilamchi muammosi

Vazifa. Ikki turdagi P1 va P2 mahsulotlarini ishlab chiqarish uchun to'rt turdagi S1, S2, S3, S4 resurslaridan foydalaniladi. Berilgan resurslar zahiralari, mahsulot birligini ishlab chiqarishga sarflangan resurslar birliklari soni. P1 va P2 ishlab chiqarish birligidan olingan foyda ma'lum. Uni sotishdan olinadigan foyda maksimal bo'ladigan mahsulot ishlab chiqarish rejasini tuzish kerak.

VazifaI(asl):

F=c1x1+c2x2+…+CnXn->maxsus cheklovlar bilan:

manfiy bo'lmagan holat x1>=0, x2>=0,…,Xn>=0

X=(x1,x2,…,Xn) shunday ishlab chiqarish rejasini tuzing, unda mahsulot sotishdan olinadigan foyda (daromad) maksimal bo'ladi, agar har bir mahsulot turi bo'yicha resurslar iste'moli mavjud bo'lganidan oshmasa. aktsiyalar

VazifaII(ikkitalik)

Z=b1y1+b2y2+…+BmYm->min

cheklovlar bilan:

va salbiy bo'lmagan holat

y1>=0, y2>=0,…,yn>=0.

Y=(y1,y2,…,yn) resurslari narxlarining (baholarining) shunday to‘plamini toping, bunda resurslarning umumiy qiymati minimal bo‘ladi, agar mahsulotning har bir turini ishlab chiqarishda resurslarning tannarxi shunday bo‘lsa. ushbu mahsulotlarni sotishdan olingan foydadan (daromaddan) kam bo'lmagan

Yuqoridagi modelda bi(i=1,2,…,m) Si resurs zaxirasini bildiradi; aij- ishlab chiqarish birligini ishlab chiqarishda sarflangan Si resurs birliklari soni Pj(j=1,2,…,n); cj- mahsulot birligini sotishdan olingan foyda (daromad) Pj (yoki ishlab chiqarish narxi Pj) .

Faraz qilaylik, qandaydir tashkilot S1, S2,…,Sm korxona resurslarini sotib olishga qaror qildi va bu resurslarga y1,y2,…,ym optimal narxlarni belgilash zarur. Ko'rinib turibdiki, sotib oluvchi tashkilot Z barcha resurslarning xarajatlari b1,b2,…,bm miqdorida bo'lishidan manfaatdor. y1,y2,…,ym narxlarida mos ravishda minimal edi, ya'ni. Z=b1,y1+b2y2+…+bmym->min.

Boshqa tomondan, resurslarni sotuvchi korxona olingan daromadning korxona resurslarni tayyor mahsulotga qayta ishlashda olishi mumkin bo'lgan miqdordan kam bo'lmasligidan manfaatdor.

A11 birlik S1 resurs, a21 birlik S2 resurs,…., aj1 resurs birligi Si1 ,……, am1 resurs Sm birlik P1 mahsulot birligini y1,y1,…,yi bahoda ishlab chiqarishga sarflanadi. mos ravishda ,…,ym. Shuning uchun, sotuvchining talablarini qondirish uchun P1 ishlab chiqarish birligini ishlab chiqarishda iste'mol qilinadigan resurslarning narxi kamida uning narxi c1 bo'lishi kerak, ya'ni. a11y1+a21y2+…+am1ym>=c1.

Xuddi shunday, P1,P2,...Pn mahsulotning har bir turi uchun tengsizliklar ko'rinishidagi cheklovlarni tuzish mumkin. Iqtisodiy-matematik model va shu tariqa olingan dual masala II ning mazmunli talqini jadvalning o‘ng qismida keltirilgan.

Resurs narxlari y1,y1,…,yi,…,ym iqtisodiy adabiyotlarda turli nomlarni olgan: hisob, yashirin, soya . Bu nomlarning ma'nosi shundan iboratki shartli , "soxta" narxlar. Odatda ishlab chiqarish boshlanishidan oldin ma'lum bo'lgan mahsulotlar uchun "tashqi" narxlardan farqli o'laroq, y1, y2, ..., ym. bor ichki , chunki ular tashqaridan o'rnatilmagan, balki muammoni hal qilish natijasida bevosita aniqlanadi, shuning uchun ular ko'pincha chaqiriladi taxminlar resurslar.

10. O'zaro dual LP masalalari va ularning xossalari

Jadvalda keltirilgan chiziqli dasturlashning ikkita I va II muammolarini ularning iqtisodiy va matematik modellariga kiritilgan parametrlarning mazmunli talqinidan abstraktlashtirib ko'rib chiqaylik.

Ikkala vazifa ham quyidagilarga ega xususiyatlari:

1. Bir masalada ular chiziqli funksiyaning maksimalini, ikkinchisida esa minimalini izlaydilar.

2. Bir masalaning chiziqli funksiyasidagi o‘zgaruvchilar uchun koeffitsientlar boshqasidagi cheklovlar tizimining erkin a’zolaridir.

3. Masalalarning har biri standart shaklda, maksimallashtirish masalasida esa shaklning barcha tengsizliklari berilgan.<=", а в задаче минимизации – все неравенства вида ">=".

4. Ikkala masalaning cheklanishlar sistemasidagi o'zgaruvchilar uchun koeffitsientlar matritsalari bir-biriga o'tkaziladi.

5. Bitta muammoning cheklovlar sistemasidagi tengsizliklar soni boshqa masaladagi o‘zgaruvchilar soniga teng.

6. Har ikkala masalada ham o‘zgaruvchilarning manfiy bo‘lmasligi shartlari saqlanib qoladi.

Izoh. Agar manfiy bo'lmagan shart dastlabki masalaning j-chi o'zgaruvchisiga qo'yilgan bo'lsa, u holda ikki tomonlama masalaning j-cheklovi tengsizlik bo'ladi, lekin j-chi o'zgaruvchi ham ijobiy, ham manfiy qiymatlarni qabul qila olsa, u holda dual masalaning j-cheklovi tenglama bo'ladi; asl muammoning cheklovlari va ikkilamchi muammoning o'zgaruvchilari xuddi shunday bog'liqdir.

Belgilangan xossalarga ega chiziqli dasturlashning ikkita I va II masalalari simmetrik o'zaro dual masalalar deyiladi. Keyinchalik, soddalik uchun biz ularni shunchaki chaqiramiz ikki tomonlama vazifalar.

Har bir LP muammosi uning ikkilamchi muammosi bilan bog'liq bo'lishi mumkin.

11. Dual masalani kompilyatsiya qilish algoritmi:

1. Asl muammoning cheklash tizimining barcha tengsizliklarini bir xil ma'noga keltiring: agar dastlabki masalada chiziqli funktsiyaning maksimal qiymati qidirilsa, unda cheklovlar tizimining barcha tengsizliklari ko'rinishga keltiriladi.<=", а если минимум – к виду ">=". Ushbu talab bajarilmagan tengsizliklar uchun -1 ga ko'paytiriladi.

2. O'zgaruvchilar uchun koeffitsientlar matritsasi, cheklovlar tizimining bo'sh a'zolari ustuni va chiziqli funksiyadagi o'zgaruvchilar uchun koeffitsientlar qatorini o'z ichiga olgan A tizimning kengaytirilgan matritsasi tuzing.

3. A matritsaga ko‘chirilgan matritsani toping .

4. Olingan matritsa asosida ikkilamchi masalani tuzing va o‘zgaruvchilarning manfiy bo‘lmasligi shartlari: o‘zgaruvchilarning koeffitsientlari sifatida dastlabki masala cheklovlar tizimining erkin a’zolarini olib, dual masalaning maqsad funksiyasini tashkil qiladi; matritsa elementlarini o‘zgaruvchilarning koeffitsientlari sifatida va boshlang‘ich masalaning maqsad funksiyasidagi o‘zgaruvchilarning koeffitsientlarini erkin a’zolar sifatida olib, dual masala bo‘yicha cheklovlar tizimini tuzing va qarama-qarshi ma’noli tengsizliklarni yozing; dual masala o'zgaruvchilari manfiy emaslik shartini yozing.

12. Birinchi duallik teoremasi

Ikkilik masalalarning optimal yechimlari orasidagi bog'lanish ikkilik teoremalari yordamida o'rnatiladi.

Optimallikning etarli belgisi.

Agar X*=(x1*,x2*,…,xn*) Va Y*=(y1*,y2*,…,ym*) tenglik mavjud bo'lgan o'zaro ikki tomonlama muammolarning maqbul echimlari;

u holda I asl masalaning optimal yechimi bo‘lib, ikki tomonlama masala II ning optimal yechimi hisoblanadi.

O'zaro ikki tomonlama muammolarning optimalligi uchun etarli mezondan tashqari, ularning echimlari o'rtasida boshqa muhim munosabatlar mavjud. Avvalo, savollar tug'iladi: har bir juftlik muammosi uchun har doim bir vaqtning o'zida optimal echim bormi; ikki tomonlama muammolardan birining yechimi bo'lsa, ikkinchisi yo'q. Bu savollarga quyidagi teorema orqali javob beriladi.

Birinchi (asosiy) duallik teoremasi. Agar o'zaro ikkilamchi masalalardan biri optimal echimga ega bo'lsa, ikkinchisi ham shunday bo'ladi va ularning chiziqli funktsiyalarining optimal qiymatlari:

Fmax = Zmin yoki F(X*)=Z(Y*) .

Agar masalalardan birining chiziqli funksiyasi cheklanmagan bo‘lsa, ikkinchi masala shartlari qarama-qarshidir (muammoning yechimi yo‘q).

Izoh. Asosiy duallik teoremasining ikkinchi qismiga qarama-qarshi bo'lgan bayonot umumiy holatda to'g'ri emas, ya'ni. asl masala shartlari qarama-qarshi bo'lganligidan ikki tomonlama masalaning chiziqli funksiyasi chegaralanmagan degan xulosa kelib chiqmaydi.

Birinchi ikkilik teoremasining iqtisodiy ma'nosi.

Ishlab chiqarish rejasi X*=(x1*,x2*,…,xn*) va resurslar Y*=(y1*,y2*,…,ym*) narxlari (baholari) toʻplami. Agar "tashqi" (oldindan ma'lum) narxlarda c1,c2,...,cn bo'lgan mahsulotdan olingan foyda (daromad) "ichki" (aniqlangan)dagi resurslar narxiga teng bo'lsa, optimal bo'ladi. faqat masala yechimidan) narxlar y1 ,y2,…,ym. Boshqa barcha rejalar uchun X Va Y ikkala vazifa, mahsulotdan olingan foyda (daromad) har doim resurslarning narxidan kam (yoki teng).

Birinchi ikkilik teoremasining iqtisodiy ma'nosini ham quyidagicha izohlash mumkin: korxona optimal reja bo'yicha mahsulot ishlab chiqarish X*=(x1*,x2*,…,xn*) va maksimal foyda olish ( daromad) Fmax yoki resurslarni optimal narxlarda sotish Y* =(y1*,y2*,…,ym*) va unga teng bo'lgan sotishdan Zmin resurslarining minimal qiymatini qoplash.

13. Ikkinchi duallik teoremasi

Ikkita o'zaro ikkilamchi masala berilsin. Agar bu masalalarning har biri simpleks usuli bilan yechilsa, ularni kanonik shaklga keltirish kerak, buning uchun I muammoning cheklanishlar tizimiga kiritish kerak (qisqacha belgi). T manfiy bo'lmagan o'zgaruvchilar, lekin II muammoning cheklovlar tizimiga () – n manfiy bo'lmagan o'zgaruvchilar, bu erda i (j) - qo'shimcha o'zgaruvchi kiritilgan tengsizliklar soni.

O'zaro ikki tomonlama muammolarning har biri uchun cheklovlar tizimi quyidagi shaklda bo'ladi:

Ikkilamchi masalalardan birining boshlang‘ich o‘zgaruvchilari bilan boshqa masala (jadval)ning qo‘shimcha o‘zgaruvchilari o‘rtasida muvofiqlikni o‘rnatamiz.

Teorema. O'zaro ikkilamchi masalalardan birining optimal yechimining ijobiy (noldan farqli) komponentlari boshqa muammoning optimal yechimining nol komponentlariga mos keladi, ya'ni. har qanday i=1,2,…,m u j=1,2,…,n uchun: agar X*j>0 bo‘lsa, u holda; Agar , keyin va shunga o'xshash,

agar, keyin ; agar, keyin.

Ushbu teoremadan muhim xulosa kelib chiqadiki, o'zaro ikkilamchi masalalarning o'zgaruvchilari optimalga erishilganda (ya'ni, har bir masalani simpleks usuli bilan hal qilishning oxirgi bosqichida) kiritilgan muvofiqlik o'rtasidagi muvofiqlikni ifodalaydi. asosiy(qoida tariqasida, nolga teng emas) ikki tomonlama muammolardan birining o'zgaruvchilari va asosiy bo'lmagan(nolga teng) boshqa muammoning o'zgaruvchilari, ular ruxsat etilgan asosiy echimlarni hosil qilganda.

Ikkinchi duallik teoremasi. Ikkilamchi masalani optimal yechish komponentlari uning optimal yechimining kichik o‘zgaruvchilari bilan ifodalangan asl muammoning chiziqli funksiyasining mos o‘zgaruvchilaridagi koeffitsientlarning mutlaq qiymatlariga teng.

Izoh. Agar o'zaro ikkilamchi masalalardan birida optimal yechimning o'ziga xosligi buzilgan bo'lsa, u holda ikki tomonlama masalaning optimal echimi degenerativ hisoblanadi. Buning sababi shundaki, agar dastlabki masalaning optimal yechimining yagonaligi buzilgan bo'lsa, uning optimal echimining chiziqli funktsiyasini asosiy bo'lmagan o'zgaruvchilar nuqtai nazaridan ifodalashda asosiy o'zgaruvchilardan kamida bittasi etishmaydi.

14. Ob'ektiv aniqlangan baholar va ularning ma'nosi

Ikkilamchi masalani optimal yechish komponentlari dastlabki masalaning optimal (ikki tomonlama) baholari deyiladi. Akademik L.V.Kantorovich ularni chaqirdi ob'ektiv ravishda shartlangan taxminlar ( adabiyotda ular yashirin daromad deb ham ataladi) .

S1, S2, S3, S4 resurslari zaxiralari o'rtasidagi farqni ifodalovchi asl muammo I ning qo'shimcha o'zgaruvchilari va ularning iste'moli, ifoda qolgan resurslar , va ulardan mahsulot birligini ishlab chiqarish uchun resurslar xarajatlari va P1, P2 mahsulotlarning cj narxlari o'rtasidagi farqni ifodalovchi ikki tomonlama muammoning II qo'shimcha o'zgaruvchilari. , ifodalash narxdan ortiqcha xarajat.

Shunday qilib, resurslarning ob'ektiv aniqlangan baholari resurslarning tanqislik darajasini belgilaydi: optimal ishlab chiqarish rejasiga ko'ra, kam (ya'ni, to'liq foydalanilgan) resurslar nolga teng bo'lmagan baholarni oladi va kam bo'lmagan - nolga teng. y*i qiymati i-resursning taxminidir. Smeta y*i qiymati qanchalik yuqori bo'lsa, resursning tanqisligi shunchalik yuqori bo'ladi. Kam bo'lmagan resurs uchun y*i=0.

Demak, optimal ishlab chiqarish rejasiga faqat tejamkor, norentabel mahsulot turlari tushishi mumkin (garchi bu erda rentabellik mezoni o'ziga xos bo'lsa-da: mahsulot narxi uni ishlab chiqarishda iste'mol qilingan resurslar xarajatlaridan oshmaydi, lekin to'liq tengdir. ularga).

Uchinchi duallik teoremasi . Ikki tomonlama muammoning optimal yechimining komponentlari chiziqli funktsiyaning qisman hosilalari qiymatlariga teng. Fmax(b1, b2,…, bm)tegishli dalillarga ko'ra, ya'ni.

Resurslarning ob'ektiv ravishda aniqlangan baholari tegishli resurs zaxirasi bir birlikka o'zgarganda mahsulot sotishdan maksimal foyda (daromad) qancha pul birligiga o'zgarishini ko'rsatadi.

Ikki tomonlama hisob-kitoblar doimiy o'zgarib turadigan sohada tahlil qilish va to'g'ri qarorlar qabul qilish uchun vosita bo'lib xizmat qilishi mumkin. Shunday qilib, masalan, resurslarning ob'ektiv aniqlangan baholari yordamida optimal shartli xarajatlar va ishlab chiqarish natijalarini taqqoslash mumkin.

Resurslarning ob'ektiv ravishda aniqlangan baholari har qanday emas, balki resurslardagi nisbatan kichik o'zgarishlarning ta'sirini baholashga imkon beradi. To'satdan o'zgarishlar bilan hisob-kitoblarning o'zi boshqacha bo'lishi mumkin, bu esa ularni ishlab chiqarish samaradorligini tahlil qilish uchun ishlatishning mumkin emasligiga olib keladi. Ob'ektiv ravishda aniqlangan hisob-kitoblar nisbatlariga ko'ra, resurslarni almashtirishning hisoblangan me'yorlari aniqlanishi mumkin, bunda ikki tomonlama hisob-kitoblarning barqarorligi doirasida amalga oshirilayotgan almashtirishlar optimal rejaning samaradorligiga ta'sir qilmaydi. Xulosa. Ikkilik ballar quyidagilar:

1. Resurslar va mahsulotlar tanqisligi ko'rsatkichi.

2. Maqsad funksiyasi qiymatiga cheklovlarning ta'siri ko'rsatkichi.

3. Optimallik mezoni nuqtai nazaridan ayrim turdagi mahsulotlarni ishlab chiqarish samaradorligi ko'rsatkichi.

4. Umumiy shartli xarajatlar va natijalarni solishtirish vositasi.

15. Narx mezoniga ko'ra transport vazifasini bayon qilish.

TK - bir hil yoki almashtiriladigan mahsulotni ishlab chiqarish punktidan (jo'nash stantsiyalari) iste'mol punktlariga (maqsad stantsiyalari) tashishning eng tejamkor rejasi muammosi - LPning eng muhim shaxsiy vazifasi bo'lib, u keng amaliy qo'llanmalarga ega emas. faqat transport muammolari uchun.

TK LPda iqtisodiy tavsiflarning aniqligi, matematik modelning xususiyatlari, yechimning o'ziga xos usullari mavjudligi bilan ajralib turadi.

Xarajatlar bo'yicha TORning eng oddiy formulasi quyidagicha: in T jo'nash nuqtalari A1,…,Am mos ravishda a1,…,am yetkazib beriladigan bir hil yuk (resurslar) birliklaridir. n iste'molchilar B1,…,Bn b1,…,bn miqdorida birlik (ehtiyojlar). Yuk birligini i-chi jo'natish nuqtasidan j-nchi iste'mol nuqtasigacha tashish uchun Cij transport xarajatlari ma'lum.

Tashish rejasini tuzish, ya'ni i-chi jo'nash nuqtasidan j-iste'mol punktiga qancha birlik yuk jo'natilishi kerakligini topish kerak, shunda ehtiyojlar to'liq qondirilsin va yuklar to'liq qondirilsin. umumiy transport xarajatlari minimaldir.

Aniqlik uchun TK shartlari jadval shaklida taqdim etiladi, bu esa deyiladi tarqatish .

Provayder	Iste'molchi			Yuk zaxirasi
Kerak

Bu yerda i-chi kelib chiqish nuqtasidan j-barelgigacha tashilgan yuk miqdori xij ga teng, i-chi jo‘natish nuqtasidagi yuk zaxirasi ai>=0 qiymati bilan aniqlanadi. j-chi manzilning yukdagi talabi bj>=0 ga teng. Barcha xij>=0 deb faraz qilinadi.

Matritsa deyiladi tarif matritsasi (xarajatlar yoki transport xarajatlari).

Transport vazifasi rejasi matritsa deb ataladi, bunda har bir xij raqami i-chi jo‘nash nuqtasidan j-chi manzilga yetkazilishi kerak bo‘lgan yuk birliklari sonini bildiradi. xij matritsasi deyiladi trafik matritsasi.

Tashish rejasini amalga oshirish bilan bog'liq umumiy umumiy xarajatlar maqsad funktsiyasi bilan ifodalanishi mumkin

Xij o'zgaruvchilari zaxiralar, iste'molchilar va salbiy bo'lmaganlik shartlariga cheklovlarni qondirishi kerak:

– aktsiyalarga cheklovlar (2);

– iste’molchilarga nisbatan cheklovlar (2);

manfiy bo'lmagan holatlardir (3).

Shunday qilib, matematik jihatdan transport masalasi quyidagicha tuzilgan. (3) shartdagi cheklovlar tizimi (2) va maqsad funksiyasi (1) berilgan. (2) sistemaning yechimlar to'plamidan (1) funktsiyani minimallashtiradigan manfiy bo'lmagan yechimni topish talab etiladi.

(1) - (3) masala uchun cheklovlar tizimi m + n tenglamani o'z ichiga oladi Tn o'zgaruvchilar. Jami zaxiralar umumiy ehtiyojlarga teng deb taxmin qilinadi, ya'ni.

16. Transport muammosining echilishi belgisi

Transport muammosining maqbul rejalari bo'lishi uchun tenglik zarur va etarli

Ikki turdagi transport vazifalari mavjud: yopiq , bunda yetkazib beruvchilar yuklarining umumiy hajmi iste'molchilarning umumiy talabiga teng bo'ladi va ochiq , bunda etkazib beruvchilarning umumiy ishlab chiqarish quvvati iste'molchilar talabidan oshib ketadi yoki iste'molchilar talabi etkazib beruvchilarning haqiqiy umumiy quvvatidan kattaroq bo'ladi, ya'ni.

Ochiq model yopiq modelga aylantirilishi mumkin. Demak, agar, u holda transport masalasining matematik modeliga xayoliy (n + 1)-chi maqsad kiritiladi. Buning uchun topshiriqlar matritsasida qo'shimcha ustun taqdim etiladi, buning uchun ehtiyoj etkazib beruvchilarning umumiy quvvati va iste'molchilarning haqiqiy talabi o'rtasidagi farqga teng:

Ushbu nuqtaga tovarlarni etkazib berish bo'yicha barcha tariflar nolga teng deb hisoblanadi. Shunday qilib, masalaning ochiq modeli yopiq modelga aylanadi. Yangi muammo uchun maqsad funktsiyasi har doim bir xil bo'ladi, chunki qo'shimcha tashish narxi nolga teng. Boshqacha qilib aytganda, xayoliy iste'molchi cheklash tizimining izchilligini buzmaydi.

Agar, u holda xayoliy (m + 1)-chi jo'nash nuqtasi kiritilgan bo'lsa, unga teng yuk zaxirasi tegishli.

Ushbu soxta etkazib beruvchidan tovarlarni etkazib berish uchun tariflar yana nolga teng deb qabul qilinadi. Matritsaga bitta qator qo'shiladi, bu maqsad funktsiyasiga ta'sir qilmaydi va masalaning cheklovlar tizimi mos keladi, ya'ni optimal rejani topish mumkin bo'ladi.

Transport muammosi uchun quyidagi teorema katta ahamiyatga ega.

Teorema. Transport muammosi matritsasining darajasi tenglamalar sonidan bir kam, ya'ni. r ( a )= m + n -1.

Teoremadan kelib chiqadiki, har bir etalon dizayn nolga teng (m-1)(n-1) erkin o'zgaruvchilarga va m+n-1 asosiy o'zgaruvchilarga ega bo'lishi kerak.

Biz transport vazifasini tashish rejasini to'g'ridan-to'g'ri tarqatish jadvalida qidiramiz. Faraz qilamizki, agar xij o'zgaruvchisi qiymat oladigan bo'lsa, u holda bu qiymatni mos keladigan katakka (I,j) yozamiz, lekin agar xij=0 bo'lsa, u holda (I,j) katakchani bo'sh qoldiramiz. Tarqatish jadvalidagi matritsaning darajasi haqidagi teoremani hisobga olgan holda bosh rejani o'z ichiga olishi kerak m+n-1 egallagan hujayralar qolganlari esa bepul bo'ladi.

Asosiy reja uchun bu talablar yagona emas. Asosiy rejalar tsikllar bilan bog'liq boshqa talabni qondirishi kerak.

Ikki va faqat ikkita qo'shni katak bir qatorda yoki bitta ustunda joylashgan va to'plamning oxirgi katagi birinchisi bilan bir xil satr yoki ustunda joylashgan trafik matritsasi kataklari to'plami yopiq deyiladi. tsikl .

Grafik jihatdan sikl yopiq siniq chiziq bo'lib, uning uchlari jadvalning egallangan kataklarida, bog'lanishlari esa faqat satr yoki ustunlarda joylashgan. Bundan tashqari, tsiklning har bir cho'qqisida aniq ikkita havola mavjud, ulardan biri qatorda, ikkinchisi esa ustunda. Agar tsiklni tashkil etuvchi poliliniya o'zini kesib o'tsa, u holda o'z-o'zidan kesishish nuqtalari cho'qqilar emas.

Tashish vazifalari rejalarining quyidagi muhim xususiyatlari tsikl hujayralari to'plami bilan bog'liq:

1) transport vazifasining ruxsat etilgan rejasi, agar ushbu reja egallagan hujayralardan tsikl hosil bo'lmasa, ma'lumotnoma hisoblanadi;

2) agar bizda asosiy reja bo'lsa, unda har bir bo'sh hujayra uchun ushbu hujayra va egallangan hujayralarning bir qismini o'z ichiga olgan faqat bitta tsikl hosil qilish mumkin.

17. Dastlabki bazani qurish

Shimoli-g'arbiy burchak qoidasi.

Dastlabki tashish rejasini tuzish uchun shimoli-g'arbiy burchak qoidasidan foydalanish qulay, bu quyidagicha.

Biz to'ldiramiz, yuqori chapdan boshlab, shartli ravishda "shimoli-g'arbiy burchak" deb ataladi, chiziq bo'ylab ustundan o'ngga yoki pastga siljiydi. Yacheykaga (1; 1) a1 va b1 raqamlaridan kichikroqini qo'yamiz, ya'ni. Agar birinchi ustun "yopiq" bo'lsa, ya'ni birinchi iste'molchining talabi to'liq qondiriladi. Bu shuni anglatadiki, birinchi ustunning boshqa barcha hujayralari uchun yuk miqdori .

Agar bo'lsa, unda birinchi qator xuddi shunday "yopiq", ya'ni uchun . Biz kiradigan qo'shni katakchani (2; 1) to'ldirishni davom ettiramiz.

Ikkinchi katakchani (1; 2) yoki (2; 1) to'ldirgandan so'ng, biz ikkinchi qatordagi yoki ikkinchi ustundagi keyingi uchinchi katakchani to'ldirishga o'tamiz. Biz bu jarayonni qaysidir bosqichda resurslar va ehtiyojlar tugaguncha davom ettiramiz. Oxirgi to'ldirilgan katak oxirgi n-ustunda va oxirgi m-chi qatorda bo'ladi.

"Minimal element" qoidasi.

"Shimoliy-g'arbiy burchak" qoidasi bo'yicha qurilgan dastlabki ma'lumot rejasi odatda optimaldan juda uzoq bo'lib chiqadi, chunki uni aniqlashda cij xarajatlari hisobga olinmaydi. Shuning uchun, keyingi hisob-kitoblarda optimal rejaga erishish uchun ko'p takrorlash kerak bo'ladi. Dastlabki reja "minimal element" qoidasiga muvofiq qurilgan bo'lsa, takrorlashlar sonini kamaytirish mumkin. Uning mohiyati shundan iboratki, har bir bosqichda yukning hujayra ichiga maksimal mumkin bo'lgan "harakati" cij minimal tarifi bilan amalga oshiriladi. Jadvalni hujayradan to'ldirishni boshlaymiz, bu tarif matritsasining eng kichik elementi cij ga to'g'ri keladi. ai yoki bj raqamlarining eng kichigi eng past tarifli katakka joylashtiriladi . Keyinchalik, zaxiralari to'liq tugagan yetkazib beruvchiga tegishli qator yoki talabi to'liq qondirilgan iste'molchiga mos keladigan ustun ko'rib chiqilmaydi. Ma'lum bo'lishicha, agar etkazib beruvchining inventarizatsiyasi to'liq tugagan va iste'molchining talabi to'liq qondirilgan bo'lsa, bir vaqtning o'zida qator va ustunni chiqarib tashlash kerak. Keyin jadvalning qolgan kataklaridan eng past tarifga ega katak yana tanlab olinadi va ularning hammasi taqsimlanib, talab qondirilgunga qadar zaxiralarni taqsimlash jarayoni davom etadi.

18. Potensiallar usuli

Potensial usul bo'yicha transport vazifasining optimal rejasini aniqlashning umumiy printsipi LP muammosini simpleks usuli bilan hal qilish printsipiga o'xshaydi, ya'ni: birinchi navbatda, transport vazifasining asosiy rejasi topiladi, keyin esa u ketma-ket amalga oshiriladi. optimal reja olinmaguncha yaxshilanadi.

Potensial usulning mohiyati quyidagicha. Dastlabki ma'lumotnoma tashish rejasi topilgandan so'ng, har bir etkazib beruvchiga (har bir qatorga) etkazib beruvchining potentsiali deb ataladigan ma'lum bir raqam beriladi Ai , va har bir iste'molchiga (har bir ustunga) iste'molchining salohiyati deb ataladigan ma'lum bir raqam beriladi.

Bir punktda bir tonna yukning narxi tashishgacha bo'lgan tonna yuk narxiga + uni tashish narxiga teng: .

Transport muammosini potentsial usul bilan hal qilish uchun quyidagilar zarur:

1. Belgilangan qoidalardan biriga muvofiq asosiy transport rejasini tuzing. To'ldirilgan katakchalar soni m+n-1 bo'lishi kerak.

2. Potensiallarni va mos ravishda etkazib beruvchilar va iste'molchilarni hisoblang (band hujayralar uchun): . To'ldirilgan katakchalar soni m+n-1, tenglamalar soni esa m+n. Chunki tenglamalar soni noma'lumlar sonidan bitta kam bo'lsa, noma'lumlardan biri bo'sh bo'lib, istalgan raqamli qiymatni qabul qilishi mumkin. Masalan, . Berilgan mos yozuvlar yechimi uchun qolgan potentsiallar yagona aniqlanadi.

3. Optimallikni tekshiring, ya'ni. bepul hujayralar uchun ballarni hisoblash. Agar, u holda transport maqsadga muvofiq va X rejasi optimal bo'lsa - optimallik belgisi. Agar kamida bitta farq bo'lsa, unda yangi mos yozuvlar rejasiga o'ting. Iqtisodiy ma'noda qiymat i-chi yetkazib beruvchi tomonidan j-iste'molchiga yagona etkazib berishni amalga oshirish natijasida yuzaga keladigan umumiy transport xarajatlarining o'zgarishini tavsiflaydi. Agar bitta etkazib berish transport xarajatlarini tejashga olib keladi, agar - ularning ko'payishiga olib keladi. Shuning uchun, agar etkazib berishning bepul yo'nalishlari orasida transport xarajatlarini tejaydigan yo'nalishlar bo'lmasa, natijada olingan reja optimal hisoblanadi.

4. Ijobiy raqamlar orasida maksimal tanlanadi, bepul hujayra uchun qurilgan, u qayta hisoblash davriga mos keladi. Tanlangan bo'sh hujayra uchun tsikl qurilgandan so'ng, siz yangi mos yozuvlar rejasiga o'tishingiz kerak. Buni amalga oshirish uchun siz ushbu bo'sh hujayra bilan bog'liq bo'lgan hujayralar ichidagi yuklarni qayta hisoblash tsikli bilan ko'chirishingiz kerak.

a) Berilgan erkin hujayra bilan sikl orqali bog'langan hujayralarning har biriga ma'lum bir belgi beriladi va bu erkin hujayra "+" va boshqa barcha hujayralar (tsikl cho'qqilari) navbat bilan "-" va "+" belgilaridir. . Biz bu hujayralarni minus va plyus deb ataymiz.

b) Tsiklning minus kataklarida biz bilan belgilagan minimal ta'minotni topamiz. Manfiy kataklardagi xij sonlarning kichigi shu erkin hujayraga o'tkaziladi. Shu bilan birga, bu raqam "+" belgisi bilan hujayralardagi mos keladigan raqamlarga qo'shiladi va minus katakchalardagi raqamlardan chiqariladi. Ilgari bo'sh bo'lgan hujayra band bo'ladi va mos yozuvlar rejasiga kiradi; va xij sonlarining minimali turgan minus katak bepul hisoblanadi va mos yozuvlar rejasini tark etadi.

Shunday qilib, yangi baza belgilandi. Yuqorida tavsiflangan bir asosiy chiziqdan ikkinchisiga o'tish qayta hisoblash siklining siljishi deb ataladi. Qayta hisoblash tsikli bo'ylab siljishda, egallangan hujayralar soni o'zgarishsiz qoladi, ya'ni u m+n-1 ga teng bo'lib qoladi. Bundan tashqari, agar minus kataklarda ikki yoki undan ortiq bir xil xij sonlar mavjud bo'lsa, unda bu hujayralardan faqat bittasi bo'shatiladi, qolganlari esa nol zaxira bilan band bo'ladi.

5. Olingan mos yozuvlar rejasi optimalligi uchun tekshiriladi, ya'ni. 2-banddagi barcha amallarni takrorlang.

19. Dinamik dasturlash tushunchasi.

DP (rejalashtirish) - ko'p bosqichli (ko'p bosqichli) masalalarning optimal echimlarini topishning matematik usuli. Ushbu muammolarning ba'zilari tabiiy ravishda alohida bosqichlarga (bosqichlarga) bo'linadi, ammo DP usuli bilan hal qilish uchun bo'limni sun'iy ravishda kiritish kerak bo'lgan muammolar mavjud.

Odatda, DP usullari ba'zi boshqariladigan tizimlarning ishlashini optimallashtiradi, ularning ta'siri baholanadi qo'shimcha, yoki multiplikativ, maqsad funktsiyasi. Qo'shimcha qiymati faqat bitta xj o'zgaruvchiga bog'liq bo'lgan ba'zi fj funksiyalar yig'indisi sifatida hisoblangan bir necha o'zgaruvchilarning f(x1,x2,…,xn) funktsiyasidir: . Qo'shimcha maqsad funktsiyasining shartlari boshqariladigan jarayonning alohida bosqichlarida qabul qilingan qarorlarning ta'siriga mos keladi.

R. Bellmanning optimallik tamoyili.

Dinamik dasturlashda qo'llaniladigan yondashuvning ma'nosi dastlabki ko'p o'lchovli muammoning echimini pastki o'lchamdagi muammolar ketma-ketligi bilan almashtirishdan iborat. Vazifalar uchun asosiy talablar:

1. tadqiqot ob'ekti bo'lishi kerak boshqariladigan tizim (ob'ekt) berilgan amal bilan davlatlar va ruxsat etiladi bo'limlari;

2. topshiriq ko'p bosqichli jarayon sifatida talqin qilishga imkon berishi kerak, uning har bir bosqichi qabul qilishdan iborat yechimlar O olib boradigan ruxsat etilgan nazorat vositalaridan birini tanlash davlat o'zgarishi tizimlar;

3. vazifa bosqichlar soniga bog'liq bo'lmasligi va ularning har biri bo'yicha aniqlanishi kerak;

4. har bir bosqichda tizimning holati bir xil (tarkibiy) parametrlar to'plami bilan tavsiflanishi kerak;

5. tizim yechimni tanlagandan so'ng o'zini topadigan keyingi holat k-chi qadam, faqat berilgan yechimga va boshlang'ich holatiga bog'liq k- qadam. Bu xususiyat dinamik dasturlash mafkurasi nuqtai nazaridan asosiy hisoblanadi va deyiladi oqibatlarning yo'qligi .

Dinamik dasturlash modelini umumlashtirilgan shaklda qo'llash masalalarini ko'rib chiqing. Turli holatlarda bo'lishi mumkin bo'lgan ba'zi mavhum ob'ektni boshqarish vazifasi bo'lsin. Ob'ektning hozirgi holati ma'lum parametrlar to'plami bilan aniqlanadi, ular S bilan belgilanadi va chaqiriladi. davlat vektori. Barcha mumkin bo'lgan holatlarning S to'plami berilgan deb taxmin qilinadi. To'plam ob'ekt uchun ham aniqlanadi ruxsat etilgan nazorat(nazorat harakatlari) x, umumiylikni yo'qotmasdan, sonli to'plam deb hisoblanishi mumkin. Nazorat harakatlari vaqtning diskret nuqtalarida va nazorat qilishda amalga oshirilishi mumkin yechim boshqaruv elementlaridan birini tanlashdan iborat. reja vazifalar yoki boshqaruv strategiyasi x=(x1,x2,…,xn-1) vektor chaqiriladi, uning komponentlari jarayonning har bir bosqichida tanlangan boshqaruv elementlari hisoblanadi. Kutilganlarni hisobga olgan holda keyingi ta'sirning yo'qligi Sk va Sk+1 ob'ektining har ikki ketma-ket holati o'rtasida ma'lum funktsional bog'liqlik mavjud bo'lib, u tanlangan boshqaruvni ham o'z ichiga oladi: . Shunday qilib, ob'ektning dastlabki holatini o'rnatish va rejani tanlash X o'ziga xos tarzda belgilaydi xatti-harakatlarning traektoriyasi ob'ekt.

Har bir qadamda boshqaruv samaradorligi k joriy Sk holatiga, tanlangan boshqaruv xk ga bog'liq va yig'indisi bo'lgan fk(xk,Sk) funksiyalari yordamida miqdoriy aniqlanadi. qo'shimcha maqsad funktsiyasi , ob'ektni boshqarishning umumiy samaradorligini tavsiflovchi. ( Eslatma , fk(xk,Sk) funksiyaning ta'rifi ruxsat etilgan qiymatlar oralig'ini o'z ichiga oladi xk , va bu maydon, qoida tariqasida, Sk ning hozirgi holatiga bog'liq). Optimal nazorat , berilgan dastlabki holat uchun S1, shunday optimal rejani tanlashga qisqartiradi x* , qaysi vaqtda maksimal miqdor mos keladigan traektoriya bo'yicha fk qiymatlari.

Dinamik dasturlashning asosiy printsipi shundan iboratki, har bir qadamda fk(xk,Sk) funksiyasini izolyatsiya qilingan optimallashtirishga intilmay, keyingi barcha bosqichlar optimal deb faraz qilingan holda optimal boshqaruv x*k ni tanlash kerak. Rasmiy ravishda, bu tamoyil har bir qadamda topish orqali amalga oshiriladi k shartli optimal boshqaruvlar , joriy holat S deb faraz qilgan holda, ushbu bosqichdan boshlab eng yuqori umumiy samaradorlikni ta'minlaydi.

fk funksiyalar yig‘indisining maksimal qiymatini Zk(lar) bilan belgilang dan qadamlar davomida k oldin P(jarayonning berilgan segmentida optimal nazorat ostida olingan), ob'ekt qadam boshida bo'lishi sharti bilan k S holatda bo'ladi. U holda Zk(lar) funksiyalar rekursiv munosabatni qanoatlantirishi kerak:

Bu nisbat deyiladi asosiy takrorlanish munosabati (asosiy funktsional tenglama) dinamik dasturlash. U dinamik dasturlashning asosiy printsipini amalga oshiradi, shuningdek, deb nomlanadi Bellmanning optimallik printsipi :

Optimal boshqaruv strategiyasi quyidagi shartlarga javob berishi kerak: boshlang'ich holati qanday bo'lishidan qat'iy nazar sk k-bosqichda va bu bosqichda tanlangan boshqaruv xk, keyingi nazorat (boshqaruv qarorlari) nisbatan optimal bo'lishi kerak kokmo yanyu ,k bosqichida qabul qilingan qarordan kelib chiqadi .

Asosiy munosabat Zk(lar) funksiyalarini topishga imkon beradi. faqat V bilan birlashtirilgan boshlang'ich holati bu bizning holatlarimizda tenglikdir.

Yuqorida tavsiflangan optimallik printsipi faqat optimal boshqaruvni tanlash boshqariladigan jarayonning tarixiga, ya'ni tizimning hozirgi holatga kelganiga bog'liq bo'lmagan boshqaruv ob'ektlariga nisbatan qo'llaniladi. Aynan shu holat muammoni tahlil qilish va uni amaliy hal qilish imkonini beradi.

Har bir aniq vazifa uchun funktsional tenglama o'zining o'ziga xos shakliga ega, ammo u (*) ifodasiga xos bo'lgan va optimallik printsipining asosiy g'oyasini o'zida mujassam etgan takroriy tabiatni saqlab qolishi kerak.

20. O'yin modellari haqida tushuncha.

Konfliktli vaziyatning matematik modeli deyiladi o'yin , mojaroda ishtirok etgan tomonlar futbolchilar va mojaroning natijasi g'alaba qozonish.

Har bir rasmiylashtirilgan o'yin uchun biz tanishtiramiz qoidalar , bular. Quyidagilarni belgilovchi shartlar tizimi: 1) o'yinchilarning harakatlari variantlari; 2) har bir o'yinchi sheriklarning xatti-harakatlari haqida ma'lumot miqdori; 3) har bir harakat to'plami olib keladigan foyda. Odatda, daromad (yoki yo'qotish) miqdoriy jihatdan aniqlanishi mumkin; masalan, mag'lubiyatni nolga, g'alabani bittaga va durangni 1/2 ga baholashingiz mumkin. O'yin natijalarini hisoblash deyiladi to'lov .

O'yin deyiladi bug 'xonasi , ikki futbolchi ishtirok bor bo'lsa, va bir nechta , agar o'yinchilar soni ikkitadan ko'p bo'lsa. Biz faqat juftlashgan o'yinlarni ko'rib chiqamiz. Ularni ikkita o'yinchi o'ynaydi A Va IN, manfaatlari qarama-qarshi bo'lgan va o'yin deganda biz bir qator harakatlarni nazarda tutamiz A Va IN.

O'yin deyiladi nol summali o'yin yoki antagonistik skoy , agar o'yinchilardan birining daromadi ikkinchisining yo'qotishiga teng bo'lsa, ya'ni. har ikki tomonning to'lovlari yig'indisi nolga teng. O'yin vazifasini bajarish uchun ulardan birining qiymatini ko'rsatish kifoya . Agar belgilasak A- o'yinchilardan birini g'alaba qozonish, b – boshqasining to'lovi, keyin nol summali o'yin uchun b= –A, shuning uchun, masalan, hisobga olish kifoya A.

Qoidalarda nazarda tutilgan harakatlardan birini tanlash va amalga oshirish deyiladi harakat futbolchi. Harakatlar bo'lishi mumkin shaxsiy Va tasodifiy . shaxsiy harakat – bu o'yinchining mumkin bo'lgan harakatlardan birini ongli ravishda tanlashi (masalan, shaxmat o'yinidagi harakat). Har bir shaxsiy harakat uchun mumkin bo'lgan variantlar to'plami o'yin qoidalari bilan tartibga solinadi va ikkala tomonning oldingi harakatlarining umumiyligiga bog'liq.

Tasodifiy harakat – bu tasodifiy tanlangan harakat (masalan, aralashgan palubadan kartani tanlash). O'yin matematik tarzda aniqlanishi uchun o'yin qoidalari har bir tasodifiy harakat uchun belgilanishi kerak ehtimollik taqsimoti mumkin bo'lgan natijalar.

Ba'zi o'yinlar faqat tasodifiy harakatlardan (sof tasodif o'yinlari deb ataladi) yoki faqat shaxsiy harakatlardan (shaxmat, shashka) iborat bo'lishi mumkin. Ko'pgina karta o'yinlari aralash turdagi o'yinlarga tegishli, ya'ni ular tasodifiy va shaxsiy harakatlarni o'z ichiga oladi. Keyingi gaplarda faqat futbolchilarning shaxsiy harakatlarini ko'rib chiqamiz.

O'yinlar nafaqat harakatlarning tabiati (shaxsiy, tasodifiy), balki har bir o'yinchi uchun boshqasining harakatlariga oid ma'lumotlarning tabiati va miqdori bo'yicha ham tasniflanadi. O'yinlarning maxsus klassi "to'liq ma'lumotga ega o'yinlar" deb ataladi. To'liq ma'lumotga ega o'yin O'yin deyiladi, unda har bir o'yinchi har bir shaxsiy harakatdagi barcha oldingi harakatlar natijalarini biladi, ham shaxsiy, ham tasodifiy. To'liq ma'lumotga ega bo'lgan o'yinlarga misol qilib, shaxmat, shashka va taniqli tic-tac-toe o'yinlarini keltirish mumkin. Amaliy ahamiyatga ega bo'lgan aksariyat o'yinlar to'liq ma'lumotga ega bo'lgan o'yinlar sinfiga kirmaydi, chunki raqibning harakatlari to'g'risida noma'lum narsa odatda ziddiyatli vaziyatlarning muhim elementi hisoblanadi.

O'yin nazariyasining asosiy tushunchalaridan biri kontseptsiyadir strategiyalar .

strategiya O'yinchi vaziyatga qarab har bir shaxsiy harakat uchun uning harakatini tanlashni belgilaydigan qoidalar to'plami deb ataladi. Odatda o'yin davomida har bir shaxsiy harakatda o'yinchi muayyan vaziyatga qarab tanlov qiladi. Biroq, printsipial jihatdan, barcha qarorlar o'yinchi tomonidan oldindan qabul qilinishi mumkin (har qanday vaziyatga javoban). Bu o'yinchi qoidalar ro'yxati yoki dastur shaklida berilishi mumkin bo'lgan ma'lum strategiyani tanlaganligini anglatadi. (Shunday qilib, siz o'yinni kompyuter yordamida o'ynashingiz mumkin). O'yin deyiladi yakuniy , agar har bir o'yinchida cheklangan miqdordagi strategiyalar mavjud bo'lsa va cheksiz .– aks holda.

Uchun qaror o'yin , yoki toping o'yin qarori , har bir o'yinchi shartni qondiradigan strategiyani tanlashi kerak optimallik , bular. o'yinchilardan biri qabul qilishi kerak maksimal g'alaba, ikkinchi o'z strategiyasiga yopishib qachon, Shu bilan birga, ikkinchi futbolchi bo'lishi kerak minimal yo'qotish , agar birinchisi o'z strategiyasiga rioya qilsa. Bunday strategiyalar deyiladi optimal . Optimal strategiyalar ham shartni qondirishi kerak barqarorlik , bular. bu o'yinda o'z strategiyasidan voz kechish har qanday o'yinchi uchun foydasiz bo'lishi kerak.

Agar o'yin etarlicha takrorlangan bo'lsa, o'yinchilar har bir o'yinda g'alaba qozonish va mag'lub bo'lishdan manfaatdor bo'lmasligi mumkin, A o'rtacha g'alaba (mag'lubiyat) barcha partiyalarda.

O'yin nazariyasining maqsadi har bir o'yinchi uchun optimal strategiyani aniqlashdir.

21. To'lov matritsasi. O'yinning pastki va yuqori narxi

O'yinchi ishtirok etadigan o'yinni tugating A Unda bor T strategiyalar va o'yinchi B - p strategiyalar m × n o'yini deb ataladi.

Ikki o'yinchining m × n o'yinini ko'rib chiqing A Va IN("biz" va "raqib").

O'yinchiga ruxsat bering A ega T shaxsiy strategiyalar, biz ularni A1, A2,…, Am bilan belgilaymiz. O'yinchiga ruxsat bering IN mavjud n shaxsiy strategiyalar, biz ularni B1, B2,…, Bn deb belgilaymiz.

Har bir tomon ma'lum strategiyani tanlashiga ruxsat bering; biz uchun bu Ai bo'ladi, raqib Bj uchun. O'yinchilarning Ai va Bj () har qanday strategiya juftligini tanlashi natijasida o'yin natijasi noyob tarzda aniqlanadi, ya'ni. aij o'yinchisini yutib oling A(ijobiy yoki salbiy) va o'yinchining yo'qolishi (-aij). IN.

Aytaylik, aij qiymatlari har qanday strategiyalar juftligi uchun ma'lum (Ai, Bj) . Matritsa P=aij , uning elementlari Ai va Bj strategiyalariga mos keladigan to'lovlardir; chaqirdi to'lov matritsasi yoki o'yin matritsasi. Ushbu matritsaning qatorlari o'yinchining strategiyalariga mos keladi A, va ustunlar o'yinchining strategiyalari B. Ushbu strategiyalar toza deb ataladi.

m×n o‘yin matritsasi quyidagi ko‘rinishga ega:

Matritsali m×n o‘yinini ko‘rib chiqing va A1, A2,…, Am strategiyalari orasida eng yaxshisini aniqlang. . O'yinchi uchun strategiyani tanlash A futbolchini kutish kerak IN unga o'yinchi uchun to'lov Bj strategiyalaridan biri bilan javob beradi A minimal (o'yinchi IN futbolchiga "zarar" berishga intiladi A).

O'yinchining eng kam to'lovi bilan belgilang A u o'yinchining barcha mumkin bo'lgan strategiyalari uchun Ai strategiyasini tanlaganida IN(eng kichik raqam i- to'lov matritsasining qatori), ya'ni.

Barcha raqamlar orasidan () eng kattasini tanlang: .

Qo'ng'iroq qilaylik o'yinning past narxi, yoki maksimal g'alaba (maksimal). Bu B o'yinchining har qanday strategiyasi uchun A o'yinchisining kafolatlangan to'lovidir. Demak,

Maksiminga mos keladigan strategiya deyiladi maksimal strategiya . O'yinchi IN futbolchining to'lovini kamaytirishdan manfaatdor A, Bj strategiyasini tanlab, u maksimal mumkin bo'lgan to'lovni hisobga oladi A. Belgilamoq

Barcha raqamlar orasida eng kichigini tanlang

va qo'ng'iroq qiling yuqori o'yin narxi yoki minimal to'lov(minimaks). Ego B o'yinchisini yo'qotishni kafolatladi. Shuning uchun,

Minimax strategiyasi deyiladi Minimax strategiyasi.

O'yinchilarga eng "ehtiyotkor" minimaks va maksimal strategiyalarni tanlashni talab qiladigan printsip deyiladi. Minimax printsipi . Bu tamoyil har bir o'yinchi raqibning qarama-qarshi maqsadiga erishishga intiladi, degan oqilona taxmindan kelib chiqadi.

Teorema. O'yinning past narxi hech qachon o'yinning yuqori narxidan oshmaydi. .

Agar o'yinning yuqori va pastki narxlari bir xil bo'lsa, o'yinning yuqori va pastki narxlarining umumiy qiymati deyiladi. o'yinning sof narxi, yoki o'yin narxi. O'yin narxiga mos keladigan minimaks strategiyalari optimal strategiyalar , va ularning umumiyligi optimal yechim yoki o'yin qarori. Bunday holda, o'yinchi A maksimal kafolatlangan (o'yinchining xatti-harakatidan qat'iy nazar) oladi. IN) g'alaba qozonish v, va o'yinchi IN kafolatlangan minimal darajaga erishadi (o'yinchining xatti-harakatidan qat'iy nazar). A) yo'qotish v. O'yinning yechimi borligi aytiladi barqarorlik , bular. agar o'yinchilardan biri o'zining optimal strategiyasiga sodiq qolsa, ikkinchisi uchun optimal strategiyasidan chetga chiqish foydali bo'lmaydi.

Agar o'yinchilardan biri (masalan A) uning optimal strategiyasiga yopishadi, va boshqa futbolchi (IN) har qanday tarzda o'zining optimal strategiyasidan chetga chiqadi, keyin og'ish qilgan futbolchi uchun, bu hech qachon foydali bo'lishi mumkin emas; o'yinchining bunday og'ishi IN eng yaxshi holatda daromadni o'zgarishsiz qoldirishi mumkin. va eng yomon holatda, uni oshiring.

Aksincha, agar IN uning optimal strategiyasiga rioya qiladi va A o'zidan chetga chiqsa, bu hech qanday tarzda foydali bo'lishi mumkin emas A.

Sof strategiyalar juftligi mos keladigan element bo'lsa, o'yin uchun maqbul echimni beradi ustunidagi eng kattasi ham, qatoridagi eng kichigi ham. Bunday vaziyat, agar mavjud bo'lsa, deyiladi Power Point. Geometriyada sirtdagi nuqta: bir koordinata bo'ylab bir vaqtning o'zida minimal va ikkinchisi bo'ylab maksimal xususiyatga ega bo'lgan nuqta deyiladi. kuch nuqta, analogiya bo'yicha bu atama o'yin nazariyasida qo'llaniladi.

Buning uchun o'yin , chaqirdi Power Point o'yini. Ushbu xususiyatga ega bo'lgan element matritsaning quvvat nuqtasidir.

Shunday qilib, quvvat nuqtasi bo'lgan har bir o'yin uchun har ikki tomon uchun bir juft optimal strategiyani aniqlaydigan yechim mavjud bo'lib, u quyidagi xususiyatlarda farqlanadi.

1) Agar ikkala tomon ham o'zlarining optimal strategiyalariga sodiq qolishsa, o'rtacha daromad o'yinning sof qiymatiga teng bo'ladi. v, bu uning ham past, ham yuqori narxidir.

2) Agar tomonlardan biri o‘zining optimal strategiyasiga amal qilsa, ikkinchisi esa o‘z strategiyasidan chetga chiqsa, u holda chetga chiqqan tomon bundan faqat yutqazishi mumkin va hech qanday holatda o‘z foydasini oshira olmaydi.

O'yin nazariyasida, xususan, to'liq ma'lumotga ega bo'lgan har bir o'yin kuch nuqtasiga ega ekanligi isbotlangan va shuning uchun har bir bunday o'yin yechimga ega, ya'ni bir tomon va ikkinchisi uchun optimal strategiyalar juftligi mavjud. o'yin narxiga teng bo'lgan o'rtacha to'lov. Agar to'liq ma'lumotga ega bo'lgan o'yin faqat shaxsiy harakatlardan iborat bo'lsa, unda har bir tomon o'zining optimal strategiyasini qo'llasa, u har doim aniq natija bilan yakunlanishi kerak, ya'ni o'yin narxiga to'liq teng keladigan foyda.

22. Aralash strategiyalarda o'yinning yechimi.

Amaliy ahamiyatga ega chekli o'yinlar orasida kuch nuqtasi bo'lgan o'yinlar nisbatan kam uchraydi; o'yinning pastki va yuqori narxlari har xil bo'lganda odatiy holdir. Bunday o'yinlarning matritsalarini tahlil qilib, biz shunday xulosaga kelamizki, agar har bir o'yinchiga bitta strategiyani tanlash huquqi berilsa, unda oqilona harakat qiladigan raqibga asoslanib, bu tanlov minimax printsipi bilan belgilanishi kerak. Maksimal strategiyamizga rioya qilgan holda, raqibning har qanday xatti-harakati uchun biz o'zimizga o'yinning past narxiga teng bo'lgan to'lovni kafolatlaymiz. aralash strategiyalar

aralash strategiya Sa A o'yinchisi p1,p2,…pi,…pm ehtimolliklari bilan A1,A1,…,Ai,…,Am sof strategiyalarini qo'llash deb ataladi va ehtimollar yig'indisi 1: ga teng. A o'yinchining aralash strategiyalari matritsa sifatida yoziladi

yoki satr sifatida Sa=(p1,p2,…,pi,…,pm).

Xuddi shunday, B o'yinchining aralash strategiyalari quyidagilar bilan belgilanadi:

Yoki Sb=(q1,q2,…,qi,…,qn),

bu erda strategiyalarning paydo bo'lish ehtimoli yig'indisi 1 ga teng: .

Shubhasiz, har bir sof strategiya aralash strategiyaning alohida holati bo'lib, unda bittadan tashqari barcha strategiyalar nol chastotalar (ehtimollar) bilan qo'llaniladi va bu 1 chastotasi (ehtimoli) bilan qo'llaniladi.

Ma'lum bo'lishicha, nafaqat sof, balki aralash strategiyalarni qo'llash orqali har bir chekli o'yin uchun yechim olish mumkin, ya'ni bunday (umuman aralash) strategiyalar juftligi shundayki, har ikkala o'yinchi ulardan foydalanganda foyda teng bo'ladi. o'yin narxiga va optimal strategiyadan har qanday bir tomonlama og'ish bo'lsa, to'lov faqat deviant uchun noqulay yo'nalishda o'zgarishi mumkin. Shunday qilib, minimax printsipiga asoslanib, u aniqlanadi optimal yechim (yoki yechim) o'yinlar: bu optimal strategiyalar juftligi umumiy holatda, aralash, quyidagi xususiyatga ega: agar o'yinchilardan biri o'zining optimal strategiyasiga rioya qilsa, ikkinchisi unikidan chetga chiqishi foydali bo'lmaydi. Optimal yechimga mos keladigan to'lov deyiladi o'ynash evaziga v . O'yinning narxi tengsizlikni qondiradi:

Bu erda a va b o'yinning pastki va yuqori narxlari.

Bu bayonot deb atalmish mazmuni hisoblanadi o'yin nazariyasining asosiy teoremasi. Bu teorema birinchi marta 1928 yilda Jon fon Neyman tomonidan isbotlangan. Teoremaning ma'lum isbotlari nisbatan murakkab; shuning uchun biz faqat uning formulasini keltiramiz.

Har bir cheklangan o'yin kamida bitta optimal echimga ega, ehtimol aralash strategiyalar orasida.

Asosiy teoremadan kelib chiqadiki, har bir cheklangan o'yinning narxi bor.

Qo'ying va – optimal strategiyalar juftligi. Agar sof strategiya nolga teng bo'lmagan ehtimollik bilan optimal aralash strategiyaga kiritilgan bo'lsa, u deyiladi faol (foydali) .

Yarmarka faol strategiya teoremasi: agar o'yinchilardan biri o'zining optimal aralash strategiyasiga rioya qilsa, ikkinchi o'yinchi o'zining faol strategiyasidan tashqariga chiqmasa, to'lov o'zgarishsiz qoladi va v o'yinining narxiga teng bo'ladi.

O'yinchi o'zining har qanday faol strategiyasidan sof shaklda foydalanishi va ularni istalgan nisbatda aralashtirishi mumkin.

Ushbu teorema katta amaliy ahamiyatga ega - u egar nuqtasi bo'lmagan taqdirda optimal strategiyalarni topish uchun aniq modellarni beradi.

O'ylab ko'ring 2x2 o'lchamli o'yin, bu cheklangan o'yinning eng oddiy holati. Agar bunday o'yinda egar nuqtasi bo'lsa, unda eng maqbul echim bu nuqtaga mos keladigan sof strategiyalar juftligidir.

O'yin nazariyasining asosiy teoremasiga ko'ra, egar nuqtasi bo'lmagan o'yin optimal yechim mavjud va aralash strategiyalar juftligi bilan belgilanadi Va.

Ularni topish uchun biz faol strategiyalar haqidagi teoremadan foydalanamiz. Agar o'yinchi A uning optimal strategiyasiga amal qiladi , keyin uning o'rtacha to'lovi o'yin narxiga teng bo'ladi v, o'yinchi qanday faol strategiyadan foydalanmasin IN. 2v2 o'yin uchun, agar ssdl nuqtasi bo'lmasa, har qanday raqibning sof strategiyasi faol bo'ladi. O'yinchi g'alaba qozonadi A(o'yinchining yo'qolishi IN)- tasodifiy o'zgaruvchi, uning matematik kutilishi (o'rtacha qiymati) o'yinning narxi. Shunday qilib, o'yinchining o'rtacha daromadi A(optimal strategiya) ga teng bo'ladi v 1 va 2-dushman strategiyalari uchun.

O'yin to'lov matritsasi tomonidan berilsin.

O'yinchining o'rtacha daromadi A, u optimal aralash strategiya va futbolchi foydalanadi, agar IN - sof strategiya B1 (bu to'lov matritsasining 1-ustuniga to'g'ri keladi R), o'yin narxiga teng v: .

O'yinchi bir xil o'rtacha daromad oladi A, agar 2-o'yinchi B2 strategiyasidan foydalansa, ya'ni. . Shuni hisobga olib, biz optimal strategiyani aniqlash uchun tenglamalar tizimini olamiz va o'yin narxlari v:

Ushbu tizimni yechish orqali biz optimal strategiyani olamiz

va o'yinning narxi.

Topish uchun faol strategiya teoremasini qo'llash – o'yinchining optimal strategiyasi IN, Biz buni o'yinchining har qanday sof strategiyasi uchun olamiz A (A1 yoki A2) o'rtacha o'yinchi yo'qotish IN o'yin narxiga teng v, ya'ni.

Keyin optimal strategiya formulalar bilan aniqlanadi: .

O'yinni hal qilish vazifasi, agar uning matritsasida egar nuqtasi bo'lmasa, qanchalik qiyin bo'lsa, qiymat shunchalik katta bo'ladi. m Va n. Shuning uchun, matritsali o'yinlar nazariyasida, ba'zi o'yinlarning yechimi boshqa, sodda bo'lganlarning yechimiga, xususan, matritsaning o'lchamini kamaytirishga olib keladigan usullar ko'rib chiqiladi. Matritsaning o'lchamini istisno qilish orqali kamaytirish mumkin dublikat va aniq noqulay strategiyalar.

Dublikat to'lov matritsasidagi elementlarning bir xil qiymatlariga mos keladigan strategiyalar deyiladi, ya'ni. matritsa bir xil satrlarni (ustunlarni) o'z ichiga oladi.

Agar matritsaning i-qatorining barcha elementlari k-qatorning mos keladigan elementlaridan kichik bo'lsa, u holda o'yinchi uchun i-chi strategiya. A foydasiz (kamroq g'alaba qozonish).

Agar matritsaning r-ustunining barcha elementlari j-ustunning mos keladigan elementlaridan katta bo'lsa, u holda o'yinchi uchun IN R-chi strategiya foydasiz (yo'qotish kattaroq).

Takroriy va aniq foydasiz strategiyalarni yo'q qilish tartibi har doim o'yinni hal qilishdan oldin bo'lishi kerak.

23. 2×2 o‘yinining geometrik talqini

O'yin qarori 2×2 aniq geometrik talqin qilish imkonini beradi.

O'yin to'lov matritsasi P=(aij), i, j=1,2 bilan berilgan bo'lsin.

Abscissa ustida (rasm) chetga qo'ying birlik segment A1A2; nuqta A1 ( X=0) A1 strategiyasini, A2 nuqtasini ( X=1) A2 strategiyasini tasvirlaydi va bu segmentning barcha oraliq nuqtalari birinchi o'yinchining aralash strategiyalari Sa hisoblanadi va Sa dan segmentning o'ng oxirigacha bo'lgan masofa A1 strategiyasining p1 ehtimolligidir. , chap uchigacha bo'lgan masofa A2 strategiyasining p2 ehtimoli .

A1 va A2 nuqtalar orqali x o'qiga ikkita perpendikulyar o'tkazamiz: o'q I-I va o'q II-II. I-I o'qida biz A1 strategiyasi bo'yicha yutuqlarni kechiktiramiz; II-II o'qi bo'yicha - A2 strategiyasi bo'yicha to'lovlar.

Agar A o'yinchisi A1 strategiyasidan foydalansa, B o'yinchining B1 strategiyasi bo'yicha uning to'lovi a11, B2 strategiyasi bo'yicha esa a12 bo'ladi. I o'qdagi a11 va a12 raqamlari B1 va B2 nuqtalariga to'g'ri keladi.

Agar A o'yinchisi A2 strategiyasidan foydalansa, B o'yinchining B1 strategiyasi bo'yicha uning to'lovi a21, B2 strategiyasida esa a22 ga teng. a21 va a22 raqamlari II o'qdagi B1 va B2 nuqtalariga to'g'ri keladi.

B1 (I) va B1 (II) nuqtalarini bog'laymiz; B2 (I) va B2 (II). Ikkita to'g'ri chiziq bor. To'g'ri chiziq B1B1 - agar o'yinchi A aralash strategiyani qo'llaydi (p1 va p2 ehtimolliklari bilan A1 va A2 strategiyalarining har qanday kombinatsiyasi) va B o'yinchisi B1 strategiyasini qo'llaydi. G'olib o'yinchi A bu chiziqning qaysidir nuqtasiga mos keladi. Aralash strategiyaga mos keladigan o'rtacha daromad a11p1+a21p2 formulasi bilan aniqlanadi va M1 nuqtasi bilan ifodalanadi. B1B1 liniyasida.

Xuddi shunday, biz ikkinchi o'yinchi tomonidan B2 strategiyasidan foydalanishga mos keladigan B2B2 segmentini quramiz. Bunda o'rtacha daromad a12p1+a22p2 formula bilan aniqlanadi va M2 nuqta bilan ifodalanadi. B2B2 to'g'ri chiziqda.

Biz optimal S*a strategiyasini, ya'ni minimal foyda keltiradigan strategiyani topishimiz kerak (har qanday xatti-harakatlar uchun IN) maksimal darajaga aylanadi. Buning uchun biz quramiz daromadning pastki chegarasi B1B2 strategiyalari bilan , ya'ni, shaklda belgilangan B1NB2 singan chiziq. qalin chiziq. Bu pastki chegara o'yinchining minimal to'lovini ifodalaydi A uning har qanday aralash strategiyasi uchun; nuqtaN , unda bu minimal to'lov maksimal darajaga etadi va yechim (optimal strategiya) va o'yin narxini belgilaydi. Nuqta ordinatasi N o'ynash uchun narx bormi v. Nuqta koordinatalari N B1B1 va B2B2 chiziqlarning kesishish nuqtalarining koordinatalari sifatida topamiz. Bizning holatda, o'yinning yechimi strategiyalarning kesishish nuqtasi bilan aniqlandi. Biroq, bu har doim ham shunday bo'lmaydi.

O'yinchi sifatida optimal strategiyani aniqlash geometrik jihatdan mumkin A, shuningdek, o'yinchi IN; ikkala holatda ham minimaks printsipi qo'llaniladi, lekin ikkinchi holda, to'lovning pastki emas, balki yuqori chegarasi quriladi va maksimal emas, balki minimal belgilanadi.

Agar to'lov matritsasi manfiy sonlarni o'z ichiga olgan bo'lsa, muammoni grafik hal qilish uchun manfiy bo'lmagan elementlarga ega yangi matritsaga o'tish yaxshiroqdir; Buning uchun dastlabki matritsaning elementlariga mos keladigan musbat sonni qo'shish kifoya. O'yinning qarori o'zgarmaydi, lekin o'yin narxi bu raqamga oshadi. Grafik usul o'yinni 2×n, m×2 yechish uchun ishlatilishi mumkin.

24. Matritsali o‘yinni chiziqli dasturlash masalasiga keltirish

m × n o'yini odatda vizual geometrik talqinga ega emas. Uning yechimi kattalar uchun ancha mashaqqatli T Va n, biroq, u hech qanday fundamental qiyinchiliklarga ega emas, chunki uni chiziqli dasturlash muammosini hal qilish uchun qisqartirish mumkin. Keling, ko'rsataylik.

m×n o‘yin to‘lov matritsasi bilan berilgan bo‘lsin . O'yinchi A A1,A2,..Ai,..Am strategiyalariga ega , futbolchi IN - strategiyalar B 1,B 2,..B men,.. B n. Optimal strategiyalarni va qaerdaligini aniqlash kerak mos keladigan sof strategiyalarni qo'llash ehtimoli Ai, Bj,

Optimal strategiya quyidagi talabni qondiradi. Bu o'yinchini ta'minlaydi A o'rtacha to'lov o'yin narxidan kam bo'lmagan v, o'yinchining har qanday strategiyasi uchun IN va o'yin narxiga teng bo'lgan to'lov v, o'yinchining optimal strategiyasi bilan IN. Umumiylikni yo'qotmasdan, biz o'rnatdik v> 0; Bunga barcha elementlarni yasash orqali erishish mumkin . Agar o'yinchi A har qanday sof strategiya Bj o'yinchiga qarshi aralash strategiyani qo'llaydi IN, keyin oladi o'rtacha daromad , yoki g'alaba qozonishni matematik kutish (ya'ni elementlar j-Go to'lov matritsasi ustunlari A1, A2,..Ai,..Am strategiyalarining mos keladigan ehtimoli bilan muddatga ko'paytiriladi va natijalar qo'shiladi).

Optimal strategiya uchun barcha o'rtacha to'lovlar o'yin narxidan kam emas v, shuning uchun biz tengsizliklar tizimini olamiz:

Tengsizliklarning har birini raqamga bo'lish mumkin. Keling, yangi o'zgaruvchilarni kiritamiz: . Keyin tizim shaklni oladi

O'yinchi maqsadi A - kafolatlangan to'lovingizni maksimal darajada oshiring, ya'ni. o'yin narxi v.

Tenglikka bo'linib, o'zgaruvchilar shartni qanoatlantirishini olamiz: . O'yin narxini maksimallashtirish v miqdorini minimallashtirishga tengdir , shuning uchun muammoni quyidagicha shakllantirish mumkin: o'zgaruvchan qiymatlarni aniqlang , machiziqli cheklovlarni qondirish uchun(*) Va chiziqli funksiya esa (2*) minimal darajaga qaytdi.

Bu chiziqli dasturlash muammosi. (1*)–(2*) masalani yechish orqali biz optimal yechimga erishamiz va optimal strategiya .

Optimal strategiyani aniqlash uchun o'yinchi ekanligini hisobga olish kerak IN kafolatlangan to'lovni minimallashtirishga intiladi, ya'ni. maksimalni toping. O'zgaruvchilar tengsizliklarni qondiradi

o'yinchining o'rtacha yo'qotishidan kelib chiqadi IN o'yinning qiymatidan oshmaydi, o'yinchi qanday sof strategiyadan foydalanmasin A.

Agar (4*) ni belgilasak, tengsizliklar sistemasini olamiz:

O'zgaruvchilar shartni qondiradi.

O'yin keyingi vazifaga qisqartirildi.

O'zgaruvchan qiymatlarni aniqlash , bu tengsizliklar tizimini qanoatlantiradi (5*)Va chiziqli funksiyani maksimallashtirish

Chiziqli dasturlash masalasini yechish (5*), (6*) optimal strategiyani belgilaydi. Shu bilan birga, o'yinning narxi. (7*)

(1*), (2*) va (5*), (6*) masalalar uchun kengaytirilgan matritsalarni tuzib, biz bir matritsa boshqasidan transpozitsiya orqali olinganligiga ishonch hosil qilamiz:

Shunday qilib, chiziqli dasturlash masalalari (1*), (2*) va (5*), (6*) oʻzaro ikkilikdir. Shubhasiz, aniq masalalarda optimal strategiyalarni aniqlashda, yechimi kamroq mehnat talab qiladigan o'zaro ikki tomonlama masalalardan birini tanlash va ikkilik teoremalaridan foydalangan holda boshqa masalaning echimini topish kerak.

m×n o‘lchamdagi ixtiyoriy chekli o‘yinni yechishda quyidagi sxemaga amal qilish tavsiya etiladi:

1. Boshqa strategiyalar bilan solishtirganda foyda matritsasidan aniq foydasiz strategiyalarni chiqarib tashlang. O'yinchi uchun bunday strategiyalar A

operatsiyalar tadqiqoti) - nisbatan yangi hudud, uning qisqacha tarixi Ikkinchi jahon urushi boshlanishiga borib taqaladi. Bu aniq mat. fan aniq belgilangan umumiy tamoyillarni o'z ichiga oladi, to-rye tadqiqotchilarga ilmiy tadqiqot operatsiyalarini amalga oshirish rejasini beradi. U quyidagi bosqichlarni o'z ichiga oladi. 1. Muammoni shakllantirish. 2. Matnning qurilishi. o'rganilayotgan tizimni ifodalovchi model. 3. Ushbu modeldan yechim olish. 4. Model va undan olingan yechimni tekshirish. 5. Qaror ustidan nazoratni o'rnatish. 6. Amaliyot. yechimni amalga oshirish: amalga oshirish. Muammoni shakllantirish Muammoning umumiy mohiyatini va eng muhimi, tadqiqot maqsadlarini aniqlashga jiddiy e'tibor berish kerak. Ushbu maqsadlar noaniqlik va noaniqlikni kamaytirish yoki yo'q qilish uchun xatti-harakatlar nuqtai nazaridan shakllantirilishi kerak. Haqiqiy erishish mumkin bo'lgan maqsadlarni to'g'ri belgilash uchun vaqt ham berilishi kerak. Maqsadlarning juda uzun ro'yxati ularni amalga oshirishda mumkin bo'lgan qiyinchiliklarga olib kelishi mumkin, ayniqsa bu maqsadlar mantiqiy ketma-ketlikda aniq bog'lanmagan bo'lsa. Matematik modelni qurish T. sp bilan tadqiqotning ikkinchi bosqichi. Va taxminan. modelning tavsifini taklif qiladi. Modelning maqsadi haqiqiy dunyoni tasvirlashdir. I. o.da. bunday modellar ramziy, matda ifodalangan. shartlari. E \u003d mc2 klassik tenglamasi matning odatiy namunasidir. modellar. Bunday modellar uchun an'anaviy shakllar algebraik tenglamalar, to-rye nafaqat val. og'zaki formulalarga qaraganda ancha tejamkor, lekin ayni paytda alohida elementlar va ularning munosabatlarini aniq ifodalash va tushunish uchun zarur bo'lgan ta'rifning puxtaligi va aniqligini talab qiladi. Bunday modelni qurishda eng muhim vazifa maqsad funktsiyasini aniq va aniq ishlab chiqish va aniqlashdir. Bu funksiya mustaqil va qaram o'zgaruvchilar o'rtasidagi munosabatni ifodalaydi. Berilgan modeldan yechim olish Uchinchi bosqich - yechim topish. Qoidaga ko'ra, optimal yoki yaxshiroq yechim topish maqsadga muvofiqdir, ammo shuni hisobga olish kerakki, bunday yechim faqat ko'rib chiqilayotgan model kontekstida qiymatga ega bo'ladi. Model faqat real dunyo muammosining timsoli bo'lganligi sababli, optimal echim eng yaxshi tanlov bilan bog'lanmasligi mumkin bo'lgan ko'plab vaziyatlar mavjud. Biroq, optimal yechim kamroq optimal yoki ko'proq real bo'lgan muqobil echimlar bilan birlashtirilsa, ularni keyinchalik haqiqiy muammoga nisbatan sinovdan o'tkazish imkoniyati mavjud bo'lsa, optimal echimdan foydalanish ma'lum foyda keltiradi. Bunday imtiyozlardan biri tadqiqot oxiridagi ta'rif bilan bog'liq. bu ideal yechim va qabul qilingan muqobil o'rtasidagi nisbiy masofa. Ushbu metodologiyaning qo'shimcha mahsuloti I. o. kamroq optimal echimlarni maqsadga erishish yo'lidagi toshlar sifatida ko'rish mumkin degan taxmindir. Ushbu ketma-ket yaqinlashish usuli operatsiyalar tadqiqotchisini yanada samarali natijalarga olib kelishi mumkin. Ko'p matlar bor. I. o.dagi yechimlarni olish tartiblari. Ushbu protseduralar ehtimollik nazariyasini qo'llashga asoslangan. Modelni tekshirish va undan olingan yechim Model va yechimni tekshirish ikki bosqichni amalga oshirish bilan bog'liq. Birinchisi, modelning barcha elementlarini, shu jumladan, to'liq tahlil qilishdan iborat. haqiqiyligiga ta'sir qilishi mumkin bo'lgan sodda kosmetik xatolar mavjudligi uchun uning algebraik omillarini qayta tekshirish. Dr. Bundan ham muhimroq qadam, modelning ushbu modelni ishlab chiqishda dastlab foydalanilgan taxminlarga munosabatini qayta aniqlashni o'z ichiga oladi. Yana tizimli ko'rib chiqish rejasi ist dan foydalanishni ham o'z ichiga oladi. prototip yechimini olish uchun modelga osongina kiritilishi mumkin bo'lgan ma'lumotlar. Operatsiya tadqiqotchisiga tekshirishning haqiqiyligini ta'minlash uchun ushbu ma'lumotlar diqqat bilan ko'rib chiqilishi kerak. Shuni ta'kidlash kerakki, ushbu model avvalgi manbalar asosida amalda ishlab chiqilishi bilanoq. ma'lumotlar va ehtiyojlar, u kelajakda juda boshqacha harakat qilishi mumkin. Dr. keng tarqalgan xato - bu modelga omillarni kiritish, to-rye istda taqdim etilmagan. ma'lumotlar bazasi. Nazoratni o'rnatish Qaror ustidan nazoratni o'rnatish beshinchi bosqich modeldan takroran foydalanish jarayonida paydo bo'ladi. Operatsion tadqiqotchi ist qiymatlaridagi nomuvofiqlikka yo'l qo'yganda model ustidan nazorat o'rnatiladi. ma'lumotlar va bu nomuvofiqliklar model elementlari va natijaviy echimlar o'rtasidagi munosabatlarga ta'sir qilishi mumkinligini tan oladi. Dr. muhim qadam tanlangan asoslar bo'yicha cheklovlar ishlab chiqish bo'lishi mumkin. haqiqiy ma'lumotlarga asoslangan maqbul qiymatlar qatorini o'rnatish uchun model parametrlari. Modelni amalga oshirish Yakuniy bosqich modelga real ma'lumotlarni kiritishdir. Amaliyot. modelni amalga oshirish haqiqiy ma'lumotlarni kiritish va haqiqiy muammoning echimini olishning aniq bosqichi bilan bog'liq. Bundan tashqari, haqiqiy yechimning istga yaqinligini baholash ham muhimdir. ilgari olingan echimlar, shuningdek, ushbu qarorning modeldan foydalanish usulini yaxshilash uchun oqibatlari. Ushbu qadamlar mat o'rtasida muhim aloqani ta'minlaydi. tabiat I. o. va mashq qiling. tadqiqot natijalari. Oxir oqibat, bu qarorlar va ularning boshqaruv oqibatlari tajribali AI mutaxassisi tomonidan qo'llaniladi. kelajakda foydalanish uchun modelni takomillashtirish. Shuningdek qarang (ilmiy) tadqiqot metodologiyasi R. S. Endrulis