Qavariq to'plamlar va ularning xossalari. Qavariq to'plamning xossalarini o'rganish uchun qavariq to'plamga qat'iy ta'rif berish kerak. Ilgari qavariq to'plam o'zining istalgan ikkita nuqtasi bilan birga ularni bog'lovchi segmentni o'z ichiga olgan to'plam sifatida aniqlangan.

Bir nechta nuqtalar uchun segment tushunchasini umumlashtirish ularning konveks chiziqli birikmasidir.

X nuqta deyiladi qavariq chiziqli birikma ball, agar shartlar bajarilsa

Nuqtalar to'plami qavariq, agar u istalgan ikkita nuqta bilan birgalikda ularning ixtiyoriy qavariq, chiziqli birikmasini o'z ichiga olsa.

Qavariq ko‘pburchakning tasviri haqidagi quyidagi teoremani isbotlashimiz mumkin.

1.1 teorema. Qavariq n o‘lchamli ko‘pburchak uning burchak nuqtalarining qavariq chiziqli birikmasidir.

1.1 teoremadan kelib chiqadiki, qavariq ko'pburchak uning burchak nuqtalari yoki uchlari orqali hosil bo'ladi: segment ikki nuqta, uchburchak uch, tetraedr to'rt nuqta va boshqalar. Shu bilan birga, qavariq ko'pburchak mintaqasi, chegaralanmagan to'plam bo'lib, uning burchak nuqtalari bilan yagona aniqlanmaydi: uning biron bir nuqtasini burchak nuqtalarining qavariq chiziqli birikmasi sifatida tasvirlash mumkin emas.

Chiziqli dasturlash masalasining xossalari. Ilgari chiziqli dasturlash masalasining turli shakllari ko'rib chiqilgan va har qanday chiziqli dasturlash masalasi umumiy yoki kanonik masala sifatida ko'rsatilishi mumkinligi ko'rsatilgan.

Chiziqli dasturlash masalasining xossalari va uni yechish usullarini asoslash uchun kanonik masala belgilanishining yana ikkita turini ko‘rib chiqish maqsadga muvofiqdir.

Matritsani yozib olish shakli:

Bu yerga BILAN- qatorli matritsa, A- tizim matritsasi, X- matritsa-o'zgaruvchilar ustuni, IN- erkin a'zolarning matritsa ustuni:

Yozib olishning vektor shakli:

bu erda vektorlar noma'lumlar uchun koeffitsientlar ustunlariga mos keladi.

Bu yuqorida ishlab chiqilgan, ammo isbotlanmagan umumiy ko'rinish keyingi teorema.

1.2 teorema. Chiziqli dasturlash masalasining cheklashlar tizimining barcha mumkin bo'lgan yechimlari to'plami qavariqdir.

Isbot: Mayli - matritsa shaklida berilgan PLP ning ikkita mumkin bo'lgan echimi. Keyin . Keling, yechimlarning konveks chiziqli birikmasini ko'rib chiqaylik, ya'ni.

va (1.3) tizimning ham ruxsat etilgan yechimi ekanligini ko'rsating. Haqiqatdan ham

ya'ni yechim X tizimni qanoatlantiradi (1.3). Ammo o'shandan beri X>0, ya'ni. yechim noaniqlik shartini qanoatlantiradi.

Shunday qilib, chiziqli dasturlash muammosining barcha mumkin bo'lgan echimlari to'plami qavariq ekanligi isbotlangan, aniqrog'i, u qavariq ko'pburchak yoki qavariq ko'p yuzli mintaqani ifodalaydi, biz uni keyinchalik bir atama bilan chaqiramiz - eritmalar ko'p yuzli.

Eritmalar ko'pburchakning qaysi nuqtasida mumkin bo'lgan savolga javob optimal yechim chiziqli dasturlash masalasi quyidagi fundamental teoremada berilgan.

1.3 teorema. Agar chiziqli dasturlash masalasi optimal yechimga ega bo‘lsa, chiziqli funksiya yechim ko‘pburchakning burchak nuqtalaridan birida o‘zining maksimal qiymatini oladi. Agar chiziqli funktsiya bir nechta burchak nuqtalarida maksimal qiymat olsa, u uni ushbu nuqtalarning qavariq chiziqli birikmasi bo'lgan istalgan nuqtada oladi.

Isbot: Eritma ko'pburchak chegaralangan deb faraz qilamiz. Uning burchak nuqtalarini bilan belgilaymiz , va optimal yechim orqali X*. Keyin F(X*)³ F(X) barcha nuqtalar uchun X eritmalar ko'p yuzli. Agar X* burchak nuqtasi bo'lsa, u holda teoremaning birinchi qismi isbotlanadi.

Keling, shunday da'vo qilaylik X* burchak nuqtasi emas, demak, teorema 1.1 ga asoslanadi X* eritma polihedrining burchak nuqtalarining konveks chiziqli birikmasi sifatida ifodalanishi mumkin, ya'ni.

