Bài toán quy hoạch tuyến tính đối ngẫu - Chương 2: Tối ưu hóa

ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 1 Ths. Nguyễn Công Trí Copyright 2001 Ths. Nguyễn Công Trí Copyright 2001 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU 1. CÁCH THÀNH LẬP BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU (Xem) 2. CÁC ĐỊNH LÝ ĐỐI NGẪU (Xem) 3. THUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪU (Xem) 4. MỘT SỐ ỨNG DỤNG CỦA LÝ THUYẾT ĐỐI NGẪU TRONG BÀI TOÁN QHTT (Xem) 5. BÀI TẬP (Xem) CHƯƠNG 2 THÀNH LẬP BÀI TOÁN ĐỐI NGẪU Mục đích và ý nghĩa  Với bài toán QHTT, bài toán gốc, ký hiệu là P (Primal), chúng ta có thể thiết lập bài toán QHTT khác, bài toán đối ngẫu, ký hiệu là D (Dual), sao cho từ lời giải của bài toán này ta có thể thu thập được thông tin về lời giải của bài toán kia.  Để có thông tin cần thiết về bài toán gốc, có thể nghiên cứu trên bài toán đối ngẫu của nó.  Hơn nữa, khi phân tích đồng thời cả hai bài toán gốc và đối ngẫu, chúng ta có thể rút ra các kết luận có giá trị về mặt toán học lẫn về mặt ý nghĩa kinh tế. THÀNH LẬP BÀI TOÁN ĐỐI NGẪU Xét bài toán QHTT (P) dưới dạng chính tắc Với x = (x1, x2,..., xn) n, b = (b1, b2,..., bm) m Giả sử bài toán (P) có P.A.T.U là xopt và gọi x 0 là một P.A của bài toán (P), ta có ctxopt ≤ c tx0. Gọi x = (x1, x2,..., xn) n, với x ≥ 0 sao cho Ax – b  0 Bài toán tương đương:     ( ) min 0. t Pf x c x P IAx b x              ( , ) min 0 . t t m L x y c x y b Ax P IIx y R          THÀNH LẬP BÀI TOÁN ĐỐI NGẪU Gọi g(y) là hàm mục tiêu của bài toán (II), ta có g(y) = min{ctx + yt(b – Ax)}, với x ≥ 0. ≤ ctx + yt(b – Ax), với x ≥ 0.  Nếu x là P.A của bài toán (I) thì b – Ax = 0 và g(y) ≤ ctx. Vậy g(y) là một cận dưới bất kỳ của hàm mục tiêu.  Ta tìm cận dưới lớn nhất Max{g(y)}, thật vậy g(y) = min{ctx + yt(b – Ax)}, với x ≥ 0. = min{ctx + ytb – ytAx}, với x ≥ 0. = min{ytb + (ct – ytA)x}, với x ≥ 0. = ytb + min{ (ct – ytA)x}, với x ≥ 0. ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 2 THÀNH LẬP BÀI TOÁN ĐỐI NGẪU Xét Vậy ta được g(y) = ytb Suy ra bài toán đối ngẫu có dạng Hay bài toán tương đương    t t tx 0 0 c 0 min c c 0 t t t khi y A y A x khi y A            ( ) max ( ) max 0 . . t t t t t t m m g y y b g y y b D c y A y A c y R y R                   ( ) max . t t m g y y b D A y c y R        THÀNH LẬP BÀI TOÁN ĐỐI NGẪU Ví dụ 2.1. Bài toán đối ngẫu của bài toán QHTT sau đây là bài toán 1 4 5 1 3 5 2 5 2 3 4 ( ) 2 8 6 min 2 4 2 4 2 3 13 0 1,5j f x x x x x x x x x x x x x j                   1 2 3 1 2 3 1 3 3 1 2 ( ) 4 4 13 max 2 2 2 0 2 0 3 8 6 Df y y y y y y y y y y y y                  THÀNH LẬP BÀI TOÁN ĐỐI NGẪU VD2.2 VD2.3 VD2.4 VD2.5 VD2.6 VD2.7 Bài toán gốc (P) Bài toán đối ngẫu (D) Hàm mục tiêu Hàm mục tiêu Ràng buộc thứ i Ràng buộc thứ j Ẩn thứ j Ẩn thứ I 1 1, n ij j i j a x b i m             1 ( ) min n P j j j f x c x    1 , 1, m ij i j i a y c j n             0, 1,jx j n          không ràng buộc 0, 1,iy i m          không ràng buộc 1 ( ) max m D i i i f y b y    Ví dụ 2.2. Viết bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu của bài toán QHTT Các cặp đối ngẫu 1 2 3 4 1 2 3 4 1 2 3 1 2 3 4 ( ) 2 2 min 2 2 1 3 3 2 3 4 0 1,2j f x x x x x x x x x x x x x x x x x j                        THÀNH LẬP BÀI TOÁN ĐỐI NGẪU 1 2 3 1 2 3 1 2 3 1 2 3 1 3 1 2 ( ) 3 4 max 3 2 1 3 2 2 1 2 2 0, 0 Df y y y y y y y y y y y y y y y y y                         Bài toán đối ngẫu         1 1 2 3 2 1 2 3 1 2 3 4 1 1 2 3 2 0, 3 2 1 1 0, 3 2 2 2 2 1, 0 3 3 3, 0 4 x y y y x y y y x x x x y x x x y                  ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 3 Ví dụ 2.3. Viết bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu của bài toán QHTT Các cặp đối ngẫu 1 2 3 1 2 3 1 2 3 1 2 3 ( ) 2 8 max 7 4 2 28 3 3 10 2 3 15 0 1,2j f x x x x x x x x x x x x x x j                     THÀNH LẬP BÀI TOÁN ĐỐI NGẪU 1 2 3 1 2 3 1 2 3 1 2 3 1 3 ( ) 28 10 15 min 7 3 2 2 4 3 1 2 3 8 0, 0 Df y y y y y y y y y y y y y y y                     Bài toán đối ngẫu         1 1 2 3 2 1 2 3 1 2 3 1 1 2 3 3 0, 7 3 2 2 1 0, 4 3 1 2 7 4 2 28, 0 3 2 3 15, 0 4 x y y y x y y y x x x y x x x y                 Ví dụ 2.4. Viết bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu của bài toán QHTT Bài toán đối ngẫu 1 2 3 1 2 3 ( ) 4 3 8 min 1 0 1 2 0 1 2 5 0 1,3j f x x x x x x x x j                         THÀNH LẬP BÀI TOÁN ĐỐI NGẪU           1 1 2 2 3 1 2 1 3 1 2 3 2 0, 4 1 0, 3 2 0, 2 8 3 2, 0 4 2 5, 0 5 x y x y x y y x x y x x y              Các ràng buộc đối ngẫu 1 2 1 2 ( ) 2 5 max 1 0 4 0 1 3 1 2 8 0; 1, 2 D j f y y y y y y j                           Ví dụ 2.5. Viết bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu của bài toán QHTT THÀNH LẬP BÀI TOÁN ĐỐI NGẪU 1 2 1 2 ( ) 2 5 max 1 0 4 0 1 3 1 2 8 0; 1,2j f x x x x x x j                           Ràng buộc đối ngẫu           1 1 3 2 2 3 1 1 2 2 1 2 3 0, 2 1 0, 2 5 2 4, 0 3 3, 0 4 2 8, 0 5 x y y x y y x y x y x x y              1 2 3 1 2 3 ( ) 4 3 8 m in 1 0 1 2 0 1 2 5 0 1, 3 D j f y y y y y y y y j                         Bài toán đối ngẫu CÁC ĐỊNH LÝ ĐỐI NGẪU ĐỊNH LÝ 1. Nếu một trong hai bài toán đối ngẫu nhau có P.A.T.Ư thì bài toán kia cũng có P.A.T.Ư và giá trị hàm mục tiêu của chúng bằng nhau. HỆ QUẢ 1. Điều kiện cần và đủ để cho các bài toán đối ngẫu nhau có phương án tối ưu là mỗi bài toán có ít nhất một phương án. HỆ QUẢ 2. Điều kiện cần và đủ để cho các bài toán đối ngẫu nhau không có P.A.T.Ư là một bài toán có P.A còn bài toán kia không có P.A. ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 4 CÁC ĐỊNH LÝ ĐỐI NGẪU ĐỊNH LÝ 2.(ĐỊNH LÝ ĐỘ LỆCH BÙ YẾU) Điều kiện cần và đủ để cặp bài toán đối ngẫu nhau có P.A.T.Ư. là trong cặp ràng buộc đối ngẫu, nếu ràng buộc này xảy ra với dấu bất đẳng thức ngặt (“>” hoặc “<“) thì ràng buộc kia xảy ra với dấu đẳng thức. Nghĩa là, với Xopt = (x1 opt, x2 opt, ..., xn opt), Yopt = (y1 opt, y2 opt, ..., ym opt) lần lượt là P.A.T.Ư. của bài toán gốc và bài toán đối ngẫu, ta có  Nếu xj opt > 0 thì  Nếu thì yi opt = 0 1 m opt ij i j i a y c    , 1 n opt ij j i j a x b      CÁC ĐỊNH LÝ ĐỐI NGẪU ĐỊNH LÝ 3.(ĐỊNH LÝ ĐỘ LỆCH BÙ MẠNH) Nếu cặp bài toán đối ngẫu nhau có P.A.T.Ư. thì tồn tại một cặp phương án sao cho trong các cặp đối ngẫu, nếu ràng buộc này xảy ra với dấu đẳng thức thì ràng buộc kia xảy ra với dấu bất đẳng thức ngặt. Nghĩa là, với Xopt = (x1 opt, x2 opt, ..., xn opt), Yopt = (y1 opt, y2 opt, ..., ym opt) lần lượt là P.A.T.Ư. của bài toán gốc và bài toán đối ngẫu, ta có  Nếu xj opt = 0 thì tồn tại  Nếu thì tồn tại yi opt  0 (> hoặc <). 1 m opt ij i j i a y c        1 n opt ij j i j a x b   Ví dụ 2.6. Cho bài toán QHTT có P.A.T.Ư của bài toán đối ngẫu là yopt = (2, 3) và f(yopt) = 19. Hãy tìm P.A.T.Ư của bài toán trên. Bài toán đối ngẫu 1 2 3 1 2 3 ( ) 4 3 8 min 1 0 1 2 0 1 2 5 0, 1,3j f x x x x x x x x j                         ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU                         1 2 1 2 ( ) 2 5 max 1 0 4 0 1 3 1 2 8 Df y y y y y Các cặp ràng buộc đối ngẫu x1 ≥ 0 và y1 ≤ 4 (1) x2 ≥ 0 và y2 ≤ 3 (2) x3 ≥ 0 và y1 + 2y2 ≤ 8 (3) Thay yopt = (2, 3) vào các ràng buộc Từ (1): y1 = 2 < 4  x1 = 0 (định lý 2). Thay x1 = 0 vào hpt của bài toán gốc Vậy, P.A.T.Ư của bài toán gốc là xopt= (0,1,2) và f(xopt) = fD(yopt) = 19. ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU 2 3 0 1 0 1 2 0 1 2 5 x x                   3 2 3 2 3 2 1; 2 2 5 x x x x x        ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 5 Ví dụ 2.7. Cho bài toán QHTT Có P.A.T.Ư là xopt = (0,14, 6, 5) và f(xopt) = 54. Hãy tìm P.A.T.Ư của bài toán đối ngẫu. Bài toán đối ngẫu 1 2 3 4 1 2 3 4 1 3 4 1 3 4 ( ) 2 2 4 max 5 6 50 3 2 16 4 3 23 0 1,4j f x x x x x x x x x x x x x x x x j                   ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU 1 2 3 1 2 3 1 1 2 3 1 2 3 2 3 ( ) 5 0 1 6 2 3 m i n 5 3 4 2 2 3 1 6 2 4 0 ; 0 Df y y y y y y y y y y y y y y y y                      Các cặp ràng buộc đối ngẫu x1 ≥ 0 và 5y1 – 3y2 + 4y3 ≥ 2 (1) x2 ≥ 0 và y1 ≥ 2 (2) x3 ≥ 0 và y1 + y2 + 3y3 ≥ 1 (3) x4 ≥ 0 và 6y1 + 2y2 + y3 ≥ 4 (4) -3x1 + x3 + 2x4 ≥ 16 và y2 ≤ 0 (5) 4x1 + 3x3 + x4 ≤ 23 và y3 ≥ 0 (6) Thay xopt = (0, 14, 6, 5) vào các ràng buộc Từ (2): x2 = 14 > 0  y1 = 2. Từ (3): x3= 6 > 0  y1 + y2 + 3y3 = 1 Từ (4): x4= 5 > 0  6y1 + 2y2 + y3 = 4 Giải hệ phương trình trên, ta có y1 = 2; y2 = -23/5; y3 = 6/5. Vậy, P.A.T.Ư của bài toán đối ngẫu là yopt= (2, -23/5, 6/5) và fD(yopt) = 54. ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU Ví dụ 2.8. Cho bài toán QHTT Xét các vectơ sau X = (3, 0, 11, 0), Y = (2, 1, 8, 0), Z = (-4, 2, 0, 10) và T = (1, 2, 1, 2). Vectơ nào là P.A.T.Ư. của bài toán? Cách giải. 1. Kiểm tra các vectơ có phải là P.A hay không? 2. Viết bài toán đối ngẫu, 3. Kiểm tra các P.A có phải là P.A.T.Ư.? ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU 1 2 3 1 2 4 1 2 1 3 4 ( ) 2 3 5 3 3 2 0 1,4j f x x x x Max x x x x x x x x x j                      1. Kiểm tra trực tiếp, ta thấy X, Y, và T là P.A của bài toán. Vì Z không thỏa mãn các ràng buộc nên Z không là P.A của bài toán. 2. Bài toán đối ngẫu Ta có 7 cặp ràng buộc đối ngẫu ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU 1 2 3 1 2 3 1 2 3 1 3 1 2 3 ( ) 5 3 2 min 3 1 3 2 1 0 0; 0; 0 Df y y y y y y y y y y y y y y y                  ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 6 x1 ≥ 0 và y1 + y2 – 3y3 ≥ -1 (1) x2 ≥ 0 và 3y1 + y2 ≥ 2 (2) x3 ≥ 0 và y3 ≥ 1 (3) x4 ≥ 0 và – y1 + y3 ≥ 0 (4) x1 + 3x2 – x4 ≤ 5 và y1 ≥ 0 (5) x1 + x2 ≤ 3 và y2 ≥ 0 (6) -3x1 + x3 + x4 ≤ 2 và y3 ≥ 0 (7) 3. Kiểm tra X, Y, T là P.A.T.Ư  Giả sử X = (3, 0, 11, 0) là P.A.T.Ư của bài toán. Từ (1): x1 = 3 > 0  y1 + y2 – 3y3 = -1 Từ (3): x3=11 > 0  y3 = 1 Từ (5): 3 + 0 + 0 + 0 = 3 < 5  y1 = 0 Giải hệ phương trình, ta được X*= (0, 2, 1). ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU Dễ dàng kiểm tra vectơ X*= (0, 2, 1) thỏa các ràng buộc của bài toán đối ngẫu. Hơn nữa, fD(X *)= f(X)= 8 nên X là P.A.T.Ư. của bài toán gốc.  Do Y = (2, 1, 8, 0) là P.A của bài toán gốc và f(X) = f(Y)= 8 nên Y cũng là P.A.T.Ư.  Với T = (1, 2, 1, 2), ta có f(T)= 4  fmax = 8 Vậy T không phải là P.A.T.Ư. mà T chỉ là phương án của bài toán. ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU Ví dụ 2.9. Giải bài toán QHTT Bài toán đối ngẫu 1 2 3 1 2 3 ( ) 10 8 19 min 2 1 1 6 3 0 2 2 1 2 5 5 0 1,3j f x x x x x x x x j                                ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU 1 2 3 1 2 3 ( ) 6 2 5 max 2 3 1 10 1 0 2 8 1 2 5 19 0 1,3 D j f y y y y y y y y j                               Ví dụ 2.10 Đưa bài toán về dạng chính tắc bằng cách thêm 3 ẩn phụ y4 ≥ 0, y5 ≥ 0, y6 ≥ 0 Ta thấy bài toán cũng có dạng chuẩn. Sử dụng thuật giải đơn hình ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU 1 2 3 1 4 2 5 3 6 ( ) 6 2 5 max 2 3 1 10 1 0 2 8 1 2 5 19 0 1,6 D j f y y y y y y y y y y y j                                           ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 7 3 2  HỆ SỐ ẨN C.B P.A 1y 2y 3y 4y 5y 6y 6 2 5 0 0 0 4y 5y 6y 0 0 0 10 8 19 2 1 1 3 0 0 1 1 2 5 0 0  f x 0 6 2 5 0 0 0 2 0 0 01 1 1y 5y 6y 6 0 0 5 1 32 12 12 0 0 3 0 32 12 01 14 0 12 9 2 12 10  f x 30 0 7 2 3 0 0 ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU Bài toán có P.A.T.Ư yopt=(4, 0, 2) và f(yopt)= 34. P.A.T.Ư của bài toán gốc là HỆ SỐ ẨN C.B P.A 1y 2y 3y 4y 5y 6y 6 2 5 0 0 0 1y 3y 6y 6 5 0 4 1 2 0 32 12 0 2 0 1 1 13 023 5 0 5 0 1 13  f x 34 0 5 0 73 43 0 ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU GHI CHÚ 1 4 4 2 5 5 3 6 6 opt x b x x b x b             7 7 3 31 4 4 3 32 3 0 0 0 0 0 opt x x x x              Cách 2: dùng định lý đối ngẫu x1 ≥ 0 và 2y1 + 3y2 + y3 ≤ 10 (1) x2 ≥ 0 và y1 + 2y3 ≤ 8 (2) x3 ≥ 0 và y1 + 2y2 + 5y3 ≤ 19 (3) 2x1 + x2 + x3 ≥ 6 và y1 ≥ 0 (4) 3x1 + 2x3 ≥ 2 và y2 ≥ 0 (5) x1 + 2x2+ 5x3 ≥ 5 và y3 ≥ 0 (6) Ta có P.A.T.Ư của bài toán đối ngẫu yopt= (4,0,2) Từ (3): 4 +20 + 52 = 14 < 19  x3 = 0. Từ (4): y1 = 4 > 0  2x1 + x2 + x3 = 6 Từ (6): y3= 2 > 0  x1 + 2x2 + 5x3 = 5 Giải hệ phương trình, ta có PA.T.Ư của bài toán gốc là xopt = (7/3, 4/3, 0) và f(xopt) = 34. ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU GHI CHÚ. Chúng ta cũng có thể sử dụng quy tắc sau đây để tìm P.A.T.Ư của bài toán đối ngẫu: Với các ẩn cơ bản xj (j = 1, 2, ..., m) trong P.A.C.B đầu tiên lập thành ma trận đơn vị cấp m tương ứng với các j trong bảng cuối cùng. Trong Ví dụ 2.9, ẩn cơ bản đầu tiên của bài toán đối ngẫu là y4, y5 và y6 thì P.A.T.Ư của bài toán gốc (đối ngẫu của bài toán đối ngẫu) là Xopt = (7/3, 4/3, 0) và f(Xopt) = 34. ÁP DỤNG ĐỊNH LÝ ĐỐI NGẪU 1 1 1 2 2 2 opt m m m y c y c y y c                ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 8  Do Lemke G.E đề xuất năm 1954. Đây là thuật giải đơn hình được áp dụng vào bài toán đối ngẫu nhưng để tìm P.A.T.Ư cho bài toán gốc.  Thuật giải đơn hình đối ngẫu xuất phát từ một “phương án giả” thỏa các ràng buộc chính của bài toán (nghiệm đúng Ax = b) nhưng không thoả điều kiện ràng buộc về dấu (x  0), nghĩa là bảng đơn hình đầu tiên không có phần tử dương trong dòng mục tiêu (dòng cuối) nhưng lại có phần tử âm trong cột phương án.  Thuật giải này thường được áp dụng khi chưa biết P.A.C.B nào của bài toán gốc nhưng lại có sẵn một P.A.C.B của bài toán đối ngẫu. THUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪU Đúng bi ≥ 0,i? THUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪU Sai Đúng Sai Đúng LẬP BẢNG ĐƠN HÌNH ĐỐI NGẪU XÁC ĐỊNH PHƯƠNG ÁN MỚI Aån ra : Aån vào : P.A.T.Ư KẾT THÚC THUẬT GIẢI aij  0,j? BÀI TOÁN KHÔNG CÓ P.A.T.Ư BIẾN ĐỔI BẢNG ĐƠN HÌNH 0i i i b Minb x   0ij j j a ij Min x a   SỐ BƯỚC LẶP LÀ HỮU HẠN j ≤ 0,j? Sai THUẬT GIẢI ĐƠN HÌNH Ví dụ 2.10. Giải bài toán QHTT trong Ví dụ 2.9 bằng thuật giải đơn hình đối ngẫu. Đưa bài toán về dạng chính tắc, rồi sau đó nhân (–1) cho các ràng buộc đẳng thức, ta có bài toán dạng chính tắc như sau Xuất phát từ phương án giả X = (0,0,0,–6,–2,–5). Ta có bảng đơn hình đối ngẫu như sau THUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪU 1 2 3 1 2 3 4 1 3 5 1 2 3 6 ( ) 10 8 19 min 2 6 3 2 2 2 5 5 0, 1,6j f x x x x x x x x x x x x x x x x j                             THUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪU 10 x1 3 1 ½ ½ –½ 0 0 0 x5 7 0 3/2 –½ –3/2 1 0 0 x6 –2 0 –3/2 9/2 –½ 0 1 f(x) 30 0 –3 –14 –5 0 0 Hệ số Ẩn C.B P.A 10 8 19 0 0 0 x1 x2 x3 x4 x5 x6 0 x4 –6 –2 –1 –1 1 0 0 0 x5 –2 –3 0 –2 0 1 0 0 x6 –5 –1 –2 –5 0 0 1 f(x) 0 –10 –8 –19 0 0 0 ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 9 Vậy, P.A.T.Ư của bài toán là xopt = (7/3, 4/3, 0) và f(xopt) = 34. THUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪU Hệ số Ẩn C.B P.A 10 8 19 0 0 0 x1 x2 x3 x4 x5 x6 10 x1 7/3 1 0 2 –2/3 0 1/3 0 x5 5 0 0 4 –2 1 1 8 x3 4/3 0 1 –3 1/3 0 –2/3 f(x) 34 0 0 –23 –4 0 –2 GHI CHÚ. Đối với thuật giải đơn hình đối ngẫu, để tìm P.A.T.Ư của bài toán đối ngẫu Yopt, ta có biểu thức sau Trong Ví dụ 2.10, ẩn cơ bản đầu tiên của bài toán đối ngẫu là x4, x5 và x6 thì P.A.T.Ư của bài toán đối ngẫu là Yopt = (4, 0, 2) và f*(Yopt) = 34. THUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪU 1 1 1 2 2 2 opt m m m y c y c y y c                1 4 4 2 5 5 3 6 6 opt y c y y c y c             1 2 3 ( 4) 0 4 0 0 0 ( 2) 0 2 y y y                  Ví dụ 2.11. Dùng thuật giải đơn hình đối ngẫu để giải bài toán quy hoạch tuyến tính sau đây Xuất phát từ phương án giả X = (–2,0,0,–4,0,2,6). Ta có bảng đơn hình đối ngẫu THUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪU 1 2 3 4 5 1 2 5 2 3 4 5 3 5 6 2 3 5 7 ( ) 2 4 2 2 2 2 4 4 2 2 4 6 0, 1,7j f x x x x x x Min x x x x x x x x x x x x x x x j                               THUẬT GIẢI ĐƠN HÌNH ĐỐI NGẪU Hệ số Ẩn C.B P.A 2 –4 1 –1 2 0 0 x1 x2 x3 x4 x5 x6 x7 2 x1 –2 1 –2 0 0 –2 0 0 –1 x4 –4 0 4 1 1 –1 0 0 0 x6 2 0 0 2 0 –1 1 0 0 x7 6 0 1 1 0 4 0 1 f(x) 0 0 –4 –2 0 –5 0 0 2 x1 6 1 –10 –2 –2 0 0 0 –1 x5 4 0 –4 –1 –1 1 0 0 0 x6 6 0 –4 1 –1 0 1 0 0 x7 –10 0 17 5 4 0 0 1 f(x) 20 0 –24 –7 –5 0 0 0 Do a4j  0, j = 1,..., 7 nên bài toán trên không có P.A.T.Ư. ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 10 1. TÌM PHƯƠNG ÁN TỐI ƯU MỚI KHI CÓ THÊM RÀNG BUỘC VÀO BÀI TOÁN (XEM) 2. TÌM NGHIỆM KHÔNG ÂM CỦA HỆ PHƯƠNG TRÌNH TUYẾN TÍNH BẰNG THUẬT GIẢI ĐƠN HÌNH MỞ RỘNG (XEM) 3. Ý NGHĨA KINH TẾ CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU (XEM) MỘT SỐ ỨNG DỤNG CỦA LÝ THUYẾT ĐỐI NGẪU TRONG BÀI TOÁN QHTT Ví dụ 2.12. a) Dùng thuật giải đơn hình đối ngẫu để giải bài toán quy hoạch tuyến tính sau đây b) Nếu thêm một ràng buộc nữa x1 + x2 + x3  60 vào bài toán trên, tìm phương án tối ưu của bài toán mới. MỘT SỐ ỨNG DỤNG CỦA LÝ THUYẾT ĐỐI NGẪU TRONG BÀI TOÁN QHTT 1 2 3 1 2 3 1 2 3 ( ) 15 12 10 3 4 2 160 2 3 140 0, 1,3j f x x x x Min x x x x x x x j                 Đưa bài toán về dạng chính tắc, rồi sau đó nhân (–1) cho các ràng buộc đẳng thức, ta có bài toán dạng chính tắc như sau a) Xuất phát từ phương án giả X = (0, 0, 0, –160, –140. Ta có bảng đơn hình đối ngẫu MỘT SỐ ỨNG DỤNG CỦA LÝ THUYẾT ĐỐI NGẪU TRONG BÀI TOÁN QHTT 1 2 3 1 2 3 4 1 2 3 5 ( ) 15 12 10 3 4 2 160 2 3 140 0, 1,5j f x x x x Min x x x x x x x x x j                       MỘT SỐ ỨNG DỤNG LÝ THUYẾT ĐỐI NGẪU 12 x2 40 ¾ 1 ½ –¼ 0 0 x5 –60 ½ 0 –2 –½ 1 f(x) 480 –6 0 –4 –3 0 12 x2 25 7/8 1 0 –3/8 ¼ 10 x3 30 –¼ 0 1 ¼ –½ f(x) 600 –7 0 0 –2 –2 P.A.T.Ư là xopt = (0, 25, 30) và f(xopt) = 600. Hệ Số Ẩn C.B P.A 15 12 10 0 0 x1 x2 x3 x4 x5 0 x4 –160 –3 –4 –2 1 0 0 x5 –140 –1 –2 –3 0 1 f(x) 0 –15 –12 –10 0 0 ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 11 b) Do xopt = (0, 25, 30) không thỏa ràng buộc x1 + x2 + x3  60 nên xopt không phải là phương án của bài toán mới. Để xử lý ràng buộc mới này, ta đưa ràng buộc bất đẳng thức về ràng buộc đẳng thức bằng cách thêm ẩn phụ x6  0, ta được –x1 – x2 – x3 + x6 = –60. Sử dụng bảng cuối cùng trong câu a) và đưa ràng buộc mới –x1 – x2 – x3 + x6 = –60 vào bảng trên. Lưu ý ẩn x6 là ẩn cơ bản trong bài toán mới, còn x4 và x5 là ẩn cơ bản trong bài toán cũ nên trong ma trận hệ số của bài toán mới ta cộng dòng 1 và dòng 2 vào dòng 3 để vectơ cột ứng với x4 và x5 là các vectơ đơn vị. MỘT SỐ ỨNG DỤNG CỦA LÝ THUYẾT ĐỐI NGẪU TRONG BÀI TOÁN QHTT MỘT SỐ ỨNG DỤNG LÝ THUYẾT ĐỐI NGẪU 12 x2 25 7/8 1 0 –3/8 ¼ 0 10 x3 30 –¼ 0 1 ¼ –½ 0 0 x6 –5 –3/8 0 0 –1/8 –¼ 1 f(x) 600 –7 0 0 –2 –2 0 Hệ số Ẩn C.B P.A 15 12 10 0 0 0 x1 x2 x3 x4 x5 x6 12 x2 25 7/8 1 0 –3/8 ¼ 0 10 x3 30 –¼ 0 1 ¼ –½ 0 0 x6 –60 –1 –1 –1 0 0 1 f(x) 600 –7 0 0 –2 –2 0 MỘT SỐ ỨNG DỤNG LÝ THUYẾT ĐỐI NGẪU P.A.T.Ư là x/opt = (0, 20, 40) và f(x / opt) = 640. Hệ số Ẩn C.B P.A 15 12 10 0 0 0 x1 x2 x3 x4 x5 x6 12 x2 20 ½ 1 0 –½ 0 1 10 x3 40 ½ 0 1 ½ 0 –2 0 x5 20 3/2 0 0 ½ 1 –4 f(x) 640 –4 0 0 –1 0 –8 Tìm nghiệm không âm của hệ phương trình tuyến tính AX = b, X  0 (1), trong đó A là ma trận mn, bm có thể quy về giải bài toán quy hoạch tuyến tính  Bài toán (2) luôn luôn có P.A.T.Ư vì (0,b) là một P.A và hàm mục tiêu bị chặn [f(x)  0].  Giả sử P.A.T.Ư của bài toán trên là (xopt, x g opt), nếu xgopt = 0, j thì xopt là nghiệm của bài toán (1). Ngược lại nếu tồn tại xgj  0 thì bài toán (1) vô nghiệm. TÌM NGHIỆM KHÔNG ÂM CỦA HỆ PHƯƠNG TRÌNH TUYẾN TÍNH     1 min 2 0, 0, 0 m g j j g g f x M x AX X b X X M          ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 12 Ví dụ 2.1.Tìm nghiệm không âm của hệ phương trình tuyến tính Ta có thể quy bài toán trên về bài toán QHTT Giải bài toán trên, ta được P.A.T.Ư là (xopt, x g opt) = (3, 1, 2, 0, 0, 0). Vậy nghiệm không âm của hệ phương trình tuyến tính trên là x = (3, 1, 2). TÌM NGHIỆM KHÔNG ÂM CỦA HỆ PHƯƠNG TRÌNH TUYẾN TÍNH 1 2 3 1 2 3 1 2 3 2 3 7 2 4 9 3 2 4 x x x x x x x x x             4 5 6 1 2 3 4 1 2 3 5 1 2 3 6 ( ) 2 3 7 2 4 9 3 2 4 0, 1,6j f x M x x x Min x x x x x x x x x x x x x j                         Xét bài toán gốc là bài toán khẩu phần thức ăn Chất dinh dưỡng (%) Thức ăn Mức dinh dưỡng tối thiểu 1 2 ... j ... n 1 a11 a12 ... a1j ... a1n b1 2 a21 a22 ... a2j ... a2n b2 ... ... ... ... ... ... ... ... i ai1 ai2 ... aij ... ain bi ... ... ... ... ... ... ... ... m am1 am2 ... amj ... amn bm Giá một đơn vị thức ăn c1 c2 ... cj ... cn Ý NGHĨA KINH TẾ CỦA BÀI TOÁN ĐỐI NGẪU Gọi xj (j = 1, 2, ..., n) là số đơn vị thức ăn trong mỗi bửa, ta có mô hình bài toán QHTT như sau Bài toán đối ngẫu Chất dinh dưỡng thay thế: nhà sản xuất thuốc bổ tương ứng với các chất dinh dưỡng trên. Ý NGHĨA KINH TẾ CỦA BÀI TOÁN ĐỐI NGẪU   1 1 2 2 1 1 2 2 min , 1, 0, 1, n n i i in n i j f x c x c x c x a x a x a x b i m x j n                    1 1 2 2 1 1 2 2 max , 1, 0, 1, D m m j j mj m j i f y b y b y b y a y a y a y c j n y i m                 Gọi yi là giá bán một viên thuốc bổ có chứa chất dinh dưỡng i (i = 1, 2, ..., m). Người chăn nuôi sẽ phải lựa chọn:  Mua thuốc bổ, nếu a1jy1 + a2jy2 +... + anjyn < cj. Vì giá thuốc bổ rẻ hơn và lúc này xj = 0 (định lý độ lệch bù yếu).  Mua thức ăn, theo định lý độ lệch bù yếu, nếu yi > 0 thì ai1x1 + ai2x2 + + ainxn = bi, Nghĩa là, nếu giá một viên thuốc bổ khá cao thì người chăn nuôi sẽ mua các loại thức ăn sao cho thoả nhu cầu tối thiểu của chất dinh dưỡng. Vậy, khi phân tích cặp bài toán đối ngẫu nhau chính là phân tích tính T.Ư của từng bài toán. Ý NGHĨA KINH TẾ CỦA BÀI TOÁN ĐỐI NGẪU ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 13 Th.s Nguyễn Công Trí Copyright 2001 BÀI TẬP CHƯƠNG 2 LẬP BÀI TOÁN ĐỐI NGẪU [1a] [1b] [2] SỬ DỤNG ĐỊNH LÝ ĐỐI NGẪU [3] [4] [5] [6] PHƯƠNG PHÁP ĐƠN HÌNH ĐỐI NGẪU [7a] [7b] 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 2 3 ( ) 8 4 max 2 4 2 5 4 3 3 3 2 0, 0 Df y y y y y y y y y y y y y y y y y y                            BÀI TẬP CHƯƠNG 2 1.a) Viết bài toán đối ngẫu của bài toán QHTT Bài toán đối ngẫu 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 3 4 ( ) 4 4 3 2 min 2 1 2 3 8 5 3 4 0, 0, 0 f x x x x x x x x x x x x x x x x x x x x                          1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 3 ( ) 10 8 9 min 2 2 3 2 2 4 2 5 0, 0 Df y y y y y y y y y y y y y y y y y y                           1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 2 3 4 ( ) 2 3 4 5 max 2 2 10 2 8 2 9 0, 0, 0 f x x x x x x x x x x x x x x x x x x x x                         BÀI TẬP CHƯƠNG 2 1.b) Viết bài toán đối ngẫu của bài toán QHTT Bài toán đối ngẫu BÀI TẬP CHƯƠNG 2 2. Chứng minh bài toán QHTT sau đây trùng với bài toán đối ngẫu của nó (Bài toán tự đối ngẫu). 1 2 3 2 3 1 3 1 2 1 2 3 ( ) min 1 1 1 0, 0 0, f x x x x x x x x x x x x x                      ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 14 BÀI TẬP CHƯƠNG 2 3. Cho bài toán QHTT sau đây: a) Viết bài toán đối ngẫu của bài toán trên. b) Giải bài toán gốc, suy ra lời giải của bài toán đối ngẫu. 1 2 3 4 1 2 4 2 4 2 3 4 ( ) 2 4 max 3 1 5 2 3 4 3 0 1,4j f x x x x x x x x x x x x x x j                 BÀI TẬP CHƯƠNG 2 a) Bài toán đối ngẫu b) Giải bài toán gốc, ta được P.A.T.Ư là xopt = (1, 0, 3/4, 0), fmax= 11/4 Các cặp đối ngẫu x1  0 và y1  2 (1) x2  0 và 3y1 – 5y2 + y3  4 (2) x3  0 và + 4y3  1 (3) x4  0 và y1 – 2y2 + y3  1 (4) -5x2 – 2x4 ≤ 3 và y2  0 (5) Giải hpt (1), (3) và (5), ta được yopt = (2, 0, 1/4) và fD(yopt)= 11/4              1 2 3 1 1 2 3 3 1 2 3 2 ( ) 3 3 min 2 3 5 4 4 1 2 1 0 Df y y y y y y y y y y y y y BÀI TẬP CHƯƠNG 2 4. Cho bài toán QHTT sau đây: a) Viết bài toán đối ngẫu của bài toán trên. b) Giải bài toán đối ngẫu, suy ra lời giải của bài toán gốc.                1 2 3 1 2 3 1 2 3 1 2 3 ( ) 12 27 6 min 2 3 2 12 3 6 6 9 2 24 0 1,3j f x x x x x x x x x x x x x x j BÀI TẬP CHƯƠNG 2 5. Cho bài toán QHTT a) Viết bài toán đối ngẫu của bài toán trên. b) Phân tích các tính chất (P.A.C.B suy biến hay không suy biến) của vectơ X = (0, 1, 0, 2, 0). c) Cho biết X là P.A.T.Ư của bài toán gốc và f(X) = 5. Tìm P.A.T.Ư. của bài toán đối ngẫu. 1 2 3 4 5 1 2 3 4 5 1 3 4 5 1 2 3 5 ( ) 5 9 15 7 6 min 3 1 4 2 4 2 1 0 2,5j f x x x x x x x x x x x x x x x x x x x x j                        ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 15 BÀI TẬP CHƯƠNG 2 a) Bài toán đối ngẫu b) Kiểm tra trực tiếp, ta thấy X = (0, 1, 0, 2, 0) là P.A và X thỏa 5 ràng buộc chặt, dễ dàng kiểm tra hpt ràng buộc có hạng khác 5, nên X không là P.A.C.B. c) Chỉ ra 6 cặp đối ngẫu, từ đó áp dụng định lý đối ngẫu, ta có P.A.T.Ư của bài toán đối ngẫu là Yopt = [(y3 – 9)/3, (y3 + 12)/6, y3], với y3 ≥ 0, y1 ≤ 0.                       1 2 3 1 2 3 1 3 1 2 3 1 2 1 2 3 1 3 ( ) 4 max 4 5 3 9 15 2 7 2 6 0, 0 Df y y y y y y y y y y y y y y y y y y y BÀI TẬP CHƯƠNG 2 6. Cho bài toán QHTT Cho các vectơ: X = (-1, 2, 3, 4); Y = (0, 2, 1, 3); Z = (0, 0, 0, 8), T = (14, 0, 0, 1); S = (18, 2, 0, 0) Trong các vectơ trên, vectơ nào là phương án tối ưu của bài toán? Hãy giải thích. 1 2 3 4 1 2 3 4 1 2 3 1 2 3 4 ( ) 3 7 2 max 2 3 2 30 2 2 3 60 2 2 3 4 32 0 1,4j f x x x x x x x x x x x x x x x x x j                   BÀI TẬP CHƯƠNG 2 1. Kiểm tra trực tiếp X, Y không phải là phương án. Các vectơ Z, T, S là các phương án vì chúng thỏa các ràng buộc của bài toán. 2. Bài toán đối ngẫu Các cặp ràng buộc đối ngẫu x1 ≥ 0 và 2y1 + 2y2 + 2y3 ≥ 3 (1) x2 ≥ 0 và –3y1 – 2y2 – 2y3 ≥ –7 (2) x3 ≥ 0 và – y1 + 3y2 – 3y3 ≥ 1 (3) x4 ≥ 0 và 2 y1 + 4y3 ≥ –2 (4) 2x1 – 3x2 – x3 + 2x4 ≤ 30 và y1 ≥ 0 (5) 2x1 – 2x2 + 3x3 ≤ 60 và y2 ≥ 0 (6) 1 2 3 1 2 3 1 2 3 1 2 3 1 3 1 2 ( ) 30 60 32 min 2 2 2 3 3 2 2 7 3 3 1 2 4 2 0, 0 Df y y y y y y y y y y y y y y y y y                           BÀI TẬP CHƯƠNG 2 3. Kiểm tra tính tối ưu của các phương án  Xét phương án Z = (0, 0, 0, 8), giả sử Z là P.A.T.Ư. của bài toán gốc, ta có f(Z) = –16. Từ (4): z4 = 8  2 y1 + 4y3 = –2 Từ (5): 2x1 – 3x2 – x3 + 2x4 = 16 < 30  y1 = 0 Từ (6): 2x1 – 2x2 + 3x3 = 0 < 60  y2 = 0 P.A.T.Ư. của bài toán đối ngẫu sẽ là Z*= (0, 0,–½), nhưng Z* không thỏa ràng buộc của bài toán đối ngẫu nên Z* không thể là P.A.T.Ư. Vậy, Z không thể là P.A.T.Ư. của bài toán gốc.  Tương tự, giả sử T = (14, 0, 0, 1) là P.A.T.Ư. của bài toán gốc ta có f(T) = 40. ThS. Nguyễn Cơng Trí - Tối ưu hĩa * Chương 2 16 BÀI TẬP CHƯƠNG 2 Từ (1): t1 = 14  2y1 + 2y2 + 2y3 = 3 Từ (4): t4 = 1  2 y1 + 4y3 = –2 Từ (6): 2x1 – 2x2 + 3x3 = 28 < 60  y2 = 0 Giải hệ phương trình trên, ta có P.A.T.Ư. của bài toán đối ngẫu sẽ là T*= (4, 0,–5/2). Dễ dàng kiểm tra T* thỏa các ràng buộc của bài toán đối ngẫu nên T* là P.A.T.Ư. của bài toán đối ngẫu. Hơn nữa, fD(T *) = f(T) = 40 Vậy, T là P.A.T.Ư. của bài toán gốc.  Xét phương án S = (18, 2, 0, 0), ta có f(S) = 40 = f(T). Vậy, S là P.A.T.Ư. của bài toán gốc. BÀI TẬP CHƯƠNG 2 7. a) Dùng PPĐHĐN giải bài toán QHTT sau đây, từ đó suy ra lời giải của bài toán đối ngẫu 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 ( ) 3 2 min 2 2 10 2 8 9 0, 0, 0, 0 f x x x x x x x x x x x x x x x x x x x x x                          BÀI TẬP CHƯƠNG 2 7. b) Dùng PPĐHĐN giải bài toán QHTT sau đây, từ đó suy ra lời giải của bài toán đối ngẫu 1 2 3 4 1 2 2 3 2 4 1 2 3 4 ( ) 2 6 3 max 1 4 2 0, 0, 0, 0 f x x x x x x x x x x x x x x x                       