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

Nội dung text: Bài giảng Tối ưu hóa - Chương 2: Bài toán quy hoạch tuyến tính đối ngẫu - ThS. Nguyễn Công Trí

1. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 BAØI TOAÙN QUY HOAÏCH CHÖÔNG 2 THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU TUYEÁN TÍNH ÑOÁI NGAÃU Muïc ñích vaø yù nghóa  Vôùi baøi toaùn QHTT, baøi toaùn goác, kyù hieäu laø P 1. CAÙCH THAØNH LAÄP BAØI TOAÙN QUY HOAÏCH (Primal), chuùng ta coù theå thieát laäp baøi toaùn QHTT Ths.TUYEÁN Nguyeãn TÍNH ÑOÁI NGAÃU Coâng (Xem)Trí khaùc, baøi toaùn ñoái ngaãu, kyù hieäu laø D (Dual), sao cho töø lôøi giaûi cuûa baøi toaùn naøy ta coù theå thu 2. CAÙC ÑÒNH LYÙ ÑOÁI NGAÃU (Xem) thaäp ñöôïc thoâng tin veà lôøi giaûi cuûa baøi toaùn kia. 3. THUAÄTCopyright GIAÛI ÑÔN HÌNH ÑOÁI 2001 NGAÃU (Xem)  Ñeå coù thoâng tin caàn thieát veà baøi toaùn goác, coù theå nghieân cöùu treân baøi toaùn ñoái ngaãu cuûa noù. 4. MOÄT SOÁ ÖÙNG DUÏNG CUÛA LYÙ THUYEÁT ÑOÁI  Hôn nöõa, khi phaân tích ñoàng thôøi caû hai baøi NGAÃU TRONG BAØI TOAÙN QHTT (Xem) toaùn goác vaø ñoái ngaãu, chuùng ta coù theå ruùt ra Ths. Nguyeãn Coâng Trí caùc keát luaän coù giaù trò veà maët toaùn hoïc laãn veà 5. BAØI TAÄP Copyright 2001(Xem) maët yù nghóa kinh teá. THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Xeùt baøi toaùn QHTT (P) döôùi daïng chính taéc Goïi g(y) laø haøm muïc tieâu cuûa baøi toaùn (II), ta coù t f( x ) c x min t t P g(y) = min{c x + y (b – Ax)}, vôùi x ≥ 0. PI Ax b t t ≤ c x + y (b – Ax), vôùi x ≥ 0. x 0. n m Neáu x laø P.A cuûa baøi toaùn (I) thì b – Ax = 0 vaø Vôùi x = (x1, x2, , xn)  , b = (b1, b2, , bm)  0 t Giaû söû baøi toaùn (P) coù P.A.T.U laø xopt vaø goïi x laø g(y) ≤ c x. Vaäy g(y) laø moät caän döôùi baát kyø cuûa t t 0 moät P.A cuûa baøi toaùn (P), ta coù c xopt ≤ c x . haøm muïc tieâu. n Goïi x = (x1, x2, , xn)  , vôùi x ≥ 0 sao cho Ta tìm caän döôùi lôùn nhaát Max{g(y)}, thaät vaäy Ax – b 0 g(y) = min{ctx + yt(b – Ax)}, vôùi x ≥ 0. Baøi toaùn töông ñöông: t t t L( x , y ) ct x y t b Ax min = min{c x + y b – y Ax}, vôùi x ≥ 0. t t t P x 0 II = min{y b + (c – y A)x}, vôùi x ≥ 0. m t t t y R . = y b + min{ (c – y A)x}, vôùi x ≥ 0. 1
2. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Xeùt 0khi ct yt A 0 Ví duï 2.1. min ct yt A x  t t Baøi toaùn ñoái ngaãu cuûa baøi toaùn QHTT sau ñaây x 0 khic y A 0 f( x ) 2 x 8 x 6 x min Vaäy ta ñöôïc 1 4 5 t 2x x x 4 g(y) = y b 1 3 5 Suy ra baøi toaùn ñoái ngaãu coù daïng 2x2 x 5 4 x 2 x 3 x 13 g( y ) yt b max g ( y ) y t b max 2 3 4 x 0 j 1,5 D ct y t A 0 y t A c t j m m laø baøi toaùn fD ( y ) 4 y1 4 y 2 13 y 3 max y R y R 2y1 2 Hay baøi toaùn töông ñöông 2y2 y 3 0 t g( y ) y b max y 2 y 0 1 3 D At y c 3y 8 3 m y y 6 y R . 1 2 THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Baøi toaùn goác (P) Baøi toaùn ñoái ngaãu (D) Ví duï 2.2. Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc Haøm muïc tieâu Haøm muïc tieâu caëp raøng buoäc ñoái ngaãu cuûa baøi toaùn QHTT n m Baøi toaùn ñoái ngaãu f( x ) c x min f( y ) b y max f( x ) x 2 x x 2 x min P j j D i i 1 2 3 4 fD ( y ) y1 3 y 2 4 y 3 max j 1 i 1 x x 2 x 2 x 1 1 2 3 4 y1 3 y 2 2 y 3 1 Raøng buoäc thöù i Raøng buoäc thöù j 3x x x 3 y y 3 y 2 1 2 3 1 2 3 n m 2x1 3 x 2 x 3 x 4 4 2y y y 1 a x b i 1, m a y c, j 1, n 1 2 3  ij j i  ij i j j 1 i 1 x 0 j 1,2 2y1 y 3 2 j y 0, y 0 AÅn thöù j AÅn thöù I Caùc caëp ñoái ngaãu 1 2 x 0, y 3 y 2 y 1 1 1 1 2 3 x2 0, y 1 y 2 3 y 3 2 2 xj 0, j 1, n yi 0, i 1, m x x 2 x 2 x 1, y 0 3 khoâng raøng buoäc khoâng raøng buoäc 1 2 3 4 1 VD2.2 VD2.3 VD2.4 VD2.5 VD2.6 VD2.7 3x1 x 2 x 3 3, y 2 0 4 2
3. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU Ví duï 2.3. Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc Ví duï 2.4. Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc caëp raøng buoäc ñoái ngaãu cuûa baøi toaùn QHTT caëp raøng buoäc ñoái ngaãu cuûa baøi toaùn QHTT f( x ) 4 x 3 x 8 x min Baøi toaùn ñoái ngaãu 1 2 3 f( x ) 2 x1 x 2 8 x 3 max x1 7x 4 x 2 x 28 fD ( y ) 28 y1 10 y 2 15 y 3 min 1 0 1 2 1 2 3 x2 3x x 3 x 10 7y1 3 y 2 2 y 3 2 0 1 2 5 1 2 3 x 4y y 3 y 1 3 2x1 3 x 2 x 3 15 1 2 3 2y 3 y y 8 xj 0 j 1, 3 x 0 j 1,2 1 2 3 Caùc raøng buoäc ñoái ngaãu j Baøi toaùn ñoái ngaãu y1 0, y 3 0 x1 0, y 1 4 1 Caùc caëp ñoái ngaãu fD ( y ) 2 y1 5 y 2 max x 0, 7 y 3 y 2 y 2 1 1 1 2 3 1 0 4 x2 0, y 2 3 2 y1 x2 0, 4 y 1 y 2 3 y 3 1 2 0 1 3 x3 0, y 1 2 y 2 8 3 y 2 x x 2, y 0 4 7x1 4 x 2 2 x 3 28, y 1 0 3 1 2 8 1 3 1 x 2 x 5, y 0 5 2x1 3 x 2 x 3 15, y 3 0 4 yj 0; j 1, 2 2 3 2 THAØNH LAÄP BAØI TOAÙN ÑOÁI NGAÃU CAÙC ÑÒNH LYÙ ÑOÁI NGAÃU Ví duï 2.5. Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc ÑÒNH LYÙ 1. caëp raøng buoäc ñoái ngaãu cuûa baøi toaùn QHTT Neáu moät trong hai baøi toaùn ñoái ngaãu nhau coù f( x ) 2 x1 5 x 2 max Baøi toaùn ñoái ngaãu f( y ) 4 y 3 y 8 y m in P.A.T.Ö thì baøi toaùn kia cuõng coù P.A.T.Ö vaø giaù trò 1 0 4 D 1 2 3 x1 y haøm muïc tieâu cuûa chuùng baèng nhau. 0 1 3 1 1 0 1 2 x2 y HEÄ QUAÛ 1. 1 2 8 0 1 2 2 5 y Ñieàu kieän caàn vaø ñuû ñeå cho caùc baøi toaùn ñoái x 0; j 1,2 3 j ngaãu nhau coù phöông aùn toái öu laø moãi baøi toaùn Raøng buoäc ñoái ngaãu yj 0 j 1, 3 coù ít nhaát moät phöông aùn. x1 0, y 1 y 3 2 1 HEÄ QUAÛ 2. x2 0, y 2 2 y 3 5 2 Ñieàu kieän caàn vaø ñuû ñeå cho caùc baøi toaùn ñoái x1 4, y 1 0 3 ngaãu nhau khoâng coù P.A.T.Ö laø moät baøi toaùn coù x2 3, y 2 0 4 P.A coøn baøi toaùn kia khoâng coù P.A. x1 2 x 2 8, y 3 0 5 3
4. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 CAÙC ÑÒNH LYÙ ÑOÁI NGAÃU CAÙC ÑÒNH LYÙ ÑOÁI NGAÃU ÑÒNH LYÙ 2.(ÑÒNH LYÙ ÑOÄ LEÄCH BUØ YEÁU) ÑÒNH LYÙ 3.(ÑÒNH LYÙ ÑOÄ LEÄCH BUØ MAÏNH) Ñieàu kieän caàn vaø ñuû ñeå caëp baøi toaùn ñoái ngaãu Neáu caëp baøi toaùn ñoái ngaãu nhau coù P.A.T.Ö. thì nhau coù P.A.T.Ö. laø trong caëp raøng buoäc ñoái toàn taïi moät caëp phöông aùn sao cho trong caùc ngaãu, neáu raøng buoäc naøy xaûy ra vôùi daáu baát caëp ñoái ngaãu, neáu raøng buoäc naøy xaûy ra vôùi daáu ñaúng thöùc ngaët (“>” hoaëc “ 0 thì a yopt c  Neáu x opt = 0 thì toàn taïi a yopt c j  ij i j j  ij i j n , i 1 n i 1 a xopt b opt  Neáu opt thì toàn taïi y opt 0 (> hoaëc <).  Neáu  ij j i thì yi = 0  aij x j b i i j 1 j 1 AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU Ví duï 2.6. Cho baøi toaùn QHTT Caùc caëp raøng buoäc ñoái ngaãu f( x ) 4 x1 3 x 2 8 x 3 min x1 ≥ 0 vaø y1 ≤ 4 (1) x1 ≥ ≤ 1 0 1 2 x2 0 vaø y2 3 (2) x 0 1 2 2 5 x3 ≥ 0 vaø y1 + 2y2 ≤ 8 (3) x 3 Thay yopt = (2, 3) vaøo caùc raøng buoäc xj 0, j 1,3 Töø (1): y1 = 2 < 4 x1 = 0 (ñònh lyù 2). coù P.A.T.Ö cuûa baøi toaùn ñoái ngaãu laø yopt = (2, 3) Thay x1 = 0 vaøo hpt cuûa baøi toaùn goác vaø f(yopt) = 19. Haõy tìm P.A.T.Ö cuûa baøi toaùn treân. 0 x 2 Baøi toaùn ñoái ngaãu 1 0 1 2 3 fD ( y ) 2 y1 5 y 2 max x x 1; x 2 2 2 3 0 1 2 5 x2 2 x 3 5 1 0 4 x y 3 0 1 1 3 Vaäy, P.A.T.Ö cuûa baøi toaùn goác laø xopt= (0,1,2) vaø y2 1 2 8 f(xopt) = fD(yopt) = 19. 4
5. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU Ví duï 2.7. Cho baøi toaùn QHTT Caùc caëp raøng buoäc ñoái ngaãu f( x ) 2 x1 2 x 2 x 3 4 x 4 max x1 ≥ 0 vaø 5y1 – 3y2 + 4y3 ≥ 2 (1) 5x1 x 2 x 3 6 x 4 50 x2 ≥ 0 vaø y1 ≥ 2 (2) 3x x 2 x 16 1 3 4 x3 ≥ 0 vaø y1 + y2 + 3y3 ≥ 1 (3) 4x 3 x x 23 1 3 4 x4 ≥ 0 vaø 6y1 + 2y2 + y3 ≥ 4 (4) xj 0 j 1,4 -3x1 + x3 + 2x4 ≥ 16 vaø y2 ≤ 0 (5) Coù P.A.T.Ö laø xopt = (0,14, 6, 5) vaø f(xopt) = 54. Haõy 4x1 + 3x3 + x4 ≤ 23 vaø y3 ≥ 0 (6) tìm P.A.T.Ö cuûa baøi toaùn ñoái ngaãu. Thay xopt = (0, 14, 6, 5) vaøo caùc raøng buoäc Baøi toaùn ñoái ngaãu Töø (2): x2 = 14 > 0 y1 = 2. fD ()50 y y1 16 y 2 23 y 3 min Töø (3): x = 6 > 0 y + y + 3y = 1 5y 3 y 4 y 2 3 1 2 3 1 2 3 Töø (4): x = 5 > 0 6y + 2y + y = 4 y 2 4 1 2 3 1 Giaûi heä phöông trình treân, ta coù y1 = 2; y2 = -23/5; y1 y 2 3 y 3 1 y = 6/5. Vaäy, P.A.T.Ö cuûa baøi toaùn ñoái ngaãu laø 6y1 2 y 2 y 3 4 3 y = (2, -23/5, 6/5) vaø f (y ) = 54. y2 0 ; y 3 0 opt D opt AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU Ví duï 2.8. Cho baøi toaùn QHTT 1. Kieåm tra tröïc tieáp, ta thaáy X, Y, vaø T laø P.A cuûa f( x ) x1 2 x 2 x 3 Max baøi toaùn. Vì Z khoâng thoûa maõn caùc raøng buoäc x 3 x x 5 1 2 4 neân Z khoâng laø P.A cuûa baøi toaùn. x x 3 1 2 2. Baøi toaùn ñoái ngaãu 3x1 x 3 x 4 2 fD ( y ) 5 y1 3 y 2 2 y 3 min xj 0 j 1,4 y1 y 2 3 y 3 1 Xeùt caùc vectô sau X = (3, 0, 11, 0), Y = (2, 1, 8, 0), 3y y 2 Z = (-4, 2, 0, 10) vaø T = (1, 2, 1, 2). Vectô naøo laø 1 2 P.A.T.Ö. cuûa baøi toaùn? y3 1 Caùch giaûi. y1 y 3 0 1. Kieåm tra caùc vectô coù phaûi laø P.A hay khoâng? y1 0; y 2 0; y 3 0 2. Vieát baøi toaùn ñoái ngaãu, 3. Kieåm tra caùc P.A coù phaûi laø P.A.T.Ö.? Ta coù 7 caëp raøng buoäc ñoái ngaãu 5
6. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU x1 ≥ 0 vaø y1 + y2 – 3y3 ≥ -1 (1) Deã daøng kieåm tra vectô X*= (0, 2, 1) thoûa caùc x2 ≥ 0 vaø 3y1 + y2 ≥ 2 (2) raøng buoäc cuûa baøi toaùn ñoái ngaãu. x3 ≥ 0 vaø y3 ≥ 1 (3) ≥ ≥ * x4 0 vaø – y1 + y3 0 (4) Hôn nöõa, fD(X )= f(X)= 8 neân X laø P.A.T.Ö. cuûa x1 + 3x2 – x4 ≤ 5 vaø y1 ≥ 0 (5) baøi toaùn goác. x + x ≤ 3 vaø y ≥ 0 (6) 1 2 2  Do Y = (2, 1, 8, 0) laø P.A cuûa baøi toaùn goác vaø -3x1 + x3 + x4 ≤ 2 vaø y3 ≥ 0 (7) 3. Kieåm tra X, Y, T laø P.A.T.Ö f(X) = f(Y)= 8 neân Y cuõng laø P.A.T.Ö.  Giaû söû X = (3, 0, 11, 0) laø P.A.T.Ö cuûa baøi toaùn.  Vôùi T = (1, 2, 1, 2), ta coù f(T)= 4 fmax = 8 Töø (1): x1 = 3 > 0 y1 + y2 – 3y3 = -1 Vaäy T khoâng phaûi laø P.A.T.Ö. maø T chæ laø phöông Töø (3): x =11 > 0 y = 1 3 3 aùn cuûa baøi toaùn. Töø (5): 3 + 0 + 0 + 0 = 3 < 5 y1 = 0 Giaûi heä phöông trình, ta ñöôïc X*= (0, 2, 1). AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU Ví duï 2.9. Giaûi baøi toaùn QHTT Ñöa baøi toaùn veà daïng chính taéc baèng caùch f( x ) 10 x1 8 x 2 19 x 3 min theâm 3 aån phuï y4 ≥ 0, y5 ≥ 0, y6 ≥ 0 2 1 1 x1 6 3 0 2x 2 fD ( y ) 6 y1 2 y 2 5 y 3 max 2 1 2 5 x3 5 2 3 1 y1 y 4 10 x 0 j 1,3 1 0 2y y 8 j 2 5 Baøi toaùn ñoái ngaãu fD ( y ) 6 y1 2 y 2 5 y 3 max 1 2 5 y3 y 6 19 2 3 1 y 10 1 y 0 j 1,6 1 0 2 y 8 j 2 Ta thaáy baøi toaùn cuõng coù daïng chuaån. 1 2 5 y3 19 Söû duïng thuaät giaûi ñôn hình Ví duï 2.10 yj 0 j 1,3 6
7. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU HEÄ P.A HEÄ AÅN P.A 6 2 5 0 0 0 AÅN 6 2 5 0 0 0 SOÁ y1 y2 y3 y4 y5 y6 SOÁ C.B y1 y2 y3 y4 y5 y6 C.B 3 1 6 y1 4 1 2 0 2 2 0 0 y4 10 2 3 1 1 0 0 1 2 5 y3 2 0 1 1 3 3 0 0 y5 8 1 0 2 0 1 0 0 y6 5 0 5 0 1 3 1 0 y6 19 1 2 5 0 0 1 7 4 f x 0 6 2 5 0 0 0 f x 34 0 5 0 3 3 0 GHI CHUÙ y 5 3 1 1 0 0 6 1 1 2 2 2 Baøi toaùn coù P.A.T.Ö yopt=(4, 0, 2) vaø f(yopt)= 34. 3 3 1 0 y5 3 0 2 2 2 1 0 P.A.T.Ö cuûa baøi toaùn goác laø 1 9 1 x b x 7 0 7 0 y6 14 0 2 2 2 0 1 1 4 4 1 3 3 4 4 xopt x2 5 b 5 xopt x2 3 0 3 f x 30 0 7 2 3 0 0 x3 6 b 6 x3 0 0 0 AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU AÙP DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU Caùch 2: duøng ñònh lyù ñoái ngaãu GHI CHUÙ. Chuùng ta cuõng coù theå söû duïng quy taéc x1 ≥ 0 vaø 2y1 + 3y2 + y3 ≤ 10 (1) sau ñaây ñeå tìm P.A.T.Ö cuûa baøi toaùn ñoái ngaãu: x ≥ 0 vaø y + 2y ≤ 8 (2) y1 1 c 1 2 1 3 x3 ≥ 0 vaø y1 + 2y2 + 5y3 ≤ 19 (3) y2 2 c 2 yopt 2x1 + x2 + x3 ≥ 6 vaø y1 ≥ 0 (4)  3x + 2x ≥ 2 vaø y ≥ 0 (5) 1 3 2 ym m c m x1 + 2x2+ 5x3 ≥ 5 vaø y3 ≥ 0 (6) Vôùi caùc aån cô baûn xj (j = 1, 2, , m) trong P.A.C.B Ta coù P.A.T.Ö cuûa baøi toaùn ñoái ngaãu yopt= (4,0,2) ñaàu tieân laäp thaønh ma traän ñôn vò caáp m töông Töø (3): 4 +2 0 + 5 2 = 14 0 2x1 + x2 + x3 = 6 Trong Ví duï 2.9, aån cô baûn ñaàu tieân cuûa baøi toaùn Töø (6): y3= 2 > 0 x1 + 2x2 + 5x3 = 5 ñoái ngaãu laø y4, y5 vaø y6 thì P.A.T.Ö cuûa baøi toaùn Giaûi heä phöông trình, ta coù PA.T.Ö cuûa baøi toaùn goác (ñoái ngaãu cuûa baøi toaùn ñoái ngaãu) laø goác laø xopt = (7/3, 4/3, 0) vaø f(xopt) = 34. Xopt = (7/3, 4/3, 0) vaø f(Xopt) = 34. 7
8. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU  Do Lemke G.E ñeà xuaát naêm 1954. Ñaây laø thuaät LAÄP BAÛNG ÑÔN HÌNH ÑOÁI NGAÃU giaûi ñôn hình ñöôïc aùp duïng vaøo baøi toaùn ñoái ngaãu nhöng ñeå tìm P.A.T.Ö cho baøi toaùn goác. Ñuùng Ñuùng bi ≥ 0,i? j ≤ 0,j? P.A.T.Ö  Thuaät giaûi ñôn hình ñoái ngaãu xuaát phaùt töø moät Sai Sai “phöông aùn giaû” thoûa caùc raøng buoäc chính cuûa Ñuùng a 0,j? THUAÄT GIAÛI KEÁT THUÙC baøi toaùn (nghieäm ñuùng Ax = b) nhöng khoâng ij Sai ÑÔN HÌNH THUAÄT GIAÛI thoaû ñieàu kieän raøng buoäc veà daáu (x 0), nghóa laø XAÙC ÑÒNH PHÖÔNG AÙN MÔÙI baûng ñôn hình ñaàu tieân khoâng coù phaàn töû döông BAØI TOAÙN Aån ra : Minbi x i b 0 KHOÂNG COÙ P.A.T.Ö trong doøng muïc tieâu (doøng cuoái) nhöng laïi coù i j Aån vaøo : Min x j phaàn töû aâm trong coät phöông aùn. a 0 ij aij  Thuaät giaûi naøy thöôøng ñöôïc aùp duïng khi chöa bieát P.A.C.B naøo cuûa baøi toaùn goác nhöng laïi coù BIEÁN ÑOÅI BAÛNG ÑÔN HÌNH SOÁ BÖÔÙC LAËP saün moät P.A.C.B cuûa baøi toaùn ñoái ngaãu. LAØ HÖÕU HAÏN THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU Ví duï 2.10. Giaûi baøi toaùn QHTT trong Ví duï 2.9 Heä AÅn P.A 10 8 19 0 0 0 baèng thuaät giaûi ñôn hình ñoái ngaãu. soá C.B x x x x x x Ñöa baøi toaùn veà daïng chính taéc, roài sau ñoù 1 2 3 4 5 6 nhaân (–1) cho caùc raøng buoäc ñaúng thöùc, ta coù 0 x4 –6 –2 –1 –1 1 0 0 baøi toaùn daïng chính taéc nhö sau 0 x5 –2 –3 0 –2 0 1 0 f( x ) 10 x1 8 x 2 19 x 3 min 0 x6 –5 –1 –2 –5 0 0 1 2x x x x 6 1 2 3 4 f(x) 0 –10 –8 –19 0 0 0 3x 2 x x 2 1 3 5 10 x1 3 1 ½ ½ –½ 0 0 x 2 x 5 x x 5 1 2 3 6 0 x5 7 0 3/2 –½ –3/2 1 0 x 0, j 1,6 j 0 x6 –2 0 –3/2 9/2 –½ 0 1 Xuaát phaùt töø phöông aùn giaû X = (0,0,0,–6,–2,–5). f(x) 30 0 –3 –14 –5 0 0 Ta coù baûng ñôn hình ñoái ngaãu nhö sau 8
9. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU Heä AÅn P.A 10 8 19 0 0 0 GHI CHUÙ. Ñoái vôùi thuaät giaûi ñôn hình ñoái ngaãu, soá C.B ñeå tìm P.A.T.Ö cuûa baøi toaùn ñoái ngaãu Yopt, ta coù x1 x2 x3 x4 x5 x6 bieåu thöùc sau y1 1 c 1 10 x1 7/3 1 0 2 –2/3 0 1/3 y2 2 c 2 y 0 x5 5 0 0 4 –2 1 1 opt  8 x3 4/3 0 1 –3 1/3 0 –2/3 ym m c m f(x) 34 0 0 –23 –4 0 –2 Trong Ví duï 2.10, aån cô baûn ñaàu tieân cuûa baøi toaùn ñoái ngaãu laø x4, x5 vaø x6 thì Vaäy, P.A.T.Ö cuûa baøi toaùn laø x = (7/3, 4/3, 0) opt y1 4 c 4 y1 ( 4) 0 4 vaø f(xopt) = 34. yopt y2 5 c 5 y2 0 0 0 y3 6 c 6 y3 ( 2) 0 2 P.A.T.Ö cuûa baøi toaùn ñoái ngaãu laø Yopt = (4, 0, 2) vaø * f (Yopt) = 34. THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU THUAÄT GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU Ví duï 2.11. Heä AÅn P.A 2 –4 1 –1 2 0 0 Duøng thuaät giaûi ñôn hình ñoái ngaãu ñeå giaûi baøi soá C.B x1 x2 x3 x4 x5 x6 x7 toaùn quy hoaïch tuyeán tính sau ñaây 2 x1 –2 1 –2 0 0 –2 0 0 f( x ) 2 x1 4 x 2 x 3 x 4 2 x 5 Min –1 x4 –4 0 4 1 1 –1 0 0 x 2 x 2 x 2 0 x 2 0 0 2 0 –1 1 0 1 2 5 6 0 x 6 0 1 1 0 4 0 1 4x2 x 3 x 4 x 5 4 7 2x x x 2 f(x) 0 0 –4 –2 0 –5 0 0 Do a4j 0, 3 5 6 2 x 6 1 –10 –2 –2 0 0 0 j = 1, , 7 x2 x 3 4 x 5 x 7 6 1 neân baøi –1 x5 4 0 –4 –1 –1 1 0 0 xj 0, j 1,7 toaùn treân 0 x 6 0 –4 1 –1 0 1 0 6 khoâng coù Xuaát phaùt töø phöông aùn giaû X = (–2,0,0,–4,0,2,6). 0 x –10 0 17 5 4 0 0 1 7 P.A.T.Ö. Ta coù baûng ñôn hình ñoái ngaãu f(x) 20 0 –24 –7 –5 0 0 0 9
10. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 MOÄT SOÁ ÖÙNG DUÏNG CUÛA LYÙ THUYEÁT MOÄT SOÁ ÖÙNG DUÏNG CUÛA LYÙ THUYEÁT ÑOÁI NGAÃU TRONG BAØI TOAÙN QHTT ÑOÁI NGAÃU TRONG BAØI TOAÙN QHTT Ví duï 2.12. 1. TÌM PHÖÔNG AÙN TOÁI ÖU MÔÙI KHI COÙ a) Duøng thuaät giaûi ñôn hình ñoái ngaãu ñeå giaûi baøi THEÂM RAØNG BUOÄC VAØO BAØI TOAÙN (XEM) toaùn quy hoaïch tuyeán tính sau ñaây f( x ) 15 x 12 x 10 x Min 2. TÌM NGHIEÄM KHOÂNG AÂM CUÛA HEÄ 1 2 3 3x 4 x 2 x 160 PHÖÔNG TRÌNH TUYEÁN TÍNH BAÈNG THUAÄT 1 2 3 x 2 x 3 x 140 GIAÛI ÑÔN HÌNH MÔÛ ROÄNG (XEM) 1 2 3 x 0, j 1,3 3. YÙ NGHÓA KINH TEÁ CUÛA BAØI TOAÙN QUY j b) Neáu theâm moät raøng buoäc nöõa x1 + x2 + x3 60 HOAÏCH TUYEÁN TÍNH ÑOÁI NGAÃU (XEM) vaøo baøi toaùn treân, tìm phöông aùn toái öu cuûa baøi toaùn môùi. MOÄT SOÁ ÖÙNG DUÏNG CUÛA LYÙ THUYEÁT MOÄT SOÁ ÖÙNG DUÏNG LYÙ THUYEÁT ÑOÁI NGAÃU ÑOÁI NGAÃU TRONG BAØI TOAÙN QHTT Heä AÅn P.A 15 12 10 0 0 Soá C.B Ñöa baøi toaùn veà daïng chính taéc, roài sau ñoù x1 x2 x3 x4 x5 nhaân (–1) cho caùc raøng buoäc ñaúng thöùc, ta coù 0 x4 –160 –3 –4 –2 1 0 baøi toaùn daïng chính taéc nhö sau 0 x5 –140 –1 –2 –3 0 1 f(x) 0 –15 –12 –10 0 0 f( x ) 15 x1 12 x 2 10 x 3 Min 12 x2 40 ¾ 1 ½ –¼ 0 3x 4 x 2 x x 160 1 2 3 4 0 x –60 ½ 0 –2 –½ 1 x 2 x 3 x x 140 5 1 2 3 5 f(x) 480 –6 0 –4 –3 0 x 0, j 1,5 j 12 x2 25 7/8 1 0 –3/8 ¼ a) Xuaát phaùt töø phöông aùn giaû X = (0, 0, 0, –160, 10 x3 30 –¼ 0 1 ¼ –½ –140. Ta coù baûng ñôn hình ñoái ngaãu f(x) 600 –7 0 0 –2 –2 P.A.T.Ö laø xopt = (0, 25, 30) vaø f(xopt) = 600. 10
11. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 MOÄT SOÁ ÖÙNG DUÏNG CUÛA LYÙ THUYEÁT MOÄT SOÁ ÖÙNG DUÏNG LYÙ THUYEÁT ÑOÁI NGAÃU ÑOÁI NGAÃU TRONG BAØI TOAÙN QHTT Heä AÅn P.A 15 12 10 0 0 0 b) Do xopt = (0, 25, 30) khoâng thoûa raøng buoäc x1 soá C.B x1 x2 x3 x4 x5 x6 + x2 + x3 60 neân xopt khoâng phaûi laø phöông aùn cuûa baøi toaùn môùi. Ñeå xöû lyù raøng buoäc môùi naøy, 12 x2 25 7/8 1 0 –3/8 ¼ 0 ta ñöa raøng buoäc baát ñaúng thöùc veà raøng buoäc 10 x3 30 –¼ 0 1 ¼ –½ 0 ñaúng thöùc baèng caùch theâm aån phuï x6 0, ta 0 x6 –60 –1 –1 –1 0 0 1 ñöôïc –x1 – x2 – x3 + x6 = –60. Söû duïng baûng cuoái cuøng trong caâu a) vaø ñöa f(x) 600 –7 0 0 –2 –2 0 raøng buoäc môùi –x1 – x2 – x3 + x6 = –60 vaøo baûng 12 x2 25 7/8 1 0 –3/8 ¼ 0 treân. Löu yù aån x6 laø aån cô baûn trong baøi toaùn 10 x3 30 –¼ 0 1 ¼ –½ 0 môùi, coøn x4 vaø x5 laø aån cô baûn trong baøi toaùn cuõ neân trong ma traän heä soá cuûa baøi toaùn môùi ta 0 x6 –5 –3/8 0 0 –1/8 –¼ 1 coäng doøng 1 vaø doøng 2 vaøo doøng 3 ñeå vectô f(x) 600 –7 0 0 –2 –2 0 coät öùng vôùi x4 vaø x5 laø caùc vectô ñôn vò. MOÄT SOÁ ÖÙNG DUÏNG LYÙ THUYEÁT ÑOÁI NGAÃU TÌM NGHIEÄM KHOÂNG AÂM CUÛA Heä AÅn 15 12 10 0 0 0 HEÄ PHÖÔNG TRÌNH TUYEÁN TÍNH P.A Tìm nghieäm khoâng aâm cuûa heä phöông trình soá C.B x x x x x x 1 2 3 4 5 6 tuyeán tính AX = b, X 0 (1), trong ñoù A laø ma 12 x 20 ½ 1 0 –½ 0 1 2 traän m n, b m coù theå quy veà giaûi baøi toaùn quy m g 10 x3 40 ½ 0 1 ½ 0 –2 hoaïch tuyeán tính f x M x j min j 1 0 x5 20 3/2 0 0 ½ 1 –4 AX Xg b 2 f(x) 640 –4 0 0 –1 0 –8 XXM 0,g 0, 0 / / P.A.T.Ö laø x opt = (0, 20, 40) vaø f(x opt) = 640.  Baøi toaùn (2) luoân luoân coù P.A.T.Ö vì (0,b) laø moät P.A vaø haøm muïc tieâu bò chaën [f(x) 0]. g  Giaû söû P.A.T.Ö cuûa baøi toaùn treân laø (xopt, x opt), g neáu x opt = 0, j thì xopt laø nghieäm cuûa baøi toaùn g (1). Ngöôïc laïi neáu toàn taïi x j 0 thì baøi toaùn (1) voâ nghieäm. 11
12. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 TÌM NGHIEÄM KHOÂNG AÂM CUÛA HEÄ PHÖÔNG TRÌNH TUYEÁN TÍNH YÙ NGHÓA KINH TEÁ CUÛA BAØI TOAÙN ÑOÁI NGAÃU Ví duï 2.1.Tìm nghieäm khoâng aâm cuûa heä phöông Xeùt baøi toaùn goác laø baøi toaùn khaåu phaàn thöùc aên trình tuyeán tính 2x1 3 x 2 x 3 7 Thöùc aên Möùc x1 2 x 2 4 x 3 9 Chaát dinh dinh döôõng döôõng (%) 1 2 j n 3x1 x 2 2 x 3 4 toái thieåu Ta coù theå quy baøi toaùn treân veà baøi toaùn QHTT 1 a11 a12 a1j a1n b1 f() x M x4 x 5 x 6 Min 2 a21 a22 a2j a2n b2 2x1 3 x 2 x 3 x 4 7 x1 2 x 2 4 x 3 x 5 9 i ai1 ai2 aij ain bi 3x1 x 2 2 x 3 x 6 4 xj 0, j 1,6 g m am1 am2 amj amn bm Giaûi baøi toaùn treân, ta ñöôïc P.A.T.Ư laø (xopt, x opt) = (3, 1, 2, 0, 0, 0). Vaäy nghieäm khoâng aâm cuûa heä Giaù moät ñôn c1 c2 cj cn phöông trình tuyeán tính treân laø x = (3, 1, 2). vò thöùc aên YÙ NGHÓA KINH TEÁ CUÛA BAØI TOAÙN ÑOÁI NGAÃU YÙ NGHÓA KINH TEÁ CUÛA BAØI TOAÙN ÑOÁI NGAÃU Goïi xj (j = 1, 2, , n) laø soá ñôn vò thöùc aên trong Goïi yi laø giaù baùn moät vieân thuoác boå coù chöùa moãi böûa, ta coù moâ hình baøi toaùn QHTT nhö sau chaát dinh döôõng i (i = 1, 2, , m). f x c1 x 1 c 2 x 2  cn x n min Ngöôøi chaên nuoâi seõ phaûi löïa choïn:  Mua thuoác boå, neáu a1jy1 + a2jy2 + + anjyn 0 thì a x + a x + + a x = b , i i1 1 i2 2 in n i a1j y 1 a 2 j y 2  a mj y m c j , j 1, n Nghóa laø, neáu giaù moät vieân thuoác boå khaù cao thì y 0, i 1, m ngöôøi chaên nuoâi seõ mua caùc loaïi thöùc aên sao i cho thoaû nhu caàu toái thieåu cuûa chaát dinh döôõng. Chaát dinh döôõng thay theá: nhaø saûn xuaát thuoác Vaäy, khi phaân tích caëp baøi toaùn ñoái ngaãu nhau boå töông öùng vôùi caùc chaát dinh döôõng treân. chính laø phaân tích tính T.Ö cuûa töøng baøi toaùn. 12
13. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 BAØI TAÄP CHÖÔNG 2 BAØI TAÄP CHÖÔNG 2 1.a) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn QHTT f( x ) 4 x1 4 x 2 3 x 3 2 x 4 min LAÄP BAØI TOAÙN ÑOÁI NGAÃU x1 2 x 2 x 3 x 4 1 2x x 3 x x 8 [1a] [1b] [2] 1 2 3 4 x 5 x x 3 x 4 Th.s Nguyeãn Coâng Trí 1 2 3 4 SÖÛ DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU x1 0, x 3 0, x 4 0 Baøi toaùn ñoái ngaãu f( y ) y 8 y 4 y max [3] [4] [5] [6] D 1 2 3 Copyright 2001 y 2 y y 4 1 2 3 PHÖÔNG PHAÙP ÑÔN HÌNH ÑOÁI NGAÃU 2y1 y 2 5 y 3 4 y1 3 y 2 y 3 3 y y 3 y 2 [7a] [7b] 1 2 3 y2 0, y 3 0 BAØI TAÄP CHÖÔNG 2 BAØI TAÄP CHÖÔNG 2 1.b) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn QHTT 2. Chöùng minh baøi toaùn QHTT sau ñaây truøng vôùi f( x ) 2 x1 3 x 2 4 x 3 5 x 4 max baøi toaùn ñoái ngaãu cuûa noù (Baøi toaùn töï ñoái ngaãu). x1 x 2 2 x 3 2 x 4 10 f( x ) x1 x 2 x 3 min x1 2 x 2 x 3 x 4 8 x x 2 x x 9 x2 x 3 1 1 2 3 4 x x 1 x2 0, x 3 0, x 4 0 1 3 Baøi toaùn ñoái ngaãu x1 x 2 1 fD ( y ) 10 y1 8 y 2 9 y 3 min y y y 2 x1 0, x 2 0 x 3 0, 1 2 3 y1 2 y 2 y 3 3 2y1 y 2 2 y 3 4 2y y y 5 1 2 3 y1 0, y 3 0 13
14. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 BAØI TAÄP CHÖÔNG 2 BAØI TAÄP CHÖÔNG 2 3. Cho baøi toaùn QHTT sau ñaây: a) Baøi toaùn ñoái ngaãu fD ( y ) y1 3 y 2 3 y 3 min b) Giaûi baøi toaùn goác, y 2 f( x ) 2 x 4 x x x max 1 1 2 3 4 ta ñöôïc P.A.T.Ö laø x = opt 3y1 5 y 2 y 3 4 x1 3 x 2 x 4 1 (1, 0, 3/4, 0), f = 11/4 max 4y3 1 Caùc caëp ñoái ngaãu 5x2 2 x 4 3 y1 2 y 2 y 3 1 x1 0 vaø y1 2 (1) y 0 x2 4 x 3 x 4 3 2 x2 0 vaø 3y1 – 5y2 + y3 4 (2) xj 0 j 1,4 x3 0 vaø + 4y3 1 (3) a) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn treân. x4 0 vaø y1 – 2y2 + y3 1 (4) ≤ b) Giaûi baøi toaùn goác, suy ra lôøi giaûi cuûa baøi -5x2 – 2x4 3 vaø y2 0 (5) Giaûi hpt (1), (3) vaø (5), ta ñöôïc toaùn ñoái ngaãu. yopt = (2, 0, 1/4) vaø fD(yopt)= 11/4 BAØI TAÄP CHÖÔNG 2 BAØI TAÄP CHÖÔNG 2 5. Cho baøi toaùn QHTT 4. Cho baøi toaùn QHTT sau ñaây: f()5 x x1 9 x 2 15 x 3 7 x 4 6 x 5 min f( x ) 12 x 27 x 6 x min 1 2 3 x1 3 x 2 x 3 x 4 x 5 1 2x1 3 x 2 2 x 3 12 4x1 x 3 2 x 4 x 5 4 x x x 2 x 1 x1 3 x 2 x 3 6 1 2 3 5 x 0 j 2,5 6x1 9 x 2 2 x 3 24 j a) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn treân. x 0 j 1,3 j b) Phaân tích caùc tính chaát (P.A.C.B suy bieán hay a) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn treân. khoâng suy bieán) cuûa vectô X = (0, 1, 0, 2, 0). b) Giaûi baøi toaùn ñoái ngaãu, suy ra lôøi giaûi cuûa c) Cho bieát X laø P.A.T.Ö cuûa baøi toaùn goác vaø baøi toaùn goác. f(X) = 5. Tìm P.A.T.Ö. cuûa baøi toaùn ñoái ngaãu. 14
15. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 BAØI TAÄP CHÖÔNG 2 BAØI TAÄP CHÖÔNG 2 a) Baøi toaùn ñoái ngaãu fD ( y ) y1 4 y 2 y 3 max 6. Cho baøi toaùn QHTT b) Kieåm tra tröïc tieáp, ta y1 4 y 2 y 3 5 f( x ) 3 x1 7 x 2 x 3 2 x 4 max thaáy X = (0, 1, 0, 2, 0) laø P.A 3y1 y 3 9 2x1 3 x 2 x 3 2 x 4 30 2x 2 x 3 x 60 vaø X thoûa 5 raøng buoäc chaët, y1 y 2 y 3 15 1 2 3 y 2 y 7 2x1 2 x 2 3 x 3 4 x 4 32 deã daøng kieåm tra hpt raøng 1 2 y y 2 y 6 x 0 j 1,4 buoäc coù haïng khaùc 5, 1 2 3 j y1 0, y 3 0 Cho caùc vectô: neân X khoâng laø P.A.C.B. X = (-1, 2, 3, 4); Y = (0, 2, 1, 3); Z = (0, 0, 0, 8), T = c) Chæ ra 6 caëp ñoái ngaãu, töø ñoù aùp duïng ñònh lyù (14, 0, 0, 1); S = (18, 2, 0, 0) ñoái ngaãu, ta coù P.A.T.Ö cuûa baøi toaùn ñoái ngaãu laø Trong caùc vectô treân, vectô naøo laø phöông aùn toái Y = [(y – 9)/3, (y + 12)/6, y ], vôùi y ≥ 0, y ≤ 0. opt 3 3 3 3 1 öu cuûa baøi toaùn? Haõy giaûi thích. BAØI TAÄP CHÖÔNG 2 BAØI TAÄP CHÖÔNG 2 1. Kieåm tra tröïc tieáp X, Y khoâng phaûi laø phöông 3. Kieåm tra tính toái öu cuûa caùc phöông aùn aùn. Caùc vectô Z, T, S laø caùc phöông aùn vì chuùng  Xeùt phöông aùn Z = (0, 0, 0, 8), giaû söû Z laø thoûa caùc raøng buoäc cuûa baøi toaùn. P.A.T.Ö. cuûa baøi toaùn goác, ta coù f(Z) = –16. 2. Baøi toaùn ñoái ngaãu Töø (4): z4 = 8 2 y1 + 4y3 = –2 Caùc caëp fDraøng( y ) buoäc 30 y1ñoái 60ngaãu y 2 32 y 3 min Töø (5): 2x1 – 3x2 – x3 + 2x4 = 16 < 30 y1 = 0 2y 2 y 2 y 3 Töø (6): 2x1 – 2x2 + 3x3 = 0 < 60 y2 = 0 x1 ≥ 0 vaø 2y1 + 2y2 +12y3 ≥ 23 3 (1) 3y 2 y 2 y 7 P.A.T.Ö. cuûa baøi toaùn ñoái ngaãu seõ laø Z*= (0, 0,–½), x ≥ 0 vaø –3y – 2y –12y ≥ – 27 3 (2) 2 1 2 3 * y 3 y 3 y 1 nhöng Z khoâng thoûa raøng buoäc cuûa baøi toaùn ñoái x ≥ 0 vaø – y + 3y –13y ≥ 21 3 (3) 3 1 2 3 ngaãu neân Z* khoâng theå laø P.A.T.Ö. Vaäy, Z khoâng 2y1 4 y 3 2 x4 ≥ 0 vaø 2 y1 + 4y3 ≥ –2 (4) theå laø P.A.T.Ö. cuûa baøi toaùn goác. y1 0, y 2 0 2x1 – 3x2 – x3 + 2x4 ≤ 30 vaø y1 ≥ 0 (5)  Töông töï, giaû söû T = (14, 0, 0, 1) laø P.A.T.Ö. cuûa 2x1 – 2x2 + 3x3 ≤ 60 vaø y2 ≥ 0 (6) baøi toaùn goác ta coù f(T) = 40. 15
16. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 2 BAØI TAÄP CHÖÔNG 2 BAØI TAÄP CHÖÔNG 2 Töø (1): t1 = 14 2y1 + 2y2 + 2y3 = 3 7. a) Duøng PPÑHÑN giaûi baøi toaùn QHTT sau ñaây, töø ñoù suy ra lôøi giaûi cuûa baøi toaùn ñoái ngaãu Töø (4): t4 = 1 2 y1 + 4y3 = –2 Töø (6): 2x1 – 2x2 + 3x3 = 28 < 60 y2 = 0 f( x ) x1 3 x 2 x 3 2 x 4 min Giaûi heä phöông trình treân, ta coù P.A.T.Ö. cuûa baøi x1 x 2 2 x 3 2 x 4 10 * toaùn ñoái ngaãu seõ laø T = (4, 0,–5/2). x1 2 x 2 x 3 x 4 8 x x x x 9 Deã daøng kieåm tra T* thoûa caùc raøng buoäc cuûa baøi 1 2 3 4 toaùn ñoái ngaãu neân T* laø P.A.T.Ö. cuûa baøi toaùn ñoái x1 0, x 2 0, x 3 0, x 4 0 * ngaãu. Hôn nöõa, fD(T ) = f(T) = 40 Vaäy, T laø P.A.T.Ö. cuûa baøi toaùn goác.  Xeùt phöông aùn S = (18, 2, 0, 0), ta coù f(S) = 40 = f(T). Vaäy, S laø P.A.T.Ö. cuûa baøi toaùn goác. BAØI TAÄP CHÖÔNG 2 7. b) Duøng PPÑHÑN giaûi baøi toaùn QHTT sau ñaây, töø ñoù suy ra lôøi giaûi cuûa baøi toaùn ñoái ngaãu f( x ) 2 x1 x 2 6 x 3 3 x 4 max x1 x 2 1 x2 x 3 4 x x 2 2 4 x1 0, x 2 0, x 3 0, x 4 0 16