16-mavzu. Ikki o’zgaruvchili chiziqli dasturlash masalasini yechish

Simpleks usulni qo’llanilishi. Farz qilaylik (5)-(7) chiziqli dasturlash masalasi aynimagan bo’lsin. (11) – bu masalaning bazis rejasi bo’lsin. (10) dan foydalanib maqsad funksiyani erkli o’zgaruvchilar orqali ifodalaymiz:

a). (12) ifodada barcha koeffisientlar nomanfiy bo’lsin.
1-tasdiq. a) holda (11) burchak nuqta ustida funksiya o’zining minimumiga erishadi va bu minimum qiymat ga teng.
b). (12) ifodada koeffisientlar orasida manfiysi mavjud bo’lsin. Ulardan biri koeffisient bo’lib, (10) sistemada o’zgaruvchi oldidagi barcha koeffisientlar nomanfiy bo’lsin, ya’ni , bo’lsin.
2-tasdiq. b) holda maqsad funksiya rejalar to’plamida quyidan chegaralanmaydi, ya’ni (5)-(7) chiziqli dasturlash masalasi yechimga ega bo’lmaydi.
c). (12) ifodada koeffisientlar orasida manfiysi mavjud bo’lsin, masalan bo’lsin. (10) sistemada o’zgaruvchi oldidagi koeffisientlar orasida kamida bitta manfiy son mavjud bo’lsin.
3-tasdiq. c) holda rejalar to’plamining shunday burchak nuqtasi topiladiki tengsizlik bajariladi.
Ko’rdikki a) va b) hollarda (5)-(7) chiziqli dasturlash masalasini yechish jarayoni nihoyasiga yetadi. Shuning uchun c) holni atroflicha o’rgnib chiqamiz. (12) ifodada va (10) sistemada o’zgaruvchi oldidagi koeffisient manfiy bo’lsin. Agar koeffisientlardan bir nechtasi manfiy bo’lsa, u holda

nisbatlardan eng kichigini deb olamiz.
(10) sistemada larni erkli o’zgaruvchi deb hisoblaymiz va sistemani bazis o’zgaruvchilarga nisbatan yechamiz:

Bu yerda erkli o’zgaruvchilarni nolga tenglab yangi burchak nuqta (basiz reja) aniqlanadi. Shu bilan birga tengsizlik o’rinli. Maqsad funksiyani ham erkli o’zgaruvchilar orqali ifodalaymiz:

Maqsad funksiyaning ohirgi ifodasi bilan holda yuqoridagi a), b) va c) holatlardan biri yuz berishi mumkin. Agar a) va b) holatlardan biri yuz bersa chiziqli dasturlash masalasini yechish yakunlanadi. Agar c) holat yuz bersa yuqoridagidek almashtirishlar bajarib navbatdagi burchak nuqtaga o’tamiz va h.k. rejalar to’plamining burchak nuqtalari chekli ( dan ortmaydi) bo’lgani uchun c) holatni yuz berishini takrorlanishi ham dan ortmaydi. Shunday qilib ohirgi qadamda yo masala yechimini aniqlaymiz yo masala yechimga ega emas deb hulosa chiqaramiz.
1-misol. Simpleks usuldan foydalanib chiziqli dasturlash masalasi yechimini toping. Bunda boshlang’ich burchak nuqta sifatida va – erkli o’zgaruvchi deb olingan bazis rejani tanlang.