Tema : Sızıqlı programmalastırıw máselesin jasalma bazis usılı menen sheshiw. Mısal sheshiw

Mısal:
1. 16 - másele. Tómendegi

shegaralıq shártlerde F = -2x1+3x2-6x3-x4 funksiyaning minimum ma`nisin tabıń.
Sheshiw. Máseleni sızıqlı programmalastırıwdıń tiykarǵı máselesi kórinisine keltiremiz: Máseleniń aqırǵı sisteması daǵı belgisiz koeficiyentlerinen dúzilgen vektorlardı kórip shıǵayıq :

Pl, P2, P3, P4, P5 hám P6 vektorlar ishinde tek eki birlik vektor ámeldegi (P4 hám P5). Sol sebepli sistema daǵı 3-teńlemediń shep bólegine oń qosımsha ózgeriwshi x_j, ni kiritemiz hám keńeytirilgen máseleni sheshemiz:
Yaǵnıy tómendegi
2 xl +X2-2 X3 +X4 =24, x1+2 x2 +4 x3+x5 = 22, x1-x2 +2 x3-x6 +x7 =10,
Xj O, U=W)
shegaralıq shártlerde F (X) = 2 x1-3 x2 +6 x3+x4 -Mx7 funksiyanıń maksimum maydalanǵan gósh- tini tabamız. Bul jerde fl, =[;} Keńeytirilgen
32
máseleniń P4, P5 hám P6 birlik vektorlar orqaldi anıqlanǵan tayansh sheshimi X = (0; O; O; 24; 22; O; 10 ) boladı.
Dáslepki berilgenlerge qaray tómendegi kesteni dúzemiz:
1- jadva/

Bazis so

po 2 -3 6 I 0 0 -M
P, pl p) p4 P; p6 P,
I
2
3
4 P4 P;
P, I
0
-M 24
22
10
24 2
I I
0 I
2
-I
4 -2
4
2
-8 I
0
0
0 0
I
0
0 0
0
-I
0 0
0
I
0
0
5 -10 -I I -2 0 0 1

Bul kesteniń 4 hám 5 (m+ l, m+2) qatarların toltırıw ushın

m
F (xo) =-M" f, b; hám flj=c;1 x;1 j+c;2 X;2 j+... +c;mX;mj-cj, bul jerde
i=l
i1, ız,.. ., im bazis vektorlaming tártip nomerleri, x j, X;2 j,
•
•
•, ximj
bolsa Pif vektor yoyilmasining koefficiyentleri, bazis vektorlarǵa uyqas bolǵan Xj (j = ) ni jazıp alamız. Ol tómendegishe boladı :
X1 = (0; 0; 0; 2; I ;0; l);
X2 = (0; O; O; l; 2; O;- l);
X3 = (O; O; O; -2; 4; O; 2);
X4 = (0; 0; 0; l; 0; 0; 0);
X5 = (0; 0; 0; 0; I; O; 0);
X6 = (0; O; O; O; O; O; -1);
X7 = (O; 0; 0; 0; 0; 0; 1).

Joqarıdaǵı tayansh sheshimlerge uyqas bolǵan F0 (x) hám Zj (xj)

(j = ) laming bahaların esaplab shıǵamız : Fo (x) =24-10 M; Z4 (X4) =l+O-M;
Z1 (X1) =2-M; Z5 (Xs) =0+0-M;
Z2 (X2) =1+M;
Z3 (X3) =-2-2 M;
Z6 (X6 ) =0+M; Z7 (X7) =0-M.
33
Endi /J, J.
= z1 -c1 ayırmalardı esaplab shıǵamız :
/J,.I = Z1 -c1 =0-M;
/J,.2 = Z2 -C2 =4+ M;
/J,.3 = Z3-C3 =-8-2 M;
/J,.4 = Z4 - C4 = 1-1 = O;
/J,.5 =Z5-C5 =0-0=0;
1 J,.6 = Z6 - c6 = 0+ M;
/J,.7 =Z7-C7 =-M +M =0.
Bul jerde F0 hám /J,.; laming strukturalıq bólimleri eki jıyındınan ibarat. Sol sebepli bul jıyındılardıń M ga baylanıslı bolmaǵanlarınıń koefficiyentlerin 4-qatarǵa, baylanıslı bolǵanlarınıń
koefficiyentlerin 5-qatarǵa jazamız. Bunday jazıw kestelerdi almastırıwdı ańsatlashtiradi (1-kestege qarang).
1- jadvalning 5-qatarında eki teris san ámeldegi: {-1; -2}. Bul sonı kórsetedi, keńeytirilgen máseleniń jobası optimal emes. Simpleks usıldı qollap, bul rejani jaqsılaymız. Nátiyjede tómendegi keste payda boladı :
2-keste
i
Bazis so
po 2 -3 6 I 0 0
pl p2 P3 p4 PS p6
I
2 P4 PS I
0 34
2 3
-] 0
4 0
0 I
0 0
I -I
2
3
P3 0 5 -I
2 --I
2
I
0
0 I
-
2
4 indeks 64 4 0 0 0 0 -4
Bul kestede 4 qatar ámeldegi, sebebi jasalma bazis P7 vektor bazisdan shıǵarıldı. 2- javdaldan kórinip turıptı, olda x1 = x2 = 0, x3 = 5, x4 = 34, x5 = 2 dáslepki máseleniń tayansh sheshimleri bolıp tabıladı.
X = (0; 0; 5; 34; 2) bolsa tayansh reja bolıp tabıladı. F (O; 0; 5; 34; 2) = 64 maqset funksiyasınıń bul rejege uyqas bolǵan ma`nisi bolıp tabıladı.
2- jadvalning indeks qatarında P6 vektor ústininde (-4) teris san bar. Sol sebepli P6 vektomi bazisga kiritip, P5 vektomi bazis­ den shıǵaramız hám simpleks keste dúzemiz.
34
3- jadva/
i
Bazis so
P., 2 -3 6 I 0 0
P, pi pl p4 P; p6

