Chương 4:
Bài toán vận tải là gì, cách giải bài
toán vận tải bằng phương pháp góc
tây bắc, Hoàn thiện lời giải bằng
phương pháp thế vị
(Giải bài toán vận tải, hàm mục tiêu, ràng buộc, cách giải thông
qua ví dụ).
1. Trình bày về bài toán vận tải.
Lập bài toán vận tải
Bản chất của bài toán vận tải là tìm phương án tối ưu để vận tải
hàng hóa từ một số nơi phát đến một số nơi nhận.
Chỉ tiêu tối ưu ở đây thường là cực tiểu chi phí tổng về vận tải.
Bài toán có thể mô tả như sau: có m địa điểm phát , với các lượng
hàng hoá tương ứng a
1
, a
2
,. . ., a
m
và n địa điểm nhận, với nhu cầu
tương ứng b
1
, b
2
, . . ., b
n
. Cần xác định phương án vận tải sao cho
tổng chi phí là cực tiểu, khi biết giá thành cước phí đơn vị C
ij
vận
tải trên đoạn đường từ nơi phát i đến nơi nhận j.

j
j
m
i
i
ba
11
Bài toán vận tải được phát biểu dưới dạng toán học như sau:
- Xác định các giá trị x
ij
: i = 1, 2, , m ; j = 1, 2, , n sao cho:
f(X) =

 

m
i
n
j
ijij
xC
1 1
min
với các ràng buộc:







11
X
12
X
1n
X
mnX
m1

X
m2
Mô tả bài toán
và :
xij
≥ 0 (i = 1,2, , m ; j = 1, 2, , n )
- Ngoài ra trong trường hợp đơn giản thường giả thiết là tổng dung
lượng hàng phát đi cân bằng với tổng dung lượng nơi nhận, nghĩa
là:



n
j
j
m
i
i

b3 = 100. Cước phí vận tải cij được ghi ở góc phải phía tr
ên trong
t
ừng ngăn ở bảng. Xuất phát từ góc tây bắc ta có x11 = 150 (vì
b1<a1) như vậy x21 = 0, ở ngăn A1B2 sẽ nhận giá trị (a1 - 150) =
50 v.v Ti
ếp tục đi xuống góc đông nam và có giá trị của (m+n-1)
ẩn cơ bản, ở đây: m+n-1 = 4
Vậy phương án cơ bản ban đầu là : x11 = 150 ; x12 =50 ; x22 =
200 ; x23 = 100.
Khi đó: F1(X) = 150.5 + 50.3 + 200.4 + 100.6 = 2300.
Rõ ràng phương án cơ bản ban đầu ở đây chưa đạt min f(X) cần
tìm cách giảm giá trị f(x)
3. Hoàn thiện lời giải bằng phương pháp thế vị.
Sau khi đã có giá trị của (m+n-1) ẩn cơ bản của phương án ban
đầu, cần t
ìm phương pháp để hoàn thiện lời giải dẫn với phương án
ứng với giá trị min f(x). Sau đây sử dụng một trong những phương
pháp thường dùng là phương pháp thế vị (c
òn gọi là phương pháp
phân ph
ối cải biên).
N
ội dung phương pháp thế vị gồm những bước sau:
1.Xác định giá trị thế vị
2.Chỉ tiêu tối ưu theo phương pháp thế vị
3. Nguyên tắc vòng kín hoàn thiện lời giải
1. Xác định giá trị thế vị
Ứng với mỗi hàng (nơi phát A1, A2, ,Am) có thế vị 1, 2, ,
m và mỗi cột (nơi nhận B1, B2, Bn ) có thế vị 1, 2, , n.

0 200 100
300 1
Dung
lượng
bi 150 250 100 500
β 5 3 5
2. Chỉ tiêu tối ưu theo phương pháp thế vị:
Định lí : Phương
án X =  xij  của bài toán vận tải là tối ưu
khi các giá trị thế vị i, j thoả mãn điều kiện sau:
i + j = cij ở ngăn có xij > 0
i + j cij ở ngăn có xij = 0
3. Nguyên tắc vòng kín hoàn thiện lời giải
4.3.3. Hoàn thiện lời giải bằng phương pháp thế vị
Vậy phương án là tối ưu ,hàm mục tiêu f(x) có giá trị
F3(X) = 1400
Sơ đồ khối và một số chú ý
Trong thực tế nhiều bài toán không có điều kiện đẳng thức như
trên mà có:



n
j
j
m
i
i
ba
11

Không
Chọn ngăn (AiBj); Có max

ij
Lập vòng kín +. . . - ; Xác định xij mới

xij mới ?
Không
Bài toán vô
nghiệm
Không
Lập phương án mới
Xác định thế vị

i
: i= 1, 2, ,m ;

j : j = 1, 2, ,n