Транспорттық тапсырма моделінің ерекшеліктері

Әлжанова Н.Ш., Сәбитова Х.К. 
 
67
есептеу тəсілдерін даярлауға мүмкіндік берді жəне бұл ерекше-
ліктердің  мəні (2)-(3) шектеу  жүйесінің  салыстырмалы  түрдегі 
қарапайымдығында: 
 
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎭
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎬
⎫
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎧
4
4
4
3
4
4
4
2
1
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
4
4
4
3
4
4
4
2
1
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
4
4
4
3
4
4
4
2
1
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
Κ
n
n
n
x
x
x
x
x
x
x
x
x
mn
m
m
n
n
1
0
0
0
1
0
0
0
1
1
1
1
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
1
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
1
2
1
2
23
21
1
12
11
 
 
А  матрицасының  барлық  элементтері 1 жəне 0-ден  тұрады 
жəне мұндағы əрбір бағанда тек екі бірлік (1) қана болады. 
Шектеу жүйесін векторлық түрде жазалық: 
P
11
X
11
 + P
12
X
12
 +…+ P
1n
X
1n
 +P
21
X
21
 + P
22
X
22
 +…P
2n
X
2n
 +…+ 
P
m1
X
m1
 + P
m2
X
m2 
+…+ P
mn
X
mn
 =P
0
, мұндағы 
P
11
=
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
0
0
1
0
0
1
Κ
Κ
  ;  
P
12
=
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
0
1
0
0
0
1
Κ
Κ
   , … 
P
n
1
=
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
1
0
0
0
0
1
Κ
Κ
  ;  … 
P
mn
=
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
1
0
0
1
0
0
Κ
Κ
  ;    
P
0
=
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
a
b
b
a
a
a
n
m
Κ
Κ
2
1
2
1
      
 немесе  
P
X
P
ij
ij
n
j
m
i
0
1
1
=
Σ
Σ
=
=
 
m
n 
m
n
m 
n 
m 
n 

Экономикалық-математикалық әдістер 
 
68
 
    где   
P
ij
=
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
0
1
0
0
0
1
0
0
Κ
Κ
Κ
Κ
                              
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
=
n
j
m
i
,
1
,
1
 
 
Осылайша,  векторлық  түрдегі  транспорттық  тапсырма 
моделі мынадай түрге ие болады: 
)
4
(
,
1
,
,
1
,
0
)
5
(
1
1
)
1
(
min
1
1
)
(
0
n
j
m
i
X ij
Pij
n
j
m
i
X ij
Сij
n
j
m
i
x
L
x
P
ij
=
=
≥
=
Σ
=
Σ
=
→
Σ
=
Σ
=
=
 
 
1-анықтама.
 
mхn
X
X
ij
=
  матрицасымен  анықталатын 
(2)-(4)  жүйесінің  теріс  емес  əрбір  шешімі (1)-(4) транспорттық 
тапсырмасының жоспары деп аталады. 
2-анықтама.
 
mхn
X
X
ij
=
    жоспары  егер  нольдік  емес 
коэффициентті (5) 
теңдікке
  кіретін 
)
,
1
,
,
1
(
n
j
m
i
P
ij
=
=
  
векторлар желілік тəуелсіз болса, тірек жоспары деп аталады. 
3-анықтама.
 (1) мақсатты функциясы минималды мəнге ие 
болатын 
mхn
X
X
ij
=
 жоспары оңтайлы жоспар деп аталады. 
 
n  (m + j) -тармағы  
   m   i-тармағы 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
69
1-теорема. (1)-(4) тапсырмалары шешімді болу үшін  
b
a
j
n
j
i
m
i
Σ
Σ
=
=
=
1
1
                                    (6) 
шартының орындалуы қажет жəне ол жеткілікті. 
Мұнда транспорттық тапсырма моделі 
жабық деп аталады. 
2-теорема. (2)-(3) шектеулер  жүйесінің  А  матрицасының 
рангі шектеулер санынан 1-ге кіші, яғни 
1
)
(
−
+
=
n
m
A
r
. 
Теоремадан    желілік  тəуелсіз 
)
,
1
,
,
1
(
n
j
m
i
P
ij
=
=
  вектор-
ларының барынша  жоғары саны тек (
m+n-1) бола  алатындығы, 
ізінше,  транспорттық  тапсырманың 
mхn
X
X
ij
=
  тірек  жос-
парында 
(m+n-1)-ден  аспайтын  нөлдік  емес  компоненттердің 
бола  алатындығы  айқындалады.  Кері  жағдайда  ол 
тудырылған
 
деп аталады. 
 
2.3. Бастапқы тірек жоспарды анықтау 
 
ЖП-дың жалпы тапсырмаларын шешудегі секілді, транспорттық 
тапсырманың  оңтайлы  жоспарын  іздестіру  де  оның  қандай  да 
бір тірек жоспарын табудан басталады. 
Транспорттық  тапсырманың  бастапқы  тірек  жоспарын 
анықтаудың  бірнеше  əдісі  бар.  Оның  екеуін – батыс  бұрыш 
əдісін  жəне  минималды  элемент  əдісін  қарастыралық.  Бұл 
тəсілдердің  мəні  мынада:  тірек  жоспары 
(m+n-1)    қадамнан 
тысқары жатыр, оның үстіне əрбір қадамда  жоспардың 
искомой 
матрицасының немесе жолы, немесе бағаны анықталады. 
Солтүстік-батыс бұрышы əдіс.  
 
⎟⎟
⎟
⎟
⎟
⎠
⎞
⎜⎜
⎜
⎜
⎜
⎝
⎛
=
mn
m
m
n
n
X
X
X
X
X
X
X
X
X
X
...
..
...
...
...
...
...
2
1
2
22
21
1
12
11
 
 
жоспарын  анықтау  жоғарғы  сол  жақ  бұрыштағы  (солтүстік-
батыс) = 
Х
11 
элементінен басталады. 
 

Экономикалық-математикалық әдістер 
 
70
1-қадам. 
x
11
= min(a
1
,b
1
) 
Екі жағдай болуы мүмкін: 
А) 
,
1
1
b
a π
 бұл жағдайда 
.
,
2
,
0
,
1
11
n
j
X ij
a
X
=
=
=
 
Осылайша,  жіберудің 
А
1
  бірінші  пункті  барлық  жүкті 
тұтынудың 
В
1
  бірінші  пунктіне  бағыттады,  яғни  толығымен 
босады,  сондықтан  да  басқа 
В
2
,В
3
 , ...В
n 
  пункттеріне 
А
1
 
пунктінен  ешқандай  жүктің  жіберілуі  мүмкін  емес.  Матрица-
жоспардың  алғашқы  жолы  осылайша  анықталады,  ал  бөлуші  
кестеде  бірінші  жол  жабылады.  Мұнда  алғашқы  тұтынушының 
сұранысы 
в
1
1
 = в
1
 - х
11
 тең болады. Екінші қадамға көшейік. 
Б) )
  a
1
>b
1
  , бұл  жағдайда 
х
11
 = в
1
,  ал  бірінші  бағанның 
қалған элементтері 0-ге тең, яғни
m
i
x
i
,
2
,
0
1
=
=
 , себебі бірінші 
В  тұтынушының  сұранысы  толығымен  қанағаттандырылды, 
енді  оған  басқа 
А
2
 , ...А
m  
жіберу  пункттерінен  жүк  келмейді. 
Матрица-жоспардың  алғашқы  бағаны  осылайша  анықталады. 
Мұнда бөлуші кестедегі бірінші баған жабылады, ал бірінші 
А
1
 
жабдықтаушы жүгінің көлемі 
а
1
1
 = а
1
 - х
11
  тең болады. Екінші 
қадамға көшейік. 
2-қадам. 1-қадамға сəйкес  
А) жағдайында - 
)
,
min(
11
1
2
21
x
b
a
x
−
=
 элементін, ал  
Б)  жағдайында 
)
,
min(
2
11
1
12
b
x
a
x
−
=
  элементін  анықтай-
мыз ж.т.б. 
Бұл  процесс  жоспардың  барлық  элементтері  анықталғанға 
дейін жалғаса береді. 
Теорема.  Солтүстік-батыс  бұрыш  əдісінің  нəтижесінде 
алынған жоспар тірек жоспар болып табылады. 
Мысал:        
а
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
С
 
 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
71
Солтүстік-батыс əдісімен бастапқы тірек жоспарды анықтай-
мыз. Əуелі тапсырманың шешімділігін тексерейік: 
 
b
a
b
a
j
j
i
i
j
j
i
i
Σ
Σ
Σ
Σ
=
=
+
+
+
=
=
+
+
=
=
=
48
13
12
12
11
48
17
16
15
4
1
3
1
  
тапсырма шешімді. 
Бөлуші кесте құрайық (20-кесте): 
20-кесте 
      b
j 
a
i 
0 
1
̶̶
1
̶
 
 
0 
8
̶
 
1
̶
2
̶
 
0 
4
̶
 
1
̶̶
2
̶
 
0 
1
̶
3
̶
 
 
0  4
̶
  1
̶
5
̶
 
     8
 
11 
4
 
4 
6 3 
 
 
0  8
̶
  1
̶
6
̶
 
   7
 
 
4
 
8 
5 
8 
6 
 
 
0 1
̶
3
̶
 1
̶
7
̶
 
   3
 
 
7
 
 
4 
4 
6 
13 
 
1-қадам.     
Х
11
 = min (a
1
, b
1
) = min (15, 11) = 11 = b
1
,  бұл 
жағдайда  бірінші  тұтынушы  толығымен  қанағаттандырылды, 
сондықтан
  Х
21 
= 0,  Х
31 
= 0,  ал  бөлуші  кестеде  бірінші  баған 
жабылады, мұнда жіберудің бірінші пунктінде 
а
1
1
 = а
1
 - х
11
 = 15 
– 11 = 4 көлемде жүк қалады. 
2-қадам.  Бірінші  бағанды  анықтағаннан  кейін  матрица-
жоспарда  қалған  жоғарғы  сол  жақ  (солтүстік-батыс)  элементті 
тағы  да  анықтаймыз:  
Х
12
 =min (а
1
1
, b
2
) = min (4, 12) =4 = а
1
1
. 
Бұл  жағдайда  бірінші 
А
1
  жабдықтаушы  толығымен  босады, 
сондықтан 
В
3
  жəне
  В
4
  пункттеріне  одан  ештеңе  түспейді,  яғни 
Х
13
 =0, Х
14  
=0  жəне бөлуші кестенің бірінші жолы жабылады, ал 
екінші тұтынушының сұранысы 
в
2
1
 = в
2
 - х
12
 = 12 – 4 = 8  тең 
болады. 
3-қадам. Сызылғаннан кейін қалған матрица-жоспарда жоғарғы 
сол жақ (солтүстік-батыс) элементті тағы да анықтаймыз: 
 

Экономикалық-математикалық әдістер 
 
72
Х
22
 = min (a
2 
,b
2
1
) = min (16, 8) = 4 = b
2
1
.
 
 
Көріп  тұрғанымыздай,  екінші  тұтынушының  сұранысы 
толығымен  қанағаттандырылды,  сондықтан  да  үшінші  жабдық-
таушыдан  оған  ештеңе  жіберудің  керегі  жоқ,  яғни 
Х
32
 =0, 
бөлуші  кестенің  екінші  бағаны  жабылады,  ал  екінші  жаб-
дықтаушыда 
а
2
1
 = а
2
 - Х
22
 = 16 – 8 = 8 көлемінде жүк қалады.  
4-қадам.  Екінші  бағаны  анықталғаннан  кейін  қалған 
матрица-жоспарда элементті анықтаймыз: 
 
Х
23
 = min (а
2
1
,b
3
) = min (8, 12) = 8 = a
2
1
. 
Екінші  жабдықтаушы  толығымен  босады,  сондықтан  да 
тұтынудың 4-ші  пунктіне  бұл  жабдықтаушыдан  жүк  келмейді, 
яғни 
Х
24
 = 0, 
  сөйтіп  бөлуші  кестенің  екінші  жолы  жабылады, 
сұраныс 
b
3
1
 = b
3
 - x
23
 = 12 – 8 = 4
. 
5-қадам. 
Х
33
-ті анықтаймыз: 
 
Х
33
 = min (а
3 
,b
3
1
) = min (17,4) = 4 = b
3
1
.
 
а
3
1
 = а
3
 - Х
33
 = 17 – 4 = 13 
6-қадам. Жоспардың соңғы элементін анықтаймыз: 
 
Х
34
 = min (а
3 
1
,b
4
) = min (13,13) = 13 
Осылайша, 
m+n-1 = 3+4 – 1 = 6
  
 қадам  арқылы  бастапқы 
тірек жоспар анықталды: 
 
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
13
4
0
0
0
8
8
0
0
0
4
11
X
 
Алынған  жоспарға  сəйкес  келетін  транспорттық  шығын-
дарды анықтаймыз. Оларды бөлуші кесте бойынша оңай есептеп 
шығаруға болады: 
. 
L(X) = 11*8+4*4+8*4+8*5+4*4+13*6=88+16+32+40+16+78=270 
 
Солтүстік-батыс  бұрыш  əдісімен  құрылған  тірек  жоспарда 
транспорттық  шығындар  көрсетілмейді,  сондықтан  алынуы 
мүмкін  шешім  оңтайлы  шешімнен  алшақ  болады.  Оңтайлы 
шешімге  минималды  элемент  тəсілімен  анықталған  жоспар 
жақынырақ. 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
73
Минималды  элемент  əдісі.  Бұл  əдістің  де  алгоритмі 
қадамдардың соңғы санынан тұрады. 
1-қадам.  Шығындар  матрицасынан  минималды  элемент 
табылады: 
C j
i
Cij
0
0
min
=
 
  
:
0
0
X
j
i
жоспарының сəйкес элементі анықталады: 
      
)
0
,
0
(
min
0
0
b j
ai
X
j
i
=
 
2 жағдай болуы мүмкін: 
А) 
,
0
0 b j
ai <
 
  онда
)
,
(
min
0
0
0
0
b
a
X
j
i
j
i
=
 = 
a
i0
, 
бұл 
жағдайда 
А
i0
  пункті  толығымен  босаған,  сондықтан  басқа 
тұтынушыларға  бұл  пункттен  жүк  жіберілмейді,  яғни 
j
j
X
j
i
0
0
,
0
≠
=
    жəне  бөлуші  кестенің 
i
0
  жолы  жабылады, 
ал 
x j
i
b j
b j
−
=
0
0
0
1
0
, 2-қадамға өтелік. 
Б) 
,
0
0
b
a
>
бұл  жағдайда 
)
0
,
0
(
min
0
0
b j
ai
X
j
i
=
 = 
b
j0
, 
яғни 
B
j0
- 
тұтынушының  сұранысы  толығымен  қана-
ғаттандырылды,  демек  басқа  жабдықтаушылардан  оған  жүк 
жеткізу қажет емес, сондықтан
)
0
(
,
0
0
i
i
X ij
≠
=
, 
яғни бастапқы
 
тірек 
жоспардың 
j
0
-ші бағаны анықталды. Мұнда бөлуші кестедегі 
j
0
-
ші баған жабылады, ал 
x j
i
ai
ai
−
=
0
0
0
1
0
. 2-қадамға өтелік. 
2-қадам. 1-қадамда бастапқы тірек жоспардың жолын немесе 
бағанын  анықтағаннан  кейін,  сəйкес  жол  немесе  баған 
сызылғаннан кейін қалған бөлуші кестеде тағы да транспорттық 
шығындардың 
минималды 
элементін 
іздейміз
- 
j
j
i
i
n
j
m
i
C
ij
0
0
;
;
,
1
,
1
(
≠
≠
=
=
).
 
1-қадамдағы  секілді  жоспар-
дың  сəйкес  элементі  анықталады  жəне  т.б.  Осы  процесті 
жалғастыра отырып, қадамдардың соңғы санына қарай бастапқы 
жоспарды анықтай аламыз. 
Теорема.  Минималды  элемент  əдісімен  алынған  жоспар 
тірек жоспар болып табылады. 

Экономикалық-математикалық әдістер 
 
74
Мысалы: 
а
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
 
 
Тапсырманың  шешімділігі  алдын  ала  анықталған.  Тірек 
жоспарды минималды элемент əдісімен анықталық. 
Бөлуші кесте құрамыз (21-кесте): 
21-кесте 
          b
j 
a
i 
0 
1
̶
1
̶
 
 
1
̶
0
̶
 
 
1
̶
2
̶
 
0 
6
̶
 
1
̶̶
2
̶
 
0 
1
̶
3
̶
 
 
0  2
̶
  1
̶
5
̶
 
          8
 
 
            4
 
2 
        6 
          3  
13 
 0  6
̶
  1
̶
6
̶
 
       7
 
 
        4
 
10 
       5 
6 
          6  
 
 
0  6
̶
  1
̶
7 
       3
 
11 
        7
 
 
       4 
6 
          6  
 
 
1-қадам.  Транспорттық  шығындар  арасынан  минималды 
элементті табамыз: 
C
C
ij
14
3
min
=
=
 
Х
14
  жоспарының  бөлуші  кестенің  бірінші  жолында  жəне 
соңғы бағанында орналасқан сəйкес элементін анықтаймыз: 
Х
14
 = min (а
1 
,b
4
) = min (15,13) = 13= b
4
 
Көріп  тұрғанымыздай, 4-ші  тұтынушының  сұранысы  толы-
ғымен қанағаттандырылды,  сондықтан 
Х
24
 =0,  ал Х
34
 =0
 
  жəне 
бөлуші кестенің 4-ші бағаны жабылады, мұнда 
а
1
1
 = а
1
 - х
14
 = 15 
–13 =2. 2-қадамға өтелік. 
2-қадам. 4-ші  бағанды  сызып  тастағаннан  кейін  қалған 
бөлуші  кестеде  транспорттық  шығындардың  минималды 
элементін  іздейміз    - 
С
31
 = 3.  Жоспардың  сəйкес  элементін 

Әлжанова Н.Ш., Сәбитова Х.К. 
 
75
анықтаймыз: 
Х
31
 = min (а
3 
,b
1
) = min (17,11) = 11= b
1
, сонда 
Х
11
 
=0, Х
21
 = 0  жəне бөлуші кестенің бірінші бағаны жабылады, ал 
а
3
1
= а
3
 -х
31
 = 17 –11 =6.  3-қадамға өтеміз. 
3-қадам.  Сызылғаннан  кейін  қалған  бөлуші  кестеде  тағы  да 
транспорттық  шығындардың  минималды  элементі  анықталады. 
Олар бірнешеу болғандықтан, кез келгенін таңдаймыз, мысалы, 
С
12
 = 4. Жоспар элементін табайық Х
12
 = min (а
1
1
 
,b
2
) = min (2, 
12) = 2= (а
1
1
),
 
  мұнда 
х
13
 =0
 
    жəне  бөлуші  кестенің  бірінші 
жолы жабылады, ал 
b
2
1 
= b
2 
– x
12 
= 10.
 
4-қадам. Бөлуші кестеде 4 торша қалды, оларда транспорттық 
шығындардың  минималды  элементін  табамыз - 
С
22
 = 4. X
12
   
= 
min (а
2
, b
1
2
) = min (16, 10) = 10 = (b
1
2
 
 анықтаймыз, мұнда 
х
32
 = 0  
жəне бөлуші кестенің 2-ші бағаны жабылады, ал 
а
2
1 
= а
2 
– x
22 
= 
16-10=6. 
5-қадам.  Транспорттық  шығындардың  келесі  минималды 
элементі - 
С
33
 = 4.
 
Х
33
 = min (а
3
1
 
,b
3
) = min (6, 12) = 6= а
3
, 
анықтаймыз, 3-ші жолдың барлық элементтері анықталған, яғни 
бөлуші  кестенің 3-ші  жолы  жабылады,  мұнда  тек 3-ші 
тұтынушы  ғана  қанағаттандырылмай  қалды,  оған  жүктің            
6  бірлігі  жетпейді,  мұны  ол  жүктің 6 бірлігі  қалған 2-ші 
жабдықтаушыдан алады. 
6-қадам. 
Х
23
 = min (а
2
1
 
,b
3
1
) = min (6, 6) = 6 
 
Сонымен, тірек жоспарын аламыз 
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
0
6
0
11
0
6
10
0
13
0
2
0
X
 
 
Алынған  тасымалдау  жоспарына  сəйкес  келетін  шығындар-
ды анықтаймыз. Оларды бөлуші кесте бойынша оңай есептеуге 
болады: 
 
L(X) = 2*4+13*3*+10*4+6*5+11*3+6*4=8+39+40+30+33+24=174 
 
Егер  енді  минималды  элемент  жəне  солтүстік-батыс  бұрыш 
əдістерімен алынған жоспарлардың транспорттық шығындарын 
салыстырып  көрер  болсақ,  онда  минималды  элемент  тəсілі 
арқылы үздік тірек жоспары алынғандығын көруге болады. 
 

Экономикалық-математикалық әдістер 
 
76

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

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