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

1-misol. Grafik usuldan foydalanib chiziqli dasturlash masalasi yechimini toping:



Yechish. nuqtalar tekisligida rejalar to’plami beshburchakdan iborat. chiziqlar oilasi chiziqlaridan 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. Demak funksiya nuqtada o’zining minimum qiymatiga erishadi: .
2-misol. Chizqli dasturlash masalasini qaraymiz:



Yechish. Rejalar to’plami avvalgi misolda ko’rilgan beshburchakdan iborat.
chiziqlar oilasi chiziqlaridan 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 tomonidan chiqib ketadi. Demak funksiya tomon nuqtalari ustida o’zining minimum qiymatiga erishadi. va nuqta koordinalari mos ravishda va bo’lgani uchun har qanday minimum nuqta koordinatasi ko’rnishga ega, bu yerda . Maqsad funksiyaning minimum qiymati .
3-misol. Grafik usuldan foydalanib chiziqli dasturlash masalasi yechimini toping:



Yechish. nuqtalar tekisligida rejalar to’plami chegaralanmagan ko’pburchakdan iborat.
chiziqlar oilasi chiziqlaridan biri, masalan to’g’ri chiziq to’plamdan o’tadi. vektor funksiyaning kamayish yo’nalishini ko’rsatadi. to’gri chiziqni vektor bo’yicha parallel siljitsak hech qachon rejalar to’plamidan chiqib ketmaydi. Demak qaralayotgan chiziqli dasturlash masalasi yechimga ega emas.

Chizqli dasturlash masalasi kanonik ko’rinishda berilgan bo’lsin: