Mavzu: Chiziqli programmalashtirish masalalari Reja: Asosiy tushunchalar. Chiziqli programmalashtirish masalasining qo’yilishi

Mavzu: Chiziqli programmalashtirish masalalari
Reja:
1. Asosiy tushunchalar. Chiziqli programmalashtirish masalasining qo’yilishi.
2. Chiziqli programmalashtirish masalasining yechimi.
3. Chiziqli programmalashtirish masalasining geometrik talqini. Masalani grafik usulda yechish.

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 masalalrni, ayniqsa, iqtisodiy masalalarni yechish maqsadga muvofiq.
Ta’rif. Berilgan


*esa , , = belgilaridan biri.
Chiziqli chegaraviy n shartlar (chiziqli sistemani)ni qanoatlantiruvchi va
funksiyaga ekstremum (max, min) qiymat beruvchi nomanfiy o’zgaruvchilarning qiymatlarini toppish masalasiga chiziqli programmalashtirish masalasi deyiladi.
Bu yerda - berilgan o’zgarmas sonlar.
Ba’zan, chiziqli programmalashtirish masalasining o’zgaruvchilariga ba’zi yoki barcha lar uchun yoki 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’ngva chap qismlarini bog’lovchi belgilarningn qo’yilishiga ham ma’lum shartlar qo’yadi, masalan, eng ko’p qo’llaniladigan simpleks usul( bu usulga keyinroq to’xtalamiz) yordamida quyidagi ko’rinishda beriladigan chiziqli programmalashtirish masalalari yechiladi:
f= 1 c 1 x + 2 c 2 x +...+ n c n x  max (min) (2.1.1)
a 1 x + 12 a 2 x +...+ 1n a n x =b1 ,
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:
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 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:
max min( )
Qulaylik uchun bundan keyin biz chiziqli programmalashtirish masalasining maqsad funksiyasini min qiymatini topish usullarini ko`ramiz. Chiziqli programmalashtirish masalasini turli formalarda yozish mumkin:
a) Vektor forma
Px P x P x P     n n (2.1.9)
chegaraviy shartni qanoatlantiruvchi va
Z CX  ( ) (2.1.10)
chiziqli funksiyaga min (max) qiymat beruvchi 1 2 ( , ,..., ) X x x x  n 0 vektorni aniqlash kerak.
Bu yerda ( ) CX - skalyar ko`paytma, 1 2 ( , ,..., ) C c c c  n - vektor,