Bài giảng Tối ưu - Chương 2: Tối ưu hóa rời rạc

Nội dung text: Bài giảng Tối ưu - Chương 2: Tối ưu hóa rời rạc

1. Chương 2 TỐI ƯU HÓA RỜI RẠC 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 1
2. NỘI DUNG 1. Bài toán tối ưu hóa rời rạc (tối ưu tổ hợp) 2. Bài toán ba lô (bài toán cái túi) 3. Bài toán Quy ho ạch (QH) nguyên tuy ến tính 4. Thu ật toán Gomory 5. Ph ương pháp nhánh cận Land – Doig 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 2
3. BÀI TOÁN TỐI ƯU HÓA RỜI RẠC Đị nh nghĩa Bài toán tối ưu hóa rời rạc xác đị nh trên tập hữu hạn S, và f: S → ℝ . s* ∈ S: fs(* )= min{ fs ( )} . s∈ S 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 3
4. BÀI TOÁN TỐI ƯU HÓA RỜI RẠC Tối ưu hóa rời rạc dựa vào: • Quy ho ạch tuy ến tính • Lý thuy ết đồ th ị • Lý thuy ết về độ ph ức tạp tính toán 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 4
5. BÀI TOÁN TỐI ƯU HÓA RỜI RẠC Một số ví dụ về bài toán tối ưu rời rạc: • Bài toán tìm đường đi ng ắn nh ất • Bài toán ba lô • Bài toán ng ười du lịch 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 5
6. BÀI TOÁN BA LÔ(Knapsack problem) Bài toán: Có một tập hợp gồm n lo ại đồ vật khác nhau có tr ọng lượng và giá tr ị sử dụng tương ứng là aj và cj , j = 1, ,n. Bài toán đặ t ra là cần lựa ch ọn một tập hợp các đồ vật để cho vào một ba lô sao cho tổng giá tr ị sử dụng của chúng là lớn nh ất và tổng tr ọng lượng không được vượt quá tải tr ọng b cho tr ước của ba lô. 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 6
7. BÀI TOÁN BA LÔ( Knapsack problem) Xét bài toán ba lô 0 – 1 Một đồ vật j có th ể được ch ọn để bỏ vào ba lô ho ặc là không. = = Gọix j : 1 khi đồ vật j được ch ọn, vàx j : 0 khi đồ vật j không được ch ọn, 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 7
8. BÀI TOÁN BA LÔ( Knapsack problem) Mô hình bài toán ba lô 0 – 1 : n = maxfx ( ) ∑ cxj j j =1  n ≤ ∑aj x j b  j =1  ∈ = xj {0,1}, j 1, , n 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 8
9. BÀI TOÁN QH NGUYÊN (Integer Programming – IP ) Là bài toán quy ho ạch trong đó tất cả ho ặc một ph ần các bi ến ch ỉ nh ận giá tr ị nguyên . + QH nguyên hoàn toàn (Pure Integer Programming) + QH nguyên bộ ph ận (Mixed Integer Programming) 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 9
10. BÀI TOÁN QH NGUYÊN Mô hình bài toán QH nguyên tuy ến tính n = → fx()∑ cxj j min j =1  n = = ∑ aijj x b i , i 1, m  j =1  ≥ = (IP ) xj 0, j 1, n  = xj nguynê , j 1, n  10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 10
11. THUẬT TOÁN GOMORY Tr ước hết, gi ải bài toán nới lỏng (LP) n = → fx()∑ cxj j min j =1  n = = ∑ aijj x b i , i 1, m (LP )  j =1  ≥ = xj 0, j 1, n 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 11
12. THUẬT TOÁN GOMORY Không mất tính tổng quát, gi ả sử PATƯ của (LP) * = có dạng: x( xx1 , 2 , , x m ,0, ,0). Khi đó, hệ ràng bu ộc của (LP) có dạng: +′ ++ ′ = ′ x1 ax 1(mm+ 1) + 1 axb 1 nn 1  +′ ++ ′ = ′  x ax+ + axb  2 2(mm 1) 1 2 nn 2 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯  +′ ++ ′ = ′  xam mm(+ 1) x m + 1 axb mnn m 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 12
13. THUẬT TOÁN GOMORY ′ = = Nếu các bi , i 1, m đề u là số nguyên thì xi , i 1, m cũng là nghi ệm của (IP). ′ Ng ược lại, gi ả sử cóbi nào đó ch ưa nguyên. Ta xét ptr ràng bu ộc tương ứng : +′ ++ ′ = ′ xi a imm(+ 1) x + 1 a inn x b i (1) 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 13
14. THUẬT TOÁN GOMORY aa′=[ ′ ] +α , jm =+ 1, , n Đặ t  ij ij ij ′= ′ + β bi[ b i ] i α≥ < β < (ij 0, 0 i 1) n ⇒ +′ +α =′ + β = (1)xi∑ ([ a ij ] ij ) x j [ b i ] i , i 1, m j= m + 1 n n −+′ ′ =−β α = xi[ b i ]∑ [ a ij ] x j i ∑ ij x j , i 1, m (2) jm=+1 jm =+ 1 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 14
15. THUẬT TOÁN GOMORY Vế trái (2) sẽ là số nguyên nếux * là PA cn đ của (IP), do đó vế ph ải (2) cũng ph ải là số nguyên, tức là: n β− α i∑ ijx j nguyên (3) j= m + 1 ≥ Mặt khác x j 0,  α =−′ ′ ≥ =+  ijaa ij[ ij ] 0, jm 1, , n nên n β− α ≤ β ′ i∑ ijx j i (3 ) j= m + 1 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 15
16. THUẬT TOÁN GOMORY n ′ ⇒ β− α ≤ << β (3),(3)i∑ ijx j 0(0 i 1) j= m + 1 n Hay −α ≤ − β ∑ ijx j i (4) j= m + 1 Thêm bi ếnbùxn+1 vào (4), n −α+ = − β ∑ ijx jxn+1 i (5) j= m + 1 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 16
17. THUẬT TOÁN GOMORY Bổ sung RB (5) vào bảng đơn hình. Khi dó, bảng mới này vừa không đả m bảo RB dấu của bi ến, vừa ch ưa nguyên. Ti ếp theo , áp dụng thu ật toán đơn hình đố i ng ẫu để nh ận được PATƯ. 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 17
18. PP NHÁNH CẬN LAND – DOIG Xét bài toán QH nguyên có dạng n = → fx()∑ cxj j max j =1  n ≤ = ∑ aj x j b i , i 1, , m  j =1  ≥ = (IP0 ) xj 0, j 1, , n  =  xnguynjj ê , 1, , n  = = vớiaj, b i , c j là các số nguyên cho tr ước i1, mj ; 1, n 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 18
19. PP NHÁNH CẬN LAND – DOIG Đặ t  n  =∈n ≤=≥ = D0 : xℝ :∑ axjji bi , 1, mx , j 0, nguynj ê , 1, , n   j =1  Các bước gi ải bài toán Bước 1: gi ải bài toán nới lỏng (LP0), với  n  nl n D:= x ∈ℝ : axbimx ≤ , = 1, , ≥ 0, j = 1, , n  0  ∑ jji j   j=1  10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 19
20. PP NHÁNH CẬN LAND – DOIG 0 0 Gi ả sử (LP0) có PATƯ x và giá tr ị tối ưuf( x ) . Nếux 0 nguyênthìdừng lại. Lúc đó, x 0 cũng là PATƯ của (IP0). Ng ược lại, chuy ển sang Bước 2. 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 20
21. PP NHÁNH CẬN LAND – DOIG Bước 2: β = 0 Đặ t(D0 ): f ( x ) (cận trên của bài toán(IP0 ) ) ∈ Nếu bi ếtx D0 thìf( x ) là cận dưới của bài toán. α = −∞ Ng ược lại, đặ t: (cận dưới của bài toán(IP0 ) ) (α là giá tr ị kỷ lục, x đgl kỷ lục (nếu có)) ℘:={ } D0 danh sách các tập con củaD0 cần xem xét . 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 21
22. PP NHÁNH CẬN LAND – DOIG β Bước 3: Ch ọn tậpDk là tập có cận trên(Dk ) lớn nh ất trong các tập con của℘ cần xem xét. Gọi xk là PATƯ của bài toán(LPk ) . k Chia tậpDk thành hai tập con với bi ến chia nhánh xj k k ( x j là thành ph ần không nguyên đầ u tiên của x ) D:= { xDx ∈ : ≤ [ x k ]}, k1 0 j j D:=∈ { xDx : ≥ [ x k ] + 1}, k2 0 j j k k với[xj ] làph ần nguyên củaxj . 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 22
23. PP NHÁNH CẬN LAND – DOIG Đặ t ℘:(\{ = ℘DDD }) ∪ { , } 0 k1 k 2 Gi ải lần lượt các bài toán nới lỏng(LP ), (LP ) tương k1 k2 ứng với các tập nới lỏng DDnl, nl . k1 k 2 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 23
24. PP NHÁNH CẬN LAND – DOIG Khi gi ải các bài toán nới lỏng(LP ), i = 1,2 sẽ xảy ki ra các tr ường hợp sau đây: i. Bài toán không ch ấp nh ận được ( D =∅ ), ta lo ại ℘ ki Dk kh ỏi tập , tứclà℘=℘: \{D } . i ki 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 24
25. PP NHÁNH CẬN LAND – DOIG ii. Tìm được PATƯ x k i nguyên. Khi đó, tính lại giá tr ị kỷ lục α= max{ α ,f ( x ki )} (giá tr ị kỷ lục hi ện tại). Gọix là kỷ lục hi ện tại tương ứng với giá tr ị kỷ lục hi ện tại α=f( x ) . Lo ạiD kh ỏi tập℘ , tức là℘=℘: \{D } . ki ki 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 25
26. PP NHÁNH CẬN LAND – DOIG iii. Tìm được PATƯ x k i không nguyên. Đặ tβ(D ):= f ( x ki ) là một cận trên của bài toán (IP ). ki ki * Lo ại bỏ các tập có cận trên nh ỏ hơn ho ặc bằng giá tr ị kỷ lục hi ện tại (nếu có). 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 26
27. PP NHÁNH CẬN LAND – DOIG Bước 4: Ki ểm tra điều ki ện dừng Nếu℘=∅ thì dừng thu ật toán. Kết lu ận PATƯ là x, Giá tr ị tối ưu là α=f( x ). Ng ược lại, tr ở về Bước 3. 10/6/2012 MaMH: C02012 Ch ươ ng 2: T ối ưu hóa r ời r ạc 27