minimum cost flow probem

Cho mạng đường bay như trong hình. Các đường nối giữa 2 điểm là các chuyến bay trong lịch của hãng hàng không. Hãng cần thực hiện các chuyến bay để vận chuyển hành khách và hàng hóa từ điểm 1 và 2 đến điểm 5, 6, 7

Hãng hàng không không có các chuyến bay thẳng trực tiếp từ các điểm khởi hành 1, 2 (gọi là điểm nguồn- điểm cung) đến các điểm kết thúc 5, 6, 7 (gọi là điểm đích- điểm cầu). Vì vậy họ nối chuyến thông qua các điểm trung chuyển 3 và 4. Các số bên cạnh các nốt biểu thị chi phí vận chuyển 1 đơn vị khối lượng hành khách hay hàng hóa. Chúng ta cần tìm cách tốt nhất để vận chuyển hành khách, hàng hóa từ các điểm khởi hành đến các điểm kết thúc sao cho tổng chi phí là nhỏ nhất. Máy bay đi và đến ở điểm 4 có thể chở tối đa 50 đơn vị khối lượng vận chuyển. Biết số lượng cung hành khách, hàng hóa (hay số lượng chuyến bay) cần vận chuyển là số bên cạnh các nốt nguồn 1, 2. Nhu cầu cần đáp ứng là số bên cạnh các nốt đích.

Mô hình tổng quát được thể hiện như sau (Bazaraa và cộng sự):

Các tập hợp

M là tập hợp các nốt mạng

i, j, k là chỉ số các nốt

Các tham số:

c_ij là chi phí đơn vị để chở hàng từ điểm i đến điểm j

b_i là lượng hàng hóa/ nhu cầu tại điểm i

L_ij là giới hạn dưới của lưu lượng thông qua chặng i, j

U_ij là giới hạn trên của lưu lượng thông qua chặng i, j

Biến quyết định:

x_ij lưu lượng từ điểm i đến điểm j

Hàm mục tiêu:

Hàm mục tiêu 1.1 là tối thiểu hóa chi phí trên mạng đường bay. Các ràng buộc 1.2 nhằm thỏa mãn yêu cầu ở mỗi điểm bằng cách xác định lưu lượng hàng vận chuyển đến và đi từ điểm đó. Các ràng buộc 1.3 qui định về giới hạn cận trên và cận dưới theo tuyến bay.

Hướng dẫn giải bài toán bằng CPLEX Optimization Studio