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

tài liệu tham khảo:bài tập môn quy hoạch tuyến tính
Nội dung trích xuất từ tài liệu:
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ÍNHCâ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 oCâu 4. M t xí nghi p dt 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 ngsau â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 tcá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ãi3.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 lch 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 ơnv 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 dinhdư 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ư ngD3. 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 vch 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 hailo 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ơnngoà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à k ...