Xem mẫu
- ðH Công nghi p Tp.HCM ThS. Nguy n ðình Tùng
M TS BÀI T P T NG H P
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.
Câu 4. M t xí nghi p d ñ 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
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
1
- ðH Công nghi p Tp.HCM ThS. Nguy n ðình Tùng
C 2 3 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 nguyên li u A và 1 t n nguyên li u B. ð 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à 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
2
- ðH Công nghi p Tp.HCM ThS. Nguy n ðình Tùng
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 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 ly (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
3
- ðH Công nghi p Tp.HCM ThS. Nguy n ðình Tùng
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.
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.
4
nguon tai.lieu . vn
