Toshkent axborot texnologiyalari universiteti huzuridagi dasturiy mahsulotlar va apparat dasturiy majmualar yaratish

ma’ruza. Sun’iy bazis usulida yechish algoritmi. Sun’iy bazis usulida masalalar yechish. Chiziqli dasturlashning o‘zaro ikki yoqlama masalalari va ularning matematik modellari. O‘zaro ikki yoqlama simpleks- usul.

REJA:

1. 
   Sun’iy bazis usuli.
   
2. 
   Chiziqli dasturlashning o’zaro ikki yoqlama masalalari.
   
3. 
   Ikki yoqlama simpleks usuli
   

Foydalanilgan adabiyotlar:

1. 
   L. Yu. Turayeva, O. B. Soqiyeva. Matematik programmalash masalalariniyechish bo’yicha uslubiy qo’llanma. Termiz, TDU, 2010., 77 bet.
   
2. 
   M. Raisov, R. X. Mukumova «Matematik programmalash». Uslubiy qo‘llanma. Samarqand, SamISI, 2008., 188 bet.
   
3. 
   Е. В. Башкинова, Г.Ф. Егорова, А. А. Заусаев. Численные методы и их реализация в MS Excel. Часть 2. Самара; Самар. гос. техн. ун-т, 2009. 44 с
   

Tayanch tushunchalar. Bazis, Sun’iy 63asis, ikki yoqlama masalalari, chiziqli dasturlash masalalari, simpleks, simpleks usul

Agar masalaning shartlarida o’zaro erkli bo’lgan m ta birlik vektorlar (63asis vektorlar) qatnashmasa, ular sun’iy ravishda kiritiladi. Masalan, masala quyidagi ko’rinishda berilgan bo’lsin:

^a₁₁^x₁ ^{ a}₁₂ ^x₂ ^{ ...  a}_1n ^x_n ^{ b}₁ <sup>,

</sup>a x  a x  ...  a x  b ,

^ 21 1 22 2 2n n 2



(1)

_.............................................

^_a_m1x₁  a_m2 x₂  ...  a_mn x_n  b_m ,

x₁  0, x₂  0,

, x_n  0,

(2)

^Ymax ^

c₁x₁ 

c₂ x₂   

c_n x_n

(3)

^{Bu masalaga x}n+1^{ 0, x}n+2 ^{ 0, …, x}n+m ^{ 0 qo’shimcha o’zgaruvchilar kiritilsa,} quyidagi kegaytirilgan masala hosil bo’ladi:

^a₁₁^x₁ ^{ a}₁₂ ^x₂ ^{ ...  a}_1n ^x_n ^{ b}₁ <sup>,

</sup>a x  a x  ...  a x  b ,

^ 21 1 22 2 2n n 2



(4)

_.............................................

^_a_m1x₁  a_m2 x₂  ...  a_mn x_n  b_m ,

x₁  0, x₂  0,

, x_n  0,

, x_nm  0,

(5)

Y_min  

c₁x₁ 

c₂ x_{2 }  

^{cnxn  0}<sup>xn1,

x</sup>nm ^

(6)

Bu holda

^Pn1^{, P}n2 ^{,, P}nm

vektorlar bazis vektorlar va

^xn1^{, x}n2 ^{,, x}nm

o’zgaruvchilar «bazis o’zgaruvchilar» deb qabul qilinadi.

Agar berilgan masala quyidagi ko’rinishda bo’lsa:

^a₁₁^x₁ ^{ a}₁₂ ^x₂ ^{ ...  a}_1n ^x_n ^{ b}₁ <sup>,

</sup>a x  a x  ...  a x  b ,

^ 21 1 22 2 2n n 2



1. 
   
   

_.............................................

^_a_m1x₁  a_m2 x₂  ...  a_mn x_n  b_m ,

x₁  0, x₂  0,

, x_n  0,

2. 
   
   

^Ymin ^

c₁x₁ 

c₂ x₂   

c_n x_n

3. 
   
   

^{bu masalaga sun’iy x}n+1^,xn+2^,…,xn+m ^{o’zgaruvchilar kiritib quyidagi} kengaytirilgan masala hosil qilinadi:

^a₁₁^x₁ ^{ a}₁₂ ^x₂ ^{ ...  a}_1n ^x_n ^{ b}₁ <sup>,

</sup>a x  a x  ...  a x  b ,

^ 21 1 22 2 2n n 2



4. 
   
   

_.............................................

^_a_m1x₁  a_m2 x₂  ...  a_mn x_n  b_m ,

x₁  0, x₂  0,

, x_n  0, x_n1  0,, x_nm  0,

5. 
   
   

^{Ymin   c1x1  c2x2    cnxn  M}  ^{xn1,}

bu erda: M – yetarlicha katta musbat son.

^xnm ^

6. 
   
   

Sun’iy bazis o’zgaruvchilariga mos keluvchi

^Pn1^{, P}n2 ^{,, P}nm

vektorlar «sun’iy

bazis vektorlar» deb ataladi. Berilgan (7)-(9) masalaning optimal yechimi quyidagi teoremaga asoslanib topiladi.

Teorema: Agar kengaytirilgan (10)-(12) masalaning optimal yechimida sun’iy bazis o’zgaruvchilari nolga teng bo’lsa, ya’ni:

x_ni  0,

^{i  1,, m}

tenglik o’rinli bo’lsa, u holda bu echim berilgan (7)-(9) masalaning ham optimal yechimi bo’ladi.

Kengaytirilgan masalaning optimal echimida kamida bitta sun’iy bazis o’zgaruvchi noldan farqli bo’lsa, unda masala echimga ega bo’lmaydi.