Đề thi + đáp án cuối kỳ Tối ưu hóa 2025-2026

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.