ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN TRÀ GIANG
BÀI TOÁN VẬN TẢI
PHÂN TUYẾN TÍNH
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - Năm 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN TRÀ GIANG
BÀI TOÁN VẬN TẢI
PHÂN TUYẾN TÍNH
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số : 60.46.36
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
GS.TS. TRẦN VŨ THIỆU
Thái Nguyên - Năm 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
i
Mục lục
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
LỜI NÓI ĐẦU 1
Nội dung 4
1 BÀI TOÁN VẬN TẢI VỚI HÀM MỤC TIÊU TUYẾN
TÍNH 4
1.1 Bài toán và các tính chất . . . . . . . . . . . . . . . . . . . 4
1.2 Tìm phương án cực biên ban đầu . . . . . . . . . . . . . . 9
1.3 Tiêu chuẩn tối ưu . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Phương pháp thế vị . . . . . . . . . . . . . . . . . . . . . . 17

pháp giải bài toán vận tải đã biết cho bài toán vận tải mở rộng.
Bài toán vận tải tuyến tính có dạng một qui hoạch tuyến tính chính
tắc, vì thế các kiến thức về qui hoạch tuyến tính chính tắc nói chung đều
có thể áp dụng vào bài toán vận tải tuyến tính nói riêng. Ràng buộc của
bài toán vận tải tuyến tính và phân tuyến tính có cấu trúc vận tải nên
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
miền ràng buộc của các bài toán này có các tính chất đặc biệt. Có thể khâi
thác các tính chất đó để xây dựng thuật toán giẩi riêng, hiệu quả.
Luận văn này đề cập tới bài toán vận tải với hàm mục tiêu tuyến tính
và phân tuyến tính: giới thiệu nội dung, mô hình và các tính chất cơ bản
của bài toán; giới thiệu thuật toán thế vị giải bài toán vận tải tuyến tính
và dạng mở rộng của nó để giải bài toán vận tải phân tuyến tính. Vấn đề
đối ngẫu và các quan hệ đối ngẫu của bài toán vận tải tuyến tính và phân
tuyến tính cũng được đề cập tới.
Nội dung luận văn được chia thành hai chương.
Chương 1 với tiêu đề "Bài toán vận tải với hàm mục tiêu tuyến tính"
trình bày nội dung và các tính chất cơ bản của bài toán vận tải tuyến tính.
Tiếp đó, đề cập tới phương pháp "min cước" và phương pháp "góc Tây
- Bắc" để tìm phương án cực biên ban đầu của bài toán. Sau đó, trình
bày cơ sở lý luận và nội dung thuật toán thế vị (một biến thể của thuật
toán đơn hình) giải hiệu quả bài toán vận tải. Cuối chương nêu ví dụ số
để minh họa cho thuật toán giải.
Các kiến thức về bài toán vận tải nói chung và thuật toán thế vị nói
riêng sẽ cần đến ở chương sau, khi xét bài toán vận tải phân tuyến tính.
Chương 2 với tiêu đề "Bài toán vận tải với hàm mục tiêu phân tuyến
tính" đề cập tới một mở rộng bài toán vận tải tuyến tính, bằng cách thay
hàm mục tiêu tuyến tính bằng hàm mục tiêu phân tuyến tính (tỉ số của
hai hâm tuyến tính), hàm này có tính chất đơn điệu theo từng phương.
Dựa vào cấu trúc đặc biệt của bài toán, chương này nêu ra điều kiện để

qui hoạch tuyến tính đơn giản nhất và được áp dụng rộng rãi trong thực
tiễn.
Mục 1.1 giới thiệu mô hình bài toán và các tính chất cơ bản. Mục 1.2
nêu phương pháp min cước và phương pháp góc Tây-Bắc tìm phương án
cực biên ban đầu của bài toán. Điều kiện tối ưu được đưa ra ở Mục 1.3 và
thuật toán thế vị cùng cơ sở lý luận của thuật toán được trình bày ở Mục
1.4. Ví dụ số được xây dựng ở Mục 1.5.
Nội dung của chương chủ yếu tham khảo từ các tài liệu [1] , [2] và [4].
1.1 Bài toán và các tính chất
Mô hình toán học của bài toán vận tải có dạng như sau:
m

i=1
n

j=1
c
ij
x
ij
→ min (cực tiểu tổng chi phí vận chuyển) (1.1)
với các điều kiện:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
5
n

j=1
x
ij
= a

a
1
+ a
2
+ + a
m
= b
1
+ b
2
+ + b
n
(1.5)
Bài toán vận tải (1.1) - (1.4) là một dạng đặc biệt của qui hoạch tuyến
tính. Để thấy rõ điều này ta sắp xếp các biến số theo thứ tự
x
11
, x
12
, , x
1n
, x
21
, x
22
, , x
2n
, , x
m1
, x

+ + x
1n
= a
1
,
x
21
+ x
22
+ + x
2n
= a
2
,

x
m1
+ x
m2
+ + x
mn
= a
m
,
x
11
+ x
21
+ x
m1

, x
21
, x
22
, , x
2n
, , x
m1
, x
m2
, , x
mn
)
T
là véctơ cột m × n thành phần,
c = (c
11
, c
12
, , c
1n
, c
21
, c
22
, , c
2n
, , c
m1
, c

véctơ này có hai thành phần bằng 1 tại dòng thứ i và dòng thứ m + j, còn
các thành phần khác bằng 0.
Véctơ x thỏa mãn (1.2) - (1.4) gọi là một phương án của bài toán vận
tải. Một phương án đạt cực tiểu (1.1) gọi là phương án tối ưu hay lời giải.
Phương án x là phương án cực biên khi và chỉ khi các véctơ cột A
ij
của
ma trận A ứng với các x
ij
> 0 là độc lập tuyến tính.Sau đây ta sẽ giả thiết
là có điều kiện cân bằng thu phát (1.5).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7
Do bài toán vận tải có m+n ràng buộc chính, nên ta nghĩ rằng mỗi
phương án cực biên cũng có m+n thành phần dương, nhưng thực tế nó chỉ
có nhiều nhất m+n-1 thành phần dương, vì trong số các ràng buộc này có
một ràng buộc là thừa (có thể bỏ đi mà không làm ảnh hưởng tới lời giải
của bài toán). Một phương án cực biên của bài toán gọi là không suy biến
nếu số phần tử của tập hợp G = {(i, j) : x
ij
> 0} bằng m+n-1, gọi là suy
biến nếu |G| < m+n-1.
Để cho gọn, ta ghi lại dữ liệu của bài toán dưới dạng một bảng chữ
nhật, gọi là bảng vận tải (Bảng 1.1). Bảng gồm m hàng (i = 1, 2, , m)
và n cột (j = 1, 2, , n). Chỗ giao nhau ở hàng i, cột j ký hiệu là ô (i,j).
Mỗi hàng tương ứng với một trạm phát, mỗi cột tương ứng với một trạm
thu. Số ghi ở đầu mỗi hàng là lượng cung, số ghi ở đầu mỗi cột là lượng
cầu. Chi phí vận chuyển c
ij
ghi ở góc trên bên trái của ô (i,j), lượng hàng

1n
.
.
.
.
.
. · · ·
.
.
. · · ·
.
.
.
c
i1
c
ij
c
in
a
i
· · · · · ·
x
i1
x
ij
x
in
.
.

a)Bài toán vận tải luôn luôn có phương án tối ưu.
b) Hạng của hệ phương trình (1.2) - (1.3) của bài toán bằng m + n -
1.
c) Nếu lượng cung cầu a
i
, b
j
là các số nguyên thì bài toán này sẽ có lời
giải nguyên.
Có thể dùng các phương pháp của quy hoạch tuyến tính để giải bài toán
vận tải. Tuy nhiên do bài toán này có dạng đặc biệt nên người ta đã đề ra
nhiều thuật toán giải hiệu quả. Trong số đó có thuật toán thế vị sẽ xét ở
mục 1.4 dưới đây. Định nghĩa 1.1. Ta gọi dây chuyền là tập hợp các ô
có dạng:
(i
1
, j
1
), (i
1
, j
2
), (i
2
, j
2
), (i
2
, j
3

), (i
s+1
, j
s
).
Một dây chuyền khép kín (j
s+1
= j
1
hoặc i
s+1
= i
1
) gọi là một chu
trình. Như vậy, mỗi cặp ô liền nhau trong dây chuyền ở trên cùng một
hàng hay cùng một cột và số ô trên mỗi dây chuyền có thể chẵn hay lẻ.
Một chu trình bao giờ cũng gồm một số chẵn các ô.
Ví dụ1.1. Dãy ô đánh dấu "•" trong Hình 1.1 a) và b) lập thành các dây
chuyền, còn các ô với dấu • trong Hình 1.1 c) - e) lập thành các chu trình.
a)
b)
c)
d)
e)
Hình 1.1 Dây chuyền: a) - b).Chu trình: c) - e).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9
Cho G là một tập hợp ô bất kỳ của bảng vận tải. Một ô thuộc G gọi
là ô treo nếu nó là ô duy nhất của G trên hàng hay trên cột của ô đó. Với
tập hợp ô cho ở Hình 1.1 a) thì ô (1,1) và ô (4,3) là các ô treo. Nếu loại

