Strreplkirish I bob. Chiziqli programmalashtirish masalalari 1-§. Chiziqli programmalashtirish masalalaining amaliy masalalari

I Bob. Chiziqli programmalashtirish masalalari
1-§. CHiziqli programmalashtirish masalalaining amaliy masalalari.

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

, , ,
esa belgilardan biri. esa
Chiziqli chegaraviy shartlar (chiziqli sistema)ni qanoatlantiruvchi va

funksiyaga ekstremum (max, min) qiymat beruvchi nomanfiy o`zgaruvchilarning qiymatlarini topish masalasiga chiziqli programmalashtirish masalasi deyiladi.
Bu yerda , ( , ) - berilgan o`zgarmas sonlar.
Ba’zan, chiziqli programmalashtirish masalasining o`zgaruvchilariga ba’zi yoki barcha j 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`ng va chap qismlarini bog`lovchi belgilarning qo`yilishiga ham ma’lum shartlar qo`yadi, masalan, eng keng qo`llaniladigan simpleks usulnyordamida quyidagi ko`rinishda beriladigan chiziqli programmalashtirish masalalari echiladi:
→max(min) (1.1.1)
(1.1.2)
, , , (1.1.3)
bu yerda, « » belgi berilgan shartlarda f maqsad funksiyaning qiymatini maksimallashtirish (minimallashtirish) ma’nosiga egadir. (1.1.1), (1.1.2), (1.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:


1.1.4
1.1.5
1.1.6
1.1.7
1.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 (1.1.6) tengsizlikning chap qismiga qo`shiladi, (1.1.7) tengsizligida esa ayriladi va har bir tengsizlik belgisi tenglik belgisi bilan almashtiriladi. -o`zgaruvchi qo`shimcha o`zgaruvchi deyiladi.
Maqsad funksiyaning max qiymatini topish masalasidan uning min qiymatini topish masalasiga ham o`tish mumkin:

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.
1.1.9
chegaraviy shartni qanoatlantiruvchi va
Z (CX) (2.1.10)
chiziqli funksiyaga min (max) qiymat beruvchi vektorni aniqlash kerak.
Bu yerda (CX) - skalyar ko`paytma, - vektor,
, , ………, - bir ustunli
vektorlar.
b) Matritsali forma.
Chiziqli funksiya
f CXmin (max) (1.1.11)
Chegaraviy shartlar:
AX B , X 0 , (1.1.12)
Bu yerda - bir qatorli matritsa; -matritsa
berilgan chiziqli sistemaning koeffitsientlaridan tuzilgan, - ustun
matritsa.
c) Yig`indi belgisi bilan beriladigan forma.
chiziqli funksiyaning min(max) qiymati


shartlarda aniqlansin.