MẠNG ĐA HÀNG HÓA ĐA CHI PHÍ TUYẾN TÍNH MỞ RỘNG VÀ BÀI TOÁN TÌM LUỒNG CỰC ĐẠI

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ế,…. Cho đến nay, phần lớn các ứng dụng trong đồ thị mới chỉ xét đến trọng số của các cạnh, các đỉnh một cách độc lập, trong đó độ dài đường đi là tổng trọng số các cạnh và các đỉnh trên đường đi đó. Tuy nhiên, trong thực tế, trọng số tại một đỉnh không giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi đỉnh đó. Công trình [2] đề xuất chi phí chuyển làn (switch cost) cho đồ thị có hướng. Các công trình [3-6] nghiên cứu các bài toán luồng đa hàng hóa đơn chi phí tuyến tính trên mạng truyền thống. Các công trình [7-11] nghiên cứu các bài toán luồng đa hàng hóa đơn chi phí tuyến tính trên mạng mở rộng, trong đó chi phí chuyển làn được định nghĩa cho đồ thị hỗn hợp. Bài viết xây dựng mô hình mạng đa hàng hóa đa chi phí mở rộng để có thể áp dụng mô hình hóa các bài toán thực tế chính xác và hiệu quả hơn. Bài toán luồng đa hàng hóa đa chi phí tuyến tính cực đại được mô hình hóa bằng bài toán quy hoạch tuyến tính ẩn. Trên cơ sở lý thuyết đối ngẫu trong quy hoạch tuyến tính, một thuật toán xấp xỉ có độ phức tạp đa thức được phát triển.