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

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.
Nội dung trích xuất từ tài liệu:
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ôùisoá löôïng töông öùng laø 5580 m3 vaø 450 taán. Ñeå sx ra ba loaïi giaáyA, 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.12Bieá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 ñöôïctoá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 3MOÂ 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 ...