I

2
3
p4 P;
p1
I

0

6
35

I

11/2
2

2

1/2
0

0

I
1
0

0
1/2

1/2
1/4
0

1
0
4 lndeks

qatarı F=68 2 8 0 0 2 0

Kestede t-. 1 = z1-c1 Jar ishinde teris sanlar joq. Sol sebepli bul kestege tiykarlanıp tabılǵan jańa tayansh joba optimal bolıp tabıladı. Sonday eken,

dáslepki máseleniń tayansh jobası x• = (0; 0;.!. ..!. ; 0; 1) opti-
2
mal reja bolıp tabıladı. Bul rejege tiykarlanıp maqset funksiyasınıń ma`nisi
Fmax =2 x1 -3 x2 +6 x3+X4 =2-0-3-0+6
•1 l+l-35=68.
1. 17- másele. Tómendegi
x1+3 x2 +2 x3 +2 x4 =3,
{ 2 x1+2 x2 +x3+x4 =3,
x1 o, J=l, 2, 3, 4
shártlerdi qánaatlantiruvchi
F = 5 x1+3 x2 +4 x3 -x4
funksiyanıń maksimum ma`nisin tabıń.
Sheshiw. Ekenin aytıw kerek, sistemada birlik matritsa joq. Hár bir teńlemege birden teris bolmaǵan, uyqas túrde, x5 0, x6 0 jasalma bazisli ózgeriwshilerdi k. iritamiz. Nátiyjede berilgen máselege
salıstırǵanda keńeytirilgen másele dep atalıwshı máselege ótemiz.

35
X5 = (0;0;0;0; 1;0), Z5 (X5) =0-M,

