1-Mavzu: Butun sonli chiziqli programmalash modellari

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
L = 1 x 1 + bilan 2 x 2 + ... bilan n x n.
Shartlar ostida (aniqlik uchun tenglamalarda nol va bitta koeffitsientlar saqlanadi):
1x 1+ 0x 2 + ... 0x m + a 1m + 1x m + 1 ... + a 1n x n = b 1;
0x 1 + 1x 2 +… 0x m + a 2m + 1x m + 1 ... + a 2n x n = b 2;
……………………………………………
0x 1+ 0x 2 + ... 1x m + a mm + 1x m +1 ... + a mn x n = b m.
Ushbu tenglamalar tizimi allaqachon tayyor asosga ega, chunki har bir cheklovlar tenglamasi boshqa tenglamalarda, ya'ni o'zgaruvchilar koeffitsientlarida mavjud bo'lmagan birga teng koeffitsientli noma'lumni o'z ichiga oladi. NS 1 , NS 2 …, x m identifikatsiya matritsasini yaratishingiz mumkin.
Keling, asosiy o'zgaruvchilar uchun tenglamalarni yechamiz:
x 1 = b 1 - (a 1m + 1 x m + 1 ... + a 1n x n);
x 2 = b 2 - (a 2m + 1 x m + 1 ... + a 2n x n);
………………………………
x m = b m - (a mm + 1x m + 1 ... + a mn x n),
va maqsad funksiyasini erkin o‘zgaruvchilar bilan ifodalaymiz, ularning ifodalarini asosiy o‘zgaruvchilar o‘rniga erkin o‘zgaruvchilar bilan almashtiramiz:
L = c 1 b 1 + c 2 b 2 + cmbm - (c 1 a 1m + c 2 a 2m + 1 +… + cma mn + 1) x m + 1 -… - (c 1 a 1n + c 2 a 2n +… + cma mn) xn… + cnx n ..
O'zgaruvchilar x 1, x 2 ..., x m, ularning yordami bilan birinchi asosiy reja topilgan, asosiy, qolganlari esa x m +1, x m +2, ... x n - ozod. Tizimdagi tenglamalar qancha bo'lsa, har doim ko'p asosiy o'zgaruvchilar bo'lishi kerak. Salbiy bo'lmagan shartga asoslanib, erkin o'zgaruvchilarning eng kichik qiymati nolga teng. Tenglamalar tizimining olingan asosiy yechimi uning dastlabki ruxsat etilgan yechimidir, ya'ni. x 1 = b 1, x 2 = b 2, ... x m = b m, x m +1 = 0,..., x n = 0.
Bu yechim maqsad funksiyaning qiymatiga mos keladi
L = c 1 b 1 + c 2 b 2 + ... c m b m.
Dastlabki yechim optimallik uchun sinovdan o'tkaziladi. Agar u optimal bo'lmasa, bazisga erkin o'zgaruvchilarni kiritish orqali maqsad funktsiyasining kichikroq qiymatiga ega bo'lgan quyidagi mumkin bo'lgan echimlar topiladi. Buning uchun bazisga kiritilishi kerak bo'lgan erkin o'zgaruvchini, shuningdek, bazisdan olinishi kerak bo'lgan o'zgaruvchini aniqlang. Keyin oldingi tizimdan keyingi ekvivalent tizimga o'tadi. Bu simpleks jadvallari yordamida amalga oshiriladi. Masalani yechish maqsad funksiyaning optimal qiymati olinmaguncha davom etadi.
Simpleks jadvallar quyidagicha tuzilgan (3.1-jadvalga qarang). Barcha o'zgaruvchilar jadvalning yuqori qismida joylashgan. NS 1 , NS 2 …, x n va koeffitsientlar c j, ular bilan mos keladigan o'zgaruvchilar maqsad funktsiyasiga kiritilgan. Birinchi ustun c i bazisga kiritilgan o'zgaruvchilar uchun maqsad funksiya koeffitsientidan iborat. Undan keyin asosiy o'zgaruvchilar ustuni va tenglamalarning erkin shartlari keladi. Jadvalning qolgan ustunlari elementlari tenglamalar tizimiga kiritilgan o'zgaruvchilarning koeffitsientlarini ifodalaydi. Shunday qilib, jadvalning har bir qatori asosiy o'zgaruvchiga nisbatan echilgan tizim tenglamasiga mos keladi. Jadvalda, shuningdek, berilgan asos uchun maqsad funktsiyasiga mos keladigan reja varianti ko'rsatilgan.
Jadvalning pastki qatori deyiladi indeks... Uning har bir elementi (bahosi) ∆ j aniqlash
∆j = z j - c j,
qayerda c j- maqsad funksiyadagi mos o'zgaruvchilar uchun koeffitsientlar; z j - asosiy o'zgaruvchilar uchun maqsad funktsiyasi koeffitsientlarining tegishli o'zgaruvchilar - elementlar bo'yicha mahsuloti yig'indisi j- Jadvalning ustuni.
stol 3.1