BÀI TẬP MÔN QUI HOẠCH TUYẾN TÍNH

Chia sẻ: Phuong Linh Le | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

398
lượt xem 82
download

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

Môn học được mở đầu bằng việc giới thiệu vài vấn đề thực tế dẫn đến mô hình quy hoạch tuyến tính. Trọng tâm của môn học là phần trình bày giải thuật đơn hình ở các mức độ sử dụng khác nhau. Lý thuyết đối ngẫu được trình bày một cách đơn giản. Phần ứng của quy hoạch tuyến tính được trình bày sau cùng để thấy sự ứng dụng rộng rãi của quy hoạch tuyến tính

Chủ đề:

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

Lưu

Nội dung Text: BÀI TẬP MÔN QUI HOẠCH TUYẾN TÍNH

TÀI TRỌNG NGUYỄN TỐI ƯU HÓA NGUYỄN THỊ NGỌC THANH BAØI TAÄP QUI HOAÏCH TUYEÁN TÍNH TS. Nguyeãn Thò Ngoïc Thanh I. PHÖÔNG PHAÙP ÑÔN HÌNH VAØ BAØI TOAÙN ÑOÁI NGAÃU Giaûi baøi toaùn qui hoaïch tuyeán tính sau vaø tìm phöông aùn toái öu khaùc (neáu coù ) : 1) f(x) = -x1 + 2x2 - x3  max x1 - 2x2 + x3  6 -2x1 + x2 - 2x3 + 4x4  5 x1 + x3 - x4  3 xj  0 ( j = 1,2,3,4) ÑS : fmax =19 2) f(x) = 2x1 + x2 - x3 + x4  min x1 + x 2 - x 3 - 2 x 4 = 2 - x2 + 3x3 + 7x4  2 2x3 + 3x4  5 xj  0 ( j = 1,2,3 ) (Chuù yù : Ñaët x4 = x14 - x24 . Ñaùp soá : x= (0, 0, 16 , - 9 , 17, 0) ; f(x) = - 25 ) 3) f(x) = 3x1 - x2 + 2x3 - x4  max x1 - x 2 + x 3 + x4 + x5 = 6 2x1 + x2 - 2x4 + x5  8 x1 + 2x4 + x5  9 xj  0 ( j = 1,2,3,4,5 ) (Chuù yù : Caùch choïn aån ñöa vaøo trong baûng ñôn hình 2.) Ñaùp soá : x= (0, 17, 37/2 , 9/2 , 0, ) ; f(x) = 31/2 ) 4) f(x) = 2x1 - 3x2 - 4x3 + x4  min 3x1 + x2 + 2x3 - 4x4 = 2 2x1 - x3 - 3x4  1 x1 - 4x3 - 2x4  4 xj  0 ( j = 1,2,3 ) , x4  0 Ñ.S : x = ( 0, 2/3,0, -1/3) fmin = - 7/3. 5) Cho baøi toaùn qui hoaïch tuyeán tính sau : f(x) = 3x1 + 2m x2 + x3  min - x1 + x 2 + 2x3 = 6 x1 + 2x2 + (m-2) x3  5 3x1 - x2 + 2x3 = 14 xj  0 ( j = 1,2, 3 ) a) Giaûi baøi toaùn vôùi m =1. b) Tìm giaù trò cuûa m ñeå x0 = (2,0,4) laø phöông aùn toái öu cuûa baøi toaùn. (Ñaùp soá : a) x = (2,0,4,7) ; f(x) = 10. b) – 5/8  m  11/4 6 ) Cho baøi toaùn qui hoaïch tuyeán tính sau : f(x) = -2x1 + mx2 + 4x3 + 4 x4  min -x1 + 2x3 + x4 = 6 3x3 - 2x4  - 4 - x2 + x 3 + x 4 = 4 xj  0 ( j = 12,3,4 ) taitrongnguyen107@gmail.com Trang 1/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
TÀI TRỌNG NGUYỄN TỐI ƯU HÓA NGUYỄN THỊ NGỌC THANH a) Giaûi baøi toaùn treân khi m = 2. b) Vôùi giaù trò naøo cuûa m phöông aùn toái öu tìm ñöôïc trong caâu a cuõng laø phöông aùn toái öu cuûa baøi toaùn? c) Vôùi nhöõng giaù trò naøo cuûa m baøi toaùn khoâng coù phöông aùn toái öu ? ( Ñ.S : ( 2 , 0 , 4 , 0 , 16 ) ; m  0 ; m < 0) 7) Cho baøi toaùn qui hoaïch tuyeán tính sau : f(x) = (8 + 2)x1 + (7 + 7)x2 + (3 + 2)x3  min 2x1 + x2 1 x1 + 2x2 + x3  1 xj  0 ( j = 1,2,3 ) a) Giaûi baøi toaùn treân vôùi  = 0 vaø  = 1 b) Chöùng toû raèng vôùi   (-oo ; -3/2 ) , f(x) khoâng bò chaën döôùi treân taäp hôïp caùc phöông aùn (Höôùng daãn : döaï vaøo phöông aùn toái öu cuaû baøi toaùn khi  = 1) 8) Cho baøi toaùn qui hoaïch tuyeán tính sau : f(x) = x1 + 2x2 + 3x3  min x1 + x 2 + x 3  6 2x1 + x2 + x3  7 x1 + 2x2 = 5 xj  0 ( j = 1,2,3 ) a/ Giaûi baøi toaùn treân. Tìm phöông aùn toái öu khaùc (neáu coù) b) Vieát baøi toaùn ñoái ngaãu. Tìm phöông aùn toái öu cuûa baøi toaùn ñoái ngaãu. (Ñs: x1 = (3,1,0,2,0) ; x2 = (5,0, 0,1,3) ; y = ( 0, 0 ,1) , fmin = dmax = 5 ) 9) Cho baøi toaùn qui hoaïch tuyeán tính sau : f(x) = -2x1 +3x2 +x3 +x4 - 4x5  max 3x1 - 2x2 + x3 - 4x4 + 2x5 = 9 7x1 - 3x2 - 7x4 + 5x5 = 14 4x1 - 2x2 - 4x4 + 3x5 = 8 xj  0 ( j = 1,2,3,4,5 ) a) Giaûi baøi toaùn treân b) Vieát baøi toaùn ñoái ngaãu, chæ caùc caëp raøng buoäc ñoái ngaãu. Tìm taát caû phöông aùn toái öu cuûa baøi toaùn ñoái ngaãu. (ÑS: x = (2,0,3,0,0) f(x) = -1 y1 =1 ; y2 =t ; yû 3 = - (5+ 7t )/4 vôùi 5  t  9 hoaëc y1 = 1 ; y2 = - ( 5+ 4t )/7; yû 3 = t vôùi – 17  t  -10) 10) Cho baøi toaùn qui hoaïch tuyeán tính sau : f(x) = 3x1 - 2x2 +x3  min x1 + 4x2 - 2x3 = 4 -x1 + 2x2 + 4x3 ≤ 6 4x1 + x2 + 5x3 ≥ 2 x1  0; x2≤ 0 coù phöông aùn toái öu laø x= (24/13; 0; -14/13). taitrongnguyen107@gmail.com Trang 2/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
TÀI TRỌNG NGUYỄN TỐI ƯU HÓA NGUYỄN THỊ NGỌC THANH Haõy vieát baøi toaùn ñoái ngaãu, chæ caùc caëp raøng buoäc ñoái ngaãu, tìm phöông aùn toái öu cuûa baøi toaùn ñoái ngaãu vaø giaù trò haøm muïc tieâu öùng vôùi PATÖ tìm ñöôïc. (ÑS Y = (11/13, 0, 7/13) dmax= 58/13 ) 11) Cho baøi toaùn qui hoaïch tuyeán tính sau : f(x) = x1 + x2 + 2x3 + x4  min 2x1 + x2 + x3 + x4  11 x1 + 2x3 + x4  11 x1+ 3x2 + x3 + x4  1 4 xj  0 ( j = 1,2,3,4 ) (ÑS: x =(0,1,0,11) f(x) = 12) x2= (11, 1, 0, 0 ) 1 (Neân chuyeån veà baøi toaùn ñoái ngaãu ñeå giaûi ) 12 ) Cho baøi toaùn qui hoaïch tuyeán tính sau : f(x) = x1 + 3x2 + 4x3  min 3x1 - x2 + 2x3  7 - 2x1 + 4x2 + x3 = 12 - 4x1 + 3x2 + 8x3  10 xj  0 ( j = 1,2,3 ) Haõy xeùt xem caù vec-to x1 = ( 7/2, 9/2,1); x2 = ( 2, 7/2, 2) vaø x3 = (4, 5, 0 ) coù phaûi laø phöông aùn toái öu cuûa baøi toùan treân khoâng? 13) Moät nhaø maùy coù 2,8 tyû ñoàng duøng ñeå mua thieát bò cho khu vöïc saûn xuaát môùi . Khu vöïc daønh ñeå ñaët thieát bò coù dieän tích 166 m2. Coù 2 loaïi thieát bò coù theå choïn mua : -Maùy loaïi A: moät maùy giaù 160 tr . ñoàng , trong 1 giôø hoaït ñoäng saûn xuaát ñöôïc 110 saûn phaåm , ñeå hoaït ñoäng vaø cung caáp saûn phaåm ñöôïc caàn chieám 1 dieän tích laø 12m2 - Maùy loaïi B: moät maùy giaù 180 tr. ñoàng , trong 1 giôø hoaït ñoäng saûn xuaát ñöôïc 100 saûn phaåm , ñeå hoaït ñoäng vaø cung caáp saûn phaåm ñöôïc caàn chieám 1 dieän tích laø 9m2 Tìm phöông aùn mua thieát bò toái öu sao cho trong 1 giôø toång soá saûn phaåm ñöôïc saûn xuaát ra trong khu vöïc saûn xuaát môùi laø nhieàu nhaát. ( ÑS: 7maùy loaïi A vaø 9 maùy loaïi B) 14) Moät nhaø maùy loïc daàu hieän coù caùc loaïi daàu thoâ vôùi khoái löôïng laàn löôït laø 30000 , 25000vaø 42000 ñôn vò . Kí hieäu caùc loaïi daàu thoâ laàn löôït laø A,B,C . Ngöôøi ta coù theå cheá bieán thaønh 3 loaïi saûn phaåm laø khí ñoát , xaêng , daàu theo 3 phöông thöùc cheá bieán sau ñaây: Phöông thöùc cheá bieán Keát quaû Khí ñoát Xaêng Daàu 2A + 1B + 1C (I) 9 4 7 2A + 2B + 1C (II) 10 6 10 1A + 1B + 1C (III) 6 3 5 Giaù baùn 1 ñv saûn phaåm 1 3 2 Giaûi baøi toaùn tìm keá hoaïch saûn xuaát toá öu sao cho toång doanh soá baùn ra laø nhieàu nhaát. ( Ñ.S : f(x) = 675000) taitrongnguyen107@gmail.com Trang 3/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
TÀI TRỌNG NGUYỄN TỐI ƯU HÓA NGUYỄN THỊ NGỌC THANH 15) Bieát yeâu caàu caùc chaát dinh döôõng Protit , Lipit trong 1 ngaøy cuûa moät loaïi gia suùc ; tæ leä % theo khoái löôïng , caùc chaát dinh döôõng coù trong caùc loaïi thöùc aên A , B , C vaø giaù thöùc aên cho trong baûng sau : .Chaát dinh Khoái löôïng Khoái löôïng toái Tæ leä % trong caùc loaïi thöùc aên döôõng toái thieåu (g) ña (g) A B C Protit 70 Khoâng haïn cheá 50 40 30 Lipit 20 30 20 30 30 Giaù (ngaøn ñoàng / kg ) 8 7 6 Yeâu caàu laäp moâ hình vaø giaûi baøi toaùn tìm khoái löôïng thöùc aên toái öu caàn mua trong 1 ngaøy ñeå nuoâi loaïi gia suùc ñoù. (Ñ.S :f(x) = 1120 ñoàng ) 16) Moät xí nghieäp coù theå saûn xuaát 3 loaïi saûn phaåm , kyù hieäu laø A , B, C . Ñònh möùc hao phí nguyeân vaät lieäu , voán, lao ñoäng (giôø coâng ) vaø lôïi nhuaän thu ñöôïc tính cho 1 ñôn vò saûn phaåm moãi loaïi cho trong baûng sau : Saûn phaåm A B C Möùc huy ñoäng toái ña Nguyeân lieäu ( kg ) 2 3 3 150 Voán ( 1000ñ) 1 3 5 120 Lao ñoäng (giôø coâng) 4 8 1 100 Lôïi nhuaän (1000ñ) 2 3 5 Xí nghieäp seõ saûn xuaát bao nhieâu saûn phaåm moãi loaïi sao cho trong phaïm vi soá nguyeân lieäu , voán, giôø coâng huy ñoäng ñöôïc , xí nghieäp ñaït lôïi nhuaän cao nhaát .(Bieát raèng SP saûn xuaát ra tieâu thuï ñöôïc heát). a) Haõy laäp moâ hình baøi toaùn treân. b) Giaûi baøi toaùn tìm phöông aùn saûn xuaát toái öu ? c) Tìm lôøi giaûi toái öu cuûa baøi toaùn ñoái ngaãu ? Ñ.S : fmax = 140 (ngaøn ñoàng) 17) Moät xí nghieäp coù theå saûn xuaát 3 loaïi saûn phaåm , kyù hieäu laø S 1, S2, S3 , cung öùng cho thò tröôøng . Cho bieát naêng suaát cuûa xí nghieäp ñoái vôùi moãi saûn phaåm laø S1 : 50 sp/giôø , S2 : 25 sp/giôø , S3 : 75 sp/giôø. Naêng löïc saûn xuaát trong moät tuaàn cuûa xí nghieäp theå hieän baèng soá giôø saûn xuaát toái ña laø 45 giôø. Nhu caàu haøng tuaàn veà saûn phaåm cuûa xí nghieäp ôû thò tröôøng do xí nghieäp cung öùng laø 600 saûn phaåm S1 , 800 saûn phaåm S2 vaø 1200 saûn phaåm S3. Giaù baùn moãi ñôn vò saûn phaåm S1 laø 40.000ñ, saûn phaåm S2 laø 120.000ñ vaø saûn phaåm S3 laø 30.000ñ. a) Laäp moâ hình baøi toaùn QHTT tìm keá hoaïch saûn xuaát cuûa xí nghieäp trong moät tuaàn cho doanh thu cao nhaát ( boû qua ñieàu kieän nguyeâu ôû caùc bieán soá ). b) Döïa vaøo suy luaän kinh teá tröïc tieáp , caên cöù vaøo giaù baùn , naêng löïc saûn xuaát , naêng löïc lao ñoäng ( saûn phaåm/giôø saûn xuaát) , haõy tìm keá hoaïch saûn xuaát toái öu cho baøi toaùn . c) Duøng phöông phaùp ñôn hình giaûi baøi toaùn ôû phaàn a. d) Vieát baøi toaùn QHTT ñoái ngaãu töông öùng . Tìm lôøi giaûi toái öu cho baøi toaùn ñoái ngaãu. fmax = 125.250 (ngaøn ñoàng ) 18) Moät xí nghieäp goàm 2 phaân xöôûng , coù theå saûn xuaát hai loaïi saûn phaåm , kyù hieäu S1 vaø S2 . Hao phí saûn xuaát ñöôïc tính baèng giôø maùy . Giaû raèng xí nghieäp coù theå söû duïng nhaân coâng khoâng haïn cheá . Saûn löôïng trong thaùng vöø a qua cuûa xí nghieäp laø 5.000 saûn phaåm S1 vaø 7.000 saûn phaåm S2 . Ñeå coù ñöôïc 5.000 saûn phaåm S1 xí nghieäp ñaõ söû duïng 650 giôø maùy ôû phaân xöôûng 1 vaø 125 giôø maùy ôû phaân xöôûng 2 . Soá giôø maùy hao toán ñeå saûn xuaát 7.000 saûn phaåm S2 ôû moãi phaân xöôûng laø 350 giôø . Cho bieát giaù baùn moãi saûn phaåm S1 laø 25.000 ñ , moãi saûn phaåm S2 laø 15.000 ñ. taitrongnguyen107@gmail.com Trang 4/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
TÀI TRỌNG NGUYỄN TỐI ƯU HÓA NGUYỄN THỊ NGỌC THANH a) Döïa vaøo soá lieäu thaùng vöøa qua haõy laäp moâ hình baøi toaùn QHTT tìm keá hoaïch saûn xuaát cho thaùng naøy sao cho toång doanh thu ñaït cao nhaát , neáu bieát toång soá giôø maùy coù ñöôïc ôû phaân xöôûng 1 laø 1100 giôø vaø ôû phaân xöôûng 2 laø 550 giôø , giaù baùn saûn phaåm khoâng thay ñoåi . b) Giaûi baøi toaùn treân baêng phöông phaùp ñôn hình . c) Vieát baøi toaùn QHTT ñoái ngaãu töông öùng. Tìm lôøi giaûi toái öu cuûa baøi toaùn ñoái ngaãu. (* Ñ.S : soá saûn phaåm S1laø 5238 , S2 laø 8381 fmax = 256.665 ngaøn ñoàng ) 19) Moät xí nghieäp coù theå saûn xuaát moät loaïi saûn phaåm töø hai phaân xöôûng khaùc nhau. Caên cöù vaøo caùc nguoàn löïc hieän coù trong 1 tuaàn phaân xöôûng 1 coù theå saûn xuaát toái ña 70 saûn phaåm , phaân xöôûng 2 saûn xuaát toái ña laø 100 saûn phaåm . Toång soá giôø coâng xí nghieäp coù theå söû duïng trong tuaàn ôû caû hai phaân xöôûng laø 600 giôø . Soá giôø coâng caàn thieát ñeå saûn xuaát moät ñôn vò saûn phaåm ôû phaân xöôûng 1 laø 10 giôø , ôû phaân xöôûng 2 laø 5 giôø . Möùc saûn löôïng toái thieåu trong tuaàn cuûa xí nghieäp laø 80 saûn phaåm . Chi phí saûn xuaát cho moät ñôn vò saûn phaåm ôû phaân xöôûng 1 laø 20 ngaøn ñoàng vaø ôû phaân xöôûng 2 laø 30 ngaøn ñoàng . a) Haõy laäp moâ hình baøi toaùn QHTT , giaûi vaø tìm keá hoaïch saûn xuaát trong tuaàn ñaûm baûo toång chi phí saûn xuaát thaáp nhaát. b) Trong moâ hình a) cho bieát baøi toaùn QHTT coøn coù yù nghóa nöõa khoâng ,neáu boû raøng buoäc veà saûn löôïng toái thieåu ( 80 saûn phaåm ). c) Cho bieát giaù baùn moät ñôn vò saûn phaåm ñöôïc aán ñònh laø 50 ngaøn ñoàng . Döïa theo naêng löïc hieän coù vaø yeâu caàu saûn löôïng toái thieåu trong tuaàn , moãi phaân xöôûn g phaûi saûn xuaát bao nhieâu saûn phaåm ñeå xí nghieäp ñaït lôïi nhuaän cao nhaát ? d) Vieát baøi toaùn QHTT ñoái ngaãu cuûa baøi toaùn ôû phaàn c. Tìm PATU cuûa baøi toaùn ñoái ngaãu. * Ñ.S : a) : fmin = 2000 ngaøn ñoàng ; c) : fmax = 2300 ngaøn ñoàng ) 20) Ñeå saûn xuaát moät hoãn hôïp nhieân lieäu ngöôøi ta söû duïng 3 loaïi thaønh phaàn , kí hieäu laø N1,N2,N3. Nhieät löôïng rieâng cuûa N1, N2, N3 töông öùng laø 7.000, 4.000, 5.000 (Kcal/ñvkl). Ñvkl : ñôn vò khoái löôïng . Chi phí söû duïng 1 ñvkl nhieân lieäu N1, N2, N3 töông öùng laø 2, 1, 2 ñôn vò tieàn teä.Haõy choïn cô caáu thaønh phaàn hoãn hôïp sao cho toång khoái löôïng nhieân lieäu hoãn hôïp khoâng vöôït quùa 3.000 ñvkl,toång chi phí söû duïng khoâng vöôït quùa 4.000 ñôn vò tieàn teä , loaïi nhieân lieäu N3 ñöôïc söû duïng khoâng quùa 500 ñvkl, loaïi nhieân lieäu N1 phaûi ñöôïc söû duïng ít nhaát 500 ñvkl vaø ñaït ñöôïc nhieät löôïng toûa ra toái ña khi söû duïng heát hoãn hôïp nhieân lieä u thaønh phaàn . Ñ.S : fmax = 15.000.000 Kcal 21) Ngöôøi ta caàn caét nhöõng thanh goã daøi 2m thaønh 520 ñoaïn daøi 1,2m ; 400 ñoaïn daøi 0,8m vaø 300 ñoaïn daøi 0,6m . Haõy giaûi baøi toaùn tìm phöông aùn SX sao cho soá goå thöøa laø ít nhaát. (Ñ.S:fmin = 36m ) 22) Moät coâng ty coù caùc ñôn ñaët haøng trong voøng 4 thaùng . Chi phí saûn xuaát thay ñoåi haèng thaùng do caùc thay ñoåi trong chi phí nguyeân vaät lieäu . Naêng löïc saûn xuaát cuûa coâng ty laø 100 ñôn vò/thaùng laøm trong giôø vaø 15 ñôn vò / thaùng laøm ngoaøi giôø. Baûng sau ñaây cho thaáy nhu caàu cuûa caùc ñôn ñaët haøng vaø chi phí saûn xuaát haøng thaùng : Döõ lieäu Thaùng 1 Thaùng 2 Thaùng 3 thaùng 4 Khoái löôïng ñôn haøng(ñôn vò) 95 85 110 115 Chi phí trong giôø/ñ.v (tr.ñ) 30 30 32 32 Chi phí ngoaøi giôø/ñ.v (tr.ñ) 35 35 37 36 Chi phí löu kho cho 1 ñôn vò haøng hoùa chöa baùn ñöôïc laø 2 tr.ñ/thaùng/1ñ.vò. Coâng ty khoâng coù 1 ñôn vò haøng hoùa naøo vaøo ñaàu thaùng 1vaø mong raèng cuõng khoâng coøn 1 ñôn vò haøng hoùa naøo vaøo cuoái thaùng 4. taitrongnguyen107@gmail.com Trang 5/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
TÀI TRỌNG NGUYỄN TỐI ƯU HÓA NGUYỄN THỊ NGỌC THANH Haõy laäp moâ hình xaùc ñònh soá ñôn vò haøng saûn xuaát trong giôø vaø ngoaøi giôø moãi thaùng ñeå ñaùp öùng nhu caàu vôùi chi phí thaáp nhaát . 23) Moät nhaø maùy loïc daàu hieän coù 2 loaïi xaêng daàu cô baûn vôùi caùc ñaëc tröng nhö sau : Xaêng daàu cô baûn Chæ soá Octan Aùp suaát hôi nöôùc Soá löôïng (thuøng) Loaïi 1 104 5 30.000 Loaïi 2 94 9 70.000 Giaû söû raèng nhöõng loaïi xaêng daàu naøy coù theå pha troän laïi ñeå saûn xuaát 2 loaïi saûn phaåm cuoái cuøng : xaêng duøng cho maùy bay vaø xaêng duøng cho oâ toâ vôùi caùc ñaëc tröng nhö sau SP. Cuoái cuøng Chæ soá Octan Aùp suaát hôi Möùc baùn cao Giaù baùn nhoû nhaát nöôùc cao nhaát nhaát (thuøng) (USD/thuøng) Xaêng maùy bay 102 6 20.000 45,1 Xaêng oâ toâ 96 8 Soá löôïng baát kì 32,4 Haõy laäp moâ hình xaùc ñònh phöông aùn pha troän sao cho doanh thu töø vieäc baùn caùc saûn phaåm cuoái cuøng laø lôùn nhaát. 24) Moät coâng ty döï ñònh troàng 2 loaïi caây laø caø pheâ vaø tieâu treân 3 khu ñaát A, B, C coù dieän tích töông öùng laø 50, 60 vaø 40 (ha). Do ñaëc ñieåm cuûa caùc khu ñaát khaùc nhau neân chi phí saûn xuaát (trieäu ñ/ha ) vaø naêng suaát ( taï/ha) khaùc nhau vaø cho ôû baûng sau : Khu ñaát Caø pheâ Tieâu A 2 9 1,8 6 B 2,2 10 1,6 5 C 2,5 12 1,5 4 ( Soá lieäu ôû goùc traùi cuûa moãi oâ laø chi phí saûn xuaát; ôû goùc phaûi cuûa moãi oâ laø naêng suaát ) Yeâu caàu saûn löôïng toái thieåu cuûa caø pheâ laø 500 taï vaø tieâu laø 420 taï. Haõy laäp moâ hình xaùc ñònh phöông aùn phaân phoái ñaát troàng sao cho ñaûm baûo yeâu caàu veà saûn löôïng vôùi chi phí thaáp nhaát. 25) Ñeå phuïc vuï cho vieäc xaây döïng moät coâng trình ,ngöôøi ta caàn coù ít nhaát : 4000 thanh saét daøi 9m, 5000 thanh saét daøi 8m vaø 3000 thanh daøi 6m. Caùc thanh saét naøy ñöôï caét töø nhöõng thanh coù ñoä daøi 20m. Moãi thanh saét daøi 20m mua vôùi giaù laø 6 trieäu ñoàng. Soá saét thöøa coù ñoä daøi töø 4m- 5m coù theå baùn vôùi giaù 5 ngaøn ñoàng /m ; coøn neáu coù ñoä daøi < 4m thì baùn vôùi giaù 3 ngaøn ñoàng/m. Haõy laäp moâ hình xaùc ñònh phöông aùn caét saét sao cho chi phí thaáp nhaát. 26) Moät coâng ty muoán thöïc hieän chieán löôïc quaûng caùo moät loaïi saûn phaåm cuûa mình vôùi chi phí öôùc tính laø 150 trieäu ñoàng /thaùng. Coù 3 loaïi hình quaûng caùo ñöôïc choïn laø : tivi , baùo, ñaøi vôùi caùc döõ lieäu cho nhö sau : Loaïi hình quaûng caùo Tivi Baùo Ñaøi Chi phí 1 laàn quaûng caùo (trieäu ñoàng) 2 1,5 0,8 Soá laàn quaûng caùo toái ña trong thaùng 65 50 60 Döï ñoaùn soá ngöôi tieáp nhaän quaûng caùo 10 15 8 moãi laàn (ngaøn ngöôøi) Chieán löôïc quaûng caùo xaùc ñònh phaûi coù ít nhaát 30 laàn quaûng caùo treân tivi trong moät thaùng. Haõy laäp moâ hình baøi toaùn ñeå xaùc ñònh keá hoaïch quaûng caùo toái öu. 27) Moät xí nghieäp saûn xuaát 3 loaïi saûn phaåm A, B, C vôùi caùc döõ lieäu cho ôû baûng sau : Döõ lieäu SP. A SP.B SP.C Giaù baùn 1 saûn phaåm (ngaøn ñoàng) 80 160 250 Chí phí nguyeân lieäu cho 1 SP (ngaøn ñoàng) 40 70 120 taitrongnguyen107@gmail.com Trang 6/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
TÀI TRỌNG NGUYỄN TỐI ƯU HÓA NGUYỄN THỊ NGỌC THANH Thôøi gian hoaøn taát 1 SP (giôø) 0,2 0,3 0,6 Nhu caàu toái ña trong 1 tuaàn (SP) 1000 800 500 Xí nghieäp coù löïc löôïng lao ñoäng laø 20 ngöôøi, laøm vieäc 40 giôø/tuaàn vaø ñöôïc traû löông 400 ngaøn ñoàng/tuaàn/ngöôøi duø hoï coù laøm ñuû 40 giôø hay khoâng. Haõy laäp moâ hình baøi toaùn tìm keá hoaïch saûn xuaát sao cho toång lôïi nhuaän ñaït ñöôïc laø nhieàu nhaát. 28) Moät coâng ty coù 3 nhaø maùy A1, A2, A3 saûn xuaát moät loaïi saûn phaåm vaø phaân phoái ñeán 4 thò tröôøng B1, B2, B3, B4. Caùc soá lieäu cho nhö sau : Nhaø maùy Chi phí SX Coâng suaát (SP/ naêm) (ngaøn ñ/SP) A1 40 35.000 A2 42 40.000 A3 38 45.000 Thò tröôøng Giaù baùn (ngaøn ñ/SP) Nhu caàu ( SP/naêm) B1 90 25.000 B2 92 25.000 B3 88 35.000 B4 86 40.000 Ma traän chi phí vaän chuyeån nhö sau ( ngaøn ñ/SP ) . 24 30 28 28 C= 18 20 30 36 30 26 20 20 Haõy laäp moâ hình baøi toaùn xaùc ñònh saûn löôïng caùc nhaø maùy caàn saûn xuaát vaø phaân phoái ñeán caùc thò tröôøng trong naêm sao cho toång lôïi nhuaän thu ñöôïc nhieàu nhaát. 29) Coù 3 ngöôøi vaø 3 coâng vieäc. Chi phí ñeå ngöôøi i thöïc hieän coâng vieäc j ñöôïc cho trong baûn g sau ( ñôn vò :ngaøn ñ/ngöôøi): Coâng vieäc 1 2 3 Ngöôøi 1 7 4 3 2 5 7 6 3 10 9 8 Caàn phaân coâng ngöôøi naøo thöïc hieän coâng vieäc gì (moãi ngöôøi chæ laøm 1 vieäc, moãi vieäc chæ do 1 ngöôøi laøm) sao cho toång chi phí laø beù nhaát? Haõy vieát moâ hình baøi toaùn . 30) Ñaïi hoäi theá vaän ñöôïc toå chöùc ñoàng loaït cuøng ngaøy taïi 3 ñòa ñieåm (ta goïi laø caùc traïm thu ). Caùc nhu caàu vaät chaát ñöôïc chuyeån töø 3 ñòa ñieåm ( ta goïi laø caùc traïm phaùt). Baûng sau cho bieát yeâu caàu cuûa caùc traïm thu cuõng nhö löôïng haøng coù ôû caùc traïm phaùt ( taán); vaø khoaûng caùch giöõa caùc traïm (km) laø : T. Thu 15 20 15 T. phaùt 20 160 50 100 10 100 200 30 taitrongnguyen107@gmail.com Trang 7/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
TÀI TRỌNG NGUYỄN TỐI ƯU HÓA NGUYỄN THỊ NGỌC THANH 30 50 40 30 Do ñaëc ñieåm cuûa haøng hoaù, thôøi gian vaø phöông tieän vaän chuyeån neân khoâng theå chuyeån haøng xa treân 150 km. Theo yeâu caàu traïm phaùt thöù hai phaûi phaùt heát haøng Haõy laäp moâ hình baøi toaùn tìm phöông aùn vaän chuyeån thoaû maõn caùc ñieàu kieän neâu ra sao cho toång taán* km laø nhoû nhaát. 31) Moät coâng ty thöùc aên nhanh döï ñònh môû theâm nhaø haøng phuïc vuï. Coâng ty coù hai loaïi nhaø haøng dòch vuï tuyø choïn vaø dòch vuï choïn goùi. Moät nhaø haøng dòch vuï tuyø choïn coù chi phí xaây döïng 1 tyû ñoàng, caàn 5 nhaân vieân vaø doanh thu haøng naêm laø 4 tyû ñoàng. Moät nhaø haøng dòch vuï troïn goùi coù chi phí xaây döïng 1,5 tyû ñoàng, caàn 15 nhaân vieân vaø doanh thu laø 5 tyû ñoàng/ naêm. Coâng ty hieän coù saün 24 tyû ñoàng ñeå môû theâm nhaø haøng. Caùc hôïp ñoàng lao ñoäng chæ cho pheùp coâng ty thueâ theâm nhieàu nhaát 210 nhaân vieân, giôùi haïn ñaêng kyù kinh doanh cho pheùp coâng ty môû theâm nhieàu nhaát laø 20 nhaø haøng, a) Laäp moâ hình baøi toaùn ñeå coâng ty coù doanh thu lôùn nhaát. b) Tìm phöông aùn toái öu cuûa baøi toaùn. c) Neáu doanh thu haøng naêm cuûa moãi nhaø haøng dòch vuï tuyø choïn laø 2 tyû ñoàng thì lôøi giaûi toái öu seõ thay ñoåi nhö theá naøo? Ñ.S : b) X = ( 12, 8 ) fmax = 88. c) X = (6; 12) fmax = 72. 32) Moät doanh nghieäp coù theå saûn xuaát ra moät loaïi saûn phaåm theo 2 quy trình coâng ngheä khaùc nhau: CN1, CN2. Coù 3 loaïi nguyeân lieäu ñeå saûn xuaát laø N1, N2, N3. Bieát raèng soá löôïng nguyeân lieäu tieâu thuï cuõng nhö soá saûn phaåm laøm ra trong moät giôø theo caùc coâng ngheä cho ôû baûng sau: Nguyeân lieäu Soá löôïng nguyeân lieäu hieän coù (ñv) Ñònh möùc tieâu hao trong 1 giôø (ñv) CN1 CN2 N1 200 4 2 N2 280 3 5 N3 350 9 5 Saûn löôïng (ñv/giôø) 30 35 Haõy laäp moâ hình baøi toaùn tìm keá hoaïch saûn xuaát sao cho soá löôïng saûn phaåm ñaït ñöôïc laø lôùn nhaát. 33) Laäp moâ hình, khoâng giaûi Moät nhaø haøng-khaùch saïn coù 4 phoøng hoäi nghò A, B, C, D ; ÔÛ moãi phoøng coù moät soá vò trí coù theå laép ñaët camera quan saùt (xem sô ñoà). Camera laép ôû vò trí 1 thì chæ quan saùt ñöôïc phoøng A, camera laép ôû vò trí 2 thì quan saùt ñöôïc phoøng A vaø phoøng B, töông töï cho caùc camera coøn laïi. Phoøng D laø phoøng VIP neân caàn ít nhaát 2 camera ñeå quan saùt, caùc phoøng coøn laïi chæ caàn ít nhaát 1 camera ñeå quan saùt. Moãi camera coù chi phí laép ñaët laø 500USD, toång soá tieàn laép ñaët caùc camera khoâng vöôït quaù 2500USD. Haõy xaùc ñònh vò trí laép ñaët caùc camera sao cho: toång soá camera laép ñaët laø ít nhaát, nhöng vaãn baûo ñaûm ñieàu kieän veà an ninh vaø ñieàu kieän veà toång soá tieàn ñaàu tö. taitrongnguyen107@gmail.com Trang 8/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
TÀI TRỌNG NGUYỄN TỐI ƯU HÓA NGUYỄN THỊ NGỌC THANH 34) Coâng ty may Saøi Goøn coù 2 phaân xöôûng may kí hieäu laø M1 vaø M2 cuøng saûn xuaát hai loaïi saûn phaåm CAT1 vaø CAT2. Soá ñôn vò saûn phaåm caùc loaïi ñöôïc saûn xuaát ra vaø chi phí moãi giôø hoaït ñoäng cuû M1 vaø M2 ñöôïc cho ôû baûng sau : Xöôûng M1 Xöôûng M2 CAT1 500 500 CAT2 200 400 Chi phí 1.200.000 ñ 2.000.000 ñ Coâng ty nhaän ñöôïc ñôn haøng vôùi soá löôïng laø CAT1 : 10.000 ñôn vò vaø CAT2 : 6.000 ñôn vò a) Laäp moâ hình baøi toaùn phaân phoái thôøi gian hoaït ñoäng cho moãi xöôûng sao cho thoûa maõn yeâu caàu ñaët haøng vôùi chi phí thaáp nhaát. b) Giaûi baøi toaùn tìm phöông aùn toái öu. Ñ.S : X = ( 10, 10) fmin = 32 trieäu ñoàng. II. BAØI TOAÙN VAÄN TAÛI Giaûi vaø tìm phöông aùn toái öu khaùc ( neáu coù ) : 1) Giaûi baøi toaùn vaän taûi vôùi nhöõng thoâng tin : Coù 3 traïm phaùt vôùi löôïng haøng töông öùng : a= (40, 60, 50) Coù 4 traïm thu vôùi nhu caàu töông öùng : b = ( 40, 50, 30, 30) Ma traän chi phí : 2 5 6 3 C= 4 3 3 2 2 5 4 5 2) a = ( 30 ,40 ,53 ) ; b = ( 40 ,30 ,25 ,28 ) Ma traän chi phí : 23 27 16 18 C= 12 17 20 40 22 18 13 30 ÑS : , fmin ( x) = 1855 3) a = ( 60 ,55 ,50 ) ; b = ( 65 ,45 ,50 ,30 ) Ma traän chi phí : 10 9 12 7 C= 9 11 10 15 8 7 14 12 a) Tìm PAVCTU b) Tìm PAVCTU sao cho traïm B3 nhaän ñuû haøng . ÑS :a) , fmin ( x) = 1385 b) , fmin (x ) = 1410 4) a = ( 100 ,125 ,155 ) ; b = ( 150 ,90 ,75 ) Ma traän chi phí : 3 7 4 C= 4 8 10 7 19 9 a) Tìm PAVCTU. b) Tìm PAVCTU vaø sao cho traïm A3 phaùt heát haøng . ÑS :a) f( x) = 1865 b) f (x ) = 2065 5) a = ( 60 ,30 ,80 ) ; b = ( 70 ,50 ,30 ) Ma traän chi phí : 9 5 9 C= 5 8 3 taitrongnguyen107@gmail.com 7 4 6 Trang 9/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH
TÀI TRỌNG NGUYỄN TỐI ƯU HÓA NGUYỄN THỊ NGỌC THANH Tìm PAVCTU vaø sao cho traïm A1 phaùt heát haøng. ( ÑS : , fmin = 850) 6) Ngöôøi ta caàn gieo troàng 3 loaïi luaù treân 4 caùnh ñoàng vôùi dieän tích töông öùng laø :100,150 ,100 vaø 100 ha.Theo keá hoaïch saûn xuaát saûn löôïng moãi loaïi luaù phaûi thu hoaïch töông öùng laø : 300, 600, 250 ( taán ).Naêng suaát trung bình cuûa töøng loaïi luaù cho moãi loaïi ñaát baát kyø laø 2 taán/ha ñoái vôùi luaù 1 ; 3 taán/ha ñoái vôùi luaù 2 ; 2,5 taán/ha ñoái vôùi luaù 3. Tìm phöông aùn gieo troàng sao cho chi phí saûn xuaát thaáp nhaát . Bieát raèng chi phí cho 1 taán luaù (töø luùc gieo troàng ñeán khi thu hoaïch) laø(ÑV: 100 ngaøn ñoàng/taán.): 5 6 4 C= 3,5 6,2 3,6 4,5 6,4 3,8 5,2 5,7 4,2 ÑS : , fmin = 551.000.000 ( ngaøn ñ). 7) Ngöôøi ta phaûi gieo troàng 3 loaïi luaù A, B, C vôùi naêng suaát ,chí phí cho trong baûng nhö sau : Naêng suaát Giaù baùn Chi phí Dieän tích troàng Luaù (taán/ha) (trieäu ñ/taán) (trieäu ñ/ ha) cho caùc luaù (ha) I II III I II III A 5 3 4,5 1,2 1,5 1,1 1,4 50 B 4 3,6 3,8 1,5 1,5 1,4 1,7 70 C 3 3,4 3,2 2,0 2 1,8 1,2 40 Dieän tích(ha) 50 50 60 Haõy laäp keá hoaïch gieo troàng sao cho lôïi nhuaän cöïc ñaïi. ÑS : , fmax = 713 ( trieäu ñoàng ). 8) Moät coâng ty vaän taûi kyù hôïp ñoàng vaän chuyeån moät loaïi haøng töø 3 ñieåm phaùt ñeán 4 ñieåm nhaän haøng nhö sau : Ñòa ñieåm phaùt haøng Ñòa ñieåm nhaän haøng Soá löôïng ( taán) A1 B2 40 B4 60 B1 50 A2 B3 20 A3 B2 30 B3 20 Haõy laäp keá hoaïch vaän chuyeån toái öu sao cho toång soá taán * km xe khoâng laø ít nhaát, bieát raèng ma traän khoaûng caùch giöõa caùc ñòa ñieåm cho nhö sau ( km): 2 3 4 5 C= 6 3 5 1 3 6 4 2 Ñòa chæ vaøo phaàn meàn giaûi baøi TUH: Toiuuhoa.googlepages.com hoaëc : toiuuhoa.ungdung.goolepages -----------HẾT------- taitrongnguyen107@gmail.com Trang 10/10 – BÀI TẬP QUY HOẠCH TUYẾN TÍNH