X6 = (0;0;0;0;0;1), Z1 (X1) =0-M.
Endi f" J..
= ZJ -cJ ayirmani esaplab shıǵamız :
f"..1=-5-3 M;! '-. 2 =-3-5 M;
f"..3 =-4-3 M;
f"..4 =I-3 M;! '-. 5 =0+0-M;
f"..6 =0+0-M.
Esaplawlardı atqarıp, ZJ -cJ bahalardı tabamız hám M dıń sızıqlı funksiya ekenligin anıqlaymız.
Bul jerde hám! '-.. laming strukturalıq bólimleri eki jıyındınan ibo­ rat. Sol sebepli bul jıyındılardıń M ga baylanıslı bolǵanların 1- simpleks kesteniń 3-qatarına (m + l qatarına ), M ga baylanıslı bolmaǵanların 4-qatarına jazamız. Nátiyjede 1- simpleksjadval katekleri
tolıqtı.
1- simpleksjadval
i Bazis- Jar Bazis koeffitsi- yentlar
Po 5 3 4 1 -M -M
pl p2 P3 p4 ps p6
1 ps -M 3 1 3 2 2 1 0
2 p6 -M 3 2 2 1 1 0 1
m + l m+2 Kesteniń (m + 2) qatarında teris sanlardıń bar ekenligi tayansh sheshimdiń optimal emesligin ańlatadı jáne onı jaqsılaw múmkin boladı. Kesteniń (m + 2) qatarında eń kishi san (-5) P2 vektor bahası bolǵanlıǵı ushın gilt ústin P2 ústini boladı. min{};f}=1
olardıń kesilispesindegi 3 element bolǵanlıǵı ushın Ps vektor qatarı gilt qatar, 3 sheshiwshi (gilt) element boladı. Sonday eken, Ps ni bazisdan
shıǵarıp, ornına P2 vektordı bazisga kiritemiz. 2-simpleks kesteni dúzemiz.
37
2- simpleks keste
i Bazis- lar Bazis koeffitsi- yentlar
po 5 3 4 I -M -M
pl p2 p) p4 ps Pb
I pl 3 I 1/3 I 2/3 2/3 1/3 0
2 p6 -M I 1/3 0 -1/3 -1/3 -2/3 I
m + 1 zi-ci 3 -4 0 -2 3 I 0
m + 2 zi-ci -1 -4/3 0 1/3 1/3 513 0

2-simpleks kestesiniń (m + 2) qatarı tiykarǵı bóleginde (-3) teris san bolǵanlıǵı ushın P1 vektor ústini gilt ústin, P6 vektor qatarı

4
gilt qatar, 3 sheshiwshi (gilt) element boladı. Bazisdan P6 jasalma
vektordı shıǵarıp, P1 vektordı bazisga kiritip, 2-simpleks keste­ dagidek, 3-simpleks kesteni payda etemiz:
3- simpleks Keste
i Bazis- lar Bazis koeffitsi- yentlar
Po 5 3 4 I -M -M
pl p2 p) p4 ps po
I p2 3 3/4 0 I 3/4 3/4 l/2 -I/4
2 p6 5 3/4 I 0 -I/4 -l/4 -1/2 3/4
m + 1 zi-ci 6 0 0 -3 2 -I 3
m + 2 zi-ci 0 0 0 0 0 1 1

2- kestede (m + 2) qatarda jasalma bazis mánislerinen tısqarı hámme bahalar O ga teń boladı :

M sanınıń tańlanıwına tiykarlanıp, P5 hám P6 vektorlar endi bazisga tushmaydi.

38
x• = (¾; ¾; 0; 0; 0) sheshim berilgen máseleniń sheshimi

boladı, lekin ol optimal emes, sebebi (m + l) qatarda teris baha bar. Endi sheshimdi jaqsılaw (m + l) qatar boyınsha alıp barıladı.
z3 -c3 = -3 < 0 bolǵanlıǵı ushın P3 vektor ústini gilt ústin, P2
3
vektor qatarı gilt qatar, 4 sheshiwshi (gilt) element bolıp, (m + 2)
qatar endi esapqa alınbaydı. Joqarıda kórsetilgen usıl menen 4-simpleks kesteni dúzemiz:
4- simpleks keste
i Bazis- lar Bazis koeffitsi-
yentlar
Po 5 3 4 I -M -M
pl pi PJ p4 Ps p6
I
PJ 4
I 0 4/3
I
I 2/3 -I/3
2
pl 5
I I 1/3 0 0 -I/3 2/3
m + I -s 9 0 4 0 5 l+M 2+M
3-simpleks kesteden qoyılǵan máseleniń optimal sheshimi
X = (1 ;0; I ;0;0) bolıp, Zmax (X) = 9 boladı. Birinshi hám ekinshi qatarlardı óz-ara almastırıp, P5 hám P6 vektorlar ústininde teris matritsani payda etemiz.