Жасанды базис əдісі (М-есеп)

Әлжанова Н.Ш., Сәбитова Х.К. 
 
47
функция максимумын табу қажет 
 
f
̅̅ 
(х)= с
1
х
1 
+ с
2
 х
2 
+ … + с
n
х
n 
–M(x
n+1 
+х
n+2
 +…+ x
n+m
)    
(27) 
 
мұндағы М – жеткілікті дəрежеде үлкен оң сан. 
Бұл екі  есеп - (24)-(26) жəне (27)-(29) - əр түрлі болғанмен, 
олардың оңтайлы жоспарлары сəйкес келеді, себебі М-нің үлкен 
сан  болғаны  соншалық - x
n+1
,  х
n+2
, …, x
n+m
    ауыспалылары  М-
есептің оңтайлы жоспарында 0-ге тең болуы қажет. Осылайша,  
f(х)= с
1
х
1 
+ с
2
х
2 
+ … + с
n
х
n
 функциясы негізінен максималданады 
екен,  яғни  егер  М-есептің  шешімі  бар  болатын  болса,  ол  бастапқы 
есептің де шешімі болып табылады. Сондықтан М-есептің (27)-
(29)  шешімін  анықтауға  толығырақ  тоқталамыз.  Бұл  есепте  A 
j(
m
n
j
+
= ,
1
) векторлары арасында  m бірліктері бар. 
 
⎟⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
⎟⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
+
+
+
1
0
0
0
;
0
0
1
0
;
0
0
1
;
2
1
Μ
Μ
Μ
Λ
A
A
A
m
n
n
n
 
 
 
Оларды  бастапқы  базис  ретінде  қабылдауға  болады,  оның 
үстіне бұл векторлар жасанды деп аталады, ал осы векторлардан 
құрылған  базис  жасанды  базис  деп  аталады.  Бұл  базиске  тірек 
жоспарын сəйкес қоюға болады Х = (0,0, …, 0, x
n+1
,х
n+2
,…,x
n+m
),  
мұндағы x
n+1
, х
n+2
,…,x
n+m  
ауыспалылар да жасанды деп аталады. 
Есептеп шығарамыз: 
 
f(х)= с
1 
·0 +с
2 
· 0
 
+… + с
n
 · 0  
– M (x
n+1 
+х
n+2
 +…+ x
n+m
) = 
i
m
i
n
m
i
b
M
i
x
M
Σ
−
=
Σ
−
=
+
=
1
1
0
0
 
Жоспардың  оңтайлылығын  анықтау  үшін  есептеп  шығару 
қажет: 
∆
j 
= Z
j
 – с 
j
=
 
,
1
1
C
C
j
ij
m
i
j
j
i
n
m
i
a
M
i
С
−
Σ
−
=
−
Σ
=
+
=
Ζ
 
m
n
j
+
= ,
1
  

Экономикалық-математикалық әдістер 
 
48
Көріп отырғанымыздай, ∆
j
 
жəне f(х)  екі қосындыдан тұрады: 
бір қосынды М-ға тəуелді, ал екіншісі – тəуелді емес. М-есепке 
арналған симплексті кесте əдеттегіге ұқсас, тек оның екі жолға 
бөлінетін ∆ - жолы ғана өзгеше: ∆
′
  
жолында М-ға тəуелсіз шама 
жазылады, ал ∆
′′
 
жолында М кезіндегі коэффициенттер жазылады. 
Осылайша, есептің симплексті кестесі мынадай түрге ие болады 
(12-кесте). 
12-кесте 
 
С
0 
B
 
A
1
 
A
2
 
… A
n
 
A
n+1
  A
n+2
  … A
n+m
 
A
n+1
 -M  b
1
 
a
11
 
a
12
 
… a
1n
 
1 0 
… 0 
A
n+2
 -M  b
2
 
a
21
 
a
22
 
… a
2n
 
0 1 
… 0 
∶ 
∶ 
∶ 
∶ 
∶ 
∶ 
∶ 
∶ 
∶ 
… ∶ 
A
n+m
 -M  b
m
 
a
m1
 
a
m2
 
… a
mn
 
0 0 
… 1 
∆
′
 
 0 -c
1 
-c
2 
… -c
n 
0 0 
… 0 
∆
′′
 
 
-
b
i
m
i
Σ
=1
  -
а
i
m
i
1
1
Σ
=
а
i
m
i
2
1
Σ
−
=
 
…
а
m
i
Σ
−
=1
 
0 0 
… 0 
 
Бұл  кесте  симплексті  тəсілдің  алгоритмі  бойынша  өзгереді, 
бұл  жерде  критерий  ретінде  ∆
′′
-
жолдың  элементтері  қарастыры-
лады.  ∆
′′
-
жолдың  элементтерін  оңтайлылық  критерийі  ретінде 
жетекшілікке  ала  отырып,  кестенің  өзгеруі  төмендегілерге  қол 
жеткізілгенше жалғаса береді: 
1)  барлық жасанды векторлар базистен шығарылғанша; 
2)  жасанды  векторлардың  барлығы  бірдей  базистен  шы-
ғарылған 
жоқ, 
дегенмен 
барлық 
элементтер 
∆
′′
j
=0, 
m
n
j
+
= ,
1
, яғни оңтайлылық критерийі орындалады жəне 
жоспарды жақсарту процесін жалғастыруға болмайды. 
Бірінші  жағдайда  алғашқы (24)-(26) есептерінің  бастапқы 
тірек  жоспары  алынды.  Оның  оңтайлылығын  ∆
′
 - 
жолдың 
элементтері  анықтайды,  ал  егер  жоспар  оңтайлы  емес  болса, 
онда ∆
′′
-
жолын шегеріп тастап кестенің өзгеру процесі оңтайлы 
жоспарды алғанға дейін жалғаса береді. 
Екінші  жағдайда,  егер  ∆
′′
-
жолдың  элементі  В  бағанында 
нольге тең емес болса, онда бастапқы есептің бірде-бір жоспары 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
49
жоқ, ал егер В бағанындағы элемент 0-ге тең болса, онда есептің 
бастапқы тірек жоспары 
төмендетілген
 болады. 
Осылайша,  желілік  программалау  есебін  жасанды  базис 
тəсілімен шешу процесі төмендегі сатылардан тұрады: 
1)  М-есеп құрылады; 
2)  М-есептің бастапқы симплексті кестесі құрылады; 
3)  Симплексті  тəсілдің  алгоритмін  пайдалана  отырып,  бұл 
кесте барлық жасанды векторлары базистен шығарылғанша өзгере 
береді.  Нəтижесінде  немесе  алғашқы  есептің  бастапқы  тірек 
жоспары алынады, немесе есептің шешілмейтіндігі анықталады. 
4)  Табылған  бастапқы  тірек  жоспары  оңтайлылыққа 
тексеріледі  жəне  егер  ол  оңтайлы  болмаса,  онда  жоспарды 
жақсарту процесі оңтайлы жоспар алғанға дейін жалғаса береді, 
немесе есептің шешілмейтіндігі анықталады. 
Егер алғашқы есепте бірнеше бірлік векторлар бар болса, онда 
оларды бастапқы базиске енгізу қажет екендігін атап өткен жөн. 
Мысал. Төмендегі шектеулер жағдайында 
 
х
1 
+  х
2 
                = 10 
х
2   
+  х
3                      
 = 12 
х
1   
+  х
3                   
  = 14 
3
,
1
,
0
=
≥
j
j
x
 
 
функцияның максимумын табу қажет: 
f(х)= 5х
1 
+ 6х
2 
+7х
3 
Көріп  тұрғанымыздай, 
)
3
,
1
(
=
j
А
j
векторлары  арасында 
бірліктері  жоқ,  ал  есеп  канондық  түрде  берілген.  Демек,  оны 
жасанды базис тəсілімен шешу қажет. Ол үшін М-есеп құрамыз. 
 
f(х)= 5х
1 
+ 6х
2 
+7х
3
 –M(х
4 
+ х
5 
+х
6
) 
→
 max 
 
  х
1 
+  х
2      
+  х
4 
          =10 
  х
2   
+  х
3  
 + х
5                  
= 12  
  х
1   
+ х
3     
+
 х
6                 
= 14 
        
6
,
1
,
0
=
≥
j
j
x
 
 
М
-есепті  симплексті  тəсілмен  шешеміз.  Көріп  тұрғанымыздай, 
М
-есепте бірлік векторлар бар: 

Экономикалық-математикалық әдістер 
 
50
 
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
1
0
0
;
0
1
0
;
0
0
1
6
5
4
A
A
A
 , 
 
олар,  жоғарыда  көрсетілгендей,  жасанды  базис  құрады.  Бұл 
базиске тірек жоспары сəйкес келеді 
 
х
 = (0, 0 ,0, х
4 
, х
5
, х
6
) = (0 ,0 ,0 ,10 ,12, 14) 
 
мұндағы  х
4
,  х
5
,  х
6 
  ауыспалылары  да  жасанды  деп  аталады.  М-
есептің бастапқы кестесін құрайық (13-кесте) 
13-кесте 
 
С
0 
B
 
A
1
 
A
2
 
А
3 
A
4
 
A
5
 
A
6
 
θ 
A
4
 
-М 10  1 1 0 1  0  0  - 
A
5
 
-М 12  0 1 1 0  1  0  12 
А
6 
-М 14  1 0 1 0  0  1  14 
∆
′
 
  0  -5 -6 -7  0  0  0 
 
∆
′′
 
  -36  -2 -2 -2  0  0  0 
 
 
∆
′
  
жəне ∆
′′
 
жолдарының элементтері қалай анықталатынын 
көрсетейік. В бағанында, бізге белгілі, жоспардың нольдік емес 
компоненттері  жазылады,  ал  соңғы  екі  жолда – осы  жоспарға 
сəйкес  келетін  функция  мəні,  сонымен  қатар  бұл  мəн  С
0
 
векторының В векторына скалярлық туындысына тең: 
 
(С
0
,В) = - 10М –12М – 14М = - 36М = 0 – 36М 
 
∆
′
  
жолында М-ға тəуелсіз шаманы жазамыз, яғни - 0, ал ∆
′′
 
жолына М кезіндегі коэффициентті жазамыз, яғни – 36. 
Кестенің келесі бағандарына 
)
6
,
1
(
=
j
А
j
 A
j
  векторларының 
(Z
ij
) базисі бойынша ыдырау коэффициенттері жазылады. Соны-
мен бірге Z
ij
 = а
ij
  
базисті бірлік векторлар құрған жағдайда, ал 
∆
j 
= Z
ij
 - С
j  
,  мұндағы  Z
j
    С
0
 
жəне  А
j  
векторларының  скалярлы 
туындысы ретінде анықталады. Мысалы, 
 
∆
1 
= Z
1
 - С
1  
=(С
0 
А
1
)- С
1  
= (-М) 
⋅
 1 + (-М) 
⋅
 0+ (-М) 
⋅
 1- 5 = - 2М – 5 
 
Сондықтан  А
1 
бағанының 
Δ′  жолына  М-ға  тəуелсіз  шаманы 
жазамыз,  яғни – 5, ал 
Δ′′  жолына -  М  кезіндегі  коэффициент, 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
51
яғни – 2. Осыған ұқсас ∆
2 
= Z
2
 - С
2  
=(С
0 
А
2
) - С
2  
= (-М) 
⋅
 1 + (-М) 
⋅
 1 + (-М) 
⋅
 0 – 6 =  - 2М – 6. 
Кестенің  А
2
  бағанындағы 
Δ′  жолына – 6, ал  Δ′′  жолына – 2 
жазамыз жəне т.б. Осылайша, бастапқы кесте алында. 
Алынған  кестеден  көрініп  тұрғандай,  М-есептің  бастапқы 
жоспары  оңтайлы  емес,  себебі 
Δ′′
j
 
арасында  терістері  бар. 
Симплексті  тəсілдің  алгоритміне  сəйкес  жаңа  тірек  жоспарына 
көшеміз. Əуелі базиске енгізілуі қажетті векторды анықтаймыз, 
ол үшін 
Δ ′′
j
j
min
= 
Δ′′
1
 = 
Δ′′
2
 =
Δ′′
3
 = -2
 табамыз. 
Бұл жалпы жағдайда базиске А
1
, А
2
,
 жəне А
3 
 
векторларының 
кез келгенін енгізуге болатындығын білдіреді, бірақ 
Δ′ жолының 
сəйкес элементтеріне назар аударсақ, 
Δ′
j
j
min
= min (-5,-6,-7) = -7 = 
Δ′
3
 < 0 
онда  базиске  ∆
′
   
жəне  ∆
′′
 
жолдарындағы  минималды  мəнге 
сəйкес  келетін  А
3
  векторын  енгізу  дұрыс  екендігін  байқауға 
болады.  
12
1
14
;
1
12
min
3
0
3
,
min
=
⎟
⎠
⎞
⎜
⎝
⎛
=
>
Ζ
=
Ζ
i
i
i
i
x
θ
 
 
есептеп  шығарып,  минималды  қатынас  сəйкес  келетін  А
5
 
векторын базистен шығарып тастау керектігін анықтаймыз. Бұл 
вектор  жасанды  болғандықтан  жəне  бұдан  былай  бізге  қажет 
болмайтындықтан,  есептеулерді  қысқарту  мақсатында  бұл 
векторды  келесі  кестеге  енгібеуге  де  болады. 13-кестені  Гаусс 
формуласы бойынша өзгерте отырып, 14-кестені аламыз. 
 
14-кесте 
 
С
0 
B
 
A
1
 
A
2
 
А
3 
A
4
 
A
6
 
A
4
 
-М 
10 1 1 0 1  0 
A
3
 
7 12 0 1 1 0  0 
А
6 
-М 2  1 -1 0 0  1 
∆
′
 
 84 -5 1 0 0  0 
∆
′′
 
 -12 -2 0  0 0  0 
 

Экономикалық-математикалық әдістер 
 
52
Сонымен, жаңа жоспар алынды х = (0, 0, 12, 10, 02), бірақ ол 
да оңтайлы емес, себебі 
Δ′′
1
 = -2< 0.
 Базиске А
1
 векторын енгізіп 
жəне  базистен  жасанды  А
6
  векторын  шығарып,  келесі  тірек 
жоспарына өтеміз . Жаңа кесте төмендегі түрге ие (15-кесте). 
 
15-кесте 
 
С
0 
B
 
A
1
 
A
2
 
А
3 
A
4
 
A
4
 
-М 8 0 2 0 1 
A
3
 
7 12 0 1 1 0 
А
1 
5  2  1 -1 0 0 
∆
′
 
  94 0 -5 0 0 
∆
′′
 
  -8 0 -2 0 0 
 
Көріп  тұрғанымыздай, 
Δ′′
2
 = -2< 0. 
Жоспарды  жақсарту 
процесі  жалғаса  береді.  А
2
  векторын  базиске  енгіземіз,  ал  А
4
 
векторын – шығарамыз. Келесі кестені аламыз (16-кесте). 
 
16-кесте 
 
С
0 
B
 
A
1
 
A
2
 
А
3 
A
2
 
6 4 0 1 0 
A
3
 
7 8 0 0 1 
А
1 
5 6 1 0 0 
∆
′
 
 110 0 0 0 
∆
′′
 
  0 0 0 0 
 
Соңғы  кестеде (16-кесте)  барлық  жасанды  векторлар 
базистен  шығарылған,  демек,  алғашқы  есептің  бастапқы  тірек 
жоспары  алынды.  Оның  оңтайлылығы  ∆
′
 
-жолдың  элементтерімен 
анықталады.  Кестеден  көріп  тұрғанымыздай, 
3
,
1
,
0
'
=
=
Δ
j
j
, 
демек,  оңтайлы  жоспар  алынды  х = (6, 4, 8),  ал  функцияның 
максималды мəні 110-ға тең. 
 
1. 8. Екі жақты желілік программалау тапсырмалары 
 
Желілік  программалаудың  əрбір  тапсырмасымен  мұнымен 
байланысты  басқа  бір  тапсырманы  белгілі  бір  ретпен 
салғастыруға  болады,  бұл  тапсырма  алғашқысына  қатысты 
алғанда екі жақты деп аталады. 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
53
Екі жақты тапсырмалардың осындай жұбын бірге қарастыру 
сызықтық  бағдарламалау,  түрлі  есептеу  алгоритмдерін  құру 
мəселелерін  теориялық  тұрғыдан  зерттеудің  тиімді  құралы 
болып табылады, сонымен қатар есептеулер нəтижелерін талдау 
барысында үлкен рөл атқарады.  
  
1.8.1.
 Симметриялық екі жақты тапсырмалар, олардың 
экономикалық интерпретациясы 
Сызықтық  бағдарламалаудың  негізгі  тапсырмасы  мынадай 
түрде беріледі. 
Қандай  да  бір  мекемеде  m  түрлі  ресурстардың  b
1 
,b
2
 ,…,b
m 
көлемі бар, олардан өнімнің п түрі өндіріледі. 
Мына мəндер белгілі:  
С
j  
-
 өнімнің  j-інші түрінің 1 бірлігінің құны (
n
j
,
1
=
),  
а
ij 
–  j-інші  өнімнің 1 бірлігін  өндіруге  кеткен    i-інші  ресурс 
шығынының көлемі. 
Өнімді өндірудің өнім құнын арттыратын жоспарын анықтау 
керек. 
Тапсырманың  математикалық  моделін  құрайық.  J-інші  өнімді 
өндіру көлемін x
j 
арқылы белгілейміз, онда тапсырманың мақсатты 
түрдегі функциясы мен шектеулері былайша жазылады: 
)
32
(
,
1
,
0
)
31
(
,
1
1
n
j
j
m
i
i
j
ij
n
j
x
b
x
a
=
≥
=
≤
Σ
=
   болған жағдайда 
        
)
30
(
1
)
(
x
C
j
j
n
j
x
f
Σ
=
=
               арттыру. 
Дəл осы алғашқы мəліметтер бойынша келесі экономикалық 
тапсырманы құруға болады. 
Мекеме  қолда  бар  ресурстардан  өнім  өндірмей,  бұл 
ресурстарды  сату  жөнінде  шешім  қабылдады  делік.  Осының 
барысында  ресурстардың  мынадай  келесі  жағдайларды 
қамтамасыз  ететіндей  бағаларын  анықтау  міндеті  туындайды: 
бір  жағынан,  сатып  алатын  ұйым  барлық  ресурстардың  жалпы 

Экономикалық-математикалық әдістер 
 
54
құнын  азайтуға  тырысады;  екінші  жағынан,  өндіруші  мекеме 
ресурстың  əр  түрі  үшін  шикізатты  дайын  өнім  етіп    өндіретін 
жағдайда  қолында  болатын  сомадан  аз  болмайтындай  каржы 
алуы  тиіс,  əйтпесе  оған  ресурстарды  сату  емес,  өзінің  жеке 
өндірісін ұйымдастыру тиімді. 
Тапсырманың математикалық моделін құрайық. Айнымалы-
ларды енгіземіз:   У
i
  - ресурстың  i-інші түрінің құны (i=  
m
,
1
). 
Сонда і-інші ресурстың бүкіл көлемінің құны  у
i
b
i
-ге тең болады, 
ал барлық ресурстар бағасы: 
 
у
1
b
1
 + у
2
b
2
 + ... + у
m
b
m 
 
j
-інші  өнімнің 1 бірлігін  өндіруге  кеткен    i-інші  шикізат 
шығынының  көлемі  a
ij
-ге  тең  болады,  оның  бағасы    у
i
a
ij
-ді 
құрайды,  ал  j-інші  өнімнің 1 бірлігін  өндіруге  кеткен  барлық 
ресурстар құны мына сомаға тең болады:   
 
у
1
a
1j
 + у
2
a
2j
 + ... + у
m
a
m 
, 
 
бұл  сома  j-інші  өнімнің 1 бірлігінің  C
j 
құнынан  кем  болмауы 
тиіс,  яғни  өнімнің  əр  түрі  бойынша  мынадай  шектеулер  енгізу 
қажет: 
у
1
a
ij
 + у
2
a
2j
 + ... + у
m
a
mj
≥
 C
j
,
 
n
j
,
1
=
 
 
Осылайша,  бұл  тапсырманың  математикалық  моделі  былайша 
жазылады: 
 
y
1
a
11 
+ y
2
a
21  
+…+  y
m
a
m1  
≥
 
 C
1 
y
1
a
12 
+ y
2
a
22  
+…+  y
m
a
m2   
≥
 
 C
2   
               
(33) 
………………………... ... ... ... 
y
1
a
1n 
+ y
2
a
2n  
+… + y
m
a
mn  
≥
 
 C
n
  
 
      y
j
  ≥0,  
m
i
,
1
=
             
(34)   болған жағдайда 
 
g(y)=y
1
b
1
 + у
2
b
2
 + ... + у
m
b
m 
     
 (35)  азайту талап етіледі. 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
55
Егер (30)-(32) жəне (33)-(35) тапсырмаларын  салыстырсақ, 
онда мыналарды көреміз: 
1.  Бір  тапсырманың  мақсатының  функциясы  артады,  ал  екі 
жақты тапсырманікі азаяды. 
2.  Бір  тапсырмадағы  шектеулер  саны  келесі  тапсырмадағы 
айнымалылар санына тең. 
3.  Шектеулер  жүйесі  коэффициенттерінің  матрицасы  бірін 
екіншісінен тасымалдау арқылы алынады. 
Шындығында, (30)-(32) тапсырмасының  шектеулер  жүйесі 
коэффициенттерінің матрицасын  А арқылы белгілесек,  
 
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
=
a
a
a
a
a
a
a
a
a
mn
m
m
n
n
A
Κ
Κ
Κ
Κ
Κ
Κ
Κ
2
1
2
22
21
1
12
11
 
 
онда (33)-(35) тапсырмасының  шектеулер  жүйесі  коэффи-
циенттерінің матрицасы А
′ 
болады: 
 
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
=
′
a
a
a
a
a
a
a
a
a
mn
n
n
m
m
A
Κ
Κ
Κ
Κ
Κ
Κ
Κ
2
1
2
22
12
1
21
11
 
 
4. Екі тапсырма айнымалыларының да дұрыс мəндері сақталады. 
5.  Бір  тапсырманың  шектеулер  жүйесінің  бос  мүшелері - 
келесі тапсырманың мақсат функциясының коэффициенттері, ал 
біріншісінің  мақсат  коэффициенттері  келесі  тапсырманың 
шектеулер жүйесінің бос мүшелері болып шығады. 
6. Бір тапсырмадағы теңсіздік түрі - « 
≤ », ал екіншісінікі - « ≥ ». 
Сызықтық  бағдарламалаудың  аталмыш  сипаттарға  ие 
тапсырмалары симметриялық өзара екі жақты тапсырмалар деп 
аталады. Осының барысында олардың біреуі – тікелей (алғашқы), 
келесісі екі жақты (кездесетін) деп аталады. 

Экономикалық-математикалық әдістер 
 
56
Таза математикалық көзқарас тұрғысынан тікелей түріне екі 
жақты жұп тапсырмаларының кез келгені жатқызылады. 
Экономикалық  қырынан  алып  қарағанда,  тікелей  тапсырманы 
шешу өнімді шығарудың тиімді жоспарын береді, ал екі жақты 
тапсырманы  шешу  қолданылып  жүрген  ресурстардың  шартты 
бағаларының  оңтайлы  жүйесін  алуға  мүмкіндік  береді.  Академик 
Л.В.Конторович оларды «объективті түрде негізделген бағалар» 
деп атаған. 
 

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

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