Giáo trình Toán kinh tế: Phần 1 - Bùi Minh Trí

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

Thêm vào BST

Báo xấu

1.048
lượt xem 193
download

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

Phần 1 Giáo trình Toán kinh tế trình bày các nội dung của phần tối ưu hóa. Trong phần này gồm 5 chương, trình bày các vấn đề như bài toán tối ưu hóa tổng quát và các vấn để cơ sở, quy hoạch tuyến tính, bài toán vận tải, quy hoạch động, quy hoạch phi tuyến.

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình Toán kinh tế: Phần 1 - Bùi Minh Trí

BÙI M IN H TRÍ TOÁN KINH TÊ (Tái bản lần thứ hai) N HÀ XUẤT BAN B Á C H KHOA - H À NỘI
Bản quyền thưộc về Nhà xuất bản Bách Khoa - Hà Nội. Mọi hình thức xuất bản, sao chép mà không có sự cho phép bằng văn bản của nhà xuất bản là vi phạm pháp luật. M ã số: ỉ 38 - 201J/CXBỈ]()5 - 56/BKHN Biên m ụ c trên xuất bản p h ẩ m của T hư viện Q uốc gia V iệt Nam Bùi Minh Trí Toán kinh tế / Bùi M inh Trí. - Tái bàn lần 2. - H. : Bách khoa Hà Nội, 2011. - 272tr. ; hình vẽ, bảng ; 24cin Thư mục: tr. 269-271 1. Toán kinh tế 2. Giáo trình 330.01 - d c l 4 BKE0007p-CIP
MỤC LỤC • * LỜI NÓI Đ Ấ U ............................................................................................... 9 PHẦN I. TỐI ƯU HÓA LỜI NÓI Đ Ầ U ..............................................................................................11 Chương I. BÀI TOÁN TỐI ưu HÓA TổNG QUÁT VÀ CÁC VẤN ĐỂ Cơ SỞ.........................................................13 § 1 . Bài toán tối ưu hóa tổng quát vàphàn loại các bài t o á n .......13 1. ỉ . Bài toán lối ưu hóa tổim quát......................................................... 13 1.2. Phân loại các bài t o á n ..................................................................... 14 §2. Vấn để mỏ hình hóa toán học........................................................... 15 2.1. Xây dựiiíí mô hình toán học cho rn(M vàn đề thực t ế .............. 15 2.2. Một số mô hình thực t ế .................................................................. 17 §3. Một sô khái niệm và két quá lù đại s ó ........................................... 23 3.1. Ma t r ậ n ............................................................................................... 23 3.2. Định Ih ứ c ........................................................................................... 24 3.3. Ma irận nuhịch đáo, han;: ru;i |;K tiậĩi..........................................26 I 3.4. Hệ phươnu trình đại số tiivcn lúih ................................................27 3.5. Khône sian E u clid .......................................................................... 29 Chương II. QUY HOẠCH TUYẾN TỈNH........... ...................................... 32 M ở đ ầ u ......................................................... ....................................................32 §1. Bài toán quv hoạch tuyến tín h ....................................................... 32 1.1. Bài toán tổn^ q u á t............................................................................ 32 1.2. Dạnii chuẩn và dạng chính lăc......................................................33 3
1.3. Đưa Q H T T vé dạiiii chuẩn hoặc dạiiíỉ chính t ã c .....................34 1.4. Giai hài toán QMTI' hai biến bằng phưo'ny Ịiháp hình học .. 35 §2. M ột sỏ tính chất c h u n g ...................................................................... 38 §3. Phưotig p h áp đon hình giải Q H T T ...............................................42 3.1. Đ ư ờ n a lối chuníi \'à cơ sớ cua thuật t o á n .................................. 42 3.2. Cơ sở của thuật l o á n ........................................................................ 42 3.3. T huật toán đơn hình......................................................................... 47 3.4. C òng thức đổi cơ sở. Bang đưn h l n h .......................................... 48 §4. V ấn đề p h ư o n g án cực biên và cơ sỏ xuất phát giai đoạn 1 52 §5. Q u y h oạch đối n g ẫ u ............................................................................ 67 5.1. Q H T T dưới dạng chuẩn. Q p bài toán tuyến lính đối ng ẫu đối x ứ n g ............................................................................. 5.2. Q H T T dưới dạng chính tắc. Cặp bài toán tuyên lính đối n a ầ u không đối x ứ n g ................................................................ /3 5.3. Ý n e h ĩa cặp bài toán đối n g ẫ u ...................................................... 74 5.4. Tiêu c h u ẩ n lối ưu và thuậl toán đơn hình dối n g ẫ u ................ 76 5.5. V í d ụ ......................................................................................................80 Bài tập ch ư ơ n g I I ............ ......... .................................................................. X6 Chương III. BÀI TOÁN VẬN TẢI................................................................ 89 §1. P h át biểu bài toán - Sự tồn tại nghiệm tối ư u ..........................89 1.1. Phát bicu bài t o á n ............................................................................. 1.2. Sự tồn tại nghiệm tối ư u .................................................................. 91 §2. T iêu ch u ẩ n nhận biết phương lin cực b i ê n ................................92 §3. C ác phương pháp tìm phương án xuất p h á t............................. 95 3.1. Phư ơng pháp góc tây b ắ c .................................................................. 95 3.2. Phương pháp cước phí tối thiểu irong toàn h á n g ....................... 96 3.3. Phư ơng pháp cực ticu cước phí theo h à n g ..................................97 3.4. Phươníỉ pháp cực tiểu cước phí theo c ộ t..................................... 97
§ 4 . Tiêu chuaii tối ưu - thuật t(»án.......................................................... 97 4.1. Tièu chuẩn tôi ư u ................................................................................ 97 4.2. Thuật lo á n ............................................................................................. 99 4.3. Các ví d ụ ........................................................................................... 101 §5. Trường hợp khòng cán băng tha p h át........................................... 108 Bài tập chương I I I ...................................................................................... 109 i. Giai các bài toán vận l á i .................................................................. 109 II. Giai BTVT có phuxTne án llioai hd-i.......................................... 1 10 ill. Giai BTVT khỏim căn bàng llìu |'iiát......................................... 1 10 IV. Các càu hỏi p h ụ .............................................................................. 1 1 1 Chương IV. QUY HOẠCH Đ Ộ N G ........................................................ 112 M ử đ ầ u .........................................................................................................1 1 2 §1. Phương pháịỉ phưong trình truy toán và các n gu yên tác cơ bản của Q H Đ ...................................................................................113 1. ỉ , Bài toán phân phối niól chicu Nà pliươna trình truy toán ... 113 1.2 Các Iiizu\ én tãc co' ban cua qu\ luạch độno ( Q H Đ ) ............ 1 15 §2. Q uá trình nhiều giai đoạii và phiioiig trình h à m .....................116 2 . 1. Quá Irình nhiổu uiai (loan........................................................... 116 2.2. Xây dựng phưoìm liình h a m ....................................................... 117 §3. Sơ đổ tính vù ví dụ áp íiụri"............................................................. 118 3.1. S(ídó tính............................................ .............................................. 118 3.2. Các ví d ụ ........................................................................................... 119 §4. Bài toán thực tế: Xác định che độ khoan giếng tối ư u ........125 4.1. Thié't lập bài t o á n ............................................................................ 125 4.2. Phưívim pháp e i ủ i ............................................................................ 126 4.3. Chu'o'im trìnli và kết qu:l................................................................ 127 Bài tập chương IV ....................................................................................... 128
Chương V. QUY HOẠCH PHI TU Y Ê N .................................................130 M ở đ ầ u ............................................................................................................. 130 §1. M ột sô khái niệm cơ bản trong giải tích lồ i...............................130 1.1. Tập hợp lồi......................................................................................... I 31 1.2. H àm l ồ i ............................................................................................... 133 §2, Lý thuyết quv hoạch l ồ i ..................................................................... 141 2.1 Bài toán quy hoạch lồi tổng quát và điều kiện tối ưu........... 141 2.2. Phươns pháp siải quy hoạch lồi................................................. 146 §3. Một sô phương pháp giải Q H P T có ràng b u ộ c .........................160 3.1. Phươnc pháp g r a d i e n ..................................................................... 160 3.2. Phươns pháp Lagran>:e................................................................. 162 3.3. Một số ví d ụ : ..................................................................................... 164 §4. Bài toán quy hoạch phi tuyến và nghiệm tối ưu của n ó .... 170 4 . 1. Phát biểu bài t o á n ........................................................................... 170 4.2. N ghiêm tối ư u ................................................................................... 172 •CT 4.3. Phân loại các phưưng pháp tỉiai Q H P r .................................... 173 4.4. Quy hoạch phi tuvến tổna quát và đicu khiển tói ư u ......... 174 Bài tập chương V I I ...................................................................................... 178 TÀI LIỆU THAM K H Ả O ............................................................................ 181 PHẦN II. MÔ HÌNH TOÁN KINH TẾ MỞ Đ Ầ U .................................................................................................... 185 Chương I. MÔ HÌNH KINH TỂ VÀ MÔ HÌNH TOÁN KINH T Ể ..........187 § 1 . M ỏ hình kinh t ê .................................................................................... 187 1.1. Mô hình kinh tế lớn (m acro)....................................................... 187 1.2. M ô hình kinh tế nhỏ ( m i c r o ) ..................................................... 195 6
1.3. Mỏ hình kinh tố phái triciì........................................................... 196 §2. M ô hình toán kinh té ............ . .....................................................202 2.1. Khái n i ệ m ........................................................................................... 202 2.2. Các bước xày dựim mô liìiih học cho một vân đề thực i c ..................................................................................................203 §3. H àm sàn xiiá t................ ........................................................................204 3.1. Mô hình ch una và các khái n ic m ................................................. 204 3.2. Hàm đána c ấ p ....................................................................................204 3.3. Hàm san xuất với độ co ” iãn liia v thế hằng số ( C E S ) .........205 3.4. Hàin san XLiàì Cobb - D('Ui:lav .......................................... 207 3.5. Hàm Walras - Leontieí (1\\| )........................................................ 209 Càu hỏi ôn tập chươiig I........................................................................... 210 Chương II. PHƯƠNG PHÁP CÂN ĐỐI LiÊN NGÀNH........................... 211 §1. Cân đòi lién níỊÙnh t ĩ n h ............... .....................................................211 1.1 Bản« cán đối liên nsàiih dạiii! hii-M v ạ i ................................... 212 i 1.2. Bànư cân đối licii ngành daii” giá i r ị .......................................219 §2. Cán đối liên ngành đ ộ n g ............... ...................................................225 §3. B ảng cân đối liên ngành của Việt n a in ........................................227 Câu hỏi ôn tập chươiig I I .........................................................................232 Chương III. PHƯƠNG PHÁP s ơ Đ ổ MẠNG Lllơ l (PERT)................. 234 Mư đ ầ u ....................................................... ................ ................................... 234 §1. Các khái niệm cơ bản................................................................ 235 1.1. Một số khái niệm vc (16 tliỊ............................................................235 1.2. Các khái niệm của SO đồ maiiíi \ươì............................................ 236 ' § 2 . Các nguyên tắc thành lập mot so đổ m ạng lư ói.......................236 §3. Khái niệm về đường găiiịỉ va các đ;ic trưng lién q u a n ........239
3.1. Đườnu e ã n e ........................................................................................239 3.2. Các dặc iruìm liên CỊLiaii đèn điròng g ã n c ...................................241 Câu hỏi ôn tập chương III........................................................................ 244 Chương IV. MÔ HÌNH PHỤC v ụ ĐÁM Đ Ô N G ....................................246 § ỉ . Các đặc trưng co ban của hệ thòng phục vụ đám đ ỏ n g .... 247 1.1. Sơ đổ chuntỉ của hộ thỏns: phục vụ đám đôiiii.......................247 [.2, Phán loai các dònu \ à o ................................................................. 248 1.3. Kcnh phục \-ụ................................................................................... 249 ] ,4, Pháiì loai các hệ thốim phục \ ự.................................................. 230 1.5, Tiạn>z thái cua hc ihốiiỊ:............................................................ 250 1.6. Các tiêu chuán chất lươne cua hệ Ihốnia phục vụ đám đ ô n u ............................................................................ 254 §2. Hệ thống phục vụ đám đởii” có tù chối cổ điển (hệ thống E r la n g ơ )...............................................................................255 2 . 1. Mỏ tci hô thỏnt:.................................................................. 25S 2.2. Quií t r ì n h i h a ) đ ổi í r a n e Ihái \ à SO' d ổ I r ạ n e llìái của hc ih ốnii................................................... 2SS 2.3. Hệ phương trình trạns Ihái và các xác suâì trạne t h á i 2 56 . 2.4. Các chi liêu đánh giá hoạt độnsi cua hệ l l i ỏ n g ......................... 257 §3. Hệ thòng chừ vói độ dài hàiig chò và thòi gian chò hạn c h ế ...................................................................................................... 260 3.1. Mô la hè thõìi” ....................................................................................260 3.2. Quii irình thay đối trạnn thái \ à S Í (lồ ti-ạiis: thái của(T hộ t l i õ n e ................................................................................................2(i 1 3.3. ỉiê phương trình trạnỵ lliáí \'à các xác sLiàt Irạiiu t h á i 2 62 . Câu hỏi ón tập chưưng I V .........................................................................268 TÀI LIỆU THAM K H Ả O ............................................................................. 269
LỜI NÓI ĐẦU ' ĩroiìii k h o à n e hơn 5 0 lìăni ỉ r ó lại cla\. Uìa;t loc đ ã p h á t I r i cn rat m ạ n h và d ã d ư ọ v á p úụn^j. iìiỏl c á c h r ộ n u rài \ à sau sac \ lIo kiiili íê. v à o kl i oa h ọ c k ỹ tlìLiạ l \'à \í\0 hâu hốt các h o ạ tđ ộ ỉìu cua Ciìn Ỉ ILI UU' . ì'ừ đỏ là iìì Iiẩ \ s in h ca m ộ l iìLiaiih Ukíỉì Iìoc m ó i là '[\niii ki ii h lỏ. ^ • T o á n k i n h lè là i n ộ t c ỏ i i e c u qiiaii Iroiiii \ I nci CLII12 c ấ p p h i a í i m p h á p l u ậ n , các Ịiluroni: pháp inò hinh hoá. các phưoìii^ |)li,í|' lính toán tối ưu. Do dỏ, nó k h ô iiiỉ nliữ ni: ià cổim CỊI dẽ tư duy \'é dịnh tính 11:à c;i về d ịn li lirợ iii’ . tiiú p iziai C | u \ ê t c á c \' â n d c m ộ t c ú c h c ó hiỌu cỊua. V i ộ c l â p kc' h o ạ c h Ịihál I r i ế n kiiili tc \ à \ i i ' j n á i i ” c a o h i ệ u q u á c u a s á n \ u a ì xã hội là các ván đc quan Irọni: cua haì kv 111(111|UỐC nia nào. Để giai quyết toì c á c v â n đ ê d ó Ihì p h a i k l i ó n i i Iiiiừn>: h o à n lìiKMi L,K' p h ư ư n t i p h á p đ i c ư k h i ổ n . qu;iii lý \ à đáv nhanli lốc đỏ ticìi bo khoa ÌÌO kv lịuuìl. thực hiộn các biện pháp Ơ k l m a h ọ c LX) b ủn . l ì o o i i quá trình ció. (tÌL'u quan li'ọn,” tlau ík n hì phái xãy clụìii: đu'ực các ino hình UKÍn học từ Ihuv licn san \u a l \ à kinh cidunlì. tlịch vụ rất piioiig phú và da daiig. IIÕ Icii ihàiih các liai U),iii. S
Phần I: Tối ưu hóa Tối ưu hoá còn gọi là Q uv hoạcli toán học. TixMiíỉ phần này nêu ra đối tượng nahiôn cứu là bài toán lối ưu hóa tổna quát. Tuỳ theo tính chất các thành phần của bài loán (miền ràns buộc, hàm mục tiêu, các hàm rà n s buộc, các biẽìi số. các ihani sò) mà nsười ta phân loại ra các lớp bài toán quy hoạch khác nhau: quy hoạch luyến tính, quy hoạch phi luyên, quy hoạch rời rạc (trưòìm hợp riêniỉ quan Irọĩiíí là quv hoạch ngu\'ên). quy hoạch độns. quy hoạch tham số, quy hoạch đa mục tiêu. Do kliuỏn khổ của chươnc trình nên 2 Ìáo trình này chí xét các mồ hình toán học và các mò hình ihực tiẽn của quy hoạch tuvến tính, bài toán vận u'u. quv hoạch đ ộ n s và một sỏ loại quỵ hoạch phi luvến. Các thuật toán được trình bàv inộl cách cụ Ihế, dẻ hiểu kèm theo các ví dụ minh họa. Plĩần II: M ô hình toán kinh tê Trong phần này trình bày các bước xâv dựníz mô hình kinh lế và các inò hình kinh tế lớn, kinh t ế nhỏ và kinh lê' phát triển. Sau đó xét các mô hình kinh tế có nhiều ứns d ụ n s tro n s thực tiền là: phưiíns pháp cân đối liên n
Phần I TỐI ƯU HÓA LỜI NÓI ĐẨU Các phươim pháp tối ưu hóa được áp dụnu IIIÓ cách hiệu qua irong lủt cà I các lĩnh vực hoạt độim khác nhau cua con nuưòi. Đãc biệt các thành tựu rất sâu sãc đạt được khi siái quyết các bài toán kinh tc. lap kế hoạch sán xuất và kinh d o a n h , t h iế t k ế k v ihi iậ l và p h à n tích c á c hê thốiiii lớn t r o n g x â y d ự n g , c h i n h phục vũ trụ, trong nahiên cứu và ứni: dụnt: tiii lioc \'ào đời sống. Nhừ công cụ lính toán ngàv cà n s hoàn thiện mà các công tiìiih nghiên cứu lý thuyếl và thực hành được m ở r ộ n a và phát triến nhanh. Ngày nay đối vói nhữna neười làin kinh to. quan lý sán xuất và kinh doanh, các kỹ sư và các nhà n.iihién cứu k h o a h o e thuộc nhiều lĩnh vực khác nhau, sự hicu biết \ ’é các phưưiiổ pliáp tôi 11X lnxi cũHii cần Ihiêì như các môn 1 k h o a h ọ c c ơ bàn, c á c m ô n kỹ ihuậl co' SO' v;( CUL k h o a học c h u y ê n n g à n h . C ũna cẩn nói thêm I'àniz níiirời la còn tiọi lổi ưu lu');i là quy hoạch loán học. Với một nội dung CO' ban là uiai các bai to án cực trị có các ràng buộc kinh lố và kỹ Ihuậl dưới dạn
lìni ihuật toán lốt và kỹ (huạt lạp 11'iiih thì nuười la có ihc >:i;ii đuọ’ các bài toán c thực tế cờ lớn, phức tạp. Phần I bao cồm 5 chưoiiti: Chu''n;^ /. Bài toán tối ưu hóa tòiiii quát \'à các \ ’ấn đổ cơ scV Cliiừin:^ //. Quv hoạch tu) cn tính Cliiíoiì'^ m . Bài loán vận lai ChiừUi'^ IV. Q u \ ’ hoạch độni’ Clìiio'11^ \ \ Quv hoạch phi tuvến Co' sớ cua các phươne pháp được trình hàv tiỗ hiểu, các ihuạl toán rò ràny và không quá đi sãu vào Iv lhu\'ct phức lạp. Đối \ó'i mối mò h'mh đcu cỏ giói thiệu bài toán thực tc', mỗi ihuật toán dcu C() \'í dụ minh họa.
Chương I ____ BÀI TOÁN TỐI ƯU HÓA TONG QUÁT VÀ CÁC VẤN ĐỂ Cơ SỞ §1. BÀI TOÁN TỐI ƯU HÓA TổNG QUÁT VÀ PHÂN LOẠI CÁC BÀI TOÁN Khi tiên hành k ế hoạcli hóa san XLiát. dicu khi ôn các hệ Ihồns và thiêt kè k ỹ t h u ậ t m à b i ê t d ự a t r ê n c á c n2Li yên lă c cực trị la s ẽ li êt kiệm đ ư ợ c v ậ t t ư tiền vòn, tài nguyên, sức lao độno. ihời eian \'à tăng dưực hiệu quá giai quyct các vấn đề đặt ra. Nhữno cơ sở Iv thuvcì và các phương pháp ihực hành đế giải quyết các vấn đề nêu trên nãm trong môn học 1 oi ưu hóa ha\ còn gọi là Quy hoạch toán học. 1.1. Bài toán tối UXỈ hóa tổng quát Bài loán tói ưu hóa lổna quát được p h aỉ biéu Iihư sau: Cực đại hóa (cưc ticu hóa) hàm; i ' ( x ) m a x (rniii) (1-1) Với các dicLi kiện: g,(x) () b,. i = Km (1.2) xeX cR " (1.3) Bài toán (1.1) (1.3) dirực ízọi ià mộl cỊuỵ hoạch, hàm f(x) được gọi là h à m m ụ c tiê u , c á c h à m tỉ,(x), i = i , m đu'Ọ'c uọi là cáic h à m r à n g b u ộ c , m ỗ i đ ả n g Ihức hoặc bất đẳng ihức trong hộ (1.2) được gọi là niiội ràng buộc. Tập hợp: 13
D={xeX g,(x) ( < , = . > ) b,. i = l , m ( (1.4) được gọi là miền ràng buộc (hay miồn chấp nhận được). Mỗi điểm X = (X|, X ,...., x j e D được g ọ i là m ột phươníỉ án ( h a y m ộ t lời g i ả i c h ấ p n h ậ n được). Một phương án X* e D đạt cực đại (hav cực liêu) của hàm m ục tiêu, cụ thê là: f(x*) > f(x), Vx e D (cìối với bài toán m ax) f(x*) < f(x), Vx € D (đối vói bài toán min) được gọi là phương án tối ưu (lời giải tối ưu). Khi đó siá trị f(x*) được gọi là giá trị tối ưu của bài toán. 1.2. Phân loại các bài toán • Một trong những phươ na pháp hiển nhiên nhâì đê aiải bài toán đật ra là phương pháp điểm diện: tính aiá trị hàm mục tiêu f(x) trên tất cả các phươna án, sau đó sosánh các siá trị tính đu'Ợc để lìm ra ẹiá trị tối ưu và phươnơ án tối ưu của bài toán. Tuy nhiên cách giải quyết này khó có thể thực hiện được, n»ay cả khi kích thước của bài toán (số biến n và số ràng buộc m) là khôno lớn, bởi vì tập D thông thường g ồ m m ột số rất lớn các phần tử, tr ona nhiều trường hợp còn là không đếm được. Vì vậy cần phải có những nghiên cứu trước về mật lý thuyết đê có thê tách ra từ bài toán tổng quát n hữns Ictp bài toán “dễ giái” . Các nahiên cứu [ý thuyết đó thường là: - Nghiên cứu các tính chấl của các thành phần bài toán (hàm m ụ c tiêu, các hàm ràng buộc, các biến số, các hệ số....) - Các điều kiện tồn tại lời siâi chạp nhận (tươc - Các điều kiện cần và đủ của cực trị Tính chất của các đối lượng imliièn cứu Các tính chất của các thành phần cùa bài toán và đối lượns nsh ièn cứu giúp ta phân loại các bài toán. Một bài toán lối ưu (quv hoạch toán học) được gọi là; - Quy hoạch tuyến tính (QHTT) nếu hàm mục tiêu f(x) và tất cả các hàm ràng buộc g,(x). i = l , m là tuyến tính. Một trườna hợp riêno quan trọne của Q H T T là bài toán vận tải (BTVT) 14
- Quy hoạch tham sô (QHTS) nếu c;k; ìii' S ! iKi rit biểu thức của hàm mục ( tiêu và của các ràng buộc phụ thuộc vào tỈKìn; ^.0 - Quy hoạch động (Q ỉiĐ ) nếu đối Uiun.^ 'a-i ia các quá trình có nhiều giai đoạn nói chung, hav các quá trình phái tricii ỉhco lỉìời gian nói riêng, hay là trườne hợp hàm mục liêu có d a n s tách bion - Quy hoạch phi tuvến (QHPT) néu ỉ(,\) lìoãt LÓ ít nhất một trong các hàni g (x) là phi tuyến hoặc cá hai trường họp dó cùng x ay ra - Quy hoạch rời rac (Q H R R ) nếu miổn ràng bu(>c D là tập rời rạc. Trong trường hợp riêns khi các biến chi nhận giá trị ngu\cn ta có quy hoạch nguyên (QHN). iMộl trườns hợp riêng của QHN là quỵ hoach DÌến boolcs khi các biến số chi nhận siá Irị 0 hoặc 1 - Quy hoạch đa mục tiêu ( Q H Đ M D IIC írén cLing một miền ràng buộc ta II xét nhiều hàm mục tiêu khác nhau. §2. VẤN ĐỀ MÔ HÌNH HÓA TOÁN HỌC Tron» mục này ta sẽ nói về việc xày dưng mỏ hình toán học cho một vấn đé thực tế. Sau đó giới thiệu niột số mỏ hìĩih iliụv Ic q u a n trọng. 2.1. Xây dựng mò hình toán học cho một vấn đề thực tế Viêc mổ hình hóa loán học cho niỏl \âii dc chirc tế có thể chia ra làm bốn bước: B ước I: Xâv dưiiiĩ mò hình ctịiih tiM clìo \:tn do thực lế. lức là xác định Ìi c á c y ế u tô c ó V n e h ĩ a q u a n irọniỉ nhâì va xác líip i;á( quv' luật m à c h ú n g phải tuân theo. Nói một cách khác là phái biếu mó IV hãng Jò'i và bằng nhĩrng biếu đồ, inli các điều kiện về kinh tế. kỹ thuặl. tự nhiên. \ã liói, ( Ú lĩiục liêu cần đạt được. L B ư ớ c 2: Xây dựntỉ mò hình loán học clid V đớ dang xét. tức là diễn lả ÍIII lại dưới n sô n ngữ toán học cho mô hình (lịnh línli. Khi cỏ một hệ thống ta chọn các biến số đặc trưng cho các trạns thái cua hè ihốrm. M ô hình toán học thiêt lập mối liên hệ giũ’ các biên sỗ và các hé số dieu khiển hiện tượng. Việc làm a quan trọng ớ bước này là phái xác định hàm mục tiêu, tức là một đặc trưng bằnơ số mà giá trị càng lớn (càng nhó) cùa nó lương ứ'ng với hiệu quả càng tốt 15
h ư n iziái q u y ố í v ấ n d e m à nuLrời lì h ậ ii lời e ì a i m o i i e ỉ i ì u ỏ n . 'I'iẽp I h c o đó là p h a i dicn tá bãniz các phươne trình hoặc bat phu'í)nu íiinh các diéư kiện kinli Ic. kv ihiiậL... đó ỉa các rànu buộc loán lìọc nià các biên số pluii tuân llieo. B iiớ c 3 : Sư dụ n ii c á c cỏiiii c ụ to á n học đê k h a o sal \'à eiái q u y c ì bài loán h ì n h Ihàiìh t r o i m b ư ó v 2. Cãỉ ì c ứ v à o n i ỏ hìiih d a x â y đ ự í m c á n p h a i c h ọ i i h o ặ c xây dựníi phươne pháp eiai cho phù họp. Tiép dó cụ the hỏa plìươĩií^ pháp bãim các ihiiâl loán tối ưu. Vì các hài \oi\n ihưc tê ihirờỉie có kích thước lởn nên khỏrm thê eiài bầne lav dươc m à pliai sử dunu nìáy tíiìh diên từ. V ây cán chưưne trình hổa ihuạt toán bằne một neỏn n s ữ lập irình phù hợp. Sau đó dưa lên máy tính điện iư đe chạv và in ra kc'l quá. B ư ớ c 4: Phàn tích và kicin định lại các kèì qua lính toán thu được tronii Ixrớc 3. Trone bước nàv can phái xác định mức độ phù họp của m ò hình và kết quá íính toán bàny; thực nehiệin hoặc áp dụniz phươne pháp phân lích chuvên iũa níỉuừi sử dụng và niáv lính điện lử, không đòi hỏi neưừi sứ dụne phai có trình độ chuyên m òn cao vé toán và lia học. Kliíi nĩuìỊị 2: Mồ hình và các kết quá lính toán khổĩiii phù họp với thực tế. Trons: Irường hợp này cần phái xem xél cúc nouycn nhân của nỏ. Có thể nêu ra bốn níỉuvcn nhân sau: * NỊịiiycii nhân 1: Các kết quá lính toán tronc btrớc 3 chưa có đủ độ chính xác cần thiết. Khi dó cần phải xem lại các thuật toán cũn>z như các chươna trình tính t o án đã viết và s ử d ụ n e . * NiỊiiyèìì lìhâii 2: Các số liệu ban đầu (các hệ số, thông số) không phản ánh thực lế giá cả hoặc chi phí trên thị trườim hoặc các định mức vật tư. hoặc 16
các số liệu khúc về công suất, kha nãni: inií) du !rũ' tài nguyên,... Lúc này cần điổLi c h ỉ n h lại một cách nghiêm tLÌc, chínli \ K. NỊ^iiyêii lìliân 3: Mô hình định tínli xa\ (ỉiinụ chưa phản ánh được đầy đú hiện tượns thực tế. Nôu vậy cán I'a s o á i lai luiov I xem có yếu tố hoặc quy luậl nào còn bị bo sót khònu? * Níịiiyêiì nlìún 4; Vicc xây dưnu mo h ì n h l o á n học ở bước 2 chưa thỏa dáns. Cần phai xàv d ự n s lại cho phù họp IIIÚ clo lăna dần từ tuvến tính đến V phi tu v ế n . từ tĩnh đ ế n đ ộ n g , từ tất đ ịn h đến neẫu Iihiên. 2.2. Một sô mò hinh thực tê • ■ 2.2.1. Bài toán lập k ế hoạch sản x u ấ t tối uv Một công ly muốn sản xuất hai !oai san phàm niới A và B bằng các loại Iiiỉuỵên liệu I, II và IIÌ. Suất chi phí n^uyẽn licu dc san xuất các sán phẩm đó ciio irong bảng sau: ị ỉ Sản phẩm Nguyên ỉiệu A 1 B ......■■ ■ ■ ■ ■ ■ ■ ■ ỉ ỉ 2 1 1 1 ■ " ^ II 1 ! 2 III 0 I 1 Có nchĩa là: - Đê’ sàn xuất một đơn vị san phâni A càii tiuiiiỉ ?, dơn vị imuyên liệu I \'à ỉ d()'n vị nguyên liệu II. - Đế sân xuấl mộl đơn vị sán phám B cần (lung I (tơn vị nouyên liệu I, 2 đơn vị Iì2 uycn liệu II và I đơn vị nỵuvên liêu lli. Ban giám đốc còng ty có dự Irữ các loại n su y ê n liệu I, II và III iươni: ứnj: ỉii H 7' \ à 3 đơn vị, Tiền lãi một . đơn vị sàn phẩm A và B tưoìi” ứn« là 4 tricu donu \ à 5 Iriệu đồng. Cần lập kế hoạch sán xuất sao cho công tv thu được licn lã) lớn nhất với điều kiện hạn chế vể nsLiyên liệu. Kv hiệu X, là lượne sán phám loại A, X, ià lượno san phẩm loại B cần sán xuất. 17
M ô hình toán học có dạnạ: f(x) = 4X| + 5x, — max > 2X| + X, < 8 X| + 2x, < 7 x ,< 3 . X |,X 2>0 Đày là một bài toán QHTT. * Bùi toán lập ké hoạch sàn xu ấ t tổng cỊỉiát có dạng n h ư sau: Giả sử công ty sản xuất n loại sản phẩm và sử dụng m loại nguyên liệu. Ta đưa vào các ký hiệu sau; X lượng sản phẩm loại j, (j = j! n ) cần sản xuất; Cj: tiền lãi một đơn vị sản phẩm loại j, (j = 1, n ); a,ị: lãi suất chi phí nguyên liệu loại i đế sản xuất một đơn vị sản phẩm loại j; b,: lượng dự trữ n g uyên liệu loại i, (i = l , m ). Trong các điều kiện đã cho hãy xác định các giá trị Xj, (j = 1, n ) sao cho tổng tiền lãi (hay tổng giá trị sản phẩm hàng hóa) là lớn nhất với điều kiện hạn chế về nguyên liệu. M ô hình toán học có dạng: lì f(x) = ^ max ( 2 . 1) ' n ____ < b , j = l, m (2.2) J=| X > 0, j = l , n , (2.3) 2.2.2. Bài toán vận tải Có m kho hàng c ù n s chứa một loại hàng hóa (đánh sô' i = l , m ) lượng hàng có ở kho i là a„ (i = 1, m ). Gọi kho i là điếm p h á t i. Có n địa điểm tiêu thụ
loại hàng trên (đánh số J = l,n ) với nhu cáíi licu itiLi ở điểm j là bj, (j = l,n ). Gọi điếm tiêu thụ j là điểm thu j, Biết C|| là cước phí vạn chuyển một (1(tn VỊ h a n g hóa từ điểm phát i đến điếm thu j (i = l , m . j = l.n ). Hàng có thế chu\ển lừ điểm phát i bất kỳ đến điểm thu j bất kỳ. Hãy lập k ế hoạch vận chuyên hàrm hóa từ điếin phát đến các điểm thu sao cho tổng chi phí vận chuyển là nhỏ nhất với các điều kiện: các điểm phát thì phát hết hàng hóa, còn các điểm thu thì thỏa mãn Iihu cầu. Đ ó là mô hình định tính của BTVT. Ký hiệu x,| là lượng hàng vận chuyển từ đièm phát i đến điểm thu j. Khi đó ta có mô hình toán học: (2.4) í=l 11 = với các điều kiện sau: --- = a , , i = l,m (2.5) J! = = b , , j = l,n ( 2 .6 ) 1-1 . X , J > 0, i = l, m j = l,n , (2.7) Ngoài ra còn điều kiện cân bằng thu phát: n ì 11 (2.8) i=i j-i Có thể chứng minh điều kiện cân bằng ihii - phát như sau: - Lấy tổng 2 v ế của (2.5) theo i = l,m : n i n n ì (2 .5)’ 1=1 J=I 1=1 -- Lấy tổng 2 vế của (2.6) theo j = 1, n : 19
n in II .6) 11 1-1 = 11 = Vì hai tổnỉỉ ở vế trái 2 phương trình (2.5)’ và (2.6)' bằng nhau nên la sLi\ ra 2 tổng ở vế phái cũng bằng nhau. 2.2.3. Bài toán cái túi Một người du lịch muốn đem theo một cái túi nặng không quá b ks. C(í n loại đồ vật mà anh ta dự định đem theo. Mỗi một đồ vật loại j có khối lượng kg và trị giá Cj , người du lịch muốn chất vào các túi đồ vật sao cho tổng giá trị đồ vật đem theo là lớn nhất. Ký hiệu X, là số đồ vật loại j sẽ chái vào túi. Ta có bài toán sau: í ” ^ c.x 1 — max )• (2.9) 1-1 i a , x ^ < b (2.10) 1=! Xj > 0, j = Kn (2.11) V > nguyên, j = l, n (2.12) Đây là bài loán quy hoạch nguyên. 2.2.4. Bài toán về khẩu phẩn thức ăn Cần phải xây dựng k h ẩ u phần thức ăn từ n loại thực phẩm với đơn giá cho trước sao cho đ ảm bảo được yêu cầu về m loại chất dinh dưỡ ng và với giá rẻ nhất. KỶ hiệu: a,j: lượng chất dinh dưỡnsi loại i có trong inộl đơn vị khối lượng thực phẩm loại j; bị! lượng chất dinh dưỡng loại i cần có trong khẩu phần; c,; giá một đơn vị thực phẩrn loại j; (i = l , m , j = l , n ) . Gọi X: là lượna thực phẩm loại j tronạ khẩu phần (j = 1,11). Mô hình toán học của bài toán có dạna: 20