Luận văn Ứng dụng lý thuyết tối ưu giải bài toán lập lịch

6 CHƯƠNG 1. 3BTỐI ƯU RỜI RẠC VÀ MỘT SỐ HƯỚNG TIẾP CẬN 1.1. 8B ÀI TOÁN TỐI ƯU Tối ưu hóa là một ngành toán học ứng dụng, đã và đang được nhiều người quan tâm nghiên cứu, tìm hiểu và ứng dụng vào thực tiễn. Bài toán tối ưu là kết quả của việc mô hình hóa những vấn đề nảy sinh từ thực tế, chúng có thể được diễn đạt dưới dạng toán học là tìm các biến số thỏa mãn những điều kiện nhất định và làm cho một hàm số cho trước đạt giá trị cực tiểu hay cực đại. 1.1.1. 18BDạng tổng quát của bài toán tối ưu Tìm vectơ 1( ,... ,..., )k nx x x x= thỏa mãn: f(x) Æ min(max) (1.1) với điều kiện ≤( ) 0ig x , i = 1, 2, ..., p (1.2) ( ) 0jh x = , j = 1, 2, ..., q (1.3) x ∈ X ⊂ RPnP, k = 1, 2, …, n (1.4) Trong đó f, gRiR, hRjR (i = 1, 2, …, p; j = 1, 2, …, q) là các hàm số cho trước của n biến số (f, gRiR, hRjR: R Pn P Æ R) và X ⊂ RPnP là tập đóng, thường có dạng X = + nR ≡ {x ∈ RPnP : xRjR ≥ 0, j = 1, 2, …, n} Bài toán (1.1) – (1.4) có tên gọi là bài toán quy hoạch toán học. Hàm f(x) được gọi là hàm mục tiêu, còn gRiR(x) và hRjR(x) là các hàm ràng buộc và ràng buộc dạng xRjR ≥ 0, j = 1, 2, …, n, được gọi là các ràng buộc về dấu. Tập hợp: D = { x ∈ X: ≤( ) 0ig x , i = 1, 2, ..., p; ( ) 0jh x = , j = 1, 2, ..., q}, 7 gọi là miền ràng buộc hoặc miền chấp nhận được. Mỗi véctơ x ∈ D được gọi là một phương án hoặc một lời giải chấp nhận được của bài toán. Phương án làm cho hàm số f(x) đạt giá trị cực tiểu hoặc cực đại được gọi là phương án tối ưu hoặc lời giải của bài toán. 1.1.2. 19BPhân loại các bài toán tối ưu Các bài toán tối ưu nói chung rất phong phú và đa dạng. Để tìm lời giải cho các bài toán này, có thể có một cách chung và đơn giản nhất là duyệt toàn bộ các phương án có thể có của bài toán đặt ra để chọn phương án tối ưu. Song do số phương án của các bài toán dạng này thường là một số rất lớn, thậm chí không đếm được, nên cách làm này không phải bao giờ cũng thực hiện được, ngay cả khi kích thước của bài toán không lớn lắm. Vì thế cần phải có những nghiên cứu về mặt lý thuyết để tách ra những lớp bài toán riêng, khai thác cấu trúc đặc thù của nó để đề ra phương pháp giải thích hợp. Sau đây là một số lớp bài toán tối ưu thường gặp: - Quy hoạch tuyến tính: Khi hàm mục tiêu f(x) và tất cả các hàm ràng buộc gRiR(x), hRjR(x) là tuyến tính, tập X là tập lồi đa diện (giao của một số hữu hạn các nửa không gian đóng). - Quy hoạch tham số: Khi các hệ số trong biểu thức của hàm mục tiêu và của các ràng buộc phụ thuộc tham số. - Quy hoạch phi tuyến: Khi hàm mục tiêu f(x) hoặc tồn tại ít nhất một trong các hàm ràng buộc gRiR(x), hRjR(x) không phải là tuyến tính, hoặc tập X khác tập lồi đa diện. - Quy hoạch lồi: Khi hàm mục tiêu f(x) là hàm lồi (nếu xét bài toán tìm cực tiểu) và miền ràng buộc D là tập hợp lồi. - Quy hoạch lõm: Khi hàm mục tiêu f(x) là hàm lõm (nếu xét bài toán tìm cực tiểu) và miền ràng buộc D là tập hợp lồi. - Tối ưu rời rạc: Khi X là tập rời rạc. Các bài toán tối ưu rời rạc thường xuất hiện khi nghiên cứu các quá trình hay đối tượng rời rạc. Trong trường hợp riêng khi 8 các biến chỉ nhận giá trị nguyên ta có quy hoạch nguyên. Một trường hợp riêng của quy hoạch nguyên là quy hoạch Boole, khi mà các biến số chỉ nhận giá trị 0 hoặc 1. Có thể chứng minh rằng: mọi bài toán tối ưu rời rạc đều có thể đưa về bài toán quy hoạch Boole. Thật vậy, giả sử biến số x chỉ có thể lấy một trong các giá trị cho trước aR1R, aR2R, …, aRkR. Khi đó bằng cách đặt: x = aR1RuR1R + aR2RuR2R + … + aRkRuRk R, uR1R + uR2R + …+ uRkR = 1, uRj R∈ {0, 1}, j = 1, 2, …, k thì biến rời rạc x có thể thay thế bởi một số biến uRjR chỉ nhận giá trị 0 hay 1, gọi tắt là biến 0-1 hay biến Boole. Tương tự, nếu x ∈ {0, 1, …, k} thì ta có thể viết: x = uR1R + uR2R + …+ uRkR với uRj R∈ {0, 1}, j = 1, 2, …, k nghĩa là bất kỳ bài toán với các biến nguyên bị chặn tùy ý, đều có thể quy về bài toán với các biến 0-1. Điều này cho thấy bài toán quy hoạch nguyên 0-1 giữ vai trò quan trọng trong tối ưu rời rạc. 1.2. 9BCÁC PHƯƠNG PHÁP CHÍNH TRONG TỐI ƯU RỜI RẠC Tối ưu rời rạc hay còn gọi là tối ưu tổ hợp là một lĩnh vực quan trọng trong lý thuyết tối ưu hóa. Các bài toán tối ưu nói chung và các bài toán tối ưu tổ hợp nói riêng rất phong phú và đa dạng. Chúng có nhiều ứng dụng rộng rãi trong thực tiễn. Sau đây là một số công cụ thường dùng trong tối ưu tổ hợp. Đó là các phương pháp cắt nổi tiếng của Gomory và phương pháp “nhánh và cận” rất có hiệu quả với nhiều biến dạng khác nhau cho các bài toán cụ thể: phương pháp quy hoạch động, phương pháp tìm kiếm ngẫu nhiên… 9 1.2.1. 20BPhương pháp cắt Gomory Xét bài toán quy hoạch tuyến tính có thêm điều kiện nguyên, gọi là bài toán quy hoạch nguyên tuyến tính. 0 1 n j j j x c x = = ∑ → min với các ràng buộc: ∑ = n j jij xa 1 = bRiR , i = 1, 2, ..., m; xRjR ≥ 0, j = 1, 2, ..., n; xRjR nguyên, j = 1, 2, ..., nR1R ≤ n Nếu nR1R = n ta có bài toán quy hoạch nguyên hoàn toàn, còn nếu nR1R < n thì có bài toán quy hoạch nguyên bộ phận. Gomory là người đầu tiên đưa ra các thuật toán cắt giải quy hoạch nguyên tuyến tính. Ý đại thể của phương pháp Gomory như sau: giải quy hoạch tuyến tính không có điều kiện nguyên, nếu bài toán này không có lời giải thì bài toán nguyên cũng không có lời giải. Nếu bài toán có lời giải và lời giải đó thỏa điều kiện nguyên thì đó là lời giải của bài toán nguyên, còn nếu lời giải đó không nguyên thì ta sẽ thêm vào một ràng buộc tuyến tính mới, cắt bỏ lời giải không nguyên này và vẫn giữ lại các điểm nguyên của miền ràng buộc. Ràng buộc thêm vào như thế gọi là siêu phẳng cắt hay lát cắt. Rồi lại giải quy hoạch tuyến tính tương ứng (không có điều kiện nguyên)... Với những điều kiện nhất định, quá trình trên sẽ dẫn đến lời giải nguyên sau một số hữu hạn bước lặp. Để áp dụng được phương pháp Gomory, cần có các giả thiết sau đây: a) Hàm mục tiêu 0x bị chặn dưới (đối với bài toán min) trên miền ràng buộc không có điều kiện nguyên. 10 b) Tập phương án tối ưu (lời giải) của bài toán tuyến tính không có điều kiện nguyên nếu khác rỗng thì phải bị chặn. c) 0x đòi hỏi phải nguyên (chẳng hạn, mọi cRjR nguyên). d) Có một trong hai điều kiện sau: - Hàm mục tiêu xR0R bị chặn trên miền ràng buộc không có điều kiện nguyên. - Bài toán có phương án (điểm) nguyên. Tóm lại, các điều kiện trên sẽ được thỏa mãn nếu miền ràng buộc (không kể điều kiện nguyên) là bị chặn và các hệ số aRijR, bRiR, cRjR đều nguyên. Có ba cách khác nhau thể hiện ý tưởng phương pháp giải nêu trên. 1.2.1.1. 42BThuật giải Gomory 1 Thuật toán này áp dụng cho bài toán quy hoạch nguyên hoàn toàn (nR1R = n). Nội dung thuật toán như sau: Áp dụng phương pháp đơn hình đối ngẫu từ vựng giải quy hoạch tuyến tính không có điều kiện nguyên, nếu bài toán không giải được thì bài toán nguyên cũng không giải được. Nếu bài toán giải được và lời giải thỏa mãn điều kiện nguyên thì lời giải đó đồng thời là lời giải cần tìm (quá trình giải kết thúc). Nếu lời giải đó không nguyên, ta chuyển sang bước lặp k = 0. Bước k ≥ 0. Giả sử ta đã có lời giải xPkP không nguyên. Ký hiệu NRkR là tập chỉ số các biến phi (ngoài) cơ sở. Biểu diến hàm mục tiêu 0x = cP T Px và các biến xR1R, xR2R, ..., xRnR qua các biến phi cơ sở xRjR ( j ∈ NRkR): xRiR = 0 k k k i ij j j N x x x ∈ − ∑ , i = 0, 1, 2, ..., n và bảng các hệ số TRkR = kijx là l-chuẩn, nghĩa là ở mỗi cột j ∈ NRkR ∪ {0} phần tử khác không đầu tiên phải là số dương. 11 Chọn dòng có chỉ số nhỏ nhất mà kix 0 không nguyên: t = min {i ∈ {0, 1, 2, ..., n} | ktx 0 không nguyên} và xây dựng siêu phẳng cắt tương ứng: xRn+k+1R = ( )0{ } { } k k k t ij j j N x x x ∈ − − −∑ xRn+k+1R ≥ 0 và nguyên. ([x] : phần nguyên của x, {x} = x – [x] : phần lẻ của x) Thêm dòng xRn+k+1R vào phía dưới bảng TRkR và được bảng đơn hình không chấp nhận được (chỉ ở dòng xRn+k+1R!). Áp dụng phương pháp đơn hình đối ngẫu từ vựng, nếu kết quả ta nhận được bảng đơn hình ứng với bài toán quy hoạch tuyến tính không giải được thì bài toán quy hoạch nguyên cũng không giải được, nếu trái lại kiểm tra tính nguyên của lời giải thu được. Nếu điều kiện nguyên được thỏa mãn thì đó là lời giải cần tìm, nếu trái lại ta chuyển sang bước lặp k + 1. Nếu có các giải thiết như đã nêu trên thì thuật toán Gomory 1 kết thúc sau một số hữu hạn bước lặp k. 1.2.1.2. 43BThuật toán Gomory 2 Áp dụng cho bài toán quy hoạch nguyên bộ phận (nR1R ≤ n). Về cơ bản, thuật toán Gomory 2 giống như thuật toán Gomory 1, chỉ khác ở cách xây dựng siêu phẳng cắt. Nhờ thuật toán Gomory 2 (trong trường hợp nR1R = n) cũng có thể giải bài toán quy hoạch nguyên hoàn toàn. Nhưng trong trường hợp này không có cơ sở để so sánh hiệu quả của thuật toán Gomory 1 và 2 với nhau. Cách xây dựng siêu phẳng cắt trong thuật toán Gomory 2 như sau: Giả sử ktx 0 không nguyên. Khi đó bất đẳng thức: 12 z = 00 ≥+− ∑ ∈ kNj jj xss là siêu phẳng cắt. Ở đây, sR0R = )( 0ktx và sRjR = ⎪⎪ ⎪⎪ ⎪⎪ ⎩ ⎪⎪ ⎪⎪ ⎪⎪ ⎨ ⎧ <+≥−− ≥+≥ >≤−− ≤≤ 0,1)( }{1 }{ 0,1 }{}{,}){1( }{1 }{ }{}{,}{ 1 0 0 1 01 0 0 01 k ij k ijk t k t k ij k ij k t k ij k ijk t k t k t k ij k ij xnjx x x xnjx xxnjx x x xxnjx Các điều kiện bảo đảm tính hữu hạn của thuật toán Gomory 2 hoàn toàn giống như các điều kiện của thuật toán Gomory 1. 1.2.1.3. 44BThuật toán Gomory 3 Áp dụng cho bài toán quy hoạch nguyên hoàn toàn (nR1R = n). Thuật toán 3 có ưu điểm là không bị ảnh hưởng bởi sai số làm tròn trong quá trình tính toán. Ý tưởng của thuật toán này như sau: xuất phát từ bảng nguyên, l-chuẩn (phần tử khác không đầu tiên của của mỗi cột là số dương) và không chấp nhận được (cột phương án còn có thành phần âm). Xây dựng ràng buộc mới sao cho dùng nó làm dòng quay với phần tử quay (còn gọi là phần tử chính) bằng -1, rồi biến đổi bảng đơn hình,... cho đến khi nào bảng là chấp nhận được thì ta có lời giải cần tìm. Cách xây dựng ràng buộc mới - siêu phẳng cắt – là như sau: Cho bảng nguyên, l-chuẩn và không chấp nhận được T = ijx , i = 0, 1, ..., n; j ∈ {0} ∪ NRk Giả sử t (1 ≤ t ≤ n) là chỉ số sao cho xRt0R < 0. Khi đó z = −1 + ∑ < ∈ ≥ 0 0 tj k x Nj jx là siêu phẳng cắt. Ta có thể chọn siêu phẳng cắt tốt hơn, nhưng khá phức tạp. 13 1.2.2. 21BPhương pháp nhánh cận Land – Doig Xét bài toán quy hoạch nguyên tuyến tính sau đây ∑ = n j jj xc 1 → min (1.5) với các điều kiện: ∑ = n j jij xa 1 = bRiR, i = 1, 2, ..., m (1.6) 0 ≤ xRj R≤ uRjR, j = 1, 2, ..., n (1.7) xRjR nguyên, j ∈ J với J ⊆ {1, 2, ..., n} (1.8) trong đó uRjR là cận trên của biến xRjR (có thể uRjR = +∞). Để cho bài toán (1.5) - (1.8) có hữu hạn phương án nguyên, ta giả thiết tập tất cả các điểm x thỏa (1.6) - (1.7) là bị chặn (chẳng hạn, mọi uRjR đều hữu hạn). Nếu J ≡ {1, 2, ..., n}, ta có bài toán quy hoạch nguyên hoàn toàn, còn nếu J ⊂ {1, 2, ..., n} thì có bài toán quy hoạch nguyên bộ phận. Trong bài toán trên, cùng với các ràng buộc đẳng thức có thể còn có các ràng buộc bất đẳng thức ≤ hay ≥. Ngoài ra, như thường lệ, bài toán tìm max có thể qui về bài toán tìm min bằng các đổi dấu hàm mục tiêu. Nội dung phương pháp: Ký hiệu PR1R là bài toán quy hoạch tuyến tính tương ứng với bài toán quy hoạch nguyên (1.5) - (1.8) (tạm bỏ qua điều kiện nguyên). Bài toán (1.5) - (1.8) sẽ được chia nhỏ dần thành một số hữu hạn các bài toán nhỏ hơn (theo nghĩa số phương án nguyên ít hơn), gọi tắt là các bài toán con. Mỗi bài toán con đều nhận được từ bài toán ban đầu bằng cách thêm vào một số ràng buộc dạng: xRjR ≥ αRjR ( j ∈ JR1R), xRjR ≤ βRjR ( j ∈ JR1R) với JR1R, JR2R ⊆ J, (1.9) trong đó αRjR, βRj Rlà những số nguyên nào đó (có thể JR1R hoặc JR2R bằng ∅). 14 Với mỗi bài toán con nhận được, ta xét bài toán quy hoạch tuyến tính tương ứng (bỏ qua điều kiện nguyên), thực chất đó là bài toán PR1 Rcó thêm các ràng buộc (1.9) nêu trên. Khi giải các bài toán quy hoạch tuyến tính tương ứng, ta có thể gặp một trong các tình huống sau: a) Bài toán không có phương án (miền ràng buộc rỗng), do đó nó cũng không có phương án nguyên, vì thế bài toán con đang xét sẽ bị loại (không cần xét tiếp nữa). b) Bài toán có phương án tối ưu nguyên (mọi thành phần j thuộc J nguyên). Khi đó ta nhận được một phương án của bài toán nguyên ban đầu (1.5) - (1.8) và giá trị hàm mục tiêu, thường được gọi là giá trị kỷ lục. Bài toán con tương ứng cũng đã xét xong và bị loại. c) Bài toán có phương án tối ưu, nhưng trong đó có ít nhất một thành phần j thuộc J không nguyên. Khi đó, giá trị tối ưu nhận được là một cận dưới cho mọi phương án nguyên của bài toán con đang xét. Bài toán con nào có cận dưới lớn hơn hay bằng giá trị kỷ lục sẽ bị loại, vì nó sẽ không chứa phương án nguyên tốt hơn. Tiếp đó, trong số các bài toán con còn lại, ta chọn bài toán có cận dưới nhỏ nhất (với hy vọng nó có nhiều khả năng chứa phương án nguyên tốt hơn). Giả sử bài toán quy hoạch tuyến tính tương ứng với bài toán con được chọn là bài toán PRkR và cận dưới nhỏ nhất này tương ứng với phương án tối ưu không nguyên xRkR của bài toán PRkR đã tìm được trước đó. Giả sử thành phần ktx không nguyên.Khi đó, bài toán con đang xét được chia thành hai bài toán con mới bằng cách thêm vào ràng buộc: [ ] 1+≥ ktt xx hoặc [ ]ktt xx ≤ Để tính cận dưới cho mỗi bài toán con mới, ta lại giải bài toán quy hoạch tuyến tính tương ứng với bài toán con đó (bỏ qua điều kiện nguyên). 15 Tùy theo kết quả giải, ta có thể loại bớt một số bài toán con mà chắc chắn nó không chứa phương án nguyên tốt hơn phương án hiện biết. Tiếp tục làm như vậy làm như vậy cho đến khi không còn bài toán con nào để xét nữa thì dừng. 1.3. 10B ÀI TOÁN LUỒNG TRÊN MẠNG 1.3.1. 22BLuồng trên mạng Trong nhiều ứng dụng liên quan đến đồ thị, cần thiết phải sử dụng các biến đo lượng dòng chảy qua mỗi cung, chẳng hạn như hệ thống mạng điện, mạng viễn thông, mạng sản xuất và phân phối, mạng giao thông, mạng ống dẫn nước, mạng máy tính,… Trên những hệ thống mạng như thế, chúng ta muốn chuyển một lượng chất liệu từ nơi này đến nơi khác sao cho đạt hiệu quả cao nhất. Hiệu quả ở đây có thể xét theo tiêu chuẩn thời gian, độ dài quãng đường, chi phí tiền bạc, mức độ an toàn,… Dạng bài toán này được gọi là bài toán luồng trên mạng. Mạng là một đồ thị có hướng G(V, E) với V là tập đỉnh, E là tập các cung; trong đó có duy nhất một đỉnh s không có cung đi vào gọi là điểm phát và có duy nhất một đỉnh t không có cung đi ra gọi là điểm thu và mỗi cung e = (v, w) ∈ E được gán với một số không âm c(e) = c(v, w) gọi là khả năng thông qua của cung e (nếu không có cung (v, w) thì khả năng thông qua c(v, w) được gán bằng 0). Một luồng f trong mạng G(V, E) là ánh xạ f: E Æ RPnP, gán cho mỗi cung e = (v, w) của đồ thị một số không âm f(e) = f(v, w), gọi là luồng trên cung e, thoả mãn các điều kiện: 16 1) Luồng trên mỗi cung e không vượt quá khả năng thông qua của nó: 0 ≤ f(e) ≤ c(e) với mọi cung e ∈ E; 2) Điều kiện cân bằng luồng trên mỗi đỉnh của mạng: tổng luồng trên mỗi cung đi vào đỉnh v (trừ s, t) bằng tổng luồng trên các cung đi ra khỏi đỉnh v: ( ) ( ) w s f w, v +∈Γ ∑ = ( ) ( ) w s f w, v −∈Γ ∑ với ( )v−Γ = {w ∈ V: (w, v) ∈ E} và ( )v+Γ = {w ∈ V: (v, w) ∈ E}. 3) Giá trị của luồng f là số: val( f ) = ( ) ( ) w s f s, w +∈Γ ∑ = ( ) ( ) w s f w, t −∈Γ ∑ Bài toán luồng cực đại trong mạng: Cho mạng G = (V, E). Hãy tìm luồng f* trong mạng với giá trị luồng val(f*) là lớn nhất. Luồng f* được gọi là luồng cực đại trong mạng. 1.3.2. 23BPhân loại các thuật toán luồng trên mạng Các thuật toán trên mạng nói chung có thể được phân thành 3 loại sau: - Cải tiến chi phí nguyên thủy (Primal cost improvement): Thực hiện các vòng lặp cải tiến chi phí đến giá trị tối ưu của nó bằng cách xây dựng một dãy các luồng khả thi tương ứng. - Cải tiến chi phí đối ngẫu (Dual cost improvement): Ở đây ta xây dựng bài toán có liên hệ với bài toán luồng trên mạng ban đầu, gọi là bài toán đối ngẫu, có các biến được gọi là các giá. Sau đó thực hiện các vòng lặp cải tiến chi phí đối ngẫu đến giá trị tối ưu của nó bằng cách xây dựng một dãy các giá tương ứng. - Đấu giá: Ở đây ta sinh ra một dãy các giá theo kiểu đấu giá trong cuộc sống thực. Cụ thể, sẽ không có việc cải tiến chi phí đối ngẫu và nguyên thủy ở đây, mặc dù ta có thể xem rằng việc đầu giá như là xấp xỉ của quá trình cải tiến đối ngẫu. 17 1.3.3. 24BThuật toán tìm luồng cực đại trong mạng Hiện nay có nhiều thuật toán để giải bài toán luồng cực đại trên mạng: Ford- Fulkerson (1956), Edmonds-Karp (1969), Dinic (1970), Karzanov (1974), Malhotra-Kumar-Maheshwari (1977), Sleator-Tarian (1980), Goldberg-Tarjan (1986), … Sau đây ta xét hai thuật toán thường sử dụng nhất là thuật toán Ford-Fulkerson và thuật toán Edmonds-Karp. 1.3.3.1. 45BThuật toán Ford-Fulkerson Ta đưa thêm vào một số khái niệm sau: Giả sử f là một luồng trong mạng G = (V, E). Từ mạng G = (V, E) ta xây dựng đồ thị có trọng số trên mạng GRfR = (V, ERf R), với tập các cung ERfR và trọng số trên các cung được xác định như sau: 1) Nếu e = (v, w) thuộc E với f(v, w) = 0, thì (v,w) thuộc ERfR với trọng số c(v,w). 2) Nếu e = (v, w) thuộc E với f(v,w) = c(v, w), thì (w, v) thuộc ERfR với trọng số f(v,w). 3) Nếu e = (v, w) thuộc E với 0 < f(v,w) < c(v, w) thì (v, w) thuộc ERfR với trọng số c(v, w) - f(v, w) và (w, v) thuộc ERfR với trọng số f(v, w). Các cung của GRfR đồng thời cũng là cung của G được gọi là cung thuận, các cung còn lại được gọi là cung nghịch. Đồ thị GRfR được gọi là đồ thị tăng luồng. Ví dụ: Các số viết cạnh các cung của G ở Hình vẽ 1.1 theo thứ tự là khả năng thông qua và luồng f trên các cung. 18 Hình 1.1. Khả năng thông qua và luồng trên cung Giả sử P = (s ≡ vR1R, vR2R, vR3R,.. , vRkR ≡ t) là một đường đi từ s đến t trên đồ thị tăng luồng GRfR. Gọi d là giá trị nhỏ nhất của các trọng số của các cung trên đường đi P. Xây dựng luồng f ' trên mạng G theo quy tắc sau: f(u,v) + d nếu (u, v) thuộc P là cung thuận; f '(u, v) = f(u,v) - d nếu (v, u) thuộc P là cung nghịch; ⎧⎪⎨⎪⎩ f(u,v) nếu (u, v) không thuộc P. Ta gọi thủ tục biến đổi luồng nêu trên là tăng luồng dọc theo đường P. Đường đi từ s đến t trên đồ thị tăng luồng GRfR gọi là đường tăng luồng. Bắt đầu từ luồng với tất cả các cung bằng 0 ta tìm đường tăng luồng trên đồ thị tăng luồng và thực hiện tăng luồng theo đường đi vừa tìm được. Sơ đồ thuật toán Ford-Fulkerson được mô tả trong thủ tục sau đây: Procedure Max_Flow; (*Thuật toán Ford-Fulkerson *) Begin (* khởi tạo bắt đầu từ luồng với giá trị 0 *) for u thuộc V do for v thuộc V do f(u,v):=0; Stop:= false; while not Stop do if {tìm được đường tăng luồng P}then {tăng luồng dọc theo P} else stop:=true; End; 19 Thuật toán Ford-Fulkerson có độ phức tạp là O(m.val(f*)), với f* là luồng cực đại trong mạng. Để tìm được đường tăng luồng trong GRfR có thể sử dụng thuật toán tìm kiếm theo chiều rộng hay tìm kiếm theo chiều sâu bắt đầu từ đỉnh s, nhưng sử dụng thuật toán gán nhãn của Ford-Fulkerson sẽ tối ưu hơn. Thuật toán được thực hiện bắt đầu với duy nhất đỉnh s được khởi tạo nhãn và nhãn của nó là chưa xét, còn tất cả các đỉnh còn lại đều chưa có nhãn. Từ s ta gán nhãn tất cả các đỉnh kề với nó và nhãn của đỉnh s trở thành đã xét. Tiếp theo, từ mỗi đỉnh v có nhãn chưa xét ta lại gán nhãn cho tất cả đỉnh chưa có nhãn kề với nó và nhãn của đỉnh v trở thành đã xét. Quá trình cứ lặp lại cho tới khi: hoặc là đỉnh t trở thành có nhãn hoặc là nhãn của tất cả các đỉnh có nhãn đều trở thành đã xét nhưng đỉnh t vẫn không có nhãn. Trong trường hợp thứ nhất ta tìm được đường tăng luồng, còn trường hợp thứ hai đối với luồng đang xét không tồn tại đường tăng luồng (tức là luồng đã là cực đại). Mỗi khi tìm được đường tăng luồng, ta lại tăng luồng theo đường tìm được, sau đó xoá tất cả các nhãn đối với luồng mới thu được rồi lại sử dụng phép gán nhãn các đỉnh để tìm đường tăng luồng. Thuật toán kết thúc khi gặp trường hợp thứ hai ở trên. 1.3.3.2. 46BThuật toán Edmonds-Karp Thuật toán Edmonds-Karp áp dụng khi các khả năng thông qua là nguyên và có thời gian tốt hơn thuật toán Ford-Fulkerson. Độ phức tạp tính toán của thuật toán Edmonds-Karp là O(n.mP2 P) và thuật toán được mô tả trong thủ tục sau: Procedure Max_Flow; (*Thuật toán Edmonds-Karp *) Begin while {tồn tại đường tăng luồng trong GRfR} do { Tìm đường tăng luồng với khả năng tăng luồng lớn nhất; Tăng luồng dọc theo đường này } End; 20 1.4. 11BĐỘ PHỨC TẠP CỦA CÁC BÀI TOÁN TỐI ƯU RỜI RẠC Những khó khăn trong việc xây dựng dựng thuật toán hiệu quả để giải nhiều bài toán tối ưu rời rạc là đòi hỏi sự giải thích về mặt lý thuyết mức độ phức tạp của chúng. Có thể nói lý thuyết độ phức tạp tính toán ra đời trong hoàn cảnh đó. Để đánh giá hiệu quả của một thuật toán có hai phương pháp: tiên nghiệm và thực nghiệm. Phương pháp thực nghiệm cho phép xác định thuật toán có hữu hiệu hay không bằng cách giải một loạt các bài toán thử (test). Phương pháp này có nhiều hạn chế: kết quả thực nghiệm thường không ổn định và phụ thuộc vào kỹ thuật lập trình, phương tiện tính toán để giải các bài toán thử. Tuy vậy, nó vẫn là một phương pháp được áp dụng rộng rãi để xác định tính hiệu quả của các thuật toán, và trong nhiều trường hợp ngoài nó ra không còn phương pháp nào khác. Phương pháp tiên nghiệm khắc phục được các nhược điểm vừa nêu. Theo phương pháp này ta cần phải đánh giá số phép toán nhiều nhất cần phải thực hiện trong thuật toán và biểu diễn nó dưới dạng O(f(n)), trong đó n là độ dài của dữ liệu đầu vào (còn gọi là số chiều của bài toán), còn O(f(n)) là tập hợp các hàm số g(n) sao cho tồn tại hằng số C và số nR0R để với n> nR0R thì |g(n)| ≤ C |f(n)|. Thuật toán được chia ra làm hai loại: thuật toán đơn định và thuật toán không đơn định. Kết quả của mỗi phép toán trong thuật toán đơn định được xác định duy nhất, còn trong thuật toán không đơn định có những phép toán đa trị. Ta hiểu thời gian thực hiện của một thuật toán là số phép toán nhiều nhất cần thực hiện để nhận được lời giải của bài toán với mọi bộ dữ liệu cho trước. Ta nói rằng thuật toán có độ phức tạp tính toán là O(f(n)), nếu với mọi bộ dữ liệu cho trước có độ dài n, thời gian thực hiện của thuật toán không vượt quá Cf(n), trong đó C là hằng số. Thuật toán được gọi là có độ phức tạp tính toán đa thức, nếu thời gian thực hiện của thuật toán đó là O(P(n)), trong đó n là độ dài đầu vào, còn P(n) là một đa thức bậc cố định nào đó. Thuật toán đơn định với độ phức tạp tính toán đa thức gọi ngắn gọn là thuật toán đa thức. 21 Tập các bài toán có thể giải được bằng thuật toán đa thức ký hiệu là P. Còn ký hiệu NP là tập các bài toán có thể giải được bằng thuật toán đa thức không đơn định. Rõ ràng P ⊆ NP, nhưng cho đến nay giải thuyết P = NP vẫn chưa được ai chứng minh hay bác bỏ. Tuy vậy, người ta đã chứng minh được rằng trong lớp NP có những bài toán khó không kém bất kỳ bài toán nào trong lớp này, chính xác hơn là nếu có thuật toán đa thức để giải một bài toán nào đó trong số chúng thì cũng có thuật toán đa thức để giải mọi bài toán trong NP. Những bài toán như vậy được gọi là NP-đầy đủ. Ví dụ, những bài toán tối ưu rời rạc sau đây là NP-đầy đủ: bài toán về ổn định của đồ thị, bài toán về chu trình Hamilton, bài toán người du lịch, bài toán phủ, … Để chứng minh một bài toán nào đó là NP-đầy đủ ta cần phải chỉ ra là nó có hai tính chất: 1. Tồn tại thuật toán đa thức không đơn định để giải nó; 2. Có một bài toán NP-đầy đủ có thể dẫn về nó. Những bài toán thỏa tính chất 2 về mặt độ phức tạp tính toán là khó tương đương với các bài toán NP-đầy đủ. Vì vậy, người ta gọi là những bài toán như vậy là NP-khó. Khi nghiên cứu giải quyết các bài toán tối ưu thực tế, việc xác định nó thuộc lớp nào trong số các bài toán kể trên không chỉ có ý nghĩa lý thuyết mà còn có ý nghĩa thực tế quan trọng. Nếu bài toán đang xét được xác nhận là thuộc vào một trong ba lớp cuối (NP, NP-đầy đủ, NP-khó) thì ít nhất có hy vọng tìm được thuật toán hiệu quả để giải nó. Vì vậy, tốt hơn cả là hướng tới việc xây dựng những thuật toán gần đúng cho các bài toán như vậy.