34 trang 70 lượt tải

Bài Tập Chương 4 Toán Kinh Tế 1 | Học Viện Ngân Hàng

140

Bài Tập Chương 4 Toán Kinh Tế 1 | Học Viện Ngân Hàng với những kiến thức và thông tin bổ ích giúp sinh viên tham khảo, ôn luyện và phục vụ nhu cầu học tập của mình cụ thể là có định hướng, ôn tập, nắm vững kiến thức môn học và làm bài tốt trong những bài kiểm tra, bài tiểu luận, bài tập kết thúc học phần. Mời bạn đọc đón xem!

Môn: Toán kinh tế (HVNH) 45 tài liệu

Trường: Học viện Ngân hàng 1 K tài liệu

Tác giả:

Profile

Thanh Hoa

1 năm trước
Danh sách Quiz
/34
BÀI TẬP CHƯƠNG 4
Bài 1:
Ta có bảng đơn hình:
Hệ số Cơ sở
Phươ
ng 1 3 3 -3 -1 0
Án
x
1
x
2
x
3
x
4
x
5
x
6
1
x
1
4 1 4 -1 -1 0 0
-1
x
5
4 0 2 2 1 1 0
0
x
6
3 0 1 2 (2) 0 1
B1 f(x) 0 0 -1 -2 [1] 0 0
1
x
1
11/2 1 9/2 0 0 0 ½
-1
x
5
5/2 0 3/2 1 0 1 -1/2
-3
x
4
3/2 0 ½ 1 1 0 ½
B2 f(x) -3/2 0 -3/2 -7 0 0 -1/2
Vậy bài toán có phương án cực biên tối ưu x* = ( 11/2, 0, 0, 3/2, 5/2,
0 ) với
fmin= -3/2
Bài 2:
Ta có bảng đơn hình:
Hệ số Cơ sở
Phươ
ng 1 3 5 2 3 3
Án
x
1
x
2
x
3
x
4
x
5
x
6
3
x
2
3 1 1 1 1 0 0
3
x
5
2 (2) 0 3 -2 1 0
3
x
6
3 1 0 1 3 0 1
B1 F(x) 24 [11] 0 10 4 0 0
3
x
2
2 0 1 -1/2 2 -1/2 0
1
x
1
1 1 0 3/2 -1 1/2 0
3
x
6
2 0 0 -1/2 (4) -1/2 1
B2 F(x) 13 0 0 -13/2 [15] -11/2 0
3
x
2
1 0 1 -1/4 0 -1/4 -1/2
1
x
1
3/2 1 0 11/8 0 3/8 1/4
2
x
4
1/2 0 0 -1/8 1 -1/8 1/4
B3 F(x) 11/2 0 0 -37/8 0 -29/8 -15/4
Vậy bài toán có phương án cực biên tối ưu x* = ( 3/2, 1, 0, ½, 0, 0 )
với fmin = 11/2
Bài 3:
Ta có bảng đơn hình:
Hệ số Cơ sở
Phươ
ng 0 -2 2 2 -2 1
Án
x
1
x
2
x
3
x
4
x
5
x
6
-2
x
2
5 1 1 5 0 1 0
2
x
4
2 (2) 0 3 1 -2 0
1
x
6
5 1 0 1 0 3 1
B1 F(x) -1 [3] 0 -5 0 -1 0
-2
x
2
4 0 1 7/2 -1/2 2 0
0
x
1
1 1 0 3/2 ½ -1 0
1
x
6
4 0 0 -1/2 -1/2 (4) 1
B2 F(x) -4 0 0 -19/2 -3/2 [2] 0
-2
x
2
2 0 1 15/4 -1/4 0 -1/2
0
x
1
2 1 0 11/8 3/8 0 ¼
-2
x
5
1 0 0 -1/8 -1/8 1 ¼
B3 F(x) -6 0 0 -37/4 -5/4 0 -1/2
Vậy bài toán có phương án tối ưu x*= ( 2, 2, 0, 0, 1, 0 ) với fmin= -6
Bài 4:
Đưa bài toán về dạng chính tắc ta có:
{
2 x 1 2−x +x 3−5 x 4=5
3 3 6x 1− x 3+ x 4=3
2 4x 1 2−x −x +x 5=2
xj≥ 0( j=1. .5 )
Xét bài toán phụ:
P(x) =
x
1
g
+x
2
g
→ min
{
2 x 1 2 4−x +x 3−5 x + x
1
g
=5
3 3x 1− x 3+6 x 4+ x
2
g
=3
2 x 1 5 2−x 2−x 4+ x =
xj ≥ 0
(
j=1. .5
)
; x
1
g
, x
2
g
≥ 0
Ta có bảng đơn hình:
Hệ số Cơ sở
Phươn
g 1 1 1 3 0 1 1
Án
x
1
x
2
x
3
x
4
x
5
x
1
g
x
2
g
1
x
1
g
5 2 -1 1 -5 0 1 0
1
x
2
g
3 (3) 0 -3 6 0 0 1
0
x
5
2 2 -1 0 -1 1 0 0
B1 P(x) 8 [5] -1 -2 1 0 0 0
1
x
1
g
3 0 -1 3 -9 0 1
0
x
1
1 1 0 -1 2 0 0
0
x
5
0 0 -1 (2) -5 1 0
B2 P(x) 3 0 -1 [3] -9 0 0
1
x
1
g
3 0 (½) 0 -3/2 -3/2 1
0
x
1
1 1 -1/2 0 -1/2 ½ 0
0
x
3
0 0 -1/2 1 -5/2 ½ 0
B3 P(x) 3 0 [½] 0 -3/2 -3/2 0
1
x
2
6 0 1 0 -3 -3
1
x
1
4 1 0 0 -2 -1
1
x
3
3 0 0 1 -4 -1
B4 F(x) 13 0 0 0 -12 -5
Vậy bài toán có patu x*=( 4,6,3,0) với fmin= 13
Bài 5:
Đưa bài toán về dạng chính tắc ta có:
Xét bài toán phụ:
P(x) =
x
1
g
→min
{
3 x 1−x 2−x 3+ x 4 +x
1
g
=4
x x x x1− 2+ 3+ x 4 + 5=1
2 x 1 2 6+x +2 x 3+x =6
xj ≥ 0
(
j=1. .6
)
, x
1
g
≥ 0
Ta có bảng đơn hình:
Hệ số Cơ sở
Phươn
g -5 1 -1 -4 0 0 1
Án
x
1
x
2
x
3
x
4
x
5
x
6
x
1
g
1
x
1
g
4 3 -1 -1 1 0 0 1
0
x
5
1 (1) -1 1 1 1 0 0
0
x
6
6 2 1 2 0 0 1 0
B1 P(x) 4 [3] -1 -1 1 0 0 0
1
x
1
g
1 0 (2) -4 -2 -3 0 1
0
x
1
1 1 -1 1 1 1 0 0
0
x
6
4 0 3 0 -2 -2 1 0
B2 P(x) 1 0 [2] -4 -2 -3 0 0
1
x
2
1/2 0 1 -2 -1 -3/2 0
-5
x
1
3/2 1 0 -1 0 -1/2 0
0
x
6
5/2 0 0 6 1 5/2 1
B3 F(x) -7 0 0 4 3 1 0
Vậy bài toán có patu x*= ( 3/2, ½, 0, 0) với fmax= -7
Bài 6 :
Đưa bài toán về dạng chính tắc ta có :
{
2 x1+5 2x 2−x 3 4−4 x − x 5=6
2 x 1 4+2 2x 2+4 x 3− x −x 5=2
−2 x 1+ +x 2 7 x 3+2 x 4+x 6=6
xj ≥0 ( j=1. .6)
Xét bài toán phụ :
P(x)=
x
1
g
+x
2
g
→ min
{
2 x1+5 2x 2−x 3 4−4 x − x 5+ x
1
g
=6
2 x 1 4+2 2x 2+4 x 3− x −x 5+x
2
g
=2
− =2 x 1+x 2+ +7 x 3 2 x 4 +x 6 6
xj≥ 0
(
j=1. .6
)
; x
1
g
, x
2
g
≥ 0
Hệ số Cơ sở
Phươ
ng -2 3 3 2 0 0 1 1
Án
x
1
x
2
x
3
x
4
x
5
x
6
x
1
g
x
2
g
1
x
1
g
6 2 5 -1 -4 -2 0 1 0
1
x
2
g
2 2 (2) 4 -2 -1 0 0 1
0
x
6
6 -2 1 7 2 0 1 0 0
B1 P(x) 8 4 [7] 3 -6 -3 0 0 0
1
x
1
g
1 -3 0 -11 (1) 1/2 0 1
0
x
2
1 1 1 2 -1 -1/2 0 0
0
x
6
5 -3 0 5 3 ½ 1 0
B2 P(x) 1 -3 0 -11 [1] 1/2 0 0
2
x
4
1 -3 0 -11 1 (1/2) 0
3
x
2
2 -2 1 -9 0 0 0
0
x
6
2 6 0 38 0 -1 1
B3 F(x) 8 -10 0 -52 0 [1] 0
0
x
5
2 -6 0 -22 2 1 0
3
x
2
2 -2 1 -9 0 0 0
0
x
6
4 0 0 16 2 0 1
B4 F(x) 6 -4 0 -30 -2 0 0
Vậy bài toán có patu x*= ( 0, 2, 0, 0, 2) với fmin=6
Bài 7 :
Đưa bài toán về dạng chính tắc ta có :
{
− − − −x 1+ x 2+x3 x 4 x 5 x 6=3
x 1+ x x x2+ 3−x 4−x 5− 7=2
x x x1+x 2−2 x 3−3 4+2 x 5+ 8=4
xj ≥ 0
(
j=1. .8
)
Xét bài toán phụ :
P(x)=
x
1
g
+x
2
g
→ min
{
− − − −x1+x 2+x 3 x 4 x5 x 6 + x
1
g
=3
x x1+ x x2+ 3− 4−x x5− 7 +x
2
g
=2
x x x1+ x 2−2 x 3−3 4+2 x5+ 8=4
xj≥ 0
(
j=1..8
)
; x
1
g
, x
2
g
≥ 0
Ta có bảng đơn hình :
Hệ
số
Cơ
sở
Phươ
ng án
3 4 4 5 1 0 0 0 1 1
x x x x x x
1 2 3 4 5 6
x7 x8
x
1
g
x
2
g
1
x
1
g
3 -1 1 1 -1 -1 -1 0 0 1 0
1
x
2
g
2 1 (1) 1 -1 -1 0 -1 0 0 1
0
x
8
4 1 1 -2 -3 2 0 0 1 0 0
B1 P(x) 5 0 [2] 2 -2 -2 -1 -1 0 0 0
1
x
1
g
1 -2 0 0 0 0 -1 (1) 0 1
0 x
2
2 1 1 1 -1 -1 0 -1 0 0
0 x
8
2 0 0 -3 -2 3 0 1 1 0
B2 P(x) 1 -2 0 0 0 0 -1 [1] 0 0
0 x
7
1 -2 0 0 0 0 -1 1 0
4 x
2
3 -1 1 1 -1 -1 -1 0 0
0 x
8
1 2 0 -3 -2 3 1 0 1
B3 F(x) 12 -7 0 0 -9 -5 -4 0 0
Vậy bài toán có patu x* =( 0, 3, 0, 0, 0 ) với fmin=12
Bài 8 :
Đưa bài toán về dạng chính tắc ta có :
{
x x1−x 2+x 4+2 5=16
x x x1+x 2+2 x 3−2 5− 6 35=
− =2 x 2+2 x 3−4 x 5 20
xj≥ 0
(
j=1..6
)
Xét bài toán phụ :
P(x)=
x
2
g
+x
3
g
→ min
{
x 1−x 2+ x x4 +2 5=16
x x x1+x 2+2 x 3−2 5− 6+x
2
g
=35
−2 x 2+2 x3−4 x 5+x
3
g
=20
xj≥ 0
(
j=1..6
)
; x
2
g
, x
3
g
≥0
Ta có bảng đơn hình :
Hệ số Cơ sở
Phươ
ng 2 2 -3 -2 1 0 1 1
Án
x
1
x
2
x
3
x
4
x
5
x
6
x
2
g
x
3
g
0
x
4
16 1 -1 0 1 2 0 0 0
1
x
2
g
35 1 1 2 0 -2 -1 1 0
1
x
3
g
20 0 -2 (2) 0 -4 0 0 1
B1 P(x) 55 1 -1 [4] 0 -6 -1 0 0
0
x
4
16 1 -1 0 1 2 0 0
1
x
2
g
15 1 (3) 0 0 2 -1 1
0
x
3
10 0 -1 1 0 -2 0 0
B2 P(x) 15 1 [3] 0 0 2 -1 0
-2
x
4
21 4/3 0 0 1 8/3 -1/3
2
x
2
5 1/3 1 0 0 2/3 -1/3
-3
x
3
15 1/3 0 1 0 -4/3 -1/3
B3 f(x) -77 -5 0 0 0 -1 1
Ta có : Ta có:
{
∆ 6=1
Xj6 ≤ 0
Bài toán không giải được
Vậy bài toán không giải được
Bài 9 :
Đưa bài toán về dạng chính tắc ta có :
{
2 x 1+2 x 3 4+x =14
5 x 1 62+3 2 4x 2 3+x − x +x 5=
−2 x 1+ +2 x 2 2 x 3+ x 4=16
xj≥ 0
(
j=1..5
)
Xét bài toán phụ :
P(x)=
x
1
g
+x
3
g
→ min
{
2 x 1 3+2 x +x 4 +x
1
g
=14
5 x 1 62+3 2 4x 2 3+x − x +x 5=
−2 x 1+ +2 x 2 2 x 3+ x 4=16
xj ≥ 0
(
j=1. .5
)
;x
1
g
, x
3
g
≥ 0
Ta có bảng đơn hình :
Hệ số Cơ sở
Phươn
g 4 2 3 2 0 1 1
Án
x
1
x
2
x
3
x
4
x
5
x
1
g
x
3
g
1
x
1
g
14 2 0 (2) 1 0 1 0
0
x
5
62 5 3 1 -2 1 0 0
1
x
3
g
16 -2 2 2 1 0 0 1
B1 P(x) 30 0 2 [4] 2 0 0 0
0
x
3
7 1 0 1 1/2 0 0
0
x
5
55 4 3 0 -5/2 1 0
1
x
3
g
2 -4 (2) 0 0 0 1
B2 P(x) 2 -4 [2] 0 0 0 0
3
x
3
7 1 0 1 ½ 0
0
x
5
52 10 0 0 -5/2 1
2
x
2
1 -2 1 0 0 0
B3 F(x) 23 -5 0 0 -1/2 0
Vậy bài toán có patu x*=( 0, 1, 7, 0) với fmin=23
Bài 10 :
Đưa bài toán về dạng chính tắc ta có :
{
2 2x 1−x 2+x 3− x 4 5+x =5
3 6x 1 2+2 x −3 x 3+ x 4=3
x 1−2 x x x2+3 3−2 x 4 + 6=2
xj≥ 0
(
j=1..6
)
Xét bài toán phụ :
P(x)=
x
1
g
→min
{
2 x 1 5−x 2 3 5+x −2 4x +x =
3 3 6x 1 2+2 x − x3+ x 4 +x
1
g
=3
x x1−2 2+3 x 3−2x 4 +x 6=2
xj≥ 0
(
j=1..6
)
; x
1
g
≥ 0
Ta có bảng đơn hình :
Hệ số Cơ sở
Phươn
g -3 3 -1 -3 0 0 1
Án
x
1
x
2
x
3
x
4
x
5
x
6
x
1
g
0
x
5
5 2 -1 1 -2 1 0 0
1
x
1
g
3 3 2 -3 (6) 0 0 1
0
x
6
2 1 -2 3 -2 0 1 0
B1 P(x) 3 3 2 -3 [6] 0 0 0
0
x
5
6 3 -1/3 0 0 1 0
-3
x
4
½ ½ 1/3 -1/2 1 0 0
0
x
6
3 2 -4/3 (2) 0 0 1
B2 -f(x) -3/2 3/2 -4 [5/2] 0 0 0
0
x
5
6 3 -1/3 0 0 1 0
-3
x
4
5/4 1 0 0 1 0 ¼
-1
x
3
3/2 1 -2/3 1 0 0 ½
B3 -f(x) -21/4 -1 -7/3 0 0 0 -5/4
Vậy bài toán có patu x*= (0, 0, 3/2, 5/4) với fmax=21/4
Bài 11 :
Đưa bài toán về dạng chính tắc ta có :
{
x 1+3 x x2+x 3−4 4−2 x 5=5
2 2x 1+ x 2+2 x 3 4−2 x =2
−2 x 1+x 2+5 x 3− =2 x 4+ x 6 4
xj ≥ 0
(
j=1. .6
)
Xét bài toán phụ :
P(x)=
x
1
g
+x
2
g
→ min
{
x 1+3 x x x2+x 3−4 4−2 5 +x
1
g
=5
2 2x 1+2 x 2+ x 3−2 x 4+x
2
g
=2
−2 x 1+ x 2+5 x 3− =2 4x +x 6 4
xj≥ 0
(
j=1..6
)
; x
1
g
, x
2
g
≥0
Ta có bảng đơn hình :
Hệ số Cơ sở
Phươ
ng 3 2 1 2 0 0 1 1
Án
x
1
x
2
x
3
x
4
x
5
x
6
x
1
g
x
2
g
1
x
1
g
5 1 3 1 -4 -2 0 1 0
1
x
2
g
2 2 (2) 2 -2 0 0 0 1
0
x
6
4 -2 1 5 -2 0 1 0 0
B1 P(x) 7 3 [5] 3 -6 -2 0 0 0
1
x
1
g
2 -2 0 -2 -1 -2 0 1
0
x
2
1 1 1 1 -1 0 0 0
0
x
6
3 -3 0 4 -1 0 1 0
B2 P(x) 2 -2 0 -2 -1 -2 0 0
Vậy bài toán đã cho không giải được.
Bài 12 :
Đưa bài toán về dạng chính tắc ta có :
{
x1+3 x x2+x 3−4 4−2 x 5 10=
2 x 1 4+2 2x 2+ x 3−2 x +2 x5 6+ x =4
− − =4 x 1 4 x2+ +3 x 3+8 4x 4 x 5+x 7 15
xj≥ 0
(
j=1..7
)
Xét bài toán phụ :
P(x)=
x
1
g
→min
{
x 1+3 x x2+x 3−4 4−2 x 5+x
1
g
=10
2 x 1 4+2 2x 2+ x 3−2 x +2 x5 6+ x =4
− − =4 x 1 4 x2+ +3 x 3+8 4x 4 x 5+x 7 15
xj ≥ 0
(
j=1. .7
)
; x
1
g
≥ 0
Ta có bảng đơn hình :
Hệ số Cơ sở
Phươ
ng 3 -1 4 -3 1 0 0 1
Án
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
1
g
1
x
1
g
10 1 3 1 -4 -2 0 0 1
0
x
6
4 2 (2) 2 -2 2 1 0 0
0
x
7
15 -4 -4 3 8 4 0 1 0
B1 P(x) 10 1 [3] 1 -4 -2 0 0 0
1
x
1
g
4 -2 0 -2 -1 -5 -3/2 0 1
0
x
2
2 1 1 1 -1 1 ½ 0 0
0
x
7
23 0 0 7 4 8 2 1 0
B2 P(x) 4 -2 0 -2 -1 -5 -3/2 0 0
Vậy bài toán không giải được.
Bài 13 :
a/Đưa bài toán về dàng chính tắc ta có :
{
3 2x 2 3+2 x − x 4 5+x =72
2 x 1−3 x 3+x 4=60
2 x1−4 x 2 4 36−3 2x3− x =
xj≥ 0
(
j=1..5
)
Xét bài toán phụ :
P(x)=
x
2
g
+x
3
g
→ min
{
3 x 2 3 5+2 x −2x 4 +x =72
2 x 1−3 x 3+x 4 +x
2
g
=60
2 x1 4−4 x 2−3 2x3− x +x
3
g
=36
xj≥ 0
(
j=1..5
)
; x
2
g
, x
3
g
≥0
Ta có bảng đơn hình :
Hệ số Cơ sở
Phươn
g 4 -6 14 -5/2 0 1 1
Án
x
1
x
2
x
3
x
4
x
5
x
2
g
x
3
g
0
x
5
72 0 3 2 -2 1 0 0
1
x
2
g
60 2 0 -3 1 0 1 0
1
x
3
g
36 (2) -4 -3 -2 0 0 1
B1 P(x) 96 [4] -4 -6 -1 0 0 0
0
x
5
72 0 3 2 -2 1 0
1
x
2
g
24 0 (4) 0 3 0 1
0
x
1
18 1 -2 -3/2 -1 0 0
B2 P(x) 24 0 [4] 0 3 0 0
0
x
5
54 0 0 2 -17/4 1
-6
x
2
6 0 1 0 ¾ 0
4
x
1
30 1 0 -3/2 ½ 0
B3 F(x) 84 0 0 -20 0 0
Vậy bài toán có patu x*=( 30, 6,0,0,54)
b/,
∆
4
=0 mà 4 không thu cộ J
0
, nên theo phương
z
4
xây dựng được tập
phương án tối ưu :
x
(
θ
)
=x
¿
+θ . z
4
trong đó :
x
¿
=
{
30,6,0,0,54
}
;
z
4
=
(
−1
2
,−
3
4
,0,1,
17
4
)
v iớ 0 ≤ θ ≤8
Suy ra :
x
(
θ
)
=
{
30,6,0,0,54
}
+
(
−1
2
,−
3
4
, 0,1,
17
4
)
.
θ
v iớ 0 ≤ θ ≤ 8
Theo đề
x
2
=3
↔
6−
3
4
θ=3
=>
θ=4
.
Vậy PATU không cực biên với thành phần x =3 là :
2
x=
(
28, 3,0, 4, 71
)
Bài 14:
a/Đưa bài toán về dạng chính tắc:
{
2 x 1+x 2−x 3 4+ x =20
−x 1− =2 x 2+ +x 4 x 5 16
2 2 2 4x1− x 2 3+x − x +x 6=24
xj ≥0
(
j=1. .6
)
Xét bài toán phụ :
P(x)=
x
1
g
→min
{
2 x 1+x 2−x 3 4+x +x
1
g
=20
−x 1− =2 x 2+ +x 4 x 5 16
2 2 2 4x1− x 2 3+x − x +x 6=24
xj ≥ 0
(
j=1. .6
)
; x
1
g
≥0
Ta có bảng đơn hình:
Hệ số Cơ sở
Phươn
g -2 4 -2 7/2 0 0 1
Án
x
1
x
2
x
3
x
4
x
5
x
6
x
1
g
1
x
1
g
20 (2) 1 -1 1 0 0 1
0
x
5
16 -1 -2 0 1 1 0 0
0
x
6
24 2 -2 1 -2 0 1 0
B1 P(x) 20 [2] 1 -1 1 0 0 0
2
x
1
10 1 1/2 -1/2 1/2 0 0
0
x
5
26 0 -3/2 -1/2 (3/2) 1 0
0
x
6
4 0 -3 2 -3 0 1
B2 -f(x) 20 0 ½ -1/2 [1/2] 0 0
-2
x
1
4/3 1 1 -1/3 0 -1/3 0
7/2
x
4
52/3 0 -1 -1/3 1 (2/3) 0
0
x
6
56 0 -6 1 0 2 1
B3 -f(x) 58 0 -19/2 3/2 0 [3] 0
-2
x
1
10 1 1/2 -1/2 1/2 0 0
0
x
5
26 0 -3/2 -1/2 3/2 1 0
0
x
6
4 0 -3 (2) -3 0 1
B4 -f(x) -20 0 -5 [3] -9/2 0 0
-2
x
1
11 1 -1/4 0 -1/4 0 1/4
0
x
5
27 0 -9/4 0 ¾ 1 ¼
-2
x
3
2 0 -3/2 1 -3/2 0 1/2
B5 -f(x) -26 0 -1/2 0 0 0 -1
Vậy bài toán có patu x*=( 11, 0, 2, 0) với fmax= 26
b/,
∆
4
=0 mà 4 không thu cộ J
0
, nên theo phương
z
4
xây dựng được tập
phương án tối ưu :
x
(
θ
)
=x
¿
+θ . z
4
trong đó :
x
¿
=
{
11,0,2,0,27,0
}
;
z
4
=
(
1
4
, 0,
3
2
,1 ,−
3
4
,0
)
v iớ 0≤ θ ≤ 36
Suy ra :
x
(
θ
)
=¿
{
11,0,2,0,27,0
}
+¿
(
1
4
, 0,
3
2
,1 ,−
3
4
,0
)
.
θ
v iớ 0 ≤ θ ≤36
Theo đề
x
4
=10
↔ 0+θ=10
=>
θ=10
.
Vậy PATU với thành phần x =10 là :
4
x=
(
27
2
, 0,17,10,
39
2
, 0
)
Bài 15:
a/Đưa bài toán về dạng chính tắc ta có:
{
x x1−2 x x2+2 3− 4+x 6 8=
x x1+2 2+x x x3+ 4+ 5 10=
2 x 1 7+x 2−x 3+x =17
xj ≥ 0
(
j=1. .7
)
Ta có bảng đơn hình:
Hệ số Cơ sở
Phươ
ng -2 1 2 2 1 0 0
Án
x
1
x
2
x
3
x
4
x
5
x
6
x
7
0
x
6
8 1 -2 2 -1 0 1 0
1
x
5
10 1 2 1 1 1 0 0
0
x
7
15 (2) 1 -1 0 0 0 1
B1 F(x) 10 [3] 1 -1 -1 0 0 0
0
x
6
1/2 0 -5/2 (5/2) -1 0 1
1
x
5
5/2 0 3/2 3/2 1 1 0
-2
x
1
15/2 1 ½ -1/2 0 0 0
B2 F(x) -25/2 0 -1/2 [1/2] -1 0 0
2
x
3
1/5 0 -1 1 -2/5 0
1
x
5
11/5 0 3 0 8/5 1
-2
x
1
38/5 1 0 0 -1/5 0
B3 F(x) -63/5 0 0 0 -4/5 0
Vậy bài toán có patu x*=( 38/5, 0, 1/5, 0, 11/5) với fmin= -63/5
b/,
∆
2
=0 mà2 không thu cộ J
0
, nên theo phương
z
2
xây dựng được tập
phương án tối ưu :
x
(
θ
)
=x
¿
+θ . z
2
trong đó :
x
¿
=
{
38 /5,0,1 /5,0,11 5/
}
;
z
2
=
(
0,1,1,0 3,−
)
v iớ 0 ≤θ ≤ 11 15/
Suy ra :
x
(
θ
)
=
{
38 5,0,1 5,0,11 5/ / /
}
+
(
0,1,1,0 3,−
)
.
θ
v iớ 0 ≤ θ ≤11 15/
Theo đề
x
2
=1/5
↔θ=1/5
Vậy PATU với thành phần x =1/5 là :
2
x=
(
38
5
,
1
5
,
2
5
, 0,
8
5
)
Bài 16:
a/Đưa bài toán về dạng chính tắc ta có:
{
4 x 1 3 5−3 x 2−x +2 4x +x =34
2 x 1 6−2 x 2+3 x 3+x =60
2 2x1− x 2 32−3 x 3 7+4 x 4−x =
xj ≥ 0
(
j=1. .7
)
Xét bài toán phụ :
P(x)=
x
3
g
→min
{
4 x 1 5 34−3 2x 2 3−x + x 4+x =
2 x 1 60−2 x 2 3 6+3 x + x =
2 2x1− x 2−3 x 3+4 x 4−x 7 +x
3
g
=32
xj ≥ 0
(
j=1. .7
)
; x
3
g
≥0
Ta có bảng đơn hình:
Hệ số Cơ sở
Phươ
ng -3 1 -3 2 0 0 0 1
Án
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
3
g
0
x
5
34 4 -3 -1 2 1 0 0 0
0
x
6
60 2 -2 3 0 0 1 0 0
1
x
3
g
32 2 -2 -3 (4) 0 0 -1 1
B1 P(x) 32 2 -2 -3 [4] 0 0 -1 0
0
x
5
18 (3) -2 ½ 0 1 0 1/2
0
x
6
60 2 -2 3 0 0 1 0
2
x
4
8 ½ -1/2 -3/4 1 0 0 -1/4
B2 -f(x) 16 [4] -2 3/2 0 0 0 -1/2
-3
x
1
6 1 -2/3 1/6 0 1/3 0 1/6
0
x
6
48 0 -2/3 8/3 0 -2/3 1 -1/3
2
x
4
5 0 -1/6 -5/6 1 -1/6 0 -1/3
B3 -f(x) -8 0 2/3 5/6 0 -4/3 0 -7/6
Ta có : Ta có:
{
∆ 2 3=2/
Xj2 ≤ 0
Bài toán không giải được
Vậy bài toán không giải được
b/ Ta có : f(x)
≤18 nên f= −¿
(
x
)
≥−18
Ta suy ra phương án x là tối ưu khi –f(x) = -18
Từ bảng đơn hình thứ 3 ta có phương án cực biên x* = ( 6, 0, 0, 5, 0,
48, 0) với
–f(x*) = -8 và phương
z
2
=
(
2
3
,1, 0,
1
6
, 0,
2
3
,0
)
v à ∆
2=
2
3
l à p hư ơng gi ảm v ô hạ n
Suy ra :
x
(
θ
)
=
(
6, 0,0, 5, 0, 48, 0
)
+
(
2
3
,1, 0,
1
6
, 0,
2
3
,0
)
.
θ
;
θ ≥ 0
là các
phương án của bài toán
Ta có –f(x(
x∗¿
¿
θ ¿¿=−f ¿
=>
θ=15
Vậy patu cần tìm là x’ =( 16, 15,0, 15/2)
Bài 17 :
a/Đưa bài toán về dạng chính tắc ta có :
Xét bài toán phụ :
P(x)=
x
1
g
→min
{
x x1−2 x x2+2 3− 4+x
1
g
=12
2 x 2 3+x + x 4 +x 5=10
5
2
. x 1+x 2− x 3+x 6=15
xj≥ 0
(
j=1..6
)
; x
1
g
≥ 0
Ta có bảng đơn hình :
Hệ số Cơ sở
Phươ
ng -2 1 2 3/2 1 0 1
Án
x
1
x
2
x
3
x
4
x
5
x
6
x
1
g
1
x
1
g
12 1 -2 (2) -1 0 0 1
0
x
5
10 0 2 1 1 1 0 0
0
x
6
15 5/2 1 -1 0 0 1 0
B1 P(x) 12 1 -2 [2] -1 0 0 0
2
x
3
6 ½ -1 1 -1/2 0 0
1
x
5
4 -1/2 3 0 3/2 1 0
0
x
6
21 (3) 0 0 -1/2 0 1
B2 f(x) 16 [5/2] 0 0 -1 0 0
2
x
3
5/2 0 -1 1 -5/12 0 -1/6
1
x
5
15/2 0 3 0
17/1
2 1 1/6
-2
x
1
7 1 0 0 -1/6 0 1/3
B3 F(x) -3/2 0 0 0 -7/12 0 -5/6
Vậy bài toán có patu x* = ( 7, 0, 5/2, 0, 15/2, 0) với fmin = -3/2
b/
∆
2
=0 mà2 không thu cộ J
0
, nên theo phương
z
2
xây dựng được tập
phương án tối ưu :
x
(
θ
)
=x
¿
+θ . z
2
trong đó :
x
¿
=¿
( 7, 0, 5/2, 0, 15/2, 0);
z
2
=
(
0,1,1,0 ,−3, 0
)
v iớ 0 5≤ θ ≤ /2
Suy ra :
x
(
θ
)
=( )7, 0, 5/2, 0, 15 /2, 0
+
(
0,1,1,0 3,−
)
.
θ
v iớ 0 5≤ θ ≤ /2
Theo đề
x
2
=1
↔θ=1
Vậy PATU với thành phần x =1 là :
2
x=
(
7,1,
7
2
, 0,
9
2
, 0
)
Bài 18:
a/ Đưa bài toán về dạng chính tắc ta có:
Xét bài toán phụ :
P(x)=
x
2
g
→min
{
2 x 1 2 5+3 x −4 x 3+x =5
3 x 1 2+2 x −x 3−x 6 +x
2
g
=3
x 1+x x2− 4 +x 7=6
xj≥ 0
(
j=1..7
)
; x
2
g
≥ 0
Ta có bảng đơn hình:
Hệ số Cơ sở
Phươ
ng -1 2 0 1 0 0 0 1
Án
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
2
g
0
x
5
5 2 3 -4 0 1 0 0 0
1
x
2
g
3 (3) 2 -1 0 0 -1 0 1
0
x
7
6 1 1 0 -1 0 0 1 0
B1 P(x) 3 [3] 2 -1 0 0 -1 0 0
0
x
5
3 0 5/3 -10/3 0 1 (2/3) 0
-1
x
1
1 1 2/3 -1/3 0 0 -1/3 0
0
x
7
5 0 1/3 1/3 -1 0 1/3 1
B2 -f(x) -1 0 -8/3 1/3 -1 0 [1/3] 0
0
x
6
9/2 0 5/2 -5 0 3/2 1 0
-1
x
1
5/2 1 3/2 -2 0 1/2 0 0
0
x
7
7/2 0 -1/2 (2) -1 -1/2 0 1
B3 -f(x) -5/2 0 -7/2 [2] -1 -1/2 0 0
0
x
6
53/4 0 5/4 0 -5/2 1/4 1 5/2
-1
x
1
6 1 1 0 -1 0 0 1
0
x
3
7/4 0 -1/4 1 -1/2 -1/4 0 1/2
B4 -f(x) -6 0 -3 0 0 0 0 -1
Vậy bài toán có patu x* = ( 6, 0,7/4,0,0, 53/4) với fmax = 6
∆
4
=0 mà 4 không thu cộ J
0
, nên theo phương
z
4
xây dựng được tập
phương án tối ưu :
x
(
θ
)
=x
¿
+θ . z
4
trong đó :
x
¿
=( )6, 0,7/4,0,0, 53/4
;
z
4
=
(
1, 0
,
1
2
,1, 0,
5
2
)
v iớ 0 ≤θ
Suy ra :
x
(
θ
)
=( )6,0,7 /4,0,0,53 /4
+
(
1, 0
,
1
2
, 1, 0,
5
2
)
.
θ
v iớ 0 ≤ θ
Theo đề
x
4
=10
↔θ=10
Vậy PATU không cực biên với thành phần x =10 là :
4
x=
(
16,0,
27
4
, 10,0,
153
4
)
Bài 19: F(x) = 2x + x -> min
1 2 +
5x
3
3 x 1 9+x 2−x 3≥
(
1
)
x x x1+2 2+ 3 ≤ 5
(
2
)
¿
x x1+2 x 2+2 3 ≥ 3
(
3
)
j=( )1,3
¿
xj≥ 0 ¿
¿
a) Bài toán đốối ngẫẫu
F(y) = 9y + 5y + 3y -> max
1 2 3
¿
3 y1+ y 2−y 3 ≤2
(
1'
)
y 1+2 y 2+2 y3 ≤ 1
(
2 '
)
− y 1+ y2+2 y3 ≤ 5
(
3'
)
y y1 ≥0, 2≤ 0 , y3 ≥ 0
¿
¿
Các c p đốối ngẫẫu : xặ
1
≥ 0↔
(1’)
x
2
≥
0
↔
(2’)
x
1
≥
0
↔
(3’)
(1)
↔
y
1
≥ 0
(2)
↔
y
2
≤ 0
(3)
↔
y
3
≥ 0
b) X
0
= (3,0,0) đốối v i bài toánớ
- Vecto X th a mãn tẫốt c các ràng bu c c a bài toán nên X
0
ỏ ả ộ ủ
0
là:
PA c a bài toán : ủ
{
9 ≥9
3 ≤5
3 ≥3
- PA x th a mãn ch n ràng bu c (1), (3) và x
0
ỏ ặ ộ
2
= 0, x = 0 trong đó có 3 ràng bu (1), (3) và x
3
ộ
3
≥ 0
là đ c l p => x
ộ ậ
0
là PACB suy biêốn
- Gi s xả ử
0
là PATG c a bài toán, do xủ
0
th a mãn ràng bu c (2), xỏ ộ
1
= 3 > 0 nên m i ph ng án tốốiọ ươ
u c a bài toán đốối ngẫẫu (nêốu có) ph i th a mãn yư ủ ả ỏ
2
≤ 0
và (1’)
T c là th a mãn h ph ng trình sauứ ỏ ệ ươ
{
y 2=0
3 y 1+ y 2 2+ y 3=
{
y 2=0
y 3=2−3 y 1
HPT trên có nghi m t ng quát là y = (yệ ổ
1
, 0, 2-3y )
1
Y
1
ϵ R .
Th các nghi m này vào các ràng bu c còn l i c a bài toán đốối ngẫẫu, ta có:ử ệ ộ ạ ủ
(2’) y + 2(2-3y1)
1
≤
1 y
1
≥
3
5
(3’) -y + 2(2-3y1)
1
≤
5 y
1
≥
−
1
7
y
1
≥
0
y
3
≥
0 y
1
≤
2
3
(
y= −2 3 y1 ≥ 0
→ y
1 ≤
2
3
)
Vecto y = (y
1,
(
y y
1
,0,2−3
1
)
Tm tẫốt c các ràng bu c c a bài toán đốối ngẫẫu khi ả ộ ủ
3
5
≤ y1 ≤
2
3
Nên x là ph ng án tốối u c a bài toàn dã cho
0
ươ ư ủ
- T p ph ng án tốối u c a bài toán đốối ngẫẫu ậ ươ ư ủ
Y =
{
y=
(
y
1
, 0,2−3 y
)
|
,
(
3
5
≤ y 1 ≤2/3)
Bài toán đốối ngẫẫu có 2 PACB tốối u là:ư
- Khi
y
1=
3
5
ta có PACB y =(
1
3
5
, 0,
1
5
¿
- Khi y =
1
2
3
ta có PACB y
2
(
2
3
, 0,0
)
Bài 20:
a)
f
(
x
)
=4 x 1+12 x 2−16 x 3 →min
{
x 1−3 x 3 ≥−6
(
1
'
)
x 1+3 x x2−4 3 ≥−2
(
2
'
)
x 2−x 3 ≤ 4 (3
'
)
f
(
y
)
=−6 y 1−2 y 2+4 y 3 → max
{
y 1+ y 2=4
(
1
'
)
−3 y 1+ y 2+ y 3=12(2
'
)
−4 y 2− y 3=−16
(
3
'
)
y 1 ≥0 , y , y2≥ 0 3≤ 0
C p ràng bu c đốối ngẫẫuặ ộ
y 1 ≥ 0 ↔
(
1
)
y 2 ≥ 0 ↔
(
2
)
y 3 ≤ 0 ↔
(
3
)
b) Vecto
x=(− )1,1,1
Thay Vecto x vào bài toán ban đẫầu:
{
−4 ≥−6
−2 ≥−2
0≤ 4
Vecto x = (-1,1,1) là ph ng án, x th a mãn ch t ràng bu c (2) nên x khống là ph ng án CBươ ỏ ặ ộ ươ
Gi s X là ph ng án tốối u, X th a mãn l ng ràng bu c (1), (3) thì m i ph ng án tốối u y c a bài ả ử ươ ư ỏ ỏ ộ ọ ươ ư ủ
toán đốối ngẫẫu ph i th a mãnả ỏ
{
y y1=0→ 2=4=¿ y=( )0,4,0
y3=0
Y
0
th a mãn tẫốt c rằầng bu c c a bài toán đốối ngẫẫu nên x là ph ng án tốối uỏ ả ộ ủ ươ ư
Bài 21:
f
(
x
)
=x 1+4 x 2+ px 3→ max
a)
f
(
y
)
=10 y 1− y 2 →min
{
3 y1 1− y 2 ≥ (1
'
)
4 y1 4+ y 2 ≥ (2
'
)
4 y 1+ y 2 ≥ p (3
'
)
Hai bài toán có c p ràng bu c đốối ngẫẫuặ ộ
x 1 ≥ 0↔(1 ')
x 2 ≥ 0↔(2')
x 3 ≥ 0 ↔(3 ')
b) Thay vecto X = (2,1,0) vào bài toán gốốc
{
10 10=
−1=−1
Ta thẫốy x th a mãn bài toán gốốcỏ
X là ph ng án c a bài toán gốốc ươ ủ
G a s x là patu c a bài toán gốốcỉ ử ủ
Ta thẫốy x th a mãn l ng 2 rb vêầ dẫốu nên theo đ nh lí 2 đốối ngẫẫu ta có h :ỏ ỏ ị ệ
{
3 y 1 2 1− y =
4
y 1+ y 2=4
→ y (
5
7
,
8
7
)
Thay y vào các rb còn l c a bài toán đn thẫốy th a mãn nên suy y là patu.ạ ủ ỏ
Đ y là patu khống suy biêốn thì (3’) ể 4y1 + y2 > p p<4
Theo đ nh lí 1 ta suy ra x là patu c a bài toán.ị ủ
V i p< 4, PACBTU duy nhẫốt y’ = ớ
(
5
7
,
8
7
)
th a mãn l ng ỏ ỏ (3’) => PATU c a bài toán gốốc th a mãn ủ ỏ
{
3 4x 1+ x 2 3+4 x =10
−x 1+x 2+x 3=−1
x 3 0=
->
{
x 1=2
x 2=1
x 3=0
Đẫy là PACBTU duy nhẫốt c a bài toán gốốcủ
Bài 22
f
(
x
)
=6 x 1+ +3 x 2 x3+2 x 4 → min
− −x 1 3 x 2+2 x 3+5 x 4 ≥−16 (1)
¿∗¿
¿
3 4x1 2+x − x 3 10−x 5 ≤
(
2
)
¿
¿
7 x 1+3 x3 4−2 x =0 ¿
¿
Bài toán đốối ngẫẫu
f
(
y
)
=−16 y 1+10 y 3−2 y 4 → max
{
− y 1+ +7 y 2+3 y 3 2 y 4 ≤ 6(1
'
)
−3 y 1+ y 3+2 y 4 ≤ 3(2
'
)
2 y 1 2 1+3 y −4 y 3 ≤
(
3
'
)
5 y 1 2 2−2 y −6 y 4 ≤
(
4
'
)
− y 3 ≤ 0(5
'
)
y 1 ≥ ≤0 , y 3 0 , y 4 ≤ 0
Bài toán có 8 c p ràng bu c đốối ngẫẫy (i) (-) (i’) v i i=(1,….,8)ặ ộ ớ
Gi i bài toán gốốc bằầng ph ng pháp đ n hìnhả ươ ơ
P = x2 + x4 => min
y y
{
x x x1+3 x 2−2 x 3−5 4+ 6 16=
7 2x 1 3+3 x − x 4+x
2
y
=0
3 x 1 2 10+ x −4 x 3 7−x 5+ x =
− −2 x 1 2 x 2+6 x 4−x 8+x
4
y
=2
xj ≥ 0( j=1,8)
HS CS PA 6 3 1 2 0 0 0 0 1 1
X1 X2 X3 X4 X5 X6 X7 X8
x
2
y
x
4
y
0 X6 16 1 3 -2 -5 0 1 0 0 0 0
1
x
2
y
0 (7) 0 3 -2 0 0 0 0 1 0
0 X7 10 3 1 -4 0 -1 0 1 0 0 0
1
x
4
y
2 -2 -2 0 6 0 0 0 -1 0 1
P 2 [5] -2 3 4 0 0 0 -1 0 0
0 X6 16 0 3 -17/7 -33/7 0 1 0 0 0
0 X1 0 1 0 3/7 -2/7 0 0 0 0 0
0 X7 10 0 1 -37/7 6/7 -1 0 1 0 0
1
x
4
y
2 0 -2 6/7 (38/7) 0 0 0 -1 1
P 2 0 -2 6/7 [38/7] 0 0 -1 0
0 X6 337/19 0 24/19 -32/19 0 0 1 0 -33/38
6 X1 2/19 1 -2/19 (9/19) 0 0 0 0 -1/19
0 X7 184/19 0 25/19 -
103/19
0 -1 0 1 3/19
2 X4 7/19 0 -7/19 3/19 1 0 0 0 -7/38
F(x) 26/19 0 -83/19 [41/19] 0 0 0 0 -13/19
0 X6 163/9 32/9 8/9 0 0 0 1 0 -19/18
1 X3 2/9 19/9 -2/9 1 0 0 0 0 -1/9
0 X7 98/9 103/9 1/9 0 0 -1 0 1 -4/9
2 X4 1/3 -1/3 -1/3 0 1 0 0 0 -1/6
F(x) 8/9 -41/9 -35/9 0 0 0 0 0 -4/9
T b ng ta có ừ ả
∆ k ≤ 0 ∀k ∈ J .
Nên bài toán đã cho có ph ng án tốối u x* =ươ ư
¿
8
9
(
0,0,
2
9
,
1
3
, 0,
163
9
.
98
8
, 0)và f
(
x
)
min ¿¿
b) X* là ph ng án tốối u c a bài toán gốốc ươ ư ủ
X
¿
=( 0,0,
2
9
,
1
3
,0,
163
9
.
98
8
, 0)
Thay X* vào bài toán gốốc
−x 1−3 x 2+2 x 3+5 x 4 ≥−16
(
1
)
¿∗¿
¿
¿
¿3 x 1 5+x 2 3−4 x −x ≤ 10
(
2
)
7 x 1 3+3 x −2 x 4=0
(
¿2 6x 1+2 x 2− x 4 ≤−2
(
3
)
¿
(
¿
)
{
13
9
≥−16
0=0
−8
9
≤ 10
−3 ≤−2
¿
X* th a mãn rằầng bu c l ng (1), (2), (3) thì m i ph ng án tốối u c a bài toán đốối ngẫẫu ph i th aỏ ộ ỏ ọ ươ ư ủ ả ỏ
mãn
{
y 1 0=
y 3 0=
y 4=0
→ y
2=
6
7
Y* = (0,
6
7
,0,0)
X* th a mãn ch t ràng bu c (**) nên X* khống là PACB ỏ ặ ộ
Y* khống là PACB nh ng là PATU và PACBTUư
Bài 23
f
(
x
)
=18 x 1+13 x 2+5 x 3→ min
{
x
1+x 2≥−
1
3
(
1
)
3 2x 1+5 x ≥2
(
2
)
3 3 3x 1+ x ≥2
(
3
)
x
1+2 x 2 ≥−
1
3
(
4
)
9 3x 1+8 x 2+x ≥ 6
(
5
)
Ta có bài toán đốối ngẫẫu
f
(
y
)
=
−1
3
y1 2+2 y +2 y 3−
1
3
y 4 +6 y5 → max
{
y 1+3 y y y2+3 y 3+ 4 +9 5 18= (1
'
)
y y y y1+5 2+2 4+8 5 2=13 (
'
)
3 y3+ y 5 5= (3
'
)
Các ràng bu c c p ộ ặ
y 1 ≥ 0
(
¿
)
(
1
)
y 2 ≥ 0 ↔
(
2
)
y 3 ≥ 0 ↔
(
3
)
y 4 ≥ 0 ↔
(
4
)
y 5 ≥ 0 ↔
(
5
)
a) Vecto
x=
(
2
3
, 0,0
)
Thay vecto X vào bài toán gốốc
{
2
3
≥−
1
3
(
1
)
2 ≥ 2
(
2
)
2 ≥ 2
(
3
)
2
3
≥−
1
3
(
4
)
6 ≥ 6
(
5
)
Vecto X th a mãn tẫốt c các ràng bu c:ỏ ả ộ
PA X th a mãn ch t (2), (3), (5)ỏ ặ
PA X th a mãn l ng (1), (4)ỏ ỏ
X là PACB khống suy biêốn
- Gi s X là PATU và th a mãn l ng (1), (4) nên m i PATU c a bài toán đ ng nhiên th aả ử ỏ ỏ ọ ủ ươ ỏ
mãn.
¿
y 1= y 4=0
3 3 9y2+ y 3+ y 5=18
5 y 2 13+ 8 y5=
3 y 3 5+ y =5
¿
¿
→ y∗¿
(
0,0,
9
8
,0,
13
8
)
Y
0
th a mãn tẫốt c các ràng bu c c a bài toán => yỏ ả ộ ủ
o
là patu c a bài toánủ
Nên theo đ nh lí1 đốối ngẫẫu thì x = ị
(
2
3
, 0,0
)
là PATU c aủ bài toán g cố
b) T p PATU c a BTĐN ậ ủ
y=
{
y
0
=
(
0,0,
9
8
, 0,
13
8
)
}
Y
0
th a mãn ch t 3 rb chính và 3 rb vêầ dẫốu => yỏ ặ
0
là patu c c biên suy biêốn c a bài toán.ự ủ
c/ Tìm tẫp ph ng án tốối u c a bài toán gốốc.ươ ư ủ
PATU Y c a BTĐN th a mãn l ng y
0
ủ ỏ ỏ
3
≥ ≥0, y 5 0
M i PATU c a bài toán gốốc th a mãnọ ủ ỏ
{
3 x 1 3 2+3 x =
9
x 1+8 x 2 3+x =6
→
{
x
1=
2
3
−x 3
x 2=x 3
→ x=
(
2
3
−x 3 3, x , x 3
)
Các PATU c a bài toán gốốc ph i th a mãn các ràng bu c còn l i ủ ả ỏ ộ ạ
Thay
x=
(
2
3
−x 3 , x , x3 3
)
vào các ràng bu cộ còn l iạ ta đ cư ợ x 3≥ 0
V y t p PATU c a bài toán gốốc là ậ ậ ủ
2
3
−x 3 3, x , x 3
x=
{
¿v iớ x 3≥ 0
}
Bài 24:
a/Bài toán đối ngẫu:
g(y) = 20.y + 16.y max
1 2
{
y1 ≤ 1
(
1
)
2 y 1 2+ y ≤ 1
(
2
)
2 y 1 1−2 y 2=
(
3
)
−3 y 1+2 y2=2
(
4
)
y1 ≤0
(
5
)
y 2 tùy ý
(
6
)
Các cặp ràng buộc đối ngẫu:
x
1
≥ 0 ↔
(
1
)
x
2
≥ 0 ↔
(
2
)
x x1+2 x 2+2 3−3 x 4 ≤20 ↔
(
5
)
Ta có từ (3) và (4) suy
ra
{
y 1=−3
y
2=
−7
2
=> y* =( -3, -7/2)
Thay y* vào các ràng buộc còn lại của bài toán đối ngẫu thấy thõa
mãn nên suy ra y* là phương án tối ưu của bài toán
Nên theo định lí 1 Đối Ngẫu thì suy ra bài toán gốc giải được.
Ta thấy y* thõa mãn lỏng ràng buộc (1), (2),(5) nên theo định lí 2 Đối
Ngẫu thì bài toán gốc có patu x* thỏa mãn chặt các ràng buộc tương
ứng nên ta có hệ :
{
x 1 0=
x 2 0=
x x x x1+2 2+2 3−3 4=20
x 2−2 x 3+2 x 4=16
{
x 1 =0
x 2 =0
x 3=−44
x 4=−36
=> x* = (0, 0, -44, -36) là phương án cực biên tối ưu của bài toán
gốc.
Bài 25 :
a/Bài toán đối ngẫu :
g(y) = 3y + y + 2y min
1 2 3
{
− y 1+ y 2+2 y 3 3≥ (1)
y 1−2 y 2=1 2( )
2 y 1+3 y2+ y 3 ≤−2 3( )
y 1≤ 0 (4)
y 2 ≤ 0(5)
y 3 ≤ 0(6)
Các cặp ràng buộc đối ngẫu:
x
1
≥ 0 ↔
(
1
)
x
3
≥ 0 ↔
(
3
)
−x 1+ x 2+2 3x 3≥ ↔
(
4
)
x 1−2 x 2+3 x 3 ≥1 ↔(5)
2 3x 1+x ≥ 2↔(6)
b/ Từ (2) suy ra y1 = 1+ 2y2 thay vào (1) và (3) ta được :
{
− y 2+2 y 3≥ 4
7 y2+ y 3 ≤−4
Nhân cả 2 vế của bpt số 1 với 7, nhân cả 2 vế của bpt số 2 với -1,
sau đó cộng 2 bất phương trình lại ta được: y3
≥
32
13
Mâu thuẫn với đề bài nên suy ra bài toán đối ngẫu không giải được.
Bài 26:
a/ Bài toán đối ngẫu:
g(y) = 7y1 – 4y2 + 5y3 max
{
y y1−2 y 2+3 3 ≤−8
(
1
)
y 2− y 3 ≤ 6
(
2
)
−2 y 1− y 2+2 y3=4
(
3
)
y 1+3 y y2−6 3 ≤5
(
4
)
y 1≤ 0
(
5
)
y2 tùy ý
y3 ≥ 0
(
6
)
Các cặp ràng buộc đối ngẫu:
x
1
≥ 0 ↔
(
1
)
x
2
≥ 0 ↔
(
2
)
x 4 ≥ 0(4 )
x1−2 x 3+x 4 ≤7 ↔
(
5
)
3 x 1 3−x 2+2 x −6 x 4 5≥ ↔(6)
b/ Thay x vào các ràng buộc của bài toán thấy thỏa mãn nên suy ra
o
x
o
là phương án của bài toán.
Ta thấy x thỏa mãn chặt 3 ràng buộc chính và 2 ràng buộc về dấu
o
nên x là phương án cực biên tối ưu suy biến của bài toán.
o
c/ Ta thấy x thỏa mãn lỏng ràng buộc về dấu: x =3
0
1
≥ 0
nên bài
toán đối ngẫu pải chặt ràng buộc tương ứng suy ra ta có hệ:
{
y y1−2 y 2+3 3=−8
−2 y 1− y 2+2 y 3=4
{
y 1
y y2=8 1+28
y y3=5 1+16
=> y* = ( y1, 8y1+28, 5y1 +16) vào các ràng buộc còn lại của bài
toán đối ngẫu ta được điều kiện:
−16
5
≤ y1 ≤−2
=> y* là tập phương án tối ưu của bài toán đối ngẫu
Phương án có thành phần y1 = -3 là y’ = (-3, 4, 1)
Bài 27 :
a/Bài toán đối ngẫu :
g(y) = -10y1 +3y2 +5y3 max
{
2 y1 2− y =−4
− y1+3 y 2+ 2 y 3=1
y 2+2 y 3=−4
4 y 1 3+2 y2− y =3
− =5 y1+ y 3 2
y 1≤ 0(1)
y 2≥ 0(2)
y3 ≤ 0(3)
Các cặp ràng buộc đối ngẫu:
2 x
1
−x 2+4 x 4 5−5 y ≤−10 ↔
(
1
)
−x 1+ +3 x
2
+x 3 2 x 4 3≥ ↔
(
2
)
2x2+2x3-
x x4+ 5≤ 5(3)
b/ Tập phương án tối ưu của bài toán đối ngẫu là: y* = (-1, 2,-3)
Bài 28:
a/ Bài toán đối ngẫu:
g(y)= -27y1 -4y2 +17y3 max
{
−2 y 1+ +y 2 y 3 ≤−2
(
1
)
y y1−2 y 2+3 3 ≤19
(
2
)
−y 1−2 y 2+ y 3 ≤5
(
3
)
3 y1− y3 ≤ 3
(
4
)
2 y1 2+3 y ≤ 1
(
5
)
y1 ≥ 0
(
6
)
y2 ≤ 0
(
7
)
y3 ≥ 0
(
8
)
Các cặp ràng buộc đối ngẫu:
x1 ≥ 0↔
(
1
)
x2 ≥ 0↔
(
2
)
x3 ≥ 0 ↔
(
3
)
x 4 ≥ 0↔
(
4
)
x 5 ≥ 0 ↔
(
5
)
−2 x 1+x 2− x 3+3 x 4+2 x5 ≥−27 ↔(6)
x x1−2 x 2−2 x 3+3 5 ≤−4 ↔(7)
x 1+3 x 2+x 3−x 4 ≥ 17 ↔
(
8
)
b/ Thay y vào các ràng buộc của bài toán đối ngẫu => y là phương
án của bài toán
Ta thấy y thỏa mãn chặt ràng buộc(1) và(3) nên suy ra y là phương
án tối ưu không cực biên
c/ Đưa bài toán về dạng chính tắc ta có:
{
2 x1 2 4 5 6−x +x 3−3 x −2 x +x =27
−x 1+2 x2+2 x 3− − =3 x 5 x 7 4
x x1+3 x 2+ 3−x4−x 8=17
x
j
≥ 0
(
j=1. .8
)
Xét bài toán phụ:
P(x) =
x
2
g
+x
3
g
→ min
{
2 x 1 2 4 5 6−x + x 3−3 x −2 x +x =27
−x 1 +2 x 2+2 x 3−3 x 5−x 7 +x
2
g
=4
x x x1+3 2+ 3−x 4 −x 8+x
3
g
=17
x
j
≥ 0
(
j=1..8
)
; x
2
g
, x
3
g
≥ 0
Ta có bảng đơn hình:
Hệ số Cơ sở
Phương -2 19 5 3 1 0 0 0 1 1
án
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
2
g
x
3
g
0
x
6
27 2 -1 1 -3 -2 1 0 0 0 0
1
x
2
g
4 -1 (2) 2 0 -3 0 -1 0 1 0
1
x
3
g
17 1 3 1 -1 0 0 0 -1 0 1
Bảng 1 P(x) 21 0 [5] 3 -1 -3 0 -1 -1 0 0
0
x
6
29
3 2
/
0 2 -3
−7 2
/
1
−1 2
/
0 || 0
0
x
2
2
−1/2
1 1 0
−3 2
/
0
−1 2
/
0 || 0
1
x
3
g
11
5/2
0 -2 -1
(9
/
2)
0
3 2
/
-1 || 1
Bảng 2 P(x) 11
5 2
/
0 -2 -1
[9
/
2]
0
3
/
2
-1 || 0
0
x
6
338
/
9
31/9
0
4
/
9
−34 9
/
0 1
2 3
/
−7 9
/
19
x
2
17
/
3
1
/
3
1
1
/
3
−1 3
/
0 0 0
−1 3
/
1
x
5
22
/
9
(5
/
9)
0
−4
/
9
−2/9
1 0
1 3
/
−2 9
/
Bảng3 f(x)
991
/
9
[80
/
9]
0
8 9
/
−86 9
/
0 0
1 3
/
−59 9
/
0
x
6
112 5
/
0 0
16 5
/
−12 5
/
5 −31
/
1
−7 5
/
3 5
/
19
x
2
21 5
/
0 1
(3
/
5)
−1
/
5 −3/5
0
−1
/
5
−1
/
5
-2
x
1
22 5
/
1 0
−4
/
5
−2
/
5
9
/
5
0
3
/
5
−2 5
/
Bảng 4 f(x) 71 0 0 [8] -6 -16 0 -5 -3
0
x
6
0 0
−16 3
/
0
−4 3
/
-3 1
−1 3
/
5 3
/
3
x
3
7 0
5 3
/
1
−1 3
/
-1 0 -3 -3
-2
x
1
10 1
4 3
/
0
−2 3
/
1 0
1
/
3
−2 3
/
Bảng 5 f(x) 1 0
−50 3
/
0
−8 3
/
-6 0
−29
/
3
−23 3
/
Vậy bài toán có patu x* = ( 10, 0, 7, 0, 0) với fmin = 1
d/ Ta thấy x* thỏa lỏng 2 ràng buộc về dấu nên theo định lí 2 đối
ngẫu thì bài toán đối ngẫu có pa y* thỏa mãn chặt các ràng buộc
tương ứng nên ta có hệ :
{
−2 y 1+ y 2+ y3=−2
− y 1− =2 y 2+ y 3 5
=> y* = (3y2+7, y2, 5y2 + 12) với
−7
3
≤ y2 ≤
3
2
Bài 29:
Đưa bài toán về dạng chính tắc:
{
3 x 1+2 x 2 72−2 x 3+x 5=
−3 x 2+ +x 3 2 x 4=60
− − =4 x 1 3 x 2−2 x 3+2 x 4 36
x
j
≥ 0
(
j=1..5
)
Xét bài toán phụ:
P(x) =
x
2
g
+ x
3
g
→ min
{
3 2x 1+ x 2 72−2 x 3+x 5=
−3 x 2+ + +x 3 2 4x x
2
g
=60
− −4 x 1 3 x 2−2 x 3+2 x 4 +x
3
g
=36
x
j
≥ 0
(
j=1. .5
)
; x
2
g
, x
3
g
≥ 0
Ta có bảng đơn hình:
Hệ số Cơ sở
Phươ
ng -6 14 -5/2 4 0 1 1
Án
x
1
x
2
x
3
x
4
x
5
x
2
g
x
3
g
0
x
5
72 3 2 -2 0 1 0 0
1
x
2
g
60 0 -3 1 2 0 1 0
1
x
3
g
36 -4 -3 -2 (2) 0 0 1
B1 P(x) 96 -4 -6 -1 [4] 0 0 0
0
x
5
72 3 2 -2 0 1 0
1
x
2
g
24 (4) 0 3 0 0 1
0
x
4
18 -2 -3/2 -1 1 0 0
B2 P(x) 24 [4] 0 3 0 0 0
0
x
5
54 0 2 -17/4 0 1
-6
x
1
6 1 0 3/4 0 0
4
x
4
30 0 -3/2 1/2 1 0
B3 F(x) 84 0 -20 0 0 0
Vậy bài toán có patu x* =( 6, 0, 0, 30, 54) với fmin = 84
b/ Thay x vào các ràng buộc của bài tóan thấy thỏa mãn nên x là
o o
phương án của bài toán.
Ta thấy x thỏa mãn chặt 2 ràng buộc chính và 1ràng buộc về dấu,
o
ta có hệ :
¿
− =3 x 2+x 3+2 x 4 60
− − − =4 x 1 3 x 2 2 x 3+2 x 4 36
x 2=0
¿
¿
=> x là phương án tối ưu không cực biên của bài toán
0
c/ Bài toán đối ngẫu:
g(y)= 72y1 +60y2 +36y3 max
{
3 y1−4 y 3 ≤−6 (1)
2 y 1 2−3 y −3 y 3 ≤14 (2)
− −
2 y 1+ y 2 2 y 3 ≤−
5
2
(3)
2 y 2+2 y3 4≤ (4 )
y 1 ≤ 0(5)
Các cặp ràng buộc đối ngẫu:
x1 ≥ 0↔
(
1
)
x2 ≥ 0↔
(
2
)
x3 ≥ 0 ↔
(
3
)
x 4 ≥ 0↔
(
4
)
3 2x1+2 x 2− x 3 ≤ 72↔
(
5
)
Ta có x thỏa mãn lỏng ràng buộc về dấu và 1 ràng buộc chính nên
o
theo định lí 2 đối ngẫu thì bài toán đối ngẫu có pa y* thỏa mãn chặt
các rb tương ứng, ta có hệ:
{
y 1 0=
−3 y 1−4 y 3=−6
2 2y 2+ y 3=4
{
y 1 0=
y 2=
1
2
y
3=
3
2
=> y* = (0, ½, 3/2 ) là tập phương án tối ưu của bài toán đối ngẫu.
Ta thấy y* thỏa mãn chặt 1 ràng về dấu và 3 ràng buộc chính nên y*
là phương án cực biên suy biến duy nhất của bài toán đối ngẫu.

Tài liệu khác của Học viện Ngân hàng

Preview text:

BÀI TẬP CHƯƠNG 4 Bài 1: Ta có bảng đơn hình: Phươ Hệ số Cơ sở ng 1 3 3 -3 -1 0 Án x x x x x x 1 2 3 4 5 6 1 x 4 1 4 -1 -1 0 0 1 -1 x 4 0 2 2 1 1 0 5 0 x 3 0 1 2 (2) 0 1 6 B1 f(x) 0 0 -1 -2 [1] 0 0 1 x 11/2 1 9/2 0 0 0 ½ 1 -1 x 5/2 0 3/2 1 0 1 -1/2 5 -3 x 3/2 0 ½ 1 1 0 ½ 4 B2 f(x) -3/2 0 -3/2 -7 0 0 -1/2
Vậy bài toán có phương án cực biên tối ưu x* = ( 11/2, 0, 0, 3/2, 5/2, 0 ) với fmin= -3/2 Bài 2: Ta có bảng đơn hình: Phươ Hệ số Cơ sở ng 1 3 5 2 3 3 Án x x x x x x 1 2 3 4 5 6 3 x 3 1 1 1 1 0 0 2 3 x 2 (2) 0 3 -2 1 0 5 3 x 3 1 0 1 3 0 1 6 B1 F(x) 24 [11] 0 10 4 0 0 3 x 2 0 1 -1/2 2 -1/2 0 2 1 x 1 1 0 3/2 -1 1/2 0 1 3 x 2 0 0 -1/2 (4) -1/2 1 6 B2 F(x) 13 0 0 -13/2 [15] -11/2 0 3 x 1 0 1 -1/4 0 -1/4 -1/2 2 1 x 3/2 1 0 11/8 0 3/8 1/4 1 2 x 1/2 0 0 -1/8 1 -1/8 1/4 4 B3 F(x) 11/2 0 0 -37/8 0 -29/8 -15/4
Vậy bài toán có phương án cực biên tối ưu x* = ( 3/2, 1, 0, ½, 0, 0 ) với fmin = 11/2 Bài 3: Ta có bảng đơn hình: Phươ Hệ số Cơ sở ng 0 -2 2 2 -2 1 Án x x x x x x 1 2 3 4 5 6 -2 x 5 1 1 5 0 1 0 2 2 x 2 (2) 0 3 1 -2 0 4 1 x 5 1 0 1 0 3 1 6 B1 F(x) -1 [3] 0 -5 0 -1 0 -2 x 4 0 1 7/2 -1/2 2 0 2 0 x 1 1 0 3/2 ½ -1 0 1 1 x 4 0 0 -1/2 -1/2 (4) 1 6 B2 F(x) -4 0 0 -19/2 -3/2 [2] 0 -2 x 2 0 1 15/4 -1/4 0 -1/2 2 0 x 2 1 0 11/8 3/8 0 ¼ 1 -2 x 1 0 0 -1/8 -1/8 1 ¼ 5 B3 F(x) -6 0 0 -37/4 -5/4 0 -1/2
Vậy bài toán có phương án tối ưu x*= ( 2, 2, 0, 0, 1, 0 ) với fmin= -6 Bài 4:
Đưa bài toán về dạng chính tắc ta có:
{2x1−x2+x3−5x4=5
3 x 1−3 x 3+6 x 4=3
2 x 1−x 2−x 4 + x 5=2
xj≥ 0( j=1. .5) Xét bài toán phụ:
P(x) = xg+xg →min 1 2
{2x1−x2+x3−5x4+xg=51
3 x 1−3 x 3+6 x 4+ xg=3 2
2 x 1− x 2−x 4+ x 5= 2 xj ≥ g g
0 ( j=1. .5) ; x , x ≥ 0 1 2 Ta có bảng đơn hình: Phươn Hệ số Cơ sở g 1 1 1 3 0 1 1 Án x x x x x xg xg 1 2 3 4 5 1 2 1 xg 5 2 -1 1 -5 0 1 0 1 1 xg 3 (3) 0 -3 6 0 0 1 2 0 x 2 2 -1 0 -1 1 0 0 5 B1 P(x) 8 [5] -1 -2 1 0 0 0 1 xg 3 0 -1 3 -9 0 1 1 0 x 1 1 0 -1 2 0 0 1 0 x 0 0 -1 (2) -5 1 0 5 B2 P(x) 3 0 -1 [3] -9 0 0 1 xg 3 0 (½) 0 -3/2 -3/2 1 1 0 x 1 1 -1/2 0 -1/2 ½ 0 1 0 x 0 0 -1/2 1 -5/2 ½ 0 3 B3 P(x) 3 0 [½] 0 -3/2 -3/2 0 1 x 6 0 1 0 -3 -3 2 1 x 4 1 0 0 -2 -1 1 1 x 3 0 0 1 -4 -1 3 B4 F(x) 13 0 0 0 -12 -5
Vậy bài toán có patu x*=( 4,6,3,0) với fmin= 13 Bài 5:
Đưa bài toán về dạng chính tắc ta có:
{3x1−x2−x3+x4=4
x 1−x 2+ x 3+ x 4+ x 5=1
2 x 1+ x 2+2 x 3+ x 6=6
xj ≥ 0( j=1..6) Xét bài toán phụ:
P(x) = xg1 →min
{3x1−x2−x3+x4+xg=41
x 1−x 2+ x 3+ x 4 + x 5=1
2 x 1+ x 2+2 x 3+ x 6=6
xj ≥ 0 ( j=1. .6) , xg≥ 0 1 Ta có bảng đơn hình: Phươn Hệ số Cơ sở g -5 1 -1 -4 0 0 1 Án x x x x x x xg 1 2 3 4 5 6 1 1 xg 4 3 -1 -1 1 0 0 1 1 0 x 1 (1) -1 1 1 1 0 0 5 0 x 6 2 1 2 0 0 1 0 6 B1 P(x) 4 [3] -1 -1 1 0 0 0 1 xg 1 0 (2) -4 -2 -3 0 1 1 0 x 1 1 -1 1 1 1 0 0 1 0 x 4 0 3 0 -2 -2 1 0 6 B2 P(x) 1 0 [2] -4 -2 -3 0 0 1 x 1/2 0 1 -2 -1 -3/2 0 2 -5 x 3/2 1 0 -1 0 -1/2 0 1 0 x 5/2 0 0 6 1 5/2 1 6 B3 F(x) -7 0 0 4 3 1 0
Vậy bài toán có patu x*= ( 3/2, ½, 0, 0) với fmax= -7 Bài 6 :
Đưa bài toán về dạng chính tắc ta có :
{2x1+5x2−x3−4x4−2x5=6
2 x 1+2 x 2+4 x 3−2 x 4−x 5=2 −2 x 1+x +
2 7 x 3+2 x 4+ x 6=6
xj ≥0 ( j=1. .6) Xét bài toán phụ : P(x)= xg+ g 1 x → min 2
{2x1+5x2−x3−4x4−2x5+xg=61
2 x 1+2 x 2+4 x 3−2 x 4−x 5+ x g=2 2
−2 x 1+x 2+7 x 3+2 x 4 +x 6=6 xj≥ g g
0 ( j=1. .6 ); x , x ≥ 0 1 2 Phươ Hệ số Cơ sở ng -2 3 3 2 0 0 1 1 Án x x x x x x xg xg 1 2 3 4 5 6 1 2 1 xg 6 2 5 -1 -4 -2 0 1 0 1 1 xg 2 2 (2) 4 -2 -1 0 0 1 2 0 x 6 -2 1 7 2 0 1 0 0 6 B1 P(x) 8 4 [7] 3 -6 -3 0 0 0 1 xg 1 -3 0 -11 (1) 1/2 0 1 1 0 x 1 1 1 2 -1 -1/2 0 0 2 0 x 5 -3 0 5 3 ½ 1 0 6 B2 P(x) 1 -3 0 -11 [1] 1/2 0 0 2 x 1 -3 0 -11 1 (1/2) 0 4 3 x 2 -2 1 -9 0 0 0 2 0 x 2 6 0 38 0 -1 1 6 B3 F(x) 8 -10 0 -52 0 [1] 0 0 x 2 -6 0 -22 2 1 0 5 3 x 2 -2 1 -9 0 0 0 2 0 x 4 0 0 16 2 0 1 6 B4 F(x) 6 -4 0 -30 -2 0 0
Vậy bài toán có patu x*= ( 0, 2, 0, 0, 2) với fmin=6 Bài 7 :
Đưa bài toán về dạng chính tắc ta có :
{−x1+x2+x3−x4−x5−x6=3
x 1+ x 2+ x 3−x 4−x 5−x 7=2
x 1+ x 2−2 x 3−3 x 4+2 x 5+ x 8=4
xj ≥ 0 (j=1. .8) Xét bài toán phụ : P(x)= xg+ g 1 x → min 2
{−x1+x2+x −3x4−x5−x6+xg=31
x 1+ x 2+ x 3−x 4−x 5−x 7 + xg=2 2
x 1+ x 2−2 x 3−3 x 4+2 x 5+ x 8=4 xj≥ g g
0 ( j =1..8); x , x ≥ 0 1 2 Ta có bảng đơn hình : Hệ Cơ Phươ 3 4 4 5 1 0 0 0 1 1 số sở ng án x g g 1 x2 x3 x4 x5 x6 x7 x8 x x 1 2 1 xg 3 -1 1 1 -1 -1 -1 0 0 1 0 1 1 xg 2 1 (1) 1 -1 -1 0 -1 0 0 1 2 0 x 4 1 1 -2 -3 2 0 0 1 0 0 8 B1 P(x) 5 0 [2] 2 -2 -2 -1 -1 0 0 0 1 xg 1 -2 0 0 0 0 -1 (1) 0 1 1 0 x2 2 1 1 1 -1 -1 0 -1 0 0 0 x8 2 0 0 -3 -2 3 0 1 1 0 B2 P(x) 1 -2 0 0 0 0 -1 [1] 0 0 0 x7 1 -2 0 0 0 0 -1 1 0 4 x2 3 -1 1 1 -1 -1 -1 0 0 0 x8 1 2 0 -3 -2 3 1 0 1 B3 F(x) 12 -7 0 0 -9 -5 -4 0 0
Vậy bài toán có patu x* =( 0, 3, 0, 0, 0 ) với fmin=12 Bài 8 :
Đưa bài toán về dạng chính tắc ta có :
{ x1−x2+x4+2x5=16
x 1+ x 2+2 x 3−2 x 5−x 6=35
−2 x 2+2 x 3−4 x = 5 20
xj≥ 0 (j=1..6 ) Xét bài toán phụ :
P(x)= xg+xg →min 2 3
{ x1−x2+x4+2x5=16
x 1+ x 2+2 x 3−2 x 5−x 6+ xg=35 2
−2 x 2+2 x 3−4 x 5+ x g=20 3 xj≥ g g
0 ( j =1..6 ); x , x ≥0 2 3 Ta có bảng đơn hình : Phươ Hệ số Cơ sở ng 2 2 -3 -2 1 0 1 1 Án x x x x x x g g 1 2 3 4 5 6 x x 2 3 0 x 16 1 -1 0 1 2 0 0 0 4 1 xg 35 1 1 2 0 -2 -1 1 0 2 1 xg 20 0 -2 (2) 0 -4 0 0 1 3 B1 P(x) 55 1 -1 [4] 0 -6 -1 0 0 0 x 16 1 -1 0 1 2 0 0 4 1 xg 15 1 (3) 0 0 2 -1 1 2 0 x 10 0 -1 1 0 -2 0 0 3 B2 P(x) 15 1 [3] 0 0 2 -1 0 -2 x 21 4/3 0 0 1 8/3 -1/3 4 2 x 5 1/3 1 0 0 2/3 -1/3 2 -3 x 15 1/3 0 1 0 -4/3 -1/3 3 B3 f(x) -77 -5 0 0 0 -1 1
Ta có : Ta có: {∆6=1  Bài toán không giải được Xj6 ≤ 0
Vậy bài toán không giải được Bài 9 :
Đưa bài toán về dạng chính tắc ta có :
{ 2x1+2x3+x4=14
5 x 1+ 3 x 2+ x 3−2 x 4 + x 5=62 −2 x 1+2 x + 2 2 x 3+ x 4=16
xj≥ 0( j =1..5) Xét bài toán phụ :
P(x)= xg+xg →min 1 3
{ 2x1+2x3+x4+xg=141
5 x 1+ 3 x 2+ x 3−2 x 4 + x 5=62 −2 x 1+2 x + 2 2 x 3+ x 4=16 xj ≥ g g
0 ( j=1. .5); x , x ≥ 0 1 3 Ta có bảng đơn hình : Phươn Hệ số Cơ sở g 4 2 3 2 0 1 1 Án x x x x x xg xg 1 2 3 4 5 1 3 1 xg 14 2 0 (2) 1 0 1 0 1 0 x 62 5 3 1 -2 1 0 0 5 1 xg 16 -2 2 2 1 0 0 1 3 B1 P(x) 30 0 2 [4] 2 0 0 0 0 x 7 1 0 1 1/2 0 0 3 0 x 55 4 3 0 -5/2 1 0 5 1 xg 2 -4 (2) 0 0 0 1 3 B2 P(x) 2 -4 [2] 0 0 0 0 3 x 7 1 0 1 ½ 0 3 0 x 52 10 0 0 -5/2 1 5 2 x 1 -2 1 0 0 0 2 B3 F(x) 23 -5 0 0 -1/2 0
Vậy bài toán có patu x*=( 0, 1, 7, 0) với fmin=23 Bài 10 :
Đưa bài toán về dạng chính tắc ta có :
{2x1−x2+x3−2x4+x5=5
3 x 1+ 2 x 2−3 x 3+6 x 4=3
x 1−2 x 2+3 x 3−2 x 4 + x 6=2
xj≥ 0 ( j=1..6) Xét bài toán phụ : P(x)= xg→min 1
{2x1−x2+x3−2x4+x5=5
3 x 1+ 2 x 2−3 x 3+6 x 4 + xg=3 1
x 1−2 x 2+3 x 3−2 x 4 + x 6=2
xj≥ 0( j=1..6); xg ≥ 0 1 Ta có bảng đơn hình : Phươn Hệ số Cơ sở g -3 3 -1 -3 0 0 1 Án x x x x x x xg 1 2 3 4 5 6 1 0 x 5 2 -1 1 -2 1 0 0 5 1 xg 3 3 2 -3 (6) 0 0 1 1 0 x 2 1 -2 3 -2 0 1 0 6 B1 P(x) 3 3 2 -3 [6] 0 0 0 0 x 6 3 -1/3 0 0 1 0 5 -3 x ½ ½ 1/3 -1/2 1 0 0 4 0 x 3 2 -4/3 (2) 0 0 1 6 B2 -f(x) -3/2 3/2 -4 [5/2] 0 0 0 0 x 6 3 -1/3 0 0 1 0 5 -3 x 5/4 1 0 0 1 0 ¼ 4 -1 x 3/2 1 -2/3 1 0 0 ½ 3 B3 -f(x) -21/4 -1 -7/3 0 0 0 -5/4
Vậy bài toán có patu x*= (0, 0, 3/2, 5/4) với fmax=21/4 Bài 11 :
Đưa bài toán về dạng chính tắc ta có :
{x1+3x2+x3−4x4−2x5=5
2 x 1+2 x 2+2 x 3−2 x 4=2
−2 x 1+x 2+5 x 3−2 x 4+ x 6=4
xj ≥ 0( j=1. .6) Xét bài toán phụ :
P(x)= xg+xg →min 1 2
{x1+3x2+x3−4x4−2x5+xg=51
2 x 1+ 2 x 2+ 2 x 3−2 x 4+ xg=2 2
−2 x 1+ x 2+5 x 3−2 x 4 +x 6=4
xj≥ 0( j =1..6); xg , xg ≥0 1 2 Ta có bảng đơn hình : Phươ Hệ số Cơ sở ng 3 2 1 2 0 0 1 1 Án x x x x x x g g 1 2 3 4 5 6 x x 1 2 1 xg 5 1 3 1 -4 -2 0 1 0 1 1 xg 2 2 (2) 2 -2 0 0 0 1 2 0 x 4 -2 1 5 -2 0 1 0 0 6 B1 P(x) 7 3 [5] 3 -6 -2 0 0 0 1 xg 2 -2 0 -2 -1 -2 0 1 1 0 x 1 1 1 1 -1 0 0 0 2 0 x 3 -3 0 4 -1 0 1 0 6 B2 P(x) 2 -2 0 -2 -1 -2 0 0
Vậy bài toán đã cho không giải được. Bài 12 :
Đưa bài toán về dạng chính tắc ta có :
{ x1+3x2+x3−4x4−2x5=10
2 x 1+2 x 2+2 x 3−2 x 4+2 x 5+ x 6=4 −4 x −
1 4 x 2+3 x 3+ 8 x 4 +4 x 5+ x 7=15
xj≥ 0 ( j=1..7 ) Xét bài toán phụ : P(x)= xg→min 1
{ x1+3x2+x3−4x4−2x5+xg=101
2 x 1+2 x 2+2 x 3−2 x 4+2 x 5+ x 6=4 −4 x −
1 4 x 2+3 x 3+ 8 x 4 +4 x 5+ x 7=15
xj ≥ 0( j=1. .7) ; xg≥ 0 1 Ta có bảng đơn hình : Phươ Hệ số Cơ sở ng 3 -1 4 -3 1 0 0 1 Án x x x x x x x xg 1 2 3 4 5 6 7 1 1 xg 10 1 3 1 -4 -2 0 0 1 1 0 x 4 2 (2) 2 -2 2 1 0 0 6 0 x 15 -4 -4 3 8 4 0 1 0 7 B1 P(x) 10 1 [3] 1 -4 -2 0 0 0 1 xg 4 -2 0 -2 -1 -5 -3/2 0 1 1 0 x 2 1 1 1 -1 1 ½ 0 0 2 0 x 23 0 0 7 4 8 2 1 0 7 B2 P(x) 4 -2 0 -2 -1 -5 -3/2 0 0
Vậy bài toán không giải được. Bài 13 :
a/Đưa bài toán về dàng chính tắc ta có :
{3x2+2x3−2x4+x5=72
2 x 1−3 x 3+ x 4=60
2 x 1−4 x 2−3 x 3−2 x 4=36
xj≥ 0 ( j =1..5) Xét bài toán phụ :
P(x)= xg+xg →min 2 3
{ 3x2+2x3−2x4+x5=72
2 x 1−3 x 3+ x 4 + xg=60 2
2 x 1−4 x 2−3 x 3−2 x 4+ x g=36 3 xj≥ g g
0 ( j=1..5); x , x ≥0 2 3 Ta có bảng đơn hình : Phươn Hệ số Cơ sở g 4 -6 14 -5/2 0 1 1 Án x x x x x xg xg 1 2 3 4 5 2 3 0 x 72 0 3 2 -2 1 0 0 5 1 xg 60 2 0 -3 1 0 1 0 2 1 xg 36 (2) -4 -3 -2 0 0 1 3 B1 P(x) 96 [4] -4 -6 -1 0 0 0 0 x 72 0 3 2 -2 1 0 5 1 xg 24 0 (4) 0 3 0 1 2 0 x 18 1 -2 -3/2 -1 0 0 1 B2 P(x) 24 0 [4] 0 3 0 0 0 x 54 0 0 2 -17/4 1 5 -6 x 6 0 1 0 ¾ 0 2 4 x 30 1 0 -3/2 ½ 0 1 B3 F(x) 84 0 0 -20 0 0
Vậy bài toán có patu x*=( 30, 6,0,0,54)
b/, ∆ =0mà 4 khôngthu c
ộ J , nên theo phương 4 0
z4 xây dựng được tập phương án tối ưu :
x(θ )= x¿+θ . z4 trong đó : 17
x¿={30,6,0,0,54} ; z4=( −1,− 3 ,0,1, ) v i
ớ 0 ≤ θ ≤8 2 4 4 Suy ra : 17
x( θ)={30,6,0,0,54 } +(−1 ,−3 ,0,1, ) . θ với0≤ θ≤8 2 4 4
Theo đề x =3 ↔6− 3θ=3 => θ=4 . 2 4
Vậy PATU không cực biên với thành phần x2 =3 là : x=(28,3,0,4,71) Bài 14:
a/Đưa bài toán về dạng chính tắc:
{ 2x1+x2−x3+x4=20
−x 1−2 x 2+x 4+x 5=16
2 x 1−2 x 2+ x 3−2 x 4 + x 6=24
xj ≥0 ( j=1. .6) Xét bài toán phụ : P(x)= xg→min 1
{ 2x1+x2−x3+x4+xg=201
−x 1−2 x 2+x 4+x 5=16
2 x 1−2 x 2+ x 3−2 x 4 + x 6=24 xj ≥ g
0 ( j=1. .6) ; x ≥0 1 Ta có bảng đơn hình: Phươn Hệ số Cơ sở g -2 4 -2 7/2 0 0 1 Án x x x x x x xg 1 2 3 4 5 6 1 1 xg 20 (2) 1 -1 1 0 0 1 1 0 x 16 -1 -2 0 1 1 0 0 5 0 x 24 2 -2 1 -2 0 1 0 6 B1 P(x) 20 [2] 1 -1 1 0 0 0 2 x 10 1 1/2 -1/2 1/2 0 0 1 0 x 26 0 -3/2 -1/2 (3/2) 1 0 5 0 x 4 0 -3 2 -3 0 1 6 B2 -f(x) 20 0 ½ -1/2 [1/2] 0 0 -2 x 4/3 1 1 -1/3 0 -1/3 0 1 7/2 x 52/3 0 -1 -1/3 1 (2/3) 0 4 0 x 56 0 -6 1 0 2 1 6 B3 -f(x) 58 0 -19/2 3/2 0 [3] 0 -2 x 10 1 1/2 -1/2 1/2 0 0 1 0 x 26 0 -3/2 -1/2 3/2 1 0 5 0 x 4 0 -3 (2) -3 0 1 6 B4 -f(x) -20 0 -5 [3] -9/2 0 0 -2 x 11 1 -1/4 0 -1/4 0 1/4 1 0 x 27 0 -9/4 0 ¾ 1 ¼ 5 -2 x 2 0 -3/2 1 -3/2 0 1/2 3 B5 -f(x) -26 0 -1/2 0 0 0 -1
Vậy bài toán có patu x*=( 11, 0, 2, 0) với fmax= 26
b/, ∆ =0mà 4 khôngthu c
ộ J , nên theo phương 4 0
z4 xây dựng được tập phương án tối ưu :
x(θ )= x¿+θ . z4 trong đó : 3
x¿={11,0,2,0,27,0} ; z4=(1 ,0, ,1,−3 ,0)v iớ 0≤θ≤36 4 2 4 Suy ra : 3
x( θ)=¿ {11,0,2,0,27,0}+¿ (1 ,0, ,1,− 3 ,0) . θ với0≤θ≤36 4 2 4 Theo đề x =10 4
↔ 0+θ=10 => θ=10 .
Vậy PATU với thành phần x 39 4 =10 là :
x=( 27 ,0,17,10, ,0) 2 2 Bài 15:
a/Đưa bài toán về dạng chính tắc ta có:
{x1−2x2+2x3−x4+x6=8
x 1+2 x 2+ x 3+ x 4+ x 5=10
2 x 1+ x 2−x 3+ x 7=17
xj ≥ 0 ( j=1. .7) Ta có bảng đơn hình: Phươ Hệ số Cơ sở ng -2 1 2 2 1 0 0 Án x x x x x x x 1 2 3 4 5 6 7 0 x 8 1 -2 2 -1 0 1 0 6 1 x 10 1 2 1 1 1 0 0 5 0 x 15 (2) 1 -1 0 0 0 1 7 B1 F(x) 10 [3] 1 -1 -1 0 0 0 0 x 1/2 0 -5/2 (5/2) -1 0 1 6 1 x 5/2 0 3/2 3/2 1 1 0 5 -2 x 15/2 1 ½ -1/2 0 0 0 1 B2 F(x) -25/2 0 -1/2 [1/2] -1 0 0 2 x 1/5 0 -1 1 -2/5 0 3 1 x 11/5 0 3 0 8/5 1 5 -2 x 38/5 1 0 0 -1/5 0 1 B3 F(x) -63/5 0 0 0 -4/5 0
Vậy bài toán có patu x*=( 38/5, 0, 1/5, 0, 11/5) với fmin= -63/5
b/, ∆ =0mà2khôngthu c ộ J , nên theo phương 2 0
z2 xây dựng được tập phương án tối ưu :
x(θ )=x¿+θ . z2
trong đó : x¿={38/5,0,1/5,0,11/5} ; z2=( 0,1,1,0,−3) v i
ớ 0 ≤θ ≤ 11/15
Suy ra : x( θ)={38/5,0,1/5,0,11/5} + (0,1,1,0,−3) . θ với0≤θ≤11/15
Theo đề x =1/5 ↔θ=1/5 2
Vậy PATU với thành phần x 1 2 8 2 =1/5 là : x=( 38 , , ,0, ) 5 5 5 5 Bài 16:
a/Đưa bài toán về dạng chính tắc ta có:
{4x1−3x2−x3+2x4+x5=34
2 x 1−2 x 2+ 3 x 3+ x 6=60
2 x 1−2 x 2−3 x 3+ 4 x 4−x 7=32
xj ≥ 0 ( j=1. .7) Xét bài toán phụ : P(x)= xg3→min
{ 4x1−3x2−x3+2x4+x5=34
2 x 1−2 x 2+3 x 3+ x 6=60
2 x 1−2 x 2−3 x 3+ 4 x 4−x 7 + xg=32 3 xj ≥ g
0 ( j=1. .7); x ≥0 3 Ta có bảng đơn hình: Phươ Hệ số Cơ sở ng -3 1 -3 2 0 0 0 1 Án x x x x x x x g 1 2 3 4 5 6 7 x3 0 x 34 4 -3 -1 2 1 0 0 0 5 0 x 60 2 -2 3 0 0 1 0 0 6 1 xg 32 2 -2 -3 (4) 0 0 -1 1 3 B1 P(x) 32 2 -2 -3 [4] 0 0 -1 0 0 x 18 (3) -2 ½ 0 1 0 1/2 5 0 x 60 2 -2 3 0 0 1 0 6 2 x 8 ½ -1/2 -3/4 1 0 0 -1/4 4 B2 -f(x) 16 [4] -2 3/2 0 0 0 -1/2 -3 x 6 1 -2/3 1/6 0 1/3 0 1/6 1 0 x 48 0 -2/3 8/3 0 -2/3 1 -1/3 6 2 x 5 0 -1/6 -5/6 1 -1/6 0 -1/3 4 B3 -f(x) -8 0 2/3 5/6 0 -4/3 0 -7/6
Ta có : Ta có: {∆2=2/3  Bài toán không giải được Xj2 ≤ 0
Vậy bài toán không giải được
b/ Ta có : f(x) ≤18nên=¿−f ( x) ≥−18
Ta suy ra phương án x là tối ưu khi –f(x) = -18
Từ bảng đơn hình thứ 3 ta có phương án cực biên x* = ( 6, 0, 0, 5, 0, 48, 0) với –f(x*) = -8 và phương 1 2
z2=( 2 ,1,0, ,0, ,0)v à ∆2=2 là phư ơng giảmvôhạn 3 6 3 3 Suy ra : 1 2
x( θ )=(6, 0,0, 5, 0, 48, 0)+(2 ,1,0, ,0, ,0) . θ ; θ≥0 là các 3 6 3 phương án của bài toán x∗¿ Ta có –f(x( ¿ θ ¿ ¿=−f ¿ => θ=15
Vậy patu cần tìm là x’ =( 16, 15,0, 15/2) Bài 17 :
a/Đưa bài toán về dạng chính tắc ta có :
{x1−2x2+2x3−x4=12
2 x 2+ x 3+ x 4+ x 5=10
5 . x1+x 2−x3+x 6=15 2
xj ≥0( j=1. .6) Xét bài toán phụ : P(x)= xg→min 1
{x1−2x2+2x3−x4+xg=121
2 x 2+ x 3+ x 4 + x 5=10
5 .x 1+x2− x3+x 6=15 2 xj≥ g
0( j=1..6 ); x ≥ 0 1 Ta có bảng đơn hình : Phươ Hệ số Cơ sở ng -2 1 2 3/2 1 0 1 Án x x x x x x xg 1 2 3 4 5 6 1 1 xg 12 1 -2 (2) -1 0 0 1 1 0 x 10 0 2 1 1 1 0 0 5 0 x 15 5/2 1 -1 0 0 1 0 6 B1 P(x) 12 1 -2 [2] -1 0 0 0 2 x 6 ½ -1 1 -1/2 0 0 3 1 x 4 -1/2 3 0 3/2 1 0 5 0 x 21 (3) 0 0 -1/2 0 1 6 B2 f(x) 16 [5/2] 0 0 -1 0 0 2 x 5/2 0 -1 1 -5/12 0 -1/6 3 17/1 1 x 15/2 0 3 0 2 1 1/6 5 -2 x 7 1 0 0 -1/6 0 1/3 1 B3 F(x) -3/2 0 0 0 -7/12 0 -5/6
Vậy bài toán có patu x* = ( 7, 0, 5/2, 0, 15/2, 0) với fmin = -3/2
b/ ∆ =0mà2khôngthu c
ộ J , nên theo phương 2 0
z2 xây dựng được tập phương án tối ưu :
x(θ )=x¿+θ . z2
trong đó : x¿=¿ ( 7, 0, 5/2, 0, 15/2, 0); z2=( 0,1,1,0,−3,0) v i
ớ 0≤ θ ≤ 5/2
Suy ra : x( θ)=(7,0,5/2,0,15/2,0) + (0,1,1,0,−3) . θ với0≤θ≤5/2
Theo đề x =1 ↔θ=1 2
Vậy PATU với thành phần x 7 9 2 =1 là :
x=(7,1, ,0, ,0) 2 2 Bài 18:
a/ Đưa bài toán về dạng chính tắc ta có:
{2x1+3x2−4x3+x5=5
3 x 1+ 2 x 2−x 3−x 6=3
x 1+ x 2−x 4+ x 7=6
xj ≥0 ( j=1..7) Xét bài toán phụ : P(x)= xg2→min
{2x1+3x2−4x3+x5=5
3 x 1+ 2 x 2−x 3−x 6 + xg=3 2
x 1+ x 2−x 4 + x 7=6 xj≥ g
0 ( j=1..7 ) ; x ≥ 0 2 Ta có bảng đơn hình: Phươ Hệ số Cơ sở ng -1 2 0 1 0 0 0 1 Án x x x x x x x g 1 2 3 4 5 6 7 x2 0 x 5 2 3 -4 0 1 0 0 0 5 1 xg 3 (3) 2 -1 0 0 -1 0 1 2 0 x 6 1 1 0 -1 0 0 1 0 7 B1 P(x) 3 [3] 2 -1 0 0 -1 0 0 0 x 3 0 5/3 -10/3 0 1 (2/3) 0 5 -1 x 1 1 2/3 -1/3 0 0 -1/3 0 1 0 x 5 0 1/3 1/3 -1 0 1/3 1 7 B2 -f(x) -1 0 -8/3 1/3 -1 0 [1/3] 0 0 x 9/2 0 5/2 -5 0 3/2 1 0 6 -1 x 5/2 1 3/2 -2 0 1/2 0 0 1 0 x 7/2 0 -1/2 (2) -1 -1/2 0 1 7 B3 -f(x) -5/2 0 -7/2 [2] -1 -1/2 0 0 0 x 53/4 0 5/4 0 -5/2 1/4 1 5/2 6 -1 x 6 1 1 0 -1 0 0 1 1 0 x 7/4 0 -1/4 1 -1/2 -1/4 0 1/2 3 B4 -f(x) -6 0 -3 0 0 0 0 -1
Vậy bài toán có patu x* = ( 6, 0,7/4,0,0, 53/4) với fmax = 6
∆ =0 mà 4 không thu c ộ J , nên theo phương 4 0
z4 xây dựng được tập phương án tối ưu :
x(θ )=x¿+θ . z4 trong đó : 1 5
x¿=(6, 0,7/4,0,0, 53/ 4 ) ; z4=(1,0, ,1,0, )v i ớ 0 ≤θ 2 2 Suy ra : 1 5
x( θ )=(6,0,7 / 4,0,0,53 / 4) + (1,0, ,1,0, ) . θ với0≤θ 2 2 Theo đề x =10 4 ↔θ=10
Vậy PATU không cực biên với thành phần x4 =10 là : 27 153 x=(16,0, ,10,0, ) 4 4
Bài 19: F(x) = 2x1 + x2 + 5x3 -> min
3 x 1+ x 2−x 3≥ 9( 1)
x 1+2 x 2+ x 3 ≤ 5 ( 2) ¿
x 1+2 x 2+2 x 3 ≥ 3(3) j=( ) 1,3 ¿ xj≥ 0 ¿ ¿
a) Bài toán đốối ngẫẫu
F(y) = 9y1 + 5y2 + 3y3 -> max ¿
3 y 1+ y 2− y 3 ≤2 (1' )
y 1+2 y 2+2 y 3 ≤ 1(2 ' )
− y 1+ y 2+2 y 3 ≤ 5(3' )
y 1 ≥0, y 2≤ 0 , y 3 ≥ 0 ¿ ¿ Các c p đốối ng ặ
ẫẫu : x1 ≥ 0↔ (1’)
x2 ≥ 0 ↔ (2’)
x1 ≥ 0 ↔ (3’) (1) ↔ y1 ≥ 0 (2) ↔ y ≤ 0 2 (3) ↔ y3 ≥ 0
b) X0 = (3,0,0) đốối v i bài toán ớ - Vecto X0 th a mãn t ỏ ẫốt c các r ả àng bu c c ộ a bài t ủ oán nên X0 là: PA c a bài toán : ủ
{9≥93≤53≥3 - PA x0 th a mãn ch ỏ n r ặ àng bu c (1), (3) v ộ
à x2 = 0, x3 = 0 trong đó có 3 ràng bu (1), (3) và x ộ 3
≥ 0 là độc lập => x0 là PACB suy biêốn -
Giả sử x0 là PATG c a bài to ủ
án, do x0 thỏa mãn ràng bu c (2), x ộ 1 = 3 > 0 nên m i ph ọ ng án tốối ươ u cư a bài toán đ ủ
ốối ngẫẫu (nêốu có) ph i th ả a mãn y ỏ 2 ≤ 0 và (1’) Tức là thỏa mãn h ph ệ ng trình sau ươ { y2=0
3 y 1+ y 2+ y 3=  { y2=0 2 y 3=2−3 y 1 HPT trên có nghi m t ệ ng quát là y = (y ổ 1, 0, 2-3y1) Y1 ϵ R . Th các nghi ử m này vào c ệ ác ràng bu c còn l ộ i cạ a b
ủ ài toán đốối ngẫẫu, ta có: 3 (2’) y  ≥ 1 + 2(2-3y1) ≤ 1 y  1 5 (3’) -y  ≥− 1 1 + 2(2-3y1) ≤ 5 y  1 7 y ≥ 1 0 2 3 y 1 ≥ 0 2 y ) 3 ≥ 0 y  ≤ (y= − 1 2 3 → y 1 ≤ 3 3 2 Vecto y = (y ( y ,0,2−3 y ) ả ộ ủ ≤ y 1 ≤ 1, 1 1 Tm tẫốt c các ràng bu
c c a bài toán đốối ngẫẫu khi 5 3 Nên x0 là ph ng án tốối ươ u c ư a bài toàn dã cho ủ - T p ph ậ ng án tốối ươ u c ư a bài toán đ ủ ốối ngẫẫu Y =
{y= (y ,0,2−3 y )|,(3 ≤ y 1≤2/3) 1 5
Bài toán đốối ngẫẫu có 2 PACB tốối u là: ư 3 1 - Khi y 1=3 ta có PACB y1 =( , 0, ¿ 5 5 5 2 - Khi y ta có PACB y2 (2 1 = , 0,0) 3 3 Bài 20: a)
f ( x)=4 x 1+12 x 2−16 x 3 →min
{ x1−3x3≥−6(1')
x 1+3 x 2−4 x 3 ≥−2(2' )
x 2−x 3 ≤ 4 (3' )
f ( y)=−6 y 1−2 y 2+4 y 3 → max
{ y1+y2=4(1')
−3 y 1+ y 2+ y 3=12(2')
−4 y 2− y 3=−16(3' )
y 1 ≥0 , y 2≥ 0 , y 3≤ 0 C p ràng ặ bu c đốối ng ộ ẫẫu
y 1 ≥ 0 ↔(1)
y 2 ≥ 0 ↔(2)
y 3 ≤ 0 ↔(3) b) Vecto x=(− ) 1,1,1
Thay Vecto x vào bài toán ban đẫầu: {−4≥−6 −2 ≥−2 0≤ 4 Vecto x = (-1,1,1) là ph ng án, x th ươ a mãn ch ỏ t r
ặ àng bu c (2) nên x khống là ộ ph ng án CB ươ Gi sả X là ph ử ng án t ươ ốối u, X th ư a mãn l ỏ ng r ỏ àng bu c (1), (3) thì m ộ i ph ọ ng án tốối ươ u y c ư a bài ủ toán đốối ngẫẫu ph i ả th a mãn ỏ
{y1=0→y2=4=¿y=(0,4,0) y 3=0 Y0 th a mãn t ỏ ẫốt c rằầng bu ả c cộa bài t
ủ oán đốối ngẫẫu nên x là ph ng án tốối ươ u ư Bài 21:
f (x )=x 1+ 4 x 2+ px 3→ max a)
f (y )=10 y 1− y 2 →min
{3y1−y2≥1(1')
4 y 1+ y 2 ≥ 4( 2' )
4 y 1+ y 2 ≥ p (3') Hai bài toán có c p r
ặàng bu c đốối ngẫẫ ộ u
x 1 ≥ 0↔(1 ' )
x 2 ≥ 0↔( 2' )
x 3 ≥ 0 ↔(3 ' )
b) Thay vecto X = (2,1,0) vào bài toán gốốc {10=10 −1=−1
Ta thẫốy x th a mãn bài toá ỏ n gốốc  X là ph ng án c ươ a bài t ủ oán gốốc G a s ỉ x là patu c ử a bài toán g ủ ốốc Ta thẫốy x th a mãn l ỏ
ng 2 rb vêầ dẫốu nên theo đ ỏ nh lí 2 đốối n ị gẫẫu ta có h : ệ {3y1−y2=1 8 → y (5 , ) 4 y 1+ y 2=4 7 7 Thay y vào các rb còn l c
ạ a bài toán đn thẫốy th ủ a mãn nên suy y là patu. ỏ Đ y là patu khốn ể
g suy biêốn thì (3’)  4y1 + y2 > p  p<4 Theo đ nh lí 1 ta s ị
uy ra x là patu c a bài toán. ủ 8 V i p< 4, P ớ
ACBTU duy nhẫốt y’ = ( 5 , ) thỏa mãn l ng ỏ
(3’) => PATU c a bài toán gốốc t ủ h a mãn ỏ 7 7
{3x1+4x2+4x3=10
−x 1+x 2+ x 3=−1 -> {x1=2 x 2=1 x 3=0 x 3=0
Đẫy là PACBTU duy nhẫốt c a bài toán gốốc ủ Bài 22
f (x )=6 x 1+ 3 x 2+ x 3+2 x 4 → min −x − 1
3 x 2+2 x 3+5 x 4 ≥−16 (1) ¿∗¿ ¿
3 x 1+ x 2−4 x 3−x 5 ≤10 (2) ¿ ¿
7 x 1+3 x 3−2 x 4=0 ¿ ¿ Bài toán đốối ngẫẫu
f (y )=−16 y 1+10 y 3−2 y 4 → max
{−y1+7y2+3y3+2y4≤6(1')
−3 y 1+ y 3+2 y 4 ≤ 3(2' )
2 y 1+ 3 y 2−4 y 3 ≤1( 3')
5 y 1−2 y 2−6 y 4 ≤ 2 (4' )
− y 3 ≤ 0(5' )
y 1 ≥ 0 , y 3 ≤ 0 , y 4 ≤ 0 Bài toán có 8 c p rà ặ ng bu c đốối ng ộ
ẫẫy (i) (-) (i’) v i i=(1,….,8) ớ Gi i bài toán gốốc b ả ằầng ph ng pháp đ ươ n hình ơ P = x2y + x4y => min
{x1+3x2−2x3−5x4+x6=16
7 x 1+ 3 x 3−2 x 4+ xy=0 2
3 x 1+ x 2−4 x 3−x 5+ x 7=10 −2 x −
1 2 x 2+6 x 4−x 8+ x y =2 4 xj ≥ 0( j=1,8) HS CS PA 6 3 1 2 0 0 0 0 1 1 X1 X2 X3 X4 X5 X6 X7 X8 xy xy 2 4 0 X6 16 1 3 -2 -5 0 1 0 0 0 0 1 xy 0 (7) 0 3 -2 0 0 0 0 1 0 2 0 X7 10 3 1 -4 0 -1 0 1 0 0 0 1 xy 2 -2 -2 0 6 0 0 0 -1 0 1 4 P 2 [5] -2 3 4 0 0 0 -1 0 0 0 X6 16 0 3 -17/7 -33/7 0 1 0 0 0 0 X1 0 1 0 3/7 -2/7 0 0 0 0 0 0 X7 10 0 1 -37/7 6/7 -1 0 1 0 0 1 xy 2 0 -2 6/7 (38/7) 0 0 0 -1 1 4 P 2 0 -2 6/7 [38/7] 0 0 -1 0 0 X6 337/19 0 24/19 -32/19 0 0 1 0 -33/38 6 X1 2/19 1 -2/19 (9/19) 0 0 0 0 -1/19 0 X7 184/19 0 25/19 - 0 -1 0 1 3/19 103/19 2 X4 7/19 0 -7/19 3/19 1 0 0 0 -7/38 F(x) 26/19 0 -83/19 [41/19] 0 0 0 0 -13/19 0 X6 163/9 32/9 8/9 0 0 0 1 0 -19/18 1 X3 2/9 19/9 -2/9 1 0 0 0 0 -1/9 0 X7 98/9 103/9 1/9 0 0 -1 0 1 -4/9 2 X4 1/3 -1/3 -1/3 0 1 0 0 0 -1/6 F(x) 8/9 -41/9 -35/9 0 0 0 0 0 -4/9 Từ bảng ta có
∆ k ≤ 0 ∀k ∈ J . Nên bài toán đã cho có ph ng án tốối ươ u x* = ư ¿ 89 ( 2 1 163 98 0,0, , , 0, .
, 0) và f ( x ) min ¿¿ 9 3 9 8 b) X* là ph ng án tốối ươ u c ư a bài toán gốốc ủ 2 1 163 98 X¿=( 0,0, , ,0, . , 0) 9 3 9 8
Thay X* vào bài toán gốốc
−x 1−3 x 2+2 x 3+5 x 4 ≥−16( 1) ¿∗¿ ¿ ¿
¿ 3 x 1+x 2−4 x 3−x 5≤ 10( 2) ≥−16 0=0
7 x 1+3 x 3−2 x 4=0(¿2 x 1+2 x 2−6 x 4 ≤−2 (3 ) ¿(¿ ) {139−8≤10 9 −3 ≤−2 ¿ X* th a mãn ỏ rằầng bu c l ng ộ (1), ỏ (2), (3) thì m i ph ọ ng ư án ơ tốối u c ư a bài ủ
toán đốối ngẫẫu ph i ả th a ỏ mãn {y1=0 y 3=0→ y 2= 67 y 4=0 6  Y* = (0, ,0,0) 7 X* th a mãn ch ỏ t ràng bu ặ c (**) nên X* khống là P ộ ACB
 Y* khống là PACB nhưng là PATU và PACBTU Bài 23
f (x )=18 x 1+13 x 2+5 x 3→ min
{x1+x2≥−1(1)3
3 x 1+5 x 2 ≥2 (2)
3 x 1+ 3 x 3 ≥2 (3)
x 1+2 x 2 ≥− 1 ( 4) 3
9 x 1+8 x 2+ x 3 ≥ 6 (5)
Ta có bài toán đốối ngẫẫu −1 f (y )=
y 1+2 y 2+2 y 3− 1 y 4 +6 y 5 → max 3 3
{y1+3y2+3y3+y4+9y5=18(1')
y 1+ 5 y 2+2 y 4+8 y 5=13 (2')
3 y 3+ y 5=5(3') Các ràng bu c c ộ p ặ
y 1 ≥ 0 (¿) (1 )
y 2 ≥ 0 ↔(2)
y 3 ≥ 0 ↔(3 )
y 4 ≥ 0 ↔( 4)
y 5 ≥ 0 ↔(5 )
a) Vecto x=( 2 ,0,0) 3
Thay vecto X vào bài toán gốốc
{2≥−1(1)332≥2(2)2≥2(3)2≥−1(4)336≥6(5) Vecto X th a mãn tẫốt c ỏ các r ả àng bu c: ộ PA X th a mãn ch ỏ t (2), (3), (5) ặ PA X th a mãn l ỏ n ỏ g (1), (4)
 X là PACB khống suy biêốn - Giả sử X là PATU và th a ỏ mãn l ng ỏ (1), (4) nên m i ọ PATU c a ủ bài toán đ ng ươ nhiên th a ỏ mãn. ¿ y 1= y 4=0
3 y 2+3 y 3+9 y 5=18 5 y 2+ 8 y 5=13 3 y 3+ y 5=5 ¿ ¿ 9 13
→ y∗¿(0,0, ,0, ) 8 8 Y0 th a mãn tẫốt c ỏ các r ả àng bu c c ộ a bài toán => y ủ o là patu c a bài toán ủ
Nên theo đ nh lí1 đốối ng ị
ẫẫu thì x = (2 ,0,0)là PATU củabàitoángốc 3 b) T p P ậ ATU c a BT ủ ĐN 9 13
y={y0=(0,0, ,0, )} 8 8 Y0 th a mãn ch ỏ t 3 rb chính và 3 r ặ
b vêầ dẫốu => y0 là patu c c
ự biên suy biêốn c a bài toán. ủ c/ Tìm tẫp ph ng án tốối ươ u c ư a bài to ủ án gốốc. PATU Y0 c a B ủ TĐN th a mãn l ỏ ng y ỏ 3
≥ 0 , y 5 ≥ 0  M i P ọ ATU c a bài toán gốố ủ c th a mãn ỏ { 3x1+3x3=2 −x 3 →{x1=23
9 x 1+8 x 2+ x 3=6 x 2=x 3
→ x=(2−x3, x3,x3) 3 Các PATU c a bài toán g ủ ốốc ph i th ả a mãn ỏ các ràng bu c còn l ộ i ạ
Thay x=( 2−x 3,x 3,x 3) vàocác ràngbuộccònl iạta đư cợx 3≥0 3
2 −x 3,x 3,x 3 V y t ậ p P ậ ATU c a bài toán g ủ ốốc là 3
x={¿với x 3≥ 0 } Bài 24: a/Bài toán đối ngẫu: g(y) = 20.y1 + 16.y2 max  { y1≤1(1)
2 y 1+ y 2≤ 1( 2)
2 y 1−2 y 2=1 (3)
−3 y 1+2 y 2=2(4 ) y 1 ≤0 (5) y 2 tùy ý (6)
Các cặp ràng buộc đối ngẫu: x ≥ 0 ↔(1) x ≥ 0 ↔(2)
x 1+2 x 2+2 x 3−3 x 4 ≤20 ↔(5 ) Ta có từ (3) và (4) suy 1 2 ra {y1=−3−7 y 2= 2 => y* =( -3, -7/2)
Thay y* vào các ràng buộc còn lại của bài toán đối ngẫu thấy thõa
mãn nên suy ra y* là phương án tối ưu của bài toán
Nên theo định lí 1 Đối Ngẫu thì suy ra bài toán gốc giải được.
Ta thấy y* thõa mãn lỏng ràng buộc (1), (2),(5) nên theo định lí 2 Đối
Ngẫu thì bài toán gốc có patu x* thỏa mãn chặt các ràng buộc tương ứng nên ta có hệ : { x1=0x2=0
x 1+2 x 2+2 x 3−3 x 4=20
x 2−2 x 3+2 x 4=16 { x1=0x2=0 x 3=−44 x 4=−36
=> x* = (0, 0, -44, -36) là phương án cực biên tối ưu của bài toán gốc. Bài 25 : a/Bài toán đối ngẫu : g(y) = 3y1 + y2 + 2y3 min 
{−y1+y2+2y3≥3(1) y 1−2 y 2=1(2)
2 y 1+ 3 y 2+ y 3 ≤−2(3) y 1≤ 0 (4) y 2 ≤ 0(5) y 3 ≤ 0(6)
Các cặp ràng buộc đối ngẫu: x ≥ 0 ↔(1) x ≥ 0 ↔(3)
−x 1+x 2+2 x 3≥ 3 ↔(4 ) 1 3
x1−2x 2+3x 3≥1↔(5)
2x 1+x3≥ 2↔(6) b/
Từ (2) suy ra y1 = 1+ 2y2 thay vào (1) và (3) ta được :
{−y2+2y3≥4
7 y 2+ y 3 ≤−4
Nhân cả 2 vế của bpt số 1 với 7, nhân cả 2 vế của bpt số 2 với -1,
sau đó cộng 2 bất phương trình lại ta được: y3 32 ≥ 13
Mâu thuẫn với đề bài nên suy ra bài toán đối ngẫu không giải được. Bài 26: a/ Bài toán đối ngẫu: g(y) = 7y1 – 4y2 + 5y3 max 
{y1−2y2+3y3≤−8(1)
y 2− y 3 ≤ 6(2)
−2 y 1− y 2+2 y 3=4 (3 )
y 1+3 y 2−6 y 3 ≤5 ( 4) y 1≤ 0 ( 5) y 2 tùy ý y 3 ≥ 0 ( 6)
Các cặp ràng buộc đối ngẫu: x ≥ 0 ↔(1) x ≥ 0 ↔(2) 1 2 x 4≥0(4)
x 1−2 x 3+ x 4 ≤7 ↔( 5)
3 x1−x 2+2x 3−6 x 4≥ 5↔(6)
b/ Thay xo vào các ràng buộc của bài toán thấy thỏa mãn nên suy ra
xo là phương án của bài toán.
Ta thấy xo thỏa mãn chặt 3 ràng buộc chính và 2 ràng buộc về dấu
nên xo là phương án cực biên tối ưu suy biến của bài toán.
c/ Ta thấy x0 thỏa mãn lỏng ràng buộc về dấu: x1 =3 ≥0 nên bài
toán đối ngẫu pải chặt ràng buộc tương ứng suy ra ta có hệ:
{y1−2y2+3y3=−8 { y1 − y 2=8 y 1+28
2 y 1− y 2+2 y 3=4 y 3=5 y 1+16
=> y* = ( y1, 8y1+28, 5y1 +16) vào các ràng buộc còn lại của bài
toán đối ngẫu ta được điều kiện: −16 ≤ y1≤−2 5
=> y* là tập phương án tối ưu của bài toán đối ngẫu
Phương án có thành phần y1 = -3 là y’ = (-3, 4, 1) Bài 27 : a/Bài toán đối ngẫu : g(y) = -10y1 +3y2 +5y3 max  {2y1−y2=−4
− y 1+3 y 2+2 y 3=1 y 2+2 y 3=−4
4 y 1+2 y 2− y 3=3 −5 y 1+ y = 3 2 y 1≤ 0(1) y 2≥ 0(2) y 3 ≤ 0(3)
Các cặp ràng buộc đối ngẫu:
2 x −x 2+4 x 4−5 y 5≤−10 ↔(1)
−x 1+3 x +x 3+2 x 4 ≥3 ↔(2) 1 2
2x2+2x3- x 4+x 5≤5(3)
b/ Tập phương án tối ưu của bài toán đối ngẫu là: y* = (-1, 2,-3) Bài 28: a/ Bài toán đối ngẫu: g(y)= -27y1 -4y2 +17y3 max 
{−2y1+y2+y3≤−2(1)
y 1−2 y 2+3 y 3 ≤19 (2 )
− y 1−2 y 2+ y 3 ≤5(3 )
3 y 1− y 3 ≤ 3 (4)
2 y 1+3 y 2≤ 1 (5 ) y 1 ≥ 0 (6 ) y 2 ≤ 0 (7 ) y 3 ≥ 0 (8 )
Các cặp ràng buộc đối ngẫu:
x 1 ≥ 0↔( 1)
x 2 ≥ 0↔( 2)
x 3 ≥ 0 ↔( 3)
x 4 ≥ 0↔(4)
x 5 ≥ 0 ↔( 5)
−2 x 1+x 2− x 3+3 x 4+2 x 5 ≥−27 ↔(6)
x 1−2 x 2−2 x 3+3 x 5 ≤−4 ↔(7)
x 1+3 x 2+ x 3−x 4 ≥ 17 ↔( 8)
b/ Thay y vào các ràng buộc của bài toán đối ngẫu => y là phương án của bài toán
Ta thấy y thỏa mãn chặt ràng buộc(1) và(3) nên suy ra y là phương
án tối ưu không cực biên
c/ Đưa bài toán về dạng chính tắc ta có:
{2x1−x2+x3−3x4−2x5+x6=27
−x 1+2 x 2+2 x 3−3 x − 5 x = 7 4
x 1+3 x 2+ x 3−x 4−x 8=17
x ≥ 0 ( j=1. .8) j Xét bài toán phụ:
P(x) = xg+xg →min 2 3
{2x1−x2+x3−3x4−2x5+x6=27
−x 1+2 x 2+2 x 3−3 x 5−x 7 + xg=4 2
x 1+3 x 2+ x 3−x 4−x 8+ x g=17 3 x ≥ g g
0 ( j =1..8 ); x , x ≥ 0 j 2 3 Ta có bảng đơn hình: Phương -2 19 5 3 1 0 0 0 1 1 Hệ số Cơ sở án x1 x2 x3 x4 x5 x6 x7 x8 g g x2 x3 0 x6 27 2 -1 1 -3 -2 1 0 0 0 0 1 g 4 -1 (2) 2 0 -3 0 -1 0 1 0 x2 1 g 17 1 3 1 -1 0 0 0 -1 0 1 x3 Bảng 1 P(x) 21 0 [5] 3 -1 -3 0 -1 -1 0 0 0 x6 29 3/2 0 2 -3 −7/ 2 1 −1/2 0 || 0 0 x2 2 −1/2 1 1 0 −3/ 2 0 −1/2 0 || 0 1 g 11 5/2 0 -2 -1 (9/2) 0 3/2 -1 || 1 x3 Bảng 2 P(x) 11 5/2 0 -2 -1 [9/2] 0 3/2 -1 || 0 0 x6 338/9 31/9 0 4/9 −34/9 0 1 2/3 −7/ 9 19 x / 2 17/3 1/3 1 1/3 −1/ 3 0 0 0 −1 3 1 x −2/ 9 5 22/9 (5/ 9) 0 −4/9 −2/9 1 0 1/3 Bảng3 f(x) 991/9 [80/ 9] 0 8/9 −86/9 0 0 1/3 −59/9 0 x / / −12/5 −31/5 / 6 112 5 0 0 16 5 1 −7 5 3/5 19 x2 21/5 0 1 (3/5) −1/ 5 −3/5 0 −1/ 5 −1/ 5 -2 x / 1 22/5 1 0 −4/5 −2/ 5 9/5 0 3/5 −2 5 Bảng 4 f(x) 71 0 0 [8] -6 -16 0 -5 -3 0 x / / / 6 0 0 −16 3 0 −4 3 -3 1 −1 3 5/3 3 x / 3 7 0 5/3 1 −1 3 -1 0 -3 -3 -2 x / 1 10 1 4/3 0 −2 3 1 0 1/3 −2/ 3 Bảng 5 f(x) 1 0 −50/3 0 −8/ 3 -6 0 −29/3 −23/3
Vậy bài toán có patu x* = ( 10, 0, 7, 0, 0) với fmin = 1
d/ Ta thấy x* thỏa lỏng 2 ràng buộc về dấu nên theo định lí 2 đối
ngẫu thì bài toán đối ngẫu có pa y* thỏa mãn chặt các ràng buộc
tương ứng nên ta có hệ :
{−2y1+y2+y3=−2
− y 1−2 y 2+ y 3=5
=> y* = (3y2+7, y2, 5y2 + 12) với −7 3 ≤ y 2 ≤ 3 2 Bài 29:
Đưa bài toán về dạng chính tắc:
{ 3x1+2x2−2x3+x5=72
−3 x 2+x 3+2 x 4=60 −4 x −
1 3 x 2−2 x 3+2 x 4=36
x ≥ 0( j =1..5) j Xét bài toán phụ:
P(x) = xg+ xg→min 2 3
{ 3x1+2x2−2x3+x5=72
−3 x 2+ x 3+ 2 x 4 + x g=60 2
−4 x 1−3 x 2−2 x 3+2 x 4 + xg=36 3 x ≥ g g
0( j=1. .5 ); x , x ≥ 0 j 2 3 Ta có bảng đơn hình: Phươ Hệ số Cơ sở ng -6 14 -5/2 4 0 1 1 Án x x x x x xg xg 1 2 3 4 5 2 3 0 x 72 3 2 -2 0 1 0 0 5 1 xg 60 0 -3 1 2 0 1 0 2 1 xg 36 -4 -3 -2 (2) 0 0 1 3 B1 P(x) 96 -4 -6 -1 [4] 0 0 0 0 x 72 3 2 -2 0 1 0 5 1 xg 24 (4) 0 3 0 0 1 2 0 x 18 -2 -3/2 -1 1 0 0 4 B2 P(x) 24 [4] 0 3 0 0 0 0 x 54 0 2 -17/4 0 1 5 -6 x 6 1 0 3/4 0 0 1 4 x 30 0 -3/2 1/2 1 0 4 B3 F(x) 84 0 -20 0 0 0
Vậy bài toán có patu x* =( 6, 0, 0, 30, 54) với fmin = 84
b/ Thay xo vào các ràng buộc của bài tóan thấy thỏa mãn nên xo là phương án của bài toán.
Ta thấy xo thỏa mãn chặt 2 ràng buộc chính và 1ràng buộc về dấu, ta có hệ : ¿
−3 x 2+x 3+2 x 4=60
−4 x 1−3 x 2−2 x 3+2 x 4=36 x 2=0 ¿ ¿
=> x0 là phương án tối ưu không cực biên của bài toán c/ Bài toán đối ngẫu: g(y)= 72y1 +60y2 +36y3 max 
{ 3y1−4y3≤−6(1)
2 y 1−3 y 2−3 y 3 ≤14 (2)
−2 y 1+ y 2−2 y 3 ≤− 5 (3) 2
2 y 2+2 y 3 ≤ 4 (4 ) y 1 ≤ 0(5)
Các cặp ràng buộc đối ngẫu:
x 1 ≥ 0↔( 1)
x 2 ≥ 0↔( 2)
x 3 ≥ 0 ↔( 3)
x 4 ≥ 0↔(4)
3 x 1+2 x 2−2 x 3 ≤ 72↔(5 )
Ta có xo thỏa mãn lỏng ràng buộc về dấu và 1 ràng buộc chính nên
theo định lí 2 đối ngẫu thì bài toán đối ngẫu có pa y* thỏa mãn chặt
các rb tương ứng, ta có hệ: { y1=0
−3 y 1−4 y 3=−6 2 y 2+2 y 3=4
{y1=01y2=2y3=32
=> y* = (0, ½, 3/2 ) là tập phương án tối ưu của bài toán đối ngẫu.
Ta thấy y* thỏa mãn chặt 1 ràng về dấu và 3 ràng buộc chính nên y*
là phương án cực biên suy biến duy nhất của bài toán đối ngẫu.

Tài liệu liên quan: