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

10/26/2012 1 Bài giảng QUY HOẠCH TUYẾN TÍNH ThS. Nguyeãnããã Vaênêêê Phong Email : nvphong1980@gmail.com, nv.phongbmt@ufm.edu.vn ĐẠI HỌC TÀI CHÍNH – MARKETING BỘ MÔN TOÁN – KHOA CƠ BẢN 2 Chương 2. BÀI TOÁN ĐỐI NGẪU 1. KHÁI NIỆM - THÀNH LẬP BÀI TOÁN ĐỐI NGẪU 2. CÁC ĐỊNH LÝ ĐỐI NGẪU 3. THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê 3 KHÁI NIỆM – THÀNH LẬP QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê Tùy thuộc vào dạng của bài toán QHTT gốc (P) khi đó ta xây dựng bài toán đối ngẫu (D) như sau Gốc (P) Đối ngẫu (D) Ràng Buộc Dấu Dấu RàngBuộc min ,c x max ,b y 1, , i ia x b i M= ∈ 2, , i ia x b i M≤ ∈ 3, , i ia x b i M≥ ∈ töï do, 1iy i M∈ 20,iy i M≤ ∈ 30,iy i M≥ ∈ 10,jx j N≥ ∈ 20,jx j N≤ ∈ töï do, 3jx j N∈ 3, ,j jA y c j N= ∈ 2, ,j jA y c j N≥ ∈ 1, ,j jA y c j N≤ ∈ 1 2 3 1 2 3,M M M m N N N n+ + = + + = 10/26/2012 2 4 KHÁI NIỆM – THÀNH LẬP QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê QUAN HỆ GIỮA BT (P) VÀ BT (D) như sau - Mục tiêu của hai bài toán thì đối ngẫu (min ↔ max) - Số ràng buộc của (P) bằng với số ẩn của (D) - Số ẩn của (P) bằng với số ràng buộc của (D) - Dấu của ẩn của (P) và Dấu ràng buộc của (D) thì trái dấu. QUY TẮC: RÀNG BUỘC RÀNG BUỘC RÀNG BUỘC DẤU DẤU MINMAXMIN 5 CÁC ĐỊNH LÝ ĐỐI NGẪU QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê 1. Định lý đối ngẫu (Yếu). Nếu x là một PACNĐ bất kỳ của (P) và y là một PACNĐ bất kỳ của (D), thì , ,b y c x≤ 2. Hệ quả. Giả sử x là một PACNĐ của (P) và y là một PACNĐ của (D), và . Khi đó x là PATƯ của (P) và y PATƯ của (D) , ,b y c x= 3. Định lý đối ngẫu (Mạnh). Nếu một bài toán có PATU thì bài toán đối ngẫu của nó cũng có PATU và giá trị TU của hai hàm mục tiêu bằng nhau. Chứng minh. Trước hết ta nhắc lại một số ký hiệu sau Baøi toaùn (P) , min 0 f c x Ax b x = → = ≥ Baøi toaùn (D) töï do , max T g b y A y c y = → ≤ 6 CÁC ĐỊNH LÝ ĐỐI NGẪU QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê { } { } { } Giaû söû laø PATU cuûa (P), ta coù Khi ñoù, ta coù vaø f Vaø vì laø PATU neân hay * * * * * * * * * * * * * 1 * * 1 min * * 1 * 1 , ( ) , , ( ) , , ( ) ( ) ( ) ( ) ( ) 0, ( ) j j jB B B B k k kB TT B x B A j J x C c j J x X x j J x X B b f x C B b x C B A c k A C B c − − − − = ∈ = ∈ = ∈ = = = ∆ = − ≤ ∀   − ≤  Ta ñaët thì (y laø ACNÑ cuûa (D)) Hôn nöõa ñpcm * * * * * * 1 * * * * * 1 * 0 ( ) , ( ) , ( ) T T B T B B B y C B A y c b y y b C B b C X c x − −  = ≤   = = = =  10/26/2012 3 7 CÁC ĐỊNH LÝ ĐỐI NGẪU QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê 4. Định lý độ lệch bù. Giả sử x là PACNĐ của (P), y là PACNĐ của (D). Khi đó x là PATU của (P) và y là PATU của (D), nếu và chỉ nếu , 0 , 0T Ax b y c A y x  − =  − = Áp dụng. ( ) ( ) Vì neân ñònh lyù ñöôïc vieát laïi nhö sau0, 0 0 , ( ) : , 0, , 0 0 0 , ( ) : , 0, , 0 0 i i ii i i i i i j j j j j j j j j x y y a x b I a x b y i a x b y x A y c II c y A x j c y A x ≥ ≥  > ⇒ =  − = ∀ ⇔  − > ⇒ =  > ⇒ =  − = ∀ ⇔  − > ⇒ = 8 THUẬT TOÁN ĐỐI NGẪU QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê 1. Hệ phương trình đối ngẫu. Xét hai hệ sau 11 1 1 1 1 1 1 1 1 1 1 1 ... ... ... ... ... ... ... ... ... ... ... ... i i n n n j ji i jn n n j j m mi i mn n n m m i i n n a x a x a x x b a x a x a x x b a x a x a x x b c x c x c x f α + + + + + + + + =   + + + + + =    + + + + + =  + + + + + = Hệ (II) Hệ (I) 11 1 1 1 1 1 1 1 1 1 1 1 ... ... ... ... ... ... ... ... j j m m m i ji j mi m m i i n jn j mn n m n n j j m m a y a y a y y c a y a y a y y c a y a y a x y c b y b y b y g α + + + − − − − − + =   − − − − − + =    − − − − − + =  − − − − − + = − 9 THUẬT TOÁN ĐỐI NGẪU QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê Hệ (I), (II) được gọi là đối ngẫu, nếu - Hệ số các ẩn tự do trong phương trình thứ j của hệ (I) và hệ số của ẩn tự do thứ j của hệ (II) (hệ số của yj trong các phương trình của hệ (II)) thì đối nhau. - Số hạng tự do của hệ (I) và hệ số các ẩn tự do của phương trình cuối hệ (II) thì đối nhau. - Số hạng tự do của hệ (II) và hệ số các ẩn tự do của phương trình cuối hệ (I) thì bằng nhau. - Số hạng tự do phương trình cuối trong hai hệ thì đối nhau. Khi đó, ta có sự tương quan giữa các ẩn tự do của hệ này với các ẩn cơ sở của hệ kia, như sau 10/26/2012 4 10 THUẬT TOÁN ĐỐI NGẪU QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê 2. Hai bài toán đối ngẫu Từ định lý đối ngẫu mạnh, ta có nhận xét sau: - Nếu trong BT (P) (min), ta chuyển từ B tới B* (TU), - Sau đó ta thực hiện một phép biến đổi cơ sở tương ứng trong BT (D) cũng tối ưu. - Khi đó, nghiệm cơ sở TU của BT (D) được xác định như sau : - Giả sử cơ sở tối ưu của bài toán min là {x1, x2, ,xn} , {xn+1, xn+2, ,xn+m}, là các ẩn tự do mà đối với cơ sở này bài toán min đạt cực tiểu. - Cơ sở tương ứng của bài toán đối ngẫu là {y1, y2, ,ym} , {ym+1, ym+2, ,ym+n}, là các ẩn tự do. - Khi đó, hai BT này tạo thành hai hệ phương trình đối ngẫu. 11 THUẬT TOÁN ĐỐI NGẪU QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê 2. Hai bài toán đối ngẫu Từ định lý đối ngẫu mạnh, ta có nhận xét sau: - Nếu trong BT (P) (min), ta chuyển từ B tới B* (TU), - Sau đó ta thực hiện một phép biến đổi cơ sở tương ứng trong BT (D) (max) cũng tối ưu. - Khi đó, nghiệm cơ sở TU của BT (D) được xác định như sau: - Giả sử cơ sở tối ưu của bài toán min là {x1, x2, ,xn} , các ẩn {xn+1, xn+2, ,xn+m}, là các ẩn tự do mà đối với cơ sở này bài toán min đạt cực tiểu. - Cơ sở tương ứng của bài toán đối ngẫu là {y1, y2, ,ym} , các ẩn {ym+1, ym+2, ,ym+n}, là các ẩn tự do. - Khi đó, hai BT này tạo thành hai hệ phương trình đối ngẫu. Và các ẩn của chúng có quan hệ như trong phần 1. 12 THUẬT TOÁN ĐỐI NGẪU QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê 2. Hai bài toán đối ngẫu Và nghiệm của bài toán (D) được xác định như sau: Chú ý. Ta thấy trong cặp bài toán đối ngẫu nhau chỉ xảy ra một trong ba trường hợp sau : * Trường hợp 1. Cả hai bài toán cùng có phương án thì cả hai bài toán cùng có phương án tối ưu. * Trường hợp 2. Bài toán này có phương án, bài toán kia không có phương án thì cả hai bài toán không có phương án tối ưu. * Trường hợp 3. Cả hai bài toán không có phương án thì hiển nhiên cả hai không có phương án tối ưu. 1 1 1 1 ... ... ... ... ... ... n m m m m n n y c y c y c y c + + +  =    =  =   = Trong đó, các cj là các hệ số của các ẩn trong hàm mục tiêu ở bảng đơn hình TU 10/26/2012 5 13 THUẬT TOÁN ĐỐI NGẪU QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê 3. Thuật toán đơn hình đối ngẫu Nghĩa là: Ta dùng thuật toán đơn hình trên bài toán đối ngẫu và sử dụng mối quan hệ giữa các ẩn của hai bài toán đê suy ra nghiệm cho bài toán gốc và ngược lại. Ví dụ. Tìm nghiệm của bài toán sau bằng thuật toán đơn hình đối ngẫu. 1 2 3 1 2 3 1 2 3 1 2 3 2 3 max 2 3 1 2 1 , , 0. f y y y y y y y y y y y y = − − − → − + − ≤  − − ≤ − ≥ 1 2 1 2 1 2 1 2 1 2 min 2 1 2 2 3 3 , 0. g x x x x x x x x x x = − → − + ≥ −  − ≥ −  − − ≥ − ≥ BT (P) BT (D) 14 THUẬT TOÁN ĐỐI NGẪU QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê 3. Thuật toán đơn hình đối ngẫu Trước tiên, ta viết hai bài toán này thành hai hệ đối ngẫu. 1 2 3 4 1 2 3 5 1 2 3 2 3 1 2 1 2 3 0 y y y y y y y y y y y f − + − + =  − − + = −  + + + = 1 2 3 1 2 4 1 2 5 1 2 2 1 2 2 3 3 0 x x x x x x x x x x x g − + =  − + + =  + + =  − + + = BT (P) BT (D) 15 THUẬT TOÁN ĐỐI NGẪU QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê Đối với (D), ta chuyển về dạng chuẩn như sau ( )1 2 1 2 1 2 3 1 2 4 1 2 5 1 2 3 4 5 min 0 2 1 2 2 3 3 , , , , 0. g x x g x x x x x x x x x x x x x x x x = − → − + = − + =  − + + =  + + = ≥ Và lập bảng đơn hình Hệ số CB Cơ sở B Phương án 1 -1 0 0 0 θ A1 A2 A3 A4 A5 0 A3 1 1 -2 1 0 0 0 A4 2 -2 1 0 1 0 0 A5 3 3 1 0 0 1 g 0 -1 1 0 0 0 10/26/2012 6 16 THUẬT TOÁN ĐỐI NGẪU QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê Đối với (D), ta chuyển về dạng chuẩn như sau ( )1 2 1 2 1 2 3 1 2 4 1 2 5 1 2 3 4 5 min 0 2 1 2 2 3 3 , , , , 0. g x x g x x x x x x x x x x x x x x x x = − → − + = − + =  − + + =  + + = ≥ Và bảng đơn hình TU là Hệ số CB Cơ sở B Phương án 1 -1 0 0 0 θ A1 A2 A3 A4 A5 0 A3 28/5 0 0 1 7/5 3/5 0 A2 12/5 0 1 0 3/5 2/5 0 A1 1/5 1 0 0 -1/5 -1/5 g -11/5 0 0 0 -4/5 -1/5 17 THUẬT TOÁN ĐỐI NGẪU QUY HOAÏCH TUYEÁN TÍNHÏ ÁÏ ÁÏ Á NGUYEÃN VAÊN PHONGÃ ÊÃ ÊÃ Ê Ta có quan hệ giữa các ẩn như sau 1 2 3 4 5 4 5 1 2 3 x x x x x y y y y y Vậy nghiệm tối ưu của bài toán gốc là 1 2 3 4 50, 4 / 5, 1/ 5, 0, 0y y y y y= = = = =