Avzu: chiziqli modellar

L = 4x 1 + 6x 2= 4 40 + 6 30 = 340 ming rubl.
Ko'rib chiqilgan misol va ikkita o'zgaruvchi bilan optimallashtirish muammosining geometrik talqini asosida quyidagi xulosalar chiqarish mumkin:
1) ikki o'lchovli fazoda mumkin bo'lgan echimlar mintaqasi ko'pburchakdir;
2) ko'pburchakning har bir tomoni nolga teng bitta o'zgaruvchining qiymatiga mos keladi;
3) mumkin bo'lgan echimlar ko'pburchagining har bir tepasi nolga teng bo'lgan ikkita o'zgaruvchining qiymatlariga mos keladi;
4) maqsad funktsiyasining har bir qiymatiga to'g'ri chiziq mos keladi;
5) masalaning optimal yechimi ko‘pburchak cho‘qqisiga to‘g‘ri keladi, bunda maqsad funksiyasi optimal qiymatga ega bo‘ladi va bu cho‘qqining koordinatalari optimal o‘zgaruvchilar hisoblanadi.
Umuman olganda, optimallashtirish masalalari xuddi shunday geometrik talqinga ega. Muammoli rejalar to'plami cho'qqilari mos yozuvlar rejalariga mos keladigan ko'pburchakni ifodalaydi. Masalani yechishda maqsad funksiyasining katta qiymatiga ega bo‘lgan ko‘pburchakning bir cho‘qqisidan boshqasiga uning optimal qiymati olinmaguncha o‘tish amalga oshiriladi. E'tibor bering, optimallashtirish usullarining samaradorligi aniq cho'qqilarni qidirish (iteratsiya) faqat maqsad funktsiyasining eng katta o'sishi yo'nalishida amalga oshirilishida. Shuning uchun, juda ko'p sonli barcha cho'qqilar emas, balki faqat ekstremalga yaqinroq bo'lganlar hisobga olinadi.
Optimallashtirish masalalari sinfini aniqlashda va uni yechish usulini tanlashda amalga oshirilishi mumkin bo‘lgan yechimlar to‘plamining qavariq yoki qavariq bo‘lmaganligini, chiziqli yoki chiziqli bo‘lmagan maqsad funksiya ekanligini bilish kerak.
Ta'rifga ko'ra, to'plam chaqiriladi qavariq agar har qanday ikkita nuqta uchun ushbu nuqtalarni bog'laydigan butun segment ushbu to'plamga tegishli bo'lsa. Qavariq to'plamlarga misol sifatida, masalan, segment (3.2-rasm, a), aylana shaklidagi tekislik, kub, parallelepiped, shuningdek, uning har bir tomonining bir tomonida to'liq joylashgan ko'pburchaklar mavjud. , va boshqalar.
Shaklda. 3.2b qavariq bo'lmagan to'plamlarni tasvirlaydi. Qavariq bo'lmagan to'plamlarda AB segmentining ko'rib chiqilayotgan to'plamga tegishli bo'lmagan kamida ikkita nuqtasini ko'rsatish mumkin.
3.3. Simpleks usuli
Simpleks usuli Chiziqli dasturlash masalalarini hal qilishning keng tarqalgan usuli. Usul o'z nomini "simpleks" so'zidan oldi, bu eng oddiy konveks ko'pburchakni bildiradi, uning uchlari soni har doim bo'shliq o'lchamidan bittaga ko'p. Simpleks usuli AQSHda 1940-yillarning oxirida matematik J.Dansig tomonidan ishlab chiqilgan.
Simpleks usuli (3.1) tipidagi kanonik chiziqli tenglamalar tizimining manfiy bo'lmagan asosiy yechimini olish, maqsad funktsiyasini (3.3) keyinchalik minimallashtirish (maksimallashtirish) va shu tarzda qidirilayotgan o'zgaruvchilarning optimal qiymatlarini topishni o'z ichiga oladi. x 1, x 2 ... x n.
Simpleks usulining g'oyasi shundan iboratki, hisoblash jarayonida birinchi asosiy yechimdan ikkinchi, uchinchi va boshqalarga ketma-ket o'tish. deb atalmish orqali oddiy transformatsiyalar. O'zgartirishlar simpleks jadvallar shaklida amalga oshiriladi, bu esa hisob-kitoblarni sezilarli darajada soddalashtiradi va tezlashtiradi.
Chiziqli tenglamalar tizimining manfiy bo'lmagan asosiy yechimlarini olish uchun noma'lumlarni yo'q qilish jarayonini o'tkazish kerak, shunda tenglamalarning erkin shartlari jarayonning barcha bosqichlarida manfiy bo'lmaydi. Bunday holda, quyidagi qoidaga amal qilish kerak: yangi asosiy o'zgaruvchi sifatida kamida bitta ijobiy koeffitsientga ega bo'lgan har qanday erkin o'zgaruvchi olinadi; o'zgaruvchi tenglamalarning erkin shartlarining bazisga kiritilgan o'zgaruvchi uchun tenglamalarning tegishli musbat koeffitsientlariga eng kichik nisbatiga mos keladigan asosdan olinadi. Bunday transformatsiyalar deyiladi simpleks konvertorlari.
Bu juda muhim, chunki ko'rsatilgan o'zgaruvchining diapazonini aniqlash va uning maksimal qiymatini almashtirish o'rniga, boshqa erkin o'zgaruvchilarning nol qiymatlarida har qanday erkin o'zgaruvchining mumkin bo'lgan eng katta qiymatiga mos keladigan ma'lum bir salbiy bo'lmagan yechimni topish uchun. mumkin bo'lgan qiymatni umumiy yechimga kiritish uchun ushbu o'zgaruvchini asosiy sifatida qabul qilish va tizimni yangi asosga o'tadigan simpleks transformatsiyasiga topshirish kifoya, bu esa hisob-kitoblarni sezilarli darajada osonlashtiradi.
Simpleks jadvallari yordamida hisob-kitoblar qulay tarzda amalga oshiriladi. Bir jadvaldan ikkinchisiga o'tish bir iteratsiyaga, ya'ni bir asosdan ikkinchisiga o'tishga to'g'ri keladi, shu bilan birga maqsad funktsiyasining qiymati kamayadi. Muayyan miqdordagi iteratsiyalar uchun ular maqsad funktsiyasining optimal (minimal yoki maksimal) qiymati olinadigan asosga o'tadi. Simpleks usulini umumiy ko'rib chiqamiz.
Chiziqli dasturlashning umumiy muammosi - o'zgaruvchilari chiziqli tenglamalar tizimi bilan o'zaro bog'langan, manfiy bo'lmagan shartga bo'ysunadigan maqsad funktsiyasini minimallashtirish (maksimallashtirish).
Chiziqli shaklni minimallashtirish kerak bo'lsin