pháp thế vị, trước hết ta cần biết một phương án cực biên của bài toán.
Có nhiều cách để tìm một phương án như thế. Sau đây là một vài phương
pháp thông dụng và có hiệu quả.
a) Phương pháp min cước
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10
Trong bảng vận tải 1.1 ta chọn ô (p, q) sao cho c
pq
= min{c
ij
: ∀(i, j)}.
Nếu cực tiểu đạt tại nhiều ô thì ta chọn một ô bất kỳ trong số các ô đó.
Sau đó phân phối hàng nhiều nhất có thể theo tuyến p → q, nghĩa là đặt
x
pq
= min{a
p
, b
q
}.
Trừ lượng hàng vừa phân phối vào khả năng thu, phát của hàng p và cột
q. Tiếp đó, ta xóa hàng p nếu điểm phát p đã phát hết hàng, hoặc cột thu
q nếu điểm thu q đã nhận đủ hàng. Khi cả hàng, cột đều hết và đủ hàng
thì chỉ xóa hàng hoặc cột, không xóa đồng thời cả hai. Trong bảng còn lại,
ta lại chọn ô có cước phí nhỏ nhất và phân phối tối đa lượng hàng còn lại
vào ô này (lượng này có thể bằng 0). Phương án x thu được có đúng m +
n - 1 ô đã được phân hàng, nó là một phương án cực biên vì các ô đã chọn
không tạo thành chu trình.
Tìm phương án cực biên ban đầu của bài toán vận tải với các số liệu
cho ở bảng 1.2.

15
130
25 30 15
70
180
45 30 40
110
35
70
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11
Cước phí nhỏ nhất trong bảng là 15 đạt tại hai ô (2.1) và (2.4). Ta chọn ô
thứ nhất và phân vào ô này lượng hàng x
21
= min{200, 130} = 130. Cột
1 đã nhận đủ hàng nên bị loại (không phân hàng vào đó nữa). Hàng 2 chỉ
còn lại lượng phát a

1
= 200 − 130 = 70.
Trong bảng còn lại (ba cột cuối), ta chọn ô (2,4) có cước phí nhỏ nhất
(bằng 15) và phân vào ô này lượng hàng x
24
= min{70, 140} = 70. Lúc
này hàng 2 đã phát hết hàng nên bị loại. Cột 4 chỉ còn thiếu lượng hàng
b

4
= 140 − 70 = 70.
Trong bảng còn lại (ba cột cuối hàng 1 và 3), ta chọn ô (1,2) có cước phí

, c
ij
, i = 1, , m, j =
1, , n.
• Bắt đầu từ ô ở vị trí góc tây bắc của bảng T (ô(1,1)), ta điền lượng hàng
x
11
lớn nhất có thể vào đó, tức cho chuyển một lượng hàng lớn nhất có
thể từ điểm phát 1 đến điểm thu 1. Dễ thấy
x
11
= min{a
1
, b
1
}
Có một trong ba khả năng sau có thể xảy ra:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12
♦ Nếu x
11
= a
1
< b
1
thì điểm phát 1 đã hết hàng, điểm thu 1 còn cần
b
1
− a
1

1
thì điểm phát 1 còn a
1
− b
1
đơn vị hàng, điểm
thu 1 đã thỏa mãn nhu cầu. Xóa cột thứ nhất của bảng T ta thu được
bảng T’ gồm m hàng và n-1 cột với lượng phát, thu tương ứng:
a
1

= a
1
− x
11
= a
1
− b
1
; a
i

= a
i
, i = 2, 3, , m,
b
j

= b
j

và các cột của bảng vận tải. Những ô (i, j) không được phân phối hàng có
x
ij
= 0
Ví dụ: Xét lại bài toán vận tải cho ở Ví dụ 1.2
Bảng 1.3
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
130 160 120 140
170
20
130
18
40
22 25
200
15 25
120
30
80
15
180
45 30 40
40
35
140
130 160 120 140
170
20
130


i=1
n

j=1
c
ij
x
ij
(P T)
v.đ.k
n

j=1
x
ij
= a
i
, i = 1, , m
m

i=1
x
ij
= b
j
, j = 1, , n
x
ij
≥ 0, i = 1, , m, j = 1, , n.

