2. Chiziqli dasturlash masalasini yechishning grafik usuli

2.Chiziqli dasturlash masalasini yechishning grafik usuli

n

.

Chiziqli dasturlash masalasini ikki o‘zgaruvchi uchun quyidagicha yozamiz.

Chiziqli dasturlash masalasini grafik usulda yechish quyidagi ketma-ketlikda bajariladi:

1.Tenglamalar yoki tengsizliklar tizimining grafiklari quriladi .

2.Har bir tengsizlikning tekislikdagi aniqlanish tomonlari (sohasi) belgilanadi.

3.Mumkin bo‘lgan yechimlar sohasi ajratiladi .

4. N=(c₁,c₂) vektori quriladi va unga (0,0) nuqtada perpendikulyar o‘tkaziladi.

5.Ko‘pburchakdan perpendikulyarga parallel chiziqni vektor yo‘nalishi bo‘yicha parallel siljitilib ekstremal nuqta topiladi. Agar Z funksiyaning minimal qiymatiga

mos nuqtani topish kerak bo‘lsa, u holda bu nuqta p vektorga perpendikulyarning shu vektor yo‘nalishi bo‘yicha siljitganda mumkin bo‘lgan nuqtalar sohasining birinchi nuqtasiga mos keladi. Maksimum qiymat beruvchi nuqta esa eng oxirgi nuqta bo‘ladi. Agar vektor qiymati (manfiy ishora) -N bo‘lsa yuqoridagi holning teskarisi bo‘ladi.

6.Optimal nuqta koordinatasi topiladi va Z funksiya qiymati hisoblanadi

Misol. Quyidagi chiziqli dasturlash masalasini grafik usulda yeching.

3.10 rasm.

Berilgan tengsizliklarning grafiklarini X₁OX₂ tekislikda quramiz va mumkin bo‘lgan yechimlar sohasini aniqlaymiz (3.10 rasm). Soha grafigida shtrixlangan joyni aniqlaydi. Chunki bu joy hamma tengsizliklarni qanoatlantiruvchi sohadir. Mumkin bo‘lgan yechimlar sohasidan optimal yechimni aniqlaymiz. Aniqlash uchun (0,0) nuqtadan o‘tuvchi N=(2,-5) vektorini yasaymiz va uning yo‘nalishini aniqlaymiz. (0,0) nuqtada bu vektorga N perpindikulyarini o‘tkazamiz va uni vektor yo‘nalishi bo‘yicha siljitamiz. Soha bilan perpindikulyarning oxirgi kesishish nuqtasi Z funksiyasiga maksimal qiymat beruvchi nuqtadir. Bu nuqta (3,0) bo‘lib uning koordinatasi x₁=3, x₂=0 masalaning yechimi bo‘ladi. Grafikdan ko‘rinib turibdiki Z funksiyaga minumum qiymat beruvchi nuqta esa (0,3).