1-Mavzu: Butun sonli chiziqli programmalash modellari

3.1-misol. Omborda 300 tonna penobeton mahsulotlari, 200 tonna po‘lat bor. Avtomobil kompaniyasi ushbu mahsulotlarni qurilayotgan ob'ektga etkazib berishi kerak. Avtomobil kompaniyasida KamAZ - 5320 va yuk mashinalari mavjud
ZIL-4314. Bir safar uchun KamAZ-5320 6 tonna ko'pikli beton va 2 tonna po'latni etkazib berishi mumkin va sayohatdan olinadigan foyda 4 ming rublni tashkil qiladi. ZIL-4314 bir safarda 2 tonna ko'pikli beton va 4 tonna po'lat etkazib beradi, sayohatdan olingan foyda 6 ming rublni tashkil qiladi. Avtotransportni avtomobil kompaniyasi uchun eng katta foydani ta'minlaydigan tarzda tashkil qilish kerak.
Keling, masalaning matematik modelini tuzamiz. KamAZ-5320 haydovchilarining kerakli sonini x 1 bilan belgilaymiz NS 2 ta ZIL-4314 haydovchilarining kerakli soni.
Tonna ko'pikli beton buyumlarning umumiy tashish hajmi 6 tani tashkil qiladi x 1 + 2x 2, va po'latdan 2 x 1 + 4x 2... Mavjud narsalar soniga qarab tashish cheklovlari - 6 ta x 1 + 2x 2 ≤ Ko'pikli beton uchun 300t va 2 x 1 + 4x 2 ≤ po'lat uchun 200t.
Umumiy foyda ming rublda 4 sifatida ifodalanadi NS 1 + 6NS 2, uni maksimal darajada oshirish kerak va ko'rib chiqilayotgan muammoda optimallik mezoni hisoblanadi. Shunday qilib, masalaning matematik modeli quyidagicha ko'rinadi. Maqsad funktsiyasini maksimal darajada oshirish kerak
L = 4x 1 + 6x 2 → sharoitlarda maksimal: 6 x 1 + 2x 2 ≤ 300; 2x 1 + 4x 2 ≤ 200; x 1 ≥ 0;x 2 ≥ 0.
6-tenglamani ko'rib chiqing x 1 + 2x 2 = 300. Ushbu tenglama bilan tasvirlangan to'g'ri chiziqni qurish uchun biz ushbu to'g'ri chiziqda yotgan ikkita nuqtani topamiz. Da x 1= 0 to'g'ri chiziq tenglamasidan 2 ni topamiz x 2 = 300, bundan x 2 = 150. Demak, koordinatalari (0,150) bo'lgan A nuqta kerakli to'g'ri chiziqda yotadi. Da x 2= 0, bizda 6 bor x 1= 300, bundan x 1 = 50 va nuqta D koordinatalari bilan (50,0) ham qidirilayotgan chiziqda. Ushbu ikkita nuqta orqali to'g'ri chiziq torting AD(3.1-rasm).
Chiziqli tengsizlik 6 x 1 + 2x 2 ≤ 300 - qurilgan to'g'ri chiziqning bir tomonida joylashgan yarim tekislik 6 x 1 + 2x 2 = 300. Kerakli yarim tekislik nuqtalari shu to'g'ri chiziqning qaysi tomonida joylashganligini bilish uchun 6 ni almashtiramiz. x 1 + 2x 2 ≤ Chegara chizig'ida yotmaydigan har qanday nuqtaning 300 koordinatasi. Masalan, kelib chiqishi 0- (0,0). Uning uchun tengsizlik 6 ∙ 0 + 2 ∙ 0 = 0< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой AD va rasmda. 3.1 soyali.
Tenglama 2 x 1 + 4x 2= 200, biz ikkita nuqtada quramiz. Da x 1 = 0 4x 2 = 200, qayerdan x 2 = 50. Keyin nuqta E koordinatalariga ega (0,50) va kerakli to'g'ri chiziqqa tegishli. Da x 2= 0, 2x 2 = 200, nuqta bilan koordinatalari (100,0) bilan berilgan chiziqda joylashgan. Nuqta koordinatalarini tengsizlikka almashtirish bilan(0,0), biz 2 ∙ 0 + 4 ∙ 0 = 0 ni olamiz< 200. Значит, начало координат находится в области допустимых значений от прямой 2x 1+ 4x 2= 200.
Muammoli cheklovlar tizimi rejalarni talab qiladi ( x 1; x 2) barcha to'rtta tengsizlikni qanoatlantiring, ya'ni ruxsat etilgan dizaynlar nuqtalar ( x 1; x 2) bir vaqtning o'zida barcha to'rtta yarim tekislikda bo'lishi kerak. Bu talab faqat poligonning ichida va chegarasida joylashgan nuqtalar tomonidan qondiriladi. OEKD, bu mumkin bo'lgan yechimlar ko'pburchagi.
Mumkin yechimlar ko‘pburchagining uchlari nuqtalardir O, E, K, D, chiziq segmentlari OE, EK, KD, OD- uning qovurg'alari. Ko'pburchakning istalgan nuqtasi OEKD muammoning barcha shartlarini qondiradigan rejasidir. Ko'pburchakning uchlari ikkita to'g'ri chiziqning kesishmasidan hosil bo'ladi va masalaning asosiy rejalariga mos keladi, ular orasida eng yaxshi (optimal) reja mavjud. Shunday qilib, mumkin bo'lgan echimlar ko'pburchagida qanchalik ko'p tayanch rejalar bo'lsa, shuncha ko'p bo'ladi.
Maqsad funktsiyasi uchun aniq geometrik tasvirni ham olish mumkin. L = 4x 1 + 6x 2... Keling, masalan, maqsad funktsiyasining ba'zi qiymatini aniqlaymiz L= 120. tenglik 4 x 1 + 6x 2 = 120 nuqta orqali chiziqni belgilaydi V koordinatalari (x 1 = 0; x 2 = 20) va nuqta bilan L koordinatalari bilan (( NS 1 = 30; NS 2 = 0). Bo'lim BL poligon ichida joylashgan OEKD... Shuning uchun, ushbu segmentning barcha rejalari (nuqtalari) uchun maqsad funktsiyasining qiymati bir xil va 120 ga teng. Maqsad funktsiyasiga boshqa qiymatlarni belgilash orqali biz parallel chiziqlarni olamiz, ular deyiladi. darajali chiziqlar maqsad funktsiyasi.
To'g'ri harakat qilish L o'ziga bir yo'nalishda parallel ravishda biz maqsad funktsiyasining ortishiga erishamiz va teskari yo'nalishda - uning kamayishi. Ushbu misolda to'g'ri chiziqning harakati BL o'ng tomonda biz maksimal darajaga ko'taradigan maqsad funktsiyasining o'sishini aniqlaydi. Biz buni to'g'ridan-to'g'ri bajaramiz BL mumkin bo'lgan yechimlar ko'pburchagi bilan kamida bitta umumiy nuqtaga ega bo'ladi OEKD... Anjirdan. 3.1, shundan kelib chiqadiki, maqsad funktsiyasi darajasining to'g'ri chizig'i kesib o'tgan oxirgi nuqta nuqta bo'ladi TO... Bu shuni anglatadiki, nuqta TO optimal vazifa rejasini belgilaydi.
Darajali chiziqqa perpendikulyar ko'tarilish yo'nalishi deyiladi eng katta o'sish yo'nalishi maqsad funktsiyasi va uning maksimal o'sishini aniqlaydi. Ushbu yo'nalish chizilgan darajali chiziqlarsiz o'rnatilishi mumkin. Buning uchun eksalarda kerak x 1 va x 2 maqsad funksiya koeffitsientlariga teng segmentlarni keyinga qoldirish va ulardan koordinatalar sifatida maqsad funksiyasining eng katta ortishi vektorini qurish. Matematikada u deyiladi gradient va daraja bilan belgilang. Funktsiya uchun gradient L = 4x 1 + 6x 2 vektor bo'ladi n| 4; 6 | ... Uning qurilishi qulayligi uchun biz koordinatalarni, masalan, 10 barobarga oshiramiz, ya'ni. n | 40; 60 | ... Maqsad funksiyasining gradientini tuzamiz L, buning uchun koordinatali (40; 60) nuqtani koordinatali nuqta bilan bog'laymiz. Maqsad funksiyasi darajasidagi chiziqlar gradient yo‘nalishiga perpendikulyar chizilgan.
Shunday qilib, u yoki bu nuqta aniqlandi TO o'zgaruvchilarning qiymatlari berilgan nuqtaning koordinatalariga mos keladigan muammoning optimal rejasini aniqlaydi. Koordinatalarni o'rnatish uchun ushbu cho'qqini tashkil etuvchi to'g'ri chiziqlar tenglamalari tizimini echish kerak:
6x 1 + 2x 2= 300;
2x 1 + 4x 2= 200.
Ikkinchi tenglamani 3 ga ko'paytirish orqali x 1 da koeffitsientlarni tenglashtiramiz va ikkinchi tenglamadan birinchisini ayiramiz. Biz 10 ni olamiz x 2= 300,x 2 = 30. Har qanday tenglamada, masalan, birinchisida x 2 = 30 qiymatini almashtirib, biz qiymatni aniqlaymiz. NS 1:
6x 1+ 2NS · 30 = 300,
qayerdan 6 x 1 = 300 - 60 = 240, shuning uchun x 1 = 40.
Shunday qilib, eng katta foyda olish uchun avtokorxona KamAZ-5320da 40 ta, ZIL-4314da 30 ta sayohatni bajarishi kerak. Bu holda maksimal foyda bo'ladi