GIÁO TRÌNH QUY HOẠCH TUYẾN TÍNH

Giả sử, một cái túi có thể chứa tối đa b kg (bỏ qua yếu tố thể tích). Có n loại đồ vật T (i 1,n) i = có thể được đưa vào trong túi với khối lượng & giá trị tương ứng là i a và i c . Yêu cầu đặt ra: Cần đặt vào trong túi bao nhiêu đồ vật mỗi loại để cái túi có giá trị lớn nhất.
Nội dung trích xuất từ tài liệu:
GIÁO TRÌNH QUY HOẠCH TUYẾN TÍNH Quy hoaïch tuyeán tính Trang 1 CHÖÔNG I BAØI TOAÙN QUY HOAÏCH TUYEÁN TÍNH BAØI 1. MOÄT SOÁ BAØI TOAÙN DAÃN ÑEÁN BAØI TOAÙN QUY HOAÏCH TUYEÁN TÍNH 1. Baøi toaùn caùi tuùi Giaû söû, moät caùi tuùi coù theå chöùa toái ña b kg (boû qua yeáu toá theå tích). Coù n loaïi ñoà vaät Ti (i = 1, n) coù theå ñöôïc ñöa vaøo trong tuùi vôùi khoái löôïng & giaù trò töông öùng laø ai vaø ci . Yeâu caàu ñaët ra: Caàn ñaët vaøo trong tuùi bao nhieâu ñoà vaät moãi loaïi ñeå caùi tuùi coù giaù trò lôùn nhaát. Goïi xi laø soá ñoà vaät Ti (i = 1, n) caàn ñaët vaøo tuùi; vôùi ñieàu kieän xi ≥ 0 vaø xi nguyeân. Khi ñoù, moâ hình toaùn caàn laäp coù daïng nhö sau: n f ( x) = ∑ ci xi → max i =1 ⎧ n ⎪∑ ai xi ≤ b ⎨ i =1 ⎪ x ≥ 0 (i = 1, n), nguyen ⎩ i Ñaây laø moät baøi toaùn quy hoaïch tuyeán tính. 2. Baøi toaùn laäp keá hoaïch saûn xuaát toái öu Moät doanh nghieäp caàn saûn xuaát n loaïi saûn phaåm P1 ,..., P n töø m loaïi nguyeân lieäu M 1 ,..., M m . Giaù xuaát xöôûng saûn phaåm, tröõ löôïng nguyeân lieäu hieän coù vaø ñònh möùc söû duïng nguyeân lieäu ñeå saûn xuaát caùc loaïi saûn phaåm ñöôïc cho ôû baûng sau: Teân Tröõ löôïng Saûn phaåm nguyeân lieäu nguyeân lieäu P1 P2 … Pn M1 b1 a11 a12 … a1n M2 b2 a21 a22 … a2 n … … … … … … Mm bm am1 am 2 … amn Giaù xuaát xöôûng c1 c2 … cn Ñeå khoâng bò ñoäng trong quaù trình saûn xuaát, doanh nghieäp caàn xaùc ñònh soá löôïng saûn phaåm caàn saûn xuaát moãi loaïi sao cho toång trò giaù xuaát xöôûng laø lôùn nhaát trong phaïm vi tröõ löôïng nguyeân lieäu hieän coù cuûa doanh nghieäp. Haõy laäp moâ hình toaùn ñeå xaùc ñònh soá saûn phaåm ñoù. Goïi xi laø soá saûn phaåm Pi (i = 1, n) caàn phaûi saûn xuaát; vôùi ñieàu kieän xi ≥ 0 . Khi ñoù: n + Trò giaù xuaát xöôûng cuûa doanh nghieäp ñöôïc xaùc ñònh baèng: R = ∑ ci xi ; i =1 + Toång löôïng nguyeân lieäu loaïi M j ( j = 1, m) duøng ñeå saûn xuaát soá saûn phaåm treân laø: n w j = ∑ aij xi ; Trong phaïm vi tröõ löôïng nguyeân lieäu hieän coù cuûa doanh nghieäp, ta caàn i =1 Tröôøng ÑH Laïc Hoàng/ Khoa Quaûn trò- Kinh teá quoác teá Nguyeãn Thanh Laâm- 2009 Quy hoaïch tuyeán tính Trang 2 xaùc ñònh xi (i = 1, n) sao cho w j ≤ b j ( j = 1, m) ; Do ñoù, moâ hình toaùn ñeå xaùc ñònh soá saûn phaåm caàn saûn xuaát cuûa doanh nghieäp ñöôïc vieát nhö sau: n R = ∑ ci xi → max i =1 ⎧ n ⎪∑ aij xi ≤ b j ( j = 1, m) ⎨ i =1 ⎪ x ≥ 0 (i = 1, n) ⎩ i Ñaây laø moät baøi toaùn quy hoaïch tuyeán tính. 3. Baøi toaùn xaùc ñònh khaåu phaàn thöùc aên toái öu Theo lôøi khuyeân cuûa chuyeân gia dinh döôõng, ñeå ñaûm baûo söùc khoeû vaø söï phaùt trieån toát cuûa moät loaïi gia suùc L naøo ñoù, haèng ngaøy, chuû chaên nuoâi caàn cung caáp ñuû caùc loaïi chaát dinh döôõng N1 ,..., N n vôùi khoái löôïng toái thieåu töông öùng b1 ,..., bn . Giaû söû treân thò tröôøng coù m loaïi thöùc aên F1 ,..., Fm vôùi haøm löôïng chaát dinh döôõng trong töøng loaïi vaø giaù mua moãi loaïi ñöôïc cho qua baûng sau: Teân chaát Löôïng Loaïi thöùc aên dinh döôõng toái thieåu F1 F2 … Fm N1 b1 a11 a12 … a1m N2 b2 a21 a22 … a2 m … ...