Maruza mashg’ulotlari

Cheklanish shartlari n noma’lumli m ta tenglamalar sistemasidan iborat bo‘lgan chiziqli dasturlash masalalarini grafik usulda echish.

Biz hozigrgacha cheklanish shartlari ikki noma’lumli m ta tengsizliklar sistemasidan iborat bo‘lgan chiziqli dasturlash masalasini grafik usulda echilishini ko‘rdik. Bu usul cheklanish shartlari n noma’lumli m ta tenglamalar sistemasidan iborat bo‘lgan chiziqli dasturlash masalalarini n-m=2 bo‘lganada ham echish mumkin. haqiqatan ham, bizga ushbu

Z_min= , (14.6)

a₁₁x₁ +a₁₂x₂+... +a_1nx_n=b₁

a₂₁x₁ +a₂₂x₂+... +a_2nx_n=b₂

- - - - - - - - - - - - - - - - - - (14.7)

a_m1x₁ +a_m2x₂+... +a_mnx_n=b_m

x_j 0, j=1,n, n-m=2

chiziqli dasturlash masalasi berilgan bo‘lsin. Ko‘rinib turibdiki, (14.7) da noma’lumlar soni tenglamalar sonidan 2 ta ko‘pdir, ya’ni n-m=2. Shuning uchun, x₁, x₂, ... ,x_m larni erksiz o‘zgaruvchilar, x_m+1,x_m+2 larni erkli o‘zgaruvchilar deb qabul qilamiz. (14.7) sistemani erksiz o‘zgaruvchilarga nisbatan Gauss usuli bilan echsak, quyidagiga ega bo‘lamiz:

(14.8)

Endi (14.8) ni (14.6) ga qo‘ysak, maqsad funksiyamiz quyidagi

Z_min= (14.9)

ko‘rinishga keladi. Echimlarning manfiy bo‘lmaslik shartlari, ya’ni x_j 0, j=1,2,...,n nazarda tutsak (14.8) ni quyidagicha yozish mumkin:

(14.10)
(14.9) – (14.10) masalani grafik usulda echamiz. Cheklanish tengsizliklari (14.10) ni qanoatlantirib, maqsad funksiya (14.9) ga minimum beruvchi optimal echim x_m+1,x_m+2 ni topib, (14.8) ga qo‘ysak, (14.6) funksiyaga minimum beruvchi x₁, x₂, ... ,x_m larning ham optimal qiymatlarini topgan bo‘lamiz;

Misol.Grafik usul bilan

Z=2x₁ –x₂ +x₃ -3x₄+4x₅ (14.11)

funksiyaning cheklanish shartlari

x₁-x₂+3x₃-18x₄+2x₅=-4,

2x₁-x₂+4x₃-21x₄+4x₅=22,

3x₁-2x₂+8x₃-43x₄+11x₅=38

x_j 0, j=1,5

ni qanoatlantiradigan maksimumi topilsin.

Echish.Cheklanish tenglamalarini x_1,x₂ va x₃ larga nisbatan Gauss usuli bilan echsak,

x₁+x₄-3x₅=6,

x₂+7x₄₊10x₅=70,

x₃-4x₄+5x₅=20

tenglamalar sistemasini hosil qilamiz.

Bu erdan

x₁=6-x₄+3x₅,

x₂=70-7x₄-10x₅,

x₃=20+4x₄-5x₅

larni topib,maqsad funksiya (14.11) ga qo‘ysak,

Z=6x₄+15x₅-38 (14.12)

ni hosil qilamiz.Echimlarning manfiy bo‘lmaslik shartlari x_j 0, ( j=1,5 )ni nazarda tutsak,

x₄ - 3x₅ 6,

7x₄+10x₅ 70,

-4x₄+5x₅ 20 (14.13)

x₄ 0, x₅ 0

tengsizliklar sistemasini hosil qilamiz. Endi (14.12) funksiyaning cheklanish tengsizliklari (14.13)ni qanoatlantiradigan maksimumini grafik usul bilan topamiz.