CHƯƠNG VI: Bài toán vận tải
I. Mô hình bài toán
1. Đặt bài toán
Một công ty vận tải cần chuyên chở hàng hóa từ mnơi giao hàng đến
nnơi nhận hàng, biết:
Mỗi nơi giao hàng có thể đem hàng giao đến nhiều nơi nhận hàng và 1
nơi nhận có thể nhận hàng từ nhiều nơi giao hàng.
+Khối lượng hàng cần chuyển đi tại mỗi nơi giao là Si(i= 1m); Si0
+ Yêu cầu về hàng hóa tại mỗi nơi nhận hàng là Dj(j=1n); Dj0
+ Chi phí để vận chuyển 1đơn vị hàng hóa từ nơi giao hàng thứ iđến
nơi nhận hàng thứ jlà Cij (i= 1m; j=1n); 𝐶𝑖𝑗 0.
Cij tính đến:Độ dài đoạn đường vận chuyển
Tính chất đoạn đường vận chuyển
Tính chất hàng hóa vận chuyển
Loại phương tiện vận chuyển
Chi phí lưu xe,bốc,dỡ hàng.
CHƯƠNG VI: Bài toán vận tải
I. 1. Đặt bài toán
Yêu cầu:
Tìm PA vận chuyển hàng hoá sao cho:
+Tổng chi phí vận chuyển hàng hoá từ tất cả các nơi giao hàng đến
tất cả các nơi nhận hàng là nhỏ nhất.
+ Thoả mãn được yêu cầu về hàng hóa tại các nơi giao hàng và các
nơi nhận hàng.Nghĩa là sau quá trình vận chuyển:
Hàng ở nơi giao hàng phải được giao hết.
Hàng nơi nhận hàng phải được nhận đủ.
CHƯƠNG VI: Bài toán vận tải
I.2. Mô hình bài toán
Gọi 𝑋𝑖𝑗 là lượng hàng vận chuyển từ nơi giao hàng thứ i (i= 1m) đến
nơi nhận hàng thứ j (j= 1n);𝑋𝑖𝑗0.
+Lập bảng chi phí (T)
Nơi
giao hàng Nơi nhận hàng
Lượng
hàng
ở
nơi
giao (Si)
1 2 ... n
1
C
11
X
11
C
12
X
12
C
1n
X
1n
S1
2
C
21
X
21
C
22
X
22
C
2n
X
2n
S2
...
...
...
m
C
m1
X
m1
C
m2
X
m2
C
mn
X
mn
Sm
Yêu
cầu hàng
tại
nơi
nhận (Dj)D1D2... Dn
σ
𝐷𝑗&
σ
𝑆𝑖
CHƯƠNG VI: Bài toán vận tải
I.2. Mô hình bài toán
+ Hàng ở các nơi giao phải được phân phối hết:
X11 + X12 + … + X1n =σ𝑗=1
𝑛𝑋1𝑗= S1
X21 + X22 + … + X2n =σ𝑗=1
𝑛𝑋2𝑗= S2
…
Xm1 + Xm2 + … + Xmn =σ𝑗=1
𝑛𝑋𝑚𝑗= Sm
+ Hàng ở các nơi nhận phải được đáp ứng đủ
X11 + X21 + … + Xm1 =σ𝑖=1
𝑚𝑋𝑖1= D1
X12 + X22 + … + Xm2 =σ𝑖=1
𝑚𝑋𝑖2= D2
…
X1n + X2n + … + Xmn =σ𝑖=1
𝑚𝑋𝑖𝑛= Dn
+ RB đương nhiên:
𝑋𝑖𝑗0 (i= 1m; j=1n)
CHƯƠNG VI: Bài toán vận tải
I.2. Mô hình bài toán
Tóm tắt mô hình:
+ HMT:σ𝑖=1
𝑚σ𝑗=1
𝑛𝐶𝑖𝑗𝑋𝑖𝑗→𝑀𝑖𝑛
+ RB:
(i) Hàng ở các nơi giao hàng được phân phối hết
σ𝑗=1
𝑛𝑋𝑖𝑗=𝑆𝑖(i= 1÷m)
(ii) Yêu cầu hàng hóa ở nơi nhận được đáp ứng đủ
σ𝑖=1
𝑚𝑋𝑖𝑗=𝐷𝑗(j= 1÷n)
(iii) RB đương nhiên:
𝑋𝑖𝑗≥0 (i= 1÷m; j= 1÷n)