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

Chương 2 TỐI ƯU HÓA RỜI RẠC 10/6/2012 1MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 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 2MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 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∈ *( ) min{ ( )}. s S f s f s ∈ = 10/6/2012 3MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 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 4MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 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 5MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 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 6MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 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ọi khi đồ vật j được chọn, và khi đồ vật j không được chọn, : 1jx = : 0jx = 10/6/2012 7MaMH: C02012 Chương 2: Tối ưu hóa rời rạc BÀI TOÁN BA LÔ(Knapsack problem) Mô hình bài toán ba lô 0 – 1 : 1 max ( ) n j j j n f x c x a x b = =  ≤ ∑ ∑ 10/6/2012 8MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 1 {0,1}, 1,..., j j j jx j n =  ∈ = 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 9MaMH: C02012 Chương 2: Tối ưu hóa rời rạc BÀI TOÁN QH NGUYÊN Mô hình bài toán QH nguyên tuyến tính 1 ( ) min , 1, n j j j n f x c x a x b i m = = →  = = ∑ ∑ 10/6/2012 10MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 1 ( ) 0, 1, ê , 1, ij j i j j j IP x j n x nguy n j n =  ≥ =  =  THUẬT TOÁN GOMORY Trước hết, giải bài toán nới lỏng (LP) 1 ( ) min , 1, n j j j n f x c x a x b i m = = →  = = ∑ ∑ 10/6/2012 11MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 1( ) 0, 1, ij j i j j LP x j n =    ≥ = THUẬT TOÁN GOMORY Không mất tính tổng quát, giả sử PATƯ của (LP) có dạng: Khi đó, hệ ràng buộc của (LP) có dạng: * 1 2( , ,..., ,0,...,0).mx x x x= ...x a x a x b+ +′ ′ ′+ + + = 10/6/2012 12MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 1 1( 1) 1 1 1 2 2( 1) 1 2 2 ( 1) 1 ... ... m m n n m m n n m m m m mn n m x a x a x b x a x a x b + + + +  ′ ′ ′+ + + =    ′ ′ ′+ + + = ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯ THUẬT TOÁN GOMORY Nếu các đều là số nguyên thì cũng là nghiệm của (IP). Ngược lại, giả sử có nào đó chưa nguyên. Ta xét ptr ràng buộc tương ứng: , 1,ib i m′ = , 1,ix i m= ib ′ 10/6/2012 13MaMH: C02012 Chương 2: Tối ưu hóa rời rạc ( 1) 1 ... (1)i i m m in n ix a x a x b+ +′ ′ ′+ + + = THUẬT TOÁN GOMORY Đặt [ ] , 1,..., [ ] ij ij ij i i i a a j m n b b α β ′ ′= + = +  ′ ′= + ( 0, 0 1)ij iα β≥ < < n α β′′⇒ + + = + =∑ 10/6/2012 14MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 1 (1) ([ ] ) [ ] , 1,i ij ij j i i j m x a x b i m = + 1 1 [ ] [ ] , 1, (2) n n i i ij j i ij j j m j m x b a x x i mβ α = + = + ′ ′ − + = − =∑ ∑ THUẬT TOÁN GOMORY Vế trái (2) sẽ là số nguyên nếu là PA cnđ của (IP), do đó vế phải (2) cũng phải là số nguyên, tức là: nguyên (3) *x 1 n i ij j j m xβ α = + − ∑ Mặt khác nên 10/6/2012 15MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 0, [ ] 0, 1,..., j ij ij ij x a a j m nα ≥  ′ ′= − ≥ = + 1 (3 ) n i ij j i j m xβ α β = + ′ − ≤∑ THUẬT TOÁN GOMORY Hay 1 (3),(3 ) 0 (0 1) n i ij j i j m xβ α β = + ′ ⇒ − ≤ < <∑ 1 (4) n ij j i j m xα β = + − ≤ −∑ Thêm biến bù vào (4), 10/6/2012 16MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 1nx + 1 1 (5) n ij j i j m nx xα β+ = + − = −+∑ 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 17MaMH: C02012 Chương 2: Tối ưu hóa rời rạc PP NHÁNH CẬN LAND – DOIG Xét bài toán QH nguyên có dạng 1 ( ) max , 1,..., n j j j n j j i f x c x a x b i m = = →  ≤ = ∑ ∑ với là các số nguyên cho trước 10/6/2012 18MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 1 0( ) 0, 1,..., ê , 1,..., j j j IP x j n x nguy n j n = ≥ =  =  1, ; 1,i m j n= =, ,j i ja b c PP NHÁNH CẬN LAND – DOIG Đặt 0 1 : : , 1, , 0, ê , 1,..., n n j j i j j D x a x b i m x nguy n j n =   = ∈ ≤ = ≥ =    ∑ℝ 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 10/6/2012 19MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 0 1 : : , 1, , 0, 1,..., n nl n j j i j j D x a x b i m x j n =    = ∈ ≤ = ≥ =     ∑ℝ PP NHÁNH CẬN LAND – DOIG Giả sử (LP0) có PATƯ và giá trị tối ưu . Nếu nguyên thì dừng lại. Lúc đó, cũng là PATƯ của (IP0). Ngược lại, chuyển sang Bước 2. 0x 0( )f x 0x 0x 10/6/2012 20MaMH: C02012 Chương 2: Tối ưu hóa rời rạc PP NHÁNH CẬN LAND – DOIG Bước 2: Đặt (cận trên của bài toán ) Nếu biết thì 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 ) 0 0( ): ( )D f xβ = 0x D∈ :α = −∞ 0( )IP ( )f x 0( )IP ( là giá trị kỷ lục, đgl kỷ lục (nếu có)) danh sách các tập con của cần xem xét. 10/6/2012 21MaMH: C02012 Chương 2: Tối ưu hóa rời rạc α x D0℘:={ } 0D PP NHÁNH CẬN LAND – DOIG Bước 3: Chọn tập là tập có cận trên lớn nhất trong các tập con của cần xem xét. Gọi là PATƯ của bài toán . Chia tập thành hai tập con với biến chia nhánh ( là thành phần không nguyên đầu tiên của ) kD ( )kDβ℘ kx ( )kLP kD kx k jx kx với là phần nguyên của . 10/6/2012 22MaMH: C02012 Chương 2: Tối ưu hóa rời rạc j 1 0 : { : [ ]},kk j jD x D x x= ∈ ≤ 2 0 : { : [ ] 1},kk j jD x D x x= ∈ ≥ + [ ]kjx kjx PP NHÁNH CẬN LAND – DOIG Đặt Giải lần lượt các bài toán nới lỏng tương ứng với các tập nới lỏng 1 20 : ( \ { }) { , }k kD D D℘ = ℘ ∪ 1 ( ),kLP 1 2 , . nl nl k kD D 2 ( )kLP 10/6/2012 23MaMH: C02012 Chương 2: Tối ưu hóa rời rạc PP NHÁNH CẬN LAND – DOIG Khi giải các bài toán nới lỏng sẽ xảy ra các trường hợp sau đây: i. Bài toán không chấp nhận được ( ), ta loại khỏi tập , tức là . ( ), 1,2 ik LP i = ik D =∅ ik D ℘ : \ { } ik D℘=℘ 10/6/2012 24MaMH: C02012 Chương 2: Tối ưu hóa rời rạc PP NHÁNH CẬN LAND – DOIG ii. Tìm được PATƯ nguyên. Khi đó, tính lại giá trị kỷ lục (giá trị kỷ lục hiện tại). Gọi là kỷ lục hiện tại tương ứng với giá trị kỷ lục hiện tại . ikx max{ , ( )}ikf xα α= x ( )f xα= Loại khỏi tập , tức là . 10/6/2012 25MaMH: C02012 Chương 2: Tối ưu hóa rời rạc ik D ℘ : \ { } ik D℘=℘ PP NHÁNH CẬN LAND – DOIG iii. Tìm được PATƯ không nguyên. Đặt là một cận trên của bài toán * 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ó). ikx ( ): ( )i i k kD f xβ = ( ).ikIP 10/6/2012 26MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 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à Ngược lại, trở về Bước 3. 10/6/2012 27MaMH: C02012 Chương 2: Tối ưu hóa rời rạc ( ).f xα=