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

17-mavzu. Ko’p o’zgaruvchili chiziqli dasturlash masalasini grafik usulda yechish

(5) chegaralar sistemasi matritsasi va kengaytirilgan matrisasi

ko’rinishga ega. Agar bu matritsalarning rangi teng bo’lmasa, u holda (5)-(7) chiziqli dasturlash masalasi yechimga ega bo’lmaydi. va matritsalarning rangi ga teng bo’lsin. U holda matritsaning -tartibli biror minori noldan farqli. Aniqlik uchun dastlabki ta satr va dastlabki ta ustundan tuzilgan minori noldan farqli bo’lsin. Agar bo’sa (6) sistemaning qolgan tenglamalarini dastlabki tasi orqali ifodalanadi va ularni tashlab yuborish mumkin. Shuning uchun deb hisoblaymiz. U holda (6) chegaralar sistemasida o’zgaruvchilarni bazis o’zgaruvchilar qolgan o’zgaruvchilarni erkli o’zgaruvchilar deb ataymiz.
Agar bo’lsa (5)-(7) chiziqli dasturlash masalasini grafik usulda yechish mumkin. Buning uchun (6) sistemani bazis o’zgaruvchilarga nisbatan yechamiz:

larning nomanfiylik shartlari

ko’rinishni oladi. (4)maqsad funksiyada o’zgaruvchilar o’rniga (8) dagi ifodasini qo’yamiz:

Shunday qilib (5)-(7) chiziqli dasturlash masalasi o’zgaruvchilari iikita bo’lgan quyidagi ko’rinishga keltirildi:



Hosil bo’lgan chiziqli dasturlash masalasini grafik usuldan foydalanib yechish mumkin.
4-misol. Grafik usuldan foydalanib kanonik ko’rinishda berilgan chiziqli dasturlash masalasi yechimini toping:



Yechish. Chegaralar sistemasining matritsasi quydagi ko’rinishga ega:

Bu matritsaning dastlabki 4 ta satr va 4 ta ustunidan tuzilgan minorning qiymati noldan farqli, aniqrog’I 1 ga teng. Shuning uchun uning va kengaytirilgan matritsaning rangi 4 ga teng bo’lib erkli o’zgaruvchilar soni 2 ga teng. Demak qaralayotgan chiziqli daturlash masalasini grafik usulda yechish mumkin.
Chegaralar sistemasini bazis o’sgaruvchilarga nisbatan yechamiz:

Bazis o’zgaruvchilarni qiymatlarini maqsad funksiyaga keltirib qo’yamiz:

(9) ga ko’ra o’zgaruvchilarning nomanfiylik sharti

ko’rinishni o’ladi. Shunday qilib qaralayotgan chiziqli dasturlash masalsi quyidagi ikki o’zgaruvchili masalani yechishga keltirildi:



nuqtalar tekisligida bu masalaning rejalar to’plami beshburchakdan iborat.
chiziqlar oilasi chizqlaridan biri, masalan to’g’ri chiziq to’plamdan o’tadi. vektor funksiyaning kamayish yo’nalishini ko’rsatadi. to’gri chiziqni vektor bo’yicha to’plamning chegarasiga qadar parallel siljitamiz. Bu holda to’g’ri chiziq ko’pburchakning nuqtasidan chiqib ketadi. (9) da qiymatlarni qo’yib larni topamiz. Demak .