Желілік программалау есептерін шешудің

Экономикалық-математикалық әдістер 
 
22
қабылданады  да,  процедура  қайталанады.  Бұрыштың  сүйір 
ұшын  іріктеу  есептің  шешімі  табылғанға  дейін  немесе  есептің 
шешілмейтіндігі  белгіленгенге  дейін  жүре  береді.  Сонымен 
қатар  қадам  саны  түпкілікті,  себебі  жоспарлар  жиынтығы  немесе 
дөңес  көпқырлылық,  немесе  дөңес  көпқырлы  аумақ,  бірақ  екі 
жағдайда да шеткі нүктелер (бұрыштардың сүйір ұштары) саны 
түпкілікті. 
 
1.5.1.  Тірек  жоспардың  оңтайлылық  жəне  оңтайсыздық   
өлшемдері 
 
ЖП есебі канондық формада берілсін делік: 
 
А
1
х
1 
 + А
1
х
2
 + … + А
n
х
n 
= В              (6) 
x
j
  ≥0, j = 1, n
̅
                                    (7) 
 
шарты жағдайында 
 
f(х)= с
1
х
1 
+ с
2
 х
2 
+ … + с
n
х
n   
→ max            (5) 
 
табу керек, мұндағы 
 
;
;
;
2
1
2
1
,
1
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
=
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
=
b
b
b
n
j
a
a
a
A
m
mj
j
j
j
B
Μ
Μ
 
 
Қандай  да  бір 
төмендемеген
  (невырожденный)  тірек 
жоспары  белгілі  болсын  делік  х = (х
1 
х
2 
, …, х
n
).  Талқылау 
қарапайым  болу  үшін  жоспардың  нольдік  емес  компоненттері 
алғашқы m компонент болсын деп, ал қалған компоненттері 0-ге 
тең деп есептелік, яғни х
m+1 = 
х
m+2 
= … = х
n  
= 0. 
Осылайша, бастапқы тірек жоспары мынадай түрге ие: 
Х = (х
1
,
 
х
2
, …, х
m
, 0,0, …, 0) немесе  Х = (х
1
,х
2
,…, 
 
х
m
) 
Бəрімізге  мəлім,  əрбір  тірек  жоспарға  берілген  жүйенің 
желілік  тəуелсіз  векторлар  жүйесі  А
1
,А
2 
,…,  А
kn 
сəйкес  келеді. 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
23
Бастапқы  тірек  жоспарына  х = (х
1
,х
2
, …, 
 
х
m
  )  m-өлшемдік 
кеңістікте  базис  құратын  А
1
,А
2 
,…,  А
m
.  Желілік  тəуелсіз  векторлар 
сəйкес келеді.  х = (х
1
,х
2
, …, 
 
х
m
 ) -  есеп жоспары болғандықтан, 
ол (6) шартын қанағаттандырады, яғни 
 
А
1
х
1
+А
2
 х
2
,+ … + А
m
 х
m 
= В      немесе  
B
i
Ai
m
i
x
=
Σ
=1
 (8) 
 
Есептің басқа еркін жоспарын алайық 
Х(
θ
) = (х
1
(
θ
),х
2
(
θ
), …, 
 
х
m 
(
θ
),х
m+1
(
θ
), …, х
n 
(
θ
)), 
Бұл  бастапқы  х  жоспарынан  өзінің  j–ші  компонентасының 
(j>m) 0-ден өзгешелігімен ерекшеленеді, яғни 
Х
m+1
(
θ
) = Х
m+2
(0)=...= X
j-1
(
θ
)= Х
j+1
(
θ
) =…=
 
Х
n 
(
θ
) =0,Х
j
(
θ
) =
 
θ
 
