MÔ HÌNH LƯU LƯỢNG CỰC ĐẠI

Nguyễn Như Phong

Kỹ thuật Hệ thống Công nghiệp

Đại học Bách Khoa TPHCM

a. Bài toán lưu lượng cực đại 

Một bài toán lưu lượng cực đại là bài toán vận chuyển dầu thô từ một giếng dầu đến nhà máy lọc dầu qua một mạng ống dẫn dầu. Giữa giếng dầu và nhà máy lọc dầu trên mạng ống dẫn dầu là những trạm bơm được lắp đặt để bơm dầu trong mạng.

Mỗi đường ống tương ứng với một cung có thuộc tính là năng lực định bởi lưu lượng cực đại của đường ống. Một thuộc tính khác của cung là định hướng hay không, nghĩa là đường ống dẫn dầu chỉ một chiều hay cả hai chiều. Bài toán có mục tiêu cực đại lưu lượng của mạng dẫn dầu với các ràng buộc về năng lực của hệ thống đường ống.

b.  Giải thuật lưu lượng cực đại 

Bài toán cực đại lưu lượng có thể giải bằng các giải thuật cực đại lưu lượng, tuy nhiên cũng có thể giải qua mô hình QHTT.

Gọi lưu lượng cực đại trên cung (i,j) là C_ij và lưu lượng trên cung (i,j) là X_ij. Mục tiêu bài toán là cực đại lưu lượng giữa nút đầu và nút cuối. Với các ràng buộc về bảo toàn lưu lượng ở các nút và lưu lượng cực đại ở các cung. Ngoại trừ nút đầu và nút cuối, ràng buộc bảo toàn lưu lượng các nút có nghĩa là tổng lưu lượng vào nút phải bằng với tổng lưu lượng ra nút. Ràng buộc lưu lượng cực đại ở các cung là lưu lượng ở các cung không được vượt quá lưu lượng cực đại của cung.

TLTK

Nguyễn Như Phong. Vận trù xác định. NXBĐHQG. 2010