Tiểu luận: Lý thuyết đối ngẫu

Chia sẻ: VAN DE JONE | Ngày: | Loại File: DOC | Số trang:19

Thêm vào BST

Báo xấu

143
lượt xem 23
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tiểu luận: Lý thuyết đối ngẫu nhằm phân tích tổng quan các vấn đề liên quan đến đề tài luận án như thuật toán đường đi ngắn nhất, thuật toán Bellmen - Ford,...và phương pháp nghiên cứu, kết quả dự kiến và phương hướng phát triển của đề tài.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tiểu luận: Lý thuyết đối ngẫu

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG TIỂU LUẬN LÝ THUYẾT ĐỐI NGẪU Học phần: Tối ưu hóa Chuyên ngành: Khoa học máy tính Mã sô: 62.48.01.01 ́ Khóa học: 2011 - 2015 NCS. Trần Ngọc Việt Người hướng dẫn: PGS.TSKH. Trần Quốc Chiến PGS.TS. Lê Mạnh Thạnh ĐÀ NẴNG – 2012 1
MỤC LỤC MỞ ĐẦU ……………………………………………………………… 2 Chương 1. PHÂN TÍCH TỔNG QUAN CÁC VẤN ĐỀ LIÊN QUAN ĐẾN ĐỀ TÀI LUẬN ÁN 1. Tổng quan về các công trình trong nước liên quan đến đề tài luận án …………………………………………………….. 3 1.1. Công trình về thuật toán tìm đường đi ngắn nhất ……….. 3 1.1.1. Thuật toán đường đi ngắn nhất xuất phát từ một đỉnh .. 5 1.1.2. Thuật toán đường đi ngắn nhất trong k cặp đỉnh nguồn đích ……………………………………………….. 6 1.2. Thuật toán Bellman – Ford …………………………….. 8 1.3. Thuật toán Floyd-Warshall ……………………………. . 9 1.4. Công trình về thuật toán luồng cực đại …………………. 10 1.5. Bài toán luồng đa phương tiện cực đại …………………. 14 1.6. Bài toán luồng đa phương tiện cực đại đồng thời ………. 19 1.7. Bài toán luồng đa phương tiện cực đại đồng thời có ràng buộc chi phí …………………………………………….. 23 2. Tổng quan về các công trình đã nghiên cứu trên thế giới …. 27 3. Một số ứng dụng lớn trên thế giới ………………………. 28 4. Danh mục các công trình liên quan ………………………. 29 Chương 2. PHƯƠNG PHÁP NGHIÊN CỨU, KẾT QUẢ DỰ KIẾN VÀ HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI …………. 31 KẾT LUẬN ………………………………………………………… 33 TÀI LIỆU THAM KHẢO …………………………………………. 34 2
Chương 1. LÝ THUYẾT ĐỐI NGẪU 1.1. Khái niệm về đối ngẫu Đối ngẫu là một khái niệm cơ bản của việc giải bài toán quy ho ạch tuyến tính vì lý thuyết đối ngẫu dẫn đến một kết quả có tầm quan trọng v ề mặt lý thuyết và cả mặt thực hành. 1.2. Phát biểu bài toán đối ngẫu Tương ứng với mỗi bài toán Quy hoạch tuyến tính (còn gọi là bài toán gốc) có một bài toán đối ngẫu. Bài toán đối ngẫu của bài toán QHTT cũng là một bài toán QHTT. Như vậy, bài toán gốc và bài toán đối ngẫu của nó lập thành một cặp bài toán QHTT, tính chất của bài toán này có th ể được kh ảo sát thông qua bài toán kia. Nhiều quy trình tính toán hay phân tích đ ược hoàn thi ện khi xem xét cặp bài toán trên trong mối liên quan ch ặt ch ẽ của chúng, mang l ại lợi ích trong việc giải quyết các vấn đề phát sinh từ th ực tế. Với m ục đích tìm hiểu bước đầu, chúng ta xét bài toán gốc là bài toán quy hoạch tuyến tính dạng Max với các ràng buộc chỉ có dấu ≤ và các biến đều thoả mãn điều kiện không âm. Bài toán gốc max f ( x) = c1 x1 + c2 x2 + ... + cn xn với các điều kiện ràng buộc  a11 x1 + a12 x2 + ... + a1n xn ≤ b1  a x + a x + ... + a x ≤ b  21 1  22 2 2n n 2  ... a x + a x + ... + a x ≤ b  m1 1 m2 2 mn n m   x1 , x2 ,..., xn ≥ 0 3
Lúc đó bài toán QHTT sau đây được gọi là bài toán đối ngẫu của bài toán QHTT trên. Bài toán đối ngẫu min g ( y ) = b1 y1 + b2 y 2 + ... + bm y m với các điều kiện ràng buộc:  a11 y1 + a21 y 2 + ... + am1 y m ≥ c1 a y + a y + ... + a y ≥ c  12 1  22 2 m2 m 2  ... a y + a y + ... + a y ≥ c  1n 1 2n 2 mn m n   y1 , y 2 ,..., y m ≥ 0 Các biến y1 , y 2 ,..., y m được gọi là các biến đối ngẫu. Trong trường hợp này, do bài toán gốc có m ràng buộc, nên bài toán đối ngẫu có m bi ến đối ng ẫu. Biến đối ngẫu yi tương ứng với ràng buộc thứ i của bài toán gốc. Trong trường hợp quy hoạch tuyến tính tổng quát, những quy tắc sau đây được áp dụng để xây dựng bài toán đối ngẫu : - Hàm mục tiêu đối ngẫu : . max ↔ min - Biến đối ngẫu : . mỗi ràng buộc ↔ một biến đối ngẫu - Chi phí đối ngẫu và giới hạn ràng buộc : . chi phí đối ngẫu ↔ giới hạn ràng buộc - Ma trận ràng buộc đối ngẫu : . ma trận chuyển vị - Chiều của ràng buộc và dấu của biến : . ràng buộc trong bài toán max có dấu ≤ thì biến đối ng ẫu trong bài toán min có dấu ≥ 0 ( trái chiều ) 4
. ràng buộc trong bài toán max có dấu = thì biến đối ng ẫu trong bài toán min có dấu tùy ý. . ràng buộc trong bài toán max có dấu ≥ thì biến đối ng ẫu trong bài toán min có dấu ≤ 0 ( trái chiều ) . biến của bài toán max có dấu ≥ 0 thì ràng buộc đối ngẫu trong bài toán min có dấu ≥ ( cùng chiều ) . biến của bài toán max có dấu tùy ý thì ràng buộc đ ối ng ẫu trong bài toán min có dấu = . biến của bài toán max có dấu ≤ 0 thì ràng buộc trong bài toán đối ngẫu min có dấu ≤ ( cùng chiều ) 1.3. Định lý độ lệch bù Giả sử x* và y* là các phương án tối ưu của cặp bài toán đối ngẫu. Lúc đó (x*, y*) thoả mãn hệ:  y T ( Ax − b) = 0  T  x (c − A y ) = 0 T Chứng minh Với x = x* , y = y * ⇒ f ( x) = g ( y ) hay y T b = bT y = cT x = xT c. Mặt khác, y T Ax = xT AT y ⇒ y T ( Ax − b) = xT ( AT y − c) ⇒ y T ( Ax − b) + xT (c − AT y ) = 0  y T ( Ax − b) = 0 ⇒ T  x (c − A y ) = 0 T Chú ý rằng: y T ≥ 0, Ax − b ≤ 0, x T ≥ 0, c − A T y ≤ 0. Vậy, ta có điều phải chứng minh. 1.4. Cơ sở của phương pháp đơn hình đối ngẫu Xét bài toán gốc: min f ( x) = cT x với x ∈ D = {x ∈ R n : Ax ≥ b, x ≥ 0}. Dễ dàng đưa bài toán này về dạng chính tắc: min f ( x) = cT x với các ràng buộc 5
A x = b, x ≥ 0 , trong đó A = [ A − I ], cT = (cT , cT ), x = ( xT , xT )T , với chỉ số s s dưới s dùng để ký hiệu các chỉ số bù. Xét một véc tơ x thỏa mãn A x = b, x ≥ 0 . Bằng cách phân rã A = [ N B ], x = ( x N , x B )T và cho x N = 0, với x B = B b . Các véc tơ cột T T −1 a j , ∀j ∈ J B của B được gọi là: - Cơ sở gốc chấp nhận nếu x B = B −1b ≥ 0 , nhưng không nhất thiết T T c B B −1 A ≤ c - Cơ sở đối ngẫu chấp nhận nếu c T B −1 A ≤ cT , nhưng không nhất thiết B x B = B −1b ≥ 0 Kiểm tra lại các bước của thuật toán đơn hình đối ngẫu. Giả sử, T T x = ( x N , x B )T là một phương án đối ngẫu khả thi, tức là các véc tơ cột T a j , ∀j ∈ J B , là cơ sở đối ngẫu chấp nhận. Nên ∆ j = c j − c B B −1 a j ≥ 0. Nếu xB = B −1b ≥ 0 thì x là phương án tối ưu. Chú ý rằng, thuật toán đơn hình đối ngẫu được bắt đầu với ma trận B ≡ − I , do đó có xB = B −1b = − Ib. Nếu xB = B −1b ≥ 0 chưa được thỏa mãn thì tồn tại xq < 0, q ∈ J B . Lúc đó ta cần thực hiện thủ tục xoay. Trường hợp 1: ∀j ∈ J ( J là tập các chỉ số của các véc tơ cột của ma trận A ), xqj ≥ 0. Điều này có nghĩa là tất cả các tọa độ thứ q của các véc tơ B −1 a j , ∀j ∈ J đều không âm. Ta sẽ chỉ ra rằng bài toán gốc không có phương án, hay bài toán đối ngẫu có hàm mục tiêu không bị chặn trên. Xét véc tơ: T y = (c B B −1 )T . Dễ dàng chứng minh được đây đúng là phương án của bài toán đối ngẫu. Thật vậy, ta có: T A y≤c 6
Đặt U q là véc tơ hàng q trong ma trận B −1 và xét y ' = y − θU q với θ > 0 T T T T nào đó. Thế thì ( y ')T a j = ( y − θU q )a j = y a j − θU q a j ≤ y a j . T T T ' T ' ' Ta có y a j ≤ c j , nên ( y )T a j ≤ c j . Do đó, A y ≤ c hay y cũng là phương án của bài toán đối ngẫu. Mặt khác, giá trị của hàm m ục tiêu trong bài toán đối ngẫu là ' ' T T g ( y ) = ( y )T b = ( y − θU q )b = y b − θU q b = g ( y ) − θ xq → + ∞ T T khi θ → + ∞. Để chứng minh bài toán gốc không có phương án có thể lập luận ngắn gọn hơn. Thật vậy, ta có ∑ xqj x j = x j < 0 (do B −1 A x = B −1b) . j∈ J Nếu bài toán gốc có phương án với các tọa độ không âm thì đây là điều vô lý vì: xqj , x j ≥ 0, ∀j ∈ J . Trường hợp 2: ∃j ∈ J : xqj ≥ 0. Ta chọn cột xoay theo “qui tắc tỷ số âm lớn nhất”, tức là chọn chỉ số s sao cho: ∆s ∆ j    = min   xqs x qj < 0  xqj    Tiếp tục thực hiện thủ tục xoay trong bài toán đơn hình đối ngẫu, ta sẽ chuyển được sang phương án đối ngẫu khả thi mới. Trong phương án mới xs sẽ là biến cơ sở thay chỗ cho biến xq . Vì mỗi phương án đối ngẫu khả thi tìm được trong quá trình giải tương ứng với một ma trận cơ sở B trong một phân rã nào đó A = [N B], nên s ố ph ương án đối ngẫu khả thi được xem xét là một số hữu hạn. Do đó, sau một số h ữu 7
hạn bước, ta sẽ kết thúc việc giải bài toán QHTT bằng phương pháp đơn hình đối ngẫu. 1.5. Thuật toán đơn hình đối ngẫu Thuật toán đơn hình đối ngẫu được xây dựng dựa trên tính chất của cặp bài toán đối ngẫu. Thuật toán của phương pháp đơn hình đối ngẫu được phát bi ểu cho bài toán QHTT: min f ( x) = c T x , với x ∈ D = {x ∈ R n : Ax = b, x ≥ 0}. Bước khởi tạo -Tìm một phương án đối ngẫu khả thi x = B −1b tương ứng với ma trận cơ sở B trong một phân rã nào đó A = [ N B ] : điều kiện x j ≥ 0, ∀j có thể không được thỏa mãn nhưng luôn có ∆ j ≥ 0, ∀j. -Tính: ∆ j = c j − f j , ∀j = 1, n trong đó n là số biến của bài toán đang xét. Các bước lặp Bước 1: Kiểm tra điều kiện tối ưu. Nếu điều kiện tối ưu x j ≥ 0, ∀j = 1, n đã được thỏa mãn thì in / lưu kết quả của bài toán và dừng. Bước 2: Nếu tồn tại một chỉ số j sao cho x j < 0 thì tiến hành thủ tục xoay gồm nhiều bước tương tự theo thủ tục xoay của phương pháp đơn hình với các khác biệt sau: - Trước tiên chọn hàng xoay là hàng với biến x j có giá trị âm (thông thường với trị tuyệt đối lớn nhất, hoặc chọn ngẫu nhiên). - Sau đó chọn cột xoay theo quy tắc tỷ số âm lớn nh ất (các t ỷ s ố đ ược tạo ra bằng cách lấy hàng ∆ j chia cho hàng x j và chỉ xét các tỷ số có mẫu số âm). Nếu không tìm được cột xoay thì kết luận bài toán không có phương án kh ả thi, in / lưu kết quả của bài toán và chuyển sang bước kết thúc. 8
- Nếu tìm được cột xoay thì thực hiện các bước tiếp theo của thủ tục xoay. -Tính lại các ∆ j , ∀j = 1, n và quay lại bước 1. -Việc thực hiện giải bài toán gốc bằng phương pháp đơn hình đối ngẫu thực chất là việc giải bài toán đối ngẫu bằng phương pháp đơn hình. Điều này cũng giải thích lí do tại sao khi thực hiện thủ tục xoay của phương pháp đơn hình đối ngẫu cần trước hết xác định hàng xoay rồi sau đó mới xác đ ịnh c ột xoay. Ví dụ: Xét cặp bài toán đối ngẫu Bài toán gốc min f ( x) = 3 x1 + 2 x2 với các ràng buộc  x1 + 2 x2 ≥ 4  x +x ≥3  1 2  2 x1 + x2 ≥ 4  x1 , x2 ≥ 0  Nếu giải trực tiếp bài toán trên bằng phương pháp đơn hình, thì cần đ ưa bài toán về dạng chính tắc với 8 biến (thêm ba biến bù “th ừa” và ba bi ến gi ả). Một phương pháp khác như đã biết là, trước hết tìm cách gi ải bài toán đ ối ngẫu (chỉ với 5 biến), sau đó sẽ tìm được phương án tối ưu của bài toán gốc. Bài toán đối ngẫu max g ( y ) = 4 y1 + 3 y2 + 4 y3 với các ràng buộc  y1 + y2 + 2 y3 ≤ 3  2 y1 + y2 + y3 ≤ 2  y ,y ,y ≥0  1 2 3 9
Viết bài toán đối ngẫu dưới dạng chính tắc: max g ( y ) = 4 y1 + 3 y2 + 4 y3 + 0 y4 + 0 y5 với các ràng buộc  y1 + y2 + 2 y3 + y4 = 3  2 y1 + y2 + y3 + y5 = 2  y ,y ,y ,y ,y ≥0  1 2 3 4 5 Cách 1. Giải bài toán đối ngẫu bằng phương pháp đơn hình. Kết quả được cho trong bảng. Theo tính chất của cặp bài toán đối ngẫu, ta có phương án tối ưu của bài toán gốc là x1 = 1, x2 = 2 với f min = 7. * * Hệ số Biến cơ sở P/án c1 = 4 c2 = 3 c3 = 4 c4 = 0 c5 = 0 y1 y2 y3 y4 y5 0 y4 3 1 1 [2] 1 0 0 y5 2 2 1 1 0 1 0 0 0 0 0 0 4 3 4 0 0 4 y3 3/2 ½ ½ 1 ½ 0 0 y5 1/2 [3/2] 1/2 0 -1/2 1 2 2 4 2 0 6 2 1 0 -2 0 4 y3 4/3 0 1/3 1 2/3 -1/3 4 y1 1/3 1 [1/3] 0 -1/3 2/3 4 8/3 4 4/3 4/3 20/3 0 1/3 0 -4/3 -4/3 4 y3 1 -1 0 1 1 -1 3 y2 1 3 1 0 -1 2 5 3 4 1 2 7 -1 0 0 -1 -2 10
Cách 2. Giải bài toán gốc bằng phương pháp đơn hình đối ngẫu. Trước hết đưa Bài toán gốc về dạng sau: min f ( x) = 3 x1 + 2 x2 + 0 x3 + 0 x4 + 0 x5 với các ràng buộc − x1 − 2 x2 + x3 = −4  − x − x + x = −3  1 2 4  − 2 x1 − x2 + x5 = −4  x1 , x2 , x3 , x4 , x5 ≥ 0  Nội dung tóm tắt của phương pháp đơn hình đối ngẫu: Trong phương pháp đơn hình, dịch chuyển dần từ phương án khả thi, tức là x j ≥ 0, ∀j nhưng điều kiện Δ j ≥ 0, ∀j chưa được thoả mãn, tới phương án tối ưu, tức là x j ≥ 0 và Δ j ≥ 0, ∀j. Trong phương pháp đơn hình đối ngẫu, ta dịch chuyển dần từ phương án không khả thi (nhưng đối ngẫu khả thi), tức là điều kiện x j ≥ 0, ∀j không được thoả mãn nhưng luôn có Δ j ≥ 0, ∀j, tới phương án tối ưu, tức là có x j ≥ 0 và Δ j ≥ 0, ∀j. Quy trình giải bài toán gốc dạng chuẩn tắc trên đây bằng phương pháp đơn hình đối ngẫu được mô tả trong bảng như sau: 11
Hệ số Biến cơ sở P/án 3 2 0 0 0 x1 x2 x3 x4 x5 0 x3 -4 -1 -2 1 0 0 0 x4 -3 -1 -1 0 1 0 0 x5 -4 [-2] -1 0 0 1 0 0 0 0 0 0 3 2 0 0 0 0 x3 -2 0 [-3/2] 1 0 -1/2 0 x4 -1 0 -1/2 0 1 -1/2 3 x1 2 1 1/2 0 0 -1/2 3 3/2 0 0 -3/2 6 0 1/2 0 0 3/2 2 x2 4/3 0 1 -2/3 0 1/3 0 x4 -1/3 0 0 [-1/3] 1 -1/3 3 x1 4/3 1 0 1/3 0 -2/3 4 2 -1/3 0 -4/3 20/3 0 0 1/3 0 4/3 2 x2 2 0 1 0 -2 1 0 x3 1 0 0 1 -3 1 3 x1 1 1 0 0 1 -1 3 2 0 -1 -1 7 0 0 0 1 1 12
Chương 2. ỨNG DỤNG BÀI TOÁN ĐỐI NGẪU 2.1. Ứng dụng bài toán đối ngẫu cho bài toán phân luồng giao thông tuyến tính + Cho một đồ thị có hướng G = (V, E) với kh ả năng thông qua c ủa các cung là c : E → R*. Trong V có k đỉnh nguồn s1 , s2 ,..., sk tương ứng với k đỉnh đích t1 , t 2 ,..., t k và các đỉnh trung gian khác tạo thành một mạng có hướng. Ở đây mỗi cặp đỉnh nguồn đích ( s j , t j ) được gắn với một phương tiện j . Giả thiết rằng phương tiện j xuất phát từ đỉnh nguồn s j định trước, thì sẽ kết thúc tại đỉnh đích t j tương ứng, với j = 1,..., k . Bài toán luồng đa phương tiện cực đại là tìm một luồng đa phương tiện trong mạng G đã cho, sao cho t ổng các lu ồng của tất cả k phương tiện đạt cực đại. +Cơ sở lý thuyết thuật toán: Gọi Pj là tập hợp các đường đi từ s j đến t j trong mạng G, j = 1,..., k . Gọi P = P ∪ P2 ∪ ... ∪ Pk , là hợp của 1 P , P2 ,..., Pk . Với Pe là tập hợp các đường trong P đi qua e, ∀e ∈ E. Mỗi 1 đường p ∈ P , gắn một biến x( p ) của luồng gửi dọc theo đường p. Yêu cầu bài toán được phát biểu dạng bài toán quy hoạch tuyến tính như sau: 13
λ = max ∑ x( p)  p∈P   ∑ x( p) ≤ c(e), ∀e ∈ E  (P) p∈P  x≥0   Giải bài toán (P) ta xây dựng mô hình tuyến tính đối ngẫu v ới (P) g ọi là bài toán (D) như sau: ∀e ∈ E , gắn cho e một hàm độ dài l (e) . Định nghĩa: β = min D (l ) = ∑ c(e).l (e) e∈E   ∑ l (e) ≥ 1, ∀p ∈ P  (D) e∈ p  l≥0   Gọi dist j (l ) là độ dài ngắn nhất tính theo l trong các đường thuộc Pj , ∀j = 1,..., k . Đặt α (l ) = min { dist j (l ) j = 1,..., k } Vậy α (l ) là độ dài ngắn nhất trong mọi đường giữa các cặp nguồn đích. Xét bài toán  D (l )  min  l : E → R*  ( Dα )  α (l )  Ta có ∑ l ' (e) ≥ 1, ∀p ∈ P. e∈ p D (l ) Khi đó, ta được l ' là phương án chấp nhận của (D) và D (l ' ) = . α (l ) Từ đó suy ra min( D ) ≤ min( Dα ) . Ngược lại, nếu l là phương án chấp nhận D (l ) của (D) thì ≤ D(l ) , từ đó suy ra min( D ) ≥ min( Dα ) . α (l ) 14
Cuối cùng ta được min( D ) = min( Dα ) . Tiếp theo, nếu l là nghiệm tối ưu của bài toán ( Dα ) thì l ' (e) = l (e) / α (l ), ∀e ∈ E là nghiệm tối ưu của bài toán (D). +Thuật toán: Thuật toán được thực hiện bởi một số bước lặp. Gọi li −1 là hàm độ dài tại điểm bắt đầu bước lặp thứ i và f i −1 là giá trị tổng luồng đã đạt được sau các bước lặp 1,..., i − 1. Ta có α (li −1 ) là độ dài ngắn nhất trong các đường nối giữa các cặp nguồn đích, tính theo li −1 . Gọi p là đường đi có độ dài α (li −1 ) và c là khả năng thông qua cực tiểu trên p . Tại bước lặp i , ta chuyển c đơn vị phương tiện dọc theo p. Theo đó f i = f i −1 + c. Tiếp theo ta đặt li (e) = li −1 (e).(1 + ε .c / c(e)), ∀e ∈ p, trong đó ε ≥ 0 là hằng số sẽ chọn sau. Ban đầu, ∀e ∈ E , đặt l0 (e) = δ , trong đó δ là hằng số cũng được chọn sau. Thuật toán dừng sau t bước, với t là số nhỏ nhất mà α (lt ) ≥ 1. 2.2. Ứng dụng bài toán đối ngẫu cho bài toán luồng đa phương tiện cực đại đồng thời Cho một đồ thị có hướng G = (V, E) với khả năng thông qua của các cung là c : E → R*. Trong V có k đỉnh nguồn s1 , s2 ,..., sk tương ứng với k đỉnh đích t1 , t 2 ,..., t k và các đỉnh trung gian khác tạo thành một mạng có hướng. Ở đây mỗi cặp đỉnh nguồn đích ( s j , t j ) được gắn với một phương tiện j . Giả thiết rằng phương tiện j xuất phát từ đỉnh nguồn s j định trước, thì sẽ kết thúc tại đỉnh đích t j tương ứng, với j = 1,..., k . Bài toán luồng đa phương tiện cực đại đồng thời là mỗi phương tiện j có một yêu cầu vận chuyển d ( j ) gắn với nó. Nhiệm vụ của bài toán là tìm số λ lớn nhất sao cho 15
có một luồng đa phương tiện chuyển λ .d ( j ) đơn vị phương tiện j qua luồng, ∀j = 1,..., k . +Cách biểu diễn đường đi, ta có bài toán theo mô hình quy hoạch tuyến tính như sau: max λ   ∑ x( p) ≤ c(e), ∀e ∈ E  p∈ e ℘   (P) ∑ x( p) ≥ λ.d ( j ), ∀1 ≤ j ≤ k  p∈℘ j  x ≥ 0, λ ≥ 0   Để giải (P) ta xây dựng mô hình tuyến tính đối ngẫu với (P), gọi là (D), như sau: ∀e ∈ E , gắn cho e một hàm độ dài l (e) , với mỗi phương tiện j = 1,..., k , gán một biến z ( j ). Định nghĩa: min l D(l ) = ∑ c(e).l (e)  e∈E  ∑ l (e) ≥ z ( j ), ∀1 ≤ j ≤ k , ∀p ∈℘ j  e∈ p  k  (D) ∑ d ( j ).z ( j ) ≥ 1  j =1   l, z ≥ 0  Định nghĩa z ( j ) (còn gọi là dist j (l ) ) là độ dài ngắn nhất trong các đường thuộc Pj tính theo l , ∀1 ≤ j ≤ k . Đặt 16
α (l ) = ∑ d ( j ).dist j (l ) j Bài toán đối ngẫu (D) tương đương với tìm hàm l : E → R* sao cho hàm D (l ) / α (l ) đạt cực tiểu. Đặt D (l ) β = min l . α (l ) Thuật toán: Thuật toán được thực hiện qua một số giai đoạn, mỗi giai đoạn gồm k vòng lặp ( k là số phương tiện). Ở vòng lặp thứ j của giai đoạn i ta chuyển d ( j ) đơn vị phương tiện thứ j qua luồng. Việc vận chuyển này được thực hiện trong một số bước. s −1 s Gọi li , j là hàm độ dài ở đầu bước thứ s , gọi pi , j là đường ngắn s s −1 nhất giữa s j và t j lúc này, tức là pi, j có độ dài là dist j (li , j ) . s s −1 { Trong bước này ta vận chuyển f i , j = min c, d i , j đơn vị phương tiện } s s thứ j dọc theo pi , j . Trong đó c là khả năng thông qua nhỏ nhất trên pi , j , d is, −1 là lượng phương tiện thứ j còn lại cần chuyển qua (số d ( j ) đơn vị cần j chuyển qua trong bước này). Sau đó ta đặt d is, j = d is, −1 − f is j và j ,  s  lis, j (e) s −1 = li , j (e).1 + ε . f i , j , ∀e ∈ p s & l s (e) = l s −1 (e), ∀e ∉ p s  i, j i, j i, j i, j c ( e)    Tiếp theo ta có D (lis, j ) = ∑ lis, j (e).c(e) = ∑ lis, −1 (e).c (e) + j ∑ lis, −1 (e).ε . f is j j , e∈E e∈E e∈ pis, j 17
= D (lis, −1 ) + ε . f is j .dist j (lis, −1 ) ≤ D (lis, −1 ) + ε . f is j .dist j (lis, j ) j , j j , q (i , j ) Vòng lặp thứ j của giai đoạn i kết thúc sau q(i, j ) bước, khi mà d i , j = 0. Giai đoạn i kết thúc, khi vòng lặp thứ k của giai đoạn i kết thúc. Hàm độ dài l được tính như sau: 0 - Hàm độ dài ban đầu: l1,0 = δ / c(e), ∀e ∈ E. - Hàm độ dài ở đầu bước lặp đầu tiên của mỗi giai đoạn i > 1 bằng hàm 0 q (i −1, k ) độ dài ở cuối giai đoạn trước: li ,0 = li −1, k . - Hàm độ dài ở đầu mỗi vòng lặp tiếp theo có giá trị bằng hàm độ dài ở 0 q (i , j −1) cuối vòng lặp trước: li , j = li , j −1 . Ta có D (liq (ji , j ) ) ≤ D(liq (ji , j ) −1 ) + ε . f iqj(i , j ) .dist j (liq (ji , j ) ) , , , , ≤ ... ≤ D (li0 j ) + ε .d ( j ).dist j (liq (ji , j ) ) , , Ký hiệu: li , D (i ), α (i ) là giá trị các hàm ở cuối mỗi giai đoạn. Từ quan h ệ trên suy ra D (i ) = D (li ) ≤ D (li0k ) + ε .d (k ).dist k (li ) , = D (liqki−k −1) ) + ε .d (k ).dist k (li ) (, , 1 ≤ D(li0k −1 ) + ε .(d (k ).dist k (li ) + d (k − 1)).dist k −1 (li ) ≤ ... , k 0 ≤ D(li ,0 ) + ε . ∑ d ( j ).dist j (li ) = D(i − 1) + ε .α (i ) j =1 ⇒ D (i ) ≤ D(i − 1) + ε .α (i ), ∀i = 1,..., t Thuật toán dừng sau giai đoạn t , khi mà D (t ) ≥ 1. 18
19