Strreplkirish I bob. Chiziqli programmalashtirish masalalari 1-§. Chiziqli programmalashtirish masalalaining amaliy masalalari

Misol. tengsizligi bilan aniqlanadigan yarimtekislikni chizmada ko`rsating.
to`g`ri chiziq tekislikda yasaladi. To`g`ri chiziq koordinata boshidan o`tmaganligi sababli O(0,0) nuqtani tengsizlikka qo`yib, tekshirib ko`rish mumkin. Bunda, 0 < 3 to`g`ri munosabat hosil bo`ladi. Demak, tengsizlik O(0,0) nuqtani o`z ichiga oluvchi yarim tekislikni aniqlaydi.

Xuddi shuningdek, (1.2.1) va (1.2.2) tengsizliklarning har biri mos holda , 0, 0 chiziqlar bilan chegaralangan yarim tekisliklarni ifodalaydi. (1.2.1), (1.2.2) tengsizliklarning har birini qanoatlantiradigan nuqtalar to`plami ular aniqlaydigan yarimtekisliklarning kesishishidan hosil bo`ladigan umumiy nuqtalar to`plami (qavariq to`plam) dan iborat bo`ladi. Bunday nuqtalar to`plamiga berilgan ikki o`zgaruvchili ChPM ning mumkin bo`lgan yechim sohasi deyiladi.
(1.2.3) chiziqli funksiya ham ma’lum bir o`zgarmas qiymatda to`g`ri chiziqni ifodalaydi. Mumkin bo`lgan yechim soha - qavariq to`plamni hosil qilish uchun

to`g`ri chiziqlar bilan chegaralangan ko`pburchak yasaladi.
Faraz qilaylik, bu ko`pburchak ABCDE bo`lsin (1-shakl). Chiziqli funksiyani ixriyoriy o`zgarmas songa teng deb olaylik.
Natijada to`g`ri chiziq hosil bo`ladi. Bu to`g`ri chiziqni (1.2.3) – maqsad funksiyaning gradient vektori bo`lgan vektor yo`nalishda yoki unga teskari yo`nalishda o`ziga parallel ravishda shunday surib borish kerakki, bu vektor yechim sohani bosib o`tsin.
Qavariq ko`pburchakning chiziqli funksiyaga eng kichik qiymat beruvchi chetki nuqtasini aniqlaymiz.
Agar yechimlardan tashkil topgan qavariq ko`pburchak chegaralanmagan bo`lsa, ikki hol bo`lishi mumkin.
1-hol. to`g`ri chiziq vektor bo`yicha yoki unga qarama-qarshi yo`nalishda siljib borib, har vaqt qavariq ko`pburchakni kesib o`tadi. Ammo, na minimal, na maksimal qiymatga erishmaydi. Bu holda chiziqli funksiya quyidan va yuqoridan chegaralanmagan bo`ladi (4-shakl).
2-hol. to`g`ri chiziq vektor bo`yicha siljib borib qavariq ko`pburchakning birorta chetki nuqtasida o`zining minimum yoki maksimum qiymatiga erishadi. Bunday holda chiziqli funksiya yuqoridan chegaralangan, quyidan esa chegaralanmagan (2-shakl) yoki quyidan chegaralangan, yuqoridan esa chegaralanmagan bo`lishi mumkin (3-shakl).



1-misol. Quyidagi chiziqli programmalash masalasini grafik usulda
yeching:

Yechish. Yechimlardan tashkil topgan qavariq ko`pburchakni yasash
uchun koordinatalar sistemasida


chiziqlarni yasaymiz.
Berilgan tengsizliklarni qanoatlantiruvchi yechimlar sohasi OABC ko`pburchakni tashkil qiladi. Endi koordinatalar boshidan =(2, -5) vektorni yasaymiz va unga perpendikulyar bo`lgan to`g`ri chiziq o`tkazamiz. Bu to`g`ri chiziq tenglama orqali ifodalanadi.
Uni vektor yo`nalishida o`ziga parallel siljitib boramiz. Natijada chiziqli funksiyaga maksimal qiymat beruvchi C (3,0) nuqtani topamiz.
Bu nuqtaning koordinatalari , . Masalaning optimal yechimi va bo`ladi.