> 0 
Осы жоспарлар арасында қандай байланыс бар екенін, яғни х 
жоспарынан  жаңа  Х(
θ
)  жоспарына  қалай  өтуге  болатындығын 
қарастырайық. 
Х(
θ
)  есептің  жоспары  болғандықтан,  ол  да (6) шартты 
қанағаттандырады: 
A
1
x
1
(
θ
)+...+ A
m
x
m
(
θ
)+A
j
x
j
(
θ
)=B                       немесе 
B
A
Ai
x
x
j
j
i
m
i
=
+
Σ
=
)
(
)
(
1
θ
θ
          
         немесе 
(8) формуланы алып, екі бөліктен де A
j 
·
θ
 шығарып тастаймыз: 
)
10
(
1
θ
θ
⋅
−
=
⋅
−
Σ
=
A j
B
A j
i
Ai
m
i
x
 
 
A
1,
...,A
m 
  векторлар  жүйесі  базис  құратын  болғандықтан,  кез 
келген 
)
,
1
(
n
j
j
A
=
векторын  осы  базис  векторларына  бір  рет 
қана жіктеуге болады: 
)
11
(
,
1
,
1
n
j
ij
Ai
m
i
j
A
=
Σ
=
=
Ζ
 
)
9
(
)
(
)
(
1
θ
θ
θ
⋅
−
=
−
=
Σ
=
A j
B
j
A j
B
i
Ai
m
i
x
x
(9) 

Экономикалық-математикалық әдістер 
 
24
мұндағы 
−
Ζ
ij жіктеу  коэффициенті. (11)-ді (10)-ға  əкеліп 
қояйық: 
)
12
(
)
(
1
1
1
θ
θ
θ
θ
A
j
B
ij
xi
Ai
m
i
или
A j
B
ij
Ai
m
i
xi
Ai
m
i
−
=
−
Σ
=
⋅
−
=
Σ
=
−
Σ
=
Ζ
Ζ
  
(9)  жəне (12) формулаларын  салыстыра  отырып,  олардың  екеуі 
де сол бір вектордың В - A
j 
·
θ
  базис бойынша жіктелуі екендігін 
көреміз, ал мұндай жіктеу біреу ғана болғандықтан, онда, демек, 
жіктеу коэффициенттері тең болуы керек, яғни 
 
)
13
(
,
1
,
,
1
,
)
(
n
j
m
i
ij
xi
xi
=
=
Ζ
⋅
−
=
θ
θ
 
 
 
Осылайша,  бір  тірек  жоспарынан  екінші  тірек  жоспарына 
өтуге  болатын  реккуретті  қатынас  алдық.  Сонымен  бірге  х(
θ
) 
(5) - (7) есебінің жоспары болу үшін,   
θ
     x
i 
(
θ
) ≥ 0  болатындай 
етіп таңдалып алынады. Бұдан басқа, х(
θ
)  тірек жоспары болуы 
үшін, онда m- нен кем нольдік емес компоненттер болуы қажет, 
яғни 
θ
  х
1
(
θ
)  компонеттерінің  бірі 0-ге  айналатындай  етіп 
таңдалып алынады: 
n
j
m
i
ij
xi
ij
xi
xi
,
1
,
,
1
,
0
)
(
=
=
Ζ
=
=
Ζ
−
=
θ
θ
θ
 
Ең дұрысы, 
0
min
>
Ζ
=
ij
xi
i
θ
 
алу керек. 
0
min
>
Ζ
=
Ζ
=
rj
r
ij
i
i
x
x
θ
 болсын делік, онда 
Х
r
(
θ
) = Х
r 
-
θ
 ·Z
rj
 =
 
Х
r 
–X
r
 = 0
, 
т.е. 
Х(
θ
) = Х
1
(
θ
),...,X
r-1
(
θ
),0,Х
r+1
(
θ
),…,
 
Х
m 
(
θ
),0...Х
j
(
θ
)... 0; 
немесе 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
25
Осылайша,  Х(
θ
)  құрамында  m  нольдік  емес  компоненттер 
жəне  А
1
,  А
2
,...,  А
r-1
,  А
r+1
,...,А
m 
  жоспарының  нольдік  емес 
компоненттеріне  сəйкес  келетін  векторлар  бар,  A
j 
  желілік 
тəуелсіз. Демек, х(
θ
) жоспары – тірек жоспары. 
Назар  аударатын  тағы  бір  мəселе,  бір  х  тірек  жоспарынан 
екінші х(
θ
) жоспарына өткенде бастапқы А
1,
,...,А
m 
бір А
r  
векторы 
шығарылған,  ал  қалған  А
m+1
,..., A
n 
векторларының  ішіндегі 
екінші A
j  
векторы енгізілген. 
Желілік  форманың  жаңа  х(
θ
)  тірек  жоспарына  сəйкес  мəнін 
анықтайық.  Айта  кететін  нəрсе, 
x
i
ci
m
i
x
f
Σ
=
=
1
)
(
-  желілік 
форманың  бастапқы х жоспарына сəйкес келетін мəні. 
    
)
(
)
(
1
)
(
(
θ
θ
θ
x j
c j
i
ci
m
i
x
f
x
+
Σ
=
=
 
Осы формулаға (13)-ті қоямыз: 
c j
ij
ci
m
i
xi
ci
m
i
ij
i
ci
m
i
x
f
C
x
j
−
Σ
=
−
Σ
=
=
⋅
+
−
Σ
=
=
Ζ
Ζ
1
(
1
)
1
)
(
(
(
θ
θ
θ
θ
) 
)
(
1
x
f
i
ci
m
i
x
=
Σ
=
екендігін 
ескере 
отырып 
жəне 
,
1
Ζ
Ζ
=
Σ
=
j
ij
ci
m
i
  деп  белгілегенде,  соңғы  формула  мынадай 
түрге  ие  болады: 
),
(
)
(
))
(
(
c
j
j
x
f
x
f
−
−
=
Ζ
θ
θ
 
),
j
j
C
j
Δ
=
−
Ζ
 
деп белгілеп, мынаны аламыз: 
Δ
−
=
j
x
f
x
f
θ
θ
)
(
))
(
(
, себебі 
θ
  
≥ 0 болса, онда 3 жағдай болуы мүмкін: 
1)  ∆
j
  ≥ 0 барлығы  үшін 
n
j
,
1
=
,  сонда  f(x(
θ
))≤ f(x)
,
  яғни  х 
жоспарына  желілік  форманың  максималды  мəні  сəйкес  келеді. 
Тірек жоспарының оңтайлылығының келесі критерийлерін аламыз. 
4-теорема. (5)-(7) есептерінің x=(x
1,
 x
2
, ..., x
n
) тірек  жоспары 
оңтайлы болып табылады, егер ∆
j
 ≥ 0 кез келген 
n
j
,
1
=
үшін болса. 

Экономикалық-математикалық әдістер 
 
26
2)  ∆
j
 < 0 кейбір  ∆