m
, v
1
, , v
n
)
T
.
Để đơn giản việc trình bày, giả sử rằng bài toán (1.1) - (1.4) không suy
biến, tức mọi phương án cực biên của nó đều không suy biến. Cách nhận
biết và khắc phục khi gặp phương án cực biên suy biến sẽ trình bày ở phần
sau
Cho phương án x
0
. Ký hiệu G(x
0
) = {(i, j) ∈ T


x
0
ij
> 0}. Sau đây là điều
kiện cần và đủ để phương án x
0
= (x
0
ij
) là phương án tối ưu.
Phương án x

0
ii
) là phương án tối ưu của bài toán vận
tải (1.1) - (1.4). Theo định lý đối ngẫu mạnh, bài toán đối ngẫu có phương
án tối ưu y
0
= (u
1
, , u
m
, v
1
, , v
n
)
T
. Do y
0
là phương án chấp nhận được
của bài toán đối ngẫu nên nó thỏa mãn mọi ràng buộc của bài toán, tức
u
i
+ v
j
≤ c
ij
; i = 1, , m; j = 1, , n.
Đây chính là điều kiện (1.6). Hơn nữa, vì x
0
là phương án tối ưu của bài

i
; i = 1, , m và
v
j
; j = 1, , n thỏa mãn (1.6) và (1.7). Ta phải chứng minh x
0
là phương
án tối ưu. Thật vậy, do có (1.7) và do x
0
ij
= 0 với (i, j) /∈ G(x
0
) nên giá trị
hàm mục tiêu tại x
0
là
f(x
0
) =
m

i=1
n

j=1
c
ij
x
0
ij

≥
m

i=1
n

j=1
(u
i
+ v
j
)x
ij
=
m

i=1
u
i
n

j=1
x
ij
+
n

j=1
v
j

j=1
x
0
ij
+
n

j=1
v
j
m

i=1
x
0
ij
(vì x
0
là một phương án)
(1.8)
=
m

i=1
(u
i
+ v
j
)x
0

= c
ij
, (i, j) ∈ G(x
0
)
có m + n - 1 phương trình độc lập tuyến tính với nhau và m + n biến
u
i
, i = 1, , m và v
j
, j = 1, , n. Do đó để giải hệ này, có thể cho một
biến giá trị tùy ý (thông thường cho u
1
= 0) và các ẩn còn lại được xác
định duy nhất bằng phương pháp thế. Như vậy, mỗi phương án cực biên
không suy biến x
0
= (x
0
ij
) tương ứng với các bộ số u
i
, i = 1, , m và
v
j
, j = 1, , n. (sai khác một hằng số) thỏa mãn (1.8). Ta gọi các số u
i
, v
j
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

i
k
j
k
> 0 (1.9)
thì x
0
không phải phương án tối ưu và từ x
0
ta chuyển đến được một
phương án cực biên x
1
tốt hơn x
0
, tức
f(x
1
) < f(x
0
)
Cách xây dựng x
1
như sau:
Do x
0
là phương án cực biên không suy biến nên


G(x
0

Xây dựng x
1
= (x
1
ij
) theo công thức
x
1
ij
=



x
0
ij
+ θ nếu (i, j) ∈ K
+
x
0
ij
− θ nếu (i, j) ∈ K
−
x
0
ij
, nếu (i, j) /∈ K
(1.10)
với
θ = min{x

r
,j
r
)}) ∪ {(i
k
,j
k
)}
Hơn nữa,
f(x
1
) = f(x
0
) − θ∆
i
k
j
k
< f(x
0
).
Ô (i
k
, j
k
) được gọi là ô điều chỉnh và K được gọi là chu trình điều chỉnh.
1.4 Phương pháp thế vị
Mục này giới thiệu phương pháp thế vị giải bài toán vận tải. Thuật
toán xuất phát từ một phương án cực biên ban đầu không suy biến x
0

0
ij
). Tập ô chọn tương ứng với x
0
là G(x
0
) = {(i, j)


x
0
ij
> 0 } gồm m+n-
1 phần tử và không chứa chu trình.
Bước 1. Xác định các thế vị u
i
, i = 1, , m, và v
j
, j = 1, , n tương ứng
với phương án cực biên x
0
bằng việc giải hệ phương trình.
u
i
+ v
j
= c
ij
∀(i, j) ∈ G(x
0

án tối ưu (Tiêu chuẩn tối ưu)). Trái lại, Chuyển bước 4.
Bước 4. (Điều chỉnh phương án)
(4.a) Xác định ô điều chỉnh (i
s
, j
s
) với
∆
i
s
j
s
= max{∆
ij
> 0|(i, j) /∈ G(x
0
)}
(4.b) Tìm chu trình điều chỉnh duy nhất K trong tập G(x
0
) ∪ (i
s
, j
s
).
(4.c) Đánh dấu lần lượt các ô trong chương trình bởi dấu (+) và (-) với
(i
s
, j
s
) ∈ K

