tailieunhanh - 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! | 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ụ 4 Bài toán vận tải có ô cấm Phương pháp giải Ví dụ 5 Bài toán vận tải dạng max Phương pháp giải Ví dụ 6 Bài toán phân việc Thuật toán Hungarian Ví dụ 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ụ 4 Bài toán vận tải có ô cấm Phương pháp giải Ví dụ 5 Bài toán vận tải dạng max Phương pháp giải Ví dụ 6 Bài toán phân việc Thuật toán Hungarian Ví dụ 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 gt 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 . 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 . 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ụ 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ụ 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ụ 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 0 7 160 6 70 40 50 7 2 9 4 6 0 6 140 80 3 60 1 6 8 49 .