Bài giảng Quy hoạch tuyến tính (38tr)

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:38

Thêm vào BST

Báo xấu

452
lượt xem 40
download

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

Bài toán quy hoạch tuyến tính là bài toán tối ưu hoá hàm mục tiêu với các ràng buộc là những biểu thức tuyến tính theo các biến số và các tham số. Mời các bạn cùng tham khảo bài giảng sau đây để tìm hiểu thêm về các mô hình toán trong 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 giảng Quy hoạch tuyến tính (38tr)

QUY HOAÏCH TUYEÁN TÍNH Baøi toaùn quy hoaïch tuyeán tính laø baøi toaùn toái öu hoaù haøm muïc tieâu vôùi caùc raøng buoäc laø nhöõng bieåu thöùc tuyeán tính theo caùc bieán soá vaø caùc tham soá. 1 1-BAØI TOAÙN VEÀ LAÄP KEÁ HOAÏCH SAÛN XUAÁT Moät nhaø maùy sx giaáy coù hai loaïi nguyeân lieäu laø goå vaø acid vôùi soá löôïng töông öùng laø 5580 m3 vaø 450 taán. Ñeå sx ra ba loaïi giaáy A, B, C thì caàn tieâu hao nguyeân lieäu theo baûng ñònh möùc sau : Nguyeân lieäu Saûn phaåm A B C Goã (m3) 1.5 1.8 1.6 Acid (taán) 0.1 0.15 0.12 Bieát raèng lôïi nhuaän töông öùng cho töøng loaïi giaáy A, B, C laø 4 ; 5 ; 4.3 trieäu ñoàng. Haõy laäp keá hoaïch sx sau cho lôïi nhuaän ñaït ñöôïc toái ña. 2 1
MOÂ HÌNH BAØI TOAÙN Goïi x1, x2, x3 laø soá giaáy A, B, C caàn sx. Ta coù : xj ≥ 0. Theo ñònh möùc thì löôïng nguyeân lieâu tieâu hao laø : 1.5 * x1 + 1.8 * x2 + 1.6 * x3 ≤ 5,580 (m3) 0.1 * x1 + 0.15 * x2 + 0.12 * x3 ≤ 450 (taán) Lôïi nhuaän thu ñöôïc theo keá hoaïch laø : Z = 4 * x1 + 5 * x2 + 4.3 * x3 phaûi ñaït cöïc ñaïi. Ta ñöôïc moâ hình sau : Tìm x1, x2, x3 sao cho : Z = 4 * x1 + 5 * x2 + 4.3 * x3 ⇒ Max Caùc raøng buoäc : 1.5 * x1 + 1.8 * x2 + 1.6 * x3 ≤ 5,580 (m3) 0.1 * x1 + 0.15 * x2 + 0.12 * x3 ≤ 450 (taán) xj ≥ 0. (j = 1, 2, 3) 3 MOÂ HÌNH TOÅNG QUAÙT BAØI TOAÙN CÖÏC ÑAÏI Giaû söû coù m loaïi nguyeân lieäu vôùi löôïng toàn tröû thöù i (i=1,2,3,…m) laø bi . Caàn saûn xuaát n saûn phaåm vôùi löôïng nguyeân lieäu thöù i duøng ñeå sx saûn phaåm thöù j (j = 1,2,3 … n) laø aij . Lôïi nhuaän cuûa moät ñôn vò saûn phaåm loaïi j laø cj . Xaùc ñònh xj sao cho lôïi nhuaän ñaït cöïc ñaïi. Ta coù moâ hình baøi toaùn cöïc ñaïi toång quaùt sau : n Maximize(Z = ∑ cj * xj) j =1 n ∑ aij * xj ≤ bi j =1 (i = 1,2,3,..., m) xj ≥ 0 ∀j = 1,2,3,..., n 4 2
2-BAØI TOAÙN VEÀ KHAÅU PHAÀN : Ñeå coù theå taùi taïo laïi söùc lao ñoäng, ngöôøi ta caàn ít nhaát 70 g protit, 30 g lipit vaø 420 g gluxit. Haøm löôïng caùc chaát treân coù trong 1 g thöùc aên A vaø B nhö sau : Chaát dinh döôõng Thöùc aên A B Protit (g) 0.1 0.2 Lipit (g) 0.1 0.1 Gluxit (g) 0.7 0.6 Bieát giaù cuûa moãi g thöùc aên A vaø B laø 4 ñ vaø 6 ñ. Haõy xaùc ñònh caùch mua thöùc aên toái öu. 5 MOÂ HÌNH BAØI TOAÙN Goïi x1, x2 laø soá thöùc aên A, B caàn mua. Ta coù : xj ≥ 0. (j =1,2) Haøm löôïng caùc döôõng chaát toái thieåu theo yeâu caàu laø : Protit : 0.1 * x1 + 0.2 * x2 ≥ 70 (g) lipit : 0.1 * x1 + 0.1 * x2 ≥ 30 (g) Gluxit : 0.7 * x1 + 0.6 * x2 ≥ 420 (g) Toång chi phí caàn phaûi mua laø : Z = 4 * x1 + 6 * x2 phaûi ñaït cöïc tieåu . Ta ñöôïc moâ hình sau : Tìm x1, x2 sao cho : Z = 4 * x1 + 6 * x2 ⇒ Min Caùc raøng buoäc : 0.1 * x1 + 0.2 * x2 ≥ 70 (g) 0.1 * x1 + 0.1 * x2 ≥ 30 (g) 0.7 * x1 + 0.6 * x2 ≥ 420 (g) xj ≥ 0. (j = 1, 2) 6 3
MOÂ HÌNH TOÅNG QUAÙT BAØI TOAÙN CÖÏC TIEÅU Giaû söû cô theå caàn boå sung m loaïi döôõng chaát vôùi nhu caàu toái thieåu laø bi (i=1,2,3,…m) . Caàn mua n loaïi thöùc aên trong ñoù löôïng döôõng chaát coù trong moät ñôn vò thöùc aên thöù j laø aij (j = 1,2,3 … n). Chi phí cuûa moät ñôn vò thöùc aên loaïi j laø cj. Xaùc ñònh xj sao cho toång chi phí ñaït cöïc tieåu. Ta coù moâ hình baøi toaùn cöïc tieåu toång quaùt sau : n Minimize(Z = ∑ cj * xj) j=1 n ∑ aij * xj ≥ bi j=1 (i = 1,2,3,..., m) xj ≥ 0 ∀ j = 1,2,3,..., n 7 Baøi taäp 1 : Nhaân dòp teát Trung Thu, xí nghieäp baùnh keïo Vinabico muoán saûn xuaát ba loaïi baùnh ñaäu xanh, thaäp caåm vaø baùnh deõo. Giaû söû soá ñöôøng vaø ñaäu trong kho cuûa xí nghieäp hieän coù laø 500 kg vaø 300 kg (caùc nguyeân lieäu khaùc khoâng haïn cheá). Möùc tieâu hao ñöôøng vaø ñaäu cuõng nhö soá tieàn laõi khi baùn moät chieác baùnh cho töøng loaïi ñöôïc cho ôû baûng sau : Chæ tieâu Baùnh ñaäu xanh Baùnh thaäp caåm Baùnh deõo 1- Nguyeân lieäu söû duïng : - Ñöôøng (g) 60 40 70 - Ñaäu (g) 80 0 40 2- Lôïi nhuaän ñôn vò (1000 ñ) : 2 1,7 1,8 Yeâu caàu : Xaùc laäp moâ hình toaùn nhaèm hoå trôï vieäc xaùc ñònh lôïi nhuaän toái ña. 8 4
Baøi 2 : Moät xí nghieäp deät hieän coù ba loaïi sôïi : Cotton, Kate vaø Polyeste vôùi khoái löôïng töông öùng laø 3 ; 2,5 vaø 4,2 taán. Caùc tö lieäu saûn xuaát khaùc vaø lao ñoäng coù soá löôïng lôùn. Möùc tieâu hao ba loaïi nguyeân lieäu treân ñeå saûn xuaát 1m vaûi loaïi A, B vaø C cho ôû baûng sau : Ñôn vò tính : gam A B C Cotton 200 200 100 Kate 100 200 100 Polyeste 100 100 100 Bieát lôïi nhuaän thu ñöôïc khi baùn 1m vaûi loaïi A, B, C laàn löôït laø 3.500, 4.800, 2.500 ñoàng. Haõy xaây döïng moâ hình toái ña hoùa lôïi nhuaän cho xí nghieäp. 9 Baøi 3 : Moät noâng tröôøng phaûi quyeát ñònh phöông aùn phaân boå vieäc söû duïng 3000 ha ñaát ñeå gieo troàng ba loaïi noâng saûn A, B vaø C vôùi caùc thoâng soá kyû thuaät nhö sau : Loaïi Chi phí saûn xuaát cho 1 ha Öôùc giaù trò saûn löôïng noâng saûn (1000 ñ) thu ñöôïc treân 1 ha Voán Lao ñoäng (1000 ñ) A 300 500 2000 B 350 400 1500 C 400 450 2500 Noâng tröôøng coù theå chuaån bò ñöôïc soá tieàn laøm voán cho saûn xuaát laø 1,2 tyû vaø thueâ lao ñoäng laø 1,6 tyû. Ngoaøi ra ñeå ñaûm baûo nhu caàu hôïp ñoàng veà saûn löôïng thì phaûi gieo troàng ít nhaát 600 ha noâng saûn A. Haõy xaây döïng moâ hình toaùn hoå trôï vieäc phaân boå söû duïng ñaát nhaèm ñaït muïc tieâu toái ña hoùa giaù trò saûn löôïng saûn phaåm. 10 5
Baøi 4 : Ñeå nuoâi moät loaïi gia suùc, trong moät ngaøy vaø ñeâm caàn coù khoái löôïng toái thieåu caùc chaát ñaïm, ñöôøng vaø khoaùng töông öùng laø 80g, 120g vaø 6g. Tyû leä % caùc chaát treân coù trong caùc loaïi thöùc aên A, B, C nhö sau : Thöùc aên Döôõng chaát Ñaïm Ñöôøng Khoaùng A 10 30 2 B 20 40 1 C 25 20 3 Bieát raèng giaù 1kg thöùc aên loaïi A, B, C töông öùng laø 2.000 , 3.000 , 2.500 ñoàng. Haõy laäp moâ hình xaùc ñònh phöông aùn mua thöùc aên toái öu. 11 PHÖÔNG PHAÙP TÌM NGHIEÄM : PHÖÔNG PHAÙP ÑOÀ THÒ Xeùt moâ hình : Max (Z = 5 * x1 + 3 * x2) 6 * x1 + 2 * x2 ≤ 36 5 * x1 + 5 * x2 ≤ 40 2 * x1 + 4 * x2 ≤ 28 x1, x2 ≥ 0 Treân heä truïc toïa ñoä (x1,x2), döïa vaøo caùc raøng buoäc, veõ caùc ñöôøng thaúng : 6 * x1 + 2 * x2 = 36 5 * x1 + 5 * x2 = 40 2 * x1 + 4 * x2 = 28 12 6
x1 2.x1+4.x2 = 28 5.x1+5.x2 = 40 6.x1+2.x2 = 36 13 Tìm mieàn xaùc ñònh cuûa raøng buoäc 1 : 6.x1 + 2.x2 ≤ 36 x1 2.x1+4.x2 = 28 5.x1+5.x2 = 40 6.x1+2.x2 = 36 14 7
Tìm mieàn xaùc ñònh cuûa raøng buoäc 2 : 5.x1 + 5.x2 ≤ 40 x1 2.x1+4.x2 = 28 5.x1+5.x2 = 40 6.x1+2.x2 = 36 15 Tìm mieàn xaùc ñònh cuûa raøng buoäc 1 vaø 2 : x1 2.x1+4.x2 = 28 6.x1+2.x2 = 36 5.x1+5.x2 = 40 16 8
Tìm mieàn xaùc ñònh cuûa raøng buoäc 3 : 2.x1 + 4.x2 ≤ 28 x1 2.x1+4.x2 = 28 6.x1+2.x2 = 36 5.x1+5.x2 = 40 17 Tìm mieàn xaùc ñònh cuûa raøng buoäc 1, 2 vaø 3 : x1 6.x1+2.x2 = 36 5.x1+5.x2 = 40 2.x1+4.x2 = 28 18 9
Veõ ñöôøng thaúng theå hieän haøm muïc tieâu Z = 5.x1 + 3.x2 vaø tònh tieán ñeán caùc ñieåm cöïc : x1 Z = 5.x1+3.x2 19 Xaùc ñònh nghieäm toái öu cuûa moâ hình : x1 Z = 5.x1+3.x2 20 10
Xaùc ñònh nghieäm toái öu cuûa moâ hình : x1 x1=5 ; x2=3 Z = 5.x1+3.x2 21 2- Baøi toaùn cöïc tieåu : Xeùt moâ hình Min (Z = 2 * x1 + 4 * x2) 2 *x1 + x2 ≥ 14 x1 + x2 ≥ 12 x1 + 3 * x2 ≥ 18 x1 , x2 ≥ 0 Treân heä truïc toïa ñoä (x1,x2), döïa vaøo caùc raøng buoäc, veõ caùc ñöôøng thaúng : 2 * x1 + x2 = 14 x1 + x2 = 12 x1 + 3 * x2 = 18 22 11
x1+3.x2 = 18 x1+ x2 =12 2.x1+ x2 = 14 23 Tìm mieàn xaùc ñònh cuûa raøng buoäc 1 : 2.x1 + x2 ≥ 14 x1+3.x2 = 18 x1+ x2 =12 2.x1+ x2 = 14 24 12
Tìm mieàn xaùc ñònh cuûa raøng buoäc 2 : x1 + x2 ≥ 12 x1+3.x2 = 18 x1+ x2 =12 2.x1+ x2 = 14 25 Tìm mieàn xaùc ñònh cuûa raøng buoäc 1 vaø 2 : x1+3.x2 = 18 x1+ x2 =12 2.x1+ x2 = 14 26 13
Tìm mieàn xaùc ñònh cuûa raøng buoäc 3 : x1 + 3.x2 ≥ 18 x1+3.x2 = 18 x1+ x2 =12 2.x1+ x2 = 14 27 Tìm mieàn xaùc ñònh cuûa raøng buoäc 1, 2 vaø 3 : x1+3.x2 = 18 x1+ x2 =12 2.x1+ x2 = 14 28 14
Veõ ñöôøng thaúng theå hieän haøm muïc tieâu : Z = 2.x1 + 4.x2 vaø tònh tieán ñeán caùc ñieåm cöïc : x1+3.x2 = 18 Z = 2.x1+ 4.x2 x1+ x2 =12 2.x1+ x2 = 14 29 Xaùc ñònh nghieäm toái öu cuûa moâ hình : x1+3.x2 = 18 x1 = 9 ; x2 = 3 x1+ x2 =12 2.x1+ x2 = 14 Z = 2.x1+ 4.x2 30 15
PHÖÔNG PHAÙP TÌM NGHIEÄM : THUAÄT TOAÙN ÑÔN HÌNH 1-Baøi toaùn cöïc ñaïi : Xeùt moâ hình : Max (Z = 5 * x1 + 3 * x2) 6 * x1 + 2 * x2 ≤ 36 5 * x1 + 5 * x2 ≤ 40 2 * x1 + 4 * x2 ≤ 28 x1, x2 ≥ 0 Ñeå thuaän lôïi cho vieäc tìm nghieäm, ta theâm caùc bieán buø si ñeå caùc baát phöông trình thaønh caùc phöông trình : 6 * x1 + 2 * x2 + s1 = 36 5 * x1 + 5 * x2 + s2 = 40 2 * x1 + 4 * x2 + s3 = 28 Trong ñoù : (si coù heä soá cj = 0). Laäp baûng ñôn hình : 31 AÅn CB Heä soá (Cb) 5 3 0 0 0 Haèng soá bi x1 x2 s1 s2 s3 s1 0 6 2 1 0 0 36 s2 0 5 5 0 1 0 40 s3 0 2 4 0 0 1 28 Zj = ∑Cb.aij 0 0 0 0 0 0 Cj – Zj 5 3 0 0 0 Trong baûng ta coù : Caùc aån töông öùng vôùi vector coät ñôn vò laø caùc aån cô baûn (s1, s2, s3). Caùc aån coøn laïi laø aån khoâng cô baûn (x1, x2). Moät nghieäm khaû dó cuûa baøi toaùn laø nghieäm thoaû maûn caùc raøng buoäc maø ôû ñoù caùc aån khoâng cô baûn baèng khoâng. Vôùi baûng ñôn hình ñaàu tieân, ta xaùc ñònh ñöôïc lôøi giaûi cô baûn (phöông aùn ban ñaàu) nhö sau : x1 = x2 = 0 ; s1 = 36 s2 = 40 s3 = 28 vaø giaù trò haøm muïc tieâu baèng khoâng. 32 16
TÌM PHÖÔNG AÙN TOÁI ÖU 1-Kiểm tra tính tối ưu : Xét hàng giá trị tham khảo Cj-Zj Nếu các giá trị của hàng tham khảo ñều ≤ 0 ⇒ Phương án hiện tại tối ưu. Nếu tồn tại một giá trị tham khảo > 0 ⇒ Phương án hiện tại chưa tối ưu. 2-Tìm phương án thay theá : Ñeå ñaït ñeán giaù trò toái öu cuûa haøm muïc tieâu, caàn xem xeùt moät phöông aùn khaùc baèng caùch ñöa moät bieán môùi vaøo trong phöông aùn ban ñaàu vaø ñoàng thôøi loaïi boû moät trong nhöõng bieán trong lôøi giaûi cuû. Moät phöông phaùp thay theá bieán laø döïa vaøo phaàn töû xoay. Caùch xaùc ñònh phaàn töû xoay nhö sau : o Döïa vaøo coät coù giaù trò tham khaûo (Cj - Zj) lôùn nhaát (Coät xoay). o Döïa vaøo haøng coù tyû (bi / aij ) beù nhaát (Haøng xoay). 33 AÅn CB Heä soá (Cb) 5 3 0 0 0 Haèng soá bi x1 x2 s1 s2 s3 s1 0 6 2 1 0 0 36 s2 0 5 5 0 1 0 40 s3 0 2 4 0 0 1 28 Zj = ∑Cb.aij 0 0 0 0 0 0 Cj – Zj 5 3 0 0 0 Vôùi caùch xaùc ñònh treân, a11 chính laø phaàn töû xoay, s1 laø bieán ñöa ra vaø x1 laø bieán ñöa vaøo thay theá cho s1. Chia haøng xoay cho giaù trò xoay. Bieán ñoåi caùc soá haïng cuûa truïc xoay thaønh 0 baèng phöông phaùp khöû : 34 17
AÅn CB Heä soá (Cb) 5 3 0 0 0 Haèng soá bi x1 x2 s1 s2 s3 x1 5 1 1/3 1/6 0 0 6 s2 0 0 10/3 - 5/6 1 0 10 s3 0 0 10/3 -1/3 0 1 16 Zj = ∑Cb.aij 5 5/3 5/6 0 0 Cj – Zj 0 4/3 - 5/6 0 0 30 Vôùi baûng bieán ñoåi treân, ta xaùc ñònh ñöôïc moät phöông aùn môùi toát hôn (giaù trò haøm muïc tieâu baèng 30) töông öùng caùc nghieäm x2 = s1 = 0, x1 =6 s2 = 10 s3 = 16 . Haøng tham khaûo (Cj – Zj) vaãn coøn chöùa giaù trò tham khaûo döông. Do ñoù phöông aùn vöøa tìm ñöôïc chöa toái öu. Ta tieáp tuïc xaùc ñònh phaàn töû xoay ñeå thay theá bieán. Döïa vaøo caùch xaùc ñònh phaàn töû xoay ôû treân, ta tìm ñöôïc giaù trò a22 laø phaàn töû xoay. Vaäy bieán loaïi khoûi phöông aùn laø s2 vaø thay theá baèng bieán x2. Chia haøng xoay cho giaù trò xoay. Bieán ñoåi caùc soá haïng cuûa truïc xoay thaønh 0 baèng phöông phaùp khöû ta ñöôïc baûng : 35 AÅn CB Heä soá (Cb) 5 3 0 0 0 Haèng soá bi x1 x2 s1 s2 s3 x1 5 1 0 1/4 -1/10 0 5 x2 3 0 1 -1/4 3/10 0 3 s3 0 0 0 1/2 -1 1 6 Zj = ∑Cb.aij 5 3 1/2 2/5 0 34 Cj – Zj 0 0 - 1/2 - 2/5 0 Ta nhaän thaáy caùc giaù trò ôû haøng tham khaûo ñeàu nhoû hôn hay baèng khoâng. Do ñoù, ñaây laø phöông aùn toái öu. Giaù trò haøm muïc tieâu toái öu baèng 34 ñôn vò, vaø heä nghieäm cuûa baøi toaùn laø : x1 = 5 vaø x2 = 3. 36 18
Baøi 5 : Giaûi caùc baøi toaùn sau theo phöông phaùp ñôn hình : 1- Max (Z = 6.x1 + 5.x2 + 20.x3) 2.x1 + 2.x2 + 7.x3 ≤ 13 2.x1 + x2 + 6.x3 ≤ 9 x1,x2,x3 ≥ 0 (ÑS : x*(0,3,1) ; Z = 35) 2- Max (Z = x1 + 2.x2 + x3 + x4) 2.x1 + x2 + x3 + x4 ≤ 11 2.x2 + x3 + x4 ≤ 11 3.x1 + x2 + x3 ≤8 x1,x2,x3,x4 ≥ 0 (ÑS : X*(1,6 ; 3,2 ; 0 ; 4,6) ; Z = 12,6) 37 2- Baøi toaùn cöïc tieåu : Xeùt moâ hình Min (Z = 2 * x1 + 4 * x2) 2 *x1 + x2 ≥ 14 x1 + x2 ≥ 12 x1 + 3 * x2 ≥ 18 x1 , x2 ≥ 0 Ñeå laäp baûng ñôn hình, ta theâm caùc bieán buø si vaø caùc bieán nhaân taïo Ai ñeå caùc baát phöông trình thaønh caùc phöông trình . 2 * x1 + x2 - s1 + A1 = 14 x1 + x2 - s2 + A2 = 12 x1 + 3 * x2 - s3 + A3 = 18 Trong ñoù : si coù Cj = 0 vaø Ai coù Cj = M (M : laø soá ñuû lôùn ñeå loaïi boû Ai ra khoûi heä). Sau ñoù laäp baûng ñôn hình : 38 19
AÅn CB Heä soá 2 4 0 0 0 M M M Haèng x1 x2 s1 s2 s3 A1 A2 A3 soá bi A1 M 2 1 -1 0 0 1 0 0 14 A2 M 1 1 0 -1 0 0 1 0 12 A3 M 1 3 0 0 -1 0 0 1 18 Zj =∑ ∑Cb.aij 4M 5M -M -M -M M M M 44M Zj - Cj 4M-2 5M-4 - M -M -M 0 0 0 Vôùi baûng ñôn hình ñaàu tieân, ta xaùc ñònh ñöôïc lôøi giaûi cô baûn : x1 = x2 = s1 = s2 = s3 = 0 ; A1 = 14 A2 = 12 A3 =18 vaø giaù trò haøm muïc tieâu baèng 44M. Haøng tham khaûo coøn chöùa moät soá giaù trò tham khaûo döông neân phöông aùn naøy chöa toái öu. Ñeå tìm phöông aùn toái öu, ta söû duïng caùc böôùc gioáng nhö ôû baøi toaùn cöïc ñaïi. Xaùc ñònh phaàn töû xoay : * Döïa vaøo coät coù giaù trò tham khaûo (Zj-Cj) lôùn nhaát. * Döïa vaøo haøng coù tyû (bi / aij ) beù nhaát. 39 AÅn CB Heä soá 2 4 0 0 0 M M M Haèng soá bi x1 x2 s1 s2 s3 A1 A2 A3 A1 M 2 1 -1 0 0 1 0 0 14 A2 M 1 1 0 -1 0 0 1 0 12 A3 M 1 3 0 0 -1 0 0 1 18 Zj =∑ ∑Cb.aij 4M 5M -M -M -M M M M 44M Zj - Cj 4M-2 5M-4 - M -M -M 0 0 0 Ta thaáy a32 laø phaàn töû xoay. x2 laø bieán ñöa vaøo vaø A3 laø bieán ñöa ra. Chia haøng xoay cho giaù trò xoay. Bieán ñoåi caùc soá haïng cuûa truïc xoay thaønh 0 baèng phöông phaùp khöû 40 20