Транспорттық тапсырманың тірек жоспарының

Әлжанова Н.Ш., Сәбитова Х.К. 
 
77
Алдын  ала  қарастырылған  кезеңде  бізге  белгілі  əдістердің 
(солтүстік-батыс  бұрыш  əдісі,  минималды  элемент  əдісі  жəне 
т.б.) бірі арқылы бастапқы тірек жоспар анықталады. 
Өз кезегінде, əрбір итерация 2 кезеңге бөлінеді. 
Бірінші  сатыда  алынған  тірек  жоспардың  оңтайлылығы 
тексеріледі.  Егер  жоспар  оңтайлы  болса,  онда  шешу  процесі 
аяқталады,  егер  оңтайлы  болмаса,  онда  екінші  кезеңге  өту  іске 
асады.  Екінші  кезеңде  едəуір  оңтайлы  жаңа  тірек  жоспары 
құрылады. 
Алдын  ал  қарастырылған  кезеңде  қандай  да  бір 
mxn
X
X
ij
=
 
тірек жоспары анықталды деп есептейік.
 
1-кезең. Жоспардың оңтайлылығын тексеру. 
Жоспардың  оңтайлылығын  тексеру  үшін  бұл  жоспардың 
бағалаушы матрицасын табу қажет: 
mxn
U
C
mxn
C
C
V
j
i
ij
ij
−
+
=
=
1
1
. 
Бағалаушы матрицаны құру үшін 
)
,
1
,
,
1
(
n
j
m
i
и
U
V
j
i
=
=
 
потенциалдарын анықтау қажет. Олар  
 
 
(*)
.
0
,
0
>
=
−
+
X
бол оол
V
U
C
ij
j
i
ij
 
мәні ‰шін бар болып табылады.
 
Бұдан  былай  бұл  элементтерді 
)
0
(
>
X
ij
  базистік  деп 
атаймыз.  Бізге  белгілі  болғандай,  егер 
mxn
X
X
ij
=
 
тудырмаған 
тірек жоспары болса, онда ол нақты (m+n-1)
 
 нөлдік 
емес  базистік  элементтерді  қамтиды.  Олардың  əрқайсысы  үшін 
(*)  қатынасын  құрамыз.  Теңдіктердің  (m+n)  белгісіздері  бар  
(m+n-1) 
жүйесін, 
яғни 
белгісіздік 
жүйесін 
аламыз: 
)
,
1
(
)
,
1
(
n
j
и
m
i
U
V
j
j
=
=
.  Айнымалылардың  біріне 
туынды  мəн  бере  отырып,  бұл  жүйенің  кейбір  жеке  шешімін 
табамыз. 
Мысалы, 
,
0
1
=
U
 
мәнін
  қойып  (m+n-1)
 
белгісіздері  бар 
(m+n-1)  теңдеулер  жүйесін  аламыз,  мұны  шешу  арқылы  басқа 
белгісіздердің  мəнін  табамыз.  Потенциалдарды  осылайша 
анықтап  алып,  жоспардың  бағалаушы  матрицасын  құрамыз. 
болғанда 
және

Экономикалық-математикалық әдістер 
 
78
Егер  бағалаушы  матрицаның  барлық  элементтері  теріс  емес 
болса,  онда  Х  жоспары  оңтайлы  (оптималды)  жəне  процесс 
аяқталған, ал егер бағалаушы матрица элементтерінің арасында 
терістері бар болса, онда жоспар оңтайлы (оптималды) емес жəне 
2-сатыға өту керек. 
2-саты. Жаңа тірек жоспарын құру. 
Бағалаушы  матрицаның  теріс  элементтерінің  арасында 
минималды  элемент  бар.  Бұл 
C
rk
1
, 
элементі  болсын,  яғни 
0
1
1
min
<
= C rk
C ij
 
Матрица-жоспарда 
X rk
  сəйкес  элементі  үшін  шығыршық 
құрылады. 
Шығыршық – бұл  тұйық  үзік  желі,  мұның  өзектері  жолдар 
мен  бағандардан  алшақ  орналасқан,  ал  жоғарғы  жағында 
берілген 
X rk
= элементі жəне жоспардың нөлдік емес (базистік) 
элементі орналасқан. 
 Егер жоспар туындамайтын тірек жоспар болса, онда оның 
əрбір  базистік  емес  (нөлдік)  элементі  үшін  шығыршық  құруға 
болады жəне бұл шығыршық біреу ғана болмақ.  
Шығыршықтар түрлі конфигурацияға ие. Мысалы, мынадай 
түрлері болады: 
 
 
 
 
 
 
 
12-сурет 
 
Шығыршықтың  жоғарғы  жағын 
X rk
  элементінен  бастап 
кезекпен «+» жəне «-» белгілерімен белгілейміз. Шығыршықтың 
жоғарғы  жағында  орналасқан  жəне «-» белгісімен  белгіленген 
жоспар  элементтерінің  ішінде  ең  минималды  элементті  табу 
керек, яғни   
{ }
"
"
0
0
min
−
=
=
X
j
i
X i
цепи
j
θ
     
 
+
X
rk
 
+ 
- 
- 
+
+
X
rk
 
+
X
rk
 
- 
- 
+
+
+ 
- 
- 
- 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
79
θ  санын  шығыршықтың «+» белгісімен  белгіленген 
элементтеріне  қоса  отырып  жəне  «-» белгісімен  белгіленген 
элементтерінен  ала  отырып,  шығыршық  бойымен  оның  орнын 
ауыстырамыз.  Шығыршыққа  енбейтін  жоспардың  қалған 
элементтері  өзгеріссіз  қалады.  Нəтижесінде  жаңа  жоспар  пайда 
болады,  мұнда 
X
j
i 0
0
  элементі    -  базистік  емес,  ал 
X rk
=  θ 
(бұрынғы  базистік  емес)  элементі  базистік  сипат  алады. 
Осылайша,  жаңа  жоспарда  базистік  элементтердің  саны 
өзгермейді.  Содан  кейін 1-кезеңге  өтеміз,  мұнда  пайда  болған 
жаңа  жоспардың  оңтайлылығы  тексеріледі.  Бұл  үшін  оны 
бағалау  матрицасын  құру  керек.  Мұны,  бұрын  көрсетілгендей, 
тірек  жоспардың 
)
,
1
(
)
,
1
(
n
j
V j
и
m
i
U i
=
=
  потенциалдарын 
анықтау арқылы жүзеге асыруға болады. Алайда жаңа жоспарды 
бағалау  матрицасын  алдыңғы  жоспарды  бағалау  матрицасын 
дəлме-дəл  қайта  жасай  отырып  құруға  болады.  Шынымен-ақ, 
жаңа жоспардың алдыңғы жоспардан еркшелігі мынада екекніне 
назар  аударайық:  мұнда  алдыңғы  жоспарда  базистік  болған  бір 
ауыспалы    (
X
j
i 0
0
) – базистік  емес,  ал  базистік  емес  ауыспалы 
(
X rk
),  керісінше,  базистік  сипат  алады,  ал  екі  жоспардың  да 
қалған  базистік  ауыспалылары  абсолюттік  көлемі  бойынша 
ерекшеленсе  де,  өзара  сəйкес  келеді.  Бірақ  жаңа  жəне  алдыңғы 
жоспарларды  бағалау  матрицалары  үшін  бұл  базистік 
ауыспалыларға  нөлдер  сəйкес  келеді.  Сондықтан  алдыңғы 
жоспарды  бағалау  матрицасының  жасалу  алгоритмінің  мəні 
мынада: мұнда  
Crk
1
 элементі  0-ге айналып, барлық базистік 0-
дер  сақталуы  керек,  тек  сақталмайтыны – жаңа  жоспарда 
базистік  емес    (
C j
i
1
0
0
)  элементіне  айналған  элементке  сəйкес 
келетін  базистік 0. Бұл  былайша  іске  асады.  Бағалау 
матрицасының r жолының (немесе k бағанының) элементтеріне 
C
rk
1
  қосылады,  яғни 
Crk
1
 =0 болады.  Егер  осының  барысында 
осы  жолда  (немесе  бағанда)  тұрған  базистік 0-дер  бұзылатын 
болса, онда олар бұзылған базистік 0 қайда болса, сол бағанның 
(немесе жолдың) барлық элементтерінен 
Crk
1
 санын алу арқылы 

Экономикалық-математикалық әдістер 
 
80
қалпына келтіріледі. Егер базистік нөлдер тағы да бұзылса, онда 
ұқсас жолмен олар қалпына келтірілуі керек, бұл үрдіс бағалау 
матрицасы  толығымен  қайта  жасалғанша  жалғасады.  Осының 
барысында  жаңа  жоспардағы  базистік  емес  элементке  сəйкес 
келетін  алдыңғы  жоспардағы  базистік 0-ді  қалпына  келтіру 
қажет емес екенін ескерте кету керек. 
 Жаңа  жоспардың  бағалау  матрицасын  осылайша  құра 
отырып,  оның  тиімділігін  тексереміз.  Ал  егер  жоспар  тиімді 
болмаса, онда 2-кезеңге өтеміз, яғни желілік форманың төменгі 
мəні сəйкес келетін жаңа тірек жоспарын құрамыз.  
Мысал. Тапсырманың тиімді жоспарын табу керек:      
                      а
1
 = 15            в
1
 = 11               
 
 
  а
2
 = 16            в
2
 = 12 
                      а
1
 = 17            в
3
 = 12 
                                              в
4
 = 13  
 
 
   
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
6
4
7
3
6
5
4
7
3
6
4
8
C
 
 
Тапсырманың  шешімділігі  алдын  ала  анықталған.  Барлық 
алғашқы берілген мəліметтерді бөлуші кестеге орналастырайық. 
  
22-кесте 
       b
j
 
a
i 
11
 
 
12
 
 
12 13
 
 
U 
15 8 
 
 
 
11 
            4   
 
4                  
 
           6 
 
3    
 
U
1
=0 
16 
            7 
 
            4   
 8 
           5 
8 
 
     6 
 
U
2
=0 
 
 
17 
           3 
 
            7 
 
4   
4 
 
            6 
13 
U
3
=1 
 
 
V 
 
V
1
=8 V
2
=4 V
3
=5 V
4
=7  
 
 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
81
Бөлуші  кестені  тағы  бір  бағанмен  жəне  жолмен 
толықтырайық.  
Кестеге  солтүстік-батыс  бұрыш  əдісі  арқылы  алынған 
жоспарды орналастырамыз. 
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
13
4
0
0
0
8
8
0
0
0
4
11
X
 
1-кезең. Жоспардың оңтайлылығын тексеру. 
Х  жоспарының  оңтайлылығын  тексеру  үшін  оны  бағалау 
матрицасын құру қажет:  
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎝
⎛
=
C
C
C
C
C
C
C
C
C
C
C
C
C
1
1
1
1
1
1
1
1
1
1
1
1
34
33
32
31
24
23
22
21
14
13
12
11
1
 
Мұндағы 
V
U
C
C
j
i
ij
ij
−
+
=
1
,  ал  U
i
    и  V
j
  потенциалдары   
0
>
x
ij
    (жоспардың  нөлдік  емес,  базистік  элементтері)  үшін 
шарт (*) 
0
=
−
+
V
U
C
j
i
ij
 болған жағдайда анықталады.  
U
i
    жəне 
V
j
  потенциалдарын  анықтаймыз.  Нөлдік  емес 
)
1
,
1
(
0
11
11
=
=
>
=
j
i
x
  элементі  үшін  шарт (*) былайша 
жазылады:  
0
1
1
11
=
−
+
V
U
C
, ал 
8
11
=
C
. Мынадай теңдік шығады:  
0
8
1
1
=
−
+
V
U
 
Нөлдік  емес 
)
2
,
1
(
12
=
= j
i
x
  элементі  үшін  шарт (*) былайша 
жазылады:  
 
0
2
1
12
=
−
+
V
U
C
, яғни 
4
12
=
C
 мəнін осы қатынасқа қойғанда, 
0
4
2
1
=
−
+
V
U
 теңдігі шығады. 
Əрі қарай осыған ұқсас теңдіктер шығарамыз:  
0
6
0
,
0
13
0
4
0
,
0
4
0
5
0
,
0
8
0
4
0
,
0
8
4
3
4
3
34
34
3
3
3
3
33
33
3
2
3
2
23
23
2
2
2
2
22
22
=
−
+
=
−
+
>
=
=
−
+
=
−
+
>
=
=
−
+
=
−
+
>
=
=
−
+
=
−
+
>
=
V
U
V
U
C
X
V
U
V
U
C
X
V
U
V
U
C
X
V
U
или
V
U
C
X
 
Осылайша, мынадай жүйе пайда болады: 
 

Экономикалық-математикалық әдістер 
 
82
⎪
⎪
⎪
⎪
⎩
⎪⎪
⎪
⎪
⎨
⎧
=
−
+
=
−
+
=
−
+
=
−
+
=
−
+
=
−
+
0
6
0
4
0
5
0
4
0
4
0
8
4
3
3
3
3
2
2
2
2
1
1
1
V
U
V
U
V
U
V
U
V
U
V
U
 
 
Бұл – 7 белгісізі  бар 6 теңдіктен  тұратын  анықталмаған 
жүйе.  Осы  жүйенің  жеке  шешімін  табалық. 
,
0
1
=
U
  делік,  онда 
бірінші теңдіктен -  
8
0
0
8
:
1
1
1
=
⇒
=
−
+
V
V
V
, ал екінші теңдіктен 
4
0
0
4
:
2
2
2
=
⇒
=
−
+
V
V
V
 теңдіктерін анықтаймыз. V
2  
мəнін біле 
отырып, үшінші теңдіктен       
0
0
4
4
:
2
2
2
=
⇒
=
−
+
U
U
U
 теңдігін 
есептеп 
шығарамыз. 
Əрі 
қарай 
төртінші 
теңдіктен 
5
,
0
0
5
:
3
3
3
=
=
−
+
V
V
V
  теңдігін  анықтай  аламыз. V
3 
мəнін  біле 
отырып,  бесінші  теңдіктен 
1
,
0
5
4
:
3
3
3
=
=
−
+
U
U
U
  теңдігін 
табамыз  жəне  ақырында  соңғы  теңдіктен    U
3 
=1  мəнін  қоя 
отырып,  
.
7
,
0
1
6
:
4
4
4
=
=
−
+
V
V
V
 теңдігін анықтаймыз. 
Көріп отырғанымыздай, потенциалдарды есептеп шығару - 
əжептəуір күрделі үдеріс. Оны былайша елеулі түрде оңайлатуға 
болады. Теңдікті мынадай түрде жазамыз: 
0
>
x
ij
 (базистік) үшін 
⎪⎭
⎪
⎬
⎫
+
=
−
=
⇒
=
−
+
Cij
U i
V j
Cij
V j
U i
V j
U i
Cij
0
(*)
 
    Енді  бөлуші  кестеге U қосымша  бағаны  мен V қосымша 
тармағын  енгіземіз. (**) формуласын  қолданып, U
1
=0  мəнін 
қоямыз.  Бөлуші  кестенің  бірінші  тармағынан  нөлдік  емес 
мəндерді  табамыз  жəне V-ның  сəйкес  мəндерін  анықтаймыз. 
Осылайша, бірінші тармақ пен бірінші бағанда 
0
11
11
≠
=
x
, ізінше, 
8
8
0
11
1
1
=
+
=
+
=
C
U
V
  теңдігін  анықтаймыз.  Сонымен  қатар 
бірінші  жол  мен  екінші  бағанда 
0
12
≠
x
,  сондықтан 
.
4
4
0
12
1
2
=
+
=
+
=
C
U
V
мəнін есептеп шығаруға болады. Енді бұл 
жолда нөлдік емес мəндер жоқ. Енді бөлуші кестенің V мəндері 
анықталған  бағандарын  қарастырамыз.  Бұлар – бірінші  жəне 
екінші бағандар. Бірінші бағанда нөлдік емес мəндер жоқ  (х
11 
–

Әлжанова Н.Ш., Сәбитова Х.К. 
 
83
ден  басқа),  ал  екіншісінде – х
22
 = 8 ≠ 0. Осы  нөлдік  емес  мəн 
арқылы 
.
0
4
4
22
2
2
=
−
=
−
=
C
V
U
теңдігін анықтауға болады (қар.(**)). 
U
2 
мəнін  біле  отырып,  х
23
 = 8 ≠ 0 нөлдік  емес  мəн  арқылы   
5
5
0
23
2
3
=
+
=
−
=
C
U
V
  теңдігін  табамыз,  ал  х
33
 = 4 ≠ 0 мəні 
арқылы 
1
4
5
33
3
3
=
−
=
−
=
C
V
U
 теңдігін аламыз, соңында х
34
 =13 
≠ 0 мəні  арқылы, U
3 
мəнін  біле  отырып, 
7
6
1
34
3
4
=
+
=
−
=
C
U
V
 
теңдігін  анықтаймыз.  Осылайша,  теңдіктер  құрмай-ақ (*), 
бөлуші  кесте  негізінде,  (**) формулаларды  қолдана  отырып, 
потенциалдарды  анықтауға  болады. 1-кестеде  аталған  тəсілмен 
бөлуші  кестедегі  потенциалдарды  есептеп  шығару  барысы 
бағыттауыштармен  көрсетілген.  Біздіңше,  потенциалдарды 
есептеп шығарудың бұл тəсілі анағұрлым ыңғайлы. 
Енді  бағалау  матрицасын  құруға  көшуімізге  болады.  
mxn
C
C
ij
1
1
=
 
бағалау 
матрицасының 
элементтері 
V
U
C
C
j
ij
ij
−
+
=
1
1
 формуласы бойынша анықталатыны белгілі. 
Көріп  отырғанымыздай,  бөлуші  кестеде  потенциалдар 
бағаны  мен  тармағы  болғанда (1-кестені  қар.),  бағалау 
матрицасының  элементтерін  есептеп  шығару  жеткілікті  түрде 
қарапайым  болып  келеді,  ал  нақты  C
ij
  бағалау  матрицасының 
элементін  анықтау  үшін 
C
ij
  шығындар  матрицасының  сəйкес 
элементіне  қиылыстарында  алғашқы  элемент  орналасқан i-інші 
тармақтағы  U
i  
потенциалын  қосып, j-інші  бағандағы  V
j   
потенциалын  алып  тастау  керек.  Осылайша, 
11
1
C
-ді  анықтау 
үшін 
C
11
элементіне  бірінші  тармақта  орналасқан    U
1
-ді  қосып, 
бірінші  бағанда  орналасқан  V
1
-ді  алып  тастау  керек,  яғни: 
0
8
0
8
1
1
11
11
1
=
−
+
=
−
+
=
V
U
C
C
. 
Мысалы, 
24
1
C
  мəнін  анықтау  үшін 
6
24
=
C
  элементіне    U
2 
(екінші  тармақта)  қосып, V
4 
(төртінші  бағанда)  алып  тастау 
қажет, өйткені бұл элемент бөлуші кестенің екінші тармағы мен 
төртінші 
бағанының 
қиылысында 
орналасқан, 
яғни 
1
7
0
6
4
2
24
24
1
−
=
−
+
=
−
+
=
V
U
C
C
. 

Экономикалық-математикалық әдістер 
 
84
Итеративті  түрде  есептеп  шығару  барысын  келесі  түрде 
орналастырған ыңғайлы. Есеп шығару барысын сипаттайық. 
 
23-кесте 
 Интер-
вал № 
Тірек жоспар 
Бағалау матрицасы 
0 
 
0 
 
 
 
 
 
 
 
4
0
4
1
0
0
1
4
1
0
0
+
⊗
−
−
−
 
 
 
θ = min (11,8,4)=4 
                        
1 
 
 
 
 
8
0
4
8
0
5
0
0
1
1
0
−
−
−
⊗
 
 
 
θ = 7 
  +8                +8              
2 
 
 
 
 
4
0
0
3
0
0
7
0
1
0
8
+
⊗
 
 
θ = 6 
-4 
 
⋅
⋅
⋅
⋅
⋅
⋅
6
11
6
10
13
2
 
0
0
4
0
3
0
0
3
0
1
0
4
 
 
 
  
- 
8
 
  + 
8 
- 
 
11 
. 
+ 
 
 
.
 
- 
 4 

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

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