ỨNG DỤNG BÀI TOÁN LUỒNG CỰC ĐẠI VỚI CHI PHÍ CỰC TIỂU CHO BÀI TOÁN VẬN CHUYỂN HÀNG CỨU TRỢ TRÊN ĐỊA BÀN QUẢNG BÌNH

Abstract

Bài toản luồng cực đại trong mạng có nhiều ứng dụng trong thực tế, điển hình như bài toán xác định cường độ lớn nhất của dòng vận tài giữa hai nút của một bản đồ giao thông, bài toản tìm luồng dầu lớn nhất có thể bơm từ tàu chở dầu vào bể chứa của một hệ thống đường ống dẫn dầu... Ngoài ra, ứng dụng của bài toán còn để giải các dạng như: Bài toán đám cưới vùng quê, bài toản về hệ thống đại diện chung, bài toán phân nhóm sinh hoạt, bài toán lập lịch cho hội nghị... Trong nghiên cứu này chúng tôi trình bày việc ứng dụng bài toán luồng cực đại với chi phí cực tiểu (một biến thể của bài toàn luồng cực đại trong mạng) để xây dựng ứng dụng hỗ trợ công tác vận chuyển hàng cứu trợ bão lũ. Ứng dụng nhằm mục đích tìm ra phương án vận chuyển được tối đa lượng hàng hóa, lương thực cung ứng đủ cho người dân vùng lũ song vẫn đảm bảo được chi phí vận chuyển nhỏ nhất. Kết quả nghiên cứu là cơ sở để phát triển một ứng dụng dùng trong vận tải nói chung nhằm tiết kiệm chỉ phỉ nhưng vẫn đảm bảo được khối lượng vận chuyển.