Bài toán vận tải mở rộng
GV : Phạm Thị Hoài
Viện Toán ứng dụng và Tin học
Trường Đại học Bách khoa Hà Nội
1 / 49
Nội dung chính
1Bài toán không cân bằng thu phát
Cung lớn hơn cầu
Cầu lớn hơn cung
2Bài toán vận tải với ràng buộc bất đẳng thức
3Bài toán lập kho hàng
Phương pháp giải
Ví dụ 3.1
4Bài toán vận tải có ô cấm
Phương pháp giải
Ví dụ 4.1
5Bài toán vận tải dạng max
Phương pháp giải
Ví dụ 5.1
6Bài toán phân việc
Thuật toán Hungarian
Ví dụ 6.1 2 / 49
Bài toán không cân bằng thu phát
Nội dung
1Bài toán không cân bằng thu phát
Cung lớn hơn cầu
Cầu lớn hơn cung
2Bài toán vận tải với ràng buộc bất đẳng thức
3Bài toán lập kho hàng
Phương pháp giải
Ví dụ 3.1
4Bài toán vận tải có ô cấm
Phương pháp giải
Ví dụ 4.1
5Bài toán vận tải dạng max
Phương pháp giải
Ví dụ 5.1
6Bài toán phân việc
Thuật toán Hungarian
Ví dụ 6.1 3 / 49
Bài toán không cân bằng thu phát Cung lớn hơn cầu
Bài toán đặt ra cung lớn hơn cầu
Tức là: m
X
i=1
ai>
n
X
j=1
bj
Mô hình bài toán:
min f(x) =
m
X
i=1
n
X
j=1
cij xij (1)
v.đ.k.
n
X
j=1
xij ≤ai, i = 1,· · · , m
m
X
i=1
xij =bj, j = 1,· · · , n
xij ≥0, i = 1,· · · , m, j = 1,· · · , n.
4 / 49
Bài toán không cân bằng thu phát Cung lớn hơn cầu
Phương pháp giải
Ta chỉ cần thêm vào điểm thu giả với cước phí tại các ô đó đều là 0. Bài toán với m điểm
phát và n+1 điểm thu là :
min f(x) =
m
X
i=1
n+1
X
j=1
cij xij (2)
v.đ.k.
n+1
X
j=1
xij =ai, i = 1,· · · , m
m
X
i=1
xij =bj, j = 1,· · · , n + 1
xij ≥0, i = 1,· · · , m, j = 1,· · · , n + 1.
Với bn+1 =
m
X
i=1
ai−
n
X
j=1
bj
5 / 49