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

j j mj a a A a Ví dụï 1.5. Đưa bàøi toáùn QHTT sau đây vê àà dạïng chính tắéc vàø viếát bàøi toáùn chính tắéc dướùi dạïng ma trậän Thêm 2 â åån phụï x4, x5 0 vàøo ràøng buộäc thứù nhấát vàø ràøng buộäc thứù ba. Thay x/3 = –x3 0 Thay x2 = x/2 –x//2 0, vớùi x/2, x//2 0 CÁÙC DẠÏNG CỦÛA BÀØI TOÁÙN QHTT 1 2 3 1 2 3 1 2 3 1 2 3 1 3 ( ) 3 2 min 3 2 7 2 4 12 4 3 8 10 0 0 f x x x x x x x x x x x x x x x Bàøi toáùn QHTT cóù dạïng chính tắéc như sau Bàøi toáùn QHTT dướùi dạïng ma trậän như sau f(x) = (1, 3, – 2, 0, 0, 0)T(x1, x/2, x//2, x/3, x4, x5) min (x1, x/2, x//2, x/3, x4, x5) (0, 0, 0, 0, 0, 0) CÁÙC DẠÏNG CỦÛA BÀØI TOÁÙN QHTT 1 2 2 3 1 2 2 3 4 1 2 2 3 1 2 2 3 5 1 2 2 3 4 5 ( ) 3 3 2 min 3 2 7 2 4 4 12 4 3 3 8 10 0, 0, 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 x x x x 1 2 2 3 4 5 3 1 1 2 1 0 7 2 4 4 1 0 0 12 4 3 3 8 0 1 10 x x x x x x Ví dụï 1.6. Cho bàøi toáùn QHTT sau: Ta cóù ma trậän hệä sốá củûa hệä ràøng buộäc: chứùa I3 nên bâ øøi toáùn quy hoạïch tuyếán tính trên cô ùù dạïng chuẩån. CÁÙC DẠÏNG CỦÛA BÀØI TOÁÙN QHTT 2 5 1 2 5 2 3 5 2 4 5 ( ) min 2 1 3 3 2 2 0 1,5j f x x x x x x x x x x x x x j 11020 10130 20011 A ÝØJLỊÙ ïỉ ÞßH× ÌĐßGỊ ÏË× ØĐßQÝØ ÌËÇÛ_Ị ÌSỊØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Mộät phương áùn x* = (x1*, x2*,..., xn*) củûa bàøi toáùn QHTT dạïng tổång quáùt làø phương áùn cựïc biênâ (P.A.C.B) nếáu x* = (x1*, x2*,..., xn*) thỏûa mãn chã ëët n ràøng buộäc độäc lậäp tuyếán tính. Tứùc làø: Trong đóù A làø ma trậän con cấáp n củûa hpt (*). Mộät P.A.C.B không suy biê áán làø mộät P.A.C.B thỏûa mãn õ đúùng n ràøng buộäc chặët. Mộät P.A.C.B suy biếán làø mộät P.A.C.B thỏûa mãn õ hơn n ràøng buộäc chặët. P.A.C.B còøn đượïc gọïi làø phương áùn cơ bảûn. ĐỊNH NGHĨA PHƯƠNG ÁÙN CỰÏC BIÊN *X la P.A.C.B j n * ij i j=1 * j a x = b , i=1,k,k m * k+l n,det A 0 x =0, j=1,l,l n Ví dụï 1.7. Cho bàøi toáùn QHTT Cáùc vectơ nàøo sau đâyâ làø phương áùn cựïc biên?â ĐỊNH NGHĨA PHƯƠNG ÁÙN CỰÏC BIÊN 1 2 3 1 2 3 1 1 2 3 1 2 3 2 3 ( ) 50 16 23 min 5 3 4 2 2 3 1 6 2 4 0 0 f x x x x x x x x x x x x x x x x 0, 1, 3X 3, 0, 0Y 23 62, , 5 5 Z ĐỊNH LÝÙ 1. (TÍNH CHẤÁT ĐẶËC TRƯNG CỦÛA P.A.C.B) Mộät phương áùn X* = (x1*, x2*,…, xn*) củûa bàøi toáùn QHTT dạïng chính tắéc làø phương áùn cựïc biên nê ááu vàø chỉ nếáu hệä vectơ cộät Aj ứùng vớùi thàønh phầàn xj* > 0 làø độäc lậäp tuyếán tính. Ví dụï 1.8. Cho bàøi toáùn QHTT Cáùc vectơ nàøo sau đây X = (2, 2, 0), Y = (0, 0, 4), â Z = (1, 1, 2), làø P.A.C.B củûa bàøi toáùn. CÁÙC TÍNH CHẤÁT CỦÛA BÀØI TOÁÙN QHTT 1 2 3 1 2 3 1 2 ( ) 2 3 min 4 0 0, 1,3j f x x x x x x x x x x j X, Y, Z thỏûa cáùc ràøng buộäc nên chuâ ùùng làø P.A. Mặët kháùc ta cóù Vớùi X = (2, 2, 0), nên X lâ øø P.A.C.B. Vớùi Y = (0, 0, 4), hệä chỉ gồàm mộät vectơ A3 nên â Y cũng lã øø P.A.C.B. Vớùi Z=(1, 1, 2), ta thấáy hệä {A1, A2, A3} phụï thuộäc tuyếán tính vì A1+A2–2A3=0 nên Z không lâ â øø P.A.C.B. HỆÄ QUẢÛ 1. (tính hữu hã ïïn củûa P.A.C.B). Sốùáù phương áùn cựïc biên cuâ ûûa bàøi toáùn QHTT dạïng chính tắéc làø hữu hã ïïn. CÁÙC TÍNH CHẤÁT CỦÛA BÀØI TOÁÙN QHTT 1 1 1 A 2 1 1 A 3 1 0 A 1 1 det 2 1 1 HỆÄ QUẢÛ 2. Sốùáù thàønh phầàn dương trong mỗi ã phương áùn cựïc biên cuâ ûûa bàøi toáùn quy hoạïch tuyếán tính dạïng chính tắéc tốái đa bằèng m (m làø sốá dòøng củûa ma tậän A). ĐỊNH LÝÙ 2. (SỰÏ TỒÀN TẠÏI CỦÛA PHƯƠNG ÁÙN TỐÁI ƯU) Nếáu bàøi toáùn quy hoạïch tuyếán tính cóù phương áùn vàø hàøm mụïc tiêu bị châ ëën dướùi (đốái vớùi f(x) min) hoặëc hàøm mụïc tiêu bị châ ëën trên â (đốái vớùi f(x) max) trên tâ ääp cáùc phương áùn thì bàøi toáùn cóù phương áùn tốái ưu. ĐỊNH LÝÙ 3. (SỰÏ TỒÀN TẠÏI CỦÛA P.A.C.B. TỐÁI ƯU) Nếáu bàøi toáùn QHTT dạïng chính tắéc cóù P.A.T.Ư thì bàøi toáùn cóù P.A.C.B tốái ưu (P.A.C.B.T.Ư). CÁÙC TÍNH CHẤÁT CỦÛA BÀØI TOÁÙN QHTT ĐỊNH LÝÙ 4. (SỰÏ TỒÀN TẠÏI NHIỀÀU P.A.C.B.T.Ư) Nếáu bàøi toáùn QHTT cóù P.A.T.Ư làø X0 vàø X1, X2 hai phương áùn kháùc nhau củûa bàøi toáùn thoảû X0 = X1 + (1– )X2, 0 1 thì X1, X2 làø P.A.T.Ư. NHẬÄN XÉÙT 1. Ta cóù thểå tìm P.A.T.Ư củûa bàøi toáùn QHTT trong sốá cáùc P.A.C.B củûa bàøi toáùn vàø cóù thểå xáùc định ngay P.A.C.B củûa bàøi toáùn dạïng chuẩån bằèng cáùch cho cáùc ẩån không cơ bâ ûûn bằèng không (xem â Ví dụï 1.9). 2. Trong bàøi toáùn QHTT dạïng chính tắéc. Nếáu hạïng củûa ma trậän hệä sốá A làø m thì P.A.C.B đượïc gọïi làø không suy biê áán nếáu nóù cóù đúùng m thàønh phầàn dương. Nếáu P.A.C.B cóù ít hơn m thàønh phầàn dương thì đượïc gọïi làø P.A.C.B suy biếán (xem Ví dụï 1.10). CÁÙC TÍNH CHẤÁT CỦÛA BÀØI TOÁÙN QHTT ÝØJLỊÙ ïỉ ÞßH× ÌĐßGỊ ÏË× ØĐßQÝØ ÌËÇÛ_Ị ÌSỊØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ô g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Ví dụï 1.9 . Vớùi bàøi toáùn quy hoạïch tuyếán tính Ta cóù phương áùn X = (1, 0, 3, 2, 0) làø phương áùn cựïc biên cuâ ûûa bàøi toáùn vì cáùc ẩån x1, x3, x4 làø cáùc ẩån cơ bảûn củûa bàøi toáùn dạïng chuẩån. CÁÙC TÍNH CHẤÁT CỦÛA BÀØI TOÁÙN QHTT 5,10 22 33 12 min)( 542 532 521 52 jx xxx xxx xxx xxxf j Ví dụï 1.10 . Vớùi bàøi toáùn quy hoạïch tuyếán tính Kiểåm tra vectơ X = (11, 3, 0, 0) cóù phảûi làø P.A.C.B? Kiểåm tra trựïc tiếáp, ta cóù X làø P.A củûa bàøi toáùn. Hạïng củûa ma trậän hệä sốá củûa hệä ràøng buộäc tuyếán tính bằèng 3 vàø X cóù 2 thàønh phầàn dương làø x1 =11, x2 = 3 nên X lâ øø P.A.C.B suy biếán. CÁÙC TÍNH CHẤÁT CỦÛA BÀØI TOÁÙN QHTT 1 2 3 4 1 2 4 1 2 3 4 1 2 3 4 ( ) 3 4 2 2 min 2 2 28 5 3 2 26 2 2 2 16 0 1,4j f x x x x x x x x x x x x x x x x x j Ths. Nguyễn Công Trã â í Copyright 2001 4.1. PHƯƠNG PHÁÙP HÌNH HỌÏC (Xem) 4.2. PHƯƠNG PHÁÙP ĐƠN HÌNH (Xem) 4.3.PHƯƠNG PHÁÙP ĐƠN HÌNH MỞÛ RỘÄNG (BÀØI TOÁÙN M) (Xem) CÁÙC PHƯƠNG PHÁÙP GIẢÛI BÀØI TOÁÙN QUY HOẠÏCH TUYẾÁN TÍNH ax+by=c PHƯƠNG PHÁÙP HÌNH HỌÏC ax+by>c ax+by<c O =m (đườøng mứùc) a b tăngê giảûm N(a,b) Xéùt bàøi toáùn QHTT cóù 2 biếán. Ví dụï 1.11. Mộät công ty cô ùù 2 phân xâ ưởûng: PX1 vàø PX2 cùøng sảûn xuấát 2 loạïi sảûn phẩåm A vàø B. Năng ê suấát vàø chi phí sảûn xuấát củûa mỗi PX trong 1 giơã øø: Đơn đặët hàøng: ít nhấát 5.000 SpA, 3.000 SpB. Hãy phân phõ â áái thờøi gian hoạït độäng củûa 2 phân â xưởûng sao cho thoảû yêu câ ààu đơn đặët hàøng vàø chi phí sảûn xuấát thấáp nhấát. 10,6Chi phí (triệäu đồàng/ giờø) 200100Sảûn phẩåm B 250250Sảûn phẩåm A PX2PX1Phân xâ ưởûng Năng suă áát PHƯƠNG PHÁÙP HÌNH HỌÏC Gọïi x1, x2 lầàn lượït làø sốá giờø hoạït độäng củûa phân â xưởûng thứù nhấát vàø phân xâ ưởûng thứù hai. Ta cóù mô hâ ình bàøi toáùn Dùøng phương pháùp hình họïc đểå giảûi bàøi toáùn trên nhâ ư sau PHƯƠNG PHÁÙP HÌNH HỌÏC 1 2 1 2 1 2 1 2 0,6 min 250 250 5000 100 200 3000 0 0 f x x x x x x x x x ÝØJLỊÙ ïỉ ÞßH× ÌĐßGỊ ÏË× ØĐßQÝØ ÌËÇÛ_Ị ÌSỊØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com 10 20 30 10 15 20 250x1+250x2=5000 100x1+200x2=3000 0,6x1+x2=m tăngê giảûm Miềàn ràøng buộäc DA1(0,20) A2(30,0) A3 (10,10) PHƯƠNG PHÁÙP HÌNH HỌÏC Vậäy P.A.T.Ư: xopt(10,10) vàø f(xopt)=16 triệäu đồàng. Ví dụï 1.12. Giảûi bàøi toáùn quy hoạïch tuyếán tính bằèng phương pháùp hình họïc 1 2 1 2 1 2 1 2 2 min 2 2 2 0 0 f x x x x x x x x x PHƯƠNG PHÁÙP HÌNH HỌÏC Hàøm mụïc tiêu không bị châ â ëën. Bàøi toáùn không â cóù phương áùn tốái ưu. -2 2 2 x1-x2= -2 tăngê giảûm Miềàn ràøng buộäc D -1 -x1+2x2= -2 A1(0,2) A2(2,0)O -1 -2x1+x2= m PHƯƠNG PHÁÙP HÌNH HỌÏC Ví dụï 13: giảûi bàøi toáùn Đưa bàøi toáùn vềà dạïng chính tắéc 1 2 3 1 2 3 1 2 3 1 2 3 ( ) 3 2 min 2 4 3 10 3 4 5 2 2 8 0 1,3j f x x x x x x x x x x x x x x j CƠ SỞÛ PHƯƠNG PHÁÙP ĐƠN HÌNH 1 2 3 1 2 3 1 1 2 3 2 1 2 3 3 ( ) 3 2 min 2 4 3 10 3 4 5 2 2 8 0, 1,3, 0, 1,3j i f x x x x x x x w x x x w x x x w x j w i Ta cóù P.A.C.B làø x = (0, 0, 0, 10, 5, 8) Bàøi toáùn tương đương cóù P.A.C.B làø x = (0, 0, 0, 10, 5, 8) vàø f(x) = 0. Nhậän xéùt: cóù thểå đổåi P.A bằèng cáùch tăng xê 1 bằèng mộät giáù trị dương vàø giửû x2 = x3 = 0 thỏûa điềàu kiệän wi 0. CƠ SỞÛ PHƯƠNG PHÁÙP ĐƠN HÌNH 1 2 3 1 1 2 3 2 1 2 3 3 1 2 3 ( ) 3 2 min 10 2 4 3 5 3 4 8 2 2 0 1,3, 0, 1,3j i f x x x x w x x x w x x x w x x x x j w i Ta cóù Chọïn x1 = 5/3, ta đượïc P.A mớùi làø x1 = 5/3, x2 = x3 = w2 = 0, w1 = 20/3, w3 = 19/3. Vàø f(x) = - 5. Bàøi toáùn tương đương: tạïi ràøng buộäc thứù hai tính x1 theo cáùc biếán còøn lạïi, rồài thếá giáù trị x1 vừøa tính đượïc vàøo cáùc ràøng buộäc vàø hàøm mụïc tiêu.â CƠ SỞÛ PHƯƠNG PHÁÙP ĐƠN HÌNH 1 1 1 2 1 1 1 3 1 1 510 2 0 5 55 3 0 3 3 8 0 8 xw x w x x x w x x (Chọn dòng 2) ÝØJLỊÙ ïỉ ÞßH× ÌĐßGỊ ÏË× ØĐßQÝØ ÌËÇÛ_Ị ÌSỊØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ô g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Ta cóù kếát quảû Nhậän xéùt: cóù thểå đổåi P.A bằèng cáùch tăng xê 2 bằèng mộät giáù trị dương vàø giửû x3 = w2 = 0 thỏûa điềàu kiệän wi 0. CƠ SỞÛ PHƯƠNG PHÁÙP ĐƠN HÌNH 2 2 3 1 2 2 3 1 2 2 3 3 2 2 3 ( ) 5 3 min 20 2 10 1 3 3 3 3 5 1 1 4 3 3 3 3 19 1 5 2 3 3 3 3 0 1,3, 0, 1,3j i f x w x x w w x x x w x x w w x x x j w i Ta cóù Chọïn x2 = 2, ta đượïc P.A mớùi làø x1 = 1, x3 = w1 = w2 = 0, w3 = 3 vàø f(x) = - 7. Bàøi toáùn tương đương: tạïi ràøng buộäc thứù nhấát tính x2 theo cáùc biếán còøn lạïi, rồài thếá giáù trị x2 vừøa tính đượïc vàøo cáùc ràøng buộäc vàø hàøm mụïc tiêu.â CƠ SỞÛ PHƯƠNG PHÁÙP ĐƠN HÌNH 1 1 2 1 2 2 2 2 3 2 20 10 0 3 3 2 5 1 0 5 2 3 3 1919 5 0 53 3 w x x x x x x xw x (Chọn dòng 1) Ta cóù kếát quảû Bàøi toáùn cóù P.A.T.U làø xopt = (1, 2, 0) vàø f(xopt) = - 7 CƠ SỞÛ PHƯƠNG PHÁÙP ĐƠN HÌNH 1 2 3 2 1 2 3 1 1 2 3 3 1 3 3 4 31( ) 7 min 10 5 10 3 1 12 10 5 10 1 6 391 10 15 30 1 23 2 3 0 1,3, 0, 1,3j i f x w w x x w w x x w w x w w x x j w i 1 , 1 ( ) min max 1 2 0 1, 0 3 n j j j n m i i m k m k i k j i f x c x hay x a x b x j n b CƠ SỞÛ PHƯƠNG PHÁÙP ĐƠN HÌNH 0 0 1 2 1 ( , , ; ,.0 ,0) ( ) m m i i i x b b b f x c b 1 2, ( , , , )nx D x x x x 1 1 1 ( ) n m n m j j i i m k m k j i k f x c x c x c x Dựïa trên cơ sơâ ûû bàøi toáùn cóù dạïng chuẩån Dấáu hiệäu tốái ưu củûa bàøi toáùn Phương áùn cựïc biên â đầàu tiên lâ øø: Chọïn mộät P.A bấát kỳø củûa bàøi toáùn CƠ SỞÛ PHƯƠNG PHÁÙP ĐƠN HÌNH , 1 2 , n m i i i m k m k k x b a x , 1 1 1 m n m m i i i m k i m k m k i k i f x c x a c c x , 1 m m k i m k i m k i a c c 0 1 n m m k m k k f x f x x 0m k 0 ,f x f x 0m kx 0m k 0 ,f x f x 0m kx 1 m j ij i j i a c c ( )f x Min 0;j j ( )f x Max 0;j j Đặët thì Nếáu thì vì Nếáu thì vì Kýù hiệäu lạïi: (1) Khi thì (2) Khi thì Dấáu hiệäu bàøi toáùn không cô ùù P.A.T.Ư Định lýù. Vớùi mộät phương áùn cựïc biên, nê ááu tồàn tạïi j > 0 màø aij 0, i thì bàøi toáùn không cô ùù P.A.T.Ư. (xem Ví dụï 1.13) CƠ SỞÛ PHƯƠNG PHÁÙP ĐƠN HÌNH C1 C2 … Ci … Cm Cm+1 … Cj … CnHệä sốá Aåån C.B PA CB x1 x2 … xi … xm xm+1 … xj … xm C1 x1 b1 1 0 … … … 0 a1,m+1 … a1j … a1n C2 x2 b2 0 1 … … … 0 a2,m+1 … a2j … a2n Ci xi bi 0 0 … … … 0 ai,m+1 … aij … ain xm bm 0 0 … … … 1 am,m+1 … amj … amnCm f(x) f(x0) 0 0 … … … 0 m+1 … j … n ÝØJLỊÙ ïỉ ÞßH× ÌĐßGỊ ÏË× ØĐßQÝØ ÌËÇÛ_Ị ÌSỊØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com C1 C2 … Ci … Cm Cm+1 … Cj … CnHệä sốá ẨÅn C.B PA CB x1 x2 … xi … xm xm+1 … xj … xm C1 x1 b1 1 0 … … … 0 a1,m+1 … a1j … a1n C2 x2 b2 0 1 … … … 0 a2,m+1 … a2j … a2n Ci xi bi 0 0 … … … 0 ai,m+1 … aij … ain xm bm 0 0 … … … 1 am,m+1 … amj … amnCm f(x) f(x0) 0 0 … … … 0 m+1 … j … n Dấáu hiệäu bàøi toáùn cóù P.A.C.B. kháùc tốát hơn Định lýù. Vớùi mộät P.A.C.B, nếáu j>0, i: aij > 0 thì bàøi toáùn cóù P.A.C.B kháùc tốát hơn P.A.C.B đang xéùt. CƠ SỞÛ PHƯƠNG PHÁÙP ĐƠN HÌNH BẢÛNG ĐƠN HÌNH C1 C2 … Ci … Cm Cm+1 … CJ … CnHệ Số Ẩn C.B PA CB x1 x2 … xi … xm xm+1 … xj … xn C1 x1 b1 1 0 … … … 0 a1,m+1 … a1j … a1n C2 x2 b2 0 1 … … … 0 a2,m+1 … a2j … a2n Ci xi bi 0 0 … … … 0 ai,m+1 … aij … ain xm bm 0 0 … … 1 am,m+1 … amj … amnCm f(x) f(x0) 0 0 … … … 0 m+1 … j … n j 0, j? THUẬÄT GIẢÛI ĐƠN HÌNH Sai Đúùng Sai Đúùng LẬÄP BẢÛNG ĐƠN HÌNH XÁÙC ĐỊNH PHƯƠNG ÁÙN MỚÙI Aåån vàøo: Aåån ra: 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 0j j jMax x 0ij i ia ij bMin x a SỐÁ BƯỚÙC LẶËP LÀØ HỮU Hà ÏÏN THUẬÄT GIẢÛI ĐƠN HÌNH NHẬÄN XÉÙT. Dấáu hiệäu bàøi toáùn cóù nhiềàu P.A.T.Ư. Vớùi P.A.C.B.T.Ư Xopt tìm đượïc, nếáu j = 0, màø xj không lâ øø P.A.C.B thì bàøi toáùn cóù P.A.C.B.T.Ư kháùc X/opt (xem Ví dụï 1.15). Tậäp phương áùn tốái ưu: Trườøng hợïp cóù 2 P.A.C.B.T.Ư Xopt vàø X/opt Topt = { Xopt + (1 – )X/opt, [0, 1]} Trườøng hợïp cóù 3 P.A.C.B.T.Ư X(1)opt, X(2)opt, X(3)opt Topt = { X(1)opt + X(2)opt + X(3)opt, }, vớùi , , 0 vàø + + = 1. 1 2 3 4 5 6 7 1 2 4 6 7 1 3 4 6 7 1 4 5 6 ( ) 6 3 7 6 min 3 2 4 2 9 4 2 3 2 0 1,7j f x x x x x x x x x x x x x x x x x x x x x x x j Ví dụï 1.14. Giảûi bàøi toáùn quy hoạïch tuyếán tính THUẬÄT GIẢÛI ĐƠN HÌNH BT không cô ùù P.A.T.Ư vì 4= 1 > 0 màø ai4 < 0, i. HỆÄ SỐÁ ẨÅN C.B P.A 1x 2x 3x 4x 5x 6x 7x 6 1 1 3 1 7 6 2x 3x 5x 1 1 1 3 9 2 1 2 4 1 0 0 1 1 4 2 2 3 1 f x 14 5 0 0 6 0 7 6 0 0 0 0 0 1 1 1 6x 3x 5x 7 1 1 3 1 1 0 1 0 1 1 3 0 2 1 2 0 30 11 1 3 0 1 0 31 f x 7 2 7 0 1 0 0 13 THUẬÄT GIẢÛI ĐƠN HÌNH ÝØJLỊÙ ïỉ ÞßH× ÌĐßGỊ ÏË× ØĐßQÝØ ÌËÇÛ_Ị ÌSỊØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Ví dụï 1.15. Giảûi bàøi toáùn quy hoạïch tuyếán tính Bàøi toáùn cóù phương áùn tốái ưu kháùc hay không? â Nếáu cóù tìm tậäp phương áùn tốái ưu vàø chỉ ra 3 phương áùn tốái ưu. 1 2 3 4 5 6 1 2 3 4 1 2 3 5 1 3 6 ( ) 5 4 5 2 3 min 2 4 3 152 4 2 3 60 3 36 0 1,6j f x x x x x x x x x x x x x x x x x x x j THUẬÄT GIẢÛI ĐƠN HÌNH HỆÄ SỐÁ ẨÅN C.B P.A 1x 2x 3x 4x 5x 6x 5 4 5 2 1 3 4x 5x 6x 2 1 3 152 60 36 2 4 3 4 2 0 1 3 3 1 0 0 f x 472 12 6 7 0 0 0 0 0 0 01 1 4x 5x 1x 2 1 5 128 0 4 7 3 1 0 2 3 12 0 2 5 3 0 4 31 12 1 0 13 0 130 f x 328 0 6 3 0 0 4 THUẬÄT GIẢÛI ĐƠN HÌNH Bàøi toáùn cóù P.A.T.Ư xopt=(12, 6, 0, 104, 0, 0) vàø f(xopt)= 292. Bàøi toáùn còøn P.A.C.B.T.Ư kháùc vì 6 = 0, nhưng x6 không phâ ûûi làø A.C.B. Ta cóù P.A.C.B.T.Ư thứù hai bằèng cáùch chọïn ẩån x6 làø ẩån đưa vàøo. HỆÄ SỐÁ ẨÅN C.B P.A 1x 2x 3x 4x 5x 6x 5 4 5 2 1 3 4x 2x 1x 2 4 5 104 0 0 1 1 2 2 6 0 1 5 6 0 2 312 12 1 0 13 0 130 f x 292 0 0 2 0 3 0 THUẬÄT GIẢÛI ĐƠN HÌNH Bàøi toáùn cóù phương áùn cựïc biên tô áái ưu kháùc làø x/opt = (0, 30, 0, 32, 0, 36) vàø f(x/opt) = 292. Tậäp phương áùn tốái ưu Topt={ xopt + (1 - )x/opt, 0, 1 } HỆÄ SỐÁ ẨÅN C.B P.A 1x 2x 3x 4x 5x 6x 5 4 5 2 1 3 4x 2x 6x 2 4 3 32 6 0 3 1 2 0 30 2 1 3 2 0 012 36 3 0 1 0 10 f x 292 0 0 2 0 3 0 THUẬÄT GIẢÛI ĐƠN HÌNH Vớùi tậäp phương áùn tốái ưu, ta cóù : xopt + (1 - )x/opt = (12, 6, 0, 104, 0, 0) + (1- )(0, 30, 0, 32, 0, 36) = (12 , 30–24 , 0, 32 + 72 , 0, 36 - 36 ) 3 phương áùn tốái ưu làø Vớùi = 0, ta cóù P.A.T.Ư: x/opt = (0, 30, 0, 32, 0, 36) vàø f(x/opt) = 292. Vớùi = 1, ta cóù P.A.T.Ư: xopt = (12, 6, 0, 104, 0, 0) vàø f(x/opt) = 292. Vớùi = ½, ta cóù P.A.T.Ư: Zopt = (6, 18, 0, 68, 0, 18) vàø f(zopt) = 292. THUẬÄT GIẢÛI ĐƠN HÌNH NHẬÄN XÉÙT. Nếáu bàøi toáùn cóù hàøm mụïc tiêuâ Cóù hai cáùch giảûi: Giảûi trựïc tiếáp bàøi toáùn (xem Ví dụï 1.16), vớùi: Tiêu chuâ åån tốái ưu làø ẨÅn vàøo làø ẨÅn ra làø Chuyểån hàøm mụïc tiêu cuâ ûûa bàøi toáùn vềà min 1 ( ) n j j j f x c x Max ( ) ( )g x f x Min 0,j j 0j jMin THUẬÄT GIẢÛI ĐƠN HÌNH 0ij i a ij bMin a ÝØJLỊÙ ïỉ ÞßH× ÌĐßGỊ ÏË× ØĐßQÝØ ÌËÇÛ_Ị ÌSỊØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Ví dụï 1.16. Giảûi bàøi toáùn quy hoạïch tuyếán tính Bàøi toáùn cóù phương áùn tốái ưu kháùc hay không? â Nếáu cóù, hãy chõ ỉ ra phương áùn tốái ưu kháùc. 1 2 3 4 1 2 3 4 2 3 4 3 4 ( ) 2 max 2 2 7 3 2 3 2 5 0 1,4j f x x x x x x x x x x x x x x x j THUẬÄT GIẢÛI ĐƠN HÌNH Đưa bàøi toáùn vềà dạïng chính tắéc bằèng cáùch thêm â åån phụï x5 0 vàøo ràøng buộäc thứù hai vàø ẩån phụï x6 0 vàøo ràøng buộäc thứù ba. Ta cóù bàøi toáùn ởû dạïng chuẩån Lậäp bảûng đơn hình 1 2 3 4 1 2 3 4 2 3 4 5 3 4 6 ( ) 2 max 2 2 7 3 2 3 2 5 0 1,6j f x x x x x x x x x x x x x x x x x j THUẬÄT GIẢÛI ĐƠN HÌNH HỆÄ SỐÁ ẨÅN C.B P.A 1x 2x 3x 4x 5x 6x 2 1 1 1 0 0 1x 5x 6x 2 0 0 2 2 5 1 0 0 1 1 0 1 2 7 3 3 2 f x 4 0 1 5 1 0 0 0 0 0 01 1 3x 5x 6x 1 0 0 1 12 12 1 12 0 0 9 7 2 5 2 0 12 01 8 3 2 3 2 0 12 10 f x 1 5 2 3 2 0 32 0 0 THUẬÄT GIẢÛI ĐƠN HÌNH Vì cáùc j 0, j nên bâ àøi toáùn cóù P.A.T.Ư làø Xopt = (0, 0, 9, 16) vàø f(Xopt) = 25. Bàøi toáùn trên không cô â øøn phương áùn tốái ưu nàøo kháùc vì không cô ùù j = 0 nàøo vớùi xj làø ẩån không â cơ bảûn. HỆÄ SỐÁ ẨÅN C.B P.A 1x 2x 3x 4x 5x 6x 2 1 1 1 0 0 3x 5x 4x 1 0 1 9 2 2 1 0 0 1 17 5 4 0 0 11 16 3 3 0 1 20 f x 25 7 6 0 0 0 3 THUẬÄT GIẢÛI ĐƠN HÌNH Xuấát pháùt từø bàøi toáùn dạïng chính tắéc Không lâ øøm mấát tính tổång quáùt củûa bàøi toáùn, ta giảû sửû cáùc bi 0 vàø ma trậän hệä sốá củûa hệä ràøng buộäc không châ ứùa vectơ (cộät) đơn vị nàøo. Cộäng vàøo mỗi rẫ øøng buộäc vớùi mộät ẩån giảû tương ứùng xi(g) 0 thì ta đượïc bàøi toáùn cóù dạïng: CƠ SỞÛ THUẬÄT GIẢÛI ĐƠN HÌNH MỞÛ RỘÄNG 1 1 ( ) , 1, 0 1, 0 n j j j n ij j i j j i f x c x Min a x b i m I x j n b Bàøi toáùn (I) đượïc gọïi làø bàøi toáùn gốác, bàøi toáùn (II) gọïi làø bàøi toáùn mởû rộäng hay bàøi toáùn M. Mộät phương áùn củûa bàøi toáùn M cóù dạïng trong đóù xj gồàm n ẩån thậät vàø xi(g) gồàm m ẩån giảû. CƠ SỞÛ THUẬÄT GIẢÛI ĐƠN HÌNH MỞÛ RỘÄNG 1 1 1 ( ) , 1, 0, 1, ; 0, 1, , 0 vo â cùng lớn. n m g j j i j i n g ij j i i j g j i f x c x M x Min a x x b i m II x j n x i m M , gj ix x x ÝØJLỊÙ ïỉ ÞßH× ÌĐßGỊ ÏË× ØĐßQÝØ ÌËÇÛ_Ị ÌSỊØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Trong đóù cáùc xn+i (i = 1, 2, ..., m) làø cáùc ẩån giảû. C1 C2 … Cm Cm+1 … Cj … CnHệ Số Ẩn C.B PA CB x1 x2 … xm xm+1 … xj … xn M xn+1 b1 a11 a12 … a1m a1,m+1 … a1j … a1,n M x n+2 b2 a21 a22 … a2m a2,m+1 … a2j … a2,n M x n+i bi ai1 ai2 … aim ai,m+1 … aij … ai,n xn+m bm am1 am2 … amm am,m+1 … amj … am,nM f(x) f(x0) 1 2 … m m+1 … j … n BẢÛNG ĐƠN HÌNH MỞÛ RỘÄNG NHẬÄN XÉÙT. Khi thuậät giảûi củûa bàøi toáùn M kếát thúùc thì cóù hai trườøng hợïp sau đây cô ùù thểå xảûy ra: [1] Nếáu bàøi toáùn M (Bàøi toáùn II) không cô ùù phương áùn tốái ưu thì bàøi toáùn gốác (Bàøi toáùn I) cũng không cõ â ùù phương áùn tốái ưu. [2] Nếáu bàøi toáùn M (Bàøi toáùn II) cóù phương áùn tốá i ưu thì cóù 3 trườøng hợïp xảûy ra sau đây:â a) Trong hệä A.C.B không châ ứùa ẩån giảû nàøo thì P.A.T.Ư củûa bàøi toáùn M cũng chõ ính làø P.A.T.Ư củûa bàøi toáùn gốác (xem Ví dụï 1.17). CƠ SỞÛ THUẬÄT GIẢÛI ĐƠN HÌNH MỞÛ RỘÄNG b) Nếáu trong hệä ẩån cơ bảûn củûa bàøi toáùn M cóù chứùa ẩån giảû nhưng giáù trị củûa chúùng đềàu bằèng không thâ ì P.A.T.Ư củûa bàøi toáùn gốác làø P.A.T.Ư. củûa bàøi toáùn M loạïi bỏû cáùc ẩån giảû bằèng không â (xem Ví dụï 1.18). c) Nếáu trong hệä ẩån cơ bảûn củûa bàøi toáùn M cóù mộät ẩån giảû màø giáù trị củûa chúùng kháùc không thâ ì bàøi toáùn gốác không cô ùù P.A.T.Ư. Chúù ýù. Nếáu hàøm mụïc tiêu lâ øø f(x) Max thì hệä sốá cáùc ẩån giảû trong hàøm mụïc tiêu cuâ ûûa bàøi toáùn M làø (– M), vớùi M > 0 vô cuâ øøng lớùn (xem Ví dụï 1.19). CƠ SỞÛ THUẬÄT GIẢÛI ĐƠN HÌNH MỞÛ RỘÄNG Đúùng Sai aij 0? Sai Đúùng Khôngâ CóùĐúùng j 0? THUẬÄT GIẢÛI ĐƠN HÌNH MỞÛ RỘÄNG Sai LẬÄP BẢÛNG ĐƠN HÌNH Xáùc định phương áùn mớùi Aåån vàøo: Aåån ra: CÓÙ P.A.T.Ư ĐƯA BÀØI TOÁÙN VỀÀ DẠÏNG CHUẨÅN KHÔNG CÓÙ P.A.T.Ư KẾÁT THÚÙC THUẬÄT GIẢÛI CÓÙ P.A.T.Ư BIẾÁN ĐỔÅI BẢÛNG ĐƠN HÌNH ?gix 0? g ix KHÔNG CÓÙ P.A.T.Ư 0j jMax 0ij i a ij bMin a SỐÁ BƯỚÙC LẶËP LÀØ HỮU Hà ÏÏN Ví dụï 1.17. (trườøng hợïp a). Giảûi bàøi toáùn QHTT Nhân (⠖ 1) vàøo ràøng buộäc thứù nhấát, bàøi toáùn cóù dạïng chính tắéc như sau 1 2 3 1 2 3 1 2 3 ( ) 8 6 2 min 4 4 3 18 4 3 4 16 0 1,3j f x x x x x x x x x x x j THUẬÄT GIẢÛI ĐƠN HÌNH MỞÛ RỘÄNG 1 2 3 1 2 3 1 2 3 ( ) 8 6 2 min 4 4 3 18 4 3 4 16 0 1,3j f x x x x x x x x x x x j Đưa bàøi toáùn vềà dạïng chuẩån: Thêm hai â åån giảû x4 0 vàø x5 0 vàøo lầàn lượït vàøo ràøng buộäc thứù nhấát vàø thứù hai củûa bàøi toáùn Bàøi toáùn cóù dạïng chuẩån như sau: Ta cóù bảûng đơn hình mởû rộäng 1 2 3 4 5 1 2 3 4 1 2 3 5 ( ) 8 6 2 ( ) 4 4 3 18 4 3 4 16 0 1,5 M 0 vo â cùng lớn.j f x x x x M x x Min x x x x x x x x x j THUẬÄT GIẢÛI ĐƠN HÌNH MỞÛ RỘÄNG ÝØJLỊÙ ïỉ ÞßH× ÌĐßGỊ ÏË× ØĐßQÝØ ÌËÇÛ_Ị ÌSỊØ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ̸­ị Ị¹«§»=² ݱ>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ¸¬¬°ỉđđ²½¬®·ị½±ị½½ Ng uy ễn C ôn g T rí PDF created with pdfFactory Pro trial version www.pdffactory.com Bàøi toáùn cóù P.A.T.Ư Xopt=(5/2, 2, 0), f(Xopt)= –8. HỆÄ SỐÁ ẨÅN C.B P.A 1x 2x 3x 8 6 2 4x 5x M M 18 16 4 4 4 3 3 4 f x 34M 8 8M 7 6M 2M 4x 1x M 8 2 0 1 7 4 1 3 4 1 f x 2 32M 0 12M 7 10M THUẬÄT GIẢÛI ĐƠN HÌNH MỞÛ RỘÄNG 2x 1x 6 8 2 5 2 0 1 1 0 7 25 4 f x 8 0 0 94 Ví dụï 1.18. (trườøng hợïp b). Giảûi bàøi toáùn QHTT Thêm â åån phụï x4 0 vàøo ràøng buộäc thứù nhấát 1 2 3 1 2 3 1 2 3 1 2 3 ( ) 6 3 min 2 5 10 4 3 2 16 2 4 8 0 1,3j f x x x x x x x x x x x x x x j THUẬÄT GIẢÛI ĐƠN HÌNH MỞÛ RỘÄNG 1 2 3 1 2 3 4 1 2 3 1 2 3 ( ) 6 3 min 2 5 10 4 3 2 16 2 4 8 0 1,4j f x x x x x x x x x x x x x x x j Thêm hai â åån giảû x5 0, x6 0 lầàn lượït vàøo ràøng buộäc thứù hai vàø ràøng buộäc thứù ba. Ta cóù bàøi toáùn dạïng chuẩån như sau Ta cóù bảûng đơn hình mởû rộäng 1 2 3 5 6 1 2 3 4 1 2 3 5 1 2 3 6 ( ) 6 3 ( ) min 2 5 4 3 2 2 4 0 1 1 6 , 0 8 6 1 j f x x x x M x x x x x x x x x x x x x x x j M 0 THUẬÄT GIẢÛI ĐƠN HÌNH MỞÛ RỘÄNG HỆÄ SỐÁ ẨÅN C.B P.A 1x 2x 3x 4x 6 3 1 0 4x 5x 6x 0 M M 10 16 8 2 4 2 5 3 1 2 1 0 0 f x 24M 6 6M 3M 3 1M 0 4 1 4x 5x 1x 0 M 6 2