Chunki F(X) chiziqli funksiyadir, biz olamiz

Ushbu parchalanishda biz qiymatlar orasidan maksimalni tanlaymiz. Bu burchak nuqtasiga mos kelsin Xk(1 £ k£ R); bilan belgilaylik M, bular. . (1.5) ifodadagi har bir qiymatni shu maksimal qiymat bilan almashtiramiz M. Keyin

Taxminlarga ko'ra X* bir tomondan optimal yechim bo'lsa, boshqa tomondan isbotlangan
F(X*)£ M, shuning uchun, , qaerda Xk- burchak nuqtasi. Shunday qilib, burchak nuqtasi bor Xk, bunda chiziqli funksiya maksimal qiymatini oladi.

Teoremaning ikkinchi qismini isbotlash uchun maqsad funksiyasi bir nechta burchak nuqtalarida, masalan, nuqtalarda maksimal qiymat oladi deb faraz qilaylik. , Qayerda , Keyin

Mayli X- bu burchak nuqtalarining konveks chiziqli birikmasi, ya'ni.

Bu holda, funktsiyani hisobga olgan holda F(X)- chiziqli, biz olamiz

bular. chiziqli funksiya F ixtiyoriy nuqtada maksimal qiymatni oladi X, bu burchak nuqtalarining konveks chiziqli birikmasidir.

Izoh. Teoremada yechim ko‘p yuzli chegaralangan bo‘lishi talabi muhim ahamiyatga ega, chunki 1.1-teoremada ta’kidlanganidek, chegaralanmagan ko‘p yuzli mintaqada bunday mintaqaning har bir nuqtasini uning burchak nuqtalarining qavariq chiziqli birikmasi bilan ifodalash mumkin emas.

Tasdiqlangan teorema asosiy hisoblanadi, chunki u chiziqli dasturlash masalalarini hal qilishning asosiy usulini ko'rsatadi. Darhaqiqat, ushbu teoremaga ko'ra, ular orasida kerakli optimal echimni topish uchun cheksiz mumkin bo'lgan echimlar to'plamini o'rganish o'rniga, faqat eritma ko'pburchakning chekli sonli burchak nuqtalarini o'rganish kerak.

Keyingi teorema burchak nuqtalarini topishning analitik usuliga bag'ishlangan.

1.4 teorema. Chiziqli dasturlash masalasining har bir ruxsat etilgan asosiy yechimi yechim ko‘pburchakning burchak nuqtasiga to‘g‘ri keladi va aksincha, yechim ko‘pburchakning har bir burchak nuqtasiga ruxsat etilgan bazis yechimi mos keladi.

Isbot: MChJ cheklovlar tizimining maqbul asosiy yechimi bo'lsin (1.4), unda birinchisi T komponent asosiy o'zgaruvchilar va qolganlari p - t komponent - asosiy yechimda nolga teng asosiy bo'lmagan o'zgaruvchilar (agar bunday bo'lmasa, mos keladigan o'zgaruvchilarni qayta raqamlash mumkin). Keling, buni ko'rsataylik X

Keling, buning aksini faraz qilaylik, ya'ni. Nima X burchak nuqtasi emas. Keyin ishora qiling X bir-biriga to'g'ri kelmaydigan ikki xilni bog'laydigan segmentning ichki nuqtasi bilan ifodalanishi mumkin X, ball

boshqacha aytganda, nuqtalarning qavariq chiziqli birikmasi eritmalar ko'p yuzli, ya'ni.

qaerda (biz buni taxmin qilamiz, chunki aks holda nuqta X nuqta bilan mos keladi X 1 yoki X 2).

(1.6) vektor tengligini koordinata shaklida yozamiz:

Chunki barcha o'zgaruvchilar va koeffitsientlar salbiy emas, keyin oxirgidan p-t tenglik bundan kelib chiqadiki, ya'ni. qarorlarda X 1 , X 2 va X tenglamalar tizimi (1.4) qiymatlari p - t Bu holda komponentlar nolga teng. Ushbu komponentlarni birlamchi bo'lmagan o'zgaruvchilarning qiymatlari deb hisoblash mumkin. Ammo asosiy bo'lmagan o'zgaruvchilarning qiymatlari asosiylarining qiymatlarini aniq belgilaydi, shuning uchun

Shunday qilib, hamma narsa P eritmalardagi komponent X 1 , X 2 va X mos keladi va shuning uchun nuqtalar X 1 va X 2 birlashma, bu taxminga zid keladi. Demak, X– eritma ko‘pburchakning burchak nuqtasi.

Keling, qarama-qarshi gapni isbotlaylik. Eritma ko'pburchakning burchak nuqtasi va uning birinchisi bo'lsin T koordinatalari musbat. Keling, buni ko'rsataylik X- ruxsat etilgan asosiy yechim. shartga zid bo'lgan burchak nuqtasi emas. Shuning uchun, bizning taxminimiz noto'g'ri, ya'ni. vektorlar chiziqli mustaqil va X muammoning qabul qilinadigan asosiy yechimi (1.4).

