Bài giảng Toán kinh tế: Bài toán vận tải mở rộng

Bài giảng "Toán kinh tế: Bài toán vận tải mở rộng" được biên soạn với các nội dung chính sau: Bài toán không cân bằng thu phát; Bài toán vận tải với ràng buộc bất đẳng thức; Bài toán lập kho hàng; Bài toán vận tải có ô cấm; Bài toán vận tải dạng max; Bài toán phân việc. Mời các bạn cùng tham khảo bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán kinh tế: Bài toán vận tải mở rộng 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 1 Bà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 2 Bài toán vận tải với ràng buộc bất đẳng thức 3 Bài toán lập kho hàng Phương pháp giải Ví dụ 3.1 4 Bài toán vận tải có ô cấm Phương pháp giải Ví dụ 4.1 5 Bài toán vận tải dạng max Phương pháp giải Ví dụ 5.1 6 Bà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 1 Bà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 2 Bài toán vận tải với ràng buộc bất đẳng thức 3 Bài toán lập kho hàng Phương pháp giải Ví dụ 3.1 4 Bài toán vận tải có ô cấm Phương pháp giải Ví dụ 4.1 5 Bài toán vận tải dạng max Phương pháp giải Ví dụ 5.1 6 Bà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 n X X ai > bj i=1 j=1 Mô hình bài toán: m X n X min f (x) = cij xij (1) i=1 j=1 n X v.đ.k. xij ≤ ai , i = 1, · · · , m j=1 m X xij = bj , j = 1, · · · , n i=1 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à : m n+1 X X min f (x) = cij xij (2) i=1 j=1 n+1 X v.đ.k. xij = ai , i = 1, · · · , m j=1 m X xij = bj , j = 1, · · · , n + 1 i=1 xij ≥ 0, i = 1, · · · , m, j = 1, · · · , n + 1. m X n X Với bn+1 = ai − bj i=1 j=1 5 / 49 Bài toán không cân bằng thu phát Cung lớn hơn cầu Ví dụ 1.1 Xét Bài toán không cân bằng thu phát được cho bởi bảng vận tải dưới đây bj 80 70 100 90 ai 6 5 3 1 100 9 7 5 8 160 2 9 4 6 140 6 / 49 Bài toán không cân bằng thu phát Cung lớn hơn cầu Ví dụ 1.1(tiếp) Ta thêm trạm thu giả n+1=5 với yêu cầu là b5 = 400 − 340 = 60 và đặt c15 = c25 = c35 = 0. bj 80 70 100 90 60 ai 6 5 3 1 0 100 9 7 5 8 0 160 2 9 4 6 0 140 7 / 49 Bài toán không cân bằng thu phát Cung lớn hơn cầu Ví dụ 1.1(tiếp) vj −4 0 −2 1 0 ui bj 80 70 100 90 60 ai 6 5 3 1 0 0 100 + − −10 −5 −5 40 60 9 7 5 8 ...