TRƯỜNG ĐẠI HỌC SPKT TPHCM
Đáp án môn: Tối ưu hóa HK 2 NH 2023-2024
KHOA KINH TẾ
Mã môn học: MAOP230706
Đề số: 2
BM QTKD
Thời gian: 60 phút
Được phép sử dụng tài liệu
Câu 1 (4 điểm)
1đ
a. Lập bài toán đối ngẫu (D) tương ứng của (P).
g(y) = 6y1 + 2y2 + 8y3 → min
y1 + 2y2 + 2y3 2
(D): y1 + 4y2 + 2y3 4
2y1 + 2y2 + 2y3 2
y1 0, y2: k.h.c, y3 0
b1. Giải bài toán gốc (P)
Bài toán dạng chuẩn:
f(x) = 2x1 + 4x2 + 2x3 - Mx6 → max
0,25 đ
x1 + x2 + 2x3 + x4 = 6
2x1 + 4x2 + 2x3 + x6 = 2
2x1 + 2x2 + 2x3 + x5 = 8
xj 0 (j = 1,6)
Ci
1đ
Xi
Yi
X1
X2
X3
X4
X5
2
4
2
0
0
Lamda
0
X4
6
1
1
2
1
0
6
-M
X6
2
2
4
2
0
0
1/2
0
X5
8
2
2
2
0
1
4
F(x)
2M
-2M - 2
-4M - 4
-2M - 2
0
0
0
X4
11/2
1/2
0
3/2
1
0
-
4
X2
1/2
1/2
1
1/2
0
0
-
0
X5
7
1
0
1
0
1
-
F(x)
2
0
0
0
0
0
0,5 đ
Tại bảng trên: Ta có ∆ij 0 ∀ ô (????,????) nên PA đang xét là PATƯ của bài toán dạng chuẩn:
0,25 đ
x*= (0, 1/2, 0, 11/2, 7, 0), F(x*) = 2
x6 = 0 với x6 là ẩn giả nên bài toán gốc ban đầu có PATƯ là:
x*= (0, 1/2, 0) F(x*) = 2
b2. Từ kết quả của bài toán gốc (P), hãy suy ra PATƯ của bài toán đối ngẫu (D)
Ta có:
1đ
x2* = 1/2 0 = y1 + 4y2 + 2y3 = 4 (1)
0 + 1/2 + 2*0 = 1/2 6 = y1 = 0 (2)
2*0 + 2*1/2 + 2*0 = 1 8 = y3 = 0 (3)
Kết hợp (1), (2), (3), ta được y1 = 0, y2 = 1, y3 = 0
Vậy y* = (0, 1, 0), g(y*) = 2
Câu 2 (3 điểm )
0,5 đ
Thêm trạm thu giả B3=120
Do nhà máy A2 phải sản xuất hết công suất, và tuyến đường A2 đến B1 bị cấm nên C23=
M và C21= M với (M 0, rất lớn)
Cửa hàng
B1: 110
B2: 140
B3 :120
10
11
0
Nhà máy
A1:120
_
0,5 đ
110
M
+
10
14-M 15
u1=0
x
M
_
A2:140
x
A3:110
-M-4
12
-4
+
9
x
v1=10
20
u2=4
120
0
M-6
110
v2=11
x
v3= M-4
u3=-2
0,25 đ
Ô đưa vào là ô (13), ô đưa ra là ô (12), d=10
Cửa hàng
B1: 110
B2: 140
10
11
B3 :120
Nhà máy
0,5 đ
4-M
A1:120
u1=0
110
M
x
15
A2:140
A3:110
12
M-8
9
0
110
M-6
+
110
v2=15-M
u2=M
_
30
_
v1=10
10
M
+
x
0, 25 đ
0
u3=M-6
x
v3= 0
Ô đưa vào là ô (33), ô đưa ra là ô (23), d=110
Cửa hàng
B1: 110
B2: 140
10
11
B3 :120
Nhà máy
-2
0
A1:120
u1=0
110
0,5 đ
M
x
16-M 15
10
M
6-M
A2:140
u2=6
x
A3:110
12
-2
140
9
0
x
v1=10
x
0
v2=9
110
v3= 0
Ta có
∆???????? = 0 ∀ ô (????,????) nên PA đang xét là PATƯ của bài toán VT (M)
0,25
đ
110
0
0
0
140
0
F(x) = 3200 (ĐVT: 1.000.000 đồng)
10
0
110
u3=0
X23=0, X21= 0 với ô (2,3) (2,1) là ô cấm nên PATƯ của BT VT (M) cũng là PATƯ của
BTBĐ
110
0
0
0,25 đ
0
140
0
Chi phí tối ưu là : F(x) = 3200 (ĐVT: 1.000.000 đồng)
Câu 3: (3 điểm)
Hệ thống nhân tử và ô chọn:
0,5 đ
0,25 đ
M/C
C1: 1
C2: 1
Ui
M1: 1
240*
160*
240 +
M2: 1
120
120*
180 -
M3: 1
180
135*
202,5 -
Vj
1+
1,5 -
1,04
-0,04
0
1
0
1
Giá trị z = 249
Lập hệ phương trình:
X11 + X12 = 1
X22 = 1
X32 = 1
240X11 = 249
160X12 +120X22 + 135X32 = 249
Ma trận phương án
0,25 đ
Phương án tìm được chưa phải là tối ưu vì còn tồn tại giá trị X12 = - 0,04 0
Vì vậy ta cần điều chỉnh hệ thống nhân tử và ô chọn
Ô đưa ra là: (1,2)
Hệ số Lamda = 1,13
Ô đưa vào là: (3,1)
0,5 đ
M/C
C1: 1
C2: 1
Ui
M1: 1
240*
160
271,2
M2: 1
120
120*
180
M3: 1
180*
135*
202,5
Vj
1,13
1,5
0,5 đ
Giá trị Z = 248,56
X11 = 1
X22 = 1
X31+ X32 = 1
240X11 + 180 X31= 248,56
120X22 + 135X32 = 248,56
Ma trận phương án:
1
0
0
1
0,05
0,95
Do xij ≥ 0 với mọi ô (i,j) nên phương án tìm được là tối ưu.
Phương án tối ưu của bài toán là:
0, 5 đ
M/C
C1: 1
C2: 1
M1: 1
1
0
M2: 1
0
1
M3: 1
0,05
0,95
Như vậy theo bảng trên nhà máy cần bố trí các máy làm việc trong một ngày như sau:
+ Bố trí máy M1 dành 1 thời gian sản xuất chi tiết C1
+ Bố trí máy M2 dành 1 thời gian sản xuất chi tiết C2
+ Bố trí máy M3 dành 0,05 thời gian sản xuất chi tiết C1 và 0,95 thời gian sản xuất chi tiết C2.
Khi đó số lượng sản phẩm sản xuất được là z = 248,56
Thời gian trung bình để hoàn thành hợp đồng là:
T= 4000/ 248,56 = 16,09 ngày (khoảng 17 ngày)
b. Hỏi phải phân công trình tự sản xuất bàn, ghế cho các máy như thế nào để hoàn thành hợp
đồng sớm nhất? (0.5 điểm)
+ Bố trí máy M1 dành 1*16,09 = 16,09 thời gian sản xuất Bàn
0,5 đ
+ Bố trí máy M2 dành 1*16,09 = 16,09 thời gian sản xuất Ghế
+ Bố trí máy M3 dành 0,05*16,09 = 0,80 thời gian sản xuất Bàn trước và 0,95*16,09 = 15,29
thời gian sản xuất Ghế sau
