1
BÀI TẬP TỐI ƯU HÓA VÀ QHTT
Bài tập chương 1
1.1 Một công ty sản xuất bánh trung thu dự kiến năm nay đưa ra thị trường 3 loại bánh : bánh loại 200g
(B200), bánh loại 300g (B300) và bánh loại 400g (B400). Nguyên liệu dùng để sản xuất gồm : bột, trứng,
sữa và hạt dưa đã được chuẩn bị sẵn trong kho, với khối lượng tương ứng là : 3 tấn, 2 tấn, 1 tấn và 0.5 tấn.
Mức tiêu hao mỗi loại nguyên liệu (g) để sản xuất một cái bánh và giá bán mỗi bánh thành phần (ngàn
đồ
ng/bánh) cho ở bảng sau :

Bánh
Nguyên liệu
B200 B300 B400
Bột 100 150 250
Trứng 30 40 50
Sữa 30 35 40
Hạt dưa 25 30 40
Giá bán 1 cái bánh 50 70 100

Theo bạn Công ty cần sản xuất mỗi loại bánh là bao nhiêu cái sao cho với lượng nguyên sẵn có mà doanh thu
của công ty đạt được cao nhất. Biết rằng sản phẩm của công ty có thể tiêu thụ hết.
1.2 Một chủ trang trại biết rằng nhu cầu dinh dưỡng trong một ngày của loài gia súc đang nuôi gồm: Đạm,
Gluxit, Protit, Khoáng tương ứng là 200, 50, 40 và 5 (gam). Tỷ lệ % theo khối lượng các chất trên có trong
các loại thức ăn E
1
,E
2
, E
3
như sau:

xx
xx
xx
xx
=− + →
+≥−
−+≤
−≤
−+≤

12
12
12
12
1
) 2 3 min
2 2
2
2 3 12
1
bZ x x
xx
xx
xx
x
=
+→
−
≥−
−

12
)4030 max
3 16
2 17
2 3 23
, 0
dZ x x
xx
xx
xx
xx
=+→
+≤
+≤
+≤
≥

12
12
12
12
12
12
) 2 max(min)
1
2 4
2 6
4 20
, 0
eZ x x

xx
=+→
≤
≤
≤
≥
≥

12
12
12
1
12
12
) 2 3 max
1
2 4
5
2 3 12
0, 0
gZ x x
xx
xx
x
xx
xx
=
+→
+≥
−+≤

12
12
12
12
12
) 2 min
3 3
2 2
2 4
5
kZ x x
xx
xx
xx
xx
=+ →
−+≤
+≥−
−≤
+≤

12
12
12
12
12
) 8 2 min
3 3
2 6
2 4

+− ≤
+++=
−− ≤
≥=

123
12 3
123
12 3
) 3 2 min
2 6
2 5
3 2 14
0, 1,3
j
bZ x x x
xx x
xxx
xx x
xj
=
−+→
−+ + ≤
+−≤
−+ ≤
≥=

12 3
123
12 3

0, 1,3
j
dZ x x x
xx x
xxx
xx x
xj
=
++→
++≤
++≤
++ =
≥=3
123
123
123
123
12 3
)53 3 max
2 2 3 5
2 4 4
2 5 3
, 0, 0
eZ x x x
xxx
xxx
xxx

123
12 3
13
)3max
2 3 6
2 3 6
2 4
0, 0
gZ x x x
xxx
xxx
xx x
xx
=+ + →
−+=
++≤
−−≤
≥≤

124
12 3 4
234
234
)2 min
2 4 2
7 5 5
2 10
0, 1,4
j
hZ x x x

xxx
xxx
=++→
+≤
+≥
++=
≥

123
123
12 3
12 3
12
) min
4 + 2 1
5 2 +3x 1
4 3 2 1
0, 0
bZ x x x
xxx
xx
xx x
xx
=
++→
+
=
+
≤
+

Hãy giải bài toán trên.
b)
Lập bài toán đối ngẫu của bài toán trên và giải bài toán đối ngẫu đó.
2.3. Giải các bài toán QHTT sau:
123
123
123
123
) 12 16 16 min
2 + 2 6
2 3 8
3 2 2 9
aZ x x x
xxx
xxx
xxx
=++→
+≥
++≥
++≥

123
123
123
123
123
) 12 27 6 min
2 3 2 12
3 6
6 9 2 24

xxx
xx x
xj
=++→
++≥
++≥
++≥
++ ≥
≥=

12 3
123
123
12 3
123
)2 3max
2 2 4
5
2 3 6
3 4 2 9
dZ x x x
xxx
xxx
xx x
xxx
=− + − →
−+≥
++≥
−− ≥
++≥

0
(9, 7 / 2, 0, 5)x = là một phương án tối ưu của bài toán.
2.5 Cho bài toán QHTT sau:
1234
12 3 4
234
34
2max
2 2
7 3 2
3 2 5
0, 1,4
j
Zxxxx
xx x x
xxx
xx
xj
=− − + + →
++ −=
−− + ≤
−+ ≤
≥=

a)
Giải bài toán trên bằng phương pháp đơn hình.
b)
Lập bài toán đối ngẫu của bài toán trên và tìm phương án tối ưu (nếu có) của bài toán đối ngẫu
này.
2.6 Cho bài toán QHTT sau:

Tìm tập phương án tối ưu cho bài toán đã cho.
2.7 Cho bài toán QHTT sau:
123
123
123
12 3
3 min
2 4
(2)2 5
2 3 8
0, 1,3;( )
j
Zxmxx
xxx
mxxx
xx x
x
jmR
=+ + →
+−=
−++≤
−+ =
≥= ∈5
a) Giải bài toán trên với 1m
=
.
b)

150 5 4 6
100 8 5 9
145 11 6 12
100 9 7 13
b)
100 50 30 70
80 3 5 6 5
70 4 5 7 8
50 3 4 4 3