Muhim xulosa to'g'ridan-to'g'ri 1.3 va 1.4 teoremalaridan kelib chiqadi: agar chiziqli dasturlash muammosi optimal yechimga ega bo'lsa, u holda mos keladi kamida, uning ruxsat etilgan asosiy echimlaridan biri bilan.

Shunday qilib, optimal chiziqli funksiya Chiziqli dasturlash masalalarini uning amalga oshirilishi mumkin bo'lgan asosiy echimlarining cheklangan sonidan izlash kerak.

Keling, asosiy chiziqli dasturlash muammosini (LPLP) ko'rib chiqaylik: x1, x2, ..., xn o'zgaruvchilarning manfiy bo'lmagan qiymatlarini toping, m shartlarni - tenglikni qondiring.

va bu o'zgaruvchilarning chiziqli funktsiyasini maksimallashtirish

Oddiylik uchun biz barcha shartlarni (1) chiziqli mustaqil (r=m) deb hisoblaymiz va biz o'z fikrimizni shu faraz asosida olib boramiz.

OLP ning ruxsat etilgan yechimini (1) shartlarni qanoatlantiradigan x1, x2, ..., xn manfiy bo'lmagan qiymatlarning har qanday to'plami deb ataymiz.Funktsiyani (2) maksimallashtiruvchi ruxsat etilgan yechimlardan birini optimal deb ataymiz. Biz optimal yechim topishimiz kerak.

Bu muammo har doim yechimga egami? Yo'q har doim emas.

