Bài giảng Tối ưu: Chương 2 - ThS. Trần Thị Thùy Nương

Nội dung trình bày trong chương 2 Tối ưu hóa rời rạc thuộc bài giảng Tối ưu nhằm trình bày về bài toán tối ưu hóa rời rạc (tối ưu tổ hợp), bài toán ba lô (bài toán cái túi), bài toán Quy hoạch (QH) nguyên tuyến tính Thuật toán Gomory, phương pháp nhánh cận Land – Doig.
Nội dung trích xuất từ tài liệu:
Bài giảng Tối ưu: Chương 2 - ThS. Trần Thị Thùy Nương Chương 2 TỐI ƯU HÓA RỜI RẠC10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 1 NỘI DUNG1. 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ính4. Thuật toán Gomory5. Phương pháp nhánh cận Land – Doig10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 2 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 địnhtrên tập hữu hạn S, và f : S → ℝ. s * ∈ S : f (s ) = min{f (s )}. * s∈S10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 3 BÀI TOÁN TỐI ƯU HÓA RỜI RẠCTố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án10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 4 BÀI TOÁN TỐI ƯU HÓA RỜI RẠCMộ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ịch10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 5 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ácnhau có trọng lượng và giá trị sử dụng tương ứnglà 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ượngkhông được vượt quá tải trọng b cho trước của balô.10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 6 BÀI TOÁN BA LÔ(Knapsack problem)Xét bài toán ba lô 0 – 1Một đồ vật j có thể được chọn để bỏ vào ba lôhoặc là không.Gọi x 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 BÀI TOÁN BA LÔ(Knapsack problem)Mô hình bài toán ba lô 0 – 1 : n max f ( x ) = ∑ c j x j j =1 n ∑ a j x j ≤ b  j =1  x ∈ {0,1}, j = 1,..., n  j10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 8 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ộtphầ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 BÀI TOÁN QH NGUYÊNMô hình bài toán QH nguyên tuyến tính n f (x) = ∑c x j =1 j j → min  n  ∑ aij x j = bi , i = 1, m  j =1  (IP )  x j ≥ 0, j = 1, n   x j nguyê n, j = 1, n  10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 10 THUẬT TOÁN GOMORYTrước hết, giải bài toán nới lỏng (LP) n f (x) = ∑c x j =1 j j → min  n  ∑ aij x j = bi , i = 1, m (LP )  j =1  x ≥ 0, j = 1, n  j10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 11 THUẬT TOÁN GOMORYKhông mất tính tổng quát, giả sử PATƯ của (LP)có dạng: x * = ( x1, x2 ,..., xm ,0,...,0).Khi đó, hệ ràng buộc của (LP) có dạng: x1 ′ ′ ′ + a1( m+1) xm+1 + ... + a1n xn = b1   x2 ′ ′ + a2(m+1) xm+1 + ... + a2n xn = b2 ′  ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯  ′ ′ xm + am(m+1) xm+1 + ... + amn xn = bm ′ 10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 12 THUẬT TOÁN GOMORYNếu các bi ′ , i = 1, m đều là số nguyên thì xi , i = 1, mcũng là nghiệm của (IP).Ngược lại, giả sử có bi ′ nào đó chưa nguyên. Taxét ptr ràng buộc tương ứng: xi + ai′( m +1) xm +1 + ... + ain xn = bi′ ′ (1)10/6/2012 MaMH: C02012 Chương 2: Tối ưu hóa rời rạc 13 THUẬT TOÁN GOMORY  ′ ′Đặt aij = [aij ] + α ij , j = m + 1,..., n  bi′ = [bi′] + β i  (α ij ≥ 0, 0 < β i < 1) n (1) ⇒ xi + ∑ ([a′ ] + α ij ij )x j = [bi ′ ] + βi , i = 1 m ...