Bài giảng Tối ưu hóa - Chương 2: Bài toán quy hoạch đối ngẫu - Nguyễn Công Trí

. 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. 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 THÀØNH LẬÄP BÀØI TOÁÙN ĐỐÁI NGẪUà 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 Ví dụï 2.1. Bàøi toáùn đốái ngẫu cuã ûûa bàøi toáùn QHTT sau đâyâ làø bàøi toáùn THÀØNH LẬÄP BÀØI TOÁÙN ĐỐÁI NGẪUà 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 ÝØJLỊÙ ỵỉ ÞßH× ÌĐßGỊ OĐ_× ỊÙß]Ë ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ N uy ễn C ôn g T í PDF created with pdfFactory Pro trial version www.pdffactory.com VD2.2 VD2.3 VD2.4 VD2.5 VD2.6 VD2.7 THÀØNH LẬÄP BÀØI TOÁÙN ĐỐÁI NGẪUà ẨÅn thứù iẨÅn thứù j Ràøng buộäc thứù jRàøng buộäc thứù i Hàøm mụïc tiêuâHàøm mụïc tiêuâ Bàøi toáùn đốái ngẫuã (D)Bàøi toáùn gốác (P) 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 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 m in 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à 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 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 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ã ĐỊ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 cuâ ûû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. CÁÙC ĐỊNH LÝÙ ĐỐÁI NGẪUà ÝØJLỊÙ ỵỉ ÞßH× ÌĐßGỊ OĐ_× ỊÙß]Ë ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng ye ãn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com ĐỊ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 = (x1opt, x2opt, ..., xnopt), Yopt = (y1opt, y2opt, ..., ymopt) 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 xjopt > 0 thì Nếáu thì yiopt = 0 CÁÙC ĐỊNH LÝÙ ĐỐÁI NGẪUà 1 m opt ij i j i a y c , 1 n opt ij j i j a x b ĐỊ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 = (x1opt, x2opt, ..., xnopt), Yopt = (y1opt, y2opt, ..., ymopt) 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 xjopt = 0 thì tồàn tạïi Nếáu thì tồàn tạïi yiopt 0 (> hoặëc <). CÁÙC ĐỊNH LÝÙ ĐỐÁI NGẪUà 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ãỹ 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 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ãỹ 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à ÝØJLỊÙ ỵỉ ÞßH× ÌĐßGỊ OĐ_× ỊÙß]Ë ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com 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 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 jVí 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 ÝØJLỊÙ ỵỉ ÞßH× ÌĐßGỊ OĐ_× ỊÙß]Ë ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com 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 3 2 12 12 0 0 3 0 3 2 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 3 2 12 0 2 0 1 1 13 02 3 5 0 5 0 1 13 f x 34 0 5 0 7 3 4 3 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 yã opt= (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 cuâ ûû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 cuã ûû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 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à Đúùngbi 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, i? BÀØI TOÁÙN KHÔNG CÓÙ P.A.T.Ư BIẾÁN ĐỔÅI BẢÛNG ĐƠN HÌNH 0i i ib Minb x 0ij j ja 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 ÝØJLỊÙ ỵỉ ÞßH× ÌĐßGỊ OĐ_× ỊÙß]Ë ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng ye ãn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com 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à 00–5–14–3030f(x) 10–½9/2–3/20–2x60 01–3/2 –½3/207x50 00–½½½13x110 000–19–8–100f(x) 100–5–2–1–5x60 010–20–3–2x50 001–1–1–2–6x40 x6x5x4x3x2x1 00019810P.AẨÅn C.B Hệä sốá 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à –20–4–230034f(x) –2/301/3–3104/3x38 11–24005x50 1/30–2/32017/3x110 x6x5x4x3x2x1 00019810P.AẨÅn C.B Hệä sốá 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 Yã opt, ta cóù biểåu thứùc sau Trong Ví dụï 2.10, ẩån cơ bảûn đầàu tiên cuâ ûû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 = (0, 0, 0, –6, –2, –5) 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à 00–50–2–400f(x) 10401106x70 01–102002x60 00–11140–4x4–1 00–200–21–2x12 x7x6x5x4x3x2x1 002–11–42P.AẨÅn C.B Hệä sốá 000–5–7–24020f(x) 10045170–10x70 010–11–406x60 001–1–1–404x5–1 000–2–2–1016x12 Do a4j 0, j = 1,..., 7 nên bâ øøi toáùn trên â không cô ùù P.A.T.Ư. ÝØJLỊÙ ỵỉ ÞßH× ÌĐßGỊ OĐ_× ỊÙß]Ë ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com 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 CU  ÛÛ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 xõ 1 + 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à 0–3–40–6480f(x) 1–½–20½–60x50 0–¼½1¾40x212 –2–200–7600f(x) –½¼10–¼30x310 ¼–3/8017/825x212 P.A.T.Ư làø xopt = (0, 25, 30) vàø f(xopt) = 600. 00–10–12–150f(x) 10–3–2–1–140x50 01–2–4–3–160x40 x5x4x3x2x1 00101215P.AẨÅn C.B Hệä Sốá b) Do xopt = (0, 25, 30) không thô ûûa ràøng buộäc x1 + x2 + x3 60 nên xâ opt 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à 0–2–200–7600f(x) 1–¼–1/800–3/8–5x60 0–½¼10–¼30x310 0¼–3/8017/825x212 0–2–200–7600f(x) 100–1–1–1–60x60 0–½¼10–¼30x310 0¼–3/8017/825x212 x6x5x4x3x2x1 000101215P.AẨÅn C.B Hệä sốá ÝØJLỊÙ ỵỉ ÞßH× ÌĐßGỊ OĐ_× ỊÙß]Ë ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com 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. –80–100–4640f(x) –41½003/2 20x50 –20½10½40x310 10–½01½20x212 x6x5x4x3x2x1 000101215 P.A ẨÅn C.B Hệä sốá Tìm nghiệäm không âm cuâ â ûû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, xgopt), 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 CU  ÛÛ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 Ví dụï 2.1.Tìm nghiệäm không âm cuâ â ûû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, xgopt) = (3, 1, 2, 0, 0, 0). Vậäy nghiệäm không âm cuâ â ûûa hệä phương trình tuyếán tính trên lâ øø x = (3, 1, 2). TÌM NGHIỆÄM KHÔNG ÂM CU  ÛÛ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ê cn...cj...c2c1Giáù mộät đơn vị thứùc ănê bmamn...amj...am2am1m ........................ biain...aij...ai2ai1i ........................ b2a2n...a2j...a22a212 b1a1n...a1j...a12a111 n...j...21 Mứùc dinh dưỡngõ tốái thiểåu Thứùc ănêChấát dinh dưỡng (%)õ ÝÙ 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à ÝØJLỊÙ ỵỉ ÞßH× ÌĐßGỊ OĐ_× ỊÙß]Ë ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com BÀI TẬP CHƯƠNG 2 LẬP BÀI TOÁN ĐỐI NGẪU [1] 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 các bài toán quy hoạch tuyến tính sau đây a) 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 5 3 0, 0, 0 f x x x x x x x x x x x x x x x x x x x x 8 4 10 b) 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 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 [2] Chứng minh bài toán quy hoạch tuyến tính 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 SỬ DỤNG ĐỊNH LÝ ĐỐI NGẪU [3] Cho bài toán quy hoạch tuyến tính 4,10 34 325 13 max42)( 432 42 421 4321 jx xxx xx xxx xxxxxf j 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. Đs: 3 11, 0, , 0 2, 0, 4 4) 11 11 4 4 opt opt opt D opt x y b f x f y ÝØJLỊÙ ỵỉ ÞßH× ÌĐßGỊ OĐ_× ỊÙß]Ë ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ãn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com [4] Cho bài toán quy hoạch tuyến tính 24296 63 12232 min62712)( 321 321 321 321 3,10 jx j xxx xxx xxx xxxxf b) Giải bài toán đối ngẫu, suy ra Đs a) Viết bài toán đối ngẫu của bài toán trên. lời giải của bài toán gốc. : 54D optf y [5] 3 3, 0, 3, 0, 3 2 2) 54 opt opt opt y x b f x Cho bài toán quy hoạch tuyến tính 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 2 1 4 0 2,5j f x x x x x x x x x x x x x x x x x x x ng án cực biên, suy biến hay không suy biến) c) Cho biế