Giáo trình cho ngành tin học và công nghệ thông tin

pdf

239 trang vanle 2080

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình cho ngành tin học và công nghệ thông tin", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

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

giao_trinh_cho_nganh_tin_hoc_va_cong_nghe_thong_tin.pdf

Nội dung text: Giáo trình cho ngành tin học và công nghệ thông tin

B GIÁO D C VÀ ðÀO T O TR ƯNG ð I H C NƠNG NGHI P HÀ N I PGS. TS. NGUY N H I THANH VN TRÙ H C Giáo trình cho ngành Tin h c và Cơng ngh thơng tin Hà N i −−− 2008
MC L C Trang LI NĨI ð U 7 CH ƯƠ NG I. M ð U 9 1. Gi i thi u v V n trù h c / Khoa h c qu n lí 9 1.1. Vai trị c a V n trù h c 9 1.2. Các b ưc áp d ng V n trù h c 10 1.3. Quá trình phát tri n c a V n trù h c 11 2. Các ng d ng và ph ươ ng pháp đnh l ưng c ơ b n c a V n trù h c 12 2.1. M t s ng d ng 12 2.2. Các ph ươ ng pháp đnh l ưng 14 2.3. H thơng tin qu n lí 14 CH ƯƠ NG II. M T S MƠ HÌNH VÀ PH ƯƠ NG PHÁP T I ƯU 16 1. Mơ hình quy ho ch tuy n tính 16 1.1. Phát bi u mơ hình quy ho ch tuy n tính 16 1.2. Ph ươ ng pháp đơ n hình gi i BTQHTT d ng chính t c 19 1.3. Ph ươ ng pháp đơ n hình hai pha gi i BTQHTT dng t ng quát 23 1.4. Ph ươ ng pháp c t Gomory gi i BTQHTT nguyên 29 1.5. M t s ng d ng c a ph ươ ng pháp đơ n hình 33 2. Mơ hình quy ho ch tuy n tính đa m c tiêu 35 2.1. Các khái ni m c ơ b n 35 2.2. Ph ươ ng pháp t ng quát gi i BTQHTT đa m c tiêu 37 2.3. Ph ươ ng pháp tho d ng m t ươ ng tác gi i BTQHTT đa m c tiêu 39 2.4. Mt ng d ng c a mơ hình quy ho ch tuy n tính đa m c tiêu 44 3. Mơ hình t i ưu phi tuy n đơn và đa m c tiêu 45 3.1. M t s khái ni m c ơ b n 45 3.2. M t s ph ươ ng pháp gi i bài tốn t i ưu phi tuy n đơ n m c tiêu và ng d ng 47 3.3. Mt s ph ương pháp gi i bài tốn t i ưu phi tuy n đa m c tiêu và ng d ng 51 Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 2
BÀI T P CH ƯƠ NG II 54 CH ƯƠ NG III. CÁC MƠ HÌNH M NG 57 1. Mơ hình m ng v n t i 57 1.1. Phát bi u bài tốn v n t i 57 1.2. T o ph ươ ng án v n t i xu t phát 58 1.3. Ph ươ ng pháp phân ph i gi i bài tốn v n t i 60 1.4. Ph ươ ng pháp phân ph i c i biên gi i bài tốn v n t i 62 2. Mơ hình m ng PERT 66 2.1. Các khái ni m c ơ b n v PERT 66 2.2. S ơ đ PERT v i s li u ng u nhiên 71 2.3. ðiu ch nh d án khi k ho ch m t s ho t đ ng b phá v 73 2.4. Tính th i gian rút g n t i ưu b ng ph ươ ng pháp đơ n hình 74 2.5. Áp d ng m ng PERT trong phân tích chi phí và qu n lí tài chính d án 75 3. M t s mơ hình m ng khác 77 3.1. Bài tốn cây khung t i thi u 77 3.2. Bài tốn tìm đưng đi ng n nh t và quy ho ch đ ng 79 3.3. Mơ hình m ng trung chuy n hàng 86 3.4. Bài tốn tìm lu ng c c đ i 88 BÀI T P CH ƯƠ NG III 90 CH ƯƠ NG IV. GI I THI U LÍ THUY T MƠ PH NG VÀ MƠ HÌNH HÀNG CH 96 1. M c đích và các cơng c c a mơ ph ng 96 1.1. Khái ni m v mơ ph ng ng u nhiên 96 1.2. Các cơng c ch y u c a mơ ph ng 97 1.3. Mơ ph ng m t s phân ph i xác su t 98 2. Áp d ng mơ ph ng ng u nhiên 101 2.1. Vai trị c a ph ươ ng pháp mơ ph ng 101 2.2. Các b ưc c n ti n hành khi áp d ng mơ ph ng 102 2.3. M t s ví d v áp d ng ph ươ ng pháp mơ ph ng 102 3. M t s v n đ v mơ hình hàng ch 112 3.1. M t s y u t c ơ b n c a h th ng hàng ch 112
3.2. Các ch s c n kh o sát 115 3.3. Tính tốn các ch s 116 3.4. Áp d ng mơ ph ng cho m t s h th ng hàng ch 118 BÀI T P CH ƯƠ NG IV 127 CH ƯƠ NG V. PHÂN TÍCH MARKOV VÀ NG D NG 131 1. Các khái ni m c ơ b n v xích Markov 131 1.1. M t s đ nh ngh ĩa 131 1.2. Ma tr n xác su t chuy n tr ng thái và phân ph i d ng 132 1.3. Các tính ch t và đnh lí 137 2. M t s ng d ng c a phân tích Markov 138 2.1. Tìm cân b ng th ph n 138 2.2. Chính sách thay th v t t ư thi t b 138 2.3. Phân tích Markov trong d báo th t thu cho các h p đ ng th c hi n tr ưc 140 2.4. Tìm phân ph i gi i h n cho m t h th ng kĩ thu t 142 2.5. 2.5. Mt ng d ng c a quá trình sinh −t cho h th ng hàngch 147 3. Mơ ph ng xích Markov 149 3.1. Mơ ph ng xích Markov th i gian r i r c 149 3.2. Mơ ph ng xích Markov th i gian liên t c 151 BÀI T P CH ƯƠ NG V 152 CH ƯƠ NG VI. M T S MƠ HÌNH RA QUY T ð NH VÀ NG DNG 158 1. Ra quy t đ nh trong mơi tr ưng b t đ nh 158 1.1. M t s khái ni m c ơ b n 158 1.2. Ra quy t đ nh trong mơi tr ưng b t đ nh nghiêm ng t 160 1.3. Ra quy t đ nh trong mơi tr ưng r i ro 163 2. Phân tích quy t đ nh Bayes 167 2.1. Phân tích quy t đ nh Bayes d a trên xác su t tiên nghi m 167 2.2. Phân tích quy t đ nh Bayes d a trên xác su t h u nghi m 167 3. Cây quy t đ nh và các bài tốn quy t đ nh nhi u giai đon 169 3.1. Bài tốn quy t đ nh nhi u giai đon 169 3.2. Phân tích Bayes s d ng cây quy t đ nh 171 4. Ra quy t đ nh d a trên tiêu chu n kì v ng th a d ng t i đa 174 Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 4
4.1. Khái ni m hàm th a d ng 174 4.2. Tiêu chu n kì v ng th a d ng t i đa 175 5. Lí thuy t trị ch ơi và ng d ng 179 5.1. M t s khái ni m c ơ b n c a lí thuy t trị ch ơi 179 5.2. Trị ch ơi hai ng ưi – t ng khơng v i chi n l ưc thu n nh t 181 5.3. Trị ch ơi hai ng ưi – t ng khơng v i chi n l ưc h n h p 182 5.4. L i gi i b ng đ th cho các trị chơi c 2 ×N ho c M×2 186 5.5. Gi i thi u v trị ch ơi nhi u ng ưi 188 BÀI T P CH ƯƠ NG VI 190 CH ƯƠ NG VII. CÁC MƠ HÌNH QU N LÍ HÀNG D TR 193 1. Các khái ni m c ơ b n 193 1.1. Các ch c n ăng c a vi c d tr hàng 193 1.2. H th ng qu n lí hàng d tr theo phân lo i giá tr ABC 193 1.3. Mơ hình qu n lí hàng d tr t ng quát 194 2. M t s mơ hình t t đ nh trong qu n lí hàng d tr 196 2.1. Mơ hình t ĩnh Wilson v i m t m t hàng 196 2.2. Mơ hình t ĩnh m t m t hàng v i d tr đ m 199 2.3. Mơ hình t ĩnh m t m t hàng v i giá chi t kh u 200 2.4. Mơ hình t ĩnh nhi u m t hàng v i di n tích kho h n ch 202 2.5. Mơ hình đng m t m t hàng N chu kì 204 3. Mơ hình l p k ho ch s n xu t N chu kì 207 3.1. Mơ hình l p k ho ch khơng cho phép n hàng 208 3.2. Mơ hình l p k ho ch cho phép n hàng 209 4. M t s mơ hình xác su t trong qu n lí hàng d tr 210 4.1. Mơ hình xác su t v i ch đ báo cáo theo dõi th ưng xuyên 210 4.2. Mơ hình xác su t m t chu kì 213 4.3. Mơ hình xác su t nhi u chu kì 218 BÀI T P CH ƯƠ NG VII 224 PH N PH L C 229 TÀI LI U THAM KH O 234
LI NĨI ð U Vn trù h c (Operations Research) đưc xem là m t cơng c đ nh l ưng n n t ng ca Khoa h c qu n lí mà trong đĩ các ph ươ ng pháp và kĩ thu t c a Tốn h c và các cơng c tính tốn, l ưu tr và x lí d li u c a Tin h c đưc áp d ng đ mơ hình hĩa, phân tích và tìm ra l i gi i cho các bài tốn quy t đ nh, nh m h tr b máy qu n lí đư a ra các quy t đ nh h p lí nh t. Trên th gi i vi c nghiên c u và ng d ng V n trù hc ngày càng phát tri n sâu r ng v i nhi u t p chí chuyên ngành n i ti ng, mơn V n trù h c đưc gi ng d y v i th i l ưng khá l n bao g m nhi u n i dung phong phú và cp thi t trong nhi u ch ươ ng trình đào t o đ i h c và cao h c. Hi n nay, nh ng mơn h c trang b ki n th c c ơ s v kinh t - qu n lí nĩi chung và các ph ươ ng pháp tốn - tin ng d ng trong mơ hình hĩa và phân tích các bài tốn quy t đ nh nĩi riêng đưc đưa vào gi ng d y trong các ch ươ ng trình đào t o đ i h c trong và ngồi n ưc. ð i v i sinh viên các ngành Tin h c, Cơng ngh thơng tin và Tốn - Tin ng d ng, kh i ki n th c v kinh t - qu n lí là th c s c n thi t cho các cươ ng v làm vi c sau này, đc bi t là c ươ ng v CIO (Chief Information Officer - Giám đc Thơng tin). Trong ch ươ ng trình đào t o ngành Tin h c c a Khoa Cơng ngh thơng tin, Tr ưng ð i h c Nơng nghi p Hà N i, kh i ki n th c trên bao g m T i ưu hĩa, Phân tích s li u, Qu n tr h c, Các ph ươ ng pháp tốn kinh t và V n trù hc. Giáo trình “V n trù h c” v i th i l ưng 60 ti t đưc biên so n l n đ u nh m tr ưc h t ph c v vi c d y và h c mơn h c này cho sinh viên n ăm th ba ho c n ăm th t ư ngành Tin h c. Hi v ng r ng, sau khi ra tr ưng các kĩ sư Tin h c s áp d ng và tri n khai các ph ươ ng pháp v n trù h c đưc m t cách r ng rãi v i nhi u hi u qu thi t thc trong vi c xây d ng các h th ng thơng tin qu n lí và các ph n m m tính tốn cho các bài tốn qu n lí, qu n tr kinh doanh và kinh t - cơng ngh khác. Qua giáo trình này, sinh viên c n n m đưc m t s mơ hình v n trù h c c ơ b n, bi t cách v n d ng các ph ươ ng pháp và kĩ thu t tốn h c, các quy trình tính tốn khoa h c thích h p đ phân tích và x lí các mơ hình đĩ. Các ch đ trong giáo trình bao g m: M t s mơ hình t i ưu (Optimization Model) nh ư các mơ hình quy ho ch tuy n tính c ũng nh ư phi tuy n đơn và đa m c tiêu đưc đ c p t i trong Ch ươ ng II. Ch ươ ng III gi i thi u v các mơ hình m ng (Network Model) v i các bài tốn v m ng vn t i, m ng PERT, v quy ho ch đ ng áp d ng trong tìm đưng đi ng n nh t và bài tốn tìm lu ng c c đ i. M t s ng d ng c a mơ hình hàng ch (Waiting Line Model) Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 6
và mơ ph ng ng u nhiên (Stochastic Simulation) đưc trình bày trong Ch ươ ng IV. Ch ươ ng V gi i thi u các khái ni m c ơ b n và ng d ng c a xích Markov (Markov Chain). Ch ươ ng VI là các ki n th c c ơ s c a lí thuy t quy t đnh (Decision Theory) nh ư các quy t c ra quy t đ nh trong các mơi tr ưng b t đ nh và r i ro, phân tích quy t đnh Bayes, cây quy t đ nh và lí thuy t trị ch ơi. Ch ươ ng VII trình bày v mơ hình qu n lí hàng d tr (Inventory Management Model), m t v n đ quan tr ng phát sinh trong qu n lí tài nguyên và ngu n l c c a các doanh nghi p. ðây là các ch đ ch yu nh t c a mơn V n trù h c mà sinh viên các ngành Tin h c, Cơng ngh thơng tin và Tốn - Tin ng d ng t i các tr ưng đ i h c n ưc ngồi b t bu c ph i h c. Ph n bài t p sau t ng ch ươ ng giúp sinh viên c ng c các ki n th c đã h c và th c hành áp dng các quy trình tính tốn khoa h c. Nh ng sinh viên khá cĩ th t h c sâu thêm bng cách thu th p tài li u liên quan qua nhi u ngu n, đ c bi t trên Internet và vi t các ph n m m nh . Giáo trình c ũng cĩ th đưc l y làm tài li u tham kh o hay d y và h c các ph ươ ng pháp tốn ng d ng hay mơ hình hĩa cho các chuyên ngành nh ư: Qu n lí đt đai, Kinh t nơng nghi p, C ơ đin và m t s chuyên ngành qu n lí − kinh t − cơng ngh khác b c đ i h c ho c cao h c. Mt s tài li u ng ưi h c cĩ th tham kh o thêm là: Gillet B. E. , Introduction to Operations Research, McGraw Hill, New York, 1990; Taha H. A. , Operations Research, MacMillan Publishing Company, New York, 1989; Levin R. I., Rubin D. S. and Stinson J. P. , Quantitative approaches to management, McGraw Hill, New York, 1986; Phan Qu c Khá nh, V n trù h c, Nxb Giáo d c, 2004; T p chí ng d ng Tốn hc, Hi ng d ng Tốn h c Vi t Nam , 2003 - 2007. Trong quá trình biên so n, tuy tác gi r t c g ng nh ưng cĩ l khơng tránh kh i sai sĩt. Tác gi xin chân thành c m ơn các ý ki n đĩng gĩp ch nh s a b n th o bài gi ng mơn h c c a các đ ng nghi p trong Khoa Cơng ngh thơng tin và sinh viên ngành Tin h c các khĩa K47, K48, K49, K50 c a Tr ưng ð i h c Nơng nghi p Hà Ni và luơn mong mu n ti p t c nh n đưc nhi u gĩp ý c a các nhà khoa h c, các gi ng viên và sinh viên đ cho giáo trình đưc hồn ch nh h ơn, chính xác h ơn và sinh đng h ơn. Hà N i, ngày 10 tháng 10 n ăm 2008 Tác gi
Ch ươ ng I M ð U 1. GI I THI U V V N TRÙ H C VÀ KHOA H C QU N LÍ 1.1. Vai trị c a V n trù h c Vn trù h c ( Operations Research − OR) là ngành h c nghiên c u v các ho t đ ng hp lí. Vi c t ch c và ti n hành các ho t đ ng trong nhi u l ĩnh v c nh ư kinh t , xã h i, qu c phịng, kinh doanh, s n xu t, d ch v địi h i các nhà qu n lí ph i vn d ng m t cách thích h p các điu ki n cho phép đ trù tính và đư a ra các quy t đ nh. ði v i b máy qu n lí các c p trong các doanh nghi p, t p đồn, cơng ti , ra quy t đnh chính là trách nhi m then ch t nh t. Quá trình ra quy t đ nh đưc b t đ u khi b máy qu n lí phát hi n m t v n đ nào đĩ c n quan tâm t i. Sau đĩ, c n xác đnh rõ v n đ, phát bi u m c tiêu ph i h ưng t i và các điu ki n h n ch (cịn g i là các điu ki n ràng bu c) c ũng nh ư tìm ki m và đánh giá các ph ươ ng án. Cu i cùng, ph i ch n ra m t ph ươ ng án hành đng đưc coi là h p lí h ơn c nh m gi i quy t v n đ m t cách t t nh t. N ăng l c c a b máy qu n lí đưc th hi n kh n ăng phát hi n v n đ và gi i quy t bài tốn quy t đ nh phát sinh. Mt quá trình ra quy t đ nh chính là m t quá trình phân tích và t ng h p thơng tin, cĩ th cĩ hình th c đnh tính hay đnh l ưng . V i cách ti p c n đ nh tính, ng ưi qu n lí cĩ th d a vào các nh n đ nh ch quan và kinh nghi m s n cĩ c a mình đ đưa ra quy t đnh. Trong m t s tr ưng h p, cách ti p c n này cĩ tính “tr c giác” nh ưng c ũng giúp đư a ra đưc quy t đ nh đ t t. Tuy nhiên, trong r t nhi u tr ưng h p khác, cách ti p c n đnh l ưng s cĩ hi u qu th t s trong vi c tr giúp quá trình ra quy t đ nh. Cách ti p cn đ nh l ưng th ưng đưc nhà qu n lí th c hi n trong các tr ưng h p sau: - V n đ đ t ra khá ph c t p bao g m nhi u bi n và do đĩ c n ph i thi t l p mơ hình tốn h c và s d ng các cơng c đ nh l ưng đ tìm ra đưc ph ươ ng án gi i quy t. - Các d li u liên quan t i v n đ c n kh o sát cĩ d ng d li u s và m c tiêu c n hưng t i cĩ tính ch t đ nh l ưng, ch ng h n nh ư c n nâng cao hay h th p m t ch s nào đy. - V n đ đ t ra cĩ tính ch t “l p”, t c là quá trình gi i quy t v n đ cĩ th bao g m mt s cơng đon/th t c l p đi l p l i nhi u l n và vì v y, ti p c n đ nh l ưng s giúp ng ưi qu n lí ti t ki m th i gian c ũng nh ư chi phí. - Ti p c n đ nh l ưng đã t ra h u hi u trong m t s tình hu ng t ươ ng t ho c khi ng ưi qu n lí đã cĩ kinh nghi m và thành cơng trong vi c gi i quy t các v n đ t ươ ng t d a trên ti p c n đ nh l ưng. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 8
Cĩ th nĩi, V n trù h c là m t cơng c đ nh l ưng n n t ng c a Khoa h c qu n lí (Management Science − MS) , mà trong đĩ các ph ươ ng pháp và kĩ thu t c a Tốn h c cũng nh ư các cơng c tính tốn, l ưu tr và x lí d li u c a Tin h c đưc áp d ng đ mơ hình hĩa, phân tích và tìm ra l i gi i cho các bài tốn quy t đ nh, nh m h tr b máy qu n lí đư a ra đư a ra đưc quy t đ nh đúng đ n trong điu ki n ngu n l c và tài nguyên h n ch . Vì v y, V n trù h c cĩ m t vai trị r t quan tr ng trong vi c thi t l p các k ho ch dài h n, phát tri n các chi n l ưc ch đ o c ũng nh ư trong vi c h tr các ho t đ ng di n ra hàng ngày trong nhi u l ĩnh v c. Vn trù h c là m t ngành h c v a cĩ tính khoa h c v a cĩ tính ngh thu t. V i t ư cách là m t khoa h c, V n trù h c nghiên c u và thi t l p các mơ hình tốn h c c a các vn đ phát sinh t th c t c ũng nh ư các ph ươ ng pháp tốn h c/các thu t gi i đ gi i quy t mơ hình đt ra. Tuy nhiên, V n trù h c c ũng là m t ngh thu t, vì r ng s thành cơng c a quá trình ra quy t đ nh ph thu c ph n l n vào tính sáng t o và n ăng l c c a các nhà phân tích quy t đ nh. Vi c thu th p s li u, thi t l p mơ hình và tri n khai ph ươ ng án tìm đưc trên th c t ph thu c vào kh n ăng c a chuyên gia hay nhĩm chuyên gia làm V n trù h c trong vi c khai thác đưc thơng tin xác th c c ũng nh ư xây dng đưc s giao ti p tin c y v i b máy qu n lí. 1.2. Các b ưc áp d ng V n trù h c Các b ưc c ơ b n khi áp d ng V n trù h c đ thi t l p và gi i quy t m t mơ hình phát sinh t th c t cĩ th đưc tĩm l ưc nh ư sau: − Kh o sát th c t và phát hi n v n đ . T i b ưc này, c n áp d ng và hồn thi n các kĩ năng nh ư: bi t l ng nghe, điu tra và kh o sát d li u, bi t phân tích các ho t đng th c t c ũng nh ư phân bi t đưc các y u t quan tr ng v i các chi ti t th y u. − Phân tích v n đ và xây d ng mơ hình. Tr ưc h t c n xác đ nh rõ m c tiêu nghiên c u và đnh d ng rõ bài tốn phát sinh và ph ươ ng án gi i quy t, t đĩ xác đnh các y u t liên quan mà nhà qu n lí cĩ th ki m sốt đưc. Nĩi cách khác, c n xác đnh m c tiêu và các điu ki n h n ch /điu ki n ràng bu c d ưi d ng đ nh tính. Sau đĩ l a ch n các bi n quy t đ nh và xây d ng mơ hình tốn h c phù h p, ph n ánh đưc th c t khách quan. − Thu th p s li u đ u vào và xác đnh ph ươ ng pháp gi i quy t. C ăn c mơ hình đã xây d ng đưc c n thu th p các s li u đ u vào c n thi t, đ tin c y c a s li u đ u vào nh h ưng r t đáng k t i k t qu đ u ra c a mơ hình. V i mơ hình đã xây d ng đưc cn tìm ra m t ph ươ ng pháp gi i quy t thích h p d a trên các ph ươ ng pháp đã bi t ho c phát tri n ph ươ ng pháp m i. − Xác đnh quy trình gi i/thu t gi i và ch n l a ph ươ ng án h p lí. Cĩ th gi i mơ hình b ng cách tính tốn thơng th ưng nhm l a ch n trong các ph ươ ng án kh thi m t ho c m t s ph ươ ng án h p lí h ơn c . ð i v i các mơ hình l n, g m nhi u bi n quy t đnh và nhi u điu ki n ràng bu c c n l p trình và gi i mơ hình trên máy tính.
− Ki m th mơ hình và đánh giá ph ươ ng án tìm đưc. Trong tr ưng h p ph ươ ng án tìm đưc kéo theo các k t qu b t th ưng v m t tính tốn ho c khơng phù h p v i th c t, c n ki m tra và ch nh s a l i mơ hình, rà sốt l i các s li u đ u vào c ũng nh ư các bưc tính tốn hay ch n l a ph ươ ng án. Sau đĩ gi i l i mơ hình đ tìm ra ph ươ ng án phù h p h ơn. − Tri n khai ph ươ ng án tìm đưc trên th c t . Trong tồn b quá trình ra quy t đnh, chuyên gia V n trù h c c n quan h ch t ch v i nhà qu n lí, gi i thích rõ ràng v tác d ng c a mơ hình đã đt ra. ð ph ươ ng án cu i cùng đưc tri n khai trên th c t , cn cĩ báo cáo chi ti t giúp b máy qu n lí hi u rõ các hi u qu thi t th c mà ph ươ ng án cĩ th mang l i. Tuy nhiên, c ũng c n nêu rõ các điu ki n đ m b o c n thi t c ũng nh ư phân tích rõ các y u t l i nhu n/chi phí/ri ro c a ph ươ ng án. 1.3. Quá trình phát tri n c a V n trù h c Nh ng ti n b nhân lo i đ t đưc trong vài th k v a qua và trong giai đon hi n ti cĩ ph n đĩng gĩp quan tr ng c a các ph ươ ng pháp khoa h c trong vi c gi i quy t các v n đ kinh t , xã h i. Ph ươ ng pháp lu n khoa h c, tr ưc đây th ưng đưc bi t t i trong các v n đ c a Khoa h c t nhiên, ngày nay ngày càng đưc ng d ng r ng rãi trong các l ĩnh v c c a Khoa h c qu n lí nh ư: l p k ho ch, t ch c và ki m sốt các ho t đ ng. T hàng vài nghìn n ăm tr ưc, các ho t đ ng ch t o và l p ráp tàu bi n t i Venice đã đưc t ch c m t cách khá khoa h c. Vào cu i th k XIX, Frederick W. Taylor đã gi i quy t thành cơng bài tốn quan tr ng c a Kĩ ngh cơng nghi p ( Industrial Engineering ) lúc đĩ là ch t o ra các lo i x ng đ khai thác các lo i qu ng khác nhau vi n ăng su t cao nh t. C ũng vào th i gian này, Henry L. Gantt gi i quy t thành cơng bài tốn l p ti n trình s n xu t ( Production Scheduling ) khi s n ph m đưc ch t o và hồn thi n qua nhi u cơng đon. Dn d n, các nhà qu n lí m r ng các bài tốn trong mt s ho t đ ng kĩ ngh cơng nghi p sang các ho t đ ng khác c a cơng ti nh ư: khai thác và s d ng các ngu n nguyên li u, thuê và phát tri n nhân l c, chính sách tài chính, b t đ ng s n Các nhà khoa h c t nhiên, xã h i c ũng b t đ u quan tâm t i các bài tốn qu n lí và nh n th c đưc t m quan tr ng c a vi c gi i quy t v n đ m t cách h th ng, t m quan tr ng c a các nghiên c u liên ngành bao g m khoa h c c ơ b n, kĩ ngh và qu n lí. ðĩ c ũng là kh i ngu n c a Khoa h c qu n lí. T đ u th k XX, V n trù h c/Khoa h c qu n lí đã đưc áp d ng khá r ng rãi trong nhi u l ĩnh v c. T i n ưc Anh vào n ăm 1914 - 1915 F. W. Lanchester đã xem xét các ho t đ ng quân s m t cách đ nh l ưng khi đưa ra ph ươ ng pháp đánh giá sc m nh quân s thơng qua s l ưng b binh và h a l c. Cịn t i M ĩ lúc đĩ, T. A. Edison nghiên cu và mơ ph ng các ho t đ ng h p lí c a tàu chi n trong t n cơng và tiêu di t các tàu ng m. Vào n ăm 1917, nhà bác h c ng ưi ðan M ch A. K. Erlang cho cơng b các cơng trình v các ho t đ ng h p lí trong h d ch v đin tho i và b ưu đin, cĩ tên g i t ng Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 10
quát là h th ng hàng ch ( Waiting Line System ). N ăm 1915, Ford W. Harris cơng b v cách xác đnh dung l ưng lơ hàng t i ưu trong bài tốn qu n lí hàng d tr ( Inventory Management ). Sau đĩ m t lo t cơng trình đưc các tác gi khác ti p t c cơng b v các mơ hình ki m sốt hàng d tr . Các ng d ng c a lí thuy t xác su t trong ki m đ nh ch t l ưng ( Quality Control ) c ũng đưc đ c p t i trong các bài báo c a Walter Shewhart. Mơ hình quy ho ch tuy n tính ( Linear Programming ) đưc giáo s ư ði h c Havard Wassily Leontieff áp d ng vào nh ng n ăm 1930 đ mơ t và phân tích tồn b nn kinh t M ĩ. Các ng d ng c a V n trù h c trong kinh doanh l n đ u tiên đưc Horace C. Levinson phát tri n trong giai đon 1920 - 1930 đ nghiên c u các m i quan h gi a doanh thu và qu ng cáo, gi a thu nh p và đa đim sinh s ng c a ng ưi tiêu dùng và các m t hàng mua s m. Sau n ăm 1945, V n trù h c ti p t c đưc ng d ng ngày càng r ng rãi trong nhi u l ĩnh v c. R t nhi u bài tốn qu n lí đưc gi i quy t b ng ph ươ ng pháp đơ n hình ( Simplex Method ) do George B. Danzig đư a ra vào n ăm 1947. Các mơ hình m ng ( Network Model ) đưc phát tri n l n đ u vào n ăm 1958 v i s tr giúp c a cơng ti t ư v n Booz, Allen và Hamilton. Ti Vi t Nam, t nhi u n ăm tr ưc đây các ho t đ ng gi ng d y và nghiên c u v Vn trù h c đã đưc ti n hành t i m t s c ơ s đào t o và nghiên c u nh ư ði h c T ng hp Hà N i, Vi n Tốn h c, Vi n ðiu khi n kinh t Vn trù h c đưc đưa vào ng dng thành cơng trong m t s l ĩnh v c nh ư giao thơng, th y l i, s n xu t nơng nghi p và cơng nghi p, d ch v , qu c phịng, v i các đĩng gĩp c a các giáo s ư Hồng T y, Tr n V ũ Thi u, Nguy n ðình Ng c, Nguy n Quý H . ðưc thành l p vào n ăm 2002, Tp chí ng dng Tốn h c đã và đang cơng b nhi u bài báo trong l ĩnh v c V n trù h c. Ngày nay, t i nhi u n ưc trên th gi i, các H i V n trù h c và các Vi n Khoa h c qu n lí đưc thành l p, v i nhi u t p chí chuyên kh o n i ti ng. Cĩ th gi i thi u đây mt s t p chí qu c t nh ư: Operations Research, Management Science, A.I.E.E. Transactions, C.O.R.S. Journal, Industrial Engineering, European Journal of Operational Research, Asia -Pacific Journal of Operational Research, Decision Sciences, Decision Support Systems. 2. CÁC NG D NG VÀ PH ƯƠ NG PHÁP ðNH L ƯNG C Ơ B N C A VN TRÙ H C 2.1. M t s ng d ng Các ng d ng c ơ b n c a V n trù h c cĩ th đưc phân lo i theo các l ĩnh v c sau đây: - L p k ho ch s d ng các ph ươ ng ti n, bao g m: xác đ nh quy mơ và đa đim xây d ng xí nghi p, l p k ho ch cho b nh vi n, các h th ng cung ng d ch v qu c t , xác đnh s l ưng ph ươ ng ti n c n thi t, s p x p ph ươ ng án v n chuy n, b trí kho hàng, phân cơng nhi m v .
- Ch t o, s n xu t: ki m sốt hàng d tr , cân b ng s n xu t và ti p th , l p ti n trình s n xu t, đ m b o n đ nh s n xu t. - Xây d ng: phân ph i các d tr tài nguyên cho các d án, xác đ nh s thành viên ca các đ i cơng tác, duy trì ti n trình cơng tác, l p ti n trình d án. - ðt hàng, mua nguyên li u: chuy n giao v t li u, chính sách mua hàng và đt l i hàng t i ưu. - Ti p th : xác đ nh chi phí ti p th , th i đim gi i thi u s n ph m m i, ch n l a danh m c s n ph m h n h p. - Tài chính: chính sách c t c, phân tích đ u t ư và ch n l a danh m c đ u t ư. - K tốn: l p k ho ch lu ng ti n, chính sách tín d ng, l p k ho ch cho chi n l ưc k tốn n . - Chính sách nhân l c: tuy n d ng nhân viên, l p k ho ch nhân l c, l p ti n trình bi d ưng cán b , cân b ng các kĩ năng. - Nghiên c u và phát tri n: Ki m sốt các d án nghiên c u và phát tri n, l p k ho ch phát tri n s n ph m m i. Chúng ta hãy xem xét m t cách chi ti t h ơn v n đ trên qua m t vài ng d ng đin hình c a V n trù h c/Khoa h c qu n lí nh ư sau: - Bài tốn l p k ho ch nhân l c. M t cơng ti c n th ưng xuyên duy trì 1000 nhân viên, trong s đĩ cĩ 70% nhân viên “c ũ” ( đã làm vi c t i cơng ti t m t n ăm tr lên) và 30% nhân viên “m i” (làm vi c d ưi m t n ăm). Theo các k t qu th ng kê cĩ đưc, trong s nhân viên m i thơng th ưng 50% b vi c trong vịng 4 tháng đu, 20% b vi c trong vịng 4 tháng ti p theo, 10% b vi c trong 4 tháng k ti p và ch cĩ 20 % khơng b vi c trong n ăm đ u tiên vào làm vi c. Trong s nhân viên c ũ, thơng th ưng hàng năm cĩ 30% b vi c (t c là kho ng 10% cho m i kì 4 tháng). V y cơng ti c n xác đ nh t l tuy n nhân viên m i hàng n ăm nh ư th nào đ: i) duy trì n đ nh đưc l ưng lao đng, ii) gi m l ưng lao đ ng hàng n ăm theo m t t l đ nh tr ưc, iii) t ăng l ưng lao đng hàng n ăm theo m t t l đ nh tr ưc. - Bài tốn phân cơng nhi m v . M t nhĩm 3 kĩ sư A, B và C đưc phân cơng hồn thành 3 nhi m v 1, 2 và 3. C n giao cho m i kĩ sư m t nhi m v sao cho t ng s ngày cơng th c hi n 3 nhi m v trên là th p nh t, bi t r ng kĩ sư A cĩ th hồn thành các nhi m c 1, 2, 3 theo th t trong vịng 2, 6 và 3 ngày, cịn s ngày nh ư v y cho các kĩ sư B và C là 8,4, 9 và 5, 7, 8. B ng cách li t kê các ph ươ ng án phân cơng nhi m v (cĩ tt c 3! = 6 ph ươ ng án phân cơng), cĩ th tìm đưc ngay ph ươ ng án phân cơng t i ưu là: phân cơng cho kĩ sư A nhi m v 3, kĩ sư B nhi m v 2 và kĩ sư C nhi m v 1. Tuy nhiên, n u bài tốn đưc m r ng khi c n phân cơng 20 nhi m v cho 20 kĩ sư thì ph ươ ng pháp li t kê (v i t t c là 20! ≈ 2,433 ×10 18 ph ươ ng án phân cơng) t ra r t kém Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 12
tác d ng. Nh ư v y c n ph i nghiên c u m t ph ươ ng pháp khác đ gi i quy t bài tốn phân cơng nghi m v t ng quát. 2.2. Các ph ươ ng pháp đnh l ưng Các ph ươ ng pháp đnh l ưng c ơ b n th ưng đưc s d ng trong V n trù h c/Khoa hc qu n lí bao g m: - Các ph ươ ng pháp t i ưu gi i mơ hình quy ho ch tuy n tính và phi tuy n, quy ho ch đ ng và quy ho ch đa m c tiêu. - Các kĩ thu t/thu t tốn chuyên d ng gi i các mơ hình m ng nh ư bài tốn v n t i, bài tốn tìm đưng đi ng n nh t, mơ hình m ng PERT, bài tốn tìm lu ng c c đ i. - Kĩ thu t mơ ph ng gi i các mơ hình hàng ch /d ch v cơng c ng. - Phân tích Markov ng d ng trong kinh doanh và qu n lí. - Các ph ươ ng pháp ch n l a quy t đ nh d a trên Lí thuy t quy t đ nh và Lí thuy t trị ch ơi. - Các mơ hình qu n lí hàng d tr . Do th i l ưng cĩ h n, m t s ph ươ ng pháp khác c a V n trù h c nh ư các ph ươ ng pháp d báo, h chuyên gia, khai phá d li u và tri th c khơng đưc đ c p t i trong giáo trình này. 2.3. H thơng tin qu n lí Các tiêu chu n v s li u. Các ph ươ ng pháp đnh l ưng hay kĩ thu t tính tốn đưc đ c p trên đây th ưng địi h i các s li u đ u vào ph i đ m b o các tiêu chu n sau: - Chính xác: s li u ph i khơng cĩ sai sĩt. - Chi phí hi u qu : chi phí thu th p s li u th p h ơn giá tr chúng cĩ th mang l i. - C p nh t: s li u ph n ánh đúng các điu ki n hi n t i. - Tin c y: s li u phát sinh k t qu khơng cĩ gì b t th ưng. - D s d ng: s li u cĩ th đưc s d ng thân thi n mà khơng ph i s a đ i gì thêm. Các tiêu chu n trên đây cĩ th cĩ tính ch t “th a hi p”, cĩ ngh ĩa là n u m t tiêu chu n nào đĩ tr nên t t h ơn thì c ũng d n t i m t tiêu chu n khác x u đi. Ch ng h n, chi phí l y s li u th p th ưng nh h ưng t i tính chính xác và đ tin c y c a s li u. Tuy nhiên, n ăm tiêu chu n này luơn là m c tiêu c n “c c đ i hĩa” khi thu th p s li u. Khái ni m h thơng tin qu n lí. Cĩ th coi h thơng tin qu n lí là m t h th ng các s li u/d li u đưc thu th p, t ch c, phân tích, x lí và l ưu tr trên máy tính/m ng máy tính d ưi d ng thơng tin h tr các quy t đ nh qu n lí. ð ng d ng thành cơng các ph ươ ng pháp đnh l ưng c a V n trù h c, chúng ta luơn c n thi t l p đưc m t h thơng tin qu n lí đ t t nh m cung c p các s li u c n thi t cho mơ hình tốn h c c a v n đ
cn gi i quy t. Rõ ràng r ng, các s li u thơ thu th p đưc trong b ưc kh o sát th c t và phát hi n v n đ đưc bi n đ i m t cách thích h p thành thơng tin h tr ra quy t đnh. Ch ng h n, các s li u thơ v h s l i nhu n c a m t lo i s n ph m đưc bi n đ i thành h s l i nhu n (trung bình)/ đơ n v s n ph m, là m t d ng thơng tin h tr vi c lp k ho ch s n xu t s n ph m này. Máy tính/m ng máy tính cĩ r t nhi u đim m nh nh ư: tính chính xác, tính nh t quán, b nh l n, x lí đưc nhi u s li u và phép tốn ph c t p, làm vi c theo các quy tc và ch ươ ng trình đnh s n. Tuy nhiên, đ thi t l p m t h thơng tin qu n lí hi u qu , cn xác đ nh đưc các d ng thơng tin h tr c n thi t giúp phát huy t t nh t các ưu đim suy lu n sáng t o và linh ho t c a ng ưi ra quy t đ nh. M t h thơng tin qu n lí “nhi u máy tính quá” th ưng d n đ n ph ươ ng án cĩ tính cơ gi i, s ph n ng thi u linh ho t và quy t đ nh ph m vi h p. Trái l i, m t h thơng tin qu n lí “nhi u tính ng ưi quá” th ưng d n đ n s ph n ng ch m ch p và s h n ch trong vi c s d ng s li u c ũng nh ư kh n ăng tìm ki m và đánh giá các ph ươ ng án thay th . ðây chính là các v n đ c n chú tr ng khi các chuyên gia V n trù h c và Cơng ngh thơng tin cùng nhau xem xét và xây d ng m t h thơng tin qu n lí. H thơng tin qu n lí cĩ th đưc phân ra ba lo i c ơ b n: h th ng cho đ u ra là các ki u báo cáo, h th ng tr l i các truy v n d ng “what - if” và h h tr ra quy t đnh ( Decision Support System - DSS ). Các h h tr ra quy t đ nh là lo i h thơng tin qu n lí hồn thi n nh t cho phép tích h p quá trình ra quy t đ nh t ươ ng tác ng ưi - máy tính v i các cơ s d li u và các mơ hình đnh l ưng nh m h tr tr c ti p vi c đưa ra quy t đ nh. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 14
Ch ươ ng II MT S MƠ HÌNH VÀ PH ƯƠ NG PHÁP T I ƯU 1. MƠ HÌNH QUY HO CH TUY N TÍNH 1.1. Phát bi u mơ hình quy ho ch tuy n tính Vi m c đích tìm hi u b ưc đ u, xét mơ hình tốn h c sau đây, cịn g i là mơ hình quy ho ch tuy n tính hay bài tốn quy ho ch tuy n tính (BTQHTT), mà trong đĩ chúng ta mu n t i ưu hĩa (c c đ i hĩa hay c c ti u hố) hàm m c tiêu: z = c 1x1 + c 2x2 + c nxn → Max (Min), vi các điu ki n ràng bu c: a11 x1 + a 12 x2 + +a 1n xn ≤ b 1 a21 x1 + a 22 x2 + +a 2n xn ≤ b 2 am1 x1 + a m2 x2 + +a mn xn ≤ b m x1, x 2, , x n ≥ 0 ( điu ki n khơng âm). Trong tr ưng h p t ng quát, BTQHTT cĩ th bao g m các ràng bu c d ng ≥, ≤ ho c d ng =, các bi n cĩ th cĩ d u ≥ 0, ≤ 0 ho c d u tùy ý. Ví d 1: z = 8x 1 + 6x 2 → Max, vi các ràng bu c: 4x 1 + 2x 2 ≤ 60 2x 1 + 4x 2 ≤ 48 x1, x 2 ≥ 0. BTQHTT trên đây chính là m t bài tốn quy t đ nh. C n tìm các giá tr c a các bi n quy t đ nh x 1, x 2 đ các ràng bu c đưc tho mãn và hàm m c tiêu đt giá tr l n nh t. Bài tốn này cĩ ý ngh ĩa kinh t nh ư sau: Gi s m t xí nghi p s n xu t hai lo i s n ph m I và II. ð s n xu t ra m t đơn v s n ph m I c n cĩ 4 đơn v nguyên li u lo i A và 2 đơ n v nguyên li u lo i B, các ch tiêu đĩ cho m t đơn v s n ph m lo i II là 2 và 4. Lưng nguyên li u d tr lo i A và B hi n cĩ là 60 và 48 ( đơ n v ). B máy qu n lí c n đư a ra quy t đ nh nên l a ch n ph ươ ng án s n xu t nào đ tri n khai nh m đ t l i nhu n ln nh t, bi t l i nhu n trên m i đơn v s n ph m bán ra là 8 và 6 ( đơ n v ti n t ) cho các s n ph m lo i I và II.
Ph ươ ng pháp đ th gi i BTQHTT hai bi n Ph ươ ng pháp đ th cĩ ý ngh ĩa minh ho và giúp hi u b n ch t v n đ . Bưc 1: V mi n ràng bu c/mi n các ph ươ ng án kh thi, là t p h p các ph ươ ng án kh thi (các ph ương án, n u nĩi m t cách ng n g n). M i ph ươ ng án đưc th hi n qua b s (x 1, x 2) cịn g i là véc t ơ nghi m, tho mãn t t c các ràng bu c đã cĩ (xem hình II.1). x2 30 4x 1 + 2x 2 = 60 1 A 8 B 4 2x 1 + 4x 2 = 48 C O 3 6 15 24 x1 Hình II.1. Ph ươ ng pháp đ th gi i bài tốn quy ho ch tuy n tính − Tr ưc h t chúng ta v đ th 4x 1 + 2x 2 = 60 b ng cách xác đ nh hai đim trên đ th : (0, 30) và (15, 0). ð th trên là m t đưng th ng chia m t ph ng làm hai n a m t ph ng: m t ph n g m các đim (x 1, x 2) tho mãn 4x 1 + 2x 2 ≤ 60; m t ph n tho mãn 4x 1 + 2x 2 ≥ 60. Ta tìm đưc n a m t ph ng tho mãn 4x 1 + 2x 2 ≤ 60. − T ươ ng t , cĩ th v đ th 2x 1 + 4x 2 = 48 b ng cách xác đ nh hai đim thu c đ th (0, 12) và (24, 0). Sau đĩ tìm n a m t ph ng tho mãn 2x 1 + 4x 2 ≤ 48. − Lúc này, giao c a hai n a m t ph ng tìm đưc trên cho ta t p h p các đim (x 1, x 2) tho mãn hai ràng bu c đ u tiên. Tuy nhiên, đ tho mãn điu ki n khơng âm c a các bi n, ta ch xét các đim n m trong gĩc ph n t ư th nh t. V y mi n các ph ươ ng án kh thi là mi n gi i h n b i t giác OABC. Bưc 2: Trong mi n (OABC) ta tìm đim (x 1, x 2) sao cho z = 8x 1 + 6x 2 đt giá tr ln nh t. Cách 1: Dùng đưng đ ng m c. Tùy theo giá tr c a x 1, x 2 mà z cĩ m c giá tr khác nhau. − V đưng đ ng m c: 8x 1 + 6x 2 = c m c c = 24, (ta cĩ th ch n giá tr c b t kì, nh ưng ch n c = 24 là b i s chung c a 6 và 8 đ vi c tìm to đ các đim c t hai tr c to đ thu n l i h ơn). Chúng ta d dàng tìm đưc hai đim n m trên đưng đ ng m c là (0, 4) và (3, 0). Các đim n m trên đưng đ ng m c này đu cho giá tr hàm m c tiêu z = 24. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 16
− T ươ ng t , cĩ th v đưng đ ng m c th hai: 8x 1 + 6x 2 = 48 đi qua hai đim (0, 8) và (6, 0). Chúng ta nh n th y, n u t nh ti n song song đưng đ ng m c lên trên theo r hưng c a véc t ơ pháp tuy n n (8, 6) thì giá tr c a hàm m c tiêu z = 8x 1 + 6x 2 t ăng lên. Vy giá tr z l n nh t đ t đưc khi đưng đ ng m c đi qua đim B(12, 6) (tìm đưc x1 = 12, x 2 = 6 b ng cách gi i h ph ươ ng trình 4x 1 + 2x 2 = 60 và 2x 1 + 4x 2 = 48). Kt lu n: Trong các ph ươ ng án kh thi thì ph ươ ng án t i ưu là (x 1, x 2) = (12, 6). T i ph ươ ng án này, giá tr hàm m c tiêu là l n nh t z max = 8 × 12 + 6 × 6 = 132. Nh n xét: Ph ươ ng án t i ưu c a bài tốn trên (hay các BTQHTT khác, n u cĩ) luơn đt đưc t i m t trong các đ nh c a mi n ph ươ ng án kh thi D (là m t t p l i đa di n trong tr ưng h p BTQHTT t ng quát) hay cịn g i là các đim c c biên (chính xác h ơn, mi n đim c c biên là đim thu c mi n D, mà khơng th tìm đưc m t đon th ng nào cũng thu c mi n D nh n đim đĩ là đim trong). Nh n xét trên đây là m t đ nh lí tốn hc đã đưc ch ng minh m t cách t ng quát trong các giáo trình mơn h c T i ưu hố. Nĩi m t cách hình nh, mu n đ t đưc ph ươ ng án t i ưu cho các BTQHTT thì c n ph i “m o hi m” đi xét các đim c c biên c a mi n ph ươ ng án kh thi. Cách 2: T nh n xét trên, đ tìm ph ươ ng án t i ưu ta ch c n so sánh giá tr c a hàm mc tiêu t i các đim c c biên c a mi n ph ươ ng án. Tính giá tr z t i O(0, 0): z(0, 0) = 0; t i A(0, 12): z(0, 12) = 72; t i C(15,0): z(15, 0) = 120; t i B(12, 6): z(12, 6) = 132 = Max{z(O), z(A), z(B), z(C)}. V y z max = 132. Nh n xét: Mu n tìm ph ươ ng án t i ưu c a BTQHTT ta xu t phát t m t đim c c biên nào đĩ, tìm cách c i thi n hàm m c tiêu b ng cách đi t i đim c c biên k nĩ. Ti p t c nh ư vy cho t i khi tìm đưc ph ươ ng án t i ưu. Trong tr ưng h p BTQHTT cĩ ph ươ ng án t i ưu thì quy trình gi i này bao g m h u h n b ưc (do s đim c c biên là h u h n). Sơ đ kh i Bt đu Nh p d li u Tìm đim c c biên xu t phát Ki m tra Sai Tìm điu ki n t i ưu đim c c biên k t t h ơn ðúng In và l ưu tr k t qu Dng Hình II.2. S ơ đ kh i gi i BTQHTT
ði v i BTQHTT đang xét, quy trình gi i đưc minh ho nh ư sau: O(0, 0) → A(0,12) → B(12,6) d ng z = 0 → z = 72 → z = 132 ho c: O(0, 0) → C(15, 0) → B(12, 6) d ng z = 0 → z = 120 → z = 132. Quy trình gi i BTQHTT t ng quát cĩ s ơ đ kh i gi n l ưc nh ư trình bày trên hình II.2. Trong s ơ đ trên, vì m c đích trình bày v n đ đơn gi n, chúng ta khơng đ c p t i các tr ưng h p khi BTQHTT cĩ mi n ph ươ ng án là t p r ng (lúc đĩ ta khơng tìm đưc ph ươ ng án xu t phát) c ũng nh ư khi ta khơng tìm đưc đim c c biên k t t h ơn m c dù điu ki n t i ưu ch ưa tho mãn (lúc đĩ t p các giá tr hàm m c tiêu z khơng b ch n). 1.2. Ph ươ ng pháp đơ n hình gi i BTQHTT d ng chính t c ðây là ph ươ ng pháp s gi i BTQHTT theo s ơ đ trên. ð gi i ví d 1 trên đây, tr ưc h t chúng ta c n đưa BTQHTT v d ng chính t c b ng cách thêm vào các bi n bù khơng âm x 3 và x 4 nh ư sau: z = 8x 1 + 6x 2 + 0x 3 + 0x 4 → Max vi các ràng bu c: 4x 1 + 2x 2 + x 3 = 60 2x 1 + 4x 2 + x 4 = 48 x1, x 2, x 3, x 4 ≥ 0. Mt cách t ng quát, BTQHTT dng chính t c là bài tốn v i các bi n khơng âm, các ràng bu c v i d u “=”, h s v ph i c a các ràng bu c khơng âm. Ngồi ra, m i ph ươ ng trình b t bu c ph i cĩ m t bi n đ ng đ c l p v i h s +1. ð gi i BTQHTT d ng chính t c trên đây, c n l p m t s b ng đơn hình nh ư trình bày trong b ng II.1. Tr ưc h t, c n đin s li u c a bài tốn đã cho vào b ng đơn hình bưc 1: − C t 1 là c t h s hàm m c tiêu ng v i các bi n c ơ s đã ch n. Ph ươ ng án xu t phát cĩ th ch n là x 1 = x 2 = 0 ( đây chính là đim g c to đ O(0, 0)), do đĩ x 3 = 60, x 4 = 48). Nh ư v y t i b ưc này chúng ta ch ưa b ưc vào s n xu t, nên trong ph ươ ng án ch ưa cĩ đơ n v s n ph m lo i I hay II đưc s n xu t ra (ch “s n xu t” ra các l ưng nguyên li u d ư th a, ta c ũng nĩi là các “s n ph m” lo i III và IV) và giá tr hàm m c tiêu z t m th i b ng 0. Các bi n bù cĩ giá tr l n h ơn 0 cĩ ngh ĩa là các nguyên li u lo i tươ ng ng ch ưa đưc s d ng h t. Ta g i các bi n x 3 và x 4 là các bi n c ơ s vì chúng cĩ Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 18
giá tr l n h ơn 0 cịn x 1 và x 2 là các bi n ngồi c ơ s vì chúng cĩ giá tr b ng 0. V i bài tốn cĩ hai ràng bu c, t i m i b ưc ch cĩ hai bi n c ơ s . − C t 2 là c t các bi n c ơ s . Trong c t 3 (c t ph ươ ng án) c n ghi các giá tr c a các bi n c ơ s đã ch n. − Các c t ti p theo là các c t h s trong các điu ki n ràng bu c t ươ ng ng v i các bi n x 1, x 2, x 3 và x 4 c a bài tốn đã cho. Bng II.1. Các b ng đơn hình gi i BTQHTT H s hàm m c c1 = 8 c2 = 6 c3 = 0 c4 = 0 Bi n c ơ s Ph ươ ng án tiêu c j x1 x2 x3 x4 0 x3 60 4 2 1 0 0 x4 48 2 4 0 1 Hàng z z0 = 0 z1 = 0 z2 = 0 z3 = 0 z4 = 0 Hàng ∆j = c j − z j ∆1 = 8 ∆2 = 6 ∆3 = 0 ∆4 = 0 8 x1 15 1 1/2 1/4 0 0 x4 18 0 3 −1/2 1 Hàng z z0 = 120 z1 = 8 z2 = 4 z3 = 2 z4 = 0 Hàng ∆j = c j − z j ∆1 = 0 ∆2 = 2 ∆3 = −2 ∆4 = 0 8 x1 12 1 0 1/3 −1/6 6 x2 6 0 1 −1/6 1/3 Hàng z z0 = 132 8 6 5/3 2/3 Hàng ∆j = c j − z j 0 0 −5/3 −2/3 Phân tích b ng đơn hình b ưc 1 − H s ng v i bi n x 1 trên hàng th nh t là a 11 = 4 cĩ ngh ĩa là t l thay th riêng gi a m t đơn v s n ph m lo i I và m t đơn v s n ph m lo i III là 4 (gi i thích: xét ph ươ ng trình/ràng bu c th nh t 4x 1 + 2x 2 + x 3 = 60, x 1 t ăng m t đơn v thì x 3 ph i gi m b n đơn v n u gi nguyên x 2). T ươ ng t ta cĩ th gi i thích đưc ý ngh ĩa c a các h s a ij khác cho trên hàng 1 và hàng 2 trong b ng đơn hình b ưc 1. − Chúng ta xét hàng z c a b ng đơn hình. ð tính z 1, c n áp d ng cơng th c z 1 = (c t h s c a hàm m c tiêu) × (c t h s c a bi n x 1) = 0 ×4 + 0 ×2 = (giá m t đơn v sn ph m lo i III) ×(t l thay th riêng lo i I/lo i III) + (giá m t đơn v s n ph m lo i IV) × (t l thay th riêng lo i I/lo i IV) = t ng chi phí ph i b ra khi đư a thêm m t đơn v s n ph m lo i I vào ph ươ ng án s n xu t m i = 0. Các giá tr z j, v i j = 1, 2, 3, 4, đưc tính t ươ ng t và chính là các chi phí khi đư a m t thêm m t đơn v s n ph m lo i x j vào ph ươ ng án s n xu t m i. Cịn z 0 là giá tr c a hàm m c tiêu đt đưc t i ph ươ ng án đang xét: z 0 = (c t h s c a hàm m c tiêu) × (c t ph ươ ng án) = 0 ×60 + 0 ×48 = 0.
− Trên hàng ∆j cn ghi các giá tr ∆j, j = 1, 2, 3, 4, tính theo cơng th c ∆j = c j -zj = l i nhu n trên m t đơn v s n ph m - chi phí trên m t đơn v s n ph m. V y ∆j là "lãi biên"/m t đơn v s n ph m khi đưa thêm m t đơn v s n ph m lo i j vào ph ươ ng án s n xu t m i. N u ∆j > 0 thì hàm m c tiêu cịn t ăng đưc khi ta đưa thêm các đơ n v s n ph m lo i j vào ph ươ ng án s n xu t m i. Cĩ th ch ng minh đưc ∆j chính là đo hàm riêng ∂z/ ∂xj c a hàm m c tiêu z theo bi n x j. Nh ư v y, x 1 t ăng lên 1 thì z t ăng lên 8 cịn x2 t ăng lên 1 thì z t ăng lên 6. Do ∆1 và ∆2 đu d ươ ng nên v n cịn kh n ăng c i thi n hàm m c tiêu khi chuy n sang (hay “xoay sang”) m t ph ươ ng án cc biên k t t h ơn (quay l i nh n xét ph n gi i bài tốn b ng ph ươ ng pháp đ th : đim c c biên k c a đim (0, 0) cĩ th là A(0, 12) hay C(15, 0)). Th t c xoay Bưc 1: Ch n c t xoay là c t cĩ ∆j > 0 t c là ch n bi n x j làm bi n c ơ s m i do x j tăng kéo theo hàm m c tiêu t ăng. đây ta ch n đưa x 1 vào ( đánh d u √ c t ∆1). Bưc 2: Ch n hàng xoay đ xác đ nh đưa bi n nào ra kh i s bi n c ơ s (vì t i m i bưc s bi n c ơ s là khơng thay đi). ð ch n hàng xoay, ta th c hi n quy t c “t s dươ ng bé nh t" b ng cách l y c t ph ươ ng án (60, 48) T chia t ươ ng ng cho c t xoay (4, 2) T đ ch n t s bé nh t. M t điu c n chú ý là ta ch xét các t s cĩ m u s d ươ ng. Vì Min{60/4, 48/2} = 60/4 đt đưc t i hàng đu, nên ta đánh d u √ vào hàng xoay là hàng đu (hàng t ươ ng ng v i bi n x 3). Do đĩ c n đưa x 3 ra kh i các bi n c ơ s . Bưc 3: Ch n ph n t xoay n m trên giao c a hàng xoay và c t xoay. Bưc 4: Xoay sang b ng đơn hình m i, xác đ nh các bi n c ơ s m i đ đin vào c t bi n c ơ s , đ ng th i thay các giá tr trong c t h s hàm m c tiêu. Sau đĩ, tính l i các ph n t c a hàng xoay b ng cách l y hàng xoay c ũ chia cho ph n t xoay đ cĩ hàng mi t ươ ng ng. Bưc 5: Các ph n t cịn l i c a b ng đơn hình m i đưc tính theo quy t c "hình ch nh t": (1) mi = (1) cũ - (2) cũ× (4) cũ/(3) cũ, trong đĩ (3) là đnh t ươ ng ng v i ph n t xoay (xem hình II.3). (2) (3) Ch ng h n: (1) cũ = 4, 2 (c ũ) = 2 (3) cũ = ph n t xoay = 4, (4) cũ = 2 ⇒ (1) mi 2 = 4 − 2 × = 3. 4 (1) (4) Hình II.3. Quy t c hình ch nh t Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 20
Gi i thích: Các b ưc xoay trên đây ch là phép bi n đ i t ươ ng đươ ng h ph ươ ng trình 4x 1 + 2x 2 + x 3 = 60 (a) 2x 1 + 4x 2 + x 4 = 48 (b) đ cĩ h x1 + (1/2)x 2 + (1/4)x3 = 15 (a’) 0x 1 + 3x 2 − (1/2)x 3 + x 4 = 18. (b’) bng cách l y ph ươ ng trình (a) chia cho 4 (ph n t xoay) đ cĩ (a’), r i l y (b) tr bt 2 × (a)/4 đ cĩ (b’). ðây chính là n i dung c a b ưc 4 và b ưc 5. Cịn b ưc 3 s đ m bo r ng giá tr c a các bi n c ơ s m i khơng âm (x 1 = 15, x 4 = 18). Áp d ng th t c xoay cho các ph n t n m trên hàng 1 và 2 c a b ng đơn hình b ưc 1, sau đĩ tính các giá tr trên hàng z j và ∆j tươ ng t nh ư khi l p b ng đơn hình b ưc 1, chúng ta s nh n đưc b ng đơn hình b ưc 2. Phân tích b ng đơn hình b ưc 2 Bng b ưc 2 cĩ th đưc phân tích t ươ ng t nh ư b ng b ưc 1. C n chú ý r ng lúc này ta đang v trí c a đim C(15, 0) vì x 1 = 15 cịn x 2 = 0; giá tr c a hàm m c tiêu là z0 = 120 đã đưc c i thi n h ơn so v i b ưc 1. Ta th y ∆2 = 2 > 0 nên cịn cĩ th c i thi n hàm m c tiêu b ng cách ch n bi n x 2 làm bi n c ơ s m i. Th c hi n các b ưc xoay sang ph ươ ng án c c biên k t t h ơn, chúng ta s cĩ b ng đơn hình b ưc 3. Phân tích b ng đơn hình b ưc 3 Ti b ng đơn hình b ưc 3 ta th y điu ki n ti ưu đã đưc tho mãn ( ∆j ≤ 0 ∀j=1, 2, 3, 4) nên khơng cịn kh n ăng c i thi n ph ươ ng án. Ph ươ ng án t i ưu đã đt đưc t i x 1 = 12, x 2 = 6, x 3 = 0, x 4 = 0, t c là t i đim c c biên B(12, 6) v i giá tr z max = 132. Khung thu t tốn đơn hình gi i BTQHTT d ng chính t c Sau đây là khung thu t tốn c a ph ươ ng pháp đơ n hình đưc phát bi u cho BTQHTT c c đ i hĩa d ng chính t c. Bưc kh i t o - Tìm m t ph ươ ng án c c biên ban đu. - Tính ∆j = c j - z j, ∀j = 1,n , trong đĩ n là s bi n c a bài tốn đang xét. Các b ưc l p
Bưc 1: Ki m tra điu ki n t i ưu. N u điu ki n t i ưu ∆j = c j - z j ≤ 0, ∀j = 1,n đã đưc tho mãn thì in/l ưu tr k t qu c a bài tốn và chuy n sang b ưc k t thúc. Bưc 2: N u t n t i m t ch s j sao cho ∆j > 0 thì ti n hành th t c xoay g m n ăm bưc đã bi t, tính l i các ∆j, ∀j = 1,n và quay l i b ưc 1 ( Chú ý: Trong tr ưng h p ta tìm đưc c t xoay mà khơng tìm đưc hàng xoay thì k t lu n hàm m c tiêu khơng b ch n, in/l ưu tr k t qu c a bài tốn và chuy n sang b ưc k t thúc). Bưc k t thúc . D ng. Chú ý: - ði v i các BTQHTT c n c c ti u hĩa hàm m c tiêu thì điu ki n t i ưu (hay tiêu chu n d ng) là ∆j ≥ 0 ∀j (n u t n t i j mà ∆j ≤ 0 thì c n ti p t c c i thi n hàm m c tiêu bng cách ch n ct j làm c t xoay ). - Trong th c ti n gi i các BTQHTT d ng t ng quát cĩ th x y ra tr ưng h p khơng tìm đưc ph ươ ng án xu t phát. Lúc này cĩ th k t lu n mơ hình đã thi t l p cĩ các điu ki n ràng bu c quá ch t ch , c n xem xét n i l ng các điu ki n này. - Trong tr ưng h p ta tìm đưc c t xoay mà khơng tìm đưc hàng xoay thì k t lu n hàm m c tiêu khơng b ch n trên ( đi v i các BTQHTT d ng Max) ho c khơng b ch n dưi ( đ i v i các BTQHTT d ng Min). Khi đĩ d ng quá trình gi i và k t lu n mơ hình quy ho ch tuy n tính đã thi t l p khơng phù h p v i th c t . 1.3. Ph ươ ng pháp đơ n hình hai pha gi i BTQHTT d ng t ng quát ðư a BTQHTT v d ng chính t c Ví d 1: (Tr ưng h p các ràng bu c đ u cĩ d u ≤) z = 8x 1 + 6x 2 → Max vi các ràng bu c: 4x+ 2x ≤ 60  1 2 2x1+ 4x 2 ≤ 48  x1 , x 2 ≥ 0. ðư a BTQHTT v d ng chính t c nh ư đã bi t b ng cách thêm hai bi n bù ( slack variables ) x 3 và x 4. Ta cĩ BTQHTT d ng chính t c là: z = 8x 1 + 6x 2 + 0x 3 + 0x 4 → Max 4x+ 2x + x = 60  1 2 3 2x1+ 4x 2 + x 4 = 48  x,x,x,x1 2 3 4 ≥ 0. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 22
Lúc này, trong h hai điu ki n ràng bu c đã cĩ đ hai bi n đ ng đc l p trong t ng ph ươ ng trình v i h s +1, nên đã cĩ th tìm đưc ph ươ ng án c c biên xu t phát đ b t đu quá trình gi i bài tốn. Ví d 2: (Tr ưng h p cĩ bi n khơng d ươ ng) z = 8x 1 − 6x 2 → Max vi các ràng bu c: 4x+ 2x + x ≤ 60  1 2 3 2x1+ 4x 2 + x 4 ≤ 48  x1≥ 0, x 2 ≤ 0, x 3 ≥ 0, x 4 ≥ 0. Lúc này mu n gi i bài tốn b ng ph ươ ng pháp đơ n hình ta ph i đ i bi n x' 2 = −x2. Ta cĩ BTQHTT v i các bi n đ u khơng âm. z = 8x 1 + 6x' 2 → Max vi các ràng bu c: 4x− 2x' + x ≤ 60  1 2 3 2x1− 4x' 2 + x 4 ≤ 48  x,x',x,x1 2 3 4 ≥ 0. Ví d 3: (Tr ưng h p cĩ bi n v i d u tu ỳ ý) z = 8x 1 + 6x 2 → Max vi các ràng buc: 4x+ 2x ≤ 60  1 2 2x1+ 4x 2 ≤ 48  x1≥ 0, x 2 . cĩ d u tu ỳ ý. Lúc này ta vi t bi n x 2 d ưi d ng x 2 = x' 2 − x'' 2 v i x '= max[0, x ] x '≥ 0  2 2 thì đm b o  2 x ''2= max[0, − x 2 ] x ''2 ≥ 0. Các ràng bu c s là 4x+ 2x' − 2x'' += x 60  1 2 23 2x1+ 4x' 2 − 4x' 24 += x 48  x,x',x'',x,x1 2 234 ≥ 0. Bài tốn v i hàm m c tiêu là: z = 8x 1 + 6x' 2 − 6x'' 2 + 0x 3 + 0x 4 và các điu ki n ràng bu c trên là BTQHTT d ng chính t c. Ví d 4: (Tr ưng h p cĩ điu ki n ràng bu c v i d u ≥ ho c d u =)
z = 8x 1 + 6x 2 → Max vi các ràng bu c: 4x+ 2x ≤ 60  1 2 (a) 2x1+ 4x 2 ≥ 48  x1≥ 0, x 2 ≥ 0. Ta thêm các bi n bù x 3 ( slack variable ) mang d u “+”, x 4 ( surplus variable ) mang du “ −” đ cĩ h điu ki n ràng bu c sau (lúc này hai ràng bu c đ u cĩ d u =): 4x+ 2x + x = 60  1 2 3 (b) 2x1+ 4x 2 − x 4 = 48  x,x,x,x1 2 3 4 ≥ 0. Ph i thêm bi n gi x 5 (x 5 g i là l ưng vi ph m c a ph ươ ng trình th hai) đ đưc h điu ki n ràng bu c 4x+ 2 x + x = 60  1 2 3 (c) 24x1+ x 2 − x 4 + x 5 = 48  xx1, 2 , x 3 , x 4 , x 5 ≥ 0. Lúc này, đã cĩ đ hai bi n đ ng đ c l p trong t ng ph ươ ng trình v i h s +1, nên đã cĩ th tìm đưc ph ươ ng án c c biên xu t phát đ b t đ u quá trình gi i bài tốn b ng ph ươ ng pháp đơ n hình v i hàm m c tiêu là z = 8x 1 + 6x 2 + 0x 3 + 0x 4 − Mx 5 → Max, trong đĩ M ≈ + ∞ và bi u th c −Mx 5 g i là l ưng ph t ( đánh thu ). Bài tốn đã đưc đư a v d ng chính t c. L ưng vi ph m x 5 càng l n thì hàm m c tiêu càng gi m, giá tr ca hàm m c tiêu ch cĩ th đ t Max khi x 5 = 0. Kt lu n: Bao gi c ũng đưa đưc BTQHTT b t kì (các bi n cĩ d u tu ỳ ý, các ràng bu c cĩ th ≤, ≥, =) v d ng chính t c. Ph ươ ng pháp đơ n hình m r ng Ph ươ ng pháp đơ n hình m r ng cịn g i là ph ươ ng pháp đánh thu M đưc áp d ng đ đ gi i BTQHTT cĩ bi n gi . Ví d 5: Sau khi thêm vào các bi n bù và bi n gi , BTQHTT trong ví d 4 đưc đư a v d ng chính t c (trong hàm m c tiêu t t c các bi n gi đ u cĩ h s là -M nên bài tốn đưc g i là bài tốn M). Max z = 8x 1 + 6x 2 +0x 3 + 0x 4 − Mx 5 (trong đĩ M ≈ + ∞) v i các ràng bu c 4x+ 2x + x = 60  1 2 3 (c)2x 1+ 4x 2 − x 45 + x = 48  x,x,x,x,x1 2 3 4 5 ≥ 0. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 24
Cách 1: Cĩ th gi i BTQHTT v i các điu ki n ràng bu c (a) b ng ph ươ ng pháp đ th đ nh n đưc k t qu : ph ươ ng án t i ưu là (x 1 = 0, x 2 = 30) và z max = 180. Cách 2: Gi i BTQHTT v i các điu ki n ràng bu c (c) b ng cách l p b ng đơn hình nh ư thơng thưng nh ưng chú ý h s M ≈ + ∞ (xem b ng II.2). Ti b ng đơn hình cu i cùng, ta th y ∆j ≤ 0 ∀j nên ph ươ ng án t i ưu đã đt đưc vi x 2 = 30, x 4 = 72, các x j khác = 0 và z Max = 180. Chú ý: − Khi m t bi n gi đã đưc đưa ra kh i c ơ s thì khơng bao gi quay li n a. Do đĩ ta cĩ th xố c t bi n gi đĩ kh i b ng đơn hình. − N u d u hi u d ng xu t hi n ( ∆j ≤ 0 ∀j) nh ưng v n cịn bi n gi v i giá tr d ươ ng trong s các bi n c ơ s thì điu này ch ng t bài tốn ban đu khơng th cĩ ph ươ ng án kh thi (cĩ th ch ng minh b ng ph n ch ng). Bng II.2. Các b ng đơn hình gi i bài tốn M H s hàm m c Ph ươ ng 8 6 0 0 −M Bi n c ơ s tiêu án x1 x2 x3 x4 x5 0 x3 60 4 2 1 0 0 −M x5 48 2 4 0 −1 +1 Hàng z z0 = −48M z1 = −2M z2 = −4M z3 = 0 z4 = M z5 = −M Hàng ∆j ∆1 = 8+2M ∆2 = 6+4M ∆3 = 0 ∆4 = −M ∆5 = 0 0 x3 36 3 0 1 1/2 −1/2 6 x2 12 1/2 1 0 −1/4 1/4 Hàng z 72 3 6 0 −3/2 3/2 Hàng ∆j 5 0 0 3/2 −M − 3/2 0 x4 72 6 0 2 1 −1 6 x2 30 2 1 1/2 0 0 Hàng z 180 12 6 3 0 0 Hàng ∆j −4 0 −3 0 −M Ph ươ ng pháp đơ n hình hai pha Vi ví d trên (xem b ng II.2) ta th y quá trình gi i chia làm hai pha: pha 1 nh m gi i bài tốn M cho t i khi bi n gi (x 5) đưc đưa ra kh i s bi n c ơ s (lúc này cĩ ph ươ ng án c c biên xu t phát cho bài tốn (b)) và pha 2 nh m tìm ph ươ ng án t i ưu cho bài tốn (b). Ph ươ ng pháp đơ n hình m r ng nh ư trình bày trên đây cĩ khĩ kh ăn trong vi c khai báo giá tr c a h s M ≈ + ∞ và tính tốn các giá tr ∆j liên quan t i h s M. ð kh c ph c các đim này, chúng ta xét ph ươ ng pháp đơ n hình hai pha: pha 1 nh m gi i bài
tốn ω đ tìm cách đư a các bi n gi ra kh i s bi n c ơ s (lúc này cĩ ph ươ ng án c c biên xu t phát cho bài tốn (b)) và pha 2 nh m tìm ph ươ ng án t i ưu cho bài tốn (b). Ví d 6: Xét BTQHTT (bài tốn 1) z = 8x 1 + 6x 2 → Max, v i các ràng bu c: 4x+ 2x ≤ 60  1 2 (a) 2x1+ 4x 2 ≥ 48  x1 , x 2 ≥ 0, hay BTQHTT d ng chu n t c (bài tốn 2) t ươ ng đươ ng v i nĩ là: z = 8x 1 + 6x 2 +0x 3 + 0x 4 → Max, v i các ràng bu c 4x+ 2x + x = 60  1 2 3 (b) 2x1+ 4x 2 − x 4 = 48  x,x,x,x1 2 3 4 ≥ 0. ð tìm ph ươ ng án c c biên xu t phát cho BTQHTT d ng chu n t c trên đây chúng ta c n th c hi n pha 1 (hàm m c tiêu ω là t ng c a t t c các bi n gi ). Pha 1: Gi i bài tốn ω (bài tốn 3): ω = x 5 → Min, v i các ràng bu c 4x+ 2x + x = 60  1 2 3 (c)2x 1+ 4x 2 − x 45 + x = 48  x,x,x,x,x1 2 3 4 5 ≥ 0. Bng II.3. Các b ng đơn hình pha 1 H s hàm Ph ươ ng 0 0 0 0 1 Bi n c ơ s mc tiêu án x1 x2 x3 x4 x5 0 x3 60 4 2 1 0 0 1 x5 48 2 4 0 −1 +1 Hàng z z0 = 48 z1 = 2 z2 = 4 z3 = 0 z4 = −1 z5 = 1 Hàng ∆j ∆1 = −2 ∆2 = −4 ∆3 = 0 ∆4 = 1 ∆5 = 0 0 x3 36 3 0 1 1/2 −1/2 0 x2 12 1/2 1 0 −1/4 1/4 Hàng z 0 0 0 0 0 0 Hàng ∆j 0 0 0 0 1 Nh ư v y trong ví d này, nh ư trình bày trong b ng II.3, sau hai b ưc chúng ta đã tìm đưc ph ươ ng án t i ưu cho bài tốn ω. M t cách t ng quát khi gi i xong bài tốn ω cĩ th x y ra ba tr ưng h p sau đây: Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 26
− Tr ưng h p 1: Tìm đưc ph ươ ng án t i ưu c a bài tốn ω v i giá tr ωMin = 0, khơng ch a các bi n gi trong s các bi n c ơ s (nh ư trong ví d trên). − Tr ưng h p 2: Tìm đưc ph ươ ng án t i ưu c a bài tốn ω v i giá tr ωMin = 0, cĩ ch a các bi n gi trong s các bi n c ơ s (lúc này các bi n gi n m trong c ơ s đ u cĩ giá tr b ng 0). − Tr ưng h p 3: Tìm đưc ph ươ ng án t i ưu c a bài tốn ω v i giá tr ωMin > 0, cĩ ch a các bi n gi trong s các bi n c ơ s (lúc này cĩ m t s bi n gi n m trong c ơ s đu cĩ giá tr d ươ ng). Cĩ th ch ng minh đưc r ng trong tr ưng h p 1, bài tốn 2 cĩ ph ươ ng án c c biên xu t phát nh ư tìm đưc trong b ng đơn hình t i ưu sau khi g ch b đi t t c các c t bi n gi . Trong tr ưng h p 2, bài tốn 2 cĩ ph ươ ng án c c biên xu t phát nh ư tìm đưc trong bng đơn hình t i ưu sau khi g ch b đi t t c các c t bi n gi và các hàng ch a bi n gi (các hàng b g ch đi t ươ ng ng v i các ph ươ ng trình ph thu c tuy n tính vào các ph ươ ng trình cịn l i trong h điu ki n ràng bu c c a BTQHTT d ng chu n t c). Cịn trong tr ưng h p 3, BTQHTT d ng chính t c khơng cĩ ph ươ ng án kh thi nên c ũng khơng cĩ ph ươ ng án t i ưu. Trong các tr ưng h p 1 và 2, chúng ta c n chuy n sang pha 2 đ ti p t c đi tìm ph ươ ng án t i ưu cho bài tốn 2 t ph ươ ng án c c biên xu t phát tìm đưc b ng cách thay các h s hàm m c tiêu và tính l i các giá tr c a hàng z j và hàng ∆j. Pha 2: Xét bài tốn 2: z = 8x 1 + 6x 2 +0x 3 + 0x 4 → Max, v i các ràng bu c 4x+ 2x + x = 60  1 2 3 (b) 2x1+ 4x 2 − x 4 = 48  x,x,x,x1 2 3 4 ≥ 0, Hay BTQHTT d ng chính t c t ươ ng đươ ng v i nĩ: z = 8x 1 + 6x 2 +0x 3 + 0x 4 → Max, v i các ràng bu c 1 3x1+ 0x 2 + 3x 3 +2 x 4 = 36  1 1 (b)′  2 x12++ x 0x 3 − 4 x 4 = 12  x,x,x,x1 2 3 4 ≥ 0. Các b ng đơ n hình c a pha 2 đưc trình bày trong b ng II.4. Bng II.4. Các b ng đơn hình pha 2 H s hàm Bi n Ph ươ ng 8 6 0 0 mc cơ s tiêu án x1 x2 x3 x4 0 x3 36 3 0 1 1/2 6 x2 12 1/2 1 0 −1/4
Hàng z 72 3 6 0 −3/2 Hàng ∆j 5 0 0 3/2 0 x4 72 6 0 2 1 6 x2 30 2 1 1/2 0 Hàng z 180 12 6 3 0 Hàng ∆j −4 0 −3 0 Chú ý: So sánh các b ng II.3 và II.4 v i b ng II.2, cĩ th th y r ng ph ươ ng pháp hai pha và ph ươ ng pháp đơ n hình m r ng th c ch t là hồn tồn t ươ ng đươ ng v i nhau. Nh ưng l p trình tính tốn d a trên ph ươ ng pháp hai pha là d dàng h ơn nhi u do tránh đưc vi c khai báo giá tr c a h s M ≈ + ∞ và tính tốn các giá tr ∆j khơng liên quan ti h s M. 1.4. Ph ươ ng pháp c t Gomory gi i BTQHTT nguyên Ví d 7. Xét BTQHTT nguyên: Max z = x 1 + 4x 2 vi các ràng bu c 2x 1 + 4x 2 ≤ 7 10x 1 + 3x 2 ≤ 15 x 1, x 2 ≥ 0 x 1, x 2 nguyên. Cn tìm các giá tr nguyên c a các bi n quy t đ nh x 1, x 2 đ các ràng bu c đưc tho mãn và hàm m c tiêu đt giá tr l n nh t. Dng t ng quát c a BTQHTT nguyên c ũng gi ng nh ư d ng t ng quát c a BTQHTT đã nêu trong m c 1.1, cĩ b sung thêm điu ki n nguyên c a các bi n quy t đ nh. ðư a BTQHTT nguyên trên đây v d ng chính t c. Max z = x 1 + 4x 2 + 0x 3 + 0x 4, v i các ràng bu c 2x 1 + 4x 2 + x 3 = 7 (a) 10x 1 + 3x 2 + x 4 = 15 x1, x 2, x 3, x 4 ≥ 0 x1, x 2, x 3, x 4 nguyên. Tr ưc h t ta gi i BTQHTT khơng nguyên t ươ ng ng, t c là t m th i b qua điu ki n nguyên c a các bi n (xem b ng II.5). Bng II.5. Các b ng đơn hình gi i BTQHTT nguyên H s hàm Bi n c ơ s Ph ươ ng án c1 = 1 c2 = 4 c3 = 0 c4 = 0 Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 28
mc tiêu c j x1 x2 x3 x4 Bng đơn hình b ưc 1 0 x3 7 2 4 1 0 0 x4 15 10 3 0 1 Hàng z z0 = 0 z1 = 0 z2 = 0 z3 = 0 z4 = 0 Hàng ∆j = c j - z j ∆1 = 1 ∆2 = 4 ∆3 = 0 ∆4 = 0 Bng đơn hình b ưc 2 4 x2 7/4 1/2 1 1/4 0 0 x4 39/4 17/2 0 - 3/4 1 Hàng z z0 = 7 z1 = 2 z2 = 4 z3 = 1 z4 = 0 Hàng ∆j = c j - z j ∆1 = - 1 ∆2 = 0 ∆3 = - 1 ∆4 = 0 Nh ư v y, ph ươ ng án t i ưu b ưc 2 ch ưa th a mãn điu ki n nguyên. T i b ng đơn hình b ưc 2 c a b ng II.5, BTQHTT nguyên đã đưc bi n đ i t ươ ng đươ ng v d ng sau: Max z = x 1 + 4x 2 + 0x 3 + 0x 4, v i các ràng bu c 1 1 7 x1 + x 2 + x3 = 2 4 4 17 3 39 (b) x1 + - x2 + x 4 = 2 4 4 x1, x 2, x 3, x 4 ≥ 0 ; x1, x 2, x 3, x 4 nguyên. Xét ph ươ ng trình (xem b ng đơn hình b ưc 2 c a b ng II.5): 1 1 7 1 1 7 x+ x + x = ⇔ x+ x + x = . 21 2 4 3 4 22 1 4 3 4 Mt cách t ng quát chúng ta cĩ th vi t: x+∑ zx = z , trong đĩ J là t p các r rjrj 0 N j∈ j N ch s t ươ ng ng v i các bi n ngồi c ơ s . Cịn x r là bi n c ơ s n m trong ph ươ ng trình đang xét. Gi s z= z  + f v i z  là ph n nguyên và f là ph n l c a z . Lúc rj r j  r j rj  rj rj đĩ cĩ: x+∑ ([z]f)x + =+ [z]f ⇔ x+∑ [z]x −=− [z]f ∑ fx . r rrjrrjj 00 r rjrrj 00 xj j j∈ j N jj∈N jj ∈ N V trái b t bu c là s nguyên theo điu ki n c a BTQHTT nguyên nên v ph i ph i là s nguyên nh h ơn 1 (do v ph i f < 1). V y v ph i luơn nh h ơn ho c b ng 0. r0 Trong ví d trên ta cĩ: x+∑ [z]x[z]f −=− ∑ fx . N u đ t v ph i 2 2j22j 00 xj j j∈ {1,3} j ∈ {1,3} là - x 5 (v i điu ki n x 5 nguyên và x 5 ≥ 0) thì cĩ ph ươ ng trình m i sau đây: 1 1 3 −∑ fxx +=−⇔− f x − xx +=− . 2j52j 0 1 35 j∈ {1,3} 2 4 4 Do ph ươ ng trình trên đây là h qu c a các điu ki n ràng bu c c a BTQHTT nguyên, nên khi đưc b sung vào các điu ki n ràng bu c, mi n ph ươ ng án c a BTQHTT nguyên khơng thay đi và do đĩ BTQHTT nguyên đưc đưa v d ng sau:
Max z = x 1 + 4x 2 + 0x 3 + 0x 4, v i các ràng bu c 1 1 7 x1 + x 2 + x3 = 2 4 4 17 3 39 (c) x1 + - x2 + x 4 = 2 4 4 1 1 3 - x1 - x3 + x 5 = − 2 4 4 x1, x 2, x 3, x 4, x 5 ≥ 0 ; x1, x 2, x 3, x 4 nguyên . Lúc này, chúng ta cĩ b ng đơn hình II.6 v i ph ươ ng án đi ng u kh thi (ph ươ ng án đi ng u kh thi là ph ươ ng án cĩ th khơng th a mãn điu ki n khơng âm c a các bi n, nh ưng luơn th a mãn các điu ki n ràng bu c cịn l i c a BTQHTT và điu ki n ∆j ≤ 0 vi m i ch s j). Chúng ta s s d ng th t c xoay c a ph ươ ng pháp đơ n hình đi ng u đ tìm ph ươ ng án ( đi ng u kh thi) t i ưu th a mãn điu ki n ∆j ≤ 0 v i m i ch s j (xem b ng đơn hình b ưc 3 c a b ng II.6). Chú ý: Th t c xoay trong ph ươ ng pháp đơ n hình đi ng u cĩ n ăm b ưc, bao g m: - Tr ưc tiên ch n hàng xoay là hàng v i bi n x j cĩ giá tr âm (thơng th ưng v i tr tuy t đ i l n nh t, ho c ch n ng u nhiên). - Sau đĩ ch n c t xoay theo quy t c “t s âm bé nh t” ( ng v i t s bé nh t trong các t s cĩ m u s âm đưc t o ra b ng cách l y hàng ∆j “chia” cho hàng x j, ch xét các t s cĩ m u s âm). N u khơng tìm đưc c t xoay thì k t lu n bài tốn khơng cĩ ph ươ ng án kh thi. - N u tìm đưc c t xoay thì th c hi n ba b ưc ti p theo c a th t c xoay nh ư trong phươ ng pháp đơ n hình gi i BTQHTT. Bng II.6. Các b ng đơn hình gi i BTQHTT nguyên (ti p) H s hàm Bi n c ơ 1 4 0 0 0 Ph ươ ng án mc tiêu s x1 x2 x3 x4 x5 Bng đơn hình b ưc 3 4 x2 7/4 1/2 1 1/4 0 0 0 x4 39/4 17/2 0 - 3/4 1 0 0 x5 - 3/4 - 1/2 0 - 1/4 0 1 zj 2 4 1 0 0 7 ∆j - 1 0 - 1 0 0 Bng đơn hình b ưc 4 4 x2 1 0 1 0 0 1 0 x4 - 3 0 0 - 5 1 17 Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 30
1 x1 3/2 1 0 1/2 0 - 2 zj 1 4 1/2 0 2 11/2 ∆j 0 0 - 1/2 0 - 2 Bng đơn hình b ưc 5 4 x2 1 0 1 0 0 1 0 x3 3/5 0 0 1 - 1/5 - 17/5 1 x1 6/5 1 0 0 1/10 - 3/10 zj 1 4 0 1/10 37/10 26/5 ∆j 0 0 0 - 1/10 - 37/10 Ta nh n th y: ph ươ ng án t i ưu ch ưa th a mãn điu ki n nguyên. Xét ph ươ ng trình th 3 trong b ng đơn hình th 5 c a b ng II.6 đ làm c ơ s cho vi c đưa vào điu ki n 1 7 1 ràng bu c b sung: −x − x +=− x . Sau đĩ, ti p t c quá trình gi i s d ng 104 10 5 6 5 ph ươ ng pháp đơ n hình đi ng u (xem b ng II.7): Bng II.7. Các b ng đơn hình gi i BTQHTT nguyên (ti p) H s hàm Bi n c ơ 1 4 0 0 0 0 Ph ươ ng án mc tiêu s x1 x2 x3 x4 x5 x6 Bng đơn hình b ưc 6 4 x2 1 0 1 0 0 1 0 0 x3 3/5 0 0 1 - 1/5 - 17/5 0 1 x1 6/5 1 0 0 1/10 - 3/10 0 0 x6 - 1/5 0 0 0 - 1/10 - 7/10 1 zj 1 4 0 1/10 37/10 0 26/5 ∆j 0 0 0 - 1/10 -37/10 0 Bng đơn hình b ưc 7 4 x2 1 0 1 0 0 1 0 0 x3 1 0 0 1 0 - 2 - 2 1 x1 1 1 0 0 0 - 1 1 0 x4 2 0 0 0 1 7 - 10 zj 1 4 0 0 3 1 5 ∆j 0 0 0 0 - 3 - 1 Ph ươ ng án t i ưu b ng đơn hình b ưc 7 c a b ng II.7 đã th a mãn điu ki n ∗ ∗ nguyên. V y ph ươ ng án t i ưu c a BTQHTT nguyên là x1 = 1, x2 = 1 và z max = 5. Khung thu t tốn c t Gomory Xét BTQHTT nguyên Max z = c 1x1 + c 2x2 + + c nxn
vi h điu ki n ràng bu c ax11 1 + ax 12 2 ++ ax 1n n = b 1  ax21 1 + ax 22 2 ++ ax 2n n = b 2  axm11+ a m22 x ++ a mnn x = b m  xj≥ 0, x j nguyên, ∀ j = 1,n. Kí hi u D là mi n ràng bu c c a BTQHTT khơng tính t i điu ki n nguyên c a các bi n. Lúc đĩ, khung thu t tốn c t Gomory cĩ th đưc phát bi u nh ư sau cho BTQHTT nguyên d ng Max v i D là gi i n i khác r ng. Bưc kh i t o Gi i BTQHTT khơng nguyên t ươ ng ng b ng ph ươ ng pháp đơ n hình đ thu đưc ph ươ ng án t i ưu x 1. ðt k = 1. Các b ưc l p (b ưc l p th k) Bưc 1: N u x k cĩ các t a đ nguyên thì chuy n sang b ưc k t thúc. Bưc 2: N u trái l i x k cĩ ít nh t m t to đ khơng nguyên thì c n ch n ra m t bi n cơ s x r cĩ giá tr khơng nguyên đ xây d ng ràng bu c b sung. Bưc 3: Gi i bài tốn thu đưc b ng ph ươ ng pháp đơ n hình đi ng u đ tìm ra ph ươ ng án t i ưu. ðt k = k+1 và chuy n v b ưc 1 (N u trong quá trình gi i khơng tìm đưc c t xoay thì k t lu n BTQHTT nguyên ban đu khơng cĩ ph ươ ng án kh thi). Bưc k t thúc . In/l ưu tr k t qu và d ng. 1.5. M t s ng d ng c a ph ươ ng pháp đơ n hình Bài tốn phân ph i đin n ăng Cĩ ba h ph t i c n đưc cung c p đin n ăng t hai ngu n đin n m cách xa nhau. Giá thành truy n t i m t đơn v đin n ăng t ngu n i đ n h tiêu th j là c ij . Kh n ăng cung c p đin n ăng c a m i ngu n b gi i h n b i tr l ưng hi n cĩ c a chúng là A 1 và A2. Nhu c u tiêu dùng c a các h tiêu th là B 1, B 2 và B 3. G i x ij là l ưng đin n ăng đưc đưa t ngu n i t i h tiêu th j. C n ph i xác đ nh các x ij sao cho t ng chi phí là nh nh t. Nh ư v y ta cĩ BTQHTT sau: 2 3 z = ∑∑ cij x ij → Min i= 1 j1 = vi các điu ki n ràng bu c là: x11 + x 12 + x 13 ≤ A 1, x 21 + x 22 + x 23 ≤ A 2, x 11 + x 21 = B 1, x12 + x 22 = B 2, x 13 + x 23 = B 3, Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 32
xij ≥ 0, ∀i = 1, 2 và ∀j = 1, 2, 3. Bài tốn phân t i cho máy Mt xí nghi p cĩ hai lo i máy M 1 và M 2. Các lo i máy này cĩ th s n xu t đưc ba lo i s n ph m P 1, P 2 và P 3 v i các n ăng su t là a ij, ch ng h n máy M 1 s n xu t s n ph m P2 v i n ăng su t a 12 . M i đơn v s n ph m mang l i lãi su t c j v i j = 1, 2, 3. M i tháng xí nghi p ph i s n xu t s n ph m lo i j khơng ít hơn b j đơ n v và khơng v ưt quá d j đơ n v, j = 1, 2, 3. Hãy l p k ho ch phân t i cho các máy sao cho đ t t ng l i nhu n l n nh t. D th y bài tốn này d n t i BTQHTT sau: 3 2 z = ∑cj ∑ a ij x ij → Max j1= i1 = vi các điu ki n ràng bu c: a11 x11 + a 21 x21 ≥ b 1, a 12 x12 + a 22 x22 ≥ b 2, a 13 x13 + a 23 x23 ≥ b 3, a11 x11 + a 21 x21 ≤ d 1, a 12 x12 + a 22 x22 ≤ d 2, a 13 x13 + a 23 x23 ≤ d 3, x11 + x 12 + x 13 ≤ m 1, x 21 + x 22 + x 23 ≤ m 2, xij ≥ 0, i = 1, 2 và j = 1, 2, 3. (trong đĩ m 1 và m 2 là t ng th i gian ch y máy M 1 và M 2). Trong các l ĩnh v c quy ho ch s n xu t hay qu n lí kinh doanh, nĩi riêng trong ngành c ơ khí và đin l c, BTQHTT đưc ng d ng r t r ng rãi và mang l i hi u qu cn thi t. Gi i mơ hình quy ho ch tuy n tính b ng các ph n m m tính tốn Hi n nay cĩ nhi u ph n m m tính tốn gi i BTQHTT khá hi u qu nh ư Excel, Lingo. Nh ng ph n m m này r t thân thi n v i ng ưi dùng. Tuy nhiên c n nh n m nh rng, vi c phát bi u đưc mơ hình bài tốn và phân tích, đánh giá đưc k t qu m i chính là nh ng khâu quan tr ng nh t trong ph ươ ng pháp mơ hình hố. Sau đây, chúng ta dùng ph n m m Lingo đ gi i ví d đã xét trên. z = 8x 1 + 6x 2 → Max vi các ràng bu c: 4x 1 + 2x 2 ≤≤≤ 60 2x 1 + 4x 2 ≤≤≤ 48 x1, x 2 ≥ 0. ð gi i bài tốn này, chúng ta c n cài đt Lingo vào trong máy tính. Nh n vào bi u tưng Lingo trên màn hình đ vào c a s Lingo. Sau đĩ th c hi n các l nh Lingo: Menu > New > và gõ vào các d li u c a bài tốn nh ư hình II.4.
Hình II.4. Nh p d li u c a bài tốn quy ho ch tuy n tính trong Lingo Ti p theo, c n nháy chu t vào nút LINGO và gi i bài tốn đ thu đưc k t qu chi ti t nh ư trên hình II.5. Hình II.5. K t qu gi i bài tốn quy ho ch tuy n tính trong Lingo Kt qu chi ti t cho ta bi t giá tr c c đ i c a hàm m c tiêu là 132 v i ph ươ ng án t i ưu là: x 1 = 12, x 2 = 6. Các giá tr t i ưu c a các bi n đ i ng u là y 1 = 5/3 và y 2 = 2/3 (cịn g i là các giá ưc đ nh hay giá bĩng Shadow Prices ). 2. MƠ HÌNH QUY HO CH TUY N TÍNH ðA M C TIÊU 2.1. Các khái ni m c ơ b n Trong các bài tốn kĩ thu t, cơng ngh , qu n lí, kinh t nơng nghi p v.v n y sinh t th c t , chúng ta th ưng ph i xem xét đ t i ưu hĩa đng th i m t lúc nhi u m c tiêu. Các m c tiêu này th ưng là khác v th nguyên, t c là chúng đưc đo b i các đơn v khác nhau. Nh ng tình hu ng nh ư v y t o ra các bài tốn t i ưu đa m c tiêu. Nh ư vy, chúng ta c n ph i t i ưu hĩa (c c đ i hĩa ho c c c ti u hĩa tu ỳ theo tình hu ng Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 34
th c t ) khơng ph i là ch m t m c tiêu nào đĩ, mà là đng th i t t c các m c tiêu đã đt ra. Cĩ th nĩi, BTQHTT đa m c tiêu là BTQHTT mà trong đĩ chúng ta ph i t i ưu hĩa cùng m t lúc nhi u m c tiêu. Tuy nhiên, các m c tiêu này th ưng đ i ch i c nh tranh vi nhau. Vi c làm t t h ơn m c tiêu này th ưng d n t i vi c làm x u đi m t s m c tiêu khác. Vì v y vi c gi i các bài tốn t i ưu đa m c tiêu, t c là tìm ra m t ph ươ ng án kh thi t t nh t theo m t ngh ĩa nào đĩ, th c ch t chính là m t bài tốn ra quy t đ nh. Hi n t i các tài li u, sách chuyên kh o, t p chí c p nh t v l ĩnh v c liên ngành Tốn − Tin, Khoa h c qu n lí. Cơng ngh thơng tin, đ c p nhi u t i bài tốn t i ưu đa m c tiêu. V n đ nghiên c u c ơ s lí thuy t, thu t tốn, l p mơ hình, xây d ng h máy tính tr giúp quy t đ nh và áp d ng các mơ hình t i ưu đa m c tiêu cho các quá trình cơng ngh , qu n lí là m t v n đ liên ngành đưc r t nhi u nhà khoa h c và kĩ sư th c hành quan tâm. Bài tốn t i ưu đa m c tiêu mà trong đĩ mi n ràng bu c D là t p l i đa di n và các mc tiêu z i = f i(X), v i i = 1, 2, , p, là các hàm tuy n tính xác đ nh trên D, đưc g i là bài tốn quy ho ch tuy n tính đa m c tiêu. Khi đĩ, ta cĩ mơ hình tốn h c sau đây đưc gi là mơ hình quy ho ch tuy n tính đa m c tiêu: n Max CX v i ràng bu c X ∈ D ⊂ R , trong đĩ: C là ma tr n c p p × n, D = {X = (x 1, n m x2, , x n) ∈ R : AX ≤ B}, A là ma tr n c p m×n và B ∈ R . Ví d 1: z1 = f 1(X) = 8x 1 + 6x 2 → Max z 2 = f 2(X) = x 1 + 3x 2 → Max T trong đĩ X = (x 1, x 2) , v i các ràng bu c: 4x 1 + 2x 2 ≤ 60 2x 1 + 4x 2 ≤ 48 x1, x 2 ≥ 0. Ta cĩ th vi t bài tốn này d ưi d ng ma tr n nh ư sau: Max CX v i ràng bu c 2 T T X ∈ D = {X ∈ R : AX ≤ B}, trong đĩ X = (x 1, x 2) , B = (60, 48, 0, 0) , cịn 4 2   8 6  2 4  C =   , A = . 1 3  −1 0    0 −1 Khái ni m then ch t trong t i ưu hĩa đa m c tiêu là khái ni m ph ươ ng án t i ưu Pareto, cịn g i là ph ươ ng án h u hi u ( efficient solution ). ðnh ngh ĩa 1: Mt ph ươ ng án t i ưu Pareto X * cĩ tính ch t sau đây:
− Tr ưc h t nĩ ph i thu c vào mi n các ph ươ ng án kh thi c a bài tốn, t c là ph i tho mãn t t c các ràng bu c: X * ∈ D. − V i m i ph ươ ng án kh thi khác X ∈ D mà cĩ m t m c tiêu nào đĩ t t h ơn (f i(X) * * tt h ơn f i(X )) thì c ũng ph i cĩ ít nh t m t m c tiêu khác x u h ơn (f j(X) x u h ơn f j(X ), j ≠ i). Ph ươ ng án X ∈ D đưc g i là ph ươ ng án Pareto y u n u v i m i ph ươ ng án kh thi khác X ∈ D mà cĩ m t m c tiêu nào đĩ t t h ơn (f i(X) t t h ơn f i( X )) thì c ũng ph i cĩ ít nh t mt m c tiêu khác khơng t t h ơn (f j(X) khơng t t h ơn f j( X ), j ≠ i). Nh ư v y, m t ph ươ ng án t i ưu Pareto c ũng là t i ưu Pareto y u, điu ng ưc l i khơng nh t thi t luơn đúng. ð nh n bi t t p ph ươ ng án t i ưu Pareto chúng ta c n t i các khái ni m sau: Tr ưc ht xét nĩn nĩn β c m sinh b i các véc t ơ gradient c 1, c 2, , c p c a các hàm m c tiêu, c 1, c2, , c p chính là các véc t ơ hàng c a ma tr n C. Cho x ∈ D. T p đim tr i t i x là t p ≥ ≥ n Dx = { x } ⊕C , v i C = {x = (x 1, x 2, , x n) ∈ R : Cx ≥ 0, Cx ≠ 0} là nĩn đi c c (đưc kí hi u là α trên hình II.6 trong ví d đang xét). Lúc đĩ, cĩ th ch ng minh đưc: x ∈ D là ph ươ ng án t i ưu Pareto khi và ch khi Dx ∩ D = { x }. Xét l i ví d đã cho trên đây. x2 c1(1,3) c (8,6) 2 O A(0, 12) α G B(12, 6) C(15,0) O x1 Hình II.6. Minh ho hình h c BTQHTT hai m c tiêu Mi n các ph ươ ng án kh thi D (mi n gi i h n b i t giác ABCD) đưc bi u th trên hình II.6, c 1(8, 6) là véc t ơ gradient và h ưng t ăng c a m c tiêu 1, cịn c 2(1, 3) là véc t ơ gradient và h ưng t ăng c a m c tiêu 2. Trên hình II.6, chúng ta cĩ th th y nĩn β là nĩn cm sinh b i các véc t ơ c 1 và c 2. Xét đim G ∈ AB, d dàng xác đnh đưc nĩn đ i c c Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 36
α và t p đim tr i t i G. D th y, t p h p P t t c các ph ươ ng án t i ưu Pareto bao g m các đim n m trên đon AB v i A(0, 12) và B(12, 6). 2.2. Ph ươ ng pháp t ng quát gi i BTQHTT đa m c tiêu ðnh ngh ĩa 2: Gi i bài tốn t i ưu tồn c c đa m c tiêu là ch n ra t t p h p P các ph ươ ng án t i ưu Pareto c a bài tốn m t (ho c m t s ) ph ươ ng án t t nh t (tho mãn nh t) theo m t ngh ĩa nào đĩ d a trên c ơ c u ưu tiên c a ng ưi ra quy t đ nh. Trong ví d trên, tu ỳ theo c ơ c u ưu tiên c a ng ưi ra quy t đ nh, chúng ta cĩ th ch n ra m t ho c m t s đim t i ưu Pareto n m trên AB làm ph ươ ng án t i ưu ca bài tốn. Cách 1: B ng m t phươ ng pháp t i ưu tốn h c thích h p tìm ra t p h p P t t c các ph ươ ng án t i ưu Pareto. Ng ưi ra quy t đ nh s đ ra c ơ c u ưu tiên c a mình đi vi t p P nh m tìm ra ph ươ ng án t i ưu Pareto tho mãn nh t cho bài tốn đa m c tiêu ban đu. Cách 2: Vi c tìm t p h p P trong tr ưng h p các bài tốn nhi u bi n là khá khĩ và mt nhi u th i gian. Vì v y, so v i cách 1, cách 2 s ti n hành theo trình t ng ưc l i. Tr ưc h t ng ưi ra quy t đ nh s đ ra c ơ c u ưu tiên c a mình. D a vào c ơ c u ưu tiên đĩ, các m c tiêu s đưc t h p vào m t m c tiêu duy nh t, tiêu bi u cho hàm t ng ti n ích c a bài tốn. Bài tốn t i ưu v i hàm m c tiêu t h p này s đưc gi i b ng m t ph ươ ng pháp t i ưu tốn h c thích h p, đ tìm ra m t (ho c m t s ) ph ươ ng án t i ưu Pareto. Lúc này, ng ưi ra quy t đ nh s ch n ra trong s các ph ươ ng án t i ưu Pareto đĩ mt ph ươ ng án t t nh t. Chúng ta s ti p t c phân tích cách th 2. Rõ ràng, ng ưi ra quy t đ nh khơng th đ ra c ơ c u ưu tiên c a mình m t cách chính xác ngay t đ u. Trong quá trình gi i bài tốn, trong m i b ưc l p, sau khi xem xét l i c ơ c u ưu tiên đã đ ra, c ũng nh ư ph ươ ng án trung gian v a tìm đưc, ng ưi ra quy t đ nh cĩ th d a vào các thơng tin đĩ đ thay đi l i c ơ c u ưu tiên c a mình. Sau đĩ, quá trình gi i l i đưc ti p tc, cho t i khi m t ph ươ ng án t i ưu cu i cùng đưc đưa ra. ðnh ngh ĩa 3: Ph ươ ng pháp gi i bài tốn t i ưu đa m c tiêu d a trên s tr giúp ca h máy tính, nh m giúp ng ưi ra quy t đ nh t ng b ưc thay đ i các quy t đ nh trung gian m t cách thích h p đ đi t i m t ph ươ ng án t i ưu Pareto tho mãn nh t, đưc g i là ph ươ ng pháp t ươ ng tác ng ưi − máy tính. Ph ươ ng pháp t ươ ng tác ng ưi − máy tính gi i bài tốn t i ưu đa m c tiêu cĩ các y u t c u thành sau: − C ơ c u ưu tiên c a ng ưi ra quy t đ nh và hàm t h p t ươ ng ng. − Ki u t ươ ng tác ng ưi − máy tính: cho bi t các thơng tin nào máy tính ph i đưa ra trong các b ưc l p trung gian và cách thay đi các thơng s c a c ơ c u ưu tiên t phía ng ưi ra quy t đ nh.
− Kĩ thu t t i ưu tốn h c đưc xây d ng d a trên lí thuy t t i ưu hĩa nh m tìm ra các ph ươ ng án t i ưu Pareto cho các bài tốn c n gi i trong các b ưc l p trung gian. Cho t i th i đim hi n nay, hàng ch c ph ươ ng pháp gi i BTQHTT đa m c tiêu đã đưc đ c p t i trong các t p chí chuyên ngành, mà đa s chúng đu cĩ nh ng ng d ng rt thành cơng trong nhi u l ĩnh v c, nh ư ph ươ ng pháp tham s , ph ươ ng pháp nĩn pháp tuy n, ph ươ ng pháp véc t ơ c c đ i, ph ươ ng pháp tr ng s t ươ ng tác c a Chebysev. Ph ươ ng pháp tho d ng m t ươ ng tác gi i BTQHTT đa m c tiêu do Nguy n H i Thanh đ xu t cĩ m t s ưu đim cho phép: − Quy các th nguyên khác nhau c a các hàm m c tiêu v cùng m t thang đo đ tho mãn c a ng ưi ra quy t đ nh. − T o ra m t quá trình t ươ ng tác ng ưi − máy tính đ tìm đưc nhi u ph ươ ng án ti ưu Pareto (hay ph ươ ng án t i ưu Pareto y u) đem l i nhi u l a ch n cho ng ưi ra quy t đ nh. 2.3. Ph ươ ng pháp tho d ng m t ươ ng tác gi i BTQHTT đa m c tiêu Bưc kh i t o i) Nh p s li u cho các hàm m c tiêu tuy n tính z i (i = 1, 2, , p) và m điu ki n ràng bu c. Gi i BTQHTT cho t ng m c tiêu z i (i = 1, 2, , p) v i mi n ràng bu c D đưc xác đ nh b i m ràng bu c ban đu đ thu đưc các ph ươ ng án t i ưu x 1, x 2, , x p (n u v i m t m c tiêu nào đĩ bài tốn khơng cho ph ươ ng án t i ưu thì c n xem xét đ ch nh s a l i các điu ki n ràng bu c ban đu). ii) Tính giá tr các hàm m c tiêu t i p ph ươ ng án x 1, x 2, , x p và l p b ng pay −off. B w B Xác đnh giá tr c n trên zi và giá tr c n d ưi zi ca m c tiêu z i (i =1, 2, , p), v i zi i w j = z i(x ) và zi = Min {z i(x ): j = 1, 2, , p}. iii) Xác đnh các hàm tho d ng m µ1(z 1), µ2(z 2), , µp(z p) cho t ng m c tiêu theo w zi− z i cơng th c: µi(z i ) =B w , i = 1, 2, , p. zi− z i 1 2 p (k) B iv) ðt: S P = {x , x , , x }, k = 1 và ai = zi v i i = 1, 2, , p. Các b ưc l p (xét b ưc l p th k) Bưc 1: i) Xây d ng hàm tho d ng t h p t các hàm tho d ng trên: u = w 1µ1(z 1) + w 2µ2(z 2) + + w pµp(z p) → Max Trong đĩ: w 1, w 2, , w p là các tr ng s (ph n ánh t m quan tr ng c a t ng hàm tho dng trong thành ph n hàm tho d ng t h p) đưc ng ưi gi i l a ch n tho mãn điu ki n: Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 38
w1 + w 2 + + w p = 1 và 0 ≤ w 1, w 2, , w p ≤ 1. ii) Gi i BTQHTT v i hàm tho d ng t h p v i m ràng bu c ban đu và p ràng (k) bu c b sung z i(x) ≤ ai , i = 1, 2, , p, đ tìm đưc ph ươ ng án t i ưu c a b ưc l p th (k) k là x và giá tr c a các hàm m c tiêu z i c ũng nh ư c a các hàm tho d ng µi(z i) (v i i =1, 2, , p). Bưc 2: i) N u µmin = Min {µi(z i): i = 1, 2, , p} bé h ơn m t ng ưng t nào đĩ (t đưc l a ch n trong đon [0, 1] và cĩ th đưc s a ch nh l i trong quá trình gi i bài tốn) thì ph ươ ng án tìm đưc x (k) khơng đưc ch p nh n. Trong tr ưng h p trái l i, ph ươ ng án (k) x đưc ch p nh n vào t p S P các ph ươ ng án t i ưu Pareto (t i ưu Pareto y u) c n xem (k) xét n u x ∉ S P. ii) N u ng ưi gi i bài tốn cịn mu n ti p t c m r ng t p S P thì đt k = k + 1. Nu k > L 1 ho c s l n b ưc l p liên ti p t p S P khơng đưc m r ng v ưt quá L 2 (k) B (L 1 và L 2 đưc ng ưi gi i tùy ch n) thì đt ai = zi v i i = 1, 2, , p và ch n ng u (k) w B nhiên m t ch s h ∈ {1, 2, , p} đ đ t l i giá tr c t a h ∈ ( zh , zh ]. Quay v b ưc 1. iii) N u ng ưi gi i bài tốn khơng mu n m r ng t p S P thì chuy n sang b ưc 3. Bưc 3: i) Lo i kh i t p S P các ph ươ ng án b tr i. ii) K t thúc. Ví d 2: Gi i BTQHTT hai m c tiêu. z1 = 8x 1+ 6x 2 → Max z2 = x 1 + 3x 2 → Max vi các ràng bu c: 4x 1 + 2x 2 ≤ 60 (D) 2x 1 + 4x 2 ≤ 48 x1, x 2 ≥ 0. a. B ưc kh i t o i) Gi i BTQHTT cho t ng m c tiêu trong ví d trên ta cĩ hai bài tốn: z 1 = 8x 1 + 6x 2 → 1 Max v i điu ki n ràng bu c (D) cho ph ươ ng án t i ưu x (12, 6) và Max z 1 = 132; 2 z2 = x1 + 3x 2 → Max cho ph ươ ng án t i ưu x (0, 12) và Max z 2 = 36. ii) L p b ng pay −off cho các m c tiêu Ph ươ ng án X i z1 z2
X1(12, 6) 132 30 X2(0, 12) 72 36 W B W Da trên thơng tin c a b ng pay −off, ta cĩ z1 = 72, z1 = 132; cịn z2 = 30, B z2 = 36. Do đĩ, đon bi n thiên c n xét cho z 1 là [72, 132] và cho z 2 là [30, 36]. iii) Thi t l p các hàm tho d ng m ng v i hai m c tiêu đã cho nh ư sau: z− z w z− 72 z 72 z µ (z ) = 1 1 = 1 = 1 − = 1 − 1,2 1 1 B w 60 z1− z 1 132− 72 60 60 Hàm tho d ng m trên đây ph thu c vào z 1, nên ph thu c vào (x 1, x 2). Khi cĩ mt ph ươ ng án kh thi (x 1, x 2) ta tính đưc đ tho d ng µ1 (z1 ) đi v i m c tiêu z 1. Tươ ng t đi v i z 2 ta cĩ hàm tho d ng m : z− z w z− 30 z µ (z ) = 2 2 = 2 = 2 − 5. 2 2 B w z2− z 2 36− 30 6 1 2 (1) (1) iv) T p S P ban đu là {x , x }. ðt k = 1, ta cĩ a1 = 132, a 2 = 36. b. Các b ưc l p Bưc 1: i) L p hàm tho d ng t h p u = w 1 µ1(z 1 ) + w 2 µ2(z 2 ) , trong đĩ w 1, w 2 là các tr ng s tho mãn 0 ≤ w 1, w 2 ≤ 1 và w 1 + w 2 = 1. Ch n w 1 = 0,5 và w 2 = 0,5 thì cĩ u = 0,5 z z z z ( 1 − 1,2) + 0,5 ( 2 − 5) = ( 1 + 2 ) − 3,1. 60 6 120 12 z z  ii) ð c c đi hĩa hàm tho d ng t h p, ta ch c n tìm Max 1+ 2  . V y 120 12  z z chúng ta c n gi i bài tốn: Max u = 1 + 2 v i các ràng bu c (D), hay bài tốn 120 12 tươ ng đươ ng: z = 120u/18 = x 1 + 2x 2 → Max, v i các ràng bu c (D). Gi i BTQHTT này ta s cĩ k t qu x (1) = (0, 12). Bưc 2: (1) 2 i) Rõ ràng x ≡ x . V y t p S P ch ưa đưc m r ng. ii) N u ng ưi gi i mu n ti p t c m r ng t p S P thì đt k = 2 và quay v b ưc 1. Quá trình gi i đưc ti p t c. (2) (2) Trong b ưc l p th 2, đ t w1 = 0,8, w 2 = 0,2, a1 = 132 và a 2 = 36 s thu đưc (2) 1 ph ươ ng án x (12, 6) ≡ x . Do đĩ t p S P v n ch ưa đưc m r ng. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 40
(3) (3) Trong b ưc l p th 3, đ t w1 = 0,8, w 2 = 0,2, a1 = 120 và a 2 = 36 s thu đưc (3) 1 2 ph ươ ng án x (9,6; 7,2) mà t i đĩ z 1 = 120 và z 2 = 31,2. T p S p lúc này là t p {x , x , x(3) }. (4) (4) Trong b ưc l p th 4, đ t w1 = 0,2, w 2 = 0,8, a1 = 132 và a 2 = 35 s thu đưc (4) 1 2 (3) ph ươ ng án x (2; 11) mà t i đĩ z 1 = 82 và z 2 = 35. T p S p lúc này là t p {x , x , x , x(4) }. Gi s ng ưi gi i khơng mu n ti p t c m r ng t p S P thì chuy n sang b ưc 3. Bưc 3: i) Trong các ph ươ ng án thu c t p S P khơng cĩ ph ươ ng án nào b tr i. ii) K t thúc v i t p S P các ph ươ ng án c n xem xét. Các ph ươ ng án này đu là ph ươ ng án t i ưu Pareto hay t i ưu Pareto y u. Ph n m m gi i bài tốn quy ho ch tuy n tính đa m c tiêu Ph n m m gi i BTQHTT đa m c tiêu MOD phiên b n 2.0 đưc xây d ng d a trên ph ươ ng pháp tho d ng m và đưc tích h p vào H h tr ra quy t đ nh ph c v quy ho ch s d ng đ t DSSLUP phiên b n 2.0. ðưc xây d ng trên ngơn ng l p trình C#, ph n m m cĩ th d dàng đưc nâng c p, b sung ho c s d ng l i trong m t s ng dng khác. Ph n m m s d ng h qu n tr c ơ s d li u SQL server, thu n l i cho vi c qu n lí và tích h p v i các ph n m m và các h th ng thơng tin - d ch v khác. Các ch c n ăng chính c a ph n m m bao g m: − Ch c n ăng nh p d li u: Nh p d li u bài tốn t t p d li u b n đ (s d ng d li u b n đ MapInfo). − Ch c n ăng l ưu tr và xu t d li u: D li u đưc l ưu và qu n lí trong c ơ s d li u SQL Server, đng th i c ũng cĩ th đưc đưa ra t p d li u b n đ (S d ng MapInfo). − Gi i bài tốn: theo dõi b ng pay −off và gi i theo ph ươ ng pháp tr ng s , cĩ s dng ràng bu c c t đ tìm thêm ph ươ ng án b sung vào t p các ph ươ ng án t i ưu Pareto cn xem xét. Sau khi cài đt ph n m m, đ thi t l p bài tốn c n ch n Cơ s d li u > T o b ng d li u nh m t o s bi n, m c tiêu và s ràng bu c cho bài tốn. Sau đĩ ch n C ơ s d li u > C p nh t d li u nh m c p nh t d li u cho các b ng m c tiêu và ràng bu c, bao gm các h s , các quan h ràng bu c và ch ra các m c tiêu nào là Max/Min. ð gi i bài tốn ch n Gi i bài tốn QHTT > Gi i bài tốn và ch n bài tốn c n gi i t c a s danh sách các b ng m c tiêu và b ng ràng bu c. ð xem thơng tin Pay-Off thì ch n nút Bng Pay -Off . Nh p các tr ng s vào c a s Nh p tr ng s , sau đĩ b m nút Gi i đa m c tiêu . Mu n t o giá tr c t mi n ràng bu c
ch n m c tiêu c n c t trong c a s Nh p giá tr c t, ch n m c c n c t và ch n nút Gi i ph ươ ng pháp c t đ gi i bài tốn theo ph ươ ng pháp c t. ð l ưu các ph ươ ng án t i ưu Pareto (sau khi đã lo i các ph ươ ng án b tr i), ch n nút Lưu ph ươ ng án . Ví d 3: Gi i BTQHTT ba m c tiêu. z1 = x 1 − 2x 2 + 3x 4 → Max z2 = −3x 1 + 6x 2 − 9x 4 → Max z3 = 5x1 + x 2 + 2x 3 → Max vi các ràng bu c: −2x 1 + x3 ≤≤≤ 6 x 1 + x 2 + 5x 3 ≤≤≤ 6 6x 1 + 5x 2 − 3x 3 ≤≤≤ 6 − x 3 + 4x 4 ≤≤≤ 8 x1, x 2, x 3, x 4 ≥ 0. Nh ư v y, đây chúng ta mu n c c đi hĩa đng th i ba hàm m c tiêu trên mi n D các ph ươ ng án kh thi tho mãn đng th i b n ràng bu c và điu ki n khơng âm ca các bi n. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 42
Hình II.7. Nh p d li u, tính b ng pay - off và các ph ươ ng án Trên hình II.7, màn hình giao di n cho bi t: − Sau khi đã nh p d li u, máy tính th c hi n tính các giá tr c a b ng pay −off đ cho bi t các gi i giá tr quan tâm c a z 1 là [-3,43; 8,14], c a z 2 là [-24,41; 10,29] và c a z3 là [3,43; 9,09]. D a trên các thơng tin này, máy tính s thi t l p các hàm tho d ng 1 2 cho t ng m c tiêu. T p S P ban đu bao g m các ph ươ ng án x (1,45; 0; 0,91; 2,23), x (0; 1,71; 0,86; 0), x 3(1,45; 0; 0,91, 0). (1) (1) (1) − w 1 = 0,2, w 2 = 0,3, w 3 = 0,5 v i a1 = 8,14, a 2 = 10,29 và a3 = 9,09, máy tính (1) tìm ra ph ươ ng án x (1,45; 0; 0,91; 0) v i các giá tr hàm m c tiêu là z 1 = 1,45, z 2 = − (1) 3 4,36 và z 3 = 9,09. Ph ươ ng án x trùng v i ph ươ ng án x . (2) ð ti p t c quá trình gi i, chúng ta ch n w 1 = 0,8, w 2 = 0,1, w 3 = 0,1 v i a1 = 6, (2) (2) (2) a 2 = 10,29 và a3 = 9,09, máy tính s tìm ra ph ươ ng án x (1,45; 0; 0,909; 0) v i các giá tr hàm m c tiêu là z 1 = 6, z 2 = − 18 và z 3 = 9,09. (3) (3) (3) Ch n w 1 = 0,1, w 2 = 0,8, w 3 = 0,1 v i a1 = 8,14, a 2 = 8 và a3 = 9,09, máy tính (3) tìm ra ph ươ ng án x (0,23; 1,45; 0,87, 0) v i các giá tr hàm m c tiêu là z 1 = −2,67, z 2 = 8 và z 3 = 4,31.
(4) (4) (4) Ch n w 1 = 0,2, w 2 = 0,3, w 3 = 0,5 v i a1 = 8,14, a 2 = 5 và a3 = 5, máy tính tìm (1) ra ph ươ ng án x (0,4; 1,2; 0,87, 0) v i các giá tr hàm m c tiêu là z 1 = −2,07, z 2 = 6,22 và z 3 = 5. 2.4. M t ng d ng c a mơ hình quy ho ch tuy n tính đa m c tiêu Xét mơ hình quy ho ch tuy n tính đa m c tiêu đánh giá hi u qu s d ng đ t và lao đng trên đa bàn c p xã. ð quy ho ch s d ng đ t, đ ng th i đ m b o đ t hi u qu mơi tr ưng, c n xem xét năm m c tiêu sau: i) T ng l i nhu n, ii) Hi u qu s d ng v n, iii) Giá tr ngày cơng lao đng, iv) S cơng lao đ ng, vi) Hi u qu mơi tr ưng. Da vào c ơ c u cây tr ng xã n ăm 1999, các bi n quy t đ nh sau đưc l a ch n: x1: Di n tích tr ng lúa xuân (ha), x 2: Di n tích tr ng lúa mùa (ha), x 3: Di n tích tr ng ngơ (ha), x 4: Di n tích tr ng đ u t ươ ng (ha), x 5: Di n tích tr ng khoai tây (ha), x 6: Di n tích tr ng rau (ha), x 7: Di n tích tr ng mùi (ha), x 8: Di n tích tr ng táo (ha), x 9: Di n tích tr ng nhãn (ha), x 10 : Di n tích tr ng xồi (ha). Các m c tiêu c n c c đ i hĩa là: z1 = 4,48x 1 + 4,2x 2 + 2,59x 3 + 0,98x 4 + 5,8x 5 + 15,61x 6 + 29,67x 7 + 39,21x 8 + 116,58x 9 + 105,13x 10 , z2 = 0,6205x 1 + 0,5915x 2 +0,465x 3 + 0,1583x 4 + 0,7065x 5 + 0,5864x 6 + 1,2996x 7 + 1,2735x 8 + 1,1726x 9 + 1,756x 10 , z3 = 0,0217x 1 + 0,0206x 2 + 0,0154x 3 + 0,0045x 4 + 0,0248x 5 + 0,0109x 6 + 0,0241x 7 + 0,0349x 8 + 0,09x 9 + 0,0811x 10 , z4 = 206x 1 + 204x 2 + 168x 3 + 216x 4 + 234x 5 + 1428x 6 + 1232x 7 + 1124x 8 + 1296x 9 + 1296x 10 , z5 = 0,7x 1 + 0,778x 2 + 1,273x 3 + 1,75x 4 + x 5 + 0,368x 6 + 0,875x 7 + 3x 8 + 3x 9 + 3x 10 , Vi các ràng bu c sau (v c ơ c u di n tích đ t canh tác): x1≤ 189,6407; x 2 ≤ 189,6407; x 3 ≤ 17,4931; x 4 ≤ 17,4931; x 5 ≤17,4931; x6 ≤189,6407; x 7 ≤ 17,4931; x 8 ≤18; x 9 ≤18; x 10 ≤ 18. Di n tích tr ng rau trên c đ t ba v và đt chuyên màu: x 6 ≥ 26,4. Di n tích đt tr ng cây v đơng trên đt ba v : x 3 + x 4 + x 5 + x 6 + x 7 = 43,8931. Di n tích đ t tr ng các cây ăn qu trên đt tr ng cây hàng n ăm khác: x 8 + x 9 + x 10 = 18. ðiu ki n đ cĩ l i nhu n là: 4,48x 1 + 4,2x 2 + 2,59x 3 + 0,98x 4 + 5,8x 5 + 15,61x 6 + 29,67x 7 + 39,21x 8 + 116,58x 9 + 105,13x 10 > 0. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 44
ðiu ki n v s n l ưng l ươ ng th c: Các cây l ươ ng th c c a xã g m lúa xuân, lúa mùa và ngơ: 5,14x 1 + 4,98x 2 + 3,77x 3 ≥ 1700,5. ðiu ki n khơng âm c a các bi n: xi (i = 1, 2, , 10) ≥ 0. Mơ hình trên đây đã đưc gi i quy t thành cơng b ng ph n m m gi i BTQHTT đa mc tiêu MOD phiên b n 2.0. 3. MƠ HÌNH T I ƯU PHI TUY N ðƠN VÀ ðA M C TIÊU 3.1. M t s khái ni m c ơ b n Mơ hình t i ưu t ng quát Mơ hình t i ưu t ng quát, hay bài tốn t i ưu t ng quát, cĩ d ng: F(X) → Min (Max) v i X ∈ D ⊂ R n. đây F(X) cĩ th là m t hàm vơ h ưng hay hàm véc t ơ, tuy n tính hay phi tuy n. Trong tr ưng h p F(X) là hàm vơ h ưng thì ta cĩ mơ hình t i ưu đơ n m c tiêu, cịn nu F là hàm véc t ơ thì cĩ mơ hình t i ưu đa m c tiêu. D đưc g i là mi n ràng bu c hay mi n ph ươ ng án kh thi, th ưng đưc bi u di n b i các đ ng th c và/ho c các b t đng th c. Mơ hình t i ưu phi tuy n đơn m c tiêu Dng chính t c c a bài tốn t i ưu m t m c tiêu đưc bi u di n nh ư sau: n f(X) → Min (Max), X = (x 1, x 2, , x n)∈ R , vi: (i) g j(X) ≤ 0, j = 1, 2, , k, (ii) g j(X) = 0, j = k+1, k+2, , m. Trong các bài tốn th c t cĩ th b sung các ràng bu c (iii) a i ≤ x i ≤ b i, i = 1, 2, , n. Trong tr ưng h p ho c hàm m c tiêu f(X) ho c cĩ ít nh t m t trong các hàm ràng bu c g j(X), j = 1, 2, , m, là hàm phi tuy n, chúng ta cĩ bài tốn t i ưu phi tuy n. Khi tt c các to đ x i đu b t bu c nh n các giá tr nguyên, i = 1, 2, , n thì ta cĩ bài tốn ti ưu nguyên. Cịn n u ch cĩ m t s to đ (nh ưng khơng ph i t t c các to đ ) b t bu c nh n giá tr nguyên thì ta cĩ bài tốn t i ưu h n h p nguyên. Kí hi u D là mi n các ph ươ ng án (mi n ràng bu c) cho b i các ràng bu c (i), (ii) và/ho c (iii) thì bài tốn t i ưu trên đây cĩ th vi t g n h ơn nh ư sau: f(X) → Min (Max) v i X ∈ D.
Lúc này, đi v i bài tốn c c ti u hố, X* ∈ D đưc g i là ph ươ ng án t i ưu tồn * * cc n u ∀X ∈ D ta luơn cĩ: f(X ) ≤ f(X). Trong tr ưng h p f(X ) ≤ f(X) ch đúng v i ∀X ∈ D trong m t lân c n nào đĩ c a X * thì X * đưc g i là ph ươ ng án t i ưu đa ph ươ ng. Mt cách t ươ ng t , ta cĩ th đ nh ngh ĩa khái ni m ph ươ ng án t i ưu tồn c c ho c đ a ph ươ ng cho bài tốn c c đ i hố. N u chúng ta ch quan tâm t i vi c tìm ki m ph ươ ng án t i ưu tồn c c thì ta cĩ bài tốn t i ưu tồn c c. Trong các bài tốn t i ưu phi tuyn ng d ng nĩi chung, trong l ĩnh v c c ơ khí − đin l c nĩi riêng, ph ươ ng án t i ưu tồn c c cĩ m t ý ngh ĩa quan tr ng. Ch ng h n trong thi t k máy nơng nghi p, sau khi dùng ph ươ ng pháp phân tích h i quy nhi u chi u, ta th ưng thu đưc hàm m c tiêu f(X) cĩ d ng phi tuy n. Bài tốn đt ra là ph i tìm đưc ph ươ ng án t i ưu tồn c c. Cĩ r t nhi u ph ươ ng pháp gi i các l p bài tốn t i ưu phi tuy n, nh ưng ch ưa cĩ ph ươ ng pháp nào t ra h u hi u cho m i bài tốn t i ưu phi tuy n, đ c bi t là các bài tốn t i ưu nguyên và h n h p nguyên. Mơ hình t i ưu phi tuy n đa m c tiêu Mơ hình t i ưu đa m c tiêu cĩ d ng: zj = f j(X) → Min (Max), X = (x 1, x 2, , x n), j = 1, 2, , p (p ≥ 2) vi: (i) g j(X) ≤ 0, j = 1, 2, , k, (ii) g j(X) = 0, j = k+1, k+2, , m. Trong các bài tốn th c t cĩ th b sung các ràng bu c (iii) a i ≤ x i ≤ b i, i = 1, 2, , n. Trong mơ hình này, ta cĩ p m c tiêu c n t i ưu hố, các h s c a các hàm m c tiêu và ràng bu c nĩi chung đưc gi s là các giá tr th c xác đ nh. Trong tr ưng h p cĩ ít nh t m t trong các hàm m c tiêu hay các hàm ràng bu c là hàm phi tuy n, chúng ta cĩ bài tốn t i ưu phi tuy n đa m c tiêu. ði v i bài tốn t i ưu phi tuy n đa m c tiêu chúng ta c ũng cĩ khái ni m ph ươ ng án t i ưu Pareto nh ư đã trình bày trong m c 2 đ i v i BTQHTT đa m c tiêu. Cũng nh ư đi v i các BTQHTT đa m c tiêu, ph ươ ng pháp gi i bài tốn t i ưu phi tuy n đa m c tiêu d a trên s tr giúp c a h máy tính, nh m giúp ng ưi ra quy t đ nh tng b ưc thay đ i các quy t đ nh trung gian m t cách thích h p đ đi t i m t ph ươ ng án t i ưu Pareto tho mãn nh t, đưc g i là ph ươ ng pháp t ươ ng tác ng ưi−máy tính. 3.2. M t s ph ươ ng pháp gi i bài tốn t i ưu phi tuy n đơn m c tiêu và ng d ng Các ph ươ ng pháp gi i bài tốn t i ưu tồn c c Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 46
Các ph ươ ng pháp gi i bài tốn t i ưu tồn c c phi tuy n đơn m c tiêu đưc phân ra thành hai l p: ph ươ ng pháp t t đ nh ( deterministic methods ) và ph ươ ng pháp ng u nhiên (stochastic methods ). Ph ươ ng pháp t t đ nh s d ng các tính ch t gi i tích c a hàm m c tiêu và các hàm ràng bu c. M t s d ng bài tốn t i ưu tồn c c v i nh ng tính ch t gi i tích nh t đ nh ca hàm m c tiêu và các hàm ràng bu c cĩ th gi i đưc b ng các ph ươ ng pháp t t đ nh thích h p, ch ng h n nh ư: ph ươ ng pháp đưng d c nh t, ph ươ ng pháp Newton (cho các bài tốn t i ưu phi tuy n khơng cĩ ràng bu c), ph ươ ng pháp quy ho ch tồn ph ươ ng, quy ho ch tách, quy ho ch l i, quy ho ch d.c (cho các bài tốn t i ưu phi tuy n cĩ ràng bu c) Trong các tr ưng h p đĩ ph ươ ng án t i ưu tồn c c cĩ th tìm đưc sau m t s hu h n b ưc tính tốn v i đ chính xác ch n tr ưc. Tuy nhiên, đi v i nhi u l p bài tốn t i ưu tồn c c ph ươ ng pháp t t đ nh t ra khơng cĩ hi u qu . Trong khi đĩ, các ph ươ ng pháp ng u nhiên nh ư: ph ươ ng pháp đa kh i t o ( multistart ), mơ ph ng tơi luy n ( simulated annealing ), thu t gi i di truy n ( genetic algorithm ), cĩ th áp d ng đ gi i các bài tốn t i ưu tồn c c d ng b t kì, khơng địi h i các tính ch t đ c bi t ca hàm m c tiêu hay các hàm ràng bu c. Các ph ươ ng pháp ng u nhiên đc bi t t ra cĩ hi u qu đ i v i các bài tốn t i ưu phi tuy n nguyên và h n h p nguyên. Tuy nhiên, các ph ươ ng pháp này th ưng ch cho ph ươ ng án “g n” t i ưu khá t t sau m t s h u h n b ưc mà khơng ki m sốt đưc đ chính xác c a ph ươ ng án tìm đưc. Gi i bài tốn t i ưu phi tuy n b ng thu t gi i RST2ANU Thu t gi i RST2ANU, đưc đưa ra b i C. Mohan và Nguy n H i Thanh nh m gi i các bài tốn t i ưu tồn c c phi tuy n d ng t ng quát v i các bi n liên t c, các bi n nguyên và cho các bài tốn h n h p nguyên. Thu t gi i này là thu t gi i tìm ki m ng u nhiên cĩ điu khi n, cĩ k t h p thu t tốn mơ ph ng tơi luy n (SA). Thu t gi i RST2ANU là thu t gi i l p, bao g m hai pha: pha c c b và pha tồn c c, đưc phát bi u m t cách ng n g n cho bài tốn t i ưu chính t c d ng c c ti u hĩa nh ư sau. Trong pha tồn c c, m t s l ưng thích h p đ l n các ph ươ ng án kh thi đưc đưc phát sinh ra m t cách ng u nhiên và l ưu tr trong m ng cĩ tên A. ðánh d u hai đim cĩ giá tr hàm m c tiêu l n nh t và nh nh t t ươ ng ng là M và L. Trong pha c c b , các ph ươ ng án đưc x lí nh m thu đưc giá tr t t h ơn c a hàm mc tiêu. Trong pha này, thu t gi i xác đ nh X là đim đưc n i suy b c hai d a trên ph ươ ng án L và hai ph ươ ng án khác đưc ch n ng u nhiên trong m ng A. N u nh ư X là ph ươ ng án kh thi thì v i f(X) ≤ f(M), M s đưc thay th b i X trong m ng A; cịn v i f(X) > f(M), M s đưc thay th b i X v i xác su t p= exp( −β(f(X) −f(M))/(f(X) −f(L))), trong đĩ β > 0 là tham s đưc l a ch n thích h p. N u X khơng ph i là ph ươ ng án kh thi, b qua X và ch n hai ph ươ ng án khác trong A m t cách ng u nhiên r i cùng v i L ti p t c sinh ra ph ươ ng án m i. Quá trình c th ti p di n nh ư v y cho t i khi t p h p
các ph ươ ng án trong A s cĩ xu h ưng co c m l i xung quanh m t ph ươ ng án t i ưu tồn c c. Ph n m m RST2ANU 1.0 đưc xây d ng d a trên thu t gi i đưc trình bày trên đây. Quá trình xây d ng ph ươ ng pháp tính tốn t i ưu, thu t gi i, cài đt trên ngơn ng C và sau này là ngơn ng Visual C++ 6.0 c ũng nh ư ch y th nghi m kéo dài g n tám năm cho th y ph n m m cĩ đ tin c y r t cao trong vi c tìm ra các ph ươ ng án t i ưu tồn c c. Ph n m m đã đưc kĩ sư ðng Xuân Hà đĩng gĩi tránh sao chép và cĩ giao di n thân thi n đ i v i ng ưi s d ng, cĩ th dùng đ gi i các bài tốn l n khi đưc cài đt trên h máy tính m nh. Ví d 1: Gi i bài tốn t i ưu phi tuy n h n h p nguyên. 0,6 0,6 0,4 , z = x 1 + x 2 + x 3 + 2x 4 + 5x 5 − 4x 3 - x6 → Min vi các ràng bu c: x2 − 3x 1 − 3x 4 = 0; x 3 − 2x 2 − 2x 5 = 0; 4x 4 - x 6 = 0; x1 + 2x 4 ≤ 4; x 2 + x 5 ≤ 4; x 3 + x 6 ≤ 6; x1 ≤ 3; x 2 ≤ 4; x 3 ≤ 4; x 4 ≤ 1; x 5 ≤ 2; x 6 ≤ 6; x 1, x 2, x 3, x 4, x 5, x 6 ≥ 0; x4, x 5, x 6 là các bi n nguyên. Hưng d n s d ng ph n m m RST2ANU Ch ươ ng trình đưc gĩi g n trong m t file ch y duy nh t mang tên rst2anu1.0.exe. Khi b t đ u kh i đ ng ch ươ ng trình, ng ưi dùng s đưc h i mã đă ng kí s d ng ch ươ ng trình. M i ng ưi dùng s đưc c p m t mã đă ng kí và ph i cĩ mã đă ng kí m i s d ng đưc ch ươ ng trình, do đĩ ch ươ ng trình khơng th b sao chép. Sau khi nh p mã đă ng kí, ng ưi dùng cĩ th nh p bài tốn m t cách d dàng (xem hình II.8) v i: − NX là s bi n c a bài tốn. − XINT xác đnh bi n nguyên và bi n khơng nguyên. Nh ư trong hình trên, XINT = 0,0,0,1,1,1 cho bi t ba bi n đ u là bi n liên t c, ba bi n sau là bi n nguyên. − FX là xâu xác đnh hàm ràng bu c, đưc nh p theo cú pháp c a Evaluate Expression. Các bi n đưc vi t b ng kí hi u “X” cĩ kèm theo ch s . Ch ng h n, X1 là bi n th nh t, X5 là bi n th 5. − N u bài tốn t i ưu là bài tốn tìm c c ti u thì l a ch n ơ MIN và ng ưc l i ch n ơ MAX v i bài tốn tìm c c đ i. − Feas xâu cho bi t các hàm ràng bu c, đưc nh p cách nhau b i d u ch m ph y ho c xu ng dịng. Các xâu này c ũng tuân theo cú pháp c a EvaluateExpression. Tr ưng ð i h c Nơng nghi p Hà N i – Giáo trình V n trù h c 48
− Rules là các xâu ch ra các lu t. đây, m t lu t cĩ th coi nh ư là m t l nh gán giá tr c a m t bi n b i giá tr c a m t bi u th c các bi n khác. − MINX là m ng xác đ nh c n d ưi cho các bi n, các giá tr vi t cách nhau b i d u ph y (,). − MAXX là m ng xác đ nh c n trên cho các bi n, các giá tr vi t cách nhau b i d u ph y (,). Hình II.8. Màn hình giao di n sau khi nh p xong d li u − NA là kích thưc c a m ng A (cĩ th ch n tu ỳ ý, t i thi u là 2(n + 1) v i n là s bi n c a bài tốn). − MAX RANDOM là s l n c g ng t i đa đ tìm m t ph ươ ng án ch p nh n đưc bng ph ươ ng pháp ng u nhiên. − ITERLAST, ISLAST, IFLAST là các gi i h n v s vịng l p, s l n th t b i trong vi c c i thi n giá tr hàm m c tiêu, s l n th t b i trong vi c n i suy ph ươ ng án mi ch p nh n đưc. − Epsilon1, epsilon2 là các s d ươ ng đ nh nh m xác đ nh tiêu chu n co c m c a mng A theo thu t gi i. − Beta là h ng s s d ng trong cơng th c tính xác xu t thay th m t ph ươ ng án t t hơn trong m ng A b i m t ph ươ ng án t i h ơn. − Prob file và Res file là các t p đ u vào và t p k t qu . Cĩ th so n s n t p bài tốn đu vào r i n p bài tốn. C ũng cĩ th l ưu m t bài tốn đã nh p ra t p.