BÀI TOÁN VẬN TẢI
I. Bài toán vận tải dạng tổng quát
1. Phát biểu bài toán vận tải
Giả sử có nguồn phát A gồm m địa
điểm phát S1,S2,…,Sm cùng sản xuất một
loại hàng hóa nào đó với trữ lượng tương
ứng lần lượt là a1,a2,…,am. và nguồn thu B
gồm n nơi tiêu thụ T1,T2,…,Tn cùng thu
một loại hàng hóa nói trên với trữ lượng
cần thu tương ứng lần lượt là b1,b2,…,bn.
Hay đơn giản, ta gọi :
: là điểm phát thứ i
: là điểm thu thứ j
: được gọi là lượng phát thứ i
: được gọi là lượng thu thứ j
: là cước phí vận chuyển một đơn vị
hàng hóa từ điểm phát thứ i đến điểm thu
thứ j.
ma trận cước phí.
i
S
j
T
i
a
j
b
ij
c
1,
1,
im
ij
jn
Cc
Hàng hóa có thể chuyển từ một điểm
phát bất kỳ đến một điểm thu bất kỳ.
Yêu cầu của bài toán vận tải là :
Hãy lập kế hoạch vận chuyển hàng
hóa từ các điểm phát đến các điểm thu
sao cho tổng cước phí vận chuyển là bé
nhất và thỏa mãn nhu cầu thu phát.
Gọi xij là lượng hàng vận chuyển từ
điểm phát thứ i đến điểm thu thứ j.
Ta có :
: chi phí vận chuyển lượng hàng
xij từ điểm phát i đến điểm thu j.
: tổng chi phí vận chuyển hàng
từ các điểm phát i đến các điểm thu j.
ij ij
cx
11
mn
ij ij
ij
cx


: lượng hàng
được chuyển đi khỏi điểm phát thứ i.
: lượng hàng
được chuyển đến điểm thu thứ j .
12
1
n
ij i i in
j
x x x x
12
1
m
ij j j mj
i
x x x x