Mavzu: Chiziqli dasturlash masalalari uchun tayanch yechim tushunchasi, ularni aniqlash usullari Toshkent-2023 Chiziqli dasturlash masalalari uchun tayanch yechim tushunchasi, ularni aniqlash usullari

Chiziqli dasturlash masalasining geometrik talqini.
Masalani grafik usulda yechish
Chiziqli dasturlash masalasini grafik usulda yechish, uni geometrik tasvirlashga asoslangan. Ikki o`lchovli fazo (tekislik)da berilgan chiziqli dasturlash masalalarini yechish uchun grafik usulni qo`llash maqsadga muvofiq. n≥3
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 dasturlash masalasini ko`ramiz:
(1)
(2)
(3)
Faraz qilaylik, (1) sistema (2) shartni qanoatlantiruvchi yechimlarga ega hamda ulardan tashkil topgan to`plam chekli bo`lsin.
Tekislikda to`g`ri burchakli Dekart koordinatalar sistemasini kiritamiz va s onlarning har bir juftligiga tekislikda koordinatalari x1 va x2 bo`lgan nuqtani mos qo`yamiz. Avval berilgan masalaning mumkin bo`lgan yechimlari qanday nuqtalar to`plamini tashkil qilishini ko`raylik. Ma’lumki, ikki o`zgaruvchili
t engsizlik tekislikda to`g`ri chiziq bilan chegaralangan yarim tekislikni aniqlaydi. Bu yarim tekislik to`g`ri chiziqqa nisbatan qaysi nuqtalar to`plami ekanini aniqlashtirish uchun ixtiyoriy nuqtani qo`yib ko`rish mumkin. Olingan nuqta tengsizlikni qanoatlantirsa, shu nuqta yotgan yarim tekislik,
aks holda ikkinchi yarimtekislik, qidirilayotgan yarimtekislik bo`ladi. Buni quyidagi misolda ko`raylik.
Misol. tengsizligi bilan aniqlanadigan yarimtekislikni
chizmada ko`rsating.
t
o`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.
X uddi shuningdek, (1) va (2) tengsizliklarning har biri mos holda
chiziqlar bilan chegaralangan yarim tekisliklarni ifodalaydi. (1), (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 ChDM ning mumkin bo`lgan yechim sohasi deyiladi.
( 3) chiziqli funksiya ham ma’lum bir o`zgarmas
qiymatda to`g`ri chiziqni ifodalaydi. Mumkin bo`lgan yechim soha - qavariq to`plamni hosil q ilish 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 c0 songa teng deb olaylik.

Natijada to`g`ri chiziq hosil bo`ladi. Bu to`g`ri

chiziqni (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 ON 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 ON 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).