Một số bài toán đơn hình

Chia sẻ: huonggiang08

Tài liệu tham khảo Một số bài toán đơn hình có kèm lời giải giúp các bạn học và ôn toán tốt hơn

Bạn đang xem 7 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: Một số bài toán đơn hình

Page 1


Bai toan đơn hinh
̀ ́ ̀

Câu1: 4 ̉
Điêm
x1 + x2 + x3  min
x1 − x4 − 2 x6 = 5

 x 2 + 2 x 4 − 3 x5 + x 6 = 3
 x3 + 2 x 4 − 5 x5 + 6 x 6 = 5
xj ≥ 0 ,j = 1..6

Bài toán có dạng chuẩn, các biến cố độc lập x1,x2,x3 nên phương án cực biên
x▫ = (5;3;5;0;0;0) cơ sở jo = {A1;A2;A3} 0.5

Bảng đơn hình

Hệ số jo Cơ sở jo Phương 1 1 1 0 0 0
́
an x1 x2 x3 x4 x5 x6
1 x1 5 1 0 0 -1 0 -2 0.25
1 x2 3 0 1 0 2 -3 1 0.25
1 x3 5 0 0 1 2 -5 6 0.25
f(x) 13 0 0 0 3 -8 5 0.25
1 x1 6.7 1.0 0.0 0.3 -0.3 -1.7 0.0 0.25
1 x2 2.2 0.0 1.0 -0.2 1.7 -2.2 0.0 0.25
0 x6 0.8 0.0 0.0 0.2 0.3 -0.8 1.0 0.25
f(x) 8.8 0.0 0.0 -0.8 1.3 -3.8 0.0 0.25
1 x1 7.1 1 0.2 0.3 0 -2.1 0 0.25
0 x4 1.3 0 0.6 -0.1 1 -1.3 0 0.25
0 x6 0.4 0 -0.2 0.2 0 -0.4 1 0.25
f(x) 7.1 0 -0.8 -0.7 0 -2.1 0 0.25


Vậy phương án tối ưu của bài toán là (7,1;0;0;1,3;0;0,4)
Minf(x)=7.1
Câu 2:

2 x1 + 4 x 2 + x3 + x 4 → Max
x1 + 3 x 2 + x4 ≤ 4

2 x1 + x 2 ≤3
 x 2 + 4 x3 + x 4 ≤ 3

x j ≥ 0; j := 1..; 4

Đưa về bai toan dang chuân sau:
̀ ́ ̣ ̉

− 2 x1 − 4 x 2 − x3 − x 4 → Min
x1 + 3 x 2 + x 4 + x5 = 4

2 x1 + x 2 + x6 = 3
 0.25
 x 2 + 4 x3 + x 4 + x7 = 3
0.25
x j ≥ 0; j := 1..;7
Bảng đơn hình
Page 2


hệ số jo cơ sở jo Phương -2 -4 -1 -1 0 0 0
́
an x1 x2 x3 x4 x5 x6 x7
0 x5 4 1 3 0 1 1 0 0 0.25
0 x6 3 2 1 0 0 0 1 0
0 x7 3 0 1 4 1 0 0 1 0.25
f(x) 0 2 4 1 1 0 0 0 0.25
-4 x2 1.3 0.3 1.0 0.0 0.3 0.3 0.0 0.0 0.25
0 x6 1.7 1.7 0.0 0.0 -0.3 -0.3 1.0 0.0
0 x7 1.7 -0.3 0.0 4.0 0.7 -0.3 0.0 1.0 0.25
f(x) -5.3 0.7 0.0 1.0 -0.3 -1.3 0.0 0.0 0.25
-4 x2 1.3 0.3 1.0 0.0 0.3 0.3 0.0 0.0
0 x6 1.7 1.7 0.0 0.0 -0.3 -0.3 1.0 0.0 0.25
-1 x3 0.4 -0.1 0.0 1.0 0.2 -0.1 0.0 0.3 0.25
f(x) -5.75 0.75 0 0 -0.5 -1.25 0 -0.25 0.25
-4 x2 1 0 1 0 0.4 0.4 -0.2 0
-2 x1 1 1 0 0 -0.2 -0.2 0.6 0 0.25
-1 x3 0.5 0 0 1 0.15 -0.1 0.05 0.25 0.25
-6.5 0.0 0.0 0.0 -0.4 -1.1 -0.5 -0.3 0.25

