2 bob. Chiziqli programmalashtirish masalasi

2 - bob. CHIZIQLI PROGRAMMALASHTIRISH MASALASI 2.1. Asosiy tushunchalar. Chiziqli programmalashtirish masalasining qo`yilishi Chiziqli programmalashtirish chiziqli funksiyaning eng katta va eng kichik qiymatini o`zgaruvchilarga nisbatan chiziqli chegaraviy shartlar qo`yilgan holda aniqlash bilan shug`ullanadi. Shuning uchun, chiziqli programmalashtirish masalalari funksiyaning shartli ekstremum masalalari qatoriga kiradi. Lekin chiziqli programmalashtirish masalalari ko`p o`zgaruvchili bo`lgani uchun matematik analizdagi funksiya ekstremumini aniqlashning klassik usulini to`g`ridan-to`g`ri qo`llash mumkin emas. Shuning uchun chiziqli programmalashtirish masalalarini yechishning maxsus usullari ishlab chiqilgan. Ular yordamida, ko`pgina masalalarni, ayniqsa, iqtisodiy masalalarni yechish maqsadga muvofiq.
Ta’rif. Berilgan
11 a 1 x + 12 a 2 x +...+ 1n a n x  b1 , 21 a 1 x + 22 a 2 x +...+ 2n a n x  2 b , ..................................... m1 a 1 x + m2 a 2 x + ... + mn a n x  m b , j x  0, j  1, n , i b  0, i  1,m ,  esa,    , , belgilardan biri. Chiziqli chegaraviy shartlar (chiziqli sistema)ni qanoatlantiruvchi va f= 1 c 1 x + 2 c 2 x +...+ n c n x funksiyaga ekstremum (max, min) qiymat beruvchi nomanfiy j x o`zgaruvchilarning qiymatlarini topish masalasiga chiziqli programmalashtirish masalasi deyiladi. Bu yerda ij a , , i j b c ( i  1, m ; j  1, n ) - berilgan o`zgarmas sonlar. Ba’zan, chiziqli programmalashtirish masalasining o`zgaruvchilariga ba’zi yoki barcha j lar uchun j x  0 yoki i b i i   x d shartlar ham qo`yilishi mumkin. O`zgaruvchilarga nisbatan bunday chegaralanishlarga to`g`ri chegaralanishlar deyiladi. Chiziqli programmalashtirish masalalarini yechishga qo`llaniladigan usullarning ko`pchiligi chegaraviy shartlarning o`ng va chap qismlarini bog`lovchi belgilarning qo`yilishiga ham ma’lum shartlar qo`yadi, masalan, eng keng qo`llaniladigan simpleks usul (bu usulga keyinroq 21 to`xtalamiz) yordamida quyidagi ko`rinishda beriladigan chiziqli programmalashtirish masalalari echiladi: f= 1 c 1 x + 2 c 2 x +...+ n c n x  max (min) (2.1.1) 11 a 1 x + 12 a 2 x +...+ 1n a n x =b1 , 21 a 1 x + 22 a 2 x +...+ 2n a n x = 2 b , (2.1.2) ..................................... m1 a 1 x + m2 a 2 x +...+ mn a n x = m b , j x 0, j  1, n i b 0, i  1,m , (2.1.3) bu yerda, «  » belgi berilgan shartlarda f maqsad funksiyaning qiymatini maksimallashtirish (minimallashtirish) ma’nosiga egadir. (2.1.1), (2.1.2), (2.1.3) – ko`rinishida beriladigan chiziqli programmalashtirish masalasini kononik formadagi chiziqli programmalashtirish masalasi deyiladi. Chiziqli programmalashtirish masalasi shartlari chiziqli tenglamalar va tengsizliklar sistemasidan iborat quyidagi ko`rinishda berilgan bo`lsin:   min max, 1     n j j j f X c x (2.1.4) , 1, , 1 1 a x bi i m n j  ij j    (2.1.5) , 1, , 1 2 1 a x bi i m m n j  ij j     (2.1.6) , 1, , 2 1 a x bi i m m n j  ij j     (2.1.7) x j  0, j 1,n (2.1.8) Bunday masalani kononik formaga, ya’ni chegaraviy shartlar faqat chiziqli tenglamalardan iborat bo`lgan ko`rinishga o`tkazish uchun masalani kengaytirilgan teng kuchli masalaga aylantiriladi. Uning uchun (2.1.6) tengsizlikning chap qismiga 1 2 0, 1, n i x i m m     qo`shiladi, (2.1.7) tengsizligida esa 2 0, 1, n i x i m m     ayriladi va har bir tengsizlik belgisi tenglik belgisi bilan almashtiriladi. n i x  -o`zgaruvchi qo`shimcha o`zgaruvchi deyiladi. Maqsad funksiyaning max qiymatini topish masalasidan uning min qiymatini topish masalasiga ham o`tish mumkin: 1 1 max min( )