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
KHOA HỌC MÁY TÍNH
Luận án tập trung giải quyết bài toán 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. Bối cảnh nghiên cứu xuất phát từ hạn chế của các nghiên cứu hiện có, vốn thường quy đổi các loại chi phí đa dạng về một chi phí chuẩn, không phản ánh đúng thực tế về sự khác biệt chi phí giữa các loại hàng hóa và các tuyến đường bị cấm hoặc có giới hạn thông hành. Mục tiêu chính là xây dựng một mô hình mạng hỗn hợp mở rộng đa hàng hóa đa chi phí nhằm mô hình hóa chính xác và hiệu quả hơn các bài toán thực tế.
Nội dung nghiên cứu bao gồm việc tìm hiểu các khái niệm cơ bản về đồ thị, mạng, luồng trên mạng, quy hoạch tuyến tính, và các bài toán luồng cực đại trên mạng truyền thống cũng như trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí. Từ đó, luận án đề xuất các mô hình và thuật toán để giải quyết các bài toán luồng tối ưu sau trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí: luồng cực đại, luồng cực đại đồng thời, luồng cực đại với chi phí giới hạn, và luồng cực đại đồng thời với chi phí cực tiểu.
Các đóng góp chính của luận án bao gồm việc đề xuất mô hình mạng hỗn hợp mở rộng đa hàng hóa đa chi phí và các thuật toán giải quyết các bài toán luồng tối ưu tương ứng. Các thuật toán này đã được chứng minh về tính đúng đắn và độ phức tạp đa thức. Luận án cũng ứng dụng các thuật toán đã xây dựng để phân luồng giao thông tại thành phố Đà Nẵng, sử dụng ngôn ngữ lập trình C++ để cài đặt và thử nghiệm, cho thấy kết quả chính xác và hiệu quả. Hướng phát triển của nghiên cứu là ứng dụng các bài toán luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí vào nhiều lĩnh vực thực tế như logistic, giao thông, kinh tế, mạng truyền thông và máy tính.