ZLP hal etilmaydi (optimal yechim yo'q):

Cheklash tizimining mos kelmasligi tufayli. Bular. tizimda 1-rasmda ko'rsatilganidek, yagona yechim yo'q.

1-rasm - Cheklovlar tizimining nomuvofiqligi

Yechimlar to'plamida maqsad funktsiyasining cheksizligi tufayli. Boshqacha qilib aytganda, LLP ni maxda yechishda maqsad funksiyaning qiymati 2-rasmda ko'rsatilganidek, cheksizlikka, LLP esa min da - minus cheksizlikka intiladi.

2-rasm - Yechimlar to'plamidagi maqsad funktsiyasining cheksizligi

ZLP hal qilinishi mumkin:

Yechimlar to'plami bitta nuqtadan iborat. 3-rasmda ko'rsatilganidek, u ham optimal hisoblanadi.

3-rasm - Yechimlar to'plami bir nuqtadan iborat

ZLP uchun yagona optimal yechim. Chegara holatidagi maqsad funksiyasiga mos keladigan to‘g‘ri chiziq yechimlar to‘plami bilan 4-rasmda ko‘rsatilganidek, bir nuqtada kesishadi.

4-rasm - yagona optimal yechim

ZLP ning optimal yechimi yagona emas. N vektor yechimlar to'plamining tomonlaridan biriga perpendikulyar. Bunda 5-rasmda ko'rsatilganidek, AB segmentidagi istalgan nuqta optimal hisoblanadi.

5-rasm - Optimal yechim yagona emas

Simpleks usuli yordamida chiziqli dasturlash masalalarini yechish

Simpleks usuli - LP muammosini hal qilish algoritmi bo'lib, u C maqsad funktsiyasining qiymatini yaxshilash yo'nalishi bo'yicha amalga oshirilishi mumkin bo'lgan echimlar mintaqasining burchak nuqtalarini sanashni amalga oshiradi. Simpleks usuli chiziqli dasturlashda asosiy hisoblanadi.

LP muammosini hal qilish uchun diplom loyihasida ushbu usuldan foydalanish quyidagi omillar bilan bog'liq:

Usul universal bo'lib, kanonik shakldagi har qanday chiziqli dasturlash masalasiga qo'llaniladi;

Usulning algoritmik xususiyati uni texnik vositalar yordamida muvaffaqiyatli dasturlash va amalga oshirish imkonini beradi.

Maqsad funktsiyasining ekstremumiga har doim mumkin bo'lgan echimlar mintaqasining burchak nuqtalarida erishiladi. Avvalo, ba'zi bir mumkin bo'lgan boshlang'ich (mos yozuvlar) yechim topiladi, ya'ni. mumkin bo'lgan echimlar mintaqasining istalgan burchak nuqtasi. Usulning protsedurasi ushbu yechimning maqbulmi degan savolga javob berishga imkon beradi. Ha bo'lsa, muammo hal qilingan. Agar "yo'q" bo'lsa, maqsadga muvofiq echimlar mintaqasining qo'shni burchak nuqtasiga o'tish amalga oshiriladi, bu erda maqsad funktsiyasining qiymati yaxshilanadi. Mumkin yechimlar mintaqasining burchak nuqtalarini sanash jarayoni maqsad funksiyaning ekstremumiga mos keladigan nuqta topilguncha takrorlanadi.

Ko'pburchakning uchlari soni cheklanganligi sababli, cheklangan miqdordagi qadamlarda optimal qiymatni topish yoki muammoni hal qilib bo'lmaydigan faktni aniqlash kafolatlanadi.

Bu erda cheklovlar tizimi chiziqli tenglamalar tizimi bo'lib, unda noma'lumlar soni ko'proq miqdor tenglamalar. Agar tizimning darajasi teng bo'lsa, u holda qolgan noma'lumlar bilan ifodalangan noma'lumlarni tanlash mumkin. Ishonch hosil qilish uchun, odatda, birinchi navbatdagi noma'lumlar tanlangan deb taxmin qilinadi. Ushbu noma'lumlar (o'zgaruvchilar) asosiy deb ataladi, qolganlari bepul. Asosiy o'zgaruvchilar soni har doim cheklovlar soniga teng.

Erkin o'zgaruvchilarga ma'lum qiymatlarni belgilash va asosiy qiymatlarni hisoblash (erkin bo'lganlar bilan ifodalangan) orqali cheklovlar tizimi uchun turli xil echimlar olinadi. Erkin o'zgaruvchilar nolga teng bo'lgan holatda olingan echimlar alohida qiziqish uyg'otadi. Bunday echimlar asosiy deb ataladi. Asosiy yechim, agar uning o'zgaruvchilari qiymatlari manfiy bo'lmasa, ruxsat etilgan asosiy yechim yoki qo'llab-quvvatlovchi yechim deb ataladi. U barcha cheklovlarga javob beradi.

Cheklovlar tizimiga ega bo'lgan holda, ushbu tizimning har qanday asosiy echimi topiladi. Agar topilgan birinchi asosiy yechim mumkin bo'lsa, u holda uning optimalligi tekshiriladi. Agar u optimal bo'lmasa, boshqa amalga oshirilishi mumkin bo'lgan asosiy echimga o'tish amalga oshiriladi.

Simpleks usuli ushbu yangi yechim bilan chiziqli shakl, agar u optimalga erishmasa, unga yaqinlashishini kafolatlaydi. Ular eng maqbul yechim topmaguncha, yangi mumkin bo'lgan asosli yechim bilan ham xuddi shunday qilishadi.

Agar topilgan birinchi asosiy yechim nomaqbul bo'lib chiqsa, u holda simpleks usulidan foydalanib, boshqa asosiy echimlarga o'tish amalga oshiriladi, toki yechimning qaysidir bosqichida asosiy yechim maqbul bo'lib chiqmaguncha yoki nomuvofiqlik haqida xulosa chiqarilmaguncha. cheklovlar tizimi.

Shunday qilib, simpleks usulini qo'llash ikki bosqichga bo'linadi:

Cheklovlar tizimiga maqbul asosiy yechim topish yoki uning nomuvofiqligi faktini aniqlash;

Cheklashlar sistemasi mos kelsa optimal yechim topish.

Keyingi mumkin bo'lgan yechimga o'tish algoritmi quyidagicha:

Maqsad funksiyasining koeffitsientlari qatorida maksimalni topishda eng kichik manfiy son tanlanadi. Koeffitsientning seriya raqami . Agar yo'q bo'lsa, unda asl asosiy yechim maqbuldir;

Ustun raqami bo'lgan matritsaning elementlari orasida (bu ustun etakchi yoki hal qiluvchi ustun deb ataladi) ijobiy elementlar tanlanadi. Agar ular bo'lmasa, maqsad funktsiyasi o'zgaruvchilarning ruxsat etilgan qiymatlari oralig'ida cheksizdir va muammoning echimi yo'q;

Matritsaning etakchi ustunining tanlangan elementlari orasida tegishli bo'sh atamaning ushbu elementga nisbati qiymati minimal bo'lgan element tanlanadi. Bu element yetakchi, u joylashgan chiziq esa yetakchi deyiladi;

Etakchi elementning qatoriga mos keladigan asosiy o'zgaruvchini erkin toifaga o'tkazish kerak va asosiy elementning ustuniga mos keladigan erkin o'zgaruvchini asosiylar soniga kiritish kerak. Asosiy o'zgaruvchilarning yangi raqamlarini o'z ichiga olgan yangi yechim tuziladi.

Muammoni maksimal darajada echishda rejaning optimalligi sharti: maqsad funktsiyasi koeffitsientlari orasida salbiy elementlar mavjud emas.

MS Excelda chiziqli modellarni optimallashtirish amalga oshiriladi simpleks usuli- chiziqli dasturlash masalasiga mos yozuvlar yechimlarini maqsadli izlash. Simpleks usuli algoritmi ko'p o'lchovli fazoda qavariq ko'pburchakni qurishga, so'ngra ekstremal qiymatni topish uchun uning uchlarini sanab o'tishga to'g'ri keladi. maqsad funktsiyasi.

Samarali vositalar chiziqli dasturlash yanada murakkab optimallashtirish masalalarini hal qilish uchun butun son va chiziqli bo'lmagan dasturlashning asosini tashkil qiladi. Biroq, bu usullar uzoqroq hisoblash vaqtlarini talab qiladi.

Keyingi ma’ruzalarda MS Excel dasturining “Yechimni izlash” plaginidan foydalangan holda optimallashtirish bo‘yicha odatiy masalalarni yechish va boshqaruv qarorlarini qabul qilish misollari batafsil muhokama qilinadi. Ushbu vosita tomonidan eng yaxshi hal qilinadigan vazifalar uchta asosiy xususiyatga ega:

• tizimning boshqa parametrlari bilan funktsional jihatdan bog'liq bo'lgan yagona maqsad mavjud bo'lib, uni optimallashtirish kerak (uning maksimal, minimal yoki ma'lum bir raqamli qiymatini topish);
• cheklashlar mavjud bo'lib, ular odatda tengsizliklar ko'rinishida ifodalanadi (masalan, ishlatiladigan xom ashyo hajmi ombordagi xom ashyo zaxirasidan oshmasligi kerak yoki mashinaning kuniga ish vaqti 24 soatdan oshmasligi kerak. vaqt);
• optimallashtirilgan qiymatlar va cheklovlarga ta'sir qiluvchi kirish o'zgaruvchilari qiymatlari to'plami mavjud.

Vazifalarning parametrlari quyidagi chegara ko'rsatkichlari bilan cheklangan:

• noma'lumlar soni - 200;
• noma'lumlar bo'yicha formulali cheklovlar soni - 100;
• noma'lumlar uchun cheklovchi shartlar soni 400 ta.

Optimal echimlarni topish algoritmi bir necha bosqichlarni o'z ichiga oladi:

• tayyorgarlik ishlari;
• yechimni tuzatish;
• yechim tahlili.

MS Excel dasturi yordamida iqtisodiy-matematik modellashtirish masalalarini yechishda bajariladigan zaruriy tayyorgarlik ishlari ketma-ketligi 1.6-rasmdagi blok-sxemada keltirilgan.

Guruch. 1.6.

Tayyorgarlik ish rejasining besh bandidan faqat beshinchi bandi rasmiylashtiriladi. Ishning qolgan qismi ijodkorlikni talab qiladi - va har xil odamlar buni turli yo'llar bilan bajarishlari mumkin. Keling, reja bandlari matnining mohiyatini qisqacha tushuntirib beraylik.

Muammoni qo'yishda maqsadli koeffitsientlar va normallashtirilgan koeffitsientlar ma'lum. Oldingi misolda maqsad funktsiyasini tashkil etuvchi koeffitsientlar har bir turdagi javon uchun normallashtirilgan foyda qiymatlari edi ( ) va bitta raf turi ( ). Normallashtirilgan koeffitsientlar materiallar iste'moli va har bir turdagi raf uchun mashina vaqti normalari edi. Matritsa shunday ko'rinardi:

Bundan tashqari, resurs qiymatlari har doim ma'lum. Oldingi misolda, bu bir haftalik taxtalar ta'minoti va mashina vaqtidan foydalanish qobiliyati edi: , . Ko'pincha muammolarda o'zgaruvchilar qiymatlarini cheklash kerak. Shuning uchun ularning o'zgarishi diapazonining pastki va yuqori chegaralarini aniqlash kerak.

Shunday qilib, optimallashtirish dasturining "Yechim izlash" dialog oynasida biz quyidagi maqsadli algoritmni o'rnatishimiz kerak:

Maqsadli funktsiya maqsadli koeffitsientlar vektoriga kerakli o'zgaruvchan qiymatlar vektorining mahsulotiga teng

Kerakli o'zgaruvchan qiymatlar vektori uchun normallashtirilgan koeffitsientlar berilgan resurs vektorining qiymatidan oshmasligi kerak.

O'zgaruvchan qiymatlar tizimning boshlang'ich elementlari sonining belgilangan chegaralarida bo'lishi kerak

Tizimning dastlabki elementlari soni

Belgilangan resurs turlari soni

Dastur salbiy natijalar haqida xabarni ko'rsatganda, yechimni disk raskadrovka qilish kerak (1.7-rasm):

Guruch. 1.7.

• agar maqbul yechim olinmasa, manba ma'lumotlar modelini sozlang;
• qabul qilinmasa optimal yechim, keyin qo'shimcha cheklovlar kiriting.

Dastur muammolari optimal yechim faqat haqiqiy muammoning modeli uchun, muammoning o'zi uchun emas. Modelni qurishda real vaziyat haqida turli soddalashtiruvchi taxminlar qilingan. Bu tizim parametrlari va maqsad o'rtasidagi haqiqiy miqdoriy munosabatlarni taxminan ko'rsatib, jarayonni rasmiylashtirishga imkon berdi. Va agar haqiqiy parametrlar modelga kiritilganlardan farq qilsa, unda yechim qanday o'zgaradi? Buni aniqlash uchun boshqaruv qarorini qabul qilishdan oldin namunaviy yechim tahlili o'tkaziladi.

Tahlil optimal yechim, dasturga kiritilgan, iqtisodiy jarayonlarni matematik modellashtirishning yakuniy bosqichini ifodalaydi. Modelning jarayonga muvofiqligini, shuningdek, optimal echimning ishonchliligini chuqurroq tekshirish imkonini beradi. U ma'lumotlarga asoslanadi optimal yechim va "Yechim izlash" bo'limida berilgan hisobotlar. Ammo u boshqaruv qarorini qabul qilishdan oldin iqtisodiy nuqtai nazardan rejaning an'anaviy tahlilini istisno qilmaydi yoki almashtirmaydi.

Iqtisodiy tahlil quyidagi maqsadlarga ega:

• model parametrini o'zgartirishda butun tizimda va uning elementlarida yuzaga kelishi mumkin bo'lgan oqibatlarni aniqlash;
• muammoning individual parametrlaridagi o'zgarishlarga optimal rejaning barqarorligini baholash: agar u ko'pchilik parametrlardagi o'zgarishlarga barqaror bo'lmasa, uni amalga oshirish va hisoblangan optimalga erishish kafolati kamayadi;
• tuzatishlar yordamida muammoni dastlabki asosdan qayta yechmasdan, variantli hisob-kitoblarni amalga oshirish va yangi reja variantlarini olish.

Mumkin bo'lgan tahlil usullari 1.8-rasmdagi diagrammada keltirilgan.

Optimal yechim olingandan keyin olingan hisobotlar asosida tahlil qilinadi. Barqarorlik tahlili- individual model parametrlari o'zgarishining optimal yechim ko'rsatkichlariga ta'sirini o'rganish. Limit tahlili- optimal rejadagi ruxsat etilgan o'zgarishlarni tahlil qilish, bunda reja optimal bo'lib qoladi.

Iqtisodiy qabul qilish mas'uliyatini hisobga olgan holda boshqaruv qarori, menejer natijada olingan optimal reja yagona to'g'ri ekanligiga ishonch hosil qilishi kerak. Buning uchun modelga asoslanib, quyidagi savollarga javob olish kerak:

• "Agar nima bo'ladi ..."
• "Buning uchun nima kerak ..."

Birinchi savolga javob berish uchun tahlil deyiladi variantni tahlil qilish; ikkinchi savolga javob berish uchun tahlil deyiladi moslashtirilgan yechimlar.

Variantlarni tahlil qilish quyidagi turlarda bo'lishi mumkin:

• Parametrik- ma'lum bir parametrning turli qiymatlari uchun muammoni hal qilishdan iborat bo'lgan tahlil.
• Strukturaviy tahlil- optimallashtirish muammosining yechimi cheklovlarning boshqa tuzilishi ostida qidirilganda.
• Ko'p mezonli tahlil turli maqsadli funksiyalardan foydalangan holda muammoning yechimidir.
• Shartli dastlabki ma'lumotlar bilan tahlil qilish- muammoni hal qilish uchun ishlatiladigan dastlabki ma'lumotlar qo'shimcha shartlarga rioya qilishga bog'liq bo'lganda.

Tahlildan so'ng natijalar grafik shaklda taqdim etilishi va aniq iqtisodiy vaziyatni hisobga olgan holda qarorlar qabul qilish bo'yicha tavsiyalar bilan hisobot tuzilishi kerak.

Hozirgi vaqtda iqtisod, moliya va menejmentga oid ixtisosliklarning ta'lim dasturiga "Optimal qarorlar usullari" deb nomlangan fan kiritilgan. Ushbu fan doirasida talabalar optimallashtirish, operatsiyalarni tadqiq qilish, qaror qabul qilish va modellashtirishning matematik tomonini o'rganadilar. asosiy xususiyat Ushbu fan matematik usullarni iqtisodiy muammolarni hal qilishda qo'llash bilan birgalikda o'rganish bilan belgilanadi.

Optimallashtirish vazifalari: umumiy ma'lumot

Agar umumiy holatni ko'rib chiqsak, optimallashtirish masalasining ma'nosi ma'lum bir cheklash sharoitida maqsad funktsiyasini maksimal darajaga tushiradigan (minimallashtiradigan) optimal echim deb ataladigan echimni topishdir.

Funktsiyalarning xususiyatlariga ko'ra, optimallashtirish muammolarini ikki turga bo'lish mumkin:

• chiziqli dasturlash masalasi (barcha funksiyalar chiziqli);
• chiziqli bo'lmagan dasturlash muammosi (kamida bitta funktsiya chiziqli emas).

Optimallashtirish masalalarining alohida holatlari fraksiyonel-chiziqli, dinamik va stokastik dasturlash masalalari hisoblanadi.

Eng ko'p o'rganilgan optimallashtirish muammolari chiziqli dasturlash muammolari (LPP) bo'lib, ularning echimlari faqat butun son qiymatlarni oladi.

PPP: shakllantirish, tasniflash

Chiziqli dasturlash masalasi umumiy holatda chiziqli funksiyaning ma’lum chiziqli cheklovlar ostida minimal (maksimal) ni topishdan iborat.

Umumiy ZLP - bu shakl muammosi

cheklovlar ostida

qayerda o‘zgaruvchilar, berilgan haqiqiy sonlar, maqsad funksiyasi, masala rejasi, (*)-(***) cheklovlar.

ZLP ning muhim xususiyati shundan iboratki, maqsad funksiyaning ekstremumiga mumkin bo'lgan yechimlar mintaqasi chegarasida erishiladi.

Optimal yechim usullarining amaliy iqtisodiy qo'llanilishi quyidagi turdagi muammolarni hal qilishda topiladi:

• aralashmalar bilan bog'liq muammolar (ya'ni, mahsulotlar tarkibini rejalashtirish);
• ishlab chiqarishni rejalashtirishda resurslarni optimal taqsimlash muammolari;

PAP: misollar

Aralash muammosi

Aralashmalar muammosini hal qilish kerakli xususiyatlarga ega aralashmani ta'minlaydigan ma'lum boshlang'ich materiallardan iborat eng arzon to'plamni topishdan iborat.

Resurslarni taqsimlash muammosi

Kompaniya ishlab chiqaradi n ishlab chiqarishni talab qiladigan turli xil mahsulotlar m har xil turdagi resurslar. Foydalanilgan resurslarning zaxiralari cheklangan va mos ravishda miqdori b 1, b 2,…, b m c.u. Bundan tashqari, texnologik koeffitsientlar ma'lum a ij, bu qancha birliklarni ko'rsatadi i-bir birlik mahsulot ishlab chiqarish uchun resurs talab qilinadi j-th turi (). Korxonaning mahsulotni sotishdan oladigan foydasi j-th turi, miqdori c j pul birliklari Mahsulot ishlab chiqarish rejasini tuzish kerak, uni amalga oshirish jarayonida korxonaning foydasi eng katta bo'ladi.

Aralashmalar va resurslarni taqsimlash bilan bog'liq masalalar ko'pincha jadval shaklida yoziladi.

Resurslar	Ehtiyojlar			Zaxiralar
	B 1	…	Bn
A 1				b 1
…				…
Am				b m
Foyda	c 1	…	c n

Aralashma va resurslarni taqsimlash muammolarini bir necha usul bilan hal qilish mumkin:

• grafik usul (o'zgaruvchilar oz sonli bo'lsa matematik model);
• simpleks usuli (agar matematik modeldagi o'zgaruvchilar soni ikkitadan ko'p bo'lsa).

Transport muammosi ma'lum bir o'ziga xos tuzilishga ega bo'lgan vazifalar sinfini anglatadi. Eng oddiy transport muammosi - bu mahsulotni jo'natish punktlaridan belgilangan manzilga tashish muammosi minimal xarajatlar barcha mahsulotlarni tashish uchun.

Aniqlik va idrok etish qulayligi uchun transport muammosining holati odatda quyidagi jadvalda yoziladi:

Umuman olganda, transport muammosini hal qilish bir necha bosqichda amalga oshiriladi:

• I bosqich: dastlabki ma'lumotnoma rejasini qurish;
• II bosqich: mos yozuvlar rejasini optimalligini tekshirish;
• III bosqich: agar u maqbul bo'lmasa, mos yozuvlar rejasini aniqlashtirish.

Dastlabki mos yozuvlar rejasini olishning bir necha usullari mavjud, masalan, shimoli-g'arbiy burchak usuli, Vogel usuli va minimal xarajat usuli.

Rejaning optimalligi potentsial usul yordamida tekshiriladi:

- ishg'ol qilingan hujayralar uchun,
- band bo'lmagan hujayralar uchun.

Agar reja optimal bo'lmasa, unda tsikl quriladi va transport qayta taqsimlanadi.

Xulosa

Bitta maqola doirasida optimal echim usullarining butun nazariyasi va amaliyotini qamrab olishning iloji yo'q, shuning uchun faqat ushbu fan, muammolar va ularni hal qilish usullari haqida umumiy tasavvur berishga imkon beradigan ba'zi fikrlar ko'rib chiqiladi.

Bundan tashqari, optimallashtirish muammolari bo'yicha olingan echimlarni tekshirish uchun siz MS Excel paketining "Yechimlarni qidirish" plaginidan juda samarali foydalanishingiz mumkinligini ta'kidlash yaxshi. Ammo bu boshqa hikoya, aslida optimallashtirish muammolarini hal qilish usullarini batafsil ko'rib chiqish.

Bu erda optimal echim usullarini o'rganish uchun bir nechta darsliklar mavjud:

1. Bandi B. Chiziqli dasturlash asoslari: Trans. ingliz tilidan – M.: Radio va aloqa, 1989. – 176 b.
2. Kremer N.Sh. Iqtisodiyotda operatsiyalar tadqiqoti: Proc. universitetlar uchun qo'llanma / N.Sh. Kremer, B.A. Putko, I.M. Trishin, M.N. Fridman; Ed. prof. N.Sh. Kremer. – M.: BIRLIK, 2005. – 407 b.

Maxsus optimallashtirish usullarini hal qilish

Biz optimal yechim usullaridan foydalangan holda har qanday muammolarni hal qilishda yordam bera olamiz. Muammolarni hal qilish uchun veb-saytimizda buyurtma berishingiz mumkin. Siz faqat oxirgi muddatni ko'rsatishingiz va faylni vazifa bilan biriktirishingiz kerak. buyurtmangiz bepul.

Chiziqli dasturlash oʻzgaruvchilar chiziqli tenglamalar yoki chiziqli tengsizliklar koʻrinishidagi chekli sonli cheklovlarni qondirish sharti bilan cheklangan sonli oʻzgaruvchilarning chiziqli funksiyasining minimal yoki maksimalini topish usullarini oʻrganuvchi matematikaning boʻlimidir.

Shunday qilib, umumiy chiziqli dasturlash muammosini (GLP) quyidagicha shakllantirish mumkin.

Haqiqiy o'zgaruvchilar qiymatlarini toping maqsad funktsiyasi

koordinatalari qanoatlantiradigan nuqtalar to'plamida minimal qiymatni oladi cheklovlar tizimi

Ma'lumki, buyurtma qilingan qiymatlar to'plami n o'zgaruvchilar , , … n o'lchovli fazodagi nuqta bilan ifodalanadi. Quyida biz ushbu nuqtani belgilaymiz X=( , , … ).

Matritsa shaklida chiziqli dasturlash masalasini quyidagicha shakllantirish mumkin:

, A- o'lcham matritsasi,

Nuqta X=( , , … ), barcha shartlarni qanoatlantiruvchi deyiladi haqiqiy nuqta . Barcha ruxsat etilgan nuqtalar to'plami deyiladi tegishli maydon .

Optimal yechim (optimal reja) chiziqli dasturlash masalasi yechim deb ataladi X=( , , … ), ruxsat etilgan mintaqaga tegishli va chiziqli funktsiya Q optimal (maksimal yoki minimal) qiymatni oladi.

Teorema. Chiziqli dasturlash masalasining cheklashlar tizimining barcha mumkin bo'lgan yechimlari to'plami qavariqdir.

Nuqtalar to'plami deyiladi qavariq , agar u istalgan ikkita nuqta bilan birgalikda ularning ixtiyoriy qavariq chiziqli birikmasini o'z ichiga olsa.

Nuqta X chaqirdi qavariq chiziqli birikma shartlar bajarilgan taqdirda ball

Chiziqli dasturlash muammosining barcha mumkin bo'lgan yechimlari to'plami qavariq ko'p burchakli mintaqa bo'lib, biz bundan buyon uni chaqiramiz. eritmalar ko'p yuzli .

Teorema. Agar ZLP optimal yechimga ega bo‘lsa, u holda maqsad funksiyasi eritma ko‘pburchak cho‘qqilaridan birida maksimal (minimal) qiymatni oladi. Agar maqsad funksiyasi bir nechta nuqtada maksimal (minimal) qiymatni qabul qilsa, u holda bu qiymatni ushbu nuqtalarning qavariq chiziqli birikmasi bo'lgan har qanday nuqtada oladi.

Tizimning ko'plab echimlari orasida m yechimlar ko'p yuzlisini tavsiflovchi chiziqli tenglamalar, asosiy yechimlar deb ataladiganlar ajratiladi.

Tizimning asosiy yechimi m n o'zgaruvchili chiziqli tenglamalar yechim bo'lib, unda hammasi n-m asosiy bo'lmagan o'zgaruvchilar nolga teng. Chiziqli dasturlash masalalarida shunday yechimlar deyiladi qabul qilinadigan asosiy echimlar (mos yozuvlar rejalari).

Teorema. Chiziqli dasturlash masalasining har bir ruxsat etilgan asosiy yechimi yechim ko‘p yuzlining cho‘qqisiga to‘g‘ri keladi va aksincha, yechim ko‘p yuzlining har bir cho‘qqisiga yo‘l qo‘yilgan asosiy yechim mos keladi.

Yuqoridagi teoremalardan muhim xulosa kelib chiqadi:

Agar chiziqli dasturlash muammosi optimal yechimga ega bo'lsa, u holda u hech bo'lmaganda amalga oshirish mumkin bo'lgan asosiy echimlardan bittasiga to'g'ri keladi.

Binobarin, chiziqli dasturlash masalasi maqsadining chiziqli funksiyasining optimalini uning amalga oshirilishi mumkin bo'lgan asosiy yechimlarining chekli soni orasidan izlash kerak.