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.