Vậy phương án tối ưu của bài toán là x= (1;1;0.5;0.0;0;0) 0.25
Maxf(x)=6.5 0.25
Câu3. ̉ ̀ ́
Giai bai toan QHTT sau:
f ( x ) = 2 x1 − 8 x 2 + x3 → Min
6 x1 + 8 x 2 − 2 x3 ≤ 1

2 x1 − 8 x 2 + x3 ≤ 3
− x − 5 x − x ≤ 2
 1 2 3


f ( x ) → Min
6 x1 + 8 x 2 − 2 x 3 + x 4 =1
 0.25
2 x1 − 8 x 2 + x3 + x5 = 3
− x − 5 x − x + x6 = 2
 1 2 3

x j ≥ 0; j = 1;.. 6 0.25

Bảng đơn hình
hệ số jo cơ sở jo Phương 2 -8 1 0 0 0
́
an x1 x2 x3 x4 x5 x6
0 x4 1 6 8 -2 1 0 0 0.25
0 x5 3 2 -8 1 0 1 0 0.25
0 x6 2 -1 -5 -1 0 0 1 0.25
f(x) 0 -2 8 -1 0 0 0 0.25
1 x2 0.13 0.75 1.00 -0.25 0.13 0.00 0.00 0.25
0 x5 4 8 0 -1 1 1 0 0.25
0 x6 2.63 2.75 0.00 -2.25 0.63 0.00 1.00 0.25
f(x) -1 -8 0 1 -1 0 0 0.25

Do ∆3 > 0 va x j 3 ≤ 0 ∀j ∈ J 0 Nên bai toan không giai đươc
̀ ́ ̉ 1.5

Câu 9:
1
f ( x) = 2 x1 + 4 x 2 + x3 − 3x 4 → Min
2
2 x1 + 2 x 2 + 3 x3 + 3x 4 ≤ 50

4 x1 + 8 x 2 + 2 x3 + 3x 4 = 80
4 x + 4 x + x + 2 x = 40
 1 2 3 4

x j ≥ 0; j = 1;..; 4
1 Page 3
f ( x) = 2 x1 + 4 x 2 + x3 − 3x 4 → Min
2
2 x1 + 2 x 2 + 3 x3 + 3x 4 ≤ 50

4 x1 + 8 x 2 + 2 x3 + 3x 4 = 80
4 x + 4 x + x + 2 x = 40
 1 2 3 4

x j ≥ 0; j = 1;..; 4

Đưa về bai toan:
̀ ́
1
f ( x ) = 2 x1 + 4 x 2 + x3 − 3x 4 → Min
2
2 x1 + 2 x 2 + 3 x3 + 3 x 4 + x5 = 50

4 x1 + 8 x 2 + 2 x3 + 3 x 4 + x g 2 = 80

4 x1 + 4 x 2 + x3 + 2 x 4 + x g 3 = 40
x j ≥ 0; j = 1;..; 4 x5 ≥ 0
̀ ́ ̣
Bai toan phu:
P ( x; x g ) = x g1 + x g 2 → Min
2 x1 + 2 x 2 + 3 x3 + 3 x 4 + x5 = 50 0.25

4 x1 + 8 x 2 + 2 x3 + 3 x 4 + x g 2 = 80

4 x1 + 4 x 2 + x3 + 2 x 4 + x g 3 = 40
0.25
x j ≥ 0; j = 1;..;4 x5 ≥ 0 ; x g1 ≥ 0; x g 2 ≥ 0

Bảng đơn hình

2 4 0.5 -3 0 0 0
hệ số jo cơ sở jo Phương 0 0 0 0 0 1 1
́
an x1 x2 x3 x4 x5 xg2 xg3
0 x5 50 2 2 3 3 1 0 0
1 xg2 80 4 8 2 3 0 1 0
1 xg3 40 4 4 1 2 0 0 1
P(x) 120 8 12 3 5 0 0 0
0 x5 30 1 0 2.5 2.25 1 0
0 x2 10 0.5 1 0.25 0.375 0 0
1 xg3 0 2 0 0 0.5 0 1
P(x) 0 2 0 0 0.5 0 0
0 x5 30 0 0 2.5 2 1
4 x2 10 0 1 0.25 0.25 0
2 x1 0 1 0 0 0.25 0 0 0.5
P(x) 0 0 0 0 0 0
f(x) 40 0 0 0.5 4.5 0
0 x5 30 -8 0 2.5 0 1
4 x2 10 -1 1 0.25 0 0
-3 x4 0 4 0 0 1 0
f(x) 40 -18 0 0.5 0 0
x3 12 -3.2 0 1 0 0.4
x2 7 -0.2 1 0 0 -0.1
x4 0 4 0 0 1 0
f(x) 34 -16.4 0 0 0 -0.2

