2-ma’ruza. Chiziqli programmalashtirishning umumiy masalasi va uni geometrik talqini reja

Chiziqli programmalash masalasini grafik usulda yechish

Chiziqli programmalash masalasini grafik usulda yechish uni geometrik tasvirlashga asoslangan. Ikki o‘lchovli fazoda (tekislikda) berilgan chiziqli programmalash masalalarini yechish uchun grafik usulni qo‘llash mumkin. o‘lchovli fazoda berilgan masalalarni grafik usul bilan yechish noqulay, chunki bu holda, yechimlardan tashkil topgan qavariq ko‘pburchakni yasash qiyinlashadi.

Ikki o‘lchovli fazoda berilgan quyidagi chiziqli programmalash masalasini ko‘ramiz:
(4)
(5)
(6)
Faraz qilaylik, (4) sistema (5) shartni qanoatlantiruvchi yechimlarga ega hamda ulardan tashkil topgan to‘plam chekli bo‘lsin. (4) va (5) tengsizliklarning har biri

chiziqlar bilan chegaralangan yarim tekisliklarni ifodalaydi. Chiziqli funksiya ham ma’lum bir o‘zgarmas

qiymatda 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‘purchak bo‘lsin (2-shakl). Chiziqli funksiyani ixtiyoriy o‘zgarmas songa teng deb olaylik.

(y)

X₂



(y)

C


B


D





A

E

N


O

X₁

2-shakl

Natijada

to‘g‘ri chiziq hosil bo‘ladi. Bu to‘g‘ri chiziqni vektor yo‘nalishida yoki unga teskari yo‘nalishda o‘ziga paralel surib borib, qavariq ko‘pburchakning chiziqli funksiyaga ega kichik qiymat beruvchi chetki nuqtasini aniqlaymiz. 2-shakldan ko‘rinib turipdiki, chiziqli funksiya o‘zining minimal qiymatga qavariq ko‘pburchakning nuqtasida erishadi. S nuqtada esa, u o‘zining maksimal qiymatiga erishadi. Birinchi holda nuqtaning koordinatalari masalaning chiziqli funksiyaga minimal qiymat beruvchi optimal yechimi bo‘ladi. Uning koordinatalarini va to‘g‘ri chiziqlarni ifodalovchi tenglamalar sistemasini yechish orqali aniqlanadi.
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 (3-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 (4-shakl) yoki quyidan chegaralangan yuqoridan esa chegaralanmagan bo‘lishi mumkin (5-shakl). Ba’zan chiziqli funksiya ham qo‘yidan, ham yuqoridan chegaralangan bo‘lishi mumkin (6-shakl).

x₂ x₂ (u) (u) (u)
(u) (u)

N N
O x₁ O x₁
3-shakl 4-shakl







N

5-shakl. 6-shakl.

1. 
   - misol.
   

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

chiziqlarni yasaymiz (7-shakl).

7-shakl

Berilgan tengsizliklarni qanoatlantiruvchi yechim shtrixlangan ko‘pburchakni tashkil qiladi. Endi koordinatalar boshidan 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 nuqtani topamiz. Bu nuqtaning koordinatalari masalaning optimal yechimi bo‘ladi va bo‘ladi.

2. 
   misol.
   

Yechish. koordinatalar sistemasida , chiziqlarni o‘tkazib, masalaning shartlarini qanoatlantiruvchi qavariq ko‘pburchakni hosil qilamiz. Bu kupburchak 8-shaklda shtrixlab qo‘yilgan uchburchakdan iborat. Koordinatalar boshidan vektorni va unga perpendikulyar bo‘lgan to‘g‘ri chiziqni o‘tkazamiz. Bu to‘g‘ri chiziqni vektor yo‘nalishida o‘ziga paralel siljitib boramiz va nuqtada funksiya o‘zining maksimal qiymatga erishishini aniqlaymiz. Bu nuqtaning koordinatalari masalaning optimal yechimi bo‘ladi. Bu yechimdagi chiziqli funksiyaning qiymati bo‘ladi.

x₁

8- shakl