LUỒNG CHI PHÍ NHỎ NHẤT

Nội dung bài toán
Phương pháp giải
Ví dụ minh họa

Trích từ cuốn "Các Phương Pháp Tối Ưu Hóa" của các tác giả
PGS. Bùi Thế Tâm
GS Trần Vũ Thiệu

1. Nội dung bài toán

        Cho một mạng đối xứng có n đỉnh, mỗi cạnh của mạng có một khả năng thông qua và một cước phí vận chuyển nhất định (như nhau theo cả hai chiều). Cho trước một lượng hàng S cần vận chuyển từ đỉnh nguồn (đánh số là 1) tới đỉnh đích (đánh số là n). Hãy tìm một phương án vận chuyển, nghĩa là hãy xác định trên mỗi cạnh của mạng cần vận chuyển bao nhiêu hàng, theo chiều nào, sao cho phù hợp với khả năng thông qua của mạng (trên mỗi cạnh lượng hàng vận chuyển không vượt quá khả năng thông qua của cạnh) và vận chuyển được lượng hàng S từ nguồn về đích với tổng chi phí vận chuyển là nhỏ nhất.

        Đây là một loại bài toán vận tải trên mạng có hạn chế khả năng thông qua. Tuy bài toán có một đỉnh nguồn và một đỉnh đích, nhưng bất kỳ bài toán vận tải trên mạng với nhiều nguồn (địa điểm sản xuất hàng) và nhiều đích (địa điểm tiêu dùng) đều có thể quy về bài tóan này bằng cách thêm các đỉnh và cạnh giả thích hợp.

        Về mặt toán học, bài tóan tìm luồng với chi phí nhỏ nhất có thể diễn đạt như sau:

        Cực tiểu hóa hàm chi phí ∑cijxij với điều kiện
            1. ∑(xij - xji) với mỗi j, có giá trị bằng
                a. S nếu i = 1
                b. 0 nếu i khác 1 và n
                c. -S nếu i = n
            2. 0 ≤ xij ≤ dij với mọi cạnh (i, j)

        Ở đây đỉnh nguồn được đánh số là 1, đỉnh đích là n, cij là chi phí vận chuyển một đơn vị hàng trên cạnh (i, j), dij là khả năng thông qua của cạnh (i, j); còn xij là khối lượng hàng vận chuyển trên cạnh (i, j) cần xác định.

2. Phương pháp giải

        Luồng chi phí nhỏ nhất có thể tìm theo thuật tóan đơn giản như sau: Xuất phát từ phương án vận chuyển bằng không (xij = 0 trên mọi cạnh). Ở mỗi bước lặp ta tìm một đường đi có chi phí nhỏ nhất từ nguồn tới đích. Đường đi này bao gồm một dãy các cạnh kế tiếp nhau sao cho trên các cạnh có vận chuyển hàng theo chiều đi từ nguồn tới đích (chiều thuận) thì lượng hàng vận chuyển chưa đạt tới khả năng thông qua của cạnh đó. Trên đường đi này, cạnh không vận chuyển hàng hoặc có vận chuyển hàng theo chiều thuận thì chi phí vận chuyển xem là số dương, còn trên cạnh có vận chuyển hàng theo chiều ngược (chiều từ đích tới nguồn) thì chi phí vận chuyển xem là âm. Tiếp đó, ta xác định khả năng thông qua của đường đi vừa tìm được, đó là số nhỏ nhất trong số các khả năng thông qua còn lại trên các cạnh có chi phí vận chuyển dương và lượng hàng vận chuyển trên các cạnh có chi phí vận chuyển âm. Thêm khả năng thông qua này vào các cạnh không vận chuyển hàng hoặc vận chuyển hàng theo chiều thuận và bớt đi ở các cạnh vận chuyển hàng theo chiều ngược của đường đi này. Rồi chuyển qua bước lặp sau. Quá trình này được lặp lại cho tới khi vận chuyển hết lượng hàng S từ nguồn tới đích hoặc phát hiện mạng không đủ khả năng vận chuyển hết lượng hàng S từ nguồn tới đích (do khả năng thông qua của các cạnh quá nhỏ so với nhu cầu vận chuyển S).

        Phương pháp giải nêu trên khá đơn giản và thuận tiện cho việc lập trình trên máy tính. Tuy nhiên ở mỗi bước lặp ta phải giải một bài toán phụ: tìm đường đi ngắn nhất từ nguồn tới đích trên mạng với cước phí có thể là số âm (Xem mục 2.1).

3. Ví dụ minh họa

        Cho mạng vẽ ở hình sau. Mỗi cạnh tương ứng với một cặp số có thứ tự mà số thứ nhất là chi phí vận chuyển một đơn vị hàng hóa trên cạnh, số thứ hai là khả năng thông qua của cạnh này. Nguồn là đỉnh 1, đích là đỉnh 6, tổng số hàng cần vận chuyển từ nguồn tới đích là 5 đơn vị.

        Ở bước lặp đầu tiên, phương án vận chuyển bằng 0 trên tất cả các cạnh. Tiếp đó ta tìm đường đi chi phí nhỏ nhất từ nguồn tới đích, đó là: 1 - 2 - 3 - 6 với tổng chi phí vận chuyển bằng 3. Khả năng thông qua của đường đi này bằng 2 (bằng khả năng thông qua của cạnh (1, 2) hoặc (3, 6)). Ta vận chuyển thêm 2 đơn vị hàng từ nguồn tới đích theo đường đi vừa tìm được.

        Ở bước lặp tiếp theo, đường đi có chi phí nhỏ nhất từ nguồn tới đích là 1 - 4 - 6 với chi phí vận chuyển bằng 7 và khả năng thông qua là 1 (bằng khả năng thông qua của cạnh (4, 6)). Ta vận chuyển thêm được 1 đơn vị hàng từ nguồn tới đích qua đường đi vừa tìm được.

        Ở bước lặp thứ ba, đường đi có chi phí nhỏ nhất từ nguồn tới đích là 1 - 4 - 3 - 2 - 5 - 6. Trên đường này có 3 cạnh không vận chuyển hàng, đó là (3, 4), (2, 5) và (5, 6); cạnh có vận chuyển hàng theo chiều thuận là (1, 4) và cạnh vận chuyển trên đường đi này bằng: 3 + 2 - 1 + 5 + 6 = 15. Khả năng thông qua của đường này bằng:

min(4 - 1, 4 - 0, 2 - 0, 2 - 0) = 2

        Ta vận chuyển thêm 2 đơn vị hàng trên các cạnh (1, 4), (4, 3), (2, 5), (5, 6) và bớt 2 đơn vị hàng trên cạnh (2, 3) (cạnh này bây giờ không còn vận chuyển hàng nữa). Kết quả là ta vận chuyển được toàn bộ 5 đơn vị hàng từ nguồn (đỉnh 1) tới đích (đỉnh 6), với tổng chi phí vận chuyển bằng

3 * 2 + 7 * 1 + 15 * 2 = 43

        Luồng chi phí nhỏ nhất là:
            x12 = 2; x14 = 3; x23 = 0; x25 = 2;
            x36 = 2; x43 = 2; x46 = 1; x56 = 2.