1
Đề thi
Tối ưu hóa
–
K31 CQ
* ThS. Phạm Trí Cao
ĐỀ THI TỐI ƯU HÓA - K31 CHÍNH QUY
ĐỀ 1
Câu 1 (2,5đ): Một xí nghiệp cơ khí cần cắt những thanh sắt dài 2m thành 400 đoạn dài 0,8m;
500 đoạn dài 0,6m; 600 đoạn dài 0,5m. Hãy lập mô hình bài toán tìm phương án cắt sao cho số
sắt thừa ít nhất (Chỉ lập mô hình, không giải).
Câu 2 (4đ): Cho bài toán QHTT (A) sau:
f(x)= x
1
+3x
2
-x
3
+3x
4
 min
x
1
+ x
2
-2x
3
+x
4
>=4
-x

>=0,
j=1,8 mà chỉ ghi x
j
>=0, j=1,4 ; thậm chí không thèm ghi điều kiện của x
j
.
Không có điều kiện M>0 rất lớn. Ghi M ở ràng buộc chung.
Kết quả thay vì ghi cột patư x thì lại ghi cột c.
Không ghi cột ứng với biến phụ trong bảng đơn hình, “tưởng” có thể bỏ được giống như biến
giả!
Không ghi giá trò tối ưu f, chỉ ghi patư x. Không xác đònh patư của bài toán gốc mà chỉ có patư
của bài toán chuẩn.
Không ghi các cặp ràng buộc đối ngẫu ra. Không ghi giá trò tối ưu của bài toán đối ngẫu.
Câu 3: Không ghi patư x của bài toán gốc, chỉ ghi patư của bài toán CBTP. Không ghi giá trò tối
ưu f.
Tại sao tôi làm “quá trời” mà tôi lại rớt ! híc híc híc
2
Đề thi
Tối ưu hóa
–
K31 CQ
* ThS. Phạm Trí Cao
ĐỀ 2
Câu 1 (2đ): Trong các mệnh đề sau, mệnh đề nào đúng, mệnh đề nào sai? Nếu sai hãy giải
thích vì sao?
1) (1đ) Bài toán vận tải không cân bằng thu phát cũng có thể không có patư.
2) (1đ) Phương án X=(x
ij
)
m*n

4
=20
2x
1
+ x
2
+2x
3
+ x
4
>=24
x
j
>=0, j=1,4
1) (3đ) Giải bài toán trên
2) (1đ) Viết bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu
Câu 3 (4đ): (3,5đ) Giải BTVT sau. (0,5đ) Tìm patư khác, nếu có.
T
F
60 10 50
30 1 2 3
40 2 7 9
40 6 3 7
25 7 4 8
ĐỀ 3
Câu 1 (2đ): Người ta trồng 3 giống lúa R1, R2, R3 trên 3 mảnh ruộng I, II, III. Do tính chất của
từng mảnh ruộng và của đặc điểm từng giống lúa nên năng suất của các giống lúa trên các
mảnh ruộng là khác nhau và được cho ở bảng:
Ruộng
Giống lúa

4
=23
-x
1
+x
2
+x
3
-x
4
<=6
-2x
2
+x
3
+2x
4
>=8
x
j
>=0, j=1,4
a) (3đ) Giải bài toán trên
b) (1,5đ) Viết bài toán đối ngẫu (D) và tìm patư của (D)
Câu 3 (3,5đ): Giải bài toán vận tải với số liệu sau. Tìm patư khác, nếu có.
T
F
60 10 50
30 1 2 3
40 2 7 9
40 6 3 7

+2x
2
+x
3
+x
4
<=30
x
1
+2x
2
+2x
3
+3x
4
=20
2x
1
+x
2
+2x
3
+x
4
>=24
x
j
>=0, j=1,4
a) (3đ) Giải bài toán trên.
b) (1đ) Viết bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu.

1
+3x
2
-x
3
+3x
4
 min
x
1
+x
2
-2x
3
+x
4
>=4
-x
1
+x
3
<=5
2x
2
-3x
3
+x
4
=15
x

C 5 3
Để chế tạo một đơn vò hợp chất, người ta cần sử dụng ít nhất 2,5 đơn vò chất A, 3 đơn vò chất B
và 4 đơn vò chất C. Chi phí khai thác mỗi một đơn vò quặng mỗi loại lần lượt là 3, 6, 5 ngàn đ.
Xác đònh lượng quặng mỗi loại cần khai thác để có thể thực hiện chế tạo được loại hợp chất cần
thiết và chi phí khai thác là ít nhất.
Câu 2 (4đ): Cho bài toán QHTT (P) sau:
f(x)= 2x
1
+x
2
+2x
3
 min
x
1
+x
2
-2x
3
>=18
2x
2
+x
3
>=12
x
j
>=0, j=1,3
a) (2,5đ) Giải bài toán (P).
b) (1,5đ) Viết bài toán đối ngẫu của (P) và tìm patư của bài toán đối ngẫu.

ĐỀ 7
Câu 1 (2đ): Một nhà máy chuyên sản xuất 3 loại thuyền: thuyền có mái chèo, ca nô, xuồng
caiac. Lợi nhuận thu được trên một đơn vò sản phẩm của từng loại thuyền tương ứng là 300$,
180$, 150$. Để sản xuất 1 chiếc thuyền mỗi loại người ta cần phải sử dụng nguyên liệu nhôm
và giờ công lao động ở các phân xưởng sản xuất (1 sản phẩm do 2 phân xưởng cùng sản xuất),
được cho ở bảng sau:
1 thuyền có mái chèo 1 ca nô 1 thuyền caiac
Nhôm (kg) 17 8 6
Phân xưởng 1 (giờ) 3 5 4
Phân xưởng 2 (giờ) 2 1 3
Nhà máy có khoảng 500kg nhôm, giờ công lao động hữu dụng ở phân xưởng 1 và 2 tương ứng
là 150 giờ và 100 giờ. Hãy lập mô hình bài toán tìm kế hoạch sản xuất của nhà máy để đạt mức
lợi nhuận tối đa.
Câu 2 (4,5đ): Cho bài toán QHTT (A) sau:
f(x)= x
1
+3x
2
-3x
3
+2x
4
 min
x
1
+x
2
-2x
3
+x

Tối ưu hóa
–
K31 CQ
* ThS. Phạm Trí Cao
ĐỀ 8
Câu 1 (2đ): Một tàu chở hàng có trọng tải 200 tấn và dung tích chứa là 80m
3
. Tàu có thể chở
được 5 loại hàng với khối lượng, thể tích và giá trò như sau:
Loại hàng
1
2
3
4
5
Khối lượng (tấn/đơn vò) 1,1 1,7 2,1 1,6 2,3
Thể tích (m
3
/đơn vò) 0,7 0,6 0,5 0,8 0,9
Giá trò (triệu đ/đơn vò) 7 8 9 10 13
Hãy lập mô hình bài toán tìm số lượng hàng tối ưu mỗi loại cần xếp lên tàu sao cho tổng giá trò
là lớn nhất.
Câu 2 (4,5đ): Cho bài toán QHTT sau:
f(x)= 3x
1
+2x
2
+3x
3
+5x

j
>=0, j=1,4
a) (3đ) Giải bài toán trên và (0,5đ) tìm patư khác, nếu có.
b) (1đ) Viết bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu.
Câu 3 (3,5đ): (3đ) Giải bài toán vận tải với số liệu sau. (0,5đ) Tìm patư khác, nếu có.
T
F
50 75 95
50 5 7 6
100 6 8 9
50 6 9 9