0
i
r
j
r
= min{x
0
ij
|(i, j) ∈ K
−
}. Ta có
G(x
1
) :=

G(x
0
)\(i
r
, j
r
)

∪ (i
s
, j
s
)
và G(x
1

s
= 0, còn ô i
r
, j
r
ứng với x
0
i
r
j
r
= θ ở trên chu trình điều
chỉnh sẽ trở thành ô loại đối với phương án x
1
. Tuy nhiên, kết quả điều
chỉnh không làm thay đổi phương án cực biên mà chỉ thay đổi tập véctơ
cơ sở ứng với phương án đó;
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
19
ii) θ đạt tại nhiều ô khác nhau. Khi đó, ta sẽ loại một trong những ô
này theo quy tắc ngẫu nhiên.
Chú ý 1.3: (Dấu hiệu bài toán có phương án tối ưu duy nhất)
Nếu phương án cực biên không suy biến x
0
thỏa mãn tiêu chuẩn
∆
ij
= u
i
+ v

) và phương án cực biên
xuất phát x
0
như sau:
a = (50, 70, 80)
T
, b = (60, 30, 40, 70)
T
C =

2 4 5 1
3 6 5 8
1 2 5 3

, x
0
=

50 0 0 0
10 30 30 0
0 0 10 70

Giải. Bài toán này có m = 3 điểm phát và n = 4 điểm thu và thỏa mãn
điều kiện cân bằng thu phát. Phương án cực biên x
0
có tập ô chọn tương
ứng là
G(x
0
) = {(1, 2), (1, 3), (2, 1), (2, 4), (3, 3), (3, 4)}

= 3 ⇒ u
2
= 3 − 2 = 1;
Ô (2, 2) : u
2
+ v
2
= c
22
= 6 ⇒ v
2
= 6 − 1 = 5;
Ô (2, 3) : u
2
+ v
3
= c
23
= 4 ⇒ v
3
= 4 − 1 = 3;
Ô (3, 3) : u
3
+ v
3
= c
33
= 5 ⇒ u
3
= 5 − 3 = 2;

Ô (1, 4) : ∆
14
= u
1
+ v
4
− c
14
= 0 + 1 − 1 = 0;
Ô (2, 4) : ∆
24
= u
2
+ v
4
− c
24
= 1 + 1 − 8 = −6;
Ô (3, 1) : ∆
31
= u
3
+ v
1
− c
31
= 2 + 2 − 1 = 3;
Ô (3, 2) : ∆
32
= u

10
70403060u
i
1
3
5
2
v
j
701053
3521
33
-6303010
8463
21
0-2150
1542
10
70403060u
i
1
3
5
2
v
j
a
i
b
i

33
, x
0
22
} = min{10, 30} = 10 = x
0
33
Do đó (i
r
, j
r
) = (3, 3). Tiến hành điều chỉnh phương án ta chuyển sang
phương án cực biên mới x
1
với giá trị hàm mục tiêu bằng
f(x
1
) = f(x
0
) − θ∆
32
= 690 − 10 × 5 = 640
và sang vòng lặp thứ hai với x
0
:= x
1
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
22
Bảng 1.4.

5
2
v
j
a
i
b
i
Vòng lặp thứ 2. Các số liệu tính toán tương ứng với phương án cực
biên x
0
mới được biểu diễn ở Bảng 1.4. Vì còn ∆
12
= 1 > 0, ∆
14
= 5 > 0
và các ô (1,2),(1,4) không thuộc G(x
0
) nên x
0
chưa phải phương án tối ưu.
Dễ thấy, trong bước lặp này ta có (i
s
, j
s
) = (1, 4). Chu trình K thuộc tập
G(x
0
) ∪ {(1, 4)} là
K = {(1, 4), (1, 1), (2, 1), (2, 2), (3, 2), (3, 4)}

mới với giá trị hàm mục tiêu là
f(x
1
) = f(x
0
) − θ∆
14
= 640 − 20 × 5 = 540
Gán x
0
:= x
1
và chuyển sang Vòng lặp thứ ba.
Vòng lặp thứ ba. Các số liệu tính toán tương ứng với phương án x
0
mới tại vòng lặp này được trình bày ở Bảng 1.5.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên