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: Bài toán quy hoạch tuyến tính

Chia sẻ: Lê Na | Ngày: | Loại File: PDF | Số trang:17

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

Chương 1 bài giảng môn Tối ưu hóa do ThS. Nguyễn Công Trí biên soạn cung cấp cho người học các kiến thức về thiết lập mô hình bài toán, các dạng của bài toán quy hoạch tuyến tính, các khái niệm cơ bản của bài toán quy hoạch tuyến tính,... Cuối mỗi chương có bài tập và lời giải 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: Bài toán quy hoạch tuyến tính

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