Phương an tôi ưu: x= ( 0;7;12;0;0)
́ ́
Page 4


Min f(x)=34
́ ́
Cach khac:
hệ số jo cơ sở jo Phương 2 4 0.5 -3 0 1 1
́
an x1 x2 x3 x4 x5 xg1 xg2
0 x5 50 2 2 3 3 1 0 0 0.25
1 xg1 80 4 8 2 3 0 1 0
1 xg2 40 4 4 1 2 0 0 1 0.25
P(x) 120 6 8 2.5 8 0 0 0 0.25
0 x5 30 1 0 2.5 2.25 1 0.25
4 x2 10 0.5 1 0.25 0.38 0
1 xg2 0 2 0 0 0.5 0 0.25
f(x) 40 2 0 0.5 5 0 0.25
0 x5 30 -8 0 2.5 0 1
4 x2 10 -1 1 0.25 0 0 0.25
-3 x4 0 4 0 0 1 0 0.25
f(x) 40 -18 0 0.5 0 0 0.25
0.5 x3 12 -3.2 0 1 0 0.4
4 x2 7 -0.2 1 0 0 -0.1 0.25
-3 x4 0 4 0 0 1 0 0.25
f(x) 34 -16.4 0 0 0 -0.2 0.25

Vậy phương án tối ưu của bài toán là ( 0 ; 7 ; 12 ; 0 ; 0) 0.25
Max f(x) = 34 0.25
Câu 10:

f ( x ) = 2 x1 + 3 x 2 − 5 x 3 → Max

− 4 x1 + x 2 + 2 x3 ≥ 12

 1
− 2 x1 + x 2 + x3 ≤ 8
 2
 3
− 2 x1 + 2 x 2 + x3 = 20

x j ≥ 0; j = 1;..; 3

p ( x ) = −2 x1 − 3 x 2 + 5 x3 → Min

− 4 x1 + x 2 + 2 x3 − x 4 + x g1 = 12

 1
− 2 x1 + x 2 + x 3 + x 5 = 8
 2
 3
− 2 x1 + 2 x 2 + x 3 + x g 2 = 20

x j ≥ 0; j = 1;..; 3
-2 -3 5 0 0 0 0
hệ số jo cơ sở jo Phương 0 0 0 0 0 1 1
́
an x1 x2 x3 x4 x5 xg1 xg2
1 xg1 12 -4 1 2 -1 0 1 0
0 x5 8 -2 0.5 1 0 1 0 0
1 xg2 20 -2 1.5 1 0 0 0 1
P(x) 32 -6 2.5 3 -1 0 1 1
Page 5


0 x3 6 -2 0.5 1 -0.5 0 0.5 0
0 x5 2 0 0 0 0.5 1 0
1 xg2 14 0 1 0 0.5 0 1
P(x) 14 0 1 0 0.5 0 1

Do ∆2 > 0; x j 2 > 0 ∀j Bài toán không giải đươc


Bài 11
f ( x) = 4 x1 + x 2 + x3 + 3 x 4 → Min
2 x 2 + x3 + x 4 = 16 2 x 2 + x3 + x 4 = 16
4 x2 + 2 x5 ≤ 8 4 x2 + 2 x5 + x 6 = 8
x1 + x 2 + 2 x 4 + x5 = 2 x1 + x 2 + 2 x 4 + x5 =2
xj ≥ 0

hệ số jo cơ sở jo Phương 4 1 1 3 0 0
́
an x1 x2 x3 x4 x5 x6
1 x3 16 0 2 1 1 0 0
0 x6 8 0 4 0 0 2 1
4 x1 2 1 1 0 2 1 0
24 0 5 0 6 4 0
x3 15 -0.5 1.5 1 0 -0.5 0 10
x6 8 0 4 0 0 2 1 2
x4 1 0.5 0.5 0 1 0.5 0 2
18 -3 2 0 0 1 0
x3 12 -2 0 1 -3 -2 0
x6 0 -4 0 0 -8 -2 1
x2 2 1 1 0 2 1 0
14 -5 0 0 -4 -1 0
Page 6
Page 7
Page 8




12
40
Page 9
Page 10
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản