1
BÀI TOÁN VẬN TẢI
1
Chương 3
NỘI DUNG CHƯƠNG
3.1 Thiết lập bài toán vận tải (btvt)
3.2 Phương án của bài toán vận tải
3.3 Giải bài toán vận tải
3.4 Bài toán vận tải mở
3.5 Bài toán vận tải có hàm mục tiêu max
2
2
3.1 Thiết lập bài toán vận tải (btvt)
3.1.1 Bài toán vậntải
Một công ty cầnvận chuyển hàng hóa từ các kho
hàng A
i
,(i=1, ,m) (gọilàtrạm phát)cótrữ lượng
hàng hóa tương ứng là a
i
đến các cửahàngB
j
,(j=1, ,n) (gọilàtrạmthu)với nhu cầutiếpnhận
khốilượng hàng hóa tương ứng là b
j
.
Giả sử tổng cung bằng tổng cầu, i.e.,
3
11
mn
ij

x
ij
0, i,j
Khi đómôhìnhtoánhọccủabtvtlàbtQHTTsau:
5
3.1.2 Mô hình toán học của BTVT
.
6
11
1
1
min
,( 1, ) (3.1.1)
,( 1, )
0,( 1, , 1, )






 



mn
ij ij
ij
n
ij i

a
1
a
2
…
a
m
b
1
b
2
…b
n
c
11
c
12
c
1n
…
c
21
c
22
…
c
2n
…
…
…

…c
2n
……………
a
m
c
m1
c
m2
…c
mn
8
Thu
Phát
x
11
x
12
x
1n
x
21
x
22
x
2n
x
m1
x
m2

là mộtPAcủabài
toán.
P T 20 40 40
30 2 1 3
30 4 5 2
40 2 3 6
10
3000
20
030
0
10 10
0
0300
0030
20 10 10
X






6
3.2.2 Phương án cơ bản (PACB) của btvt
i)Ôchọn(ôcơ sở)
Trong mộtPAcủabtvtthìôcólượng hàng dương
gọilàôchọn.Ô có lượng hàng bằng 0 gọilàôloại
hay ô không cơ sở.
ii) Chu trình (vòng)

là một PACB.
13
P T 20 40 40
30 2 1 3
30 4 5 2
40 2 3 6
30
0
0
20
0
300
10
10




3.2.2 Phương án cơ bảncủabtvt
iv) PACB không suy biến
Xét btvt có m trạm phát và n trạm thu.
- PACB không suy biếnlàPACBcủabtvtcósố ô
chọnbằng m+n-1.
-PACBcósố ôchọn<m+n-1 thì gọilàPACB
suy biến.
Để một PACB suy biếntrở thành PACB không suy
biếntabổ sung mộtsố “ôchọn không”.
14
8
3.2.2 Phương án cơ bản của btvt





3.2.3 Tính chất của btvt
Xét btvt có m trạm phát và n trạm thu.
i) Mọibtvtđềucóphương án tối ưu.
ii) Trong một bài toán vậntảithìsố ôchọncủa
một PACB không bao giờ vượt quá m+n-1 ô.
iii)Vớimột PACB không suy biếnthìmộtôloại
bấtkỳ cũng tạovới các ô chọncủaPAđó thành
một chu trình duy nhất.
16
9
3.3 Giải bài toán vận tải – PP thế vị
Thuật toán đượcxâydựngtrênýtưởng: tiếndần
đếntối ưu.
Xuất phát từ một PACB không suy biếncủa
bài toán, đánh giá tính tối ưucủaPAđó.
-Nếutối ưu thì dừng thuật toán.
-Ngượclại ta tìm cách xây dựng PACB mới
tốthơn, rồi đánh giá tính tối ưucủa nó.
17
3.3 Giải bài toán vận tải – PP thế vị
Thuật toán được tiến hành với 3 bước chính:
Bước 1. Xây dựng PACB xuất phát
Bước 2. Xây dựng tiêu chuẩn tối ưu
Bước 3. Xây dựng PACB mới tốt hơn
18
10

40 3 2 6
21
3.3.1 Xây dựng PACB xuất phát
PA xuất phát:
là PACB không
suy biến (vì số ô
chọn của PA là 5 bằng 3+3-1).
P T252550
30 3 1 2
30 5 4 3
40 3 2 6
22
3
25
5
3
0
0
1
5
2
0
4
20
2
0
3
10
6
40

và bỏđi dòng hoặccộtchứatrạm phát hoặctrạm
thucólượng hàng bằng 0.
Phân phốihhtối đavàoôcócướcphí
thấpnhất trong bảng còn lại.
ThựchiệnlạiBước2.
Quá trình này được lặp lại chó đến khi các trạm
phát phát hết hàng và các trạn thu nhận đủ hàng ta
sẽ được PACB của bài toán.
24
Bước 3:
Bước 4:
13
3.3.1 Xây dựng PACB xuất phát
Ví dụ 3.3.1b Hãy xây dựng PA xuất phát cho btvt ở
Ví dụ 3.3.1a bằng pp cước phí thấp nhất.
PACB xuất phát:
là PACB không suy
biến(vìsố ôchọn
là 5=3+3-1)
25
P T 25 25 50
30 3 1 2
30 5 4 3
40 3 2 6
3
5
3
1
4
2

nhất đồng thờinằm trên dòng hoặccộtcóđộ chênh
lệch giữacước phí thấpnhấtvàthấp thì lớnnhất.
26
14
3.3.2 Tiêu chuẩn tối ưu – PP thế vị
Giả sử X
0
=(x
0
ij
) là PACB không suy biếncủabtvt
(đóng) 3.1.1.
BTĐNcủa (3.1.1):
Theo định lý độ lệch bù yếu ĐKcầnvàđủ để X
0
là
tồntạimộtPA(u
i
,v
j
)của (3.2.2) sao cho.
27
11
max
,( 1, ; 1, ) (3.3.2)
mn
ii j j
ij
ijij
Zaubv

i j ij ij
uv cx 
ij i j ij
uvc  
0
kk
ij


15
3.3.3 Xây dựng PACB mới
i) Tìm ô vào cở sở(hệ thống ô chọn)
Ô vào là ô có:
(i.e., ô vào là ô có hệ sốướclượng dương và
lớnnhất)
ii) Xây dựng chu trình điềuchỉnh
Chu trình điềuchỉnh xuất phát từ ômớivào
cơ sởđi qua các ô chọncủaPACBtrước đó. Ô mới
đưavàođánh dấu ‘+’, các ô kế tiếp đánh dấu ‘-’,
‘+’ xen kẻ.
29
,
max{ / 0}
ij ij
ij


3.3.3 Xây dựng PACB mới
iii) Tìm lượng hàng điều chỉnh
-Lượng hàng điềuchỉnh là lượng hàng nhỏ

i
,v
j
) cho các ô chọn theo
CT:
ii) Tính hệ sốướclượng cho các ô loại:
+Nếu 
ij
0,i,j thì PACB hiệnhànhđãtối ưu.
+Nếu i’j’: 
i’j’
>0 thì PACB hiệnhànhchưatối
ưuBước3.
33
(**)
ijij
uvc
ij i j ij
uvc  
Tóm tắt thuật toán-PP thế vị
Chú ý:
+Hệ (**) là hệ pttt suy biến, nên hệ này có
vô số nghiệmvới1bậctự do. Để giảihệ này ta
cho mộtmộtbiếnbằng0vàgiảicácbiến còn lại.
(thường chọnu
i
=0, i=1,2,…).
+ Đốivới các ô chọnthì
ij
=0.

2
0
3
6

25
0
2
5
0
30
0
25 15




u
1
=0
u
2
=1
u
3
=4
v
1
=-1
v

4
2
0
3
6

25
0
2
5
0
30
0
25 15




u
1
u
2
u
3
v
1
v
2
v
3

PATƯ
và
38
P T 25 25 50
30 3 1 2
30 5 4 3
40 3 2 6
3
5
3
1
4
2
3

15
2
20
30
25




u
1
u
2
u
3







min
10.1 20.2 30.3 25.3 15.2 245Z 
20
3.4 Bài toán vận tải mở
Trường hợp Phát > Thu hoặc Phát < Thu thì
btvt gọilàbtvtmở. Để giảinótalậpbtvtphụ,có:
-Trạm phát phụ hoặc thu phụ vớilượng hàng phát
ra hoặc thu vào tương ứng bằng |Phát- Thu|.
-Cácố chứatrêntrạm phát phụ và thu phụ gọilàô
phụ.Cước phí trong ô phụ bằng 0.
39
3.4 Bài toán vận tải mở
- Btvt phụ là btvt đóng nên ta giải nó bằng PP thế
vị như 3.3, với chú ý như sau:
+Xâydựng PACB xuất phát ưu tiên phân
phối các ô chính trước, ô phụ phân phốihàngcuối
cùng.
+PATƯ btvt gốcbằng PATƯ btvt phụ bỏđi
các ô phụ.
40
21
3.4 Bài toán vận tải mở
Ví dụ 3.4.1
Xét btvt:

0
3
20
6
10
0
10
0
22
3.4 Bài toán vận tải mở
.
43
P T 25 40 25 10
20 2 1 3 0
40 4 3 6 0
40 2 5 2 0
1
20
0
0
2
25
0
2
150
0
3
20
6
10

2
2
+
-
+
+
-
-
Ô vào CS (1,1)
Lượng hàng
đ/c d=10
Ô ra CS (2,3)
3.4 Bài toán vận tải mở
Vì 
ij
0, i,j nên PACB bảng 2 đã tối ưu.
44
2130
4360
2520
1
20
0
0
2
25
0
2
150
0

+
+
-
-
Bảng 2
2130
4360
2520
1
10
2
15
2
25
3
30
0
10
2
10






v
2
=1
u

0, i,j thì PACB hiệnhànhtối ưu.
-Nếu 
i’j’
<0 thì PACB h/hành chưatối ưu.
46
24
3.5 BTVT có hàm mục tiêu cực đại
iii) Xây dựng PACB mới
-Chọnôvàocơ sở là ô có hệ sốướclượng âm
và có trị tuyệt đốilớnnhất.
- Chu trình điềuchỉnh, lượng hàng điềuchỉnh
và ô ra khỏicơ sở giống bài toán min.
47
3.5 BTVT có hàm mục tiêu cực đại
Ví dụ 3.5.1:
Một Công ty DV có 50 máy tính gồm25máyloại
I, 15 máy loạiIIvà10máyloại III . Công ty
tuyển50KTVgồm20KTVbậcI,10KTVbậcII
và 20KTV bậcIIIvớihiệusuất đứng máy
(sp/ngày) được cho chi tiếtnhư sau:
48
25
3.5 BTVT có hàm mục tiêu cực đại
Hãy phân công các KTV sao cho tổng hiệusuất
làm việc cao nhất.
49
LI LII LIII
BI 10 9 8
BII 9 7 6
BIII 8 5 4