TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT
THÀNH PHỐ HỒ CHÍ MINH
KHOA KINH TẾ
BM Quản trị kinh doanh
-
ĐỀ THI CUỐI KỲ HỌC KỲ 1
NĂM HỌC 2025-2026
Môn: TỐI ƯU HOÁ
Mã môn học: MAOP230706
Đề số/Mã đề: 01
Đề thi có 02 trang.
Thời gian: 60 phút.
Được phép sử dụng tài liệu
Câu 1 (4 điểm):
Cho bài toán gốc (P):
????(????) = ????1 + 4????2 + ????3 → ????????????
Các ràng buộc:
????1
+ ????3 ≤ 2
{2????1 + ????2 + 6????3 ≥ −1
12????1 + 12????2
= 12
????1 ≥ 0, ????2 ≥ 0, ????3 ≥ 0
a) Xây dựng bài toán đối ngẫu (D) tương ứng của bài toán gốc (P).
b) Giải bài toán (P) tìm kết quả tối ưu bằng thuật toán đơn hình. Suy ra kết quả bài toán (D).
Câu 2 (3 điểm):
Kế hoạch vận tải ngày 27/10/2026 của công ty Hoá Mỹ Phẩm Alpha từ Các kho Tân Phú
(1), Q.12 (2) và Bình Thạnh (3) đến các đại lý tại Q.1 (1), Phú Nhuận (2) và Q.2 (3). Chi phí vận
tải đơn vị được cho trong bảng (ĐVT: đồng). Hiện hàng hoá đang lưu trữ tại các kho (1)(2)(3) lần
lượt là 350, 720, 150 sản phẩm. Đơn hàng từ khách hàng (1)(2)(3) lần lượt là 222, 565, 213 sản
phẩm.
Bảng chi phí vận tải đơn vị
Q.1
Phú Nhuận
Q.2
Tân Phú
50.000
45.000
72.000
Q.12
53.000
51.000
98.000
Bình Thạnh
61.000
35.000
25.000
Kho Tân Phú hiện phải giải phóng hết hàng để chuẩn bị chuyển đổi mục đích sử dụng. Trong
khi đó, tình hình thời tiết ngày 27/10 không cho phép di chuyển từ Kho Q.12 đến Q.2
Hãy xác định kế hoạch phân phối sao cho tổng chi phí là thấp nhất?
Câu 3 (3 điểm):
Xưởng may gia công quần áo xuất khẩu An An nhận một đơn hàng 1.500 áo thun từ thị trường
Trung Đông. Tình trạng sản xuất hiện đang vào mùa cao điểm, nên đơn hàng này được phân cho Tổ sản
xuất 1 và 2. Năng suất (cái / ngày) và số lượng bán thành phẩm mỗi loại được cho trong bảng sau:
BTP1
BTP2
BTP3
4
2
2
Tổ 1 1 : 1 chuyền
20
30
70
Tổ 2 : 4 chuyền
35
70
90
a) Hỏi phải phân công thời gian sản xuất của các tổ sản xuất như thế nào để số áo thun sản xuất
trong 1 giờ của xưởng là nhiều nhất? Ước tính thời gian trung bình để hoàn thành hợp đồng ?
(2,5 điểm)
b) Hỏi phải phân công trình tự sản xuất các loại BTP cho các tổ sản xuất như thế nào để hoàn thành
hợp đồng sớm nhất? (0,5 điểm)
Ở bài toán SXĐB, SV trình bày kết quả ở dạng số, lấy 2 chữ số thập phân sau dấu phẩy, KHÔNG
trình bày ở dạng phân số.
ĐÁP ÁN
Đề 1
a/ Đưa bài toán về dạng chuẩn (0,5đ)
Các ràng buộc:
????1
+ ????3 + ????4 = 2
{−2????1 − ????2 − 6????3 + ????5 = 1
12????1 + 12????2
+ ????6 = 12
Ẩn phụ: ????4 , ????5
Ẩn giả: ????6
????1 ≥ 0, ????2 ≥ 0, ????3 ≥ 0, ????4 ≥ 0, ????5 ≥ 0, ????6 ≥ 0
????(????) = ????1 + 4????2 + ????3 − ????????6 → ????????????
M
PACBXP: ???? 0 = (0,0,0
...
...
= 1
+ ????5 = 1
− ????6 + ????7 = 16
Ẩn phụ: ????4 , ????5, ????6
Ẩn giả: ????7
????1 ≥ 0, ????2 ≥ 0, ????3 ≥ 0, ????4 ≥ 0, ????5 ≥ 0, ????6 , ????7 ≥ 0
????(????) = ????1 + 4????2 + ????3 + ????????7 → ????????????
M
PACBXP: ???? 0 = (0,0,0,1,1,0,16)
????(???? 0 ) = 16????
Bảng XP: 0,5đ
Bảng 1: 0,5đ
Bảng 2: 0,5đ
ci
xi
bi
????????
????????
????????
????????
????????
????????
1
4
1
0
0
0
????
0
????????
1
-1
-2
0
1
0
0
-
0
????????
1
0
1
1
0
1
0
1
M
????????
16
2
2
8
0
0
-1
2
????(????)
16M
2M
2M
8M
0
0
-M
-1
-4
-1
0
????????
1
-1
-2
0
1
0
0
-
1
????????
1
0
1
1
0
1
0
-
M
????????
8
2
-6
0
0
-8
-1
4
????(????)
8M
2M
-6M
0
0
-8M
-M
+1
-1
-3
+1
0
????????
5
0
-5
0
1
-4
-1/2
-
1
????????
1
0
1
1
0
1
0
-
1
????????
4
1
-3
0
0
-4
-1/2
-
????(????)
5
0
-6
0
0
-3
-1/2
KL: PATU: ???? ∗ = (4,0,1), GTTU: ????(???? ∗ ) = 5 (0,5đ)
b/ Bài toán đối ngẫu (0,5đ)
????(????) = −????1 + ????2 + 16????3 → ????????????
Các ràng buộc:
????1
+ 2????3 ≤ 1
2????
+
????
{
1
2 + 2????3 ≤ 4
????2 + 8????3 ≤ 1
????1 ≥ 0, ????2 ≤ 0, ????3 ≥ 0
Các cặp ràng buộc đối ngẫu (0,5đ)
????1 = 4 0 ⟹ ????1
+ 2????3 = 1
????3 = 1 0 ⟹ ????2 + 8????3 = 1
????1 + 2????2 = 4 −1 ⟹ ????1 = 0
KL: 0,5đ
PATU: ???? ∗ = (0, −3,1/2)
GTTU: ????(???? ∗ ) = 5
Câu 2 (3 điểm):
Nhận xét bài toán: 0,25đ
Tổng Phát Tổng thu
= Thêm trạm phát giả A4 = 220
Chi phí tại các ô cấm là M (M)
Lập bảng xuất phát, phân phối ban đầu đúng: 1đ
Xác định: SOC = 6 = m+n-1 (0,25đ)
Tính ui,vj, delta, xác định vòng, Ô đi vào, Ô đi ra (0,5đ)
Lập bảng mới, tính ui, vj, delta: 0,75
Kết luận: 0,25đ
0
222 0
PATU = (130 435 0 )
0
63 150
Trạm B1 – Q.1 chưa nhận đủ hàng, còn thiếu 220 sản phẩm
GTTU = 50.420
Câu 3 (3 điểm):
Ma trận năng suất ước lượng: (0,5đ)
BTP1
BTP2
BTP3
1
1
1
Tổ 1 1 : 1 chuyền
15
20
15
Tổ 2 : 1 chuyền
70
70
40
Hệ thống nhân tử và ô chọn (1đ)
BTP1
BTP2
BTP3
ui
1
1
1
Tổ 1 1 : 1 chuyền
15
20*
15*
20
Tổ 2 : 1 chuyền
70*
70*
40
70
vj
1
1
1,33
BTP1
BTP2
BTP3
1
1
1
Tổ 1 1 : 1 chuyền
15
20
15*
26,25
Tổ 2 : 1 chuyền
70*
70*
40*
70
vj
1
1
1,75
Z = 27,00
Ô đi ra (1,2). Lamda = 1,31. Ô đi vào (2,3)
(0,5đ)
Z = 25,67
a/ Ma trận PATU (0,5đ)
0
0
1
0,37
0,37
0,27
ui
Thời gian hoàn thành đơn hàng = 1.500/25,67 = 58,43 ngày
b/ Phân bổ thời gian (0,5đ)
Tổ 2 sản xuất BTP1 trong 21,62 ngày, sau đó sản xuất BTP 2 trong 21,62 ngày, sau đó sản xuất
BTP3 trong15,78 ngày.
Tổ 1 sản xuất BTP1 trong 58,43 ngày.
