Bài giảng Quy hoạch tuyến tính - Chương 2: Lý thuyết đối ngẫu

Nội dung text: Bài giảng Quy hoạch tuyến tính - Chương 2: Lý thuyết đối ngẫu

1. Chương 2 LÝ THUYẾT ĐỐI NGẪU 20/6/2012 MaMH : 501014 Ch ươ ng 1 : Bài toán Quy ho ạch tuy ến tính 1
2. NỘI DUNG 1. Bài toán đố i ng ẫu quy ho ạch tuy ến tính 1.1 Xây dựng bài toán đố i ng ẫu 1.2 Các đị nh lý đố i ng ẫu 2. Ph ương pháp đơn hình đố i ng ẫu 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 2
3. Bài toán đối ngẫu QHTT 1. Xây dựng bài toán đố i ng ẫu QHTT Xét bài toán n = → f( x ) ∑c j x j mi n j =1  n ≥ = ∑aij x j bi , i 1, m (P )  j =1  ≥ = xj 0, j 1, n . 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 3
4. Bài toán đối ngẫu QHTT Bài toán đố i ng ẫu của bài toán trên là m = → g( y ) ∑bi y i ma x i =1  m ≤ = ∑ayij i c j , j 1, n (D )  i =1  ≥ = yi 0, i 1, m . 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 4
5. Bài toán đối ngẫu QHTT Nhận xét : • Cả hai bài toán đề u ở dạng chu ẩn tắc; • Một bài toán min, một bài toán max; • Số bi ến của bài toán này là số ràng bu ộc của bài toán kia và ng ược lại; • cj và bi đổ i vai trò cho nhau. 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 5
6. Bài toán đối ngẫu QHTT Ví dụ 1 Lập bài toán đố i ng ẫu của bài toán sau = + + → fx()3 x1 2 x 2 5 x 3 min −2x ++ x 4 x ≥ 6  1 2 3 − + ≥  x15 x 2 2 x 3 8  ≥ =  xj 0, j 1,2,3 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 6
7. Bài toán đối ngẫu QHTT = + + → fx( )3 x12 x 25 x 3 min −2x ++ x 4 x ≥ 6  1 2 3 − + ≥ ()P x1 5 x 2 2 x 3 8  x≥0, j = 1,2, 3 = + →  j gy()6 y18 y 2 max − + ≤  2y1 y 2 3   y−5 y ≤ 2 (D )  1 2 + ≤ 4y1 2 y 2 5  ≥ ≥ y10, y 2 0 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 7
8. Bài toán đối ngẫu QHTT Quy tắc lập bài toán đố i ng ẫu Bài toán gốc (đối ngẫu) Bài toán đối ngẫu (gốc) Bi ến:x1, x 2 , , x n Bi ến: y1, y 2 , , y m Hàm mục tiêu: Hàm mục tiêu: n m = → = → fx( )∑ cxj j min gy()∑ byi i max j =1 i =1 Ràng bu ộc: Dấu của bi ến: ≥ ∈ bi , i I 1 ≥ ∈ n 0, i I 1 = ∈ ∑axij j bi i , I 2 ∈ ∈ yi ℝ, i I 2 j =1 ≤b, i ∈ I ≤ ∈ i 3 0, i I 3 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 8
9. Bài toán đối ngẫu QHTT Quy tắc lập bài toán đố i ng ẫu (tt ) Bài toán gốc (đối ngẫu) Bài toán đối ngẫu (gốc) Dấu của bi ến: Ràng bu ộc: ≤ ∈ ≥0, j ∈ J cj , j J 1 1 m ∈ ∈ = ∈ xj ℝ, j J 2 ∑ayij i cj j , J 2 = ≤0, j ∈ J i 1 ≥ ∈ 3 cj , j J 3 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 9
10. Bài toán đối ngẫu QHTT Ví dụ 2 Lập bài toán đố i ng ẫu của bài toán sau = + + → fx()2 xx1 2 7 x 3 min + − ≥ 3x1 5 x 2 4 x 3 1   2x− x + 2 x = 4 (P )  1 2 3 + + ≤  x12 x 2 6 x 3 8  ≥ ≤ ∈ x10, x 2 0, x 3 ℝ 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 10
11. Bài toán đố i ng ẫu của bài toán trên: = + + → gy() y1 4 y 2 8 y 3 max + + ≤  3y1 2 y 2 y 3 2   5y− y + 2 y ≥ 1 (D )  1 2 3 − + + =  4y1 2 y 2 6 y 3 7  ≥ ∈ ≤  y10, y 2ℝ , y 3 0 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 11
12. Bài toán đối ngẫu QHTT 2. Đị nh lý đố i ng ẫu Đị nh lý 1 (Đố i ng ẫu yếu) Nếu x là PA của (P) và y là PA của (D), thì cxcx+ + + cx ≥ by + by + + by 1122nn 1122 mm =f() x = g( y ) 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 12
13. Bài toán đối ngẫu QHTT Đị nh lý 2 (đố i ng ẫu mạnh) Nếu một QH có PATƯ thì QH đố i ng ẫu của nó cũng có PATƯ và giá tr ị mục tiêu của chúng là bằng nhau . 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 13
14. Bài toán đối ngẫu QHTT Đị nh lý 3 (Đị nh lý tồn tại) Đố i với mỗi cặp bài toán (P) và (D), một trong ba kh ả năng sau xảy ra: i) Cả (P) và (D) đề u không có PA. ii) Cả (P) và (D) đề u có PA. Khi đó, chúng sẽ có PATƯ và giá tr ị mục tiêu là bằng nhau. iii) Một QH có PA còn QH kia thì không. Khi đó, QH có PA sẽ không có PATƯ. 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 14
15. Bài toán đối ngẫu QHTT Đị nh lý 4 (đk độ lệch bù (yếu)) Một cặp PA x, y của (P) và (D) là nh ững PATƯ khi và ch ỉ khi chúng nghi ệm đúng hệ:  n  − = ∀ = yi∑ a ij x j b i  0 i 1, m (1)   j =1   m   − = ∀ = xcj j∑ ay i j i  0 jn1, (2)   i =1  20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 15
16. Phương pháp đơn hình đối ngẫu Là ph ương pháp đơn hình áp dụng cho bài toán đố i ng ẫu nh ưng để tìm nghi ệm cho bài toán gốc và các bước tính toán đề u làm trên bài toán gốc. 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 16
17. Phương pháp đơn hình đối ngẫu Thuật toán: Xu ất phát từ “gi ả PA”x0 (th ỏa mãn ràng bu ộc và ∆ ≤ ∀ dấu hi ệu tối ưuj 0, j nh ưng ch ưa th ỏa mãn đk x ≥ 0). -Lập bảng đơn hình đố i ng ẫu với gi ả PA x0. - Ki ểm tra: nếu các ph ần tử trên cột gi ả PA đề u không âm thì dừng thu ật toán. Ngược lại, tìm (gi ả) PA mới: + Ch ọn bi ến ra : là bi ến nằm trên dòng có ph ần tử âm nh ỏ nh ất ở cột gi ả PA. 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 17
18. Phương pháp đơn hình đối ngẫu + Ch ọn bi ến vào : lập tỉ số gi ữa các ph ần tử ở dòng ước lượng với các ph ần tử âm ở dòng quay (dòng ch ứa bi ến ra), ch ọn tỉ số nh ỏ nh ất. Ch ỉ số tương ứng với tỉ số nh ỏ nh ất là ch ỉ số của bi ến vào. -Lập bảng đơn hình mới, với các số li ệu được tính toán gi ống nh ư thu ật toán đơn hình thông th ường. - Quay lại bước Ki ểm tra. 20/6/2012 MaMH : 501014 Ch ươ ng 2 : Lý thuy ết đố i ng ẫu 18