›
›

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

pdf 26 trang hapham 1820
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tối ưu hóa - Chương 1: Bài toán quy hoạch tuyến tính", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_toi_uu_hoa_chuong_1_bai_toan_quy_hoach_tuyen_tinh.pdf

Nội dung text: Bài giảng Tối ưu hóa - Chương 1: Bài toán quy hoạch tuyến tính

  1. ThS. Phạm Trí Cao * Chương 1 03/01/2014 I) CAÙC VÍ DUÏ THÖÏC TEÁ CHÖÔNG 1:  Ví duï 1.1: Baøi toaùn laäp keá hoaïch saûn xuaát BAØI TOAÙN  Moät xí nghieäp coù 3 loaïi nguyeân lieäu A (ñöôøng), B QUY HOAÏCH TUYEÁN TÍNH (söõa), C (höông traùi caây) vôùi löôïng döï tröõ toái ña trong kho laàn löôït laø 10, 15, 13 taán. Xí nghieäp duøng caùc loaïi nguyeân lieäu naøy ñeå saûn xuaát ra 4 loaïi saûn phaåm keïo muùt: K1 (mum mum daâu), K2 (mum mum baïc haø), K3 (mum mum maät ong), K4 (mum mum döùa). Tieàn lôøi thu ñöôïc khi baùn caùc loaïi saûn phaåm keïo laàn löôït laø 4, 6, 5, 8 trieäu ñ/taán. 1 2 Loaïi Tyû leä pha cheá  Tyû leä pha cheá caùc loaïi nguyeân lieäu vôùi nhau ñeå Döï saûn xuaát ra caùc loaïi saûn phaåm cho trong baûng nguyeân K K K K tröõ 1 2 3 4 sau: lieäu (taán) (taán) (taán) (taán)  .  Haõy laäp keá hoaïch saûn xuaát caùc loaïi saûn phaåm A (taán) 10 1 2 3 4 sao cho: thoûa maõn yeâu caàu haïn cheá veà nguyeân B (taán) 15 3 1 4 2 lieäu, ñoàng thôøi toång soá tieàn lôøi thu ñöôïc lôùn C (taán) 13 2411 nhaát? Tieàn lôøi 4 6 5 8 (trieäu ñ/taán) 3 4 1
  2. ThS. Phạm Trí Cao * Chương 1 03/01/2014  Goïi xj laø löôïng saûn phaåm loaïi Kj caàn saûn xuaát  Ví duï 1.2: Baøi toaùn ñònh khaåu phaàn thöùc aên (taán), j= 1,4  Ñeå nuoâi 1 loaïi gia suùc, moät ñoäi saûn xuaát duøng 3  Vaäy ta coù moâ hình baøi toaùn laø: loaïi thöùc aên T1 (Tuctung), T2 (Cuncon), T3  Tìm veùc tô x= (x1,x2,x3,x4) sao cho: (Meoyeu). Trong 3 loaïi thöùc aên naøy coù chöùa 3  f(x)= 4x1 +6x2 +5x3 +8x4 max loaïi chaát dinh döôõng A (DHA), B ( A+), C (Canxi @).  x1 +2x2 +3x3 +4x4 = 0, j= 1,4  Giaûi baøi toaùn treân ta ñöôïc keát quaû: x= (4, 1, 0, 1) vaø f =30 5 max 6 Soá ñôn vò chaát dinh döôõng (g) coù  Ñeå gia suùc phaùt trieån toát vaø thoâng minh thì nhu trong 1 ñôn vò thöùc aên (kg): caàu toái thieåu veà caùc chaát dinh döôõng A, B, C trong khaåu phaàn aên haøng ngaøy cuûa gia suùc laàn Soá ñv chaát dd coù löôït laø: 17, 14, 14 g. Giaù thöùc aên T1,T2,T3 laàn Chaát dd trong 1 ñv thöùc aên löôït laø 5, 4, 7 (chuïc ngaøn ñ/kg). T1 T2 T3  Haõy xaùc ñònh löôïng thöùc aên moãi loaïi caàn coù A7 26 trong khaåu phaàn aên haøng ngaøy ñeå ñaûm baûo yeâu B 5 1 7 caàu veà chaát dinh döôõng, ñoàng thôøi toång soá tieàn mua thöùc aên haøng ngaøy laø nhoû nhaát? C 6 3 4 7 8 2
  3. ThS. Phạm Trí Cao * Chương 1 03/01/2014  Goïi xj laø löôïng thöùc aên loaïi Tj caàn cho aên haøng ngaøy (kg), j= 1,3  Vaäy moâ hình baøi toaùn laø:  Tìm veùc tô x= (x1,x2,x3) sao cho:  f(x)= 5x1 +4x2 +7x3 min  7x1 +2x2 +6x3 >= 17  5x1 +x2 +7x3 >= 14  6x1 +3x2 +4x3 >= 14  xj >=0, j= 1,3  Giaûi bt treân ta ñöôïc: x= (21/11, 0, 7/11) vaø f =14 9 min 10  – f(x) goïi laø haøm muïc tieâu.  – Khaùi nieäm phöông aùn toái öu (patö):  Caùc cj goïi laø caùc heä soá haøm muïc tieâu.  Baøi toaùn minf: Moät PA laøm cho haøm muïc tieâu ñaït cöïc  – Soá (2) goïi laø raøng buoäc chung. tieåu goïi laø phöông aùn toái öu (patö). Kyù hieäu laø x*.  Soá (3) goïi laø raøng buoäc bieán.  Nghóa laø: x D: f(x) >= f(x*)  Baøi toaùn maxf: Moät PA laøm cho haøm muïc tieâu ñaït cöïc  Heä (*) goïi laø heä raøng buoäc (mieàn raøng buoäc). ñaïi goïi laø phöông aùn toái öu (patö). Kyù hieäu laø x*.  –Caùcb goïi laø caùc heä soá töï do. i  Nghóa laø: x D: f(x) <= f(x*)  –Caùcaij goïi laø caùc heä soá cuûa raøng buoäc chung.  – Baøi toaùn QHTT coù patö goïi laø baøi toaùn giaûi ñöôïc.  – Moät veùc tô x goïi laø 1 phöông aùn (PA) cuûa baøi  – Giaûi baøi toaùn QHTT laø tìm caùc patö cuûa noù (neáu coù) toaùn neáu x thoûa heä raøng buoäc (*). hoaëc chöùng toû noù khoâng coù patö.  – Taäp hôïp taát caû caùc PA cuûa baøi toaùn goïi laø taäp  – Hai baøi toaùn QHTT goïi laø töông ñöông nhau neáu phöông aùn. Kyù hieäu D, X, Y, chuùng coù chung taäp patö. 11 12 3
  4. ThS. Phạm Trí Cao * Chương 1 03/01/2014 Phöông aùn cöïc bieân (phöông aùn cô baûn) cuûa baøi toaùn  Chuyeån baøi toaùn max veà baøi toaùn min: QHTT toång quaùt  f(x) max g(x)= f(x) min Khaùi nieäm raøng buoäc chaët, loûng. x Dx D Moät raøng buoäc goïi laø chaët ñoái vôùi pa x neáu khi ta thay x vaøo raøng buoäc naøy thì xaûy ra daáu baèng, thí duï  Ta coù 2 baøi toaùn laø töông ñöông nhau. n  a x b j 1 ij j i Moät raøng buoäc goïi laø loûng ñoái vôùi pa x neáu khi ta thay x vaøo raøng buoäc naøy thì xaûy ra daáu baát ñaúng thöùc thöïc n n söï, thí duï  a x b hoaëc  a x b j 1 ij j i j 1 ij j i Khaùi nieäm chaët, loûng xeùt cho caû raøng buoäc chung 13 14 vaø raøng buoäc bieán.  Khaùi nieäm phöông aùn cöïc bieân (pacb).  Ví duï 1:  Moät pa coù soá raøng buoäc chaët ñoäc laäp tuyeán tính  f= 3x1 +4x2 6x3 +7x4 min baèng n (soá bieán) goïi laø pacb.  2x1 +x2 +x3 x4 = 1 chaët ñoäc laäp tuyeán tính goïi laø pacb khoâng suy bieán.  x1>=0, x2>=0, x3>=0, x4<=0  Moät pacb coù soá raøng buoäc chaët nhieàu hôn soá raøng  buoäc chaët ñoäc laäp tuyeán tính goïi laø pacb suy bieán.  Chöùng minh caùc keát quaû sau:  Moät pa coù soá raøng buoäc chaët ñoäc laäp tuyeán tính ít hôn n goïi laø pa khoâng cöïc bieân.  1) x= (0, 1, 2, 0) laø pacbksb?  Löu yù:  2) x= (0, 2, 1, 0) laø pakcb?  Soá raøng buoäc chaët ñltt <= n (soá bieán)  Baøi giaûi chi tieát xem trong saùch. 15 Soá raøng buoäc chaët ñltt <= soá raøng buoäc chaët 16  VD2: pacbsb : xem trong saùch. 4
  5. ThS. Phạm Trí Cao * Chương 1 03/01/2014 2) Baøi toaùn QHTT daïng chính taéc * Daïng ma traän: * Daïng ñaïi soá: Ñaët: a a a n b x 11 12 1n 1 1 f(x)= c x min (max) (1) j j a a a b x j 1 21 22 2n 2 2 A , b , x n a x b , i= 1,m (2) ij j i a a a b x j 1 m1 m2 mn m n c c c c xj >=0 , j= 1,n (3) n 17 18 1 2  Ta vieát baøi toaùn (1)-(3) döôùi daïng ma traän:  Caùch chuyeån baøi toaùn toång quaùt veà daïng chính taéc:  f(x)= min (max)  Baát kyø baøi toaùn QHTT toång quaùt naøo cuõng  A.x= b coù theå ñöa veà daïng chính taéc baèng caùc  x>=0 pheùp bieán ñoåi tuyeán tính sau:  Vôùi quy öôùc:  * Raøng buoäc bieán:  Neáu x =0  x= (x1,x2, , xn)>=0 xj >= 0, j= 1,n j j j +  Neáu xj baát kyø thì ta ñaët xj =xj xj + vôùi xj ,xj >=0 19 20 5
  6. ThS. Phạm Trí Cao * Chương 1 03/01/2014  Ví duï 1.4: Baøi toaùn toång quaùt (P) * Raøng buoäc chung: n  f(x)= 3x1 +4x2 +7x3 max Neáu a x b thì theâm bieán phuï y >=0:  ij j i i  x1 +3x2 -2x3 = 3 a x y bi  ij j i j 1  xj >=0, j= 1,3 n  Vieát baøi toaùn daïng chính taéc (P*)? Neáu  a x b thì theâm bieán phuï yi >=0:  x*(P*)= (0, 3, 1, 0, 16) thì x*(P)= ? j 1 ij j i n  Neáu (P*) khoâng coù patö thì (P) cuõng a x y b khoâng coù patö.  ij j i i j 1  Baøi giaûi chi tieát xem trong saùch. 21 22  Ví duï 1.5: Baøi toaùn (P)  VD 1.6: Baøi toaùn (P)   f(x)= x1 +2x2 +x3 max f= x1 +0x2 +2x3 min   2x1 +x2 +3x3 =9 3x1 +x2 +4x3 =0, x2 = 4  x1 >=0 , x2 <=0 , x3 tuøy yù  Vieát baøi toaùn daïng chính taéc (P*)?  Vieát baøi toaùn chính taéc (P*) ?  x*(P*) = (0, 3/4, 13/4, 0) thì x*(P) = ?  x*(P*)= (1/10, 0, 33/10, 0, 35/10, 0) thì  Baøi giaûi chi tieát xem trong saùch. x*(P)= ?  Baøi giaûi chi tieát xem trong saùch. 23 24 6
  7. ThS. Phạm Trí Cao * Chương 1 03/01/2014  Phöông aùn cöïc bieân cuûa baøi toaùn daïng  Caùch xaùc ñònh pacb: chính taéc  x=(x1,x2, , xj , , xn) laø pa cuûa bt (1)-(3).  Baøi toaùn chính taéc daïng ma traän:  Ñaët: J(x)= {j / xj >0}  f(x) = min (max) (1)  Kyù hieäu: m(J) laø soá phaàn töû cuûa taäp J(x).  A.x = b (2)  x laø pa cöïc bieân heä veùc tô coät töông öùng vôùi caùc thaønh phaàn döông cuûa x ñoäc laäp tuyeán tính  x>=0 (3)  Nghóa laø: x= (x1,x2, , xn)laøpacb  {Aj /j J(x)} ñlaäp tt  Ta coù: A.x = b x1A1 +x2A2 + + xnAn =b  x laø pacb. Ta luoân coù: m(J) =0, j= 1,3  xj >=0, j= 1,3 j  Cmr x= (4, 0, 5) laø pacbksb?  Cmr x= (2, 4, 0) khoâng laø pacb?  Baøi giaûi chi tieát xem trong saùch.  Baøi giaûi chi tieát xem trong saùch. 27 28 7
  8. ThS. Phạm Trí Cao * Chương 1 03/01/2014  Ta coù caùc keát quaû cho baøi toaùn daïng chính taéc:  Ví duï 3:  Baøi toaùn coù theå coù pa hoaëc khoâng.  f=x1 +4x2 +x3 max  Neáu baøi toaùn coù pa thì noù coù pacb.  Baøi toaùn coù moïi pacb ñeàu khoâng suy bieán goïi laø baøi  x1 +x2 -x3 =7 toaùn khoâng suy bieán. Neáu coù ít nhaát 1 pacb suy bieán thì goïi laø baøi toaùn suy bieán.  -x1 +2x2 +x3 =14  Baøi toaùn minf : Neáu baøi toaùn coù pa vaø haøm muïc tieâu  xj >=0, j= 1,3 bò chaän döôùi thì baøi toaùn coù patö. Neáu f khoâng bò chaën döôùi thì f - .  Baøi toaùn maxf : Neáu baøi toaùn coù pa vaø haøm muïc tieâu  Cmr x= (0,7,0) laø pacbsb? bò chaän treân thì baøi toaùn coù patö. Neáu f khoâng bò chaën treân thì f + .  Baøi giaûi chi tieát xem trong saùch.  Neáu baøi toaùn coù patö thì baøi toaùn coù pacbtö.Moätpa goïi laø pacbtö neáu noù vöøa laø pacb vaø vöøa laø patö. 29 30  Neáu baøi toaùn coù 2 patö x1,x2 vôùi x1 x2 thì  3) Baøi toaùn QHTT daïng chuaån taéc .x1 +(1- ).x2 ,  [0,1] cuõng laø patö  Baøi toaùn QHTT daïng chuaån taéc laø baøi toaùn QHTT baøi toaùn coù voâ soá patö. daïng chính taéc thoûa theâm caùc ñieàu kieän sau:  - Caùc heä soá töï do bi beân veá phaûi cuûa caùc raøng buoäc chung phaûi >=0.  x laø pacb. Neáu x khoâng laø patö thì luoân tìm  - Moãi raøng buoäc chung phaûi coù bieán cô sôû töông öùng. ñöôïc pacb x' toát hôn x.  - Bieán cô sôû: laø bieán coù heä soá laø 1 ôû moät raøng buoäc Nghóa laø: chung vaø coù heä soá laø 0 ôû caùc raøng buoäc chung coøn laïi. Baøi toaùn minf: f(x') = f(x)  - Bieán cô sôû töông öùng vôùi veùc tô cô sôû, bieán töï do  Soá pacb cuûa baøi toaùn laø höõu haïn. töông öùng vôùi veùc tô töï do. 31 32 8
  9. ThS. Phạm Trí Cao * Chương 1 03/01/2014  Ví duï 1.7:  Ví duï 1.9:  f= x +2x +x -x min 1 2 3 4  f(x)= x1 + x2 –x3 max  x1 +x2 -x3 =7  x1 + x3 + x4 = 4  2x2 +x3 + x4 =5  x2 + 2x3 = 7  xj >= 0 , j= 1,4  xj >=0, j= 1,4   Höôùng daãn: Ñaây laø baøi toaùn daïng chuaån taéc.  Xeùt xem BT coù chuaån taéc khoâng?  Ta coù x1,x4 laø bieán cô sôû, x2,x3 laø bieán töï do.   Ta cho x2,x3 =0(caùc bieán töï do) thìtacoù:x1 =7, x4 =5(bieán cô sôû).  Baøi giaûi chi tieát xem trong saùch.  Vaäy ta coù pa x= (7, 0, 0, 5) laø pacb khoâng suy bieán. 33 34  Ví duï 1.9bis: III) PHÖÔNG PHAÙP HÌNH HOÏC GIAÛI BAØI TOAÙN QHTT  f(x)= x1 +x2 –x3 +6x6 max Vôùi baøi toaùn QHTT 2 bieán toång quaùt, ta coù theå duøng pp hình  x +x+ x =4 1 3 4 hoïc ñeå giaûi.  x +2x +x =7 2 3 5 Caùc keát quaû söû duïng ñeå giaûi baøi toaùn theo pp hình hoïc:  -5x3 +3x5 + x6 =0 Ñöôøng thaúng (D): ax+by=c chia maët phaúng Oxy thaønh 2  xj >=0, j= 1,6 mieàn: mieàn coù ax+by>c vaø mieàn coù ax+by c thì ta laáy 1 ñieåm baát kyø  Xeùt xem BT coù chuaån taéc khoâng? thay vaøo, thí duï ñieåm (0,0) thay vaøo : a.0+b.0 = 0, neáu 0 > c thì mieàn chöùa ñieåm (0,0) thoûa ax+by>c. 35 36 9
  10. ThS. Phạm Trí Cao * Chương 1 03/01/2014  Ví duï 1: Ñöôøng thaúng (D): ax+by=c goïi laø ñöôøng ñaúng möùc,  f(x)= 7x - 2y  5x - 4y >= -3 (qua A, C) coù phaùp veùc tô laø n =(a,b).  2x - 7y = -12 (qua B, C)  3x - 5y >= -20 (qua C, (0,4)) möùc c taêng leân.  1) Veõ taäp pa D?  3) Tìm minf, maxf? * Neáu di chuyeån (D) theo ngöôïc chieàu n thì giaù trò  Höôùng daãn:  1) Taäp pa laø 1 tam giaùc coù caùc ñænh laø A(1,2), möùc c giaûm xuoáng. 37 38 B(8,4), C(5,7). VD1 VD2 39 40 10
  11. ThS. Phạm Trí Cao * Chương 1 03/01/2014 VD4 VD3 41 42  IV) PHÖÔNG PHAÙP ÑÔN HÌNH GIAÛI BAØI VD6 TOAÙN QHTT  Böôùc 1: Laäp baûng ñôn hình xuaát phaùt  Töø baøi toaùn daïng chuaån ta xaùc ñònh caùc bieán cô sôû vaø veùc tô cô sôû töông öùng. Caùc bieán khoâng phaûi bieán cô sôû laø bieán töï do, vaø xaùc ñònh caùc veùc tô töï do töông öùng.  Xaùc ñònh pacb ban ñaàu xuaát phaùt: x= (x1,x2 , , xn).  Tacoù:J(x)={j/xj >0} taäp caùc chæ soá cuûa veùc tô cô sôû. 43 44 11
  12. ThS. Phạm Trí Cao * Chương 1 03/01/2014 Laäp baûng ñôn hình xuaát phaùt sau:  Ví duï 1.10: c c c Cô sôû Heä soá PA 1 2 n  f(x)= 6x1 +2x2 +x3 +3x4 +x5 -7x6 min A1 A2 An  -x + x +2x +x =15 1 2 4 6  4x1 +2x4 + x5 -3x6 =2 J J(x) Aj cj xj zj1 zj2 zjn  2x1 + x3 +x4 +2x6 =9  x >=0 , j= 1,6 f 1 2 n j f= f(x)= coät Heä soá * coät PA = c x :  Tacoùcaùcbieáncôsôûlaøx2,x3,x5 vaø veùc tô cô sôû laø  j j j J (x) A2,A3,A5. giaù trò haøm muïc tieâu öùng vôùi x.  caùc bieán töï do laø x1,x4,x6 vaø veùc tô töï do laø A1, k= coät Heä soá * coät Ak –ck =  c z c : A4,A6. j J (x) j jk k  x= (0, 15, 9, 0, 2, 0) laø pacb ban ñaàu. 45 heä soá öôùc löôïng cuûa bieán xk , k= 1,n 46  Böôùc 2: Xeùt daáu hieäu toái öu Baûng ñôn hình xuaát phaùt  Xem doøng ghi caùc heä soá öôùc löôïng 1, 2 , , n .  - Neáu coù k 0 vaø moïi phaàn töû thuoäc coät naøy (ôû böôùc laëp ñang xeùt) ñeàu <=0 khoâng? A3 1 9 2 0 1 1 0 (2)  - Neáu coù: BT khoâng coù patö (haøm muïc tieâu f khoâng B1 (doøng f) 41 -2 0 0 4 0 (8) bò chaän döôùi). Thuaät toaùn keát thuùc. 47 48 - Neáu khoâng: qua böôùc 4. 12
  13. ThS. Phạm Trí Cao * Chương 1 03/01/2014  Böôùc 4: Caûi tieán pa (Tìm moät pacb môùi toát  4.2) Choïn doøng chuû yeáu: hôn)   = min{ (coät PA/ coät CY) / vôùi caùc thaønh phaàn  Ta tìm pacb môùi x’= (x1’, ,xn’) toát hôn pacb x: döông cuûa coät CY} f(x’) 0} ,  Pacb x öùng vôùi baûng ñôn hình cuõ, pacb x’ öùng vôùi doøng chuû yeáu laø Ar. baûng ñôn hình môùi.   goïi laø tyû soá ñôn hình.  Laäp baûng ñôn hình môùi töø baûng ñôn hình cuõ nhö  4.3) Xaùc ñònh phaàn töû chuû yeáu: sau:  Phaàn töû CY laø phaàn töû naèm ôû vò trí: doøng chuû yeáu,  4.1) Choïn coät chuû yeáu: coät chuû yeáu, kyù hieäu laø zrs .  Choïn coät chuû yeáu laø coät coù döông lôùn nhaát.  Löu yù: Giaù trò haøm muïc tieâu khi chuyeån töø baûng  Töùc laø: choïn s sao cho s =max{ k / k >0}, coät cuõ sang baûng môùi seõ giaûm 1 löôïng laø . s : 49 chuû yeáu kyù hieäu laø A . 50 s  f(x’) = f(x) – . s  4.4) Laäp ra baûng môùi döïa vaøo baûng cuõ:  Ta nhaän thaáy, töø baûng cuõ chuyeån sang baûng  4.4.1) Treân coät cô sôû:ThayAr bôûi As , giöõ nguyeân môùi trong coät Cô sôû: ta loaïi ra 1 veùc tô (Ar) caùc phaàn töû coøn laïi. vaø thay baèng 1 veùc tô môùi (As), caùc veùc tô  Treân coät Heä soá:Thaycr bôûi cs , giöõ nguyeân coøn laïi giöõ nguyeân. caùc phaàn töû coøn laïi.  Do ñoù, ta bieán ñoåi sao cho ôû baûng môùi coät As  4.4.2) Caùc phaàn töû coøn laïi cuûa baûng: coùdaïng(0, ,1, ,0)T, vôùi soá 1 ôû vò trí  Coù nhieàu caùch ñeå xaùc ñònh caùc phaàn töû coøn laïi cuûa doøng As (môùi). baûng môùi, moãi taùc giaû ñöa ra moät caùch laøm rieâng.  Toâi ñöa ra 1 caùch laøm döïa vaøo caùc pheùp bieán ñoåi sô caáp Gauss trong Ñaïi soá tuyeán tính, taïm goïi laø  Sau khi coù ñöôïc baûng môùi, ta quay laïi böôùc Gauss Lovely. 2. 51 52 13
  14. ThS. Phạm Trí Cao * Chương 1 03/01/2014 6 2 1 3 1 -7 Cô sôû Heä soá PA A1 A2 A3 A4 A5 A6 A2 2 15 -1 1 0 2 0 1 Keát luaän? A5 1 2 4 0021-3 A3 1 9 2 0 1 1 0 (2) B1 (doøng f) 41 -2 0 0 4 0 (8) 6 2 1 3 1 -7 Cô sôû Heä soá PA A1 A2 A3 A4 A5 A6 A2 2 21/2 -2 1 -1/23/2 0 0 A5 1 31/2 7 0 3/2 7/2 1 0 A6 -7 9/2 1 0 ½ ½ 0 1 53 B2 (doøng f) 5 -10 0 -4 0 0 0 54 Löu yù: 62131-7 Ta phaûi canh theo doøng chuû yeáu ñeå bieán ñoåi. Cô sôû Heä soá PA A1 A2 A3 A4 A5 A6 ÔÛ baûng 1 khoâng ñöôïc laáy doøng A5 +3 A2 221/2-21-1/23/200 laàn doøng A2 roài keát quaû caát vaøo doøng A5 ôû baûng 2. Bôûi vì neáu laøm nhö vaäy thì coät A5 1 47 1 30 8 10 T A2 ôû baûng môùi khoâng coù daïng (1, 0, 0) . A6 -7 9/2 1 0½ ½01 B2 (doøng f) 5 -10 0-4000 55 56 14
  15. ThS. Phạm Trí Cao * Chương 1 03/01/2014 Ví duï 1.12: 1-22 -11-2 f(x) = x - 2x + 2x - x + x - 2x min 1 2 3 4 5 6 Cô sôû Heä soá PA A A A A A A 2x1 - x2 - 5x3 + x4 = 5 1 2 3 4 5 6 x1 - 2x2 + 2x3 + x5 = 4 A4 -1 5 (2)-1 -5 1 0 0 -4x1 + x2 + x3 + x6 = 2 A5 141-22010 xj >=0 , j= 1,6 A6 -2 2 -41 1 0 0 1 1 -2 2 -1 1 -2 B1 -5 (6)-1 3 0 0 0 Cô sôû Heä soá PA A1 A2 A3 A4 A5 A6 A1 15/21-1/2 -5/2 1/2 0 0 A4 -1 5 (2) -1 -5 1 0 0 A5 1 3/2 0 -3/2 9/2 -1/2 1 0 A5 1 4 1 -22010 A -2 12 0 -1 -9 2 0 1 A6 -2 2 -4 11001 6 B1 -5 (6) -1 3 0 0 0 B2 -20 0 2 18 -3 0 0 57 58 Keát luaän? Löu yù: Neáu coù nhieàu coät coù cuøng döông lôùn nhaát thì ta laøm theá naøo? VD1.13: Xem chi tieát trong saùch. Neáu coù nhieàu doøng ñeå choïn thì ta laøm Caùch 2: Tìm löôïng giaûm lôùn nhaát cuûa theá naøo? haøm muïc tieâu Qua moãi böôùc laëp, giaù trò haøm muïc tieâu Xem chi tieát ôû trong saùch. giaûm 1 löôïng laø . s , f(x’) = f(x)–. s . Vaäy ta coù theå ñöa ra caùch 2: tìm löôïng giaûm lôùn nhaát cuûa f(x) qua moãi böôùc laëp. 59 60 15
  16. ThS. Phạm Trí Cao * Chương 1 03/01/2014  VII) BAØI TOAÙN (M) – VAÁN ÑEÀ TÌM PA CÖÏC  - Neáu baøi toaùn daïng chính taéc (caùc heä soá veá phaûi BIEÂN BAN ÑAÀU raøng buoäc chung bi >= 0) chöa coù ñuû caùc bieán cô sôû töông öùng ôû moãi raøng buoäc chung thì ta theâm  Thuaät toaùn ñôn hình chæ aùp duïng cho baøi toaùn daïng bieán gia chuaån. Baøi toaùn daïng chuaån taéc cho ta pacb ban moät soá û vaøo ñeå ñoùng vai troø laø bieán cô sôû. ñaàu, coù pacb naøy ta môùi laäp ñöôïc baûng ñôn hình Baøi toaùn coù bieán giaû goïi laø bt (M). xuaát phaùt.  Neáu baøi toaùn daïng chính taéc, chöa chuaån thì ta  Ñeå bieát theâm bao nhieâu bieán giaû vaøo vaø theâm vaøo phaûi bieán ñoåi ñeå ñöa veà daïng chuaån. raøng buoäc chung naøo ta laøm nhö sau: Xeùt caùc raøng buoäc chung töø treân xuoáng döôùi, neáu raøng buoäc  - Neáu baøi toaùn daïng chính taéc, coù heä soá töï do b i chung naøo coù bieán cô sôû roài thì thoâi, coøn chöa coù beân veá phaûi raøng buoäc chung =0. 61 62  Ví duï 1.19:  Ñònh lyù:  Baøi toaùn (P):  1) Neáu baøi toaùn (M) khoâng coù patö thì baøi  f(x) = x1 -2x2 +3x3 +x4 min toaùn (P) khoâng coù patö.  4x1 +2x3 +2x4 =1  2)Neáubaøitoaùn(M)coùpatöthìcoù2tröôøng  x1 + x2 +5x3 -4x4 =6 hôïp:  xj >=0 , j= 1,4  * Neáu taát caû caùc bieán giaû trong patö cuûa  (M) ñeàu baèng 0 thì (P) coù patö, chính laø patö  Haõy vieát baøi toaùn (M) töông öùng? cuûa (M) maø loaïi ra caùc bieán giaû.  Baøi giaûi chi tieát xem trong saùch.  * Neáu trong patö cuûa (M) coù bieán giaû khaùc 0 thì (P) khoâng coù patö (vì ta khoâng 63 64 theå boû bieán giaû naøy ñöôïc). 16
  17. ThS. Phạm Trí Cao * Chương 1 03/01/2014 VD 1.19 Cô sôû Heä soá PA 1 -2 3 1 M Baøi toaùn (M) laø: A1 A2 A3 A4 A5 f(x) = x1 - 2x2 + 3x3 + x4 + Mx5 min A5 M 1 (4) 0 2 2 1 4x1 + 2x3 + 2x4 + x5 = 1 A2 -2 6 1 1 5 -4 0 x1 + x2 + 5x3 - 4x4 = 6 B1 (doøng f) M-12 (4M-3) 0 2M-13 2M+7 0 xj >=0 , j= 1,5 A1 1 1/4 1 0 1/2 (½) ¼ Cô sôû Heä soá PA 1 -2 3 1 M A2 -2 23/4 0 1 9/2 -9/2 - ¼ A1 A2 A3 A4 A5 B2 (doøng f) -45/4 0 0 -23/2 (17/2) -M+3/4 A5 M 1 (4) 0 2 2 1 A4 11/22011½ A2 -2 6 1 1 5 -4 0 A2 -2 8 9 1 9 0 2 B1 (doøng f) M-12 (4M-3) 0 2M-13 2M+7 0 B3 (doøng f) -31/2 -17 0 -20 0 -M-7/2 65 66  Keát luaän?  Ví duï 1.20:  Baøi toaùn (P)  f= x1 +x2 –x3 +2x4 +3x5 min  x1 –x3 +2x4 +x5 =1  x2 –x4 +x5 =3  x3 –2x5 =2  xj >=0, j= 1,5 67 68 17
  18. ThS. Phạm Trí Cao * Chương 1 03/01/2014 Baøi toaùn (M) Cô sôû Heä soá PA 1 1 –123 f= x1 + x2 – x3 + 2x4 + 3x5 + Mx6 min A1 A2 A3 A4 A5 x1 – x3 + 2x4 + x5 = 1 x2 – x4 + x5 = 3 A1 1 1 1 0 –1 2 1 x3 – 2x5 + x6 = 2 A2 1 3 0 1 0 –1 1 xj >=0, j= 1,6 A M 2 0 0 (1) 0 –2 Trong ñoù: x laø bieán giaû vaø M>0 (raát lôùn) 6 6 B1 2M+4 0 0 (M) –1 –2M–1 Cô sôû Heä soá PA 1 1 –123 A1 A2 A3 A4 A5 A1 1 3 1 0 0 2 –1 A1 1 1 1 0 –1 2 1 A2 1 3 0 1 0 –1 1 A2 1 3 0 1 0 –1 1 A3 –1 2 0 0 1 0 –2 A6 M 2 0 0 (1) 0 –2 B1 2M+4 0 0 (M) –1 –2M–1 B2 4 0 0 0 –1 –1 69 70  Keát luaän?  Ví duï 1.21:  Xem chi tieát trong saùch.  Baøi toaùn (P)  f= x1 -2x2 +3x3 +x4 min  4x1 +x2 +2x3 +2x4 =2  x1 +5x3 -4x4 =12  xj >=0 , j= 1,4  Vieát vaø giaûi baøi toaùn (M) töông öùng?  Baøi giaûi chi tieát xem trong saùch. 71 72 18
  19. ThS. Phạm Trí Cao * Chương 1 03/01/2014  VIII) BAØI TOAÙN QHTT DAÏNG CHUAÅN, Ví duï 1.21: f max Cô Heä PA 1 -2 3 1 sôû soá A1 A2 A3 A4  Caùch 1 (giaùn tieáp): A3 31 2 ½ 11  f max g=–f min  x Dx D A5 M 7 -9 -5/2 0 -9 B2 7M+3 -9M (-5/2)M 0-9M  Ta ñaõ bieát: +5 +(7/2) +2  x* laø patö cuûa maxf x* laø patö cuûa ming Keát luaän?  73 74 fmax = f(x*) = – gmin = – g(x*)  Caùch 2 (tröïc tieáp):  Caùch 2 (tröïc tieáp):  Thuaät toaùn gioáng thuaät toaùn daïng chuaån,  B4) Choïn coät chuû yeáu: s =min{ k / k f min. Chæ thay ñoåi: =0, k : pa ñang xeùt laø patö.  Thuaät toaùn keát thuùc.  Caùc phaàn giöõ nguyeân nhö cuõ: gioáng min.  B3) Tieâu chuaån khoâng toái öu:  B1) Baûng ñôn hình xuaát phaùt.  NeáucoùcoätAk coù k <0 vaø moïi phaàn töû thuoäc coät naøy ñeàu <=0 thì baøi toaùn khoâng coù patö (do f  B4) Doøng chuû yeáu, phaàn töû chuû yeáu. khoâng bò chaän treân).  Quaù trình chuyeån töø baûng cuõ sang baûng  Thuaät toaùn keát thuùc. môùi. 75 76 19
  20. ThS. Phạm Trí Cao * Chương 1 03/01/2014  Ví duï 1.22: Caùch 2 (giaûi tröïc tieáp): f(x)= -6x1 -2x2 -x3 -3x4 -x5 +7x6 max  f(x)= -6x1 -2x2 -x3 -3x4 -x5 + 7x6 max - x1 + x2 + 2x4 + x6 = 15 4x1 + 2x4 + x5 -3x6 = 2  -x1 + x2 + 2x4 + x6 = 15 2x1 + x3 + x4 + 2x6 = 9  4x1 + 2x4 + x5 -3x6 = 2 xj >=0, j= 1,6 -6 -2 -1 -3 -1 7  2x1 + x3 + x4 + 2x6 = 9 Cô sôû Heä soá PA A1 A2 A3 A4 A5 A6  xj >=0, j= 1,6 A2 -2 15-110201 A5 -1 2 40021-3  Caùch 1: xem chi tieát trong saùch. A3 -1 9 20110(2) B1 (doøng f) -41 2 0 0 -4 0 (-8) 77 78 -6 -2 -1 -3 -1 7  Keát luaän? Cô sôû Heä soá PA A1 A2 A3 A4 A5 A6 A2 -2 15 -1 1 0 2 0 1 A5 -1 2 4 0 0 2 1 -3 A3 -1 9 2 0 1 1 0 (2) B1 (doøng f) -41 2 0 0 -4 0 (-8) A2 -2 21/2 -2 1 -1/2 3/2 0 0 A5 -1 31/2 7 0 3/2 7/2 1 0 A6 7 9/2 1 0 ½ ½ 0 1 B2 (doøng f) -5 10 0 4 0 0 0 79 80 20
  21. ThS. Phạm Trí Cao * Chương 1 03/01/2014  Ví duï 1.23: Cô sôû Heä soá PA –111020  Baøi toaùn (P):  f(x)= –x1 +x2 +x3 +2x5 max A1 A2 A3 A4 A5 A6  2x1 –x2 –x4 =6 A1 –1 4 1 1 0 0 1 1  3x1 –x4 +x5 +x6 =10  x –2x +2x =4 3 4 5 A4 0 2 0 3 0 1 2 2  xj >=0, j= 1,6 A3 1 8 0 6 1 0 6 4  Baøi giaûi chi tieát xem trong saùch. B3 4 040033  Heä soá cuûa bieán giaû trong haøm muïc tieâu laø –M. 81 82Keát luaän?  IX) GIAÛI BAØI TOAÙN QHTT TOÅNG QUAÙT  Quaù trình giaûi baøi toaùn toång quaùt laø quaù trình keát hôïp caùc böôùc phaân tích ta ñaõ laøm töø ñaàu chöông cho ñeán ñaây.  Phöông phaùp giaûi:  * Ñöa baøi toaùn toång quaùt veà daïng chính taéc.  * Neáu caùc heä soá töï do bi ôû veá phaûi cuûa caùc raøng buoäc chung =0.  * Neáu baøi toaùn chöa laø daïng chuaån (vì thieáu bieán cô sôû) thì theâm bieán giaû vaøo, ta ñöôïc baøi 83 toaùn (M). 84 21
  22. ThS. Phạm Trí Cao * Chương 1 03/01/2014  Ví duï 1.25:  Baøi toaùn (P*)  Baøi toaùn (P)  f= x1 +3x2 +x3 min  f= x1 +3x2 +x3 min  x1 +x2 +x3 -x4 =5  x1 +x2 +x3 >= 5  x2 +2x3 = 8  -x2 -2x3 = -8  x1 +2x2 +x3 + x5 =10  x1 +2x2 +x3 =0, j= 1,5 (x4 ,x5 laø bieán phuï)  xj >=0, j= 1,3 85 86  Baøi toaùn (M)  Ví duï 1.26: f(x)= x1 +x2 +3x3 +2x4 max  x1 +2x2 +x3 +2x4 = 8  x2 +2x3 +x7 =8  xj >=0, j= 1,4  x1 +2x2 +x3 + x5 =10  Giaûi:  x >=0, j= 1,7 (x ,x laø bieán giaû) j 6 7  f(x)= x1 +x2 +3x3 +2x4 –M.x7 –M.x8 max   x1 +2x2 +x3 +2x4 + x5 =10  vôùi M>0 (raát lôùn)  2x1 +x2 +3x3 +4x4 + x7 =9  x1 +2x2 +2x3 +x4 –x6 + x8 =8  x*(M)= (1, 0, 4, 0, 5, 0, 0)  xj >=0, j= 1,8  x*(M)= (0, 3/2, 5/2, 0, 9/2, 0, 0, 0) . Keát luaän? 87 Keát luaän? 88 22
  23. ThS. Phạm Trí Cao * Chương 1 03/01/2014  X) VAÁN ÑEÀ VEÀ PATÖ DUY NHAÁT CUÛA BAØI TOAÙN QHTT Cô sôûHeä soá PA1034-22  1) Caùc khaùi nieäm A1 A2 A3 A4 A5 A6  * Veùc tô chæ phöông cuûa caïnh voâ haïn toái öu (vtcp): A3 3 5 0 -11 -2 0 1  Ví duï 1.27: A1 1 1 1 1 0 -4 0 2  f(x)= x1 +3x3 +4x4 -2x5 +2x6 min A5 -2 4 0 3 0 -7 1 4  -x2 + x3 -2x4 +x6 =5 80-800 0-5  x1 +x2 -4x4 +2x6 =1 t= (4, 0, 2, 1, 7, 0)  3x2 -7x4 + x5 +4x6 =4  xj >=0, j= 1, 6 89 90 t1 t3 t4 t5 2) Ñònh lyù (patö toång quaùt)  2) Ñònh lyù (patö toång quaùt) Baøi toaùn coù caùc pacbtö x1, x2 , , xk vaø caùc vtcp laø t1 ,  VD3: Baøi toaùn coù 1 pacbtö laø x* vaø 1 vtcp laø t2 , tm thì patö toång quaùt cuûa baøi toaùn laø: t thì patö toång quaùt laø: x= x*+.t vôùi  >=0 k i m j k  VD4: Baøi toaùn coù 1 pacbtö laø x* vaø 2 vtcp laø x =  x   t ;  i >= 0,  1;  j >=0 1 2 i 1 i j 1 j i 1 i t vaø t thì patö toång quaùt laø: 1 2 1 2 x= x* +  t +  t vôùi  ,  >=0 VD1: Baøi toaùn coù 2 pacbtö laø x , x thì patö toång quaùt laø: 1 2 1 2 1 2 1 2  VD5: Baøi toaùn coù 2 pacbtö laø x ,x vaø 2 vtcp x= x + x vôùi + =1 , 0 =0 x=91 1x + 2x + 3x vôùi 1+ 2+ 3 = 1 , 0<= i <=1 92 23
  24. ThS. Phạm Trí Cao * Chương 1 03/01/2014  3) Caùch xaùc ñònh baøi toaùn coù patö duy nhaát khoâng  Tìm tyû soá ñôn hình  :  Ñeå xaùc ñònh baøi toaùn coù patö duy nhaát hay khoâng, ta   =xr /zrs = min{(coät pa / coät chuû yeáu) / caùc laøm nhö sau: phaàn töû thuoäc coät chuû yeáu döông}  Xeùt baûng ñôn hình toái öu (laø baûng maø töø ñoù ta laáy  B21) Neáu  >0:baøi toaùn coù patö khoâng duy nhaát. ra patö) cuûa baøi toaùn QHTT.  Laáy doøng Ar laøm doøng chuû yeáu, tieáp tuïc bieán  B1) Neáu k ≠ 0 vôùi moïi bieán töï do xk : baøi toaùn coù ñoåi ta seõ coù pacbtö khaùc. patö duy nhaát.  B22) Neáu  =0:baøi toaùn coù patö duy nhaát.  B2) Neáu coù j = 0 vôùi xj laø bieán töï do: baøi toaùn coù  (patö khoâng thay ñoåi nhöng cô sôû coù theå thay theå coù patö duy nhaát hoaëc khoâng. ñoåi)  Ta xeùt tieáp nhö sau:  B23) Neáu khoâng toàn taïi  (do taát caû caùc phaàn töû  Laáy coät coù heä soá öôùc löôïng baèng 0 (öùng vôùi bieán töï treân coät As ñeàu = 2 1 2 3 A6 08212001  2x1 +x2 +2x3 =0, j= 1,3 A4 0 1 0 -1/2 -3/2 1 ½ 0  Giaûi: A1 2 1 1 -1/2 (1/2) 0 -1/2 0 A 06021011  f= 2x +x +x + Mx min 6 1 2 3 7 B2 2 0 -2 (0) 0 -1 0  x1 -x2 -x3 + x4 =2 A4 0 4 3 -2 0 1 -1 0  x 2x1 -x2 +x3 –x5 + 7 =2 A3 12(2)-110-10  2x1 +x2 +2x3 + x6 =8 A6 04-230021 B3 2 (0) -2 0 0 -1 0 95 xj >=0, j= 1,7 96 24
  25. ThS. Phạm Trí Cao * Chương 1 03/01/2014 1 Ví duï 1.34:  Pacbtö: x = (1, 0 , 0) , fmin =2 f(x) = x1 + 3x3 - 3x4 - 2x5 + 2x6 min  Ta coù pacbtö môùi: x2 = (0, 0, 2). - x2 + x3 + 2x4 + x6 = 0 1 2  Vaäy baøi toaùn chæ coù 2 pacbtö laø x vaø x . x1 + x2 + x4 + 2x6 = 1  Patö toång quaùt: 3x2 + 5x4 + x5 + 4x6 = 4 x= .x1 +(1- ).x2 vôùi [0,1] xj >=0, j= 1,6 Giaûi: Cô sôû Heä soá PA 1 0 3 -3 -2 2  Trong tröôøng hôïp naøy: pacbtö khoâng duy A1 A2 A3 A4 A5 A6 nhaát, patö khoâng duy nhaát. A3 300-112 01 A1 1 1 1 1 0 1 0 2 A5 -2 4 0 3 0 5 14 -7 0 -8 0 0 0-5 97 98  VD1.34 Môøi gheù thaêm trang web:  Baøi toaùn coù patö duy nhaát khoâng? 100   Ví duï 1.29:   Xem laïi VD 1.11, 1.13, 1.19, 1.20, 1.25 ta coù k 0 vôùi moïi bieán töï do xk : baøi toaùn coù patö duy nhaát.  Trong tröôøng hôïp naøy: pacbtö duy nhaát, patö duy nhaát. 99 25