Luồng đa hàng hóa đa chi phí tuyến tính tối ưu trên mạng hỗn hợp mở rộng

Abstract

Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế,…. Hiện nay, việc ứng dụng lý thuyết đồ thị để giải quyết các bài toán trong thực tế được các nhà khoa học quan tâm nghiên cứu. Bài toán luồng đa hàng hóa trên mạng là bài toán tối ưu có nhiều ứng dụng trong các lĩnh vực kinh tế xã hội như giao thông, truyền thông, vận tải …, khác với bài toán đơn hàng, trong bài toán mạng đa hàng hóa có nhiều loại hàng hóa được lưu thông trên mạng như các gói tin, các phương tiện giao thông,… tùy thuộc vào loại hàng hóa mà cần nhu cầu lưu chuyển khác nhau. Bài toán đặt ra là tìm luồng vận chuyển có chi phí cực tiểu và lưu lượng trên mỗi tuyến được chia sẽ cho nhiều loại hàng hóa.