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

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 - ThS. Nguyễn Công Trí

1. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAØI TOAÙN CHÖÔNG 1 MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT QUY HOAÏCH TUYEÁN TÍNH Ví duï 1.1. BAØI TOAÙN LAÄP KEÁ HOAÏCH SAÛN XUAÁT Moät xí nghieäp duøng 3 loaïi nguyeân lieäu: N ; N ; N 1. THIEÁT LAÄP MOÂ HÌNH BAØI TOAÙN (Xem) 1 2 3 ñeå saûn xuaát ra moät loaïi saûn phaåm theo 3 phöông 2. CAÙC DAÏNG CUÛA BAØI TOAÙN QUY phaùp khaùc nhau: PP1; PP2; PP3. Ñònh möùc nguyeân lieäu vaø soá löôïng saûn phaåm saûn xuaát ra trong 1 Ths.HOAÏCH Nguyeãn TUYEÁN TÍNH Coâng (Xem)Trí giôø ñöôïc cho ôû baûng sau: Nguyeân Soá löôïng Ñònh möùc nguyeân lieäu 3. CAÙC KHAÙI NIEÄM CÔ BAÛN VEÀ BAØI TOAÙN Lieäu hieän coù (ñv) PP1 PP2 PP3 QUY HOAÏCH TUYEÁN TÍNH (Xem) Copyright 2001 N1 250 4 5 3 N 350 2 4 1 4. CAÙC PHÖÔNG PHAÙP GIAÛI BAØI TOAÙN 2 N3 450 3 6 4 QUY HOAÏCH TUYEÁN TÍNH (Xem) Soá saûn phaåm (sp/giôø) 10 12 9 Ths. Nguyeãn Coâng Trí Haõy laäp moâ hình baøi toaùn sao cho xí nghieäp saûn 5. BAØI TAÄP Copyright 2001(Xem) xuaát ra nhieàu saûn phaåm nhaát? MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT Goïi x , x , x laàn löôït laø thôøi gian saûn xuaát ra saûn 1 2 3 Ví duï 1.2. BAØI TOAÙN PHA CAÉT VAÄT LIEÄU phaåm theo 3 phöông phaùp PP1, PP2, PP3. Toång saûn phaåm saûn xuaát (caàn laøm cöïc ñaïi) Moät xí nghieäp may maëc caàn saûn xuaát ñuùng 2.000 quaàn vaø ít nhaát 1.000 aùo. Moãi taám vaûi coù 6 caùch f(x) = 10x1 + 12x2 + 9x3 max caét nhö sau: Do xí nghieäp chæ coù 250 nguyeân lieäu N1 neân x1, x2, Caùch caét Quaàn AÙo x phaûi thoûa maõn 4x + 5x + 3x ≤ 250 3 1 2 3 1 90 35 Töông töï cho caùc nguyeân lieäu N2, N3 ta coù 2x1 + 4x2 + x3 ≤ 350 vaø 3x1 + 6x2 + 4x3 ≤ 450 2 80 55 Dó nhieân ta phaûi coù x1, x2, x3 khoâng aâm 3 70 70 Vaäy moâ hình baøi toaùn ñöôïc phaùt bieåu nhö sau: 4 60 90 Tìm caùc bieán x1, x2, x3 sao cho f(x)= 10x1 + 12x2 + 9x3 max, thoûa caùc ñieàu kieän 5 120 0 4x + 5x + 3x ≤ 250 1 2 3 6 0 100 2x1 + 4x2 + x3 ≤ 350 3x1 + 6x2 + 4x3 ≤ 450 Haõy tìm phöông aùn caét quaàn aùo sao cho toång soá x1 0 x2 0 x3 0 taám vaûi laø ít nhaát? 1
2. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT Goïi xj (j = 1, 2, , 6) laø soá taám vaûi ñöôïc caét theo Ví duï 1.3. BAØI TOAÙN XAÙC ÑÒNH KHAÅU PHAÀN caùch thöù j. Ñeå nuoâi moät loaïi gia suùc coù hieäu quaû, moãi ngaøy Toång soá taám vaûi duøng ñeå saûn xuaát (caàn laøm cöïc caàn phaûi coù khoái löôïng toái thieåu caùc chaát protit, tieåu) laø f(x) = x1 + x2 + x3 + x4 + x5 + x6 min glucit, khoaùng töông öùng laø 90 gram, 130 gram, Do xí nghieäp caàn saûn xuaát ñuùng 2.000 quaàn neân 10 gram. Tyû leä (%) theo khoái löôïng caùc chaát treân caùc xj phaûi thoûa maõn coù trong caùc loaïi thöùc aên A, B, C nhö sau: 90x + 80x + 70x + 60x + 120x = 2000 1 2 3 4 5 Thöùc aên Chaát dinh döôõng (%) Töông töï cho ñieàu kieän veà saûn xuaát aùo, ta coù 35x + 55x + 70x + 90x + 100x 1000 Protit Glucit Khoaùng 1 2 3 4 6 A 10 30 2 Dó nhieân ta phaûi coù xj (j = 1, 2, , 6) khoâng aâm Vaäy moâ hình baøi toaùn ñöôïc phaùt bieåu nhö sau: B 20 40 1 C 30 20 3 Tìm caùc bieán xj (j = 1, 2, , 6) sao cho f(x)= xj min, thoûa caùc ñieàu kieän Giaù 1 kg thöùc aên A, B, C töông öùng laø 3.000 90x1 + 80x2 + 70x3 + 60x4 + 120x5 = 2000 ñoàng, 4.000 ñoàng, 5.000 ñoàng. Haõy laäp moâ hình 35x1 + 55x2 + 70x3 + 90x4 + 100x6 1000 baøi toaùn xaùc ñònh khoái löôïng thöùc aên caàn thieát xj 0, (j = 1, 2, , 6). sao cho chi phí nuoâi gia suùc laø thaáp nhaát? MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT Goïi x (j = 1, 2, 3) laø soá gram thöùc aên A, B, C caàn j Ví duï 1.4. BAØI TOAÙN VAÄN TAÛI mua moãi ngaøy. Toång chi phí duøng ñeå mua thöùc aên (caàn laøm cöïc Caàn vaän chuyeån xi maêng töø 3 kho K1, K2, K3 ñeán 4 coâng tröôøng xaây döïng T1, T2, T3, T4. Cho bieát löôïng tieåu) laø f(x) = 3x1 + 4x2 + 5x3 min (ñoàng) Do caùc tyû leä caùc chaát protit, glucit vaø khoaùng coù xi maêng coù ôû moãi kho, löôïng xi maêng caàn ôû moãi coâng tröôøng vaø cöôùc phí vaän chuyeån (ngaøn trong thöùc aên A neân caùc xj phaûi thoûa maõn ñoàng/ taán) töø moãi kho ñeán coâng tröôøng nhö sau: 0,1x1 + 0,2x2 + 0,3x3 90 Töông töï cho ñieàu kieän cuûa thöùc aên B vaø C, ta coù Coâng tröôøng T1: 130 t T2: 160 t T3: 120 t T4: 140 t 0,3x1+0,4x2+0,2x3 130 vaø 0,02x1+0,01x2+0,03x3 10 Kho Vaäy moâ hình baøi toaùn ñöôïc phaùt bieåu nhö sau: K1: 170 taán 20 18 22 25 Tìm caùc bieán xj (j = 1, 2, 3) sao cho K2: 200 taán 15 25 30 15 f(x) = 3x1 + 4x2 + 5x3 min, thoûa caùc ñieàu kieän K3: 180 taán 45 30 40 35 0,1x + 0,2x + 0,3x 90 1 2 3 Laäp moâ hình baøi toaùn vaän chuyeån sao cho caùc 0,3x1 + 0,4x2 + 0,2x3 130 0,02x + 0,01x + 0,03x 10 kho phaùt heát xi maêng coù, coâng tröôøng nhaän ñuû xi 1 2 3 maêng caàn vaø chi phí vaän chuyeån thaáp nhaát? xj 0, (j = 1, 2, 3). 2
3. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 MOÄT VAØI VÍ DUÏ VEÀ BAØI TOAÙN QHTT CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT Goïi x (i = 1, 2, 3, j = 1, 2, 3, 4) laø löôïng xi maêng ij 2.1. DAÏNG TOÅNG QUAÙT caàn vaän chuyeån töø kho Ki ñeán coâng tröôøng Tj. Toång chi phí vaän chuyeån (caàn laøm cöïc tieåu) laø Tìm x = (x1, x2, , xn) sao cho: n f(x) = 20x11 + 18x12 + 22x13 + 25x14 f( x ) c x min ( hay max) (2.1) 15x21 + 25x22 + 30x23 + 15x24  j j j 1 45x31 + 30x32 + 40x33 + 35x34 min Ñieàu kieän cuûa caùc kho n x + x + x + x = 170 a x b i 1, m 2.2 11 12 13 14  ij j i j 1 x21 + x22 + x23 + x24 = 200 x + x + x + x = 180 31 32 33 34 Ñieàu kieän cuûa caùc coâng tröôøng xj 0, x k 0, j k n 2.3 x11 + x21 + x31 = 130 (2.1) goïi laø haøm muïc tieâu. (2.2) goïi laø heä raøng x12 + x22 + x32 = 160 buoäc. (2.3) goïi laø raøng buoäc veà daáu cuûa aån soá. x + x + x = 120 13 23 33 Ví duï 1.1, Ví duï 1.2 vaø Ví duï 1.3 laø caùc baøi toaùn x14 + x24 + x34 = 140 QHTT coù daïng toång quaùt. xij 0, i = 1, 2, 3, j = 1, 2, 3, 4. CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT  Moät vectô x = (x1, x2, , xn) thoûa maõn ñieàu kieän 2.2. DAÏNG CHÍNH TAÉC (2) vaø (3) ñöôïc goïi laø moät phöông aùn (P.A) cuûa Tìm x = (x1, x2, , xn) sao cho: baøi toaùn quy hoaïch tuyeán tính (QHTT). n f( x )  cj x j min ( hay max)  Taäp caùc P.A cuûa baøi toaùn ñöôïc goïi laø mieàn j 1 raøng buoäc hay mieàn xaùc ñònh. Kyù hieäu laø D. n a x b i 1, m  Phöông aùn toái öu (P.A.T.Ö) hay nghieäm cuûa  ij j i j 1 baøi toaùn, kyù hieäu laø X (optimality), neáu vectô X opt x 0, j 1, n laø moät P.A vaø haøm muïc tieâu (2.1) bò chaën. j Nhaän xeùt: Heä raøng buoäc cuûa baøi toaùn daïng chính  Baøi toaùn ñöôïc goïi laø giaûi ñöôïc hay coù lôøi giaûi hay coù nghieäm neáu noù coù ít nhaát moät P.A.T.Ö. taéc ñeàu laø caùc ñaúng thöùc vaø moïi bieán cuûa baøi  Baøi toaùn khoâng giaûi ñöôïc hay voâ nghieäm neáu toaùn ñeàu khoâng aâm. Ví duï 1.4 BAØI TOAÙN VAÄN TAÛI D =  hay noù coù P.A nhöng khoâng coù PA.T.Ö. coù daïng chính taéc. 3
4. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT 2.3. DAÏNG CHUAÅN 2.4. CHUYEÅN ÑOÅI DAÏNG BAØI TOAÙN QHTT Tìm x = (x1, x2, , xn) sao cho: Khi xeùt baøi toaùn QHTT, ngöôøi ta thöôøng söû duïng n daïng chính taéc, coù theå ñöa baøi toaùn daïng toång f( x )  cj x j min ( hay max) j 1 quaùt veà daïng chính taéc baèng caùc bieán ñoåi sau: n m x a x b, i 1, m i i, m k m k i 1) Neáu raøng buoäc thöù i coù daïng aijxj ≤ bi thì theâm k 1  vaøo moät aån phuï xn+1 0, sao cho aijxj + xn+1 = bi. xj 0 j 1, n b i 0 Nhaän xeùt: Baøi toaùn daïng chuaån laø baøi toaùn ôû 2) Neáu raøng buoäc thöù i coù daïng aijxj bi thì theâm daïng chính taéc vôùi heä raøng buoäc chöùa ma traän vaøo moät aån phuï xn+1 0, sao cho aijxj – xn+1 = bi. 3) Neáu aån x ≤ 0 thì ñöôïc thay baèng x/ = – x 0. con Im laø ma traän ñôn vò caáp m. j j j 4) Neáu aån x khoâng raøng buoäc veà daáu thì thay x Trong ñoù caùc xi (i = 1, 2, , m) ñöôïc goïi laø aån cô j j baèng hai aån phuï x/ vaø x// sao cho x = x/ – x// , vôùi baûn (A.C.B), coøn caùc aån xi,m+k, (k = 0, 1, , n – m) j j j j j / // ñöôïc goïi laø aån khoâng cô baûn. x j 0, x j 0. CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT Ñeå baøi toaùn goïn hôn, chuùng ta duøng caùc kyù hieäu Ví duï 1.5. Ñöa baøi toaùn QHTT sau ñaây veà daïng chính taéc vaø vieát baøi toaùn chính taéc döôùi daïng a11 a 12 a 1n a1 j b1 c1 x1 0 a a a a b c x 0 ma traän 21 22 2n 2 j 2 2 2 A ,Aj ,b ,c ,x ,0 f( x ) x 3 x 2 x min          1 2 3 a 3x x 2 x 7 am1 a m 2  a mn mj bm cn xn 0 1 2 3 Trong ñoù A laø ma traän m n goàm caùc heä soá ôû veá 2x1 4 x 2 x 3 12 traùi cuûa heä raøng buoäc; Aj laø vectô coät thöù j cuûa 4x1 3 x 2 8 x 3 10 ma traän A; b laø vectô heä soá ôû veá phaûi cuûa heä raøng buoäc; c laø vectô heä soá ôû haøm muïc tieâu; x laø x1 0 x 3 0 vectô aån soá; 0 laø vectô khoâng. Theâm 2 aån phuï x4, x5 0 vaøo raøng buoäc thöù nhaát Khi ñoù baøi toaùn QHTT ôû daïng chính taéc coù daïng vaø raøng buoäc thöù ba. T / f(x) = c x min (hay max) Thay x 3 = –x3 0 Ax = b, x 0 / // / // Thay x2 = x 2 –x 2 0, vôùi x 2, x 2 0 4
5. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT CAÙC DAÏNG CUÛA BAØI TOAÙN QHTT Baøi toaùn QHTT coù daïng chính taéc nhö sau Ví duï 1.6. Cho baøi toaùn QHTT: f( x ) x1 3 x 2 3 x 2 2 x 3 min f( x ) x2 x 5 min 3x x x 2 x x 7 1 2 2 3 4 x x 2 x 1 1 2 5 2x1 4 x 2 4 x 2 x 3 12 3x2 x 3 x 5 3 4x 3 x 3 x 8 x x 10 1 2 2 3 5 2x x x 2 2 4 5 x1 0, x 2 0, x 2 0, x 3 0, x 4 0, x 5 0 Baøi toaùn QHTT döôùi daïng ma traän nhö sau xj 0 j 1,5 T / // / f(x) = (1, 3, – 2, 0, 0, 0) (x1, x 2, x 2, x 3, x4, x5) min Ta coù ma traän heä soá cuûa heä raøng buoäc: x 1 1 1 0 0 2 x 3 1 1 2 1 0 2 7 A 0 3 1 0 1 x 2 4 4 1 0 0 2 12 x 0 2 0 1 1 3 4 3 3 8 0 1 10 x4 chöùa I neân baøi toaùn quy hoaïch tuyeán tính treân coù x 3 / // / 5 (x1, x 2, x 2, x 3, x4, x5) (0, 0, 0, 0, 0, 0) daïng chuaån. ÑÒNH NGHÓA PHÖÔNG AÙN CÖÏC BIEÂN ÑÒNH NGHÓA PHÖÔNG AÙN CÖÏC BIEÂN Moät phöông aùn x* = (x1*, x2*, , xn*) cuûa baøi toaùn Ví duï 1.7. Cho baøi toaùn QHTT QHTT daïng toång quaùt laø phöông aùn cöïc bieân f( x ) 50 x1 16 x 2 23 x 3 min (P.A.C.B) neáu x* = (x1*, x2*, , xn*) thoûa maõn chaët 5x1 3 x 2 4 x 3 2 n raøng buoäc ñoäc laäp tuyeán tính. Töùc laø: n x1 2 * a x = b ,i=1,k,k m *  ijj i x x 3 x 1 X la P.A.C.B * j=1 k+l n,det A 0 1 2 3 x* =0, j=1,l,l n 6x 2 x x 4 j 1 2 3 Trong ñoù A laø ma traän con caáp n cuûa hpt (*). x2 0 x 3 0  Moät P.A.C.B khoâng suy bieán laø moät P.A.C.B Caùc vectô naøo sau ñaây thoûa maõn ñuùng n raøng buoäc chaët. 23 6  X 0, 1, 3 Y 3, 0, 0 Z 2, , Moät P.A.C.B suy bieán laø moät P.A.C.B thoûa maõn 5 5 hôn n raøng buoäc chaët. laø phöông aùn cöïc bieân? P.A.C.B coøn ñöôïc goïi laø phöông aùn cô baûn. 5
6. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 ÑÒNH NGHÓA PHÖÔNG AÙN CÖÏC BIEÂN CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT º Deã daøng kieåm tra X khoâng phaûi laø phöông aùn. ÑÒNH LYÙ 1. (TÍNH ÑAËC TRÖNG CUÛA P.A.C.B) * Y, Z laø phöông aùn cuûa baøi toaùn. Moät phöông aùn X = (x1*, x2*, , xn*) cuûa baøi toaùn QHTT daïng chính taéc laø phöông aùn cöïc º Y thoûa 2 raøng buoäc chaët (2 raøng buoäc veà daáu) bieân neáu vaø chæ neáu heä vectô coät Aj öùng vôùi neân Y chæ laø P.A. thaønh phaàn xj* > 0 laø ñoäc laäp tuyeán tính. º Z thoûa 3 raøng buoäc chaët (raøng buoäc 2, raøng Ví duï 1.8. Cho baøi toaùn QHTT buoäc 3, raøng buoäc 4) vaø f( x ) x1 2 x 2 3 x 3 min x x x 4 1 0 0 1 2 3 x1 x 2 0 det 1 1 3 1 6 5 0 6 2 1 xj 0, j 1,3 Vaäy Z laø phöông aùn cöïc bieân cuûa baøi toaùn. Caùc vectô naøo sau ñaây X = (2, 2, 0), Y = (0, 0, 4), Z = (1, 1, 2), laø P.A.C.B cuûa baøi toaùn. CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT  X, Y, Z thoûa caùc raøng buoäc neân chuùng laø P.A. HEÄ QUAÛ 2. Soáù thaønh phaàn döông trong moãi  Maët khaùc ta coù phöông aùn cöïc bieân cuûa baøi toaùn quy hoaïch 1 1 1 A A A tuyeán tính daïng chính taéc toái ña baèng m (m laø 1 1 2 1 3 0 soá doøng cuûa ma taän A). 1 1  Vôùi X = (2, 2, 0), det 2 neân X laø P.A.C.B. ÑÒNH LYÙ 2. (SÖÏ TOÀN TAÏI CUÛA PHÖÔNG AÙN TOÁI ÖU) 1 1 Neáu baøi toaùn quy hoaïch tuyeán tính coù phöông aùn vaø haøm muïc tieâu bò chaën döôùi (ñoái vôùi  Vôùi Y = (0, 0, 4), heä chæ goàm moät vectô A3 neân Y cuõng laø P.A.C.B. f(x) min) hoaëc haøm muïc tieâu bò chaën treân (ñoái vôùi f(x) max) treân taäp caùc phöông aùn thì  Vôùi Z=(1, 1, 2), ta thaáy heä {A1, A2, A3} phuï thuoäc baøi toaùn coù phöông aùn toái öu. tuyeán tính vì A1+A2–2A3=0 neân Z khoâng laø P.A.C.B. HEÄ QUAÛ 1. (tính höõu haïn cuûa P.A.C.B). ÑÒNH LYÙ 3. (SÖÏ TOÀN TAÏI CUÛA P.A.C.B. TOÁI ÖU) Soáù phöông aùn cöïc bieân cuûa baøi toaùn QHTT Neáu baøi toaùn QHTT daïng chính taéc coù P.A.T.Ö daïng chính taéc laø höõu haïn. thì baøi toaùn coù P.A.C.B toái öu (P.A.C.B.T.Ö). 6
7. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT ÑÒNH LYÙ 4. (SÖÏ TOÀN TAÏI NHIEÀU P.A.C.B.T.Ö) Ví duï 1.9 . (1) (2) Neáu baøi toaùn coù P.A.T.Ö laø Xopt vaø X , X laø 2 phöông aùn khaùc nhau cuûa baøi toaùn thoaû Xopt = Vôùi baøi toaùn quy hoaïch tuyeán tính X(1) + (1–)X(2), 0  1 thì X(1), X(2) laø P.A.T.Ö. f (x) x x min NHAÄN XEÙT 2 5 1. Ta coù theå tìm P.A.T.Ö cuûa baøi toaùn QHTT x1 x2 2x5 1 trong soá caùc P.A.C.B cuûa baøi toaùn vaø coù theå xaùc ñònh ngay P.A.C.B cuûa baøi toaùn daïng 3x2 x3 x5 3 chuaån baèng caùch cho caùc aån khoâng cô baûn 2x x x 2 baèng khoâng (xem Ví duï 1.9). 2 4 5 2. Trong baøi toaùn QHTT daïng chính taéc. Neáu x j 0 j 1,5 haïng cuûa ma traän heä soá A laø m thì P.A.C.B Ta coù phöông aùn X = (1, 0, 3, 2, 0) laø phöông aùn ñöôïc goïi laø khoâng suy bieán neáu noù coù ñuùng m thaønh phaàn döông. Neáu P.A.C.B coù ít hôn m cöïc bieân cuûa baøi toaùn vì caùc aån x1, x3, x4 laø caùc thaønh phaàn döông thì ñöôïc goïi laø P.A.C.B suy aån cô baûn cuûa baøi toaùn daïng chuaån. bieán (xem Ví duï 1.10). CAÙC TÍNH CHAÁT CUÛA BAØI TOAÙN QHTT CAÙC PHÖÔNG PHAÙP GIAÛI Ví duï 1.10 . Vôùi baøi toaùn quy hoaïch tuyeán tính BAØI TOAÙN QUY HOAÏCH TUYEÁN TÍNH f( x ) 3 x1 4 x 2 2 x 3 2 x 4 min 2x 2 x x 28 1 2 4 4.1. PHÖÔNG PHAÙP HÌNH HOÏC (Xem) x1 5 x 2 3 x 3 2 x 4 26 Ths. Nguyeãn Coâng (Xem)Trí 2x1 2 x 2 2 x 3 x 4 16 4.2. PHÖÔNG PHAÙP ÑÔN HÌNH x 0 j 1,4 j 4.3.PHÖÔNG PHAÙP ÑÔN HÌNH MÔÛ ROÄNG Kieåm tra vectô X = (11, 3, 0, 0) coù phaûi laø P.A.C.B? (BAØICopyrightTOAÙN M) 2001 (Xem)  Kieåm tra tröïc tieáp, ta coù X laø P.A cuûa baøi toaùn.  Haïng cuûa ma traän heä soá cuûa heä raøng buoäc tuyeán tính baèng 3 vaø X coù 2 thaønh phaàn döông laø x1 =11, x2 = 3 neân X laø P.A.C.B suy bieán. 7
8. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 PHÖÔNG PHAÙP HÌNH HOÏC PHÖÔNG PHAÙP HÌNH HOÏC Xeùt baøi toaùn QHTT coù 2 bieán. Ví duï 1.11. Moät coâng ty coù 2 phaân xöôûng: PX1 vaø PX2 cuøng saûn xuaát 2 loaïi saûn phaåm A vaø B. Naêng ax+by=c suaát vaø chi phí saûn xuaát cuûa moãi PX trong 1 giôø: =m (ñöôøng möùc) Phaân xöôûng PX PX taêng 1 2 ax+by c Saûn phaåm B 100 200 O a Chi phí (trieäu ñoàng/ giôø) 0,6 1 giaûm b N(a,b) Ñôn ñaët haøng: ít nhaát 5.000 SpA, 3.000 SpB. Haõy phaân phoái thôøi gian hoaït ñoäng cuûa 2 phaân xöôûng sao cho thoaû yeâu caàu ñôn ñaët haøng vaø chi phí saûn xuaát thaáp nhaát. PHÖÔNG PHAÙP HÌNH HOÏC PHÖÔNG PHAÙP HÌNH HOÏC 0,6x1+x2=m Goïi x1, x2 laàn löôït laø soá giôø hoaït ñoäng cuûa phaân xöôûng thöù nhaát vaø phaân xöôûng thöù hai. 100x +200x =3000 Mieàn raøng buoäc Ta coù moâ hình baøi toaùn 1 2 D 20 A (0,20) f x 0,6 x1 x 2 min 1 15 10 250x1 250 x 2 5000 A3 taêng (10,10) A2(30,0) 100x1 200 x 2 3000 10 20 30 x1 0 x 2 0 giaûm 250x1+250x2=5000 Duøng phöông phaùp hình hoïc ñeå giaûi baøi toaùn Vaäy P.A.T.Ö: xopt(10,10) vaø f(xopt)=16 trieäu ñoàng. treân nhö sau 8
9. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 PHÖÔNG PHAÙP HÌNH HOÏC PHÖÔNG PHAÙP HÌNH HOÏC -2x1+x2= m x1-x2= -2 Ví duï 1.12. Giaûi baøi toaùn quy hoaïch tuyeán tính Mieàn raøng buoäc f x 2 x1 x 2 min D -x +2x = -2 1 2 2 x x 2 A1(0,2) 1 2 x1 2 x 2 2 -1 2 -2 O A2(2,0) x1 0 x 2 0 taêng giaûm -1 baèng phöông phaùp hình hoïc Haøm muïc tieâu khoâng bò chaën. Baøi toaùn khoâng coù phöông aùn toái öu. CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH f( x ) 3 x 2 x x min Ví duï 13: giaûi baøi toaùn 1 2 3 Ta coù P.A.C.B laø x = (0, 0, 0, 10, 5, 8) 2x1 4 x 2 3 x 3 10 Baøi toaùn töông ñöông f( x ) 3 x 2 x x min 3x1 x 2 4 x 3 5 1 2 3 x 2 x 2 x 8 w 10 2 x 4 x 3 x 1 2 3 1 1 2 3 w 5 3 x x 4 x xj 0 j 1,3 2 1 2 3 Ñöa baøi toaùn veà daïng chính taéc w 8 x 2 x 2 x 3 1 2 3 f( x ) 3 x1 2 x 2 x 3 min xj 0 j 1,3, w i 0, i 1,3 2x1 4 x 2 3 x 3 w 1 10 coù P.A.C.B laø x = (0, 0, 0, 10, 5, 8) vaø f(x) = 0. 3x1 x 2 4 x 3 w 2 5 Nhaän xeùt: x 2 x 2 x w 8 1 2 3 3 coù theå ñoåi P.A baèng caùch taêng x1 baèng moät giaù trò döông vaø giöû x2 = x3 = 0 thoûa ñieàu kieän wi ≥ 0. xj 0, j 1,3, w i 0, i 1,3 9
10. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH Ta coù Ta coù keát quaû x1 5 f( x ) 5 w2 x 2 3 x 3 min w1 10 2 x 1 0 5 5 20 2 10 1 w2 5 3 x 1 0 x 1 x 1 w w x x 3 3 13 3 2 3 2 3 3 w3 8 x 1 0 (Choïn doøng 2) x1 8 5 1 1 4 x1 w 2 x 2 x 3 3 3 3 3 Choïn x1 = 5/3, ta ñöôïc P.A môùi laø 19 1 5 2 w w x x x1 = 5/3, x2 = x3 = w2 = 0, w1 = 20/3, w3 = 19/3. 3 2 2 3 3 3 3 3 Vaø f(x) = - 5. xj 0 j 1,3, w i 0, i 1,3 Baøi toaùn töông ñöông: taïi raøng buoäc thöù hai tính Nhaän xeùt: x1 theo caùc bieán coøn laïi, roài theá giaù trò x1 vöøa tính coù theå ñoåi P.A baèng caùch taêng x2 baèng moät giaù ñöôïc vaøo caùc raøng buoäc vaø haøm muïc tieâu. trò döông vaø giöû x3 = w2 = 0 thoûa ñieàu kieän wi ≥ 0. CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH Ta coù keát quaû Ta coù 3 4 31 20 10 f( x ) 7 w1 w 2 x 3 min w x 0 1 1 10 5 10 3 3 x2 2 3 1 1 5 1 x2 2 w 1 w 2 x 3 x1 x 2 0 x 2 5 x 2 2 10 5 10 3 3 19 (Choïn doøng 1) 1 6 39 19 5 x2 x1 1 w 1 w 2 x 3 w3 x 2 0 5 10 15 30 3 3 Choïn x = 2, ta ñöôïc P.A môùi laø 1 2 2 w3 3 w 1 x 3 2 3 x1 = 1, x3 = w1 = w2 = 0, w3 = 3 vaø f(x) = - 7. Baøi toaùn töông ñöông: taïi raøng buoäc thöù nhaát xj 0 j 1,3, w i 0, i 1,3 tính x theo caùc bieán coøn laïi, roài theá giaù trò x vöøa 2 2 Baøi toaùn coù P.A.T.U laø xopt = (1, 2, 0) tính ñöôïc vaøo caùc raøng buoäc vaø haøm muïc tieâu. vaø f(xopt) = - 7 10
11. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH n m m n m m Döïa treân cô sôû baøi toaùn coù daïng chuaån 2 x b a x , n i i i, m k m k f x  ci x i   a i, m k c i c m k x m k k 1 i 1 k 1 i 1 m f( x )  cj x j min hay max 1 n m j 1 f x f x0 x Ñaët m k a i, m k c i c m k thì  m k m k n m i 1 k 1 x a x b 2 i i, m k m k i  Neáu 0 thì f x0 f x , vì x 0 k 1 m k m k x 0 j 1, n b 0 3 j i  Neáu 0 thì f x f x0 , vì x 0 Daáu hieäu toái öu cuûa baøi toaùn m k m k m Phöông aùn cöïc bieân ñaàu tieân laø: m Kyù hieäu laïi: a c c 0 0 j ij i j x ( b1 , b 2 , ; bm ,.0  ,0) f ( x )  c i b i i 1 i 1 Choïn moät P.A baát kyø cuûa baøi toaùn (1) Khi f() x Min thì j 0; j n m n m x D,(,,,) x x x x 1 2 n f() x  cj x j  c i x i  c m k x m k j 1 i 1 k 1 (2) Khi f() x Max thì j 0; j CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH CÔ SÔÛ PHÖÔNG PHAÙP ÑÔN HÌNH  Daáu hieäu baøi toaùn khoâng coù P.A.T.Ö  Daáu hieäu baøi toaùn coù P.A.C.B. khaùc toát hôn Ñònh lyù. Vôùi moät phöông aùn cöïc bieân, neáu toàn taïi Ñònh lyù. Vôùi moät P.A.C.B, neáu >0, i: a > 0 thì baøi ≤  j ij j > 0 maø aij 0, i thì baøi toaùn khoâng coù P.A.T.Ö. toaùn coù P.A.C.B khaùc toát hôn P.A.C.B ñang xeùt. (xem Ví duï 1.13) Heää Aåån PA C1 C2 Ci Cm Cm+1 Cj Cn Heää Aånå PA C1 C2 Ci Cm Cm+1 Cj Cn soáá C.B CB x1 x2 xi xm xm+1 xj xn soáá C.B CB x1 x2 xi xm xm+1 xj xn C1 x1 b1 1 0 0 a1,m+1 a1j a1n C1 x1 b1 1 0 0 a1,m+1 a1j a1n C x b 0 1 0 a a a C2 x2 b2 0 1 0 a2,m+1 a2j a2n C2 x2 b2 0 1 0 a2,m+1 a2j a2n Ci xi bi 0 0 0 ai,m+1 aij ain Ci xi bi 0 0 0 ai,m+1 aij ain Cm xm bm 0 0 1 am,m+1 amj amn Cm xm bm 0 0 1 am,m+1 amj amn 0 f(x) f(x ) 0 0 0 m+1 j n 0 f(x) f(x ) 0 0 0 m+1 j n 11
12. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAÛNG ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH Heä ä Aåån PA C1 C2 Ci Cm Cm+1 Cj Cn LAÄP BAÛNG ÑÔN HÌNH soáá C.B CB x1 x2 xi xm xm+1 xj xn Ñuùng j ≤ 0,j? P.A.T.Ö C x b 1 0 0 a a a C1 x1 b1 1 0 0 a1,m+1 a1j a1n Sai C2 x2 b2 0 1 0 a2,m+1 a2j a2n Ñuùng KEÁT THUÙC aij ≤ 0,i? Sai THUAÄT GIAÛI C x b 0 0 0 a a a XAÙC ÑÒNH PHÖÔNG AÙN MÔÙI i i ii i,m+1 ij in BAØI TOAÙN Aån vaøo: Max j x j j 0 KHOÂNG COÙ P.A.T.Ö bi Cm xm bm 0 0 1 am,m+1 amj amn Aån ra:  Min xi a 0 0 ij aij f(x) f(x ) 0 0 0 m+1 j n BIEÁN ÑOÅI BAÛNG ÑÔN HÌNH SOÁ BÖÔÙC LAËP LAØ HÖÕU HAÏN THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH Thuaät giaûi goàm 4 böôùc: Böôùc 4: Tìm P.A.C.B môùi cuûa baøi toaùn Böôùc 1: Laäp baûng ñôn hình Choïn aån vaøo: Baøi toaùn phaûi ôû daïng chuaån, ñöa caùc soá lieäu vaøo Choïn Max j ( j > 0), aån xj seõ ñöôïc choïn ñöa vaøo baûng ñôn hình. heä aån cô baûn öùng vôùi j ñaõ ñöôïc choïn.  Böôùc 2: Kieåm tra tính toái öu cuûa baøi toaùn Choïn aån ra: Choïn  = Min{b /a } (a > 0), aån x seõ ñöôïc choïn Tính = ∑a c – c i ij ij i j ij i j ñöa ra khoûi heä aån cô baûn öùng vôùi  nhoû nhaát. Neáu j ≤ 0: baøi toaùn coù P.A.T.U. Phaàn töû aij (öùng vôùi aån vaøo xi vaø aån ra xj) ñöôïc  Neáu j > 0: chuyeån sang böôùc 3. goïi laø phaàn töû truïc. Böôùc 3: Kieåm tra tính giaûi ñöôïc cuûa baøi toaùn  Duøng phöông phaùp bieán ñoåi sô caáp doøng Neáu aij ≤ 0, i: baøi toaùn khoâng coù P.A.T.U. treân ma traän heä soá ñeå bieán ñoåi aån môùi ñöa vaøo trôû thaønh aån cô baûn. Sau ñoù quay veà böôùc 2.  Neáu aij > 0: chuyeån sang böôùc 4. 12
13. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH NHAÄN XEÙT. Daáu hieäu baøi toaùn coù nhieàu P.A.T.Ö. Ví duï 1.14. Vôùi P.A.C.B.T.Ö X tìm ñöôïc, neáu  = 0, maø x opt j j Giaûi baøi toaùn quy hoaïch tuyeán tính khoâng laø P.A.C.B thì baøi toaùn coù P.A.C.B.T.Ö khaùc / f( x ) 6 x1 x 2 x 3 3 x 4 x 5 7 x 6 6 x 7 min X opt (xem Ví duï 1.15). x x x x x 3 Taäp phöông aùn toái öu: 1 2 4 6 7 2x x 4 x 2 x x 9 / 1 3 4 6 7 Tröôøng hôïp coù hai P.A.C.B.T.Ö laø Xopt vaø X opt 4x1 2 x 4 x 5 3 x 6 2 / Topt = {Xopt + (1 – )X opt,  [0, 1]} xj 0 j 1,7 (1) (2) (3)  Tröôøng hôïp coù 3 P.A.C.B.T.Ö X opt, X opt, X opt (1) (2) (3) Topt = { X opt + X opt + X opt, }, vôùi , ,  0 vaø +  +  = 1. THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH HEÄ AÅN P.A 6 1 1 3 1 7 6 Ví duï 1.15. SOÁ C.B x1 x2 x3 x4 x5 x6 x7 Giaûi baøi toaùn quy hoaïch tuyeán tính 1 x2 3 1 1 0 1 0 1 1 f( x ) 5 x1 4 x 2 5 x 3 2 x 4 x 5 3 x 6 min 1 x3 9 2 0 1 4 0 2 1 2x1 4 x 2 3 x 3 x 4 152 1 x5 2 4 0 0 2 1 3 0 4x 2 x 3 x x 60 f x 14 5 0 0 6 0 7 6 1 2 3 5 3x x x 36 7 x6 3 1 1 0 1 0 1 1 1 3 6 1 x3 3 0 2 1 2 0 0 3 x 0 j 1,6 1 x 11 1 3 0 1 1 0 3 j 5 Baøi toaùn coù phöông aùn toái öu khaùc hay khoâng? f x 7 2 7 0 1 0 0 13 Neáu coù tìm taäp phöông aùn toái öu vaø chæ ra 3 BT khoâng coù P.A.T.Ö vì 4= 1 > 0 maø ai4 < 0, i. phöông aùn toái öu. 13
14. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH HEÄ P.A HEÄ AÅN P.A 5 4 5 2 1 3 AÅN 5 4 5 2 1 3 SOÁ x1 x2 x3 x4 x5 x6 SOÁ C.B x1 x2 x3 x4 x5 x6 C.B 2 x4 104 0 0 1 1 2 2 2 x4 152 2 4 3 1 0 0 5 1 2 4 x2 6 0 1 6 0 2 3 1 x5 60 4 2 3 0 1 0 1 1 5 x1 12 1 0 3 0 0 3 3 x6 36 3 0 1 0 0 1 f x 472 12 6 7 0 0 0 f x 292 0 0 2 0 3 0 7 2 2 x4 128 0 4 3 1 0 3 Baøi toaùn coù P.A.T.Ö xopt=(12, 6, 0, 104, 0, 0) vaø 5 4 f(xopt)= 292. 1 x5 12 0 2 3 0 1 3 1 1 Baøi toaùn coøn P.A.C.B.T.Ö khaùc vì 6 = 0, nhöng x6 5 x1 12 1 0 3 0 0 3 khoâng phaûi laø A.C.B. Ta coù P.A.C.B.T.Ö thöù hai f x 328 0 6 3 0 0 4 baèng caùch choïn aån x6 laø aån ñöa vaøo. THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH Vôùi taäp phöông aùn toái öu, ta coù : HEÄ AÅN P.A 5 4 5 2 1 3 / xopt + (1 - )x opt = SOÁ C.B x1 x2 x3 x4 x5 x6 (12, 6, 0, 104, 0, 0) + (1-)(0, 30, 0, 32, 0, 36) 2 x4 32 6 0 3 1 2 0 3 1 = (12 , 30–24, 0, 32 + 72, 0, 36 - 36) 4 x2 30 2 1 2 0 2 0 3 phöông aùn toái öu laø 3 x6 36 3 0 1 0 0 1  Vôùi  = 0, ta coù P.A.T.Ö: f x 292 0 0 2 0 3 0 / / x opt = (0, 30, 0, 32, 0, 36) vaø f(x opt) = 292. Baøi toaùn coù phöông aùn cöïc bieân toái öu khaùc laø  Vôùi  = 1, ta coù P.A.T.Ö: x/ = (0, 30, 0, 32, 0, 36) vaø f(x/ ) = 292. / opt opt xopt = (12, 6, 0, 104, 0, 0) vaø f(x opt) = 292. Taäp phöông aùn toái öu  Vôùi  = ½, ta coù P.A.T.Ö: / Topt={xopt + (1 - )x opt,  0, 1} Zopt = (6, 18, 0, 68, 0, 18) vaø f(zopt) = 292. 14
15. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH NHAÄN XEÙT. Neáu baøi toaùn coù haøm muïc tieâu Ví duï 1.16. n f() x  cj x j Max Giaûi baøi toaùn quy hoaïch tuyeán tính j 1 Coù hai caùch giaûi: f( x ) 2 x1 x 2 x 3 x 4 max Giaûi tröïc tieáp baøi toaùn (xem Ví duï 1.16), vôùi: x1 x 2 2 x 3 x 4 2  Tieâu chuaån toái öu laø 0, j j x2 7 x 3 3 x 4 2 •  AÅn vaøo laø Min j 0 3x 2 x 5 j b 3 4 •  AÅn ra laø Min i aij 0 a xj 0 j 1,4  ij Chuyeån haøm muïc tieâu cuûa baøi toaùn veà min Baøi toaùn coù phöông aùn toái öu khaùc hay khoâng? g()() x f x Min Neáu coù, haõy chæ ra phöông aùn toái öu khaùc. THUAÄT GIAÛI ÑÔN HÌNH THUAÄT GIAÛI ÑÔN HÌNH Ñöa baøi toaùn veà daïng chính taéc baèng caùch HEÄ P.A theâm aån phuï x ≥ 0 vaøo raøng buoäc thöù hai vaø aån AÅN 2 1 1 1 0 0 5 x x x x x x phuï x6 ≥ 0 vaøo raøng buoäc thöù ba. SOÁ C.B 1 2 3 4 5 6 Ta coù baøi toaùn ôû daïng chuaån 2 x1 2 1 1 2 1 0 0 f( x ) 2 x1 x 2 x 3 x 4 max 0 x5 2 0 1 7 3 1 0 0 x6 5 0 0 3 2 0 1 x1 x 2 2 x 3 x 4 2 f x 4 0 1 5 1 0 0 x2 7 x 3 3 x 4 x 5 2 1 1 1 1 x3 1 2 2 1 2 0 0 7 5 1 3x3 2 x 4 x 6 5 0 x5 9 2 2 0 2 1 0 3 3 1 0 x6 8 2 2 0 2 0 1 xj 0 j 1,6 5 3 3 f x 1 0 2 0 0 Laäp baûng ñôn hình 2 2 15
16. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH CÔ SÔÛ THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG Xuaát phaùt töø baøi toaùn daïng chính taéc HEÄ AÅN P.A 2 1 1 1 0 0 n f() x c x Min SOÁ C.B x1 x2 x3 x4 x5 x6  j j x j 1 1 3 9 2 2 1 0 0 1 n 0 x 5 17 5 4 0 0 1 1 aij x j b i , i 1, m j 1 I 1 x4 16 3 3 0 1 0 2 f x 25 7 6 0 0 0 3 xj 0 j 1, n b i 0 Vì caùc j 0, j neân baøi toaùn coù P.A.T.Ö laø Khoâng laøm maát tính toång quaùt cuûa baøi toaùn, ta giaû söû caùc b 0 vaø ma traän heä soá cuûa heä raøng Xopt = (0, 0, 9, 16) vaø f(Xopt) = 25. i Baøi toaùn treân khoâng coøn phöông aùn toái öu naøo buoäc khoâng chöùa vectô (coät) ñôn vò naøo. Coäng vaøo moãi raøng buoäc vôùi moät aån giaû töông khaùc vì khoâng coù j = 0 naøo vôùi xj laø aån khoâng (g) cô baûn. öùng xi ≥ 0 thì ta ñöôïc baøi toaùn coù daïng: CÔ SÔÛ THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG BAÛNG ÑÔN HÌNH MÔÛ ROÄNG n m g Heää AÅÅn PA C C C C C C f() x  cj x j M  x i Min 1 2 m m+1 j n j 1 i 1 Soáá C.B CB x1 x2 xm xm+1 xj xn n a x xg b, i 1, m II M xn+1 b1 a11 a12 a1m a1,m+1 a1j a1,n  ij j i i j 1 M x n+2 b2 a21 a22 a2m a2,m+1 a2j a2,n g xj 0, j 1, n ; x i 0, i 1, m , M 0 vo âcuøng lôùn. M x n+i bi ai1 ai2 aim ai,m+1 aij ai,n Baøi toaùn (I) ñöôïc goïi laø baøi toaùn goác, baøi toaùn (II) goïi laø baøi toaùn môû roäng hay baøi toaùn M. M xn+m bm am1 am2 amm am,m+1 amj am,n f(x) f(x0) g f(x) f(x ) 1 2 m m+1 j n Moät phöông aùn cuûa baøi toaùn M coù daïng x xj, x i (g) trong ñoù xj goàm n aån thaät vaø xi goàm m aån giaû. Trong ñoù caùc xn+i (i = 1, 2, , m) laø caùc aån giaû. 16
17. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 CÔ SÔÛ THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG CÔ SÔÛ THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG NHAÄN XEÙT. b) Neáu trong heä aån cô baûn cuûa baøi toaùn M coù Khi thuaät giaûi cuûa baøi toaùn M keát thuùc thì coù hai chöùa aån giaû nhöng giaù trò cuûa chuùng ñeàu baèng tröôøng hôïp sau ñaây coù theå xaûy ra: khoâng thì P.A.T.Ö cuûa baøi toaùn goác laø P.A.T.Ö. [1] Neáu baøi toaùn M (Baøi toaùn II) khoâng coù cuûa baøi toaùn M loaïi boû caùc aån giaû baèng khoâng phöông aùn toái öu thì baøi toaùn goác (Baøi toaùn I) (xem Ví duï 1.18). cuõng khoâng coù phöông aùn toái öu. c) Neáu trong heä aån cô baûn cuûa baøi toaùn M coù [2] Neáu baøi toaùn M (Baøi toaùn II) coù phöông aùn toái moät aån giaû maø giaù trò cuûa chuùng khaùc khoâng thì öu thì coù 3 tröôøng hôïp xaûy ra sau ñaây: baøi toaùn goác khoâng coù P.A.T.Ö. a) Trong heä A.C.B khoâng chöùa aån giaû naøo thì Chuù yù. Neáu haøm muïc tieâu laø f(x) Max thì heä soá P.A.T.Ö cuûa baøi toaùn M cuõng chính laø P.A.T.Ö caùc aån giaû trong haøm muïc tieâu cuûa baøi toaùn M cuûa baøi toaùn goác (xem Ví duï 1.17). laø (– M), vôùi M > 0 voâ cuøng lôùn (xem Ví duï 1.19). THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG ÑÖA BAØI TOAÙN VEÀ DAÏNG CHUAÅN Ví duï 1.17. (tröôøng hôïp a). Giaûi baøi toaùn QHTT f( x ) 8 x 6 x 2 x min LAÄP BAÛNG ÑÔN HÌNH 1 2 3 4x1 4 x 2 3 x 3 18 Ñuùng COÙ g Coù x g 0? Ñuùng j ≤ 0? xi ? i P.A.T.Ö 4x1 3 x 2 4 x 3 16 Sai Khoâng Sai x 0 j 1,3 Ñuùng KHOÂNG j KHOÂNG aij ≤ 0? COÙ COÙ P.A.T.Ö Nhaân (– 1) vaøo raøng buoäc thöù nhaát, baøi toaùn coù COÙ Sai P.A.T.Ö daïng chính taéc nhö sau Xaùc ñònh phöông aùn môùi P.A.T.Ö f( x ) 8 x1 6 x 2 2 x 3 min Aån vaøo: Max j 0 KEÁT THUÙC THUAÄT GIAÛI j b 4x 4 x 3 x 18 Aån ra:  Min i 1 2 3 a 0 ij aij 4x 3 x 4 x 16 SOÁ BÖÔÙC LAËP 1 2 3 BIEÁN ÑOÅI BAÛNG ÑÔN HÌNH LAØ HÖÕU HAÏN xj 0 j 1,3 17
18. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG Ñöa baøi toaùn veà daïng chuaån: HEÄ AÅN P.A 8 6 2 SOÁ C.B x1 x2 x3 Theâm hai aån giaû x4 ≥ 0 vaø x5 ≥ 0 vaøo laàn löôït vaøo raøng buoäc thöù nhaát vaø thöù hai cuûa baøi toaùn M x4 18 4 4 3 Baøi toaùn coù daïng chuaån nhö sau: M x5 16 4 3 4 f x 34M 8M 8 7M 6 M 2 fx( ) 8 x1 6 x 2 2 xMxx 3 ( 4 5 ) Min M x4 2 0 1 7 3 4x1 4 x 2 3 x 3 x 4 18 8 x1 4 1 4 1 f x 2M 32 0 M 12 7M 10 4x1 3 x 2 4 x 3 x 5 16 6 x2 2 0 1 7 x 5 25 xj 0 j 1,5 M 0 vo â cuøng lôùn. 8 1 2 1 0 4 f x 8 0 0 94 Ta coù baûng ñôn hình môû roäng Baøi toaùn coù P.A.T.Ö Xopt=(5/2, 2, 0), f(Xopt)= –8. THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG Ví duï 1.18. (tröôøng hôïp b). Giaûi baøi toaùn QHTT f( x ) 6 x1 3 x 2 x 3 min Theâm hai aån giaû x5 ≥ 0, x6 ≥ 0 laàn löôït vaøo raøng buoäc thöù hai vaø raøng buoäc thöù ba. 2x1 5 x 2 x 3 10 Ta coù baøi toaùn daïng chuaån nhö sau 4x1 3 x 2 2 x 3 16 2x 4 x x 8 f( x ) 6 x1 3 x 2 x 3 M ( x 5 x 6 ) min 1 2 3 x 0 j 1,3 j 2x1 5 x 2 x 3 x 4 10 Theâm aån phuï x4 0 vaøo raøng buoäc thöù nhaát 4x1 3 x 2 2 x 3 x 5 16 f( x ) 6 x1 3 x 2 x 3 min 2x 5 x x x 10 2x 4 x x 1 2 3 4 1 2 3 x6 8 4x 3 x 2 x 16 1 2 3 x 0 j 1,6 M 0 2x 4 x x 8 j 1 2 3 Ta coù baûng ñôn hình môû roäng xj 0 j 1,4 18
19. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG HEÄ AÅN 6 3 1 0 HEÄ AÅN 6 3 1 0 P.A P.A SOÁ x1 x2 x3 x4 SOÁ C.B x1 x2 x3 x4 C.B x 0 x4 10 2 5 1 1 0 4 2 0 1 0 1 x M x5 16 4 3 2 0 M 5 0 0 11 0 0 x M x6 8 2 4 1 0 1 3 8 2 4 1 0 f x 24M 6M 6 M 3 3M 1 0 f x 8 4 11M 1 0 0 x 0 4 2 0 1 0 1 P.A.T.Ö cuûa BTM laø x 0, 0, 8, 2, 0, 0 M x 0 0 11 0 0 5 vôùi aån giaû x5 = 0 1 6 x1 4 1 2 2 0 P.A.T.Ö cuûa BT goác laø xopt = (0, 0, 8) 24 11M 9 0 f x 0 2 vaø f(xopt) = 8. THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG Ví duï 1.19. (tröôøng hôïp c). Giaûi baøi toaùn QHTT Theâm 2 aån giaû vaøo x , x 0 laàn löôït vaøo raøng f( x ) 2 x x x max 6 7 1 2 3 buoäc (1) & (3). 4x1 x 2 2 x 3 12 Ta coù baøi toaùn daïng chuaån nhö sau 2x1 2 x 2 x 3 10 x 2 x 1 2 x 10 f( x ) 2 x1 x 2 x 3 M x 6 x 7 max 1 2 3 4x x 2 x x x 12 xj 0 j 1,3 1 2 3 4 6 Theâm 2 aån phuï x4, x5 ≥ 0 vaøo raøng buoäc (1) & (2) 2x1 2 x 2 x 3 x 5 10 f( x ) 2 x x x max 1 2 3 1 4x1 x 2 2 x 3 x 4 12 x1 2 x 2 x 3 x 7 10 2 2x1 2 x 2 x 3 x 5 10 x 2 x 1 2 x 10 x 0 j 1,7 M 0 1 2 3 j xj 0 j 1,5 Ta coù baûng ñôn hình môû roäng 19
20. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 THUAÄT GIAÛI ÑÔN HÌNH MÔÛ ROÄNG BAØI TAÄP CHÖÔNG 1 HEÄ 2 1 1 0 0 AÅN P.A LAÄP MOÂ HÌNH BAØI TOAÙN SOÁ x1 x2 x3 x4 x5 C.B [1] [2] [3] [4] M x 12 4 1 2 1 0 6 BAØI TOAÙN QHTT DAÏNG CHÍNH TAÉC 0 x5 10 2 2 1 0 1 1 [5a] [5b] M x7 10 1 2 2 0 0 3 XAÙC ÑÒNH P.A – P.A.C.B VAØ P.A.T.Ö. f x 22M 3M 2 3M 1 2 M 1 M 0 1 1 [6] [7a] [7b] [7c] 1 x 6 2 2 1 2 0 3 GIAÛI BAØI TOAÙN QHTT BAÈNG PP HÌNH HOÏC 0 x 16 4 3 0 1 1 5 2 2 [8a] [8b] [8c] M x 13 0 9 0 1 0 7 4 4 GIAÛI BAØI TOAÙN QHTT BAÈNG PP ÑÔN HÌNH 1 9 1 1 f x 6 13M 2 4 M 2 4 M 0 0 0 [9] [10] [11] [12] P.A.T.Ö Xopt = (0, 0, 6, 0, 16, 0, 13), vôùi x7 = 13 0 neân baøi toaùn goác khoâng coù P.A.T.Ö. [13] [14] [15] [16] [17] BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 1. Moät xí nghieäp cheá bieán ñoà goã hieän coù 3.000 1.Goïi xj (j=1, 2, 3, 4) laàn löôït laø soá löôïng boä tuû, ñôn vò goã nguyeân lieäu nhoùm I, 5.000 ñôn vò goã boä cöûa, boä sa–loâng vaø boä giöôøng nguû do xí nguyeân lieäu nhoùm II vaø 2.000 ñôn vò goã nguyeân nghieäp saûn xuaát. lieäu nhoùm III. Theo keá hoaïch xí nghieäp phaûi saûn xuaát boán loaïi haøng hoaù vôùi ñònh möùc nguyeân Moâ hình cuûa baøi toaùn lieäu vaø lôïi nhuaän ñöôïc theå hieän trong baûng sau f(x) = 0,5x1 + 0,8x2 + 0,4x3 + 0,6x4 Max Saûûn phaååm Vôùi caùc raøng buoäc veà nguyeân lieäu Ñònh möùùc Boää tuûû Boää cöûûa Boää sa-loââng Boää giöôøøng nguûû Nguyeâân lieääu 30x1 + 40x2 + +10x4 ≤ 3000, Goãã nhoùùm I 30 40 0 10 Goãã nhoùùm II 10 20 50 60 10x1 + 20x2 + 50x3 + 60x4 ≤ 5000, Goãã nhoùùm III 10 50 80 20 10x1 + 50x2 + 80x3 + 20x4 ≤ 2000, Lôïïi nhuaään (trieääu ñoààng) 0,5 0,8 0,4 0,6 Raøng buoäc caùc aån soá Haõy laäp moâ hình baøi toaùn sao cho xí nghieäp ñaït lôïi nhuaän nhieàu nhaát? xj ≥ 0 , j = 1, 2, 3, 4 20
21. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 2. Moät coâng ty coù keá hoaïch quaûng caùo moät loaïi 3. Moät xí nghieäp coù theå söû duïng toái ña 510 giôø saûn phaåm do coâng ty saûn xuaát trong thôøi gian maùy caùn, 360 giôø maùy tieän vaø 150 giôø maùy maøi moät thaùng vôùi toång chi phí laø 100 trieäu ñoàng. ñeå cheá taïo 3 saûn phaåm A, B vaø C. Ñeå cheá taïo Caùc phöông tieän ñöôïc choïn ñeå quaûng caùo saûn moät saûn phaåm A caàn 9 giôø maùy caùn, 5 giôø maùy phaåm vôùi soá lieäu ñöôïc döï kieán nhö sau: tieän vaø 3 giôø maùy maøi; moät saûn phaåm B caàn 3 Phöông tieän Chi phí moãi laàn Soá laàn quaûng caùo Döï ñoaùn soá ngöôøi quaûng caùo quaûng caùo (trieäu Ñ) toái ña trong thaùng xem quaûng caùo giôø maùy caùn, 4 giôø maùy tieän; moät saûn phaåm C Truyeàn hình (1 phuùt) 1,5 60 15.000 caàn 5 giôø maùy caùn, 3 giôø maùy tieän vaø 2 giôø maùy Baùo (1/2 trang) 1 26 30.000 maøi. Moãi saûn phaåm A trò giaù 48 ngaøn ñoàng, moãi Phaùt thanh (1 phuùt) 0,5 90 9.000 saûn phaåm B trò giaù 16 ngaøn ñoàng vaø moãi saûn Coâng ty yeâu caàu phaûi coù ít nhaát 30 laàn quaûng phaåm C trò giaù 27 ngaøn ñoàng. caùo treân truyeàn hình trong thaùng. Haõy laäp moâ Haõy laäp moâ hình baøi toaùn xí nghieäp caàn cheá taïo hình baøi toaùn sao cho phöông aùn quaûng caùo moãi loaïi bao nhieâu saûn phaåm ñeå coù toång giaù trò saûn phaåm cuûa coâng ty laø toái öu. saûn phaåm lôùn nhaát. BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 4. Moät xí nghieäp vaän taûi caàn chuyeån moät loaïi 5. a) Ñöa baøi toaùn quy hoaïch tuyeán tính sau ñaây haøng hoùa töø ba kho haøng A1, A2 vaø A3 ñeán boán veà daïng chính taéc f( x ) 4 x1 3 x 2 2 x 3 min cöûa haøng B1, B2, B3 vaø B4. Chi phí vaän chuyeån x1 x 2 4 x 3 6 moät ñôn vò haøng hoùa töø kho A (i = 1, 2, 3) ñeán 2x x 3 x 8 i Theâm 2 aån phuï x4, x5 0 1 2 3 cöûa haøng B (j = 1, 2, 3, 4) ñöôïc cho ôû baûng sau j vaøo raøng buoäc thöù hai, 3x1 4 x 2 2 x 3 3 Cöûûa haøøng Löôïïng haøøng / // x1 0, x 2 0 thöù ba vaø x3 = x 3 – x 3, Chi phí vaään chuyeåån B1 B2 B3 B4 hieään coùù (taáán) / // vôùi x 3 0, x 3 0, ta coù baøi toaùn daïng chính taéc Kho A1 3 4 0 1 40 f( x ) 4 x1 3 x 2 2 x 3 2 x 3 min A 1 2 5 6 30 2 x1 x 2 4 x 3 4 x 3 6 A3 1 5 8 2 30 2x1 x 2 3 x 3 3 x 3 x 4 8 Nhu caààu cuûaû cöûûa haøøng (taáán) 20 25 30 15 3x1 4 x 2 2 x 3 2 x 3 x 5 3 Haõy laäp moâ hình baøi toaùn vaän taûi haøng hoùa sao x1 0, x 2 0 x 3 0, x 3 0, x 4 0, x 5 0 cho toång chi phí vaän taûi beù nhaát? 21
22. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 5. b) Ñöa baøi toaùn quy hoaïch tuyeán tính sau ñaây 6. Cho baøi toaùn QHTT sau ñaây veà daïng chính taéc f( x ) 2 x 3 x x max 1 2 3 f(x) 3 x1 7x2 x 3 2 x 4 max 4x 2 x x 15 1 2 3 2x1 3x2 x 3 2 x 4 30 Theâm 2 aån phuï x , x 0 5x 2 x x 10 4 5 1 2 3 2 2x 3 x 60 x1 2 3 vaøo raøng buoäc thöù nhaát, 3x 6 x 2 x 25 1 2 3 2x 2x 3 x + 4 x 32 / // 1 2 3 4 thöù ba vaø x2 = x 2 – x 2, x1 0, x 3 0 / // xj 0 (j 1,4) vôùi x 2 0, x 2 0, ta coù baøi toaùn daïng chính taéc Xeùt caùc veùctô X = (0, 0, 0, 8), Y = (14, 0, 0, 1), f( x ) 2 x1 3 x 2 3 x 2 x 3 min Z = (7, 0, 0, 9/2) vaø T = (16, 1, 0, ½) 4x1 2 x 2 2 x 2 x 3 x 4 15 (a) Vectô naøo laø P.A; vectô naøo laø P.A.C.B? 5x1 2 x 2 2 x 2 x 3 10 3x1 6 x 2 6 x 2 2 x 3 x 5 25 (b) Cho bieát Y laø P.A.T.Ö. Trong caùc vectô coøn laïi, x1 0, x 2 0 x 2 0, x 3 0, x 4 0, x 5 0 vectô naøo laø P.A.T.Ö cuûa baøi toaùn treân? BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 (a) Caùc vectô X, Y, Z vaø T laø P.A cuûa baøi toaùn vì 7. a) Tìm P.A.C.B khoâng suy bieán cuûa baøi toaùn chuùng thoûa heä raøng buoäc. f( x ) 4 x1 3 x 2 2 x 3 min  Vôùi X = (0, 0, 0, 8) thoûa 4 raøng buoäc chaët, ta coù 2 2 3 4 x1 x 2 x 3 1 1 0 0 1 0 0 0 x1 x 2 x 3 3 det 4det 0 1 0 4 0 1 0 0 x 0, j 1,2,3 0 0 1 j 0 0 1 0  Vaäy X laø P.A.C.B khoâng suy bieán. cho x1 = 0, ta coù heä phöông trình voâ nghieäm.  Töông töï, Y = (14, 0, 0, 1) laø P.A.C.B khoâng suy  cho x2 = 0, giaûi hpt, ta coù x1 = 2, x3 = 1. Kieåm tra bieán. Z vaø T khoâng phaûi laø P.A.C.B. tröïc tieáp phöông aùn X = (2, 0, 1) laø P.A.C.B khoâng (b) Vôùi Y laø P.A.T.Ö, ta coù f(Y) = 40, ta coù f(X) = – suy bieán. 16 f(Y), f(Z) = 12 f(Y) vaø f(T) = 40 = f(Y).  cho x3 = 0, ta coù Y = (2, 1, 0). Kieåm tra tröïc tieáp Vaäy T laø P.A.T.Ö. phöông aùn Y laø P.A.C.B khoâng suy bieán. 22
23. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 7. b) Tìm P.A.C.B khoâng suy bieán cuûa baøi toaùn 7. c) Tìm P.A.C.B khoâng suy bieán cuûa baøi toaùn f( x ) 4 x1 3 x 2 2 x 3 min f( x ) 4 x1 3 x 2 2 x 3 min x x x 10 x1 x 2 x 3 4 1 2 3 x x 0 2x1 x 2 3 x 3 14 1 2 x 0, j 1,2,3 xj 0, j 1,2,3 j BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 8. a) Giaûi baøi toaùn baèng phöông phaùp hình hoïc 8. b) Giaûi baøi toaùn baèng phöông phaùp hình hoïc f( x ) x x max 1 2 f( x ) 5 x1 4 x 2 max x x 1 1 2 x1 2 x 2 8 3x 2 x 6 1 2 x1 2 x 2 4 3x x 9 3x 2 x 12 1 2 1 2 x 0, j 1,2 j xj 0, j 1,2 23
24. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 8. c) Giaûi baøi toaùn baèng phöông phaùp hình hoïc 9. Giaûi baøi toaùn QHTT sau ñaây f( x ) 5 x 3 x min 1 2 f( x ) x1 x 2 2 x 4 2 x 5 3 x 6 min 2x1 x 2 6 x1 x 4 x 5 x 6 2 x1 x 2 0 2x x 0 x2 x 4 x 6 12 1 2 x 0, j 1,2 j x3 2 x 4 4 x 5 3 x 6 9 xj 0 j 1,6 BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 10. Giaûi baøi toaùn QHTT sau ñaây 11. Giaûi baøi toaùn QHTT sau ñaây f (x) 3x1 4x2 3x3 x4 max f (x) x2 2x3 2x5 min 1 1 x 3x x 2x 7 x x 2x x 3 1 2 3 5 2 1 2 4 4 5 1 1 2x2 4x3 x4 12 3x1 x3 x4 x5 x6 1 4 2 4x2 2x3 8x5 x6 10 11x1 17x4 x5 2x6 x7 20 x j 0 j 1,6 x j 0 j 1,7 24
25. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 12. Giaûi baøi toaùn QHTT sau ñaây 13. Giaûi baøi toaùn QHTT sau ñaây f( x ) x x 3 x min 1 2 3 f (x) 3x1 4x2 2x3 2x4 min Theâm 3 aån phuï 2x1 x 2 x 3 1 2x1 2x2 x4 28 x , x , x 0 vaøo 3 raøng 4 5 6 4x1 2 x 2 x 3 2 x1 5x2 3x3 2x4 31 buoäc, ta coù baøi toaùn 3x1 x 3 5 2x1 2x2 2x3 x4 16 daïng chuaån nhö sau x 0 j 1,4 xj 0 j 1,3 j Ñöa baøi toaùn veà daïng chính taéc f( x ) x1 x 2 3 x 3 min f( x ) 3 x1 4 x 2 2 x 3 2 x 4 min 2x1 x 2 x 3 x 4 1 2x1 2 x 2 x 4 28 4x1 2 x 2 x 3 x 5 2 x1 5 x 2 3 x 3 2 x 4 x 5 31 3x1 x 3 x 6 5 2x1 2 x 2 2 x 3 x 4 16 xj 0 j 1,6 xj 0 j 1,5 BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 14. Giaûi baøi toaùn QHTT sau ñaây 15. Giaûi baøi toaùn QHTT sau ñaây f (x) x1 2x2 3x3 x4 min f( x ) 3 x1 2 x 2 2 x 3 x 4 min x1 2x2 3x3 15 2x1 x 2 4 x 3 x 4 10 2x1 x2 5x3 20 3x1 2 x 2 x 3 2 x 4 8 x x x x1 2x2 x3 x4 10 41 2 2 3 4 x j 0 j 1,4 xj 0 j 1,4 25
26. ThS. Nguyễn Công Trí - Tối ưu hóa * Chương 1 BAØI TAÄP CHÖÔNG 1 BAØI TAÄP CHÖÔNG 1 16. Giaûi baøi toaùn QHTT sau ñaây 17. Duøng phöông phaùp ñôn hình giaûi caùc baøi f (x) x1 2x2 x4 x5 5x6 min toaùn töø baøi taäp [1] ñeán baøi taäp [8]. 6x1 2x2 x3 x4 x5 2x6 4 1 1 2x x x x x 3 1 3 2 3 4 2 5 1 3x x 2x 4x x x 2 1 2 3 4 2 5 6 x j 0 j 1,6 26