Ứng dụng thuật toán tìm đường đi nhanh nhất tìm luồng cực đại đa phương tiện tuyến tính đồng thời chi phí cực tiểu trên mạng giao thông mở rộng<?xml:namespace prefix = "o" ns = "urn:schemas-microsoft-com:office:office" /><o:p></o:p>

Tóm tắt

Đồ thị và mạng mở rộng 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ế, …. [7]. Kết quả chính của bài báo là nghiên cứu thuật toán tìm luồng cực đại đa phương tiện tuyến tính đồng thời chi phí cực tiểu trên mạng giao thông mở rộng, sử dụng thuật toán tìm đường đi nhanh nhất trên mạng giao thông mở rộng [6]. Trên sơ sở bài toán đối ngẫu trong [7], tác giả xây dựng thuật toán đưa tỉ lệ hàm mục tiêu hai bài toán đối ngẫu này tiến đến 1, và từ đó suy ra luồng cực đại đồng thời chi phí cực tiểu. Đây là thuật toán tính gần đúng với tỉ lệ xấp xỉ là (1+w) với w dương nhỏ tùy ý. Bài báo phân tích, chứng minh các kết quả và đánh giá độ phức tạp của thuật toán. Chương trình thuật toán được viết bằng ngôn ngữ Java với cơ sở dữ liệu mạng mở rộng cài đặt trong hệ quản trị cơ sở dữ liệu MySQL cho kết quả chính xác.<?xml:namespace prefix = \"o\" ns = \"urn:schemas-microsoft-com:office:office\" />