zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

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

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

Báo xấu

212
lượt xem 25
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 2 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 cung cấp cho người học các kiến thức về cách thành lập bài toán quy hoạch tuyến tính đối ngẫu, các định lý đối ngẫu, giải thuật đơn hình đối ngẫu,... 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 2: Bài toán quy hoạch tuyến tính đối ngẫu

ÝØJLÒÙ îæ ÞßH× ÌÑßGÒ OÑ_× ÒÙß]Ë Ì¸-ò Ò¹«§»=² Ý±>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ BAØ BAØI TOAÙ TOAÙN QUY HOAÏ HOAÏCH CH CHÖÔNG 2 THAØ THAØNH NH LAÄ LAÄP BAØ BAØI TOAÙ TOAÙN ÑOÁI NGAÃU TUYEÁ Muï Muïc ñích ñích vaø vaø yù nghó nghóa TUYEÁN TÍ TÍNH ÑOÁI NGAÃU Vôù Vôùi baø baøi toaù toaùn QHTT, baø baøi toaù goác, kyù toaùn goá kyù hieä hieäu laø laø P 1. CAÙ CAÙCH CH THAØ THAØNH NH LAÄ LAÄP BAØ BAØI TOAÙ TOAÙN QUY HOAÏ HOAÏCH CH Ths. Nguyeãn Coâng Tr Tríí (Primal), chuù chuùng ng ta coù coù theå theå thieá thieát laä laäp baø baøi toaù toaùn QHTT TUYEÁ TUYEÁN TÍ TÍNH ÑOÁI NGAÃU (Xem) Xem) khaù khaùc, c, baø toaùn ñoái ngaãu, kyù baøi toaù kyù hieä hieäu laø laø D (Dual), sao cho töø töø lôø lôøi giaû giaûi cuû cuûa baø baøi toaù toaùn naø naøy ta coù coù theå theå thu 2. CAÙ CAÙC ÑÒNH LYÙ LYÙ ÑOÁI NGAÃU (Xem) Xem) Copyright 2001 thaä thaäp ñöô ñöôïc thoâng tin veà veà lôø lôøi giaû giaûi cuû cuûa baø baøi toaù toaùn kia. 3. THUAÄ THUAÄT GIAÛ GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU (Xem) Ñeå coù coù thoâng tin caà caàn thieá thieát veà veà baø baøi toaù toaùn goá goác, c, coù coù theå theå nghieân cöù cöùu treân baø baøi toaù toaùn ñoái ngaãu cuû cuûa noù noù. í 4. MOÄ MOÄT SOÁ SOÁ ÖÙNG NG DUÏ DUÏNG CUÛ CUÛA LYÙ LYÙ THUYEÁ THUYEÁT ÑOÁI Hôn nö nöõa, khi phaân tí tích ñoàng ng thôø thôøi caû caû hai baø baøi Tr NGAÃU TRONG BAØBAØI TOAÙ TOAÙN QHTT (Xem) toaù toaùn goá goác vaø vaø ñoái ngaãu, chuù chuùng ng ta coù coù theå theå ruù ruùt ra Ths. Nguyeãn Coân g Tr Tríí caù caùc keá keát luaä luaän coù coù giaù giaù trò veà veà maë maët toaù toaùn hoï hoïc laãn veà veà 5. BAØ BAØI TAÄ TAÄP (Xem) Copyright 2001 maë maët yù yù nghó nghóa kinh teá teá. g oân THAØ THAØNH NH LAÄ LAÄP BAØ BAØI TOAÙ TOAÙN ÑOÁI NGAÃU THAØ THAØNH NH LAÄ LAÄP BAØ BAØI TOAÙ TOAÙN ÑOÁI NGAÃU Xeù Xeùt baø baøi toaù toaùn QHTT (P) dö döôùi daï daïng ng chí chính taé taéc Goï Goïi g(y) laø laø haø haøm muï muïc tieâu cuû cuûa baø baøi toaù toaùn (II), ta coù coù ct x g(y) = min{ctx + yt(b Ax)}, vôù vôùi x 0. f P ( x) min P Ax b I c tx + yt(b Ax), vôù vôùi x 0. x 0. Neá Neáu x laø laø P.A cuû cuûa baø baøi toaù toaùn (I) thì thì b Ax = 0 vaø vaø C Vôùi x = (x1, x2,... , x n) Vôù n, b = (b , b ,... , b ) 1 2 m m Giaû Giaû söû baø baøi toaù toaùn (P) coùcoù P.A.T.U laø laø x opt vaø vaø goï goïi x0 laø laø g(y) ctx. Vaä Vaäy g(y) laø laø moä moät caä caän dö döôùi baá baát kyø kyø cuû cuûa moä moät P.A cuû cuûa baø baøi toaù toaùn (P), ta coùcoù ctx opt ctx0. haø haøm muï muïc tieâu. Goïi x = (x 1, x2,... , x n) Goï n, vôù vôùi x 0 sao cho Ta tì tìm caä caän dö döôùi lôù lôùn nhaá nhaát Max{g(y)}, thaä thaät vaä vaäy Ax b 0 g(y) = min{ctx + yt(b Ax)}, vôù vôùi x 0. eãn Baø Baøi toaù toaùn tö töông ñöông: ñöông: L ( x, y ) c x t t y b Ax min = min{ctx + ytb ytAx}, vôù vôùi x 0. P x 0 II = min{ytb + (c t ytA)x}, vôù vôùi x 0. y Rm. = ytb + min{ (ct ytA)x}, vôù vôùi x 0. y gu THAØ THAØNH NH LAÄ LAÄP BAØ BAØI TOAÙ TOAÙN ÑOÁI NGAÃU THAØ THAØNH NH LAÄ LAÄP BAØ BAØI TOAÙ TOAÙN ÑOÁI NGAÃU Xeù Xeùt 0 khi c t yA 0t Ví duï duï 2.1. min c t yt A x Baø Baøi toaù toaùn ñoái ngaãu cuû cuûa baø baøi toaù toaùn QHTT sau ñaây x 0 khi c t yt A 0 Vaä Vaäy ta ñöô ñöôïc f ( x) 2 x1 8 x4 6 x5 min g(y) = ytb 2 x1 x3 x5 4 Suy ra baø baøi toaù toaùn ñoái ngaãu coù coù daï daïng ng 2 x2 x5 4 N t t x2 2 x3 3 x4 13 g ( y) yb max g ( y) yb max xj 0 j 1, 5 D ct yt A 0 yt A ct y Rm. y Rm. laø laø baø baøi toaù toaùn f D ( y) 4 y1 4 y2 13 y3 max 2 y1 2 Hay baø baøi toaù toaùn tö töông ñöông ñöông 2 y2 y3 0 g ( y) ytb max y1 2 y3 0 D At y c 3 y3 8 y Rm. y1 y2 6 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
ÝØJLÒÙ îæ ÞßH× ÌÑßGÒ OÑ_× ÒÙß]Ë Ì¸-ò Ò¹«§»=² Ý±>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ THAØ THAØNH NH LAÄ LAÄP BAØ BAØI TOAÙ TOAÙN ÑOÁI NGAÃU THAØ THAØNH NH LAÄ LAÄP BAØ BAØI TOAÙ TOAÙN ÑOÁI NGAÃU Baø Baøi toaù toaùn goá goác (P) Baø Baøi toaù toaùn ñoái ngaãu (D) Ví duï duï 2.2. Vieá Vieát baø baøi toaù toaùn ñoái ngaãu vaø vaø chæ chæ ra caù caùc Haø Haøm muï munïc tieâu Haø Haøm muï muïc mtieâu caë caëp raø raøng ng buoä buoäc ñoái ngaãu cuû cuûa baø baøi toaù toaùn QHTT Baø Baøi toaù toaùn ñoái ngaãu f P ( x) cjxj min f D ( y) bi yi max f ( x) x1 2 x2 x3 2 x4 min fD ( y ) y1 3 y2 4 y3 max j 1 i 1 Raø Raøng ng buoä buoäc thöù thöù i Raø Raøng ng buoä buoäc thöù thöù j x1 x2 2 x3 2x4 1 y1 3 y2 2 y3 1 3x1 x2 x3 3 y1 y2 3 y3 2 n m 2 x1 3 x2 x3 x4 4 2 y1 y2 y3 1 aij x j bi i 1, m aij yi c j , j 1, n j 1 i 1 xj 0 j 1, 2 2 y1 y3 2 AÅn thöù thöù j AÅn thöù thöù i Caù Caùc caë caëp ñoái ngaãu y1 0, y2 0 í x1 0, y1 3 y2 2 y3 1 1 Tr x2 0, y1 y2 3 y3 2 2 xj 0, j 1, n yi 0, i 1, m khoâ ng raøng buoä c x1 x2 2 x3 2 x4 1, y1 0 3 khoâng raøng buoä c VD2.2 VD2.3 VD2.4 VD2.5 VD2.6 VD2.7 3 x1 x2 x3 3, y2 0 4 g oân THAØ THAØNH NH LAÄ LAÄP BAØ BAØI TOAÙ TOAÙN ÑOÁI NGAÃU THAØ THAØNH NH LAÄ LAÄP BAØ BAØI TOAÙ TOAÙN ÑOÁI NGAÃU Ví duï duï 2.3. Vieá Vieát baø baøi toaù toaùn ñoái ngaãu vaø vaø chæ chæ ra caù caùc Ví duï duï 2.4. Vieá Vieát baø baøi toaù toaùn ñoái ngaãu vaø vaø chæ chæ ra caù caùc caë caëp raø raøng ng buoä buoäc ñoái ngaãu cuû cuûa baø baøi toaù toaùn QHTT caë caëp raø raøng ng buoä buoäc ñoái ngaãu cuû cuûa baø baøi toaù toaùn QHTT f ( x) 2 x x 8x max Baø Baøi toaù toaùn ñoái ngaãu f (x) 4 x1 3x2 8 x3 m in 1 2 3 f D ( y ) 28 y1 10 y2 15 y3 min x1 C 7 x1 4 x2 2 x3 28 1 0 1 2 7 y1 3 y2 2 y3 2 x2 3 x1 x2 3 x3 10 0 1 2 5 x3 2 x1 3 x2 x3 15 4 y1 y2 3y3 1 Caù Caùc raø raøng ng buoä buoäc ñoái ngaãu 2 y1 3 y2 y3 8 xj 0 j 1, 3 Baø Baøi toaù toaùn ñoái ngaãu x 0, xj 0 j 1, 2 y1 0, y3 0 y1 4 1 Caù Caùc caë caëp ñoái ngaãu 1 f D ( y) 2 y1 5 y2 max eãn x1 0, 7 y1 3 y2 2 y3 2 1 x2 0, y2 3 2 1 0 4 x2 0, 4 y1 y2 3 y3 1 2 y1 x3 0, y1 2 y2 8 3 0 1 3 y2 x1 x3 2, y1 0 4 7 x1 4 x2 2 x3 28, y1 0 3 1 2 8 x2 2 x3 5, y2 0 5 2 x1 3 x2 x3 15, y3 0 4 yj 0; j 1, 2 y gu THAØ THAØNH NH LAÄ LAÄP BAØ BAØI TOAÙ TOAÙN ÑOÁI NGAÃU CAÙ CAÙC ÑÒNH LYÙ LYÙ ÑOÁI NGAÃU Ví duï duï 2.5. Vieá Vieát baø baøi toaù toaùn ñoái ngaãu vaø vaø chæ chæ ra caù caùc Ñ ÒNH LYÙ LYÙ 1. caë caëp raø raøng ng buoä buoäc ñoái ngaãu cuûcuûa baø baøi toaù toaùn QHTT Neá Neáu moä moät trong hai baø baøi toaù toaùn ñoái ngaãu nhau coù coù f ( x ) 2 x1 5 x 2 max Baø Baøi toaù toaùn ñoái ngaãu fD ( y) 4 y1 3 y2 8 y3 m in P.A.T.Ö P.A.T.Ö thì thì baø baøi toaù toaùn kia cuõng coù coù P.A.T.Ö P.A.T.Ö vaø vaø giaù giaù trò haø haøm muï muïc tieâu cuû cuûa chuù chuùng ng baè baèng ng nhau. 1 0 4 x1 y1 0 1 3 HEÄ HEÄ QUAÛ QUAÛ 1. 1 0 1 2 N x2 y2 1 2 8 0 1 2 5 xj 0; j 1, 2 y3 Ñ ieà ieàu kieä kieän caà caàn vaø vaø ñuû ñeå cho caù caùc baø baøi toaù toaùn ñoái Raø Raøng ng buoä buoäc ñoái ngaãu y j 0 j 1, 3 ngaãu nhau coù coù phö phöông aù aùn toá toái öu laø laø moãi baø baøi toaù toaùn x1 0, y1 y3 2 1 coù coù ít nhaá nhaát moä moät phö phöông aù aùn. n. x2 0, y2 2 y3 5 2 HEÄ HEÄ QUAÛ QUAÛ 2. x1 4, y1 0 3 Ñ ieà ieàu kieä kieän caà caàn vaø vaø ñuû ñeå cho caù caùc baø baøi toaù toaùn ñoái x2 3, y2 0 4 ngaãu nhau khoâng coù coù P.A.T.Ö P.A.T.Ö laølaø moä moät baø baøi toaù toaùn coù coù x1 2 x2 8, y3 0 5 P.A coø coøn baø baøi toaù toaùn kia khoâng coùcoù P.A. ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
ÝØJLÒÙ îæ ÞßH× ÌÑßGÒ OÑ_× ÒÙß]Ë Ì¸-ò Ò¹«§»=² Ý±>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ CAÙ CAÙC ÑÒNH LYÙ LYÙ ÑOÁI NGAÃU CAÙ CAÙC ÑÒNH LYÙ LYÙ ÑOÁI NGAÃU ÑÒNH LYÙ LYÙ 2.(Ñ 2.(ÑÒNH LYÙ LYÙ ÑOÄ LEÄ LEÄCH CH BUØ BUØ YEÁ YEÁU) U) ÑÒNH LYÙLYÙ 3.(Ñ 3.(ÑÒNH LYÙ LYÙ ÑOÄ LEÄ LEÄCH CH BUØ BUØ MAÏ MAÏNH) NH) Ñ ieà ieàu kieä kieän caà caàn vaø vaø ñuû ñeå caë caëp baø baøi toaù toaùn ñoái ngaãu Neá Neáu caëcaëp baø baøi toaù toaùn ñoái ngaãu nhau coù coù P.A.T.Ö P.A.T.Ö. thì thì nhau coùcoù P.A.T.Ö P.A.T.Ö. laø laø trong caë caëp raø raøng ng buoä buoäc ñoái toà toàn taï taïi moä moät caë caëp phö phöông aù aùn sao cho trong caù caùc ngaãu, neá neáu raø raøng ng buoä buoäc naø naøy xaû xaûy ra vôùvôùi daá daáu baá baát caë caëp ño ái ngaãu, neá neáu raø raøng ng buoä buoäc naø naøy xaû xaûy ra vôù vôùi daá daáu ñaúng ng thöù thöùc c ngaë ngaët (> hoaë hoaëc 0 thì Neá thì aij yiopt cj Neáu xjopt = 0 thì Neá thì toà toàn taï taïi aij yiopt cj n , i 1 n i 1 Neá Neáu aij xopt j thì yiopt = 0 bi thì Neá Neáu a ij x opt j bi thì thì toà toàn taï taïi yiopt 0 (> hoaë hoaëc 0 y1 = 2. Töø (3): x3= 6 > 0 y1 + y2 + 3y3 = 1 f D ( y ) 5 0 y 1 1 6 y 2 2 3 y 3 m in Töø (4): x4= 5 > 0 6y1 + 2y2 + y3 = 4 5 y 1 3 y 2 4 y 3 2 y 2 Giaû Giaûi heä heä phö phöông trì trình treân, ta coù coù y1 = 2; y 2 = -23/5; 1 y y 3 y 1 y3 = 6/5. Vaä Vaäy, y, P.A.T.Ö P.A.T.Ö cuû cuûa baø baøi toaù toaùn ñoái ngaãu laø laø 1 2 3 6 y 2 y y 4 yopt= (2, -23/5, 6/5) vaø vaø fD(yopt) = 54. 1 2 3 y 2 0; y 3 0 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
ÝØJLÒÙ îæ ÞßH× ÌÑßGÒ OÑ_× ÒÙß]Ë Ì¸-ò Ò¹«§»=² Ý±>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ AÙP DUÏ DUÏNG NG ÑÒNH LYÙ LYÙ ÑOÁI NGAÃU AÙP DUÏ DUÏNG NG ÑÒNH LYÙ LYÙ ÑOÁI NGAÃU Ví duï duï 2.8. Cho baøbaøi toaù toaùn QHTT f ( x) x1 2 x2 x3 Max 1. Kieå Kieåm tra tröï tröïc tieá tieáp, p, ta thaá thaáy X, Y, vaø vaø T laø laø P.A cuû cuûa baø baøi toaù toaùn. n. Vì Vì Z khoâng thoû thoûa maõn caù caùc raø raøng ng buoä buoäc x1 3x2 x4 5 neân Z khoâng laø laø P.A cuû cuûa baø baøi toaù toaùn. n. x1 x2 3 2. Baø Baøi toaù toaùn ñoái ngaãu 3x1 x3 x4 2 f D ( y) 5 y1 3 y2 2 y3 min x j 0 j 1, 4 y1 y2 3 y3 1 Xeù Xeùt caù caùc vectô sau X = (3, 0, 11, 0), Y = (2, 1, 8, 0), 3 y1 y2 2 Z = (- (-4, 2, 0, 10) vaøvaø T = (1, 2, 1, 2). Vectô naø naøo laø laø í P.A.T.Ö P.A.T.Ö. cuû cuûa baø baøi toaù toaùn? n? y3 1 Caù Caùch ch giaû giaûi. Tr i. y1 y3 0 1. Kieå Kieåm tra caùcaùc vectô coùcoù phaû phaûi laø laø P.A hay khoâng? y1 0; y2 0; y3 0 2. Vieá Vieát baø baøi toaù toaùn ñoái ngaãu, 3. Kieå Kieåm tra caùcaùc P.A coù coù phaû phaûi laø laø P.A.T.Ö P.A.T.Ö.? Ta coù coù 7 caë caëp raø raøng ng buoä buoäc ñoái ngaãu g oân AÙP DUÏ DUÏNG NG ÑÒNH LYÙ LYÙ ÑOÁI NGAÃU AÙP DUÏ DUÏNG NG ÑÒNH LYÙ LYÙ ÑOÁI NGAÃU x1 0 vaøvaø y1 + y2 3y3 -1 (1) x2 0 vaøvaø 3y1 + y2 2 (2) Deã daø daøng kieåm tra vectô X*= (0, 2, 1) thoû ng kieå thoûa caù caùc x3 0 vaøvaø y3 1 (3) raø øng buoääc cuûûa ra ng buo cu ba toabaø øi toaù ùn ñ o ái ngaãu . x4 0 vaøvaø y1 + y3 0 (4) Hôn nö f(X)= 8 neân X laø nöõa, fD(X*)= f(X laø P.A.T.Ö P.A.T.Ö. cuû cuûa C x1 + 3x2 x4 5 vaø vaø y1 0 (5) baø ø i toaù ù n ba toa go c. goá ác. x 1 + x2 3 vaø vaø y2 0 (6) Do Y = (2, 1, 8, 0) laø laø P.A cuû cuûa baø baøi toaù toaùn goá goác vaø vaø -3x1 + x3 + x4 2 vaø vaø y3 0 (7) 3. Kieå Kieåm tra X, Y, T laølaø P.A.T.Ö P.A.T.Ö f(Y)= 8 neân Y cuõng laø f(X) = f(Y)= laø P.A.T.Ö P.A.T.Ö. Giaû Giaû söû X = (3, 0, 11, 0) laø laø P.A.T.Ö P.A.T.Ö cuû cuûa baø baøi toaù toaùn. n. Vôù Vôùi T = (1, 2, 1, 2), ta coù coù f(T)= 4 fmax = 8 eãn Töø (1): x 1 = 3 > 0 y1 + y2 3y3 = -1 Vaä Vaäy T khoâng phaû phaûi laø laø P.A.T.Ö P.A.T.Ö. maø maø T chæ chæ laø laø phö phöông Töø (3): x 3=11 > 0 y3 = 1 aùn cuû cuûa baø baøi toaù toaùn. n. Töø (5): 3 + 0 + 0 + 0 = 3 < 5 y1 = 0 Giaû Giaûi heä heä phö phöông trì ñöôïc X *= (0, 2, 1). trình, ta ñöô y gu AÙP DUÏ DUÏNG NG ÑÒNH LYÙ LYÙ ÑOÁI NGAÃU AÙP DUÏ DUÏNG NG ÑÒNH LYÙ LYÙ ÑOÁI NGAÃU Ví duï duï 2.9. Giaû Giaûi baø baøi toaù toaùn QHTT f ( x) 10 x1 8x2 19 x3 min Ñö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 phuï y 4 0, y5 0, y6 0 theâm 3 aån phuï 2 1 1 x1 6 3 0 2 x2 2 f D ( y) 6 y1 2 y2 5 y3 max N 1 2 5 x3 5 2 3 1 y1 y4 10 xj 0 j 1,3 1 0 2 y2 y5 8 Baø Baøi toaù toaùn ñoái ngaãu f D ( y ) 6 y1 2 y2 5 y3 max 1 2 5 y3 y6 19 2 3 1 y1 10 yj 0 j 1,6 1 0 2 y2 8 1 2 5 y3 19 Ta thaá thaáy baø baøi toaù toaùn cuõng coù coù daï daïng ng chuaå chuaån. n. Söû duï duïng ng thuaä thuaät giaû giaûi ñôn hì hình Ví duï duï 2.10 yj 0 j 1,3 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
ÝØJLÒÙ îæ ÞßH× ÌÑßGÒ OÑ_× ÒÙß]Ë Ì¸-ò Ò¹«§»=² Ý±>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ AÙP DUÏ DUÏNG NG ÑÒNH LYÙ LYÙ ÑOÁI NGAÃU AÙP DUÏ DUÏNG NG ÑÒNH LYÙ LYÙ ÑOÁI NGAÃU HEÄ HEÄ P.A HEÄ HEÄ A ÅN P.A 6 2 5 0 0 0 AÅ N 6 2 5 0 0 0 SOÁ SOÁ SOÁ SOÁ C.B y1 y2 y3 y4 y5 y6 C.B y1 y2 y3 y4 y5 y6 0 y4 10 2 3 1 1 0 0 6 y1 4 1 2 0 3 2 1 2 0 0 y5 8 1 0 2 0 1 0 5 y3 2 0 1 1 1 3 2 3 0 0 y6 19 1 2 5 0 0 0 y6 5 0 5 0 1 3 1 1 7 f x 0 6 2 5 0 0 0 f x 34 0 5 0 3 4 3 0 GHI CHUÙ CHUÙ 6 y1 5 1 3 1 1 0 0 Baø Baøi toaù toaùn coù coù P.A.T.Ö P.A.T.Ö yopt=(4, 0, 2) vaø vaø f(yopt)= 34. í 2 2 2 y5 P.A.T.ÖÖ cuû û a baø øi toaù P.A.T. cu ba toa go la ùn goá ác laø ø 3 3 1 0 3 0 1 0 Tr 2 2 2 0 y6 14 0 1 2 9 2 1 2 0 1 x1 4 b4 x1 7 3 0 7 3 xopt x2 b5 xopt x2 4 0 4 f x 30 0 7 2 3 0 0 5 3 3 x3 6 b6 x3 0 0 0 g oân AÙP DUÏ DUÏNG NG ÑÒNH LYÙ LYÙ ÑOÁI NGAÃU AÙP DUÏ DUÏNG NG ÑÒNH LYÙ LYÙ ÑOÁI NGAÃU Caù Caùchch 2: duø duøng ng ñònh lyù lyù ñoái ngaãu GHI CHUÙ CHUÙ. Chuù Chuùngng ta cuõng coù coù theå theå söû duï duïng ng quy taé taéc x1 0 vaø vaø 2y1 + 3y2 + y 3 10 (1) sau ñaây ñeå tìm P.A.T.Ö P.A.T.Ö cuû cuûa baø baøi toaù toaùn ñoái ngaãu: x2 0 vaø vaø y1 + 2y3 8 (2) y1 1 c1 x3 0 vaø vaø y1 + 2y2 + 5y3 19 (3) y2 2 c2 C yopt 2x1 + x 2 + x3 6 vaø vaø y1 0 (4) 3x1 + 2x 3 2 vaø vaø y2 0 (5) ym cm x1 + 2x 2+ 5x 3 5 vaø vaø y3 0 (6) m Vôù Vôùi caù caùc aå baûn x j (j = 1, 2, ... , m) trong P.A.C.B aån cô baû Ta coù coù P.A.T.Ö P.A.T.Ö cuû cuûa baø toaùn ñoái ngaãu yopt= (4,0,2) baøi toaù ñaàu tieân laä laäp thaø thaønh nh ma traä traän ñôn vò caá caáp m tö töông Töø (3): 4 +2 +2 0 + 5 2 = 14 < 19 x3 = 0. öùng ng vôù vôùi caù caùc j trong baû baûngng cuoá cuoái cuø cuøng. ng. Töø (4): y1 = 4 > 0 2x1 + x2 + x 3 = 6 eãn Trong V í duï duï 2.9, 2.9, aå aån cô baûbaûn ñaàu tieân cuû cuûa baø baøi toaù toaùn Töø (6): y3= 2 > 0 x1 + 2x2 + 5x3 = 5 ñoái ngaãu laø vaø y6 thì laø y4, y 5 vaø thì P.A.T.Ö P.A.T.Ö cuû cuûa baøbaøi toaù toaùn Giaû Giaûi heä heä phö phöông trìtrình, ta coùcoù PA.T.Ö PA.T.Ö cuû cuûa baø baøi toaù toaùn goá goác (ñ(ñoái ngaãu cuû cuûa baø baøi toaù toaùn ñoái ngaãu) laø laø goá goác laø laø x opt = (7/3, 4/3, 0) vaø vaø f(xopt) = 34. X opt = (7/3, 4/3, 0) vaøvaø f(Xopt) = 34. y gu THUAÄ THUAÄT GIAÛ GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU THUAÄ THUAÄT GIAÛ GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU Do Lemke G.E ñeà xuaá xuaát naêm 1954. Ñaây laø laø thuaä thuaät LAÄ LAÄP BAÛ BAÛNG NG ÑÔN HÌNH ÑOÁI NGAÃU giaû giaûi ñôn hì hình ñöô ñöôïc aù aùp duï duïng ng vaø vaøo baø baøi toaù toaùn ñoái Ñu ùng ng Ñu ùng ng ngaãu nhö nhöng ñeå tìm P.A.T.Ö P.A.T.Ö cho baøbaøi toaù toaùn goá goác. c. bi 0, i? j 0, j? P.A.T.Ö P.A.T.Ö Thuaä Thuaät giaû giaûi ñôn hìhình ñoái ngaãu xuaá xuaát phaù phaùt töø töø moä moät Sai Sai phö phöông aù aùn giaû giaû thoû thoûa caù caùc raø raøng ng buoä buoäc chí chính cuû cuûa Ñuùng THUAÄ THUAÄT GIAÛ GIAÛI KEÁ KEÁT THUÙ THUÙC aij N 0, i? baø baøi toaù toaùn (nghieä (nghieäm ñuùng ng Ax = b) nhö nhöng khoâng ÑÔN HÌNH THUAÄ THUAÄT GIAÛ GIAÛI Sai thoaû thoaû ñieà ieàu kieä kieän raø raøng ng buoä buoäc veà veà daá daáu (x 0), nghónghóa laø laø XAÙ XAÙC ÑÒNH PHÖ PHÖÔNG AÙ AÙN MÔÙ MÔÙI BAØ BAØI TOAÙ TOAÙN baû baûngng ñôn hì hình ñaàu tieân khoâng coù coù phaà phaàn töû töû döông Aån ra : Minbi KHOÂNG COÙ COÙ P.A.T.Ö P.A.T.Ö xi trong doødoøng ng muï muïc tieâu (doø (doøng ng cuoá cuoái) i) nhö nhöng laï laïi coù coù bi 0 Aån vaø vaøo : Min phaà phaàn töû töû aâm trong coä coät phö phöông aù aùn. j n. aij 0 aij xj Thuaä Thuaät giaû giaûi naø naøy thö thöôøng ng ñöô ñöôïc aùaùp duï duïng ng khi chö chöa bieá bieát P.A.C.B naø naøo cuû cuûa baø baøi toaù toaùn goá goác nhö nhöng laï laïi coù coù BIEÁ SOÁ SOÁ BÖÔÙC LAË LAËP BIEÁN ÑO ÅI BAÛ BAÛNG NG Ñ ÔN HÌNH saü saün moä moät P.A.C.B cuûcuûa baø baøi toaù toaùn ño ái ngaãu. LAØ LAØ HÖÕU HAÏ HAÏN ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
ÝØJLÒÙ îæ ÞßH× ÌÑßGÒ OÑ_× ÒÙß]Ë Ì¸-ò Ò¹«§»=² Ý±>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ THUAÄ THUAÄT GIAÛ GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU THUAÄ THUAÄT GIAÛ GIAÛI ÑÔN HÌNH Ñ OÁI NGAÃU Ví duï duï 2.10. Giaû Giaûi baø baøi toaù toaùn QHTT trong Ví duïduï 2.9 Heä Heä AÅn P.A 10 8 19 0 0 0 baè baèng ng thuaä thuaät giaû giaûi ñôn hì hình ñoái ngaãu. soá soá C.B x1 x2 x3 x4 x5 x6 Ñöa Ñöa baø baøi toaù toaùn veà veà daï daïngng chí chính taé taéc, c, roà roài sau ñoù nhaân ( (1) cho caùcaùc raø raøng ng buoä buoäc ñaúng ng thöù thöùc, c, ta coù coù 0 x4 6 2 1 1 1 0 0 baø baøi toaù toaùn daï daïng ng chí chính taé taéc nhö nhö sau 0 x5 2 3 0 2 0 1 0 f ( x ) 10 x1 8 x2 19 x3 min 0 x6 5 1 2 5 0 0 1 2 x1 x2 x3 x4 6 f(x) 0 10 8 19 0 0 0 3 x1 2 x3 x5 2 10 x1 3 1 ½ ½ ½ 0 0 í x1 2 x2 5 x3 x6 5 0 x5 7 0 3/2 ½ 3/2 1 0 Tr xj 0, j 1, 6 0 x6 2 0 3/2 9/2 ½ 0 1 Xuaá Xuaát phaù phaùt töø töø phö phöông aù aùn giaû giaû X = (0,0,0, (0,0,0,6, 6,2, 2,5). f(x) 30 0 3 14 5 0 0 Ta coù coù baû baûng ng ñôn hì hình ñoái ngaãu nhö nhö sau g oân THUAÄ THUAÄT GIAÛ GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU THUAÄ THUAÄT GIAÛ GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU Heä Heä AÅn P.A 10 8 19 0 0 0 GHI CHUÙ CHUÙ. Ñoái vôù vôùi thuaä thuaät giaû giaûi ñôn hì hình ñoái ngaãu, soá soá C.B x1 x2 x3 x4 x5 x6 ñeå tìm P.A.T.Ö P.A.T.Ö cuû cuûa baø toaùn ñoái ngaãu Yopt, ta coù baøi toaù coù bieå bieåu thöù thöùc c sau y1 c1 10 x1 7/3 1 0 2 2/3 0 1/3 1 y2 c2 0 x5 5 0 0 4 2 1 1 2 C yopt 8 x3 4/3 0 1 3 1/3 0 2/3 ym cm f(x) 34 0 0 23 4 0 2 m Trong Ví duï duï 2.10, 2.10, aåaån cô baûbaûn ñaàu tieân cuû cuûa baø baøi toaù toaùn ñoái ngaãu laø vaø x 6 thì laø x4, x 5 vaø thì Vaä Vaäy, y, P.A.T.Ö P.A.T.Ö cuû cuûa baø baøi toaù toaùn laø laø x opt = (7/3, 4/3, 0) y1 c4 y1 ( 4) 0 4 vaø f(xopt) = 34. vaø 4 eãn yopt y2 5 c5 y2 0 0 0 y3 6 c6 y3 ( 2) 0 2 P.A.T.Ö P.A.T.Ö cuû cuûa baø baøi toaù laø Yopt = (4, 0, 2) vaø toaùn ñoái ngaãu laø vaø f*(Yopt) = 34. y gu THUAÄ THUAÄT GIAÛ GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU THUAÄ THUAÄT GIAÛ GIAÛI ÑÔN HÌNH ÑOÁI NGAÃU Ví duï duï 2.11. Heä Heä AÅn P.A 2 4 1 1 2 0 0 Duø Duøng ng thuaä thuaät giaû giaûi ñôn hì hình ñoái ngaãu ñeå giaû giaûi baø baøi soá soá C.B x1 x2 x3 x4 x5 x6 x7 toaù toaùn quy hoaï hoaïch ch tuyeá tuyeán tí tính sau ñaây 2 x 1 2 1 2 0 0 2 0 0 f ( x) 2 x1 4 x2 x3 x4 2 x5 Min 1 x 4 4 0 4 1 1 1 0 0 0 x6 2 0 0 2 0 1 1 0 N x1 2 x2 2 x5 2 4 x2 x3 x4 x5 4 0 x7 6 0 1 1 0 4 0 1 2 x3 x5 x6 2 f(x) 0 0 4 2 0 5 0 0 Do a4j 0, x2 x3 4 x5 x7 6 2 x1 6 1 10 2 2 0 0 0 j = 1,..., 7 1 x5 4 0 4 1 1 1 0 0 neân baø baøi xj 0, j 1, 7 toaù toaùn treân 0 x6 6 0 4 1 1 0 1 0 khoâng coù coù Xuaá Xuaát phaù phaùt töø töø phö phöông aù aùn giaû giaû X = (0, 0, 0, 6, 2, 5) 0 x 7 10 0 17 5 4 0 0 1 P.A.T.Ö P.A.T.Ö. Ta coù coù baû baûng ng ñôn hìhình ñoái ngaãu f(x) 20 0 24 7 5 0 0 0 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
ÝØJLÒÙ îæ ÞßH× ÌÑßGÒ OÑ_× ÒÙß]Ë Ì¸-ò Ò¹«§»=² Ý±>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ MOÄ MOÄT SOÁ SOÁ ÖÙNG NG DUÏ DUÏNG NG CUÛ CUÛA LYÙ LYÙ THUYEÁ THUYEÁT MOÄ MOÄT SOÁ SOÁ ÖÙNG NG DUÏ DUÏNG NG CUÛ CUÛA LYÙ LYÙ THUYEÁ THUYEÁT ÑOÁI NGAÃU TRONG BAØ BAØI TOAÙ TOAÙN QHTT ÑOÁI NGAÃU TRONG BAØBAØI TOAÙ TOAÙN QHTT Ví duï duï 2.12. 1. TÌM PHÖ PHÖÔNG AÙAÙN TOÁ TOÁI ÖU MÔÙ MÔÙI KHI COÙ COÙ a) Duø Duøng ng thuaä thuaät giaû giaûi ñôn hì hình ñoái ngaãu ñeå giaû giaûi baø baøi THEÂM RAØ RAØNG NG BUOÄ BUOÄC VAØ VAØO BAØ BAØI TOAÙ TOAÙN (XEM) toaù toaùn quy hoaï hoaïch ch tuyeá tuyeán tí tính sau ñaây f ( x) 15 x1 12 x2 10 x3 Min 2. TÌM NGHIEÄ NGHIEÄM KHOÂNG AÂM CUÛ CUÛA HEÄ HEÄ 3x1 4 x2 2 x3 160 PHÖ PHÖÔNG TRÌNH TUYEÁ TUYEÁN TÍ TÍNH BAÈ BAÈNG NG THUAÄ THUAÄT x1 2 x2 3x3 140 GIAÛ GIAÛI ÑÔN HÌNH MÔÛ MÔÛ ROÄ ROÄNG NG (XEM) í xj 0, j 1, 3 3. YÙ NGHÓ NGHÓA KINH TEÁ TEÁ CUÛ CUÛA BAØ BAØI TOAÙ TOAÙN QUY Tr b) Neá Neáu theâm moä moät raø raøng ng buoä buoäc nö nöõa x 1 + x2 + x 3 60 HOAÏ HOAÏCH CH TUYEÁ TUYEÁN TÍ TÍNH ÑOÁI NGAÃU (XEM) vaø vaøo baø baøi toaù toaùn treân, tì tìm phö phöông aù aùn toá toái öu cuû cuûa baø baøi toaù toaùn môù môùi. i. g oân MOÄ MOÄT SOÁ SOÁ ÖÙNG NG DUÏ DUÏNG NG CUÛ CUÛA LYÙ LYÙ THUYEÁ THUYEÁT MOÄ MOÄT SOÁ SOÁ ÖÙNG NG DUÏ DUÏNG NG LYÙ LYÙ THUYEÁ THUYEÁT ÑOÁI NGAÃU ÑOÁI NGAÃU TRONG BAØ BAØI TOAÙ TOAÙN QHTT Heä Heä AÅn P.A 15 12 10 0 0 Soá Soá C.B x1 x2 x3 x4 x5 Ñöa Ñöa baøbaøi toaù toaùn veà veà daï daïngng chí chính taé taéc, c, roà roài sau ñoù nhaân ( (1) cho caù caùc raø raøng ng buoä buoäc ñaúng ng thöù thöùc, c, ta coù coù 0 x4 160 3 4 2 1 0 baø baøi toaù toaùn daï daïng ng chí chính taé taéc nhö nhö sau 0 x5 140 1 2 3 0 1 C f(x) 0 15 12 10 0 0 f ( x) 15 x1 12 x2 10 x3 Min 12 x2 40 ¾ 1 ½ ¼ 0 3 x1 4 x2 2 x3 x4 160 0 x5 60 ½ 0 2 ½ 1 x1 2 x2 3 x3 x5 140 f(x) 480 6 0 4 3 0 12 x2 25 7/8 1 0 3/8 ¼ eãn xj 0, j 1,5 a) Xuaá 10 x3 30 ¼ 0 1 ¼ ½ Xuaát phaù phaùt töø töø phö phöông aù aùn giaû giaû X = (0, 0, 0, 160, 140. Ta coù coù baû baûng ng ñôn hì hình ñoái ngaãu f(x) 600 7 0 0 2 2 P.A.T.Ö P.A.T.Ö laø vaø f(xopt) = 600. laø xopt = (0, 25, 30) vaø y gu MOÄ MOÄT SOÁ SOÁ ÖÙNG NG DUÏ DUÏNG NG CUÛ CUÛA LYÙLYÙ THUYEÁ THUYEÁT MOÄ MOÄT SOÁ SOÁ ÖÙNG NG DUÏ DUÏNG NG LYÙ LYÙ THUYEÁ THUYEÁT ÑOÁI NGAÃU ÑOÁI NGAÃU TRONG BAØ BAØI TOAÙ TOAÙN QHTT Heä A Ån Heä P.A 15 12 10 0 0 0 b) Do xopt = (0, 25, 30) khoâng thoû thoûa raø raøng ng buoä buoäc x1 soá soá C.B x1 x2 x3 x4 x5 x6 + x2 + x3 60 neân xopt khoâng phaû phaûi laø laø phö phöông aù aùn cuû cuûa baøbaøi toaù toaùn môù môùi. i. Ñeå xöû lyù lyù raø raøng ng buoä buoäc môù môùi naø naøy, y, 12 x2 25 7/8 1 0 3/8 ¼ 0 ta ñöa ñöa raøraøng ng buoä buoäc baábaát ñaúngng thöù thöùc veà veà raø raøng ng buoä buoäc 10 x3 30 ¼ 0 1 ¼ ½ 0 ñaúng ng thöù thöùc baè baèng ng caùcaùch ch theâm aå aån phuï phuï x 6 0, ta N ñöô ñöôïc x1 x 2 x3 + x6 = 60. 0 x6 60 1 1 1 0 0 1 Söû duï duïngng baû baûng ng cuoá cuoái cuø cuøng ng trong caâu a) vaø vaø ñöa ñöa f(x) 600 7 0 0 2 2 0 raø raøng ng buoä buoäc môù môùi x1 x2 x3 + x6 = 60 vaø vaøo baû baûng ng 12 x2 25 7/8 1 0 3/8 ¼ 0 treân. LöLöu yùyù aån x6 laø laø aån cô baû baûn trong baø baøi toaù toaùn môù coøn x4 vaø môùi,i, coø vaø x5 laø laø aån cô baû baûn trong baø baøi toaù toaùn cuõ 10 x3 30 ¼ 0 1 ¼ ½ 0 neân trong ma traä traän heä heä soá soá cuû cuûa baøbaøi toaù toaùn môù môùi ta 0 x6 5 3/8 0 0 1/8 ¼ 1 coä coäng ng doødoøng ng 1 vaø vaø doø doøng ng 2 vaøvaøo doødoøng ng 3 ñeå vectô f(x) 600 7 0 0 2 2 0 coä coät öùng ng vôù vôùi x4 vaø vaø x5 laø laø caù caùc vectô ñôn vò. ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
ÝØJLÒÙ îæ ÞßH× ÌÑßGÒ OÑ_× ÒÙß]Ë Ì¸-ò Ò¹«§»=² Ý±>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ MOÄ MOÄT SOÁ SOÁ ÖÙNG NG DUÏ DUÏNG LYÙ LYÙ THUYEÁ THUYEÁT ÑOÁI NGAÃU TÌM NGHIEÄ NGHIEÄM KHOÂNG AÂM CUÛ CUÛA Heä Heä AÅn 15 12 10 0 0 0 HEÄ HEÄ PHÖ PHÖÔNG TRÌNH TUYEÁ TUYEÁN TÍ TÍNH P.A Tìm nghieä nghieäm khoâng aâm cuû cuûa heä heä phö phöông trì trình soá soá C.B x1 x2 x3 x4 x5 x6 tuyeá tuyeán tí tính AX = b, X 0 (1), trong ñoù A laø laø ma 12 x2 20 ½ 1 0 ½ 0 1 traä traän m n, b m coù coù theå theå quy veà veà giaû giaûi baø baøi toaù toaùn quy 10 x3 40 ½ 0 1 ½ 0 2 m hoaï hoaïch ch tuyeá tuyeán tí tính f x M x j g min 0 x5 20 3/2 0 0 ½ 1 4 j 1 Xg 4 AX b 2 f(x) 640 0 0 1 0 8 X 0, X g 0, M 0 P.A.T.Ö P.A.T.Ö laø laø x /opt = (0, 20, 40) vaø vaø f(x/opt) = 640. Baø Baøi toaù toaùn (2) luoân luoân coù coù P.A.T.Ö P.A.T.Ö vì (0,b) laø laø í moä moät P.A vaø vaø haø haøm muï muïc tieâu bò chaë chaën [f(x) 0]. Giaû Giaû söû P.A.T.Ö P.A.T.Ö cuû cuûa baø baøi toaù toaùn treân laø laø (xopt, x gopt), Tr neá neáu xgopt = 0, j thìthì xopt laø laø nghieä nghieäm cuû cuûa baø baøi toaù toaùn (1). Ngö Ngöôïc laï laïi neá neáu toà toàn taï taïi xgj 0 thìthì baø baøi toaù toaùn (1) voâ nghieä nghieäm. m. g oân TÌM NGHIEÄ NGHIEÄM KHOÂNG AÂM CUÛ CUÛA HEÄ HEÄ PHÖ PHÖÔNG TRÌNH TUYEÁ TUYEÁN TÍ TÍNH YÙ NGHÓ NGHÓA KINH TEÁ TEÁ CUÛ CUÛA BAØ BAØI TOAÙ TOAÙN Ñ OÁI NGAÃU Ví duï duï 2.1.T 2.1.Tìm nghieä nghieäm khoâng aâm cuû cuûa heä heä phö phöông Xeù Xeùt baø baøi toaù toaùn goá goác laø laø baø baøi toaù toaùn khaå khaåu phaà phaàn thöù thöùc aên trì trình tuyeá tuyeán tí tính 2 x1 3 x2 x3 7 Thöù Thöùc aên Möùc x1 2 x2 4 x3 9 Chaá Chaát dinh 1 2 ... j ... n dinh dödöôõng döôõng (%) 3 x1 x2 2 x3 4 toá toái thieå thieåu C Ta coù coù theå theå quy baø baøi toaù toaùn treân veà veà baø baøi toaù toaùn QHTT 1 a11 a12 ... a1j ... a1n b1 f ( x) M x4 x5 x6 Min 2 a21 a22 ... a2j ... a2n b2 2 x1 3 x2 x3 x4 7 ... ... ... ... ... ... ... ... x1 2 x2 4 x3 x5 9 i ai1 ai2 ... aij ... ain bi 3 x1 x2 2 x3 x6 4 ... ... ... ... ... ... ... ... eãn xj 0, j 1, 6 m am1 am2 ... amj ... amn bm Giaû Giaûi baø baøi toaù toaùn treân, ta ñöô ñöôïc P.A.T. laø laø (xopt, xgopt) = (3, 1, 2, 0, 0, 0). Vaä Vaäy nghieä nghieäm khoâng aâm cuû cuûa heä heä Giaù Giaù moä moät ñôn c1 c2 ... cj ... cn phö phöông trìtrình tuyeá tuyeán tí tính treân laø laø x = (3, 1, 2). vò thöù thöùc aên y gu YÙ NGHÓ NGHÓA KINH TEÁ TEÁ CUÛ CUÛA BAØ BAØI TOAÙ TOAÙN ÑOÁI NGAÃU YÙ NGHÓ NGHÓA KINH TEÁ TEÁ CUÛ CUÛA BAØ BAØI TOAÙ TOAÙN Ñ OÁI NGAÃU Goï Goïi xj (j = 1, 2, ..., n) laø laø soá soá ñôn vò thöù thöùc aên trong Goï Goïi yi laølaø giaù giaù baù baùn moä moät vieân thuoáthuoác boå boå coù coù chöù chöùa moãi böû böûa, a, ta coù coù moâ hì hình baø baøi toaù toaùn QHTT nhö nhö sau chaá chaát dinh dö döôõng i (i = 1, 2, ..., m). f x c1x1 c2 x2 cn xn min Ngö Ngöôøi chaên nuoâi seõ phaû phaûi löïlöïa choï choïn:n: ai1 x1 ai 2 x2 ain xn bi , i 1, m Mua thuoáthuoác boå boå, neá neáu a1jy1 + a2jy2 +... + anjyn < cj. Vì giaù giaù thuoá thuoác boå boå reû reû hôn vaøvaø luù naøy xj = 0 (ñ luùc naø (ñònh lyù lyù N ñoä leä leäch ch buøbuø yeá yeáu). xj 0, j 1, n u). Baø Baøi toaù toaùn ñoái ngaãu Mua thöù thöùc aên, theo ñònh lyù lyù ñoä leä leäch ch buø buø yeá yeáu, u, fD y b1 y1 b2 y2 bm ym max neá neáu yi > 0 thìthì ai1x1 + ai2x2 + + ainxn = bi, a1 j y1 a2 j y2 amj ym cj , j 1, n Nghó Nghóa laø laø, neá neáu giaù giaù moä moät vieân thuoá thuoác boå boå khaù khaù cao thì thì yi 0, i 1, m ngö ngöôøi chaên nuoâi seõ mua caù caùc loaï loaïi thöù thöùc aên sao cho thoaû thoaû nhu caà caàu toátoái thieå thieåu cuû cuûa chaá chaát dinh dö döôõng. Chaá Chaát dinh dö döôõng thay theá theá: nhaø nhaø saû saûn xuaá xuaát thuoá thuoác Vaä Vaäy, y, khi phaân tí tích caë caëp baø baøi toaù toaùn ñoái ngaãu nhau boå boå töông öùng ng vôù vôùi caù caùc chaá chaát dinh dö döôõng treân. chí chính laølaø phaân tí tích tí tính T.Ö T.Ö cuû cuûa töø töøng ng baø baøi toaù toaùn. n. ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
ÝØJLÒÙ îæ ÞßH× ÌÑßGÒ OÑ_× ÒÙß]Ë Ì¸-ò Ò¹«§»=² Ý±>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ BAØI TAÄP CHÖÔNG 2 LAÄP BAØI TOAÙN ÑOÁI NGAÃU [1] Vieát baøi toaùn ñoái ngaãu vaø chæ ra caùc caëp raøng buoäc ñoái ngaãu cuûa caùc baøi toaùn quy hoaïch tuyeán tính sau ñaây f ( x) 4 x1 4 x2 3 x3 2 x4 min x1 2 x2 x3 x4 1 a) 2 x1 x2 3 x3 x4 8 í x1 5 x2 x3 3 x4 4 Tr x1 0, x3 0, x4 0 f ( x) 2 x1 3 x2 4 x3 5 x4 max x1 x2 2 x3 2 x4 10 g b) x1 2 x2 x3 x4 8 x1 x2 2 x3 x4 9 oân x2 0, x3 0, x4 0 [2] Chöùng minh baøi toaùn quy hoaïch tuyeán tính sau ñaây truøng vôùi baøi toaùn ñoái ngaãu cuûa noù (Baøi toaùn töï ñoái ngaãu). f ( x) x1 x2 x3 min C x2 x3 1 x1 x3 1 x1 x2 1 eãn x1 0, x2 0 x3 0, SÖÛ DUÏNG ÑÒNH LYÙ ÑOÁI NGAÃU [3] Cho baøi toaùn quy hoaïch tuyeán tính f ( x) 2 x1 4 x 2 x3 x4 max y x1 3x 2 x4 1 5x 2 2x4 3 gu x2 4 x3 x4 3 xj 0 j 1,4 a) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn treân. b) Giaûi baøi toaùn goác, suy ra lôøi giaûi cuûa baøi toaùn ñoái ngaãu. N 3 1 xopt 1, 0, , 0 yopt 2, 0, 4 4 Ñs: b ) 11 11 f xopt f D yopt 4 4 ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
ÝØJLÒÙ îæ ÞßH× ÌÑßGÒ OÑ_× ÒÙß]Ë Ì¸-ò Ò¹«§»=² Ý±>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ [4] Cho baøi toaùn quy hoaïch tuyeán tính f ( x ) 12 x1 27 x 2 6 x3 min 2 x1 3 x2 2 x3 12 x1 3 x2 x3 6 6 x1 9 x2 2 x3 24 xj 0 j 1,3 a) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn treân. b) Giaûi baøi toaùn ñoái ngaãu, suy ra lôøi giaûi cuûa baøi toaùn goác. í 3 3 Tr yopt , 0, xopt 3, 0, 3 Ñs: b ) 2 2 f xopt 54 f D yopt 54 [5] Cho baøi toaùn quy hoaïch tuyeán tính g f ( x ) 5x1 9 x2 15x3 7 x4 6 x5 min x1 3 x2 x3 x4 x5 1 oân 4 x1 x3 2 x4 x5 4 x1 x2 x3 2 x5 1 xj 0 j 2,5 C a) Vieát baøi toaùn ñoái ngaãu cuûa baøi toaùn treân. b) Phaân tích tính chaát (phöông aùn cöïc bieân, suy bieán hay khoâng suy bieán) cuûa vectô X = (0, 1, 0, 2, 0). c) Cho bieát f(xopt) = 5. Tìm phöông aùn toái öu cuûa baøi toaùn ñoái ngaãu. eãn Ñs: b) X = (0, 1, 0, 2, 0) khoâng laø P.A.C.B. X laø P.A.T.Ö. 1 1 yopt 3 y3 , 2 y3 , y3 c) 3 6 y 0 y3 9 [6] Cho baøi toaùn quy hoaïch tuyeán tính gu f ( x) 3 x1 7 x2 x3 2 x4 max 2 x1 3x2 x3 2 x4 30 2 x1 2 x2 3 x3 60 N 2 x1 2 x2 3 x3 4 x4 32 xj 0 j 1, 4 Cho caùc vectô: X = (-1, 2, 3, 4); Y = (0,2,1,3); Z = (0, 0, 0, 8), T = (14, 0, 0, 1); S = (18, 2, 0, 0) Trong caùc vectô treân, vectô naøo laø phöông aùn toái öu cuûa baøi toaùn? Haõy giaûi thích. Ñs: X, Y khoâng phaûi laø phöông aùn. T, S laø phöông aùn toái öu. ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com
ÝØJLÒÙ îæ ÞßH× ÌÑßGÒ OÑ_× ÒÙß]Ë Ì¸-ò Ò¹«§»=² Ý±>²¹ Ì®3 ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ ÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁÁ PHÖÔNG PHAÙP ÑÔN HÌNH ÑOÁI NGAÃU [7] Duøng phöông phaùp ñôn hình ñoái ngaãu giaûi caùc baøi toaùn quy hoaïch tuyeán tính sau ñaây vaø töø lôøi giaûi cuûa baøi toaùn goác suy ra lôøi giaûi cuûa baøi toaùn ñoái ngaãu f ( x) x1 3 x2 x3 2 x4 min x1 x2 2 x3 2 x4 10 a) x1 2 x2 x3 x4 8 x1 x2 x3 x4 9 x1 0, x2 0, x3 0, x4 0 í xopt 26, 17, 0, 0 yopt 0, 4, 5, 0 Ñs: Tr f xopt 77 f D yopt 77 f ( x) 2 x1 x2 6 x3 3 x4 max g x1 x2 1 b) x2 x3 4 oân x2 x4 2 x1 0, x2 0, x3 0, x4 0 xopt 3, 4, 0, 2 yopt 2, 6, 3 Ñs: ; C f xopt 16 f D yopt 16 y eãn gu N ¸¬¬°æññ²½¬®·ò½±ò½½ PDF created with pdfFactory Pro trial version www.pdffactory.com

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.