Chương 2
BÀI TOÁN VẬN TẢI
Blog:
https://nguyenphuongblog@wordpress.com
Email: nguyenphuong0122@gmail.com
1
NGUYỄN PHƯƠNG
Khoa Khoa Học Dữ Liệu trong Kinh Doanh
Trường Đại Học Ngân Hàng TPHCM
2
NỘI DUNG
1.Mô hình bài toán vận tải
2.Phương pháp giải bài toán vận tải
3.Sử dụng Excel giải bài toán vận tải
4.Một số ứng dụng của bài toán vận tải
- Bài toán phân công lao động
- Bài toán xe không
- Bài toán vận tải có ô cấm
- Bài toán bố trí cây trồng
5. Bài tập
3
1. MÔ HÌNH BÀI TOÁN VẬN
TẢI
Ví dụ 1:
Công ty lương thực An Bình cần vận chuyển gạo từ các kho
A1, A2, A3 đến các đại lý B1, B2, B3, B4. Cho biết chi phí vận
chuyển gạo (ngàn đồng/tấn) từ các kho đến kho đến các đại
lý trong bảng sau B1 B2 B3 B4
A1 100 20 200 110
A2 120 70 90 200
A3 20 140 160 180
Hãy lập mô hình bài toán vận chuyển gạo từ kho tới các đại
lý sao cho tổng chi phí vận chuyển thấp nhất. Biết rằng các
kho A1, A2, A3 có trữ lượng gạo là 15, 25, 5; đại lý B1, B2, B3,
B4 có nhu cầu nhập 5, 15, 15, 10 (tấn).
4
Gọi xij là khối lượng gạo vận chuyển từ kho Ai đến đại lý Bj
. Khi đó, ta có mô hình bài toán:
11 12 13 14 21 22
23 24 31 32 33 34
11 12 13 14
21 22 23 24
31 32 33 34
11 21 31
12 22 32
13 23 33
11 24 34
ij
( ) 100 20 200 110 120 70
90 200 20 140 160 180 min
15
25
5
5
15
15
10
0
= + + + +
+ + + + + +
+ + + =
+ + + =
+ + + =
+ + =
+ + =
+ + =
+ + =
f x x x x x x x
x x x x x x
x x x x
x x x x
x x x x
x x x
x x x
x x x
x x x
x, 1,3; 1,4
= =
i j
5
NỘI DUNG BÀI TOÁN VẬN TẢI
Giả sử cần vận chuyển một loại hàng hóa (xi măng, sắt
thép, ...) từ m điểm cung cấp (trạm phát), ký hiệu là A1,
A2, ..., Am đến n điểm tiêu thụ (trạm thu), ký hiệu là B1,
B2, ..., Bn, biết rằng
a) Số lượng hàng có ở các trạm phát A1, A2, ..., Am lần lượt
là a1, a2,..., am
b)Số lượng hàng cần ở các trạm thu B1, B2, ..., Bn lần lượt
là b1, b2,..., bn.
c)Chi phí vận chuyển một đơn vị hàng hóa từ trạm phát Ai
đến trạm thu Bj là cij.
Hãy lập kế hoạch vận tải hàng hóa sao cho tổng chi phí
vận tải thấp nhất và thỏa mãn yêu cầu thu – phát.