j
 < 0 үшін  жəне  оған  сəйкес  келетін 
Ζ
ij
арасында оң сан болатын болса. Мұндай  жағдайда f(x(
θ
))> 
f(x)
,
, яғни бұл жағдайда х бастапқы жоспары оңтайлы емес жəне 
желілік форманың үлкен мəні бар Х(
θ
) жоспарын құруға болады. 
Осылайша,  тірек  жоспарының  оңтайлы  еместігінің  келесі 
критерийлерін аламыз. 
5-теорема.  Егер  х  тірек  жоспары  төмендемеген  жəне  ∆
j
 < 0 
кейбір 
k
j
=
үшін  болса  жəне 
Ζ
ik
сандарының  арасында  оң 
сандар бар болатын болса, онда х жоспары – оңтайлы емес жəне 
оның жақсартылуы мүмкін. 
3)  ∆
j
 < 0 кейбір 
k
j
=
үшін  жəне  барлық 
Ζ
ik
≤0,  онда  х 
жоспары  оңтайлы  емес,  бірақ  жаңа  жоспар  құру  мүмкін  емес, 
себебі төмендегідей болатын 
θ
  табу мүмкін емес: 
0
min
>
Ζ
=
ik
xi
i
θ
 
6-теорема.  Егер  ∆
j
 < 0 кейбір 
k
j
=
үшін  жəне  барлық 
Ζ
ik
≤0, онда есеп шешілмейді. 
 
1.5.2. Бастапқы тірек жоспарды құру 
 
Жоғарыда  айтылғандай,  ЖП  есебін  симплексті  тəсілмен 
шешу бір тірек жоспарынан желілік форма мəні ұлғаятын екінші 
жоспарға  өтуге  негізделеді,  яғни  оңтайлы  жоспарды  іздей 
процесі кейбір бастапқы тірек жоспарынан басталады. 
(5)-(7) есебін қарастырайық. Х = (х
1
,
 
х
2
, …, х
m
, 0...0)   – осы 
есептің  төмендемеген  тірек  жоспары  болсын  делік.  Мұндағы 
А
1
,А
2
,…, 
 
А
m 
– есеп базисі. Х-ті (6) шартына қоямыз: 
 
В
i
Аi
m
i
x
=
Σ
=1
  (**) 
 
А
0 
=(А
1
,А
2
,…, 
 
А
m
) –  төмендемеген  матрица  деп  белгілейміз, 
себебі  А
1
,А
2
,…,  А
m 
векторлары  желілік  тəуелсіз.  Сонда  форму-
ланы (**) матрицалық түрде жазуға болады: 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
27
А
0
х = В, где х =(х
1
 ,х
2
,…, х
m
)                          (14) 
 
А
0 
–  төмендемеген  матрица  болғандықтан,  А
0
-1
  кері 
матрицасы  болады,  ол  жалғыз. (14)-ті  сол  жағынан  А
0
-1
-ға 
көбейтейік: 
 
А
0
-1
А
0
х = А
0
-1
В   себебі  А
0
-1
 А
0 
= Е   онда х = А
0
-1
В    (15) 
 
Бастапқы тірек жоспарының компоненттері осылай анықталады. 
Оның оңтайлылығын бағалау үшін шамасын анықтау қажет 
,
1
,
,
1
,
Ζ
Ζ
Ζ
Σ
=
=
=
−
=
Δ
ij
ci
m
i
j
где
n
j
j
j
j
c
 яғни 
Ζ
ij
- A
j
 векторының ажырау коэффициентін 
n
j
ij
Ai
m
i
j
A
,
1
,
1
=
Σ
=
=
Ζ
базисі бойынша табу қажет. 
Бұл  формуланы  енгізілген  А
0 
=(А
1
,А
2
,…, 
 
А
m
)  белгісін 
пайдалана отырып, матрицалық түрде жазамыз: 
 
А
j 
=А
0
х
j
, мұндағы  Х
j 
= (Z
ij
,Z
2j
,... Z
Zmj
) 
 
Осы формуланың екі бөлігін сол жағынан А
0
-1
 –ға көбейтіп, 
аламыз: 
 
А
0
-1
 А
j
 = А
0
-1
А
0
х
j
 ,    яғни, х
j
 = А
0
-1
 А
j                          
(16) 
 
Сонымен, (15) жəне (16) формулалары  бастапқы  тірек 
жоспарын  анықтауға  жəне  оның  оңтайлылығын  бағлауға 
мүмкіндік береді. Дегенмен есептеу процедуралары тұрғысынан 
бұл  формулалар  едəуір  қиындықтар  тудырады.  Егер  А
0
=Е- 
жалғыз матрица болса, есеп недəуір жеңілденеді, онда аламыз: 
 
Х=В  
             
              (17) 
                        х
j
 = А
j
 
 
себебі  А
0
-1
=Е яғни 
 
n
j
m
i
aij
ij
m
i
bi
xi
,
1
,
,
1
,
)
17
(
,
1
,
=
=
=
Ζ
=
=
 

Экономикалық-математикалық әдістер 
 
28
1.5.3. Симплексті əдістің алгоритмі жəне 
есептеу сызбасы 
 
ЖП-дың төмендегі түрде жазылған есебін қарастырайық: 
n
j
x j
b
a
x
x
b
x
a
x
a
x
b
x
a
x
a
x
x
a
m
n
mn
m
m
mm
n
n
m
m
n
n
m
m
,
1
,
0
1
1
2
2
1
2
1
2
1
1
1
1
1
1
=
≥
=
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=
+
+
+
=
+
+
+
+
+
+
+
+
+
+
+
+
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
Λ
 
шарты жағдайында 
f(х)= с
1
х
1 
+ с
2
 х
2 
+ … + с
n
х
n   
→ max  табу керек. 
Бұл есептің векторлық формасы мынадай түрге ие: 
А
1
х
1 
 + А
2
х
2
 + … + А
n
х
n 
= В                 
n
j
j
x
,
1
,
0
=
≥
 шарты жағдайында 
max
1
)
(
→
Σ
=
=
x
C
j
j
n
j
x
f
  табу керек, мұндағы 
 
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
=
0
0
1
1
Μ
A
      ;         
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
0
0
1
0
2
Μ
A
    ;            ...           
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
1
0
0
0
Μ
A
m
  ;   
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
+
+
+
=
+
a
a
a
A
mm
m
m
m
1
1
2
1
1
1
Μ
;
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
=
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
=
b
b
b
a
a
a
A
m
B
mn
n
n
n
Μ
Μ
Λ
2
1
;
2
1
,
 
            

Әлжанова Н.Ш., Сәбитова Х.К. 
 
29
Көріп  тұрғанымыздай,  А
1
,А
2
, …,  А
m
 – векторлар  жүйесі 
желілік тəуелсіз жəне матрица А
0 
= (А
1
,А
2
, … А
m
) =  
 
Е
=
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
1
0
0
0
1
0
0
0
1
Λ
Λ
Λ
Λ
Λ
Λ
Λ
 
Бұл  жағдайда,  егер  А
1
,А
2
, …,  А
m
 – жүйесін  бастапқы  базис 
ретінде қабылдасақ, онда оған х=(х
1
,х
2
, …,  х
m
,0, ..., 0) бастапқы 
тірек жоспары сəйкес келеді. 
Мұнымен қатар, А
0
=Е болғандықтан, (17
′) негізінде 
n
j
m
i
ij
ij
m
i
i
i
a
b
x
,
1
,
,
1
,
1
=
=
=
=
=
Ζ
 
Осылайша, бастапқы тірек жоспары мына түрге ие: 
                х=(b
1
,b
2
, …, b
m
,0, ..., 0). 
Егер нольдік компоненттерді алып тастасақ, онда х = (b
1
,b
2
, …, 
b
m
). 
Тірек  жоспарын  оңтайлылыққа  зерттеуді,  сонымен  қатар 
одан  кейінгі  есептеу  процедураларын  симплексті  деп  аталатын 
төменде берілген кестелер түрінде жүргізген ыңғайлы (2-кесте). 
Бұл  кестедегі  С
0 
бағанында  желілік  форманың  базис  векторында-
ғыдай индекске ие белгісіздерінің коэффициенттері жазылады. 
 
2-кесте 
 
 
 
 
 
С
1 
C
2 
… C
r
  … C
m
 
C
m+1
  …  C
k
…  C
n
 
I  Базис С
0 
B
 
A
1
A
2
… A
r
… A
m
 
A
m+1
  …  A
k
…  A
n
 
1 A
1
 
С
1
 
X
1
 1 0 … 0  … 0 
Z
1m+1
…  Z
1k
  …  Z
1n
 
2 A
2
 
С
2
 
X
2
 0 1 … 0  … 0  Z
2m+1
  …  Z
2k
…  Z
2n
 
∶  ∶ 
∶ 
∶ 
∶ 
∶  ∶  ∶  ∶  ∶ 
∶ 
∶ 
∶  ∶  ∶ 
R A
r
 
С
r
 
X
r
 0 0 … 1  … 0  Z
rm+1
  …  Z
rk
…  Z
rn
 
∶  ∶ 
∶ 
∶ 
∶ 
∶  ∶  ∶  ∶  ∶ 
∶ 
∶ 
∶  ∶  ∶ 
m 
A
m
 
С
m
 
X
m
 0 0 … 1  … 1  Z
mm+1
…  Z
mk
…  Z
mn
 
m+1 
  f(x) 
0 
0 
… 0  … 0 
Δ
m+1 
…  Δ
k 
…  Δ
n 

Экономикалық-математикалық әдістер 
 
30
В бағанында бастапқы тірек жоспарының оң компоненттерін 
жазамыз. Осы бағанда есептеу нəтижесінде оңтайлы жоспардың 
оң компоненттері анықталады. A
j
 (
n
j
,
1
=
) векторларының 
бағандарында осы векторлардың (
Ζ
ij
) базисі бойынша ажырау 
коэффициенті 
орналасады, 
берілген 
жағдайда 
n
j
m
i
ij
ij
a
,
1
,
,
1
=
=
=
Ζ
.  Осылайша,  əуелгі  кестенің 
бірінші m жолы есептің бастапқы деректері негізінде құрылады. 
Ал  кестенің  (m+1) –ші  жолының  көрсеткіштері  есептеліп 
шығарылады.  В  бағанындағы  осы  жолда  желілік  форманың 
берілген  тірек  жоспарына  сəйкес  келетін  мəні  жазылады,  ал 
келесі  A
j 
  бағанында - 
)
,
1
(
,
n
j
С
д
j
j
=
−
=
Ζ
Δ
  мəні. 
Шындығында да, мысалы, 
∆
1 
–ді есептеп шығаралық: 
 
∆
1
=
0
0
0
1
1
1
1
2
1
1
1
21
2
11
1
1
1
1
1
1
=
−
=
−
⋅
+
+
⋅
+
⋅
=
−
Ζ
+
+
Ζ
+
Ζ
=
−
Ζ
Σ
=
−
Ζ
=
С
C
С
С
C
С
С
С
С
С
С
С
С
m
m
m
i
i
m
i
Λ
Λ
 
 
Сол секілді 
0
0
1
0
2
2
1
2
2
22
2
12
1
2
2
1
2
2
1
2
2
2
=
−
⋅
+
+
⋅
+
⋅
=
−
+
+
+
=
−
Σ
=
−
Ζ
Σ
=
−
Ζ
=
=
=
Δ
С
С
C
С
С
а
С
а
С
а
С
С
а
Сi
С
С
С
m
m
m
i
m
i
i
i
m
i
Λ
Λ
  
 
жəне т.б., ең соңында 
0
1
0
0
2
1
1
1
=
−
⋅
+
+
⋅
+
⋅
=
−
Σ
=
−
Ζ
Σ
=
−
Ζ
=
=
=
Δ
С
С
С
С
С
а
С
С
С
С
m
m
m
im
i
m
i
m
im
i
m
i
m
m
m
Λ
 
 
Симплексті  кестенің  бастапқы  деректерін  толтырғаннан 
кейін  итеративті  есептеу  процесі  басталады,  ол  төменде  келті-
рілген бірнеше қадамнан тұрады. 
1-қадам.  Жоспарды  оңтайлылыққа  тексеру.  Бұл  үшін 
(m+1)-ші  жолдың  элементтері  қаралады - 
n
j
j
,
1
, =
Δ
.  Егер 
n
j
j
,
1
,
0
=
≥
Δ
  болса,  онда  осы  кестеде  жазылған  тірек 
жоспары  оңтайлылық  критерийіне  сəйкес  оңтайлы  болып 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
31
табылады.  Есептеу  процесі  аяқталды.  Егер 
∆
j
<0  кейбір  белгі-
ленген  j  үшін  болса,  онда  кестеде  жазылған  тірек  жоспары 
оңтайлы емес болып табылады жəне оның жақсартылуы мүмкін, 
яғни  желілік  формасының  мəні  үлкен  жаңа  тірек  жоспарын 
құруға  болады.  Жоғарыда  айтылғандай,  бір  тірек  жоспарынан 
екінші  тірек  жоспарына  өту  үшін  бастапқы  базис  векторлары-
ның  бірін  шығарып,  оның  орнына  басқа  вектор  енгізу  керек. 
Сондықтан  келесі  қадамдар  базиске  енгізілетін  жəне  одан 
шығарылатын базистерді анықтаумен байланысты болады. 
2-қадам.  Базиске  енгізілетін  векторды  анықтау.  Жалпы 
алғанда, базиске енгізілетін вектор ретінде А
j 
 векторларының ол 
үшін 
∆
j
<0  болатын  кез  келген  векторын  алуға  болады.  Бірақ, 
оңтайлы  жоспар  алу  процесін  жылдамдату  үшін  базиске  А
j
-дің 
ол  үшін 
Δ
j
j
min
  орын  алатын  векторын  енгізген  ыңғайлы. 
Δ
j
j
min
  =
∆
k
<0    болсын  делік.  Бұл  А
k 
  векторының  базиске 
енгізілетінін  білдіреді.  Мұнда  оған  сəйкес  келетін  бағанды 
бағыттаушы деп атайды. 
3-қадам.  Базистен  шығарылатын  векторды  анықтау. 
Базистен  шығарылуы  тиіс  векторларды  анықтау  үшін 
Ζ
>
Ζ
=
ik
i
ik
i
x
0
,
min
θ
  саны  анықталады. 
0
min
>
=
=
Ζ
Ζ
rk
r
ik
i
i
x
x
θ
 
болсын  делік.  Бұл  А
r 
векторының  базистен  шығарылатынын 
білдіреді,  ал  кестенің  r-  ші  жолын  бағыттаушы  деп  атайды. 
Мұнда,  атап  өту  қажет,  егер 
m
i
ik
,
1
,
0
=
≤
Ζ
  болса,  онда 
есеп шешілмейді. 
4-қадам. Симплексті кестенің Гаусс формулалары бойынша 
қайта  құрылуы.  Бұл  қадамда  бастапқы  симплексті  кестенің 
барлық элементтері Гаусс формулалары бойынша қайта құрылады. 
Мұнда  жаңа  тірек  жоспарының  компоненттері  төмендегі 
формулалар бойынша анықталады: 

Экономикалық-математикалық әдістер 
 
32
⎪
⎪
⎩
⎪
⎪
⎨
⎧
Ζ
Ζ
=
=
≠
Ζ
−
)
18
(
;
'
,
r
i
r
i
X
X
rk
xr
rk
xr
i
i
ik
 
 
А
j 
  векторларының  жаңа  тірек  жоспарына  сəйкес  келетін 
жаңа  базис  бойынша  ыдырау  коэффициенті  төмендегі 
формулалар бойынша анықталады: 
 
⎪
⎪
⎩
⎪
⎪
⎨
⎧
Ζ
Ζ
Ζ
⋅
Ζ
Ζ
=
=
≠
−
Ζ
Ζ
)
19
(
;
'
,
r
i
r
i
rk
rj
ik
rk
rj
ij
ij
 
Алынған  х'
i
  жəне  Z
'
ij 
мəндерін  жаңа  симплексті  кестеге 
жазады.  Мұнда  осы  кестенің  (m+1)-ші  жолының  элементтері 
оларды  анықтау  негізінде  немесе  Гаусс  формулалары  бойынша 
анықталады: 
 
⎪
⎪
⎩
⎪
⎪
⎨
⎧
Δ
Ζ
Ζ
−
Δ
=
Δ
Ζ
=
Δ
−
=
)
20
(
;
'
'
,
1
)
(
)
(
n
x
f
x
f
j
k
rk
rj
j
j
k
rk
xr
 
 
Осылайша, (18)-(20) рекурренті  формулаларының  негізінде 
жаңа  симплексті  кестені  аламыз (3-кесте),  онда  жаңа  тірек 
жоспарының  нольдік  емес  компоненттері,  А
j 
  векторларының 
жаңа  тірек  жоспарына  сəйкес  келетін  жаңа  базис  бойынша 
ыдырау коэффициенті жазылады. 
Жаңа симплексті кестені толтырғаннан кейін 1-қадамға, яғни 
жаңа  тірек  жоспарын  оңтайлылыққа  тексеруге  көшеміз. 1-4 
қадамдары  оңтайлы  жоспар  анықталғанша  немесе  есептің 
шығарылмайтындығы белгілі болғанша қайталана береді. 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
33
3-кесте. 
 
 
 
 
С
1 
C
2 
… C
r
 
… C
m
 
C
m
+1 …  C
k
… C
n
 
I 
Ба-
зис
С
0 
B
 
A
1
 
A
2
 
… A
r
 
… A
m
 
A
m
+1 …  A
k
… A
n
 
1 A
1
С
1
  X
1
′ 
1 0 
… Z
 
′
1r
… Z
 
′
1m
Z
 
′
1m+1
…  0  … Z
 
′
1n
 
2 A
2
С
2
  X
2
′ 
0 1 
… Z
 
′
2r
… Z
 
′
2m
Z
 
′
2m+1
…  0  … Z
 
′
2n
 
∶  ∶ 
∶  ∶ 
∶ 
∶ 
∶
∶  ∶
∶ 
∶ 
∶  ∶ ∶ 
∶ 
R A
k
С
k
  X
k
′ 
0 0 
… Z
 
′
rr
… Z
 
′
rm
Z
 
′
rm+1
…  1  … Z
 
′
rn
 
∶  ∶ 
∶  ∶ 
∶ 
∶ 
∶
∶  ∶
∶ 
∶ 
∶  ∶ ∶ 
∶ 
m 
A
m
С
m
  X
m
′ 
0 0 
… Z
 
′
mr
… Z
 
′
mm
Z
 
′
mm+1
…  0  … Z
 
′
mn
 
m+1 
 
  f(x
′
) 
0 0 
… Δ
′
r 
… 0  Δ
′
m+1
… 0 … Δ
′
n 
 
Сонымен,  бір  тірек  жоспарынан  екіншісіне  өту  бір 
симплексті кестеден екіншісіне өтуге тіреледі. Жаңа симплексті 
кесте элементтерін (18)-(20) рекуррентті формулалар көмегімен, 
немесе тікелей осылардан шығатын ережелер бойынша есептеп 
шығаруға болады. Бұл ережелер мынадай. 
r – кестенің  бағыттаушы  жолы,  ал  k – бағыттаушы  бағаны 
болсын делік. r –ші жол мен k –ші бағанның қиылысында тұрған 
элементті  бағыттаушы  деп  атаймыз.  Сонда  С
0 
  бағанының  бағыт-
таушы жолына берілген С
k 
 шамасын қоямыз. Бастапқы кестенің 
бағыттаушы жолының (* жаңа кестенікі осы жолдың элементтерін 
бөлумен анықталады) элементтерін бағыттаушы элментке. Жаңа 
кестенің  бағыттаушы  бағанының  бағыттаушы  элменттерден  басқа 
барлық элменттері 0-ге тең, жаңа кестенің бағыттаушы элменті 
1-ге  тең.  Жаңа  кестенің  базисінде  қалған  векторлар  өзгеріссіз 
жазылады.  Қалған  элементтер  тікбұрыштың  келесі  мнемоникалық 
ережесі  бойынша  анықталады.  Жаңа  кестенің  Z
'
ij
  элементін 
анықтау үшін ескі кестеде тікбұрыш құрылады, ол i-ші жəне r-
ші жолдарымен жəне j-ші жəне k-ші бағандарымен анықталады. 
 
  
j-ші баған  
k-ші баған 
 
 
Z
ij
 
 
Z
ik
 
i-ші жол 
 
 
 
 
 
 
Z
rj
 
 
Z
rk

жүктеу/скачать 1,22 Mb.

Достарыңызбен бөлісу: