TRTRƯỜNG
ĐH CÔNG NGHIỆP TPHCM
KHOA KHOA HỌC CƠ BẢN
ĐỀ THI MÔN QUY HOẠCH TUYẾN TÍNH
(Lớp ĐH-15-3-2011 - Thôøi gian 60 phút - Đề
1 -Không dùng tài liệu)
Câu I: (2.5
điểm) Cho bài tóan Quy họach tuyến
tính mà ta gọi là bài tóan (P)
1) Chứng
minh 
là phương án cực biên,
nhưng không phải là phương án tối ưu của bài tóan (P).
là phương án cực biên,
nhưng không phải là phương án tối ưu của bài tóan (P).
2) Hãy
xây dựng một phương án cực biên mới tốt hơn phương án x nói ở trên.
Câu II: (4.5 điểm)
Một Xí nghiệp chăn nuôi cần mua một
lọai thức ăn tổng hợp T1, T2, T3 cho gia súc với tỷ lệ chất dinh dưỡng như sau:
1 kg T1 chứa 4 đơn vị dinh dưỡng D1, 2 đơn vị dinh dưỡng D2, và 1 đơn vị dinh
dưỡng D3; 1 kg T2 chứa 1 đơn vị dinh dưỡng D1, 7 đơn vị dinh dưỡng D2, và 3 đơn
vị dinh dưỡng D3; 1 kg T3 chứa 3 đơn vị dinh dưỡng D1, 1 đơn vị dinh dưỡng D2,
và 4 đơn vị dinh dưỡng D3. Mỗi bữa ăn, gia súc cần tối thiểu 20 đơn vị D1, 25
đơn vị D2 và 30 đơn vị D3.
Biết rằng 1 kg T1 có giá là 10 ngàn đồng, 1
kg T2 có giá là 12 ngàn đồng, 1 kg T3 có giá là 14 ngàn đồng.
Xí nghiệp muốn mua các loại thức ăn T1, T2,
T3 để bảo đảm tốt về chất dinh dưỡng cho một bữa ăn và tổng số tiền mua là nhỏ
nhất.
1) Hãy lập bài toán quy hoạch tuyến tính, ta gọi
đây là bài toán (P).
2) Viết bài toán đối ngẫu (Q) của bài toán (P).
3) Giải bài toán (Q), từ đó suy ra phương án tối
ưu của bài toán (P).
Câu III:
(3 điểm) Cho bài toán vận tải (min hàm mục tiêu cước phí) cân bằng
thu phát như sau:
|
j
i
|
25
|
35
|
120
|
50
|
|
110
|
9
|
6
|
5
|
7
|
|
80
|
2
|
8
|
10
|
6
|
|
40
|
5
|
7
|
9
|
4
|
1)
Hãy xây dựng một phương án ban đầu bằng phương pháp
Fogel.
2)
Hỏi phương án vừa xây dựng ở câu 1) có phải là phương
án tối ưu? Nếu chưa tối ưu, hãy xây dựng một phương án mới tối hơn (chỉ cần một
phương án mới tốt hơn).
KHOA
KHCB TRƯỞNG
BỘ MÔN
ĐÁP ÁN
Câu
I: (2.5 điểm)
1) Phương án 
có hệ véctơ liên kết là A2 ,A3.
có hệ véctơ liên kết là A2 ,A3.
Ta có 
nên x là phương án cực biên.
nên x là phương án cực biên.
Lại có c=(5, 7) và
. 
.
Từ đó 
, lần lượt thay j=1, 2 3 ta được: 
, lần lượt thay j=1, 2 3 ta được: 
. Vì ước
lượng
nên x là phương án không tối ưu.
2) Xây dựng phương án mới như sau:
Véctơ đưa vào thay thế là 
, vì: 
, vì:
Véctơ thay ra là 
, vì 
.
, vì .
Ta
có cơ sở mới là: , 
. Phương án cực biên có hệ véctơ liên kết , là 
. Đây là phương án tốt hơn.
, . Phương án cực biên có hệ véctơ liên kết , là . Đây là phương án tốt hơn.
>
.
Câu II.
1) Gọi 
(kg) là số lượng thức ăn T1;
T2; T3 cần mua.
(kg) là số lượng thức ăn T1;
T2; T3 cần mua.
Tổng số tiền mua là: 
.
.
Số
đơn vị dinh dưỡng D1 có trong bữa ăn là 
.
.
Số
đơn vị dinh dưỡng D2 có trong bữa ăn là 
.
.
Số
đơn vị dinh dưỡng D3 có trong bữa ăn là 
.
.
Theo đề bài ta có bài toán QHTT
2)
Bài toán đối ngẫu (Q) là:
3)
Giải bằng phương pháp đơn hình bài toán (Q) ta có kết quả sau đây:
20 25 30
0 0 0
----------------------------------------------------------------------------------------
Co
So CJ Ph.An
A1 A2 A3
A4 A5 A6
----------------------------------------------------------------------------------------
A4 0
10 4 2 1 1 0 0
A5
0 12 1 7 3 0 1 0
A6
0 14 3 1 4 0 0 1
----------------------------------------------------------------------------------------
-20 -25 -30 0 0 0
----------------------------------------------------------------------------------------
A4
0 1 3/2 13/4
7/4 0
1 0 -1/4
A5
0 3/2 -5/4
25/4 0 0
1 -3/4
A3
30 7/2 3/4
1/4 1
0 0 1/4
----------------------------------------------------------------------------------------
5/2 -35/2
0 0
0 15/2
----------------------------------------------------------------------------------------
A4
0 152/25 18/5
0 0
1 -7/25
-1/25
A2
25 6/25 -1/5
1
0 0
4/25
-3/25
A3
30 86/25 4/5
0 1
0 -1/25
7/25
----------------------------------------------------------------------------------------
-1 0 0 0
14/5 27/5
----------------------------------------------------------------------------------------
A1
20 76/45
1 0
0 5/18 -7/90
-1/90
A2
25 26/45
0 1 0 1/18 13/90
-11/90
A3
30 94/45
0 0
1 -2/9
1/45 13/45
----------------------------------------------------------------------------------------
0 0
0 5/18
49/18 97/18
----------------------------------------------------------------------------------------
Phương
án tối ưu của bài toán đối ngẫu là:
y = (
76/45, 26/45, 94/45)
Giá
trị tối ưu: f = 998/9
Phương
án tối ưu của bài toán đối gốc là:
x=
( 5/18, 49/18, 97/18)
Câu III:
Trường hợp xây dựng bằng phương pháp
Fogel
1) Phương án ban đầu
được xây dựng bằng phương pháp Fogel như sau:
|
j
i
|
25
|
35
|
120
|
50
|
|
|
110
|
9
|
6
|
5
110
|
7
|
1 1
K
|
|
80
|
2
25
|
8
35
|
10
10
|
6
10
|
4 2 2
|
|
40
|
5
|
7
|
9
|
4
40
|
1 3
3
|
|
|
3
K
K
|
1
1
1
|
4
4
1
|
2
2
2
|
|
2) Đây
là phương án cực biên, vì tập các ô chọn không chứa chu trình. Ta kiểm tra tính
tối ưu của phương án:
Chọn
các số ri và sj như sau:
|
9
|
6
|
5
110
|
7
|
R1=0
|
|
2
25
|
8
35
|
10
10
|
6
10
|
R2=-5
|
|
5
|
7
|
9
|
4
40
|
R3=-3
|
|
S1=3
|
S2 = -3
|
S3 = -5
|
S4 = -1
|
|
Ta
được ma trận cước phí mới
|
12
|
3
|
0
110
|
6
|
|
0
25
|
0
35
|
0
10
|
0
10
|
|
5
|
1
|
1
|
0
40
|
Đay
là phương án tối ưu.
Trường hợp xây dựng bằng phương pháp min-cước:
Kết quả
trùng với phương pháp Fpgel.
0 nhận xét:
Post a Comment