tailieunhanh - Bài toán vận tải có vận chuyển ngược

Bài toán vận tải (Transportation problem) của qui hoạch tuyến tính đã khá quen thuộc trong toán ứng dụng. Trong bài toán vận tải dạng bảng chỉ cho phép vận chuyển hàng từ các điểm phát đến các điểm thu, không vận chuyển theo chiều ngược lại (từ trạm thu tới trạm phát). | Trịnh Thị Thanh Hảo Tạp chí KHOA HỌC & CÔNG NGHỆ 90(02): 107 - 112 BÀI TOÁN VẬN TẢI CÓ VẬN CHUYỂN NGƢỢC Trịnh Thị Thanh Hảo* ĐH Khoa học - ĐH Thái Nguyên TÓM TẮT Bài toán vận tải (Transportation problem) của qui hoạch tuyến tính đã khá quen thuộc trong toán ứng dụng. Trong bài toán vận tải dạng bảng chỉ cho phép vận chuyển hàng từ các điểm phát đến các điểm thu, không vận chuyển theo chiều ngƣợc lại (từ trạm thu tới trạm phát). Lời giải thu đƣợc đôi khi không cho chi phí vận chuyển nhỏ thể mở rộng bài toán vận tải dạng bảng bằng cách cho phép vận chuyển hàng theo cả chiều ngƣợc lại từ các trạm thu tới các trạm phát. Từ đó dẫn đến mô hình bài toán vận tải có vận chuyển ngƣợc (Transportation problem with reshipments). Trong nhiều trƣờng hợp, vận chuyển ngƣợc giúp làm giảm chi phí vận chuyển. Từ khóa: Bài toán vận tải, vận chuyển ngược, toán ứng dụng, trạm thu. MỞ ĐẦU* Bài toán vận tải (Transportation problem) của qui hoạch tuyến tính đã khá quen thuộc trong toán ứng dụng. Trong bài toán vận tải dạng bảng chỉ cho phép vận chuyển hàng từ các điểm phát đến các điểm thu, không vận chuyển theo chiều ngƣợc lại (từ trạm thu tới trạm phát). Lời giải thu đƣợc đôi khi không cho chi phí vận chuyển nhỏ nhất. Có thể mở rộng bài toán vận tải dạng bảng bằng cách cho phép vận chuyển hàng theo cả chiều ngƣợc lại từ các trạm thu tới các trạm phát (xem [3]). Từ đó dẫn đến mô hình bài toán vận tải có vận chuyển ngƣợc (Transportation problem with reshipments). Trong nhiều trƣờng hợp, vận chuyển ngƣợc giúp làm giảm chi phí vận chuyển. Bài viết này đề cập đến bài toán vận tải có vận chuyển ngƣợc: Phát biểu mô hình toán học của bài toán, xét tính chất của nghiệm, đƣa ra điều kiện tối ƣu. Cuối cùng, đề xuất thuật toán giải trên cơ sở mở rộng thuật toán thế vị quen thuộc và nêu ra ví dụ số. VÌ SAO CẦN VẬN CHUYỂN NGƢỢC? Ví dụ. Giả sử cần vận chuyển một loại hàng (xi măng chẳng hạn) từ hai kho A và B (gọi là các trạm phát), mỗi kho có 150 tấn, tới hai hộ tiêu thụ I và II (gọi là .