Algoritmlarni loyihalash fanidan mustaqil ishi

5.Chiziqli dasturlash masalasini yechishning grafik usuli.
Grafik usul ikki o'zgaruvchan chiziqli dasturlashni optimallashtirish uchun ishlatiladi. Agar muammoning ikkita qaror o'zgaruvchisi bo'lsa, grafik usul optimal yechimni topishning eng yaxshi usuli hisoblanadi. Bu usulda tengsizliklar to'plami cheklovlarga duchor bo'ladi. Keyin tengsizliklar XY tekisligida chiziladi. XY grafigida barcha tengsizliklar chizilganidan so'ng, kesishgan mintaqa amalga oshirilishi mumkin bo'lgan mintaqani aniqlashga yordam beradi. Mumkin bo'lgan hudud optimal yechimni ta'minlaydi, shuningdek, bizning modelimiz qanday qiymatlarni olishi mumkinligini tushuntiradi. Keling, bu yerda bir misolni ko'rib chiqaylik va chiziqli dasturlash tushunchasini yaxshiroq tushunamiz.
Misol:
Quyidagi cheklovlar uchun z = 5x + 3y ning maksimal va minimal qiymatini hisoblang.
x + 2y ≤ 14
3x – y ≥ 0
x – y ≤ 2
Yechim:
Uchta tengsizlik cheklovlarni ko'rsatadi. Belgilanadigan samolyotning maydoni mumkin bo'lgan hududdir.
Optimallashtirish tenglamasi (z) = 5x + 3y. z ning eng katta va eng kichik qiymatlarini beradigan (x,y) burchak nuqtalarini topishingiz kerak.
Avvalo, har bir tengsizlikni yeching.
x + 2y ≤ 14 ⇒ y ≤ -(1/2)x + 7
3x – y ≥ 0 ⇒ y ≤ 3x
x – y ≤ 2 ⇒ y ≥ x – 2
Mana yuqoridagi tenglamalar uchun grafik.

Endi burchak nuqtalarini topish uchun chiziqli tenglamalar tizimini yaratish uchun chiziqlarni juftlashtiring.
y = -(½) x + 7
y = 3x
Yuqoridagi tenglamalarni yechib, burchak nuqtalarini (2, 6) shaklida olamiz.
y = -1/2 x + 7
y = x – 2
Yuqoridagi tenglamalarni yechib, burchak nuqtalarini (6, 4) shaklida olamiz.
y = 3x
y = x – 2
Yuqoridagi tenglamalarni yechib, burchak nuqtalarini (-1, -3) shaklida olamiz.
Chiziqli tizimlar uchun optimallashtirish tenglamasining maksimal va minimal qiymatlari fizibilite mintaqasining burchaklarida yotadi. Shuning uchun, optimal echimni topish uchun siz faqat ushbu uchta nuqtani z = 3x + 4y ga ulashingiz kerak.
(2, 6):
z = 5(2) + 3(6) = 10 + 18 = 28
(6, 4):
z = 5(6) + 3(4) = 30 + 12 = 42
(–1, –3):
z = 5(-1) + 3(-3) = -5 -9 = -14
Demak, z = 42 ning maksimal qiymati (6, 4) va z = -14 ning minimali (-1, -3) da yotadi.
Raqamli misol: Duradgor muammosi
Maksimal 5X1 + 3 X2
Mavzu:
2 X1 + X2 £ 40
X1 + 2 X2 £ 50
va X1, X2 ikkalasi ham salbiy emas.

Izoh: Izo-qiymat maqsad funksiyasi yondashuviga bir nechta cheklovlar va cheklangan amalga oshirilishi mumkin bo'lgan hududga ega bo'lgan muammolar bilan alternativa mavjud. Birinchidan, barcha burchak nuqtalarini toping, ular ekstremal nuqtalar deb ataladi. Keyin, optimal qiymat va optimal yechimni topish uchun ekstremal nuqtalarda maqsad funktsiyasini baholang.
Shubhasiz, duradgorning ko'plab muqobil harakatlar to'plami bor. Biroq, to'rtta "ekstremal" variant:

Maqsad maksimallashtirish bo'lganligi sababli, yuqoridagi jadvaldan biz optimal qiymatni 110 deb o'qiymiz, agar duradgor X1 = 10 va X2 = 20 optimal strategiyasiga amal qilsa, olinadi.
E'tibor bering, duradgor muammosida konveks mumkin bo'lgan mintaqa burchak nuqtalarini yuqoridagi jadvalda ko'rsatilgan koordinatalar bilan ta'minlaydi.
Grafik usulning asosiy kamchiligi shundaki, u faqat 1 yoki 2 qaror
o'zgaruvchisi bilan LP muammolarini yechish bilan cheklangan. Biroq, biz grafik usullardan osongina kuzatadigan asosiy va foydali xulosa quyidagicha: