Chiziqli programmalash masalasinining geomatematik interpritatsiyasi

Chiziqli programmalash masalasini echishning grafik usuli

Chiziqli programmalash masalasini echishning grafik usuli asosan oʻzgaruvchilar soni ikkita va masala simmetrik formada berilgan holda ishlatiladi. Chiziqli programmalash masalasini ikki oʻzgaruvchi uchun quyidagicha yozish mumkin.

Bu masalaning mumkin boʻlgan echimlari sohasi qavariq koʻpburchak yoki qavariq koʻpqirra, yoki yagona nuqta boʻlishi mumkin. Tengsizliklarning har biri chiziqlar bilan chegaralangan yarim tekisliklarni ifodalaydi. Chiziqli funksiya ham ma’lum bir oʻzgarmas qiymatda toʻgʻri chiziqni ifodalaydi c₁x₁+c₂x₂=const.
Faraz qilaylik, mumkin boʻlgan echimlar qavariq koʻpburchakdan tashkil topgan boʻlsin. Echimlardan tashkil topgan qavariq toʻplamni hosil qilish uchun toʻgʻri chiziqlar bilan chegaralangan koʻpburchakni yasaymiz. Bu koʻpburchak ABCDEF boʻlsin (1.5.5-rasm). Maqsad funksiyasi X₁OX₂ tekislikda parallel toʻgʻri chiziqlarni beradi. Chiziqli funksiyani ixtiyoriy oʻzgarmas c₀ songa teng deb olaylik. Unda c₁x₁+c₂x₂=const= c₀ toʻgʻri chiziq hosil boʻladi. Unga perpendikulyar boʻlgan N(c₁,c₂) vektor z-funksiyaning oʻsish yoʻnalishini belgilaydi (1.5.5--rasm).
Agar echimlardan tashkil topgan qavariq koʻpburchak chegaralanmagan boʻlsa ikki hol boʻlishi mumkin:
1-hol. c₁x₁+c₂x₂=const toʻgʻri chiziq N(c₁,c₂) vektor vektor boʻyicha yoki unga qarama-qarshi yoʻnalishda siljib borib har vaqt qavariq koʻpburchakni kesib oʻtadi. Ammo na minumum yoki maksimum qiymatga erishmaydi. Bu holda chiziqli funksiya quyidan va yuqoridan chegaralanmagan boʻladi (1.5.6-rasm).

1.5.5- rasm. Koʻpburchak 1.5.6-rasm. Quyidan va yuqoridan
chegaralanmagan chiziqli funksiya
2-hol. c₁x₁+c₂x₂=const toʻgʻri chiziq N(c₁,c₂) vektor boʻyicha siljib borib qavariq koʻpburchakning birorta chetki nuqtasida minumum yoki maksimum qiymatga erishadi. Bunday holda chiziqli funksiya yuqoridan chegaralangan, quyidan esa chegaralanmagan (1.5.7-rasm) yoki quyidan chegaralangan yuqoridan esa chegaralanmagan boʻlishi mumkin (1.5.8-rasm). Ba’zi chiziqli funksiya yuqoridan ham, quyidan ham esa chegaralangan boʻlishi mumkin (1.5.9-rasm).

1.5.7- rasm. Chiziqli funksiya 1.5.8-rasm. Quyidan
chegaralangan yuqoridan chegaralangan yuqoridan chegaralanmagan



1.5.9-rasm. Chiziqli funksiya yuqoridan ham, quyidan ham chegaralangan

Chiziqli programalash masalasini grafik usulda echish quyidagi ketma-ketlikda bajariladi:

1. 
   Tenglamalar yoki tengsizliklar sistemasining grafiklari quriladi .
   
2. 
   Har bir tengsizlikning tekislikdagi aniqlanish tomonlari (sohasi) belgilanadi.
   
3. 
   Mumkin boʻlgan echimlar sohasi ajratiladi .
   
4. 
   N=(c₁,c₂) vektori quriladi va unga (0,0) nuqtada perpendikulyar oʻtkaziladi.
   
5. 
   Koʻpburchakdan perpendikulyarga parallel chiziqni vektor yoʻnalishi boʻyicha paralel siljitilib ekstremal nuqta topiladi. Agar Z funksiyaning minimal qiymatiga mos nuqtani topish kerak boʻlsa, u holda bu nuqta p vektorga perpendikulyarning shu vektor yoʻnalishi boʻyicha siljitganda mumkin boʻlgan nuqtalar sohasining birinchi nuqtasiga mos keladi. Maksimum qiymat beruvchi nuqta esa eng oxirgi nuqta boʻladi. Agar vektor qiymati (manfiy ishora) -N boʻlsa yuqoridagi holning teskarisi boʻladi.
   
6. 
   Optimal nuqta kordinatasi topiladi va Z funksiya qiymati hisoblanadi.
   

Misol. Quyidagi chiziqli programmalash masalasini grafik usulda eching.


1.5.10-rasm. Echimlar soxasi.

Berilgan tengsizliklarning grafiklarini X₁OX₂ tekislikda quramiz va mumkin boʻlgan echimlar soxasini aniqlaymiz (1.5.10-rasm). Soha grafigida shtrixlangan joyni aniqlaydi. Chunki bu joy hamma tengsizliklarni qanoatlantiruvchi sohadir. Mumkin boʻlgan echimlar soxasidan optimal echimni aniqlaymiz. Aniqlash uchun (0,0) nuqtadan oʻtuvchi N=(2,-5) vektorini yasaymiz va uning yoʻnalishini aniqlaymiz. (0,0) nuqtada bu vektorga N perpindikulyarini oʻtkazamiz va uni vektor yoʻnalishi boʻyicha siljitamiz. Soha bilan perpindikulyarning oxirgi kesishish nuqtasi A nuqta boʻladi. Bu nuqta Z funksiyasiga maksimal qiymat beruvchi nuqtadir. Bu nuqta (3,0) boʻlib uning koordinatasi x₁=3, x₂=0 masalaning echimi boʻladi. Grafikdan koʻrinib turibdiki z funksiyaga minumum qiymat beruvchi nuqta esa (0,3).