|
LLPni echishning grafik usulining algoritmi
salbiy bo'lmaganlik shartlarini qondiradigan ODS ni yarating .
Mumkin echimlarni toping (bajarish mumkin bo'lgan reja).
Optimal yechim toping.
Keling, taklif qilingan usulni misol bilan ko'rib chiqaylik.
3.1-misol.
Tikuvchi-furriyer ikki turdagi mahsulot ishlab chiqaradi: ayollar va erkaklar bosh kiyimlari. Bundan tashqari, u erkaklar uchun haftasiga 8 donadan, ayollar uchun esa 10 donadan ko'p bo'lmagan tikuv tikishi mumkin. Agar u ikkalasini birga tikishni boshlasa, u holda u 12 dan ortiq bosh kiyim tikmaydi. Har bir erkak shlyapasini sotish natijasida u 3 ming rubl, ayollarniki esa 2 ming rubl foyda oladi. Shlyapalar uchun astarlarni tikishdan foyda haftasiga 4 ming rublni tashkil qiladi. Eng katta foyda keltiradigan ishlab chiqarish hajmlarining shunday kombinatsiyasini toping.
Keling , masalaning matematik modelini tuzamiz. Tegishli ravishda erkaklar va ayollar shlyapalarining soni bilan belgilang , -
bir hafta tikuvchilarim . Uning imkoniyatlarini hisobga olgan holda biz quyidagilarni olamiz : ,
. Vazifaga ko'ra . Qabul qilingan belgida muammoning maqsadi - haftada maksimal foyda olish - quyidagi funktsiya sifatida ifodalanishi mumkin:
𝑥 1 va 𝑥 2 qiymatlarini aniqlashdan kelib chiqadiki, funksiya ikkita oʻzgaruvchiga ega va ifoda bilan beriladi.
𝐹maks _ = 4 + 2𝑥 1 + 3𝑥 2 ,
𝑥 1 + 𝑥 2 ≤ 12,
{ 𝑥 1 ≤ 8 va 𝑥 1 ,𝑥 2 ≥ 0 shartlarini qondirish
𝑥 2 ≤ 10
maksimal qiymat.
Keling, masalani grafik tarzda hal qilaylik.
Yechim:
Biz 𝑂𝑥 1 va 𝑂𝑥 2 o'qlarini quramiz , ular mos ravishda 𝑥 2 = 0 va 𝑥 1 = 0 tenglamalari bilan berilgan . Har qanday to'g'ri chiziqni qurish uchun ikkita nuqta etarli.
(0.0) va (10.0), (0.25) va (0,-15) nuqtalar orqali oʻqlarni quramiz. Buning uchun D12:D13 va D16:D17 kataklaridagi D ustuniga 𝑥 1 qiymatlarini va E12:E13 va E16: E17 kataklariga E ustuniga 𝑥 2 qiymatlarini o'rnating. .
MENU-dan "Qo'shish" bandini tanlang, so'ngra "Nuqta" turini va "Ko'rish" - grafiklardan birini tanlang.
Ko'rsatilgan oynada "Ma'lumotlar" bandini tanlang, "Ma'lumotlar manbasini tanlash" oynasida "Qo'shish" tugmasini bosing, paydo bo'lgan oynada "seriya nomi" - eksa 𝑂𝑥 1 ni kiriting, X qiymatlarini qo'shing. va Y qiymatlari va OK tugmasini bosing.
Xuddi shunday, 𝑂𝑥 2 o'qini tuzing .
Cheklashlar tizimidan birinchi to'g'ri chiziqni quramiz, uning tenglamasi cheklanishdagi tengsizlik belgisini aniq tenglik belgisi bilan almashtirish natijasida olinadi, ya'ni. 𝑥 1 + 𝑥 2 = 12.
Buning uchun A ustuniga A2 katakchadan boshlab 0,3 oraliqli 1 qiymatlar ketma-ketligini va birinchi qiymat nolga teng ( salbiy bo'lmagan shart bo'yicha) va 8 chegara qiymatini (ikkinchi cheklov) o'rnating . ) (3.1-rasm); tasvirning ravshanligi uchun o'zgartirish maydonini 𝑥 1 ga biroz oshirgan ma'qul, masalan , 9,3 gacha.
B2 katakka = 12-A2 formulasini yozing va markerni sudrab F ustunidagi kataklarning tegishli diapazoniga ko'chiring (3.1-rasm).
Guruch. 3.1
Cheklashlar tizimidan ikkinchi va uchinchi qatorlarni quramiz, uning tenglamasi cheklanishdagi tengsizlik belgisini aniq tenglik belgisi bilan almashtirish orqali olinadi , ya'ni . 𝑥 1 \u003d 8 - O𝑥 2 o'qiga parallel to'g'ri chiziq va 𝑥 2 \u003d 10 - O𝑥 1 o'qiga parallel to'g'ri chiziq .
To'g'ri chiziqlarni qurish o'qlarni qurishga o'xshash tarzda amalga oshiriladi (1-band)
(3.2-rasm).
3.2-rasm
Muammoning har bir cheklovi bilan aniqlangan yarim tekisliklarni topish.
Masalan, birinchi cheklov uchun yarim tekislikni ko'rib chiqamiz: 𝑥 1 + 𝑥 2 ≤ 12 .
Agar (0, 0) nuqtaning koordinatalarini ushbu tengsizlikka almashtirsak, u holda 0 ≤ 12 to'g'ri tengsizlikka ega bo'lamiz, ya'ni. berilgan tengsizlik shu nuqtani o'z ichiga oladi. Shuning uchun 1-to'g'ri chiziq uchun nuqta (0, 0) tomon yo'naltirilgan va ko'rib chiqilayotgan maydonning yo'nalishini ko'rsatadigan o'qlar chiziladi. Boshqa bog'liqliklar yuqoridagi tengsizliklarga mos ravishda xuddi shunday tuziladi.
Biz OABCD pentagonini olamiz - muammoni hal qilish uchun ruxsat etilgan soha mavjud.
Darajali liniyalarni qurish.
Darajali chiziqni qurish uchun siz 𝐹 max = 0 ni olishingiz mumkin, keyin maqsad funktsiyasi tenglamasi quyidagi ko'rinishga ega bo'ladi: 4 + 2𝑥 1 + +3𝑥 2 = 0, demak
x .
𝑥 2 o‘zgaruvchisini jadval qiymatlari sifatida ifodalaymiz. F2 katakchaga = - (4 + 2 A 2) / 3 formulasini yozing. Markerni sudrab olish usulidan foydalanib, ushbu formulani F ustunidagi kataklarning mos keladigan diapazoniga ko'chiring (3.1-rasm).
Maqsad funktsiyasining turli qiymatlarini o'rnatish orqali siz bir nechta darajali chiziqlarni qurishingiz mumkin.
Shaklda. 3.2 1 va 2-darajali chiziqlar nuqtali chiziq bilan chizilgan.
Maqsad funktsiyasi maksimal qiymatni oladigan yoki rejalar to'plamidagi funktsiyaning yuqoridan cheksizligini o'rnatadigan nuqtani (nuqtalarni) topish.
maksimalini topish masalasi hal qilinayotgan bo'lsa, maqsad funktsiyasini oshirish yo'nalishi bo'yicha yoki maqsadni kamaytirish yo'nalishi bo'yicha bir daraja chizig'idan boshqasiga "o'tish" kifoya qiladi. funktsiya, agar funktsiyaning minimalini topish masalasi hal qilinayotgan bo'lsa . 1-darajali chiziq yuqoriga ko'tariladi, ya'ni. kabi 2-darajali chiziqqa funksiyaning maksimalini topish masalasini yechish.
Bu holda B nuqtasi tanqidiy nuqta bo'lib chiqdi, ko'rib chiqilgan parallel chiziqlar oilasidan bir chiziq u orqali o'tadi ; Xuddi shu turkumdagi har qanday chiziqning istalgan nuqtasi B nuqtasidan "yuqorida" o'tib, maqsad funktsiyasiga kattaroq qiymat beradi, ammo bunday chiziqning ODD bilan umumiy nuqtalari bo'lmaydi. Va B nuqtasida ''pastdan'' o'tadigan chiziq amalga oshirilishi mumkin bo'lgan echimlar mintaqasini kesib o'tadi, lekin chiziqning barcha ushbu nuqtalarida Z funktsiyasining qiymati B nuqtadagi Z qiymatlaridan kichik bo'ladi. Natijada , B nuqtasi optimal rejadir (3.3-rasm).
B nuqtaning koordinatalarini aniqlaymiz, ya'ni maksimal foyda keltiradigan reja, optimal reja. Bu nuqta birinchi va uchinchi chiziqlarning kesishmasi bo'lganligi sababli, uning koordinatalari ushbu to'g'ri chiziqlar tenglamalarini qanoatlantiradi: 𝑥 1 + 𝑥 2 = 12 va 𝑥 2 = 10 va tenglamalar tizimining yechimi sifatida topiladi.
,
biz 𝑥 2 = 10 ni olamiz, 𝑥 1 = 2. Bizda B( 2, 10) - L1 va L3 chiziqlarning kesishish nuqtasi bor.
Ya'ni optimal reja X 0 = ( 2 , 10) ,
𝐹maks _ = 4 + 2 ∙ 2 + 3 ∙ 10 = 38 .
3.3-rasm
Keling, iqtisodiy muammoga qaytaylik.
Shunday qilib, haftada 2 ta erkaklar va 10 ta ayollar bosh kiyimlari ishlab chiqarilishi kerak. Maksimal foyda 38 ming rublni tashkil qiladi.
Do'stlaringiz bilan baham: |
