Bài tập môn quy hoạch tuyến tính

Chia sẻ: Hoang Thuy | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

765
lượt xem 265
download

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

tài liệu tham khảo:bài tập môn 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 quy hoạch tuyến tính

BÀI T P MÔN QUY HO CH TUY N TÍNH Câu 1. Cho bài tóan Quy h ach tuy n tính mà ta g i là bài tóan (P) f ( x ) = 3 x1 − 4 x2 − 5 x3 + 6 x4 → min  x1 + x2 + x3 + 13 x4 = 14  2 x1 + x2 + 14 x4 = 11  3 x2 + x3 + 14 x4 = 16  x j ≥ 0, j = 1, 4. 1) Ch ng minh x = (4,3, 7, 0) là phương án c c biên t i ưu c a bài tóan (P). 2) Vi t bài tóan i ng u c a bài tóan (P) và tìm phương án t i ưu c a bài tóan i ng u.  17 101 20  3) Ch ng minh x′ =  0, , ,  là phương án c c biên nhưng không ph i là phương  27 27 27  án t i ưu c a bài tóan (P). Hãy xây d ng m t phương án c c biên m i t t hơn x′ . Câu 2. Cho bài tóan Quy h ach tuy n tính mà ta g i là bài tóan (P) f ( x ) = 7 x1 − 2 x2 − 12 x3 + 5 x4 → min  x1 + x2 + x3 − 4 x4 = 11  2 x2 + x3 + 5 x4 = 15  x j ≥ 0, j = 1, 4. 1) Ch ng minh x = (0, 4, 7, 0) là phương án c c biên t i ưu c a bài tóan (P). 2) Vi t bài tóan i ng u c a bài tóan (P) và tìm phương án t i ưu c a bài tóan i ng u. Câu 3. Cho bài tóan Quy h ach tuy n tính mà ta g i là bài tóan (P) f ( x ) = 4 x1 + 5 x2 + 7 x3 → min 3 x1 + x2 + x3 = 6   x1 + 2 x2 + 3 x3 = 14 x j ≥ 0, j = 1, 3. 1) Li t kê t t c các phương án c c biên c a bài toán (P). 2) Ch ng t bài toán có phương án t i ưu. T ó ch ra phương án c c biên t i ưu. 3) Phát bi u bài toán i ng u c a bài toán (P), và tìm phương án t i ưu c a bài toán i ng u. nh s n xu t ba lo i s n ph m A, B và C. Các s n ph m này ư c ch t o Câu 4. M t xí nghi p d t ba lo i nguyên li u I, II và III . S lư ng các nguyên li u I, II và III mà xí nghi p có l n lư t là 30, 50, 40. S lư ng các nguyên li u c n s n xu t m t ơn v s n ph m A, B, C ư c cho b ng sau ây NL I II III SP A 1 1 3 B 1 2 2 C 2 3 1 1
Xí nghieäp muoán leân moät k ho ch s n xu t thu ư c t ng s lãi nhi u nh t (v i gi thi t các s n ph m làm ra u bán h t), n u bi t r ng lãi 5 tri u ng cho m t ơn v s n ph m lo i A, lãi 3.5 tri u ng cho m t ơn v s n ph m lo i B, lãi 2 tri u ng cho m t ơn v s n ph m lo i C. 1) L p mô hình bài toán Quy ho ch tuy n tính. 2) B ng phương pháp ơn hình, hãy gi i bài toán trên. Câu 5. M t Xí nghi p chăn nuôi c n mua m t l ai th c ăn t ng h p T1, T2, T3 cho gia súc v i t l ch t dinh dư ng như sau: 1 kg T1 ch a 4 ơn v dinh dư ng D1, 2 ơn v dinh dư ng D2, và 1 ơn v dinh dư ng D3; 1 kg T2 ch a 1 ơn v dinh dư ng D1, 7 ơn v dinh dư ng D2, và 3 ơn v dinh dư ng D3; 1 kg T3 ch a 3 ơn v dinh dư ng D1, 1 ơn v dinh dư ng D2, và 4 ơn v dinh dư ng D3. M i b a ăn, gia súc c n t i thi u 20 ơn v D1, 25 ơn v D2 và 30 ơn v D3. H i Xí nghi p ph i mua bao nhiêu kg T1, T2, T3 m i l ai cho m t b a ăn b o m t t v ch t dinh dư ng và t ng s ti n mua là nh nh t ? Bi t r ng 1 kg T1 có giá là 10 ngàn ng, 1 kg T2 có giá là 12 ngàn ng, 1 kg T3 có giá là 14 ngàn ng. Câu 6. Cho bài toán Quy h ach tuy n tính f (x) = x1 + 2x 2 + 3x 3 → min 6x1 + 3x 2 + 2x 3 ≥ 20  2x1 + 6x 2 + 3x 3 ≥ 25 x j ≥ 0; j = 1,3. 1) Phát bi u bài toán i ng u c a bài toán trên . 2) Hãy gi i m t trong hai bài toán r i suy ra phương án t i ưu c a bài toán còn l i. Câu 7. M t công ty s n xu t hai lo i sơn n i th t và sơn ngoài tr i. Nguyên li u s n xu t g m hai lo i A, B v i tr lư ng là 6 t n và 8 t n tương ng. s n xu t m t t n sơn n i th t c n 2 t n s n xu t m t t n sơn ngoài tr i c n 1 t n nguyên li u A và nguyên li u A và 1 t n nguyên li u B. 2 t n nguyên li u B. Qua i u tra th trư ng công ty bi t r ng nhu c u sơn n i th t không hơn sơn ngoài tr i quá 1 t n. Giá bán m t t n sơn n i th t là 2000 USD, giá bán m t t n sơn ngoài tr i là 3000 USD. H i c n s n xu t m i lo i sơn bao nhiêu t n có doanh thu l n nh t ? Câu 8. Cho bài tóan v n t i cân b ng thu phát hàm m c tiêu cư c phí min và phương án (phương án ư c xây d ng b ng phương pháp góc Tây – B c) 30 40 50 60 80 1 5 7 2 30 40 10 45 5 7 4 9 40 5 55 12 2 3 6 55 1) Tính cư c phí v n chuy n c a phương án trên và ch ng t phương án này là phương án c c biên không suy bi n và không t i ưu. 2
2) Xu t phát t phương án trên hãy xây d ng m t phương án m i t t hơn (ch c n m t phương án m i t t hơn). Câu 9. Cho bài tóan v n t i cân b ng thu phát hàm m c tiêu cư c phí max và phương án (phương án ư c xây d ng b ng phương pháp góc Tây – B c) 60 40 50 60 50 10 5 17 2 50 75 5 7 4 5 10 40 25 85 12 12 1 6 25 60 1) Tính cư c phí v n chuy n c a phương án trên và ch ng t phương án này là phương án c c biên không suy bi n và không t i ưu. 2) Xu t phát t phương án trên hãy xây d ng m t phương án m i t t hơn (ch c n m t phương án m i t t hơn). Câu 10. i h i th v n ư c t ch c ng lo t cùng ngày 4 a i m. Các nhu c u v t ch t (t n) ư c phát i t 3 a i m. Các d li u v yêu c u thu phát và c l y (km) ư c cho trong b ng dư i ây. Do c i m c a các phương ti n v t ch t, th i gian và phương ti n v n t i, nên không th chuy n quá xa trên 150 km. Tìm phương án chuyên ch sao cho t ng s chi u dài quãng ư ng là nh nh t. 15 10 17 18 20 160 50 100 70 30 100 200 30 60 10 50 40 30 50 Câu 11. Cho bài tóan v n t i: 80 20 60 50 5 4 2 40 3 6 70 7 9 Trong ó ô(2,1) và ô(3,3) là ô c m, t c là tuy n ư ng t nơi phát hàng th 2 n nơi nh n hàng th 1 và tuy n ư ng t nơi phát hàng th 3 n nơi nh n hàng th 3 không th i qua ư c. 3
1) Xây d ng m t phương án c c biên. 2) Xu t phát t phương án này hãy xây d ng m t phương án m i t t hơn (ch c n m t Câu 12. Gi i bài tóan v n t i cân b ng thu phát: 40 70 90 100 5 6 9 45 4 10 55 4 2 5 Trong ó ô(2,2) là ô c m, t c là tuy n ư ng t nơi phát hàng th 2 n nơi nh n hàng th 2 không th i qua ư c. Câu 13. Cho bài tóan v n t i cân b ng thu phát và hai phương án. Phương án (1) ư c xây d ng b ng phương pháp c c ti u theo b ng cư c phí (t c phương pháp “min cư c”): 40 70 20 80 10 9 2 20 60 30 4 3 1 10 20 20 2 6 2 20 Phương án (2) ư c xây d ng b ng phương pháp Fogel 40 70 20 80 10 9 2 20 60 20 30 4 3 1 10 20 2 6 2 20 1) H i các phương án này có ph i là các phương án c c biên không suy bi n? 2) H i phương án nào là phương án t t hơn? 3) Ki m tra tính t i ưu c a các phương án. Câu 14. M t nhà máy ch bi n th t, s n xu t ba lo i th t: bò, l n, c u, v i t ng lư ng m i ngày là 480 t n bò; 400 t n l n; 230 t n c u. M i lo i u có th bán ư c d ng tươi ho c n u chín. T ng lư ng các lo i th t n u chín bán trong gi làm vi c là 420 t n. Ngoài ra n u thêm ngoài gi 250 t n (v i giá cao hơn). L i nhu n thu ư c trên m t t n ư c cho b ng b ng sau: (v i ơn v là tri u ng) 4
Tươi N u chín N u chín ngoài gi Bò 8 11 14 Ln 4 7 12 Cu 4 9 13 M c ích c a nhà máy là tìm phương án ch bi n i l i nhu n. Hãy tìm phương án làm c c ch bi n ó. thi tham kh o (Th i gian làm bài 60 phút) Câu I: (3 i m) Cho bài tóan Quy h ach tuy n tính mà ta g i là bài tóan (P) f ( x ) = x1 + 4 x2 + 7 x3 + 0 x4 → min 2 x1 + 3 x2 + 4 x3 + 5 x4 = 20   x1 − x2 + x3 + x4 = 2 3 x − x + 5 x + 2 x = 16 1 2 3 4 x j ≥ 0, j = 1, 4. a) Ch ng minh x = (1, 2, 0,3) là phương án c c biên, t i ưu c a bài tóan (P). b) Vi t bài tóan i ng u c a bài tóan (P) và tìm phương án t i ưu c a bài tóan i ng u. Câu II: (4 i m) M t gia ình c n ít nh t 1800 ơn v prôtêin và 1500 ơn v lipit trong th c ăn m i ngày. M t kilôgam th t bò ch a 600 ơn v prôtêin và 600 ơn v lipit, m t kilôgam th t heo ch a 600 ơn v prôtêin và 300 ơn v lipit, m t kilôgam th t gà ch a 600 ơn v prôtêin và 600 ơn v lipit. Giá m t kilôgam th t bò là 80 ngàn ng, giá m t kilôgam th t heo là 75 ngàn ng, giá m t kilôgam th t gà là 90 ngàn ng. H i m t gia ình nên mua bao nhiêu kilôgam th t m i lo i : b o m t t kh u ph n ăn trong m t ngày và t ng s ti n ph i mua là nh nh t? Câu III: (3 i m) Gi i bài tóan v n t i cân b ng thu phát sau: j 40 45 60 65 i 90 1 5 7 2 65 5 7 4 9 55 12 2 3 6 5