Ứ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

Hoàng Văn Tám, Đậu Mạnh Hoàn

Tóm tắt


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 bài toán 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 sẽ 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 một 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ũ nhưng đảm bảo được chi phí vận chuyển là nhỏ nhất. Kết quả nghiên cứu của bài báo 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 được chi phí nhưng vẫn đảm bảo được khối lượng vận chuyển.


Từ khóa


Lý thuyết đồ thị; toán tối ưu; luồng cực đại; chi phí tối thiểu; vận tải.



TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ

Địa chỉ: Trường Đại học Quảng Bình, 312 Lý Thường Kiệt, Phường Bắc Lý, Thành phố Đồng Hới, Tỉnh Quảng Bình 
ĐT: 0232.3822010 - Fax: 0232.3821054