Giáo trình Toán kinh tế (Phần 2) - Học viện Bưu chính viến thông

Nội dung text: Giáo trình Toán kinh tế (Phần 2) - Học viện Bưu chính viến thông

1. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Ax = b, bt = -bs. bi = 0, i s, t , 0 ≤ xij ≤ uij, (i, j) A Giá trị của bs sẽ gọi là giá trị của dòng chấp nhận được tương ứng. Bài toán luồng lớn nhất có thể đưa về bài toán dòng trên mạng bằng cách sau. Trước hết, ta phải đưa vào các cij. Ta đặt cij = 0 (i, j) A . Ta vẽ thêm cung mới (t, s) với uts = +∞ và cts = - 1. Tìm cực tiểu hàm mục tiêu cijx ij  - x ts ở bài toán dòng trên mạng mới được đặt, do đó, chính là dòng chấp nhận được sao (i, j) cho xts là lớn nhất. Nhưng vì bài toán mới đặt không có nguồn và đích nên toàn bộ dòng này phải đi qua mạng để từ s quay lại t. Vậy xts chính là giá trị nghiệm của bài toán luồng lớn nhất. Ngược lại, việc tìm dòng chấp nhận được của bài toán dòng trên mạng có tải năng hạn chế có thể đưa về giải bài toán luồng lớn nhất như sau. Trước hết ta bỏ các hệ số cij đi và đưa thêm vào nút nguồn s và nút đích t. Ta vẽ thêm cung (s, j) tới mỗi đỉnh j có bi > 0 và đặt tải năng của nó là usj = bj và cung (i, t) từ mỗi nút t có bi < 0 và đặt uti = -bi. Vì ∑bk = 0 ta có ∑usj = ∑uit := w. Bây giờ ta đưa vào khái niệm cắt, dùng đến nhiều cho bài toán luồng lớn nhất. Một tập con S của tập các đỉnh X được gọi là một cắt hoặc cụ thể hơn, (s.t) cắt của bài toán luồng (dòng) lớn nhất nếu s S và t S. Dung lượng C(S) của cắt S là tổng tải năng của các cung đi từ S ra ngoài phần bù của S, tức là các cung có đuôi thuộc S, đầu không thuộc S. Vậy: CS  uij (i,j) A:i S,j S Mỗi dòng đi từ s đến t có thể tách thành hai phần là tổng các dòng trên các cung ra khỏi S trừ đi tổng các dòng trên các cung quay ngược lại S. Tức là mỗi véc tơ dòng x có giá trị v (chính là dòng từ s đến t): v  x jk -  x ij (4.4) j S,k S i S, j S Nói riêng, nếu lấy S = {s} thì v =  xsk hoặc S = X\{s} thì v =  x jt , vì ta luôn giả thiết là trong k s j t mạng không có cung dạng (t,j), tức là cung ra khỏi điểm hút. từ (4.4) ta thấy ngay là giá trị của mọi dòng chấp nhận được (từ sPTIT đến t) phải thỏa mãn: v ≤ C(S) (4.5) với mọi cắt S. Vậy dung lượng của bất kỳ cắt nào cũng là một "cổ chai" mà dòng cực đại không thể vượt quá được. Bây giờ quay lại bài toán luồng lớn nhất ta vừa lập từ bài toán dòng trên mạng. Rõ ràng giá trị w = ∑usj = ∑uit là dung lượng của cắt gồm chỉ có đỉnh s (và cũng là dung lượng của cắt gồm mọi đỉnh, chỉ trừ đỉnh t). Do đó theo (4.5) mọi dòng chấp nhận được của bài toán luồng lớn nhất đang xét đều có giá trị không vượt quá w. Cụ thể hơn là đối với dòng x chấp nhận được của bài toán luồng lớn nhất này thì 3 khẳng định sau là tương đương: - Giá trị của x là w. - xsj = usj với mọi cung (s,j). - xit = uit với mọi cung (i,t). 129
2. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Dễ thấy dòng chấp nhận được của bài toán luồng lớn nhất (mà có giá trị w) luôn là dòng chấp nhận được của bài toán dòng chấp nhận được ban đầu (vì ở các điểm nguồn và điểm đích luật bảo toàn dòng được thỏa mãn, còn ở các đỉnh khác thì sự bảo toàn dòng ở hai bài toán là như nhau). Ngược lại, mỗi dòng chấp nhận được của bài toán dòng trên mạng phải thỏa xsj = usj theo sự bảo toàn dòng ở các điểm nguồn (vì usj = bsj), nên phải là dòng chấp nhận được với giá trị w của bài toán luồng lớn nhất tương ứng. Định lý 4.3 Đối với bài toán luồng lớn nhất đúng một trong hai trường hợp sau sẽ xảy ra: - Có dòng chấp nhận được với giá trị lớn tùy ý và mọi cắt đều có dung lượng vô hạn. - Tồn tại luồng lớn nhất và giá trị của nó là cực tiểu của dung lượng của tất cả các cắt. Bài toán tìm luồng lớn nhất trên một mạng có nhiều điểm nguồn và nhiều điểm đích có thể dễ dàng quy về bài toán luồng lớn nhất trên mạng chỉ có một điểm nguồn và một điểm đích bằng cách thêm vào các đỉnh giả và cung giả thích hợp như hình 4.7a, b y1 y1 x1 x1 ∞ ∞ y2 x0 y2 ∞ y0 x 2 ∞ ∞ x y3 2 a) y3 b) Hình 4.7 4.4.2 Thuật toán Ford - Fulkerson a. Ý tưởng của thuật toán. Xuất phát từ luồng không (xij = 0  (i,j)). Tiếp đó, tìm một đường đi từ đỉnh nguồn xs đến đỉnh đích xt (xs và xt xác định trước) sao cho trên cạnh có vận chuyển theo chiều thuận (từ điểm nguồn tới điểm hút) thì lượng hàng vận chuyển chưa đạt tới khả năng thông qua của cung có dung lượng nhỏ nhất. Nếu không có đường đi nào như thế thì luồng hiện có là luồng lớn nhất, còn nếu phát hiện có đường đi như thế thì điều chỉnh luồng hiện có như sau: thêm một lượng hàng h vào mỗi cung chưa vận chuyển hoặc cóPTIT vận chuyển hàng theo chiều thuận, giảm lượng hàng vận chuyển h trên các cung có vận chuyển hàng theo chiều ngược (từ điển hút về điểm nguồn), với h là giá trị lớn nhất có thể được sao cho luồng sau khi điều chỉnh vẫn còn phù hợp với khả năng thông qua của mạng, nghĩa là 0 ≤ xij ≤ uij. Mỗi lần điều chỉnh như vậy ta sẽ vận chuyển thêm được h đơn vị hàng từ điểm nguồn tới điểm hút. Sau khi điều chỉnh ta kiểm tra xem có đường đi nào từ điểm nguồn đến điểm đích có tính chất trên không, nếu không thì thuật toán dừng. Nếu có thì điều chỉnh luồng như trên. Quá trình tiếp tục sau một số hữu hạn bước ta sẽ thu được luồng lớn nhất. b. Lược đồ thuật toán: Bước 0: Xuất phát từ luồng 0 (chưa vận chuyển xij = 0 trên mọi cung), ta lần lượt gán cho các đỉnh của đồ thị một cặp số, gọi là nhãn, như sau: gán cho đỉnh nguồn (đỉnh x0) nhãn (∞,0). Mỗi đỉnh trong quá trình thực hiện thuật toán sẽ ở một trong ba trạng thái: chưa có nhãn, có nhãn chưa xét và có nhãn đã xét. Nhãn của đỉnh gồm hai phần và có một trong hai dạng sau: [(ei,pi)] hoặc [(ei,-pi)] 130
3. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Phần thứ nhất chỉ ra lượng lớn nhất có thể tăng hoặc giảm luồng theo cung này, còn phần thứ hai chỉ ra cần tăng hay giảm luồng theo cung (i,j) hay (j,i). Đầu tiên chỉ có đỉnh xs được khởi tạo nhãn và nhãn của nó là chưa xét, các đỉnh còn lại đều chưa có nhãn. Từ xs ta gán nhãn cho các đỉnh kề với nó và nhãn của đỉnh xs trở thành đã xét Bước 1: Gọi N1 là tập các đỉnh i (i ≠ s) của mạng nối trực tiếp với đỉnh nguồn bởi một cung mà lượng hàng vận chuyển từ đỉnh nguồn trên đó chưa vượt quá khả năng thông qua. tiếp sau đó ta gán cho đỉnh i thuộc N1 một cặp số (ei,pi) gọi là nhãn, như sau: ei = u1i - x1i = khả năng thông qua còn lại trên cung (0,i) pi = 0 = Số hiệu của đỉnh nguồn đến đỉnh i. Nếu N1 chứa đỉnh nguồn (hút) xt thì chuyển sang thức hiện bước 5 để tăng giá trị của luồng. Trái lại chuyển sang bước 2. Bước 2: Ký hiệu N2 là tập hợp tất cả các đỉnh j chưa được gán nhãn của đồ thị sao cho đỉnh này được nối với một đỉnh đã được gán nhãn thuộc tập N1, chẳng hạn đỉnh i, bởi cung (i,j) với xij 0. tiếp theo, ta gán cho mỗi đỉnh j một cặp số (ej,pj) gọi là nhãn, theo công thức sau: min(ei ; uij - xij ) nếu xij 0 min(ei , uij ) ij pj = i. Chuyển sang bước 3 Bước 3: Lặp lại bước 2 với Nt thay cho Nt-1. Sau một số hữu hạn bước ta gặp một trong hai tình huống sau: 3a. Nhãn của tất cả các đỉnh có nhãn đã xét nhưng đỉnh xt vẫn không có nhẫn. Thuật toán dừng. Luồng hiện có là lớn nhất.(Không tồn tại đường tăng luồng) 3b. Đỉnh xt đã được gán nhãn. Chuyển sang bước 4. Bước 4: Tăng luồng hiện có như sau: Giả sử đỉnh đích (điểm hút) (xt) đã được gán nhãn (et,pt), et chỉ rõ lượng hàng sẽ vận chuyển thêm từ nguồn đến đích, số thứ hai (pt) cho biết đỉnh đã được dùng để gán nhãn cho đỉnh đích. Dựa vào số thứ hai trong nhãn của đỉnh đích ta tìm được đỉnh trước đó,v.v cứ thế ta lần ngược lại đỉnh nguồn. Kết quả là xác định được đường đi từ nguồn tới đích làm tăng giá trị luồng. Cách điều chỉnh luồng như sau: - Nếu cạnh (i,j) không thuộc đường đi trên thì luồng giữ nguyên. - Nếu cạnh (i,j) thuộc đường đi này và thuận chiều thì khi đó trên cạnh này xij 0, ta đặt: ' x ij = xij - et . Chuyển sang bước 5. Bước 5: Xóa nhãn của mọi đỉnh, trừ đỉnh nguồn rồi quay lại bước 1. Đối với luồng mới thu được ta lại sử dụng phép gán nhãn các đỉnh để tìm đường đi tăng.Thuật toán sẽ kết thúc sau một số hữu hạn bước, nghĩa là sau một số hữu hạn lần áp dụng các bước từ 1 đến 5 ta sẽ gặp trường hợp 3a.(trong mạng không tìm được đường đi tăng) Thí dụ 4.7: Cho đồ thị như ở hình 4.8. số ghi trên mỗi cung là khả năng thông qua của cung. Đỉnh 1 là đỉnh nguồn, đỉnh 7 là điểm hút. 131
4. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng 2 2 4 3 ` 2 6 7 1 3 5 1 1 1 3 3 3 6 2 Hình 4.8 Giải: Xuất phát từ luồng 0. Đỉnh nguồn được gán nhãn (∞, 0). Ở bước lặp đầu tiên ta gán cho đỉnh 2 nhãn: e2 = u12 = 6; p2 = 1. Gán cho đỉnh 3 nhãn: e3 = u13 = 3; p3 = 1 Tiếp đó dựa vào các đỉnh đã được gán nhãn 2 và 3, ta gán cho đỉnh 4 nhãn: e4 = min(e2, u24) = min(6, 2) = 2; p4 = 2. Gán cho đỉnh 5 nhãn: e5 = min(e3, u35)= min(3, 1)= 1; p5 = 3. Gán cho đỉnh 6 nhãn: e6 = min(e3,u36) = min(3, 2) = 2; p6 = 3. Gán cho đỉnh 7 nhãn: e7 = min(e4, u47) = min(2, 3) = 2; p7 = 4. Đỉnh 7 là điểm hút được gán nhãn. Ta vận chuyển e7 = 2 đơn vị hàng theo đường 1-2-4- 7 (x12 = x24 = x47 = 2, các đỉnh khác xij = 0), giá trị luồng tương ứng là 2. Ở vòng lặp tiếp theo, ta gán cho đỉnh 2 nhãn: e2 = u12 - x12 = 6 -2 = 4, p2 = 1. Gán cho đỉnh 3 nhãn e3 = u13 = 3, p3 = 1. Tiếp đó gán cho đỉnh 5 nhãn: e5 = min(e3, u35) = min(3, 1) = 1, p5 = 3. Gán cho đỉnh 6 nhãn e6 = min(e3,u36) = min(3, 2) = 2, p6 = 3. Lúc này đỉnh 4 không được gán nhãn vì cung (2,4) đã vận chuyển hết khả năng thông qua. Cuối cùng dựa vào các đỉnh đã được gán nhãn 5 và 6 ta gán cho đỉnh 7 nhãn e7 = min(e5, u57) = min(1,1) = 1. p7 = 5. Đỉnh 7 là đỉnh hút đã được gán nhãn. Ta vận chuyển e7 = 1 đơn vị hàng theo đường 1-3-5-7 (x13 = x35 = x57 = 1, các xij khác không đổi). Giá trị luồng bây giờ là 2 + 1 = 3. Ở vòng lặp thứ ba, ta gán cho đỉnh 2 nhãn: e2 = u12 - x12 = 6 -2 = 4, p2 = 1. Gán cho đỉnh 3 nhãn: e3 = u13 - x13 = 3 - 1 = 2, p3 = 1. Tiếp theo gán cho đỉnh 6 nhãn: e6 = min(e3, u36) = min(2, 2) = 2, p6 = 3. Lúc này đỉnh 4, 5 khôngPTIT được gán nhãn. từ đỉnh 6 ta gán cho đỉnh 7 nhãn: e7 = min(e6,u67) = min(2, 3) = 2, p7 = 6. Kết quả ta vận chuyển thêm được e7 = 2 đơn vị hàng theo đường 1-3-6-7(x13 = x36 = x67 = 2, các xij khác không đổi). Giá trị của luồng bây giờ là 3 + 2 = 5. Để kiểm tra luồng hiện có đã lớn nhất hay chưa, ta tiếp tục quá trình gán nhãn: ta gán cho đỉnh 2 nhãn: e2 = u12 - x12 = 4, p2 = 1. Gán cho đỉnh 3 nhãn: e3 = min(e2, u23) = min(4, 3) = 3, p3 = 2. Đến đây đỉnh 7 chưa được gán nhãn nhưng ta không thể gán nhãn cho đỉnh nào nữa (tình huống 3a). Vậy luồng hiện có là lớn nhất. Đó là: x12 = 2, x13 = 3, x24 = 2 x35 = 1; x36 = 2, x47 = 2, x57 = 1, x67 = 2. Lượng hàng vận chuyển lớn nhất từ điểm nguồn đến điểm hút là 5 đơn vị. Các lát cắt nhỏ nhất C(S) là (2,4), (3,5) và (3,6). tổng cộng khả năng thông qua trên các cung này đúng bằng 5 đơn vị. Thí dụ 4.8: Mạng vận tải gồm 4 nút. Nút nguồn là A, nút đích (điểm hút) là D. Các đường đi tăng được tìm bằng phương pháp tìm kiếm theo chiều sâu, trong đó các đỉnh lân cận được duyệt theo 132
5. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng thứ tự bảng chữ cái. Thí dụ nà cho thấy biểu hiện của trường hợp xấu nhất của thuật toán. Mỗi bước chỉ gửi thêm được một luồng có giá trị bằng 1. B B 0/1000 0/1000 1/1000 0/1000 A 0/1000 D A 1/1000 D 0/1000 0/1000 0/1000 1/1000 CA C B B 1/1000 1/1000 1/1000 1/1000 A 0/1000 D A 0/1000 D 1/1000 1/1000 1/1000 1/1000 C C Thuật toán đánh dấu: Nếu tồn tại một đường đi từ nguồn đến đích với điều kiện tất cả các cung trên đường đi đó vẫn còn khả năng thông qua thì ta sẽ gửi đi một luồng dọc theo đường đi đó. Sau đó ta tìm một đường đi khác và tiếp tục như vậy. Một đường đi còn khả năng thông qua là một đường đi có khả năng mở rộng thêm hay một đường đi mà luồng qua đó còn khả năng tăng thêm - gọi tắt là đường tăng. Cho đồ thị G = {X.A}, với khả năng thông qua uij và luồng f(i,j) = 0 trên các cung từ i đến j. Ta muốn tìm luồng cực đại từ nút nguồn s đến đến điểm hút t. Sau mỗi bước các điều kiện sau đây được duy trì: - f(i,j) ≤ c(i,j): Luồng từ i đến j không vượt quá khả năng thông qua. - f(i,j) = - f(j,i): Cân bằng luồng - f(i,j) = 0 cho tất cả các nút ngoại trừ s và t. Lượng vào nút bằng lượng ra khỏi nút. X Điều này có nghĩa là một luồng đi qua một mạng là một luồng hợp lệ sau mỗi vòng của thuật toán. Chúng ta định nghĩa mạng cònPTIT dư Gt = {X, At} là mạng với sức chứa ut(i,j) = uij - f(i,j) và luồng bằng 0. Chú ý rằng không chắc chắn là A = At bởi vì việc gửi luồng theo cung (i,j) (làm nó bảo hòa), nhưng lại mở một cung mới (j,i) trong mạng còn dư. Đầu vào: Đồ thị G với khả năng thông qua u. Nút nguồn s và nút đích t. Đầu ra: Luồng f sao cho f là cực đại từ s đến t. - f(i,j) ← 0 trên tất cả các cung (i,j). - Trong khi còn có một đường đi từ s đến t trong Gt: Tìm một đường đị x1, x2, , xk với x1 s, xk t: ut(xt,xt+1) > 0 Tìm m = Min{ut(xt,xt+1)}. f(xi, xi+1) ← f(xi, xi+1) + m: Gửi luồng dọc theo đường đi.(chiều thuận) f(xi+1, xi,) ← f(xi+1, xi,) - m: Luồng có thể "quay lại" sau.(Chiều ngược) Khái niệm mạng còn dư: Thể hiện lượng khả năng thông qua hiện có.Để ý rằng có thể có một cung từ i đến j trong mạng còn dư, ngay cả khi không có cung từ i đến j trong mạng ban đầu. Do 133
6. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng các luồng theo các hướng ngược nhau triệt tiêu lẫn nhau. Giảm luồng từ j đến i tương đương với tăng luồng từ i đến j. Khái niệm đường đi tăng: là một đường đi từ x1, x2, , xk trong đó x1 s và xk t và ut(xi,xi+1) > 0. Nghĩa là có thể gửi thêm luồng dọc theo đường đi này. 4. 5. Bài toán luồng nhỏ nhất 4.5.1 Bài toán Cho một đồ thị đối xứng có n đỉnh, mỗi cạnh có khả năng thông qua nhất định và có một cước phí vận chuyển xác định (như nhau theo cả hai chiều). Cho trước một lượng S cần phải vận chuyển từ đỉnh nguồn (đỉnh số 1) tới điểm hút (số n). Hãy tìm một phương án vận chuyển sao cho phù hợp với khả năng thông qua của mạng và vận chuyển được lượng hàng S từ nguồn đến điểm hút với tổng chi phí vận chuyển là nhỏ nhất. Đây là bài toán vận tải hạn chế khả năng thông qua. Tuy bài toán có một đỉnh nguồn và một điểm hút, như bất kỳ bài toán vận tải trên mạng có nhiều nguồn và nhiều điểm hút có thể quy về bài toán dạng trên bằng cách thêm vào các đỉnh giả và cung giả thích hợp như đã trình bày trong bài toán luồng lớn nhất. Về mặt toán học, bài toán luồng chi phí nhỏ nhất có thể phát biểu như sau: Cực tiểu hàm chi phí cijx ij với các điều kiện của bài toán: i, j A S , nếu i = 1 , nếu i ≠ 1, i ≠ n  x ji -  x ij 0 i i - S , nếu i = n Ở đây đỉnh nguồn được đánh số 1, đích đánh số n, cij là chi phí vận chuyển một đơn vị hàng trên cạnh (i, j), uij là khả năng thông qua của cạnh (i, j), xij là khối lượng hàng vận chuyển trên cạnh (i, j) và là biến cần xác định. 4.5.2 Phương pháp giải: Luồng chi phí nhỏ nhất có thể giải bằng thuật toán đơn giản như sau: Xuất phát từ phương án vận chuyển không (xij = 0 trên mọi cạnh của đồ thị). Ở mỗi bước lặp, ta tìm đường đi có chi phí nhỏ nhất từ nguồn đến điểm hút. Đườ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 thuận thì lượng hàng vận chuyển chưa vượt quá khả năng thông qua của cạnh đó. TrPTITên đường đi này, cạnh chưa 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 là số dương, còn trên cạnh vận chuyển hàng theo chiều ngược thì chi phí vận chuyển 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 âm. Thêm khả năng thông qua này vào các cạnh chưa 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 sang bước lặp sau. Quá trình tiếp tục cho đến khi vận chuyển hết lượng hàng S từ nguồn đến điểm hút 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 đến điểm hút. Chú ý: Ở 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 đến điểm hút trên mạng với cước phí có thể là số âm. Thí dụ 4.9 Cho đồ thị vô hướng như hình 4.9. Mỗi cạnh tương ứng với một cặp số thứ tự mà số thứ nhất là chi phí vận chuyển một đơn vị hàng trên cạnh, số thứ hai là khả năng thông qua của 134
7. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng cạnh này. Đỉnh nguồn là đỉnh 1, điểm hút là 6. Tổng khối lượng hàng cần vận chuyển từ đỉnh nguồn đến điểm hút là 5 đơn vị. 4 (4,1) (3,4) (2,4) 6 1 (1,2) 3 (1,2) (1,4) (6,2) (5,2) 2 5 Hình 4.9 Giải: Ở 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 đó, tìm đường đi có chi phí nhỏ nhất từ đỉnh nguồn đến điểm hút, đó 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 hai đơn vị hàng từ đỉnh nguồn đến điểm hút theo đường đi vừa tìm được. Ở bước lặp tiếp theo, đường đi có chi phí nhỏ nhất từ đỉnh nguồn đến điểm hút là 1 - 4- 6, với chi phí vận chuyển bằng 7 và khả năng thông qua bằng 1 bằng khả năng của cạnh (4,6). Ta vận chuyển thêm được 1 đơn vị hàng từ đỉnh nguồn tới điểm hút. Ở bước lặp thứ 3, đường đi có chi phí nhỏ nhất từ đỉnh nguồn tới điểm hút là 1 - 4 - 3 - 2 - 5 - 6. Trên đường đi này có 3 cạnh chưa vận chuyển, đó là (3,4), (2,5), (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 hàng theo chiều ngược là (2,3). Vì thế, chi phí 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 đi này bằng: Min(4-1, 4-0, 2, 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). Kết quả ta vận chuyển được 5 đơn vị hàng từ đỉnh nguồn tới điểm hút, với tổng chi phí bằng: PTIT 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 Thuật toán đánh dấu: Cho mạng (G,u) trong đó G = {X.A}, u là năng lực thông qua trên mỗi cạnh. Tìm luồng t qua mạng với giá trị tz nhỏ nhất và thỏa mãn điều kiện:  (i,j) A, t(i,j) ≥ u(i,j) Xuất phát từ một luồng t nào đó thỏa mãn điều kiện trên, ta dùng phương pháp sau đây để giảm giá trị của luồng t. Bước 1: Đánh dấu các đỉnh. Đầu tiên đánh dấu cho đỉnh đích (z) số 0. Nếu đỉnh j đã được đánh dấu, có cạnh (i,j) với đỉnh đầu chưa được đánh dấu và t(i,j) > u(i,j) thì đánh dấu cho đỉnh i là +j. Nếu đỉnh i đã được đánh dấu, có cạnh (i,j) thì đánh dấu cho đỉnh j là -i. 135
8. Bài giảngToán kinh tế Chương 4: Mô hình bài toán tối ưu trên mạng Với cách đánh dấu này mà đi tới được đỉnh nguồn (x0) thì ta đã tìm được một đường đi vô hướng từ z tới x0 được đánh dấu. Bước 2: Giảm luồng Bây giờ ta có thể giảm luồng đi 1 bằng cách chọn luồng mới t' như sau: Nếu cạnh (i,j) không thuộc đường đi trên thì giữ nguyên luồng, nghĩa là: t'(i,j) = t(i,j) ' Nếu cạnh (i,j) thuộc đường đi này và cùng chiều với chiều từ x0 đến z thì đặt: t(i,j) = t(i,j) - 1 (vì trên cạnh đó t(i,j) > u(i,j)), còn nếu cạnh (i,j) ngược chiều thì đặt t'(i,j) = t(i,j) + 1. Lặp lại quá trình giảm luồng trên cho đến khi không đánh dấu được tới đỉnh nguồn x0. Khi đó ta nhận được luồng có giá trị nhỏ nhất, Thí dụ 4.10: Xét mạng vận tải: 5/5 +0 x x 1 3 6-5/5 0 4/3 z 9/8 3-4/3 +2 +4 4/3 +3 13/13 x0 x2 x4 10-9/8 6-5/5 Luồng hiện có có giá trị là tz = 19. Luồng mới sau khi cải tiến có giá trị là tz' = 18 là luồng nhỏ nhất. 4.6 Phương pháp sơ đồ mạng lưới (Pert) 4.6.1 Một số khái niệm và quy tắc lập sơ đồ mạng lưới a. Định nghĩa: Định nghĩa 1: Một tập hợp các điểm (ta gọi là các đỉnh, ký hiệu là X) và tập hợp các cung (ký hiệu là A) được gọi là sơ đồ mạng lưới nếu chúng thỏa mãn các điều kiện sau: - Giữa 2 đỉnh có không quá một cung nối liền và ngược lại mỗi cung phải liên kết 2 đỉnh nào đó với nhau. i j Cung nối từ đỉnh i đến đỉnh j được ký hiệu là (i, j), trong đó i là điểm gốc của cung và j là điểm ngọn của cung. PTIT - Điểm gốc và điểm ngọn của mỗi cung không trùng nhau. - Trong một dãy các cung nối tiếp nhau (tức là điểm ngọn của mỗi cung là điểm gốc của cung tiếp theo) thì không bao giờ điểm ngọn của cung cuối cùng trùng với điểm gốc của cung đầu tiên. Một dãy như vậy được gọi là một đường đi trong sơ đồ mạng lưới. - Giữa 2 đỉnh tùy ý bao giờ cũng có một dãy các cung nối liền. - Có một đỉnh chỉ toàn cung đi ra gọi là đỉnh khởi công toàn bộ và có một đỉnh chỉ toàn cung đi tới gọi là đỉnh kết thúc toàn bộ. Các đỉnh còn lại có cả cung đi ra lẫn cung đi tới gọi là đỉnh trung gian. Định nghĩa 2: Ứng với mỗi cung (i, j) có một số tij đặc trưng cho cung đó về mặt lượng được gọi là độ dài hay thời hạn của cung đó. Định nghĩa 3: Độ dài đường đi μ trong sơ đồ mạng lưới là tổng độ dài của tất cả các cung thuộc đường đi đó, ký hiệu là l(μ). Theo định nghĩa thì: 136