intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Tối ưu hóa: Chương 1 - ThS. Phạm Trí Cao

Chia sẻ: Thôi Kệ | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST
Báo xấu
133
lượt xem 15
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Tối ưu hóa chương 1 trình bày đến người học các nội dung liên quan đến bài toán quy hoạch tuyến tính. Trong bài này đưa ra các bài toán ví dụ thực tế, các khái niệm và định nghĩa về quy hoạch tuyến tính,... Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Tối ưu hóa: Chương 1 - ThS. Phạm Trí Cao

  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  Tyû leä pha cheá caùc loaïi nguyeân lieäu vôùi nhau ñeå Loaïi Tyû leä pha cheá Döï saûn xuaát ra caùc loaïi saûn phaåm cho trong baûng nguyeân K1 K2 K3 K4 sau: tröõ 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 nhaát? C (taán) 13 2 4 1 1 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  x1 + 2x2 + 3x3 + 4x4
  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) 9 vaø fmin= 14 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*.  Nghóa laø: xD: f(x) >= f(x*)  Soá (3) goïi laø raøng buoäc bieán.  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ùc bi goïi laø caùc heä soá töï do.  Nghóa laø: xD: f(x)
  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.  Moät raøng buoäc goïi laø chaët ñoái vôùi pa x neáu khi ta thay xD xD 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  aij x j  bi j1  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
  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  x  b    n  11 12 1 n  1   f(x)=  c x  min (max) (1)  a  a ... a    1   j1 j j  21 22 2 n b  x     2 A  , b  , x   2 n  ... ... ... ...   ...  ...   aijxj bi , i= 1,m (2)   a a ... a     b      x    j1   m1  m2 mn     m    n xj >=0 , j= 1,n (3) cc c ... cn 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:  x= (x1, x2, ..., xn) >= 0  xj >= 0, j= 1,n  Neáu xj =0  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ï yi >=0:  x1 + 3x2 - 2x3 = 3  aijx j  yi b  xj >=0, j= 1,3 i j1  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  Neáu (P*) khoâng coù patö thì (P) cuõng n khoâng coù patö.  aijx j yi bi 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
  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).  x laø pa cöïc bieân  heä veùc tô coät töông öùng vôùi  A.x = b (2) 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  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  -x1 + 2x2 +x3 = 14 thì goïi laø baøi toaùn suy bieán.  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ät pa 29 30 goïi laø pacbtö neáu noù vöøa laø pacb vaø vöøa laø patö.  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 daïng chính taéc thoûa theâm caùc ñieàu kieän sau:  baøi toaùn coù voâ soá patö.  - 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.  - Caùc bieán khoâng phaûi laø bieán cô sôû (bieán cô baûn) thì 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= x1 + 2x2 + x3 - x4  min  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ì ta coù: x1 = 7,  x4 = 5 (bieán cô sôû).  Baøi giaûi chi tieát xem trong saùch. 33 Vaäy ta coù pa x= (7, 0, 0, 5) laø pacb khoâng suy bieán. 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  x1 + x3 + x4 =4 hoïc ñeå giaûi.  x2 + 2x3 + x5 =7 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+byc 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 35 thì mieàn chöùa ñieåm (0,0) thoûa ax+by>c. 36 9
  10. ThS. Phạm Trí Cao * Chương 1 03/01/2014 Ñöôøng thaúng (D): ax+by=c goïi laø ñöôøng ñaúng möùc,  Ví duï 1:  f(x)= 7x - 2y  coù phaùp veùc tô laø n =(a,b).  5x - 4y >= -3 (qua A, C)   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: 37 möùc c giaûm xuoáng.  1) Taäp pa laø 1 tam giaùc coù caùc ñænh laø A(1,2), 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).  Ta coù: 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: c1 c2 ..... cn  f(x)= 6x1 + 2x2 + x3 + 3x4 + x5 - 7x6  min Cô sôû Heä soá PA A1 A2 ..... An  - x1 + x2 + 2x4 + x6 = 15  4x1 + 2x4 + x5 -3x6 = 2 JJ(x) Aj cj xj zj1 zj2 …… zjn  2x1 + x3 + x4 + 2x6 = 9 f 1 2 …… n  xj >=0 , j= 1,6 f= f(x)= coät Heä soá * coät PA =  Ta coù caùc bieán cô sôû laø x2, x3, x5 vaø veùc tô cô sôû laø  c x : j J ( x ) j j 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
  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 . s  f(x’) = f(x) – .s 50  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ôû: Thay Ar 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á: Thay cr 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 A5 1 2 4 0 0 2 1 -3  Keát luaän? 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/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 53 B2 (doøng f) 5 -10 0 -4 0 0 0 54  Löu yù: 6 2 1 3 1 -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 2 21/2 -2 1 -1/2 3/2 0 0 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 3 0 8 1 0 A2 ôû baûng môùi khoâng coù daïng (1, 0, 0)T. A6 -7 9/2 1 0 ½ ½ 0 1 B2 (doøng f) 5 -10 0 -4 0 0 0 55 56 14
  15. ThS. Phạm Trí Cao * Chương 1 03/01/2014 Ví duï 1.12: 1 -2 2 -1 1 -2 f(x) = x1 - 2x2 + 2x3 - x4 + x5 - 2x6  min Cô sôû Heä soá PA A1 A2 A3 A4 A5 A6 2x1 - x2 - 5x3 + x4 =5 x1 - 2x2 + 2x3 + x5 =4 A4 -1 5 (2) -1 -5 1 0 0 -4x1 + x2 + x3 + x6 = 2 A5 1 4 1 -2 2 0 1 0 xj >=0 , j= 1,6 A6 -2 2 -4 1 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 1 5/2 1 -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 -2 2 0 1 0 A6 -2 2 -4 1 1 0 0 1 A6 -2 12 0 -1 -9 2 0 1 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 moät soá bieán giaû vaøo ñeå ñoùng vai troø laø bieán cô sôû. chuaån. Baøi toaùn daïng chuaån taéc cho ta pacb ban Baøi toaùn coù bieán giaû goïi laø bt (M). ñaàu, coù pacb naøy ta môùi laäp ñöôïc baûng ñôn hình 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 bi 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áu baøi toaùn (M) coù patö thì coù 2 tröôø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 1 1/2 2 0 1 1 ½ 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 –1 2 3 f= x1 + x2 – x3 + 2x4 + 3x5 + Mx6  min A1 A2 A3 A4 A5 x1 – x3 + 2x4 + x5 =1 x2 – x 4 + 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 A6 M 2 0 0 (1) 0 –2 Trong ñoù: x6 laø bieán giaû vaø M>0 (raát lôùn) Cô sôû Heä soá PA 1 1 –1 2 3 B1 2M+4 0 0 (M) –1 –2M–1 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 Ví duï 1.21:  VIII) BAØI TOAÙN QHTT DAÏNG CHUAÅN, f  max Cô Heä PA 1 -2 3 1 sôû soá A1 A2 A3 A4  Caùch 1 (giaùn tieáp): A3 3 1 2 ½ 1 1  f  max  g = – f  min A5 M 7 -9 -5/2 0 -9  xD xD 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?  fmax = f(x*) = – gmin = – g(x*) 73 74  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áu coù coät Ak coù k
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
25=>1