Chiziqli dasturlash masalalarini yechishning simplek usuli

1-misol

z=5x1-x2+3x3
chiziqli funksiyaga maksimum qiymat beruvchi x1+x2+x32
4x1+2x2+x33 x1-x2+2x3-1
-3x1+2x2-2x35 x10, x2 0,x30
chegaraviy sistemasining mumkin bo‘lgan yechimlari sohasida noma’lumlar topilsin. Chegaraviy sistemani kanonik ko‘rinishda quyidagicha yozib olamiz: x1+x2+x3+x4=2
4x1+2x2+x3+x5=3 x1-x2+2x3+x6=-1
-3x1+2x2-2x3+x7=5 x10, x2 0,x30
Tenglamada bazis o‘zgaruvchilarni simpleks o‘zgaruvchilardan farqlash uchun x4=u1 , x5=u2 , x6=u3 , x7=u4 belgilashlarni kiritamiz va Simpleks jadval tuzamiz.
So‘ 1 -x1 -x2 - x3 Bo‘
u1 2 1 1 1 u2 3 4 2 1 u3 -1 1 -1 2 u4 5 -3 2 -2
Z 0 -5 1 -3
O‘zgaruvchilarning manfiy bo‘lmaslik sharti berilganligini hisobga olib, to‘g‘ridan-to‘g‘ri tayanch yechimni topishga kirishamiz. Ozod hadlar ichida -1 manfiy ishorali koeffitsiyent bor. Shu qatordan ishorasi manfiy bo‘lgan modul bo‘yicha eng katta elementni topamiz. U x2 ustunidagi -1 elementdir. Qoidaga binoan musbat nisbatlar ichidan eng kichigini topamiz:
+min2/1, 3/2, -1/-1, 5/2}=1/1
Demak, unga mos element x2 ustunidagi -1 elemen. Bu element hal qiluvchi element bo‘ladi. Endi Simpleks almashtirish qilib, quyidagi jadvalni tuzamiz.
So‘ 1 -x1 -y3 - x3 Bo‘
u1 1 2 1 3 u2 1 6 2 5 x2 1 -1 -1 -2 u4 3 -1 2 2
z -1 -4 1 -1
Bu jadvaldan ko‘rinib turibdiki ozod hadlar musbat, shu sabab tayanch plan mavjud. Endi optimal yechimini topish uchun Z qatoriga qaraymiz. Bu qatorda ikkita manfiy ishorali koeffitsiyent bor. Ulardan modul bo‘yicha қиймати катта bo‘lgan koeffitsiyentni tanlab olamiz, u -4 elementidir. Qoidaga binoan hal qiluvchi elementni aniqlab yangi jadval tuzamiz:
+min1/2, 1/6, 1/-1, 3/-1}=1/6
Unga mos element x1 ustunidagi 6 elemen. Bu element hal qiluvchi element bo‘ladi. Endi Simpleks almashtirish qilib, quyidagi jadvalni tuzamiz.
So‘ 1 -y2 -y3 - x3
Bo‘
U1 2/3 -1/3 1/3 4/3
X1 1/6 1/6 1/3 5/6
X2 7/6 1/6 -2/3 -7/6
U4 19/6 1/6 7/3 17/6
Z -1/3 2/3 7/3 7/3
Ozod hadlar va Z qatoridagi koeffitsiyentlar musbat. Demak, optimal yechim topildi, ya’ni u2=u3=x3=0 va x1=1/6, x2=7/6 bo‘lganda Z ning maksimal qiymati 1/3 ga teng bo‘ladi, ya’ni z=-1/3.
2-misol.
Berilgan chiziqli programmalash masalasining maqsad funksiyasiga min qiymat beruvchi yechimni toping.
x1+x2 2
2x1-x2 2
10, x20
Z=x1-x2min Chegaraviy sistemani kanonik ko‘rinishda quyidagicha yozib olamiz:
x1+x2+x3 =2
-2x1+x2+x4 =-2
Simpleks jadval quramiz. Birinchi jadvalda ozod hadlar ichida manfiy element mavjud. Shuning uchun tayanch planni topamiz. Bu jadvaldan hal qiluvchi elementni topib, Simpleks almashtirish bajaramiz va ikkinchi жадвалга эга bo‘lamiz. Ikkinchi jadvalda tayanch plan mavjud. Shu sabab undan optimal planni topishga o‘tamiz.

Сў 1 -x₂ -x₂
Бў

y1	2	1	1		y1	1	1/2	3/2
y2	-2	-2	1		x1	1	-1/2	-1/2
z	0	-1	1		z	1	-1/2	1/2

Optimal planni topish uchun Z- qator elementlarini manfay holga keltirish kerak. Buning uchun jadvaldan hal qiluvchi elementni topamiz. Hal qiluvchi element 3/2. Simpleks almashtirish qilib quyidagi jadvalga ega bo‘lamiz.
So‘ 1 -y2 -y1
Bo‘
x2 2/3 1/3 2/3 x1 4/3 -5/6 -1/3
Z 2/3 -7/6 -1/3
Jadvaldan ko‘rinib turibdiki maqsad funksiyasiga minimal qiymat beruchi nuqta mavjud, ya’ni:
x1=4/3; x2=2/3; zmin=2/3.

Adabiyotlar

1.Badalov F.B. Optimallash nazariyasi va matematik dasturlashtirish. “O‘qituvchi”, Toshkent, 1989y.
2.Kuznetsov Y.N., Kubozov V.I., Voloshenko A.B. Matematicheskoye prpogrammirovaniye. “Visshaya shkola” M. 1980g.
3.Kuznetsov A.V., Novikova G.I., Xolod N.I. Sbornik zadach po matematicheskomu programmirovaniyu. Minsk, Visheyshaya shkola, 1985g.