9 маъруза. Chiziqli dasturlashning asosiy masalalari: kanonik va standart shakldagi masalalar. Chiziqli dasturlash masalasining geometrik talqini. Chiziqli dasturlash masalasi optimal yechimini grafik usulda topish

Chiziqli dasturlash masalasini grafik usulda echish.
Chiziqli dasturlash masalasining geometrik talqiniga hamda chiziqli dasturlash masalasi yechimining hossalariga tayanib masalani ba’zi hollarda grafikusulda yechish mumkin.
Ikkio‘lchovli fazoda berilgan quyidagi chiziqli dasturlash masalasini ko‘ramiz:
_{ } (1)
_{ }, (2)
_{ } (3)
Farazqilaylik, (1) sistema (2) shartni qanoatlantiruvchi yechimlarga ega bo‘lsin hamda yechimlardan tashkil topgan to‘plam chekli bo‘lsin. (1) va (2) tengsizliklarning har biri


сhiziqlar bilan chegaralangan yarim tekisliklarni ifodalaydi.
_{ } (4)
tengsizlikni qanoatlantiruvchi yarim tekislik _{ } to‘g‘ri chiziqning qaysi tomonida yotishini aniqlash uchun O(0;0) koordinata boshini mo‘ljal nuqta deb qarash mumkin. Agar_{ } qiymatlarni (4) tengsizlikka qo‘yganda _{ } tengsizlik hosil bo‘lsa, u holda qidirilayotgan yarim tekislik _{ } to‘g‘ri chiziqning ostida (koordinata boshi tomonida) yotadi, aks holda u bu to‘g‘ri chiziqning yuqorisida yotuvchi yarimtekislikdan iborat bo‘ladi.
Chiziqli funksiya (3) ham ma’lum bir o‘zgarmas _{ } qiymatda

sath to‘g‘ri chiziqlar oilasiga tegishli bo‘lgan to‘g‘ri chiziqni ifodalaydi. Yechimlardan tashkil topgan qavariq to‘plamni hosil qilish uchun


to‘g‘ri chiziqlar bilan chegaralangan ko‘pburchakni yasaymiz.
Faraz qilaylik bu ko‘pburchak ABCDE beshburchakdan iborat bo‘lsin (1-rasm).

1-rasm.
Chiziqli funksiyani ixtiyoriy o‘zgarmas_{ } songa teng deb olamiz.
Natijada

to‘g‘ri chiziq hosil bo‘ladi. Bu to‘g‘ri chiziqni _{ } vector yo‘nalishida yoki unga teskari yo‘nalishida o‘ziga parallel suribborib qavariq ko‘pburchakning chiziqli funksiyaga eng kata yoki eng kichik qiymat beruvchi nuqtalarni aniqlaymiz.⁴
1-rasmdan ko‘rinib turibdiki, chiziqli funksiya o‘zining minimal qiymatiga qavariq ko‘pburchakning A nuqtasida erishadi. S nuqtada esa, u o‘zining maksimal (engkatta) qiymatiga erishadi. Birinchi holda _{ } nuqtaning koordinatalari masalaning chiziqli funksiyasiga minimal qiymat beruvchi optimal yechimi bo‘ladi. Uning koordinatalari AB va AE to‘g‘ri chiziqlarni ifodalovchi tenglamalar orqali aniqlanadi.
Agar yechimlardan tashkil topgan qavariq ko‘pburchak chegaralanmagan bo‘lsa, ikki hol bo‘lishi mumkin.
l-hol. _{ } to‘g‘ri chiziq _{ } vector bo‘yicha yoki unga qarama-qarshi yo‘nalishda siljib borib har vaqt qavariq ko‘pburchakni kesib o‘tadi. Ammo minimal va maksimal qiymatga erishmaydi. Bu holda chiziqli funkstiya quyidan va yuqoridan chegaralanmagan bo‘ladi (2-rasm).

2-rasm.
_{ } to‘g‘ri chiziq _{ } vektor bo‘yicha siljib borib qavariq ko‘pburchakning birorta burchak nuqtasida o‘zining minimal yoki maksimum qiymatiga erishadi. Bunday holda chiziqli funksiya yuqoridan chegaralangan, quyidan esa chegaralanmagan (3-rasm) yoki quyidan chegaralangan, yuqoridan esa chegaralanmagan (4-rasm) bo‘lishi mumkin.

3-rasm.

4-rasm.