Bai Lam Thay Tao1

Trường Đại học Bách Khoa Đà Nẳng Khoa Công nghệ Thông Tin

Bài tập toán chuyên đề

 

Bài 1: Giải các bài toán bằng phương pháp hình học rồi kiểm tra lại bằng phương pháp đơn hình 1 : Tìm f ( x, y ) = x + 2 y → max

với

 3x + y ≤ 6   3x + 4 y ≤ 1 2  x ≥ 0, y ≥ 0  -

Phương pháp hình học

Từ hình vẽ ta thấy f đạt giá trị lớn nhất tại (x,y) = (0,2), giá trị fmax = 6 -

Phương pháp dùng bảng đơn hình

Đặt g(x) = -f(x), f ( x) →max thì g ( x) = −x − 2 y → min Dùng ẩn phụ z,t đưa vào điều kiện ta đưa bài toán về dạng chính tắc Tìm giá trị nhỏ nhất của g ( x, y ) = −x − 2 y với

 3x + y + z + 0t = 6   3x + 4 y + 0 z + t = 1 2  x ≥ 0, y ≥ 0, z ≥ 0, t ≥ 0  Võ Quang Hòa Lớp 07T4 – Nhóm 12B

Trang 1

Trường Đại học Bách Khoa Đà Nẳng Khoa Công nghệ Thông Tin

Bài tập toán chuyên đề



Bảng đơn hình

Hệ số

Ẩn

Phương án

X -1

Y -2

Z 0

T 0

0

z

6

3

1

1

0

0

t

12

3

0

1

0

1

2

0

0

0

1

1

0

0

0

0

Y

6

-2

z

3 -6

4

9 4 3 4 1 − 2

1 4 1 4 1 − 2 −

∆j ≥ 0 với mọi j = 1..6 nên xopt= (0,3,0,0) và gmin=-6 Từ đó suy ra kết quả bài toán gốc là f max = 6 2 : Tìm f ( x) = 5 x − 3 y → min với điều kiện

 x + 2y ≤ 4   x + 3y ≥ 6  x ≥ 0, y ≥ 0 

Với điều kiện trên thì chỉ có 1 điểm thỏa mãn là (0,2) nên tại đó, hiển nhiên f(x) đạt giá trị nhỏ nhất và bằng -6

Võ Quang Hòa Lớp 07T4 – Nhóm 12B

Trang 2

Trường Đại học Bách Khoa Đà Nẳng Khoa Công nghệ Thông Tin

Bài tập toán chuyên đề

 

- Giải bằng phương pháp đơn hình Đặt ẩn phụ z,t ≥ 0 đưa bài toán về dạng chính tắc Tìm giá trị nhỏ nhất của f(x)= 5x – 3y với

 x + 2 y + z + 0t = 4   − x − 3 y + 0z + t = − 6  x, y , z , y ≥ 0  Hệ số

Ẩn

Phương án

X 5

Y -3

Z 0

T 0

0

Z

4

1

2

1

0

0

T

-6

-1

-3

0

1

-5

3

0

0

-3

Y

2

0

T

0 -6

1 2 1 2 13 − 2

1 0 0

1 2 3 2 3 − 2

0 1 0

∆j ≤ 0 với mọi j = 1..6 nên xopt= (0,2,0,0) và fmin=-6 Bài 2 : Giải bài toán bằng phương pháp đơn hình

F(x)=4x1+5x2-3x3 min

 4 x1 + x 2 − 3x1 = 4  4 x − 3x + 5 x = 1 2  1 2 3   x1 + 2 x 2 + 3x3 = 1 0  x j ≥ 0( j = 1..3)  Đặt ẩn phụ z,t,m ≥0 ta biến đổi bài toán về dạng chính tắc F(x)= 4x1+5x2-3x3+Mx4+Mx5+Mx6 min

Võ Quang Hòa Lớp 07T4 – Nhóm 12B

Trang 3

Trường Đại học Bách Khoa Đà Nẳng Khoa Công nghệ Thông Tin

Bài tập toán chuyên đề

 

 4 x1 + x2 − 3x3 + x4 = 4  4 x − 3x + 5x + x = 1 2  1 2 3 5   x1 + 2 x2 + 3x3 + x6 = 1 0  x j ≥ 0( j = 1..6)  Bảng đơn hình

Hệ số

Ẩn

Phương án

X1 4

X2 5

X3 -3

X4 M

X5 M

X6 M

M

X4

4

4

1

-3

1

0

0

M

X5

12

4

-3

5

0

1

0

M

X6

10

1

2

3

0

0

1

26M

9M-4

-5

5M+3

4

X1

1

1

1 4

−

M

X5

8

0

-4

8

M

X6

9

0

17M+4

0

7 4 9M − −4 4 1 − 8 1 − 2 29 8 29 M −6 8

15 4 47 M 4

1

0

0

0

0

1

0

1

0

0

0

0

4

X1

7 4

1

-3

X3

1

0

M

X6

4

X1

-3

X3

5

X2

21 4 21 M+4 4 56 29 50 29 42 29 284 29

Võ Quang Hòa Lớp 07T4 – Nhóm 12B

0 0

0

3 4

0 1 0 0

1 4

0

0

-1

1

0

0

1

−

1 4

9M +1 0 0 4 5 3 0 32 32 1 1 − 0 8 8 7 15 − 1 32 32 25 M 47 M − +1 − +1 0 32 32 19 9 1 116 116 29 11 7 4 − 116 116 29 7 8 15 − 116 116 29 −

-M+

36 29

-M-

15 29

32 -M 29

Trang 4

Trường Đại học Bách Khoa Đà Nẳng Khoa Công nghệ Thông Tin ∆j ≤0 với mọi j = 1..6 nên xopt= (

Võ Quang Hòa Lớp 07T4 – Nhóm 12B

Bài tập toán chuyên đề

 

56 42 50 284 , , ,0,0,0) và fmin= 29 29 29 29

Trang 5

Trường Đại học Bách Khoa Đà Nẳng Khoa Công nghệ Thông Tin

Bài tập toán chuyên đề



Câu 3: Bài toán (D,f) F(x)=6x1+3x2+5x3  min

 3x1 + 2 x 2 + 5x3 ≥ 5  x − 4 x + 3x ≥ − 3  1 2 3   2 x1 + x 2 − 2 x3 ≥ 2  x j ≥ 0( j = 1..3)  a) Viết bài toán đối ngẫu của bài toán (D,f) là

~ ( D, g )

G(x)= 5y1-3y2+2y3  max

 3 y1 + y 2 + 2 y 3 ≤ 6  2 y − 4 y + 1y ≤ 3  1 2 3   5 y1 + 3 y 2 − 2 y 3 ≤ 5  y j ≥ 0( j = 1..3)  b) Giải bài toán đối ngẫu bằng phương pháp đơn hình. Thêm ẩn y4,y5,y6, đặt h(x) =-G(x) ta chuyển bài toán về dạng chuẩn tắc Tìm min của H(x)=-5y1+3y2-2y3

 3 y1 + y2 + 2 y3 + y4 = 6  2y − 4y + y + y = 3  1 2 3 5   5 y1 + 3 y2 − 2 y3 + y6 = 5  y j ≥ 0( j = 1..6)  Bảng đơn hình Hệ số

Ẩn

Phương án

Y1 -5

Y2 3

Y3 -2

Y4 0

Y5 0

Y6 0

0

Y4

6

3

1

2

1

0

0

0

Y5

3

2

-4

1

0

1

0

0

Y6

5

5

3

-2

0

0

1

0

5

-3

2

0

0

0

4 5 26 − 5

16 5 9 5

1

0

0

1

0

Y4

3

0

0

Y5

1

0

Võ Quang Hòa Lớp 07T4 – Nhóm 12B

−

3 5 2 − 5 −

Trang 6

Trường Đại học Bách Khoa Đà Nẳng Khoa Công nghệ Thông Tin -5

Y1

0

Y4

-2

Y3

-5

Y1

Y2

-2

Y3

-5

Y1

1

3 5

-5

0

-6

11 9 5 9 11 9

11 76 37 38 99 76 305 38

∆j ≤0 với mọi j = 1..6 nên yopt= ( nhất của G(y) là −

 

1

5 3

Bài tập toán chuyên đề

76 9 26 − 9 5 − 9 50 9

0 0 1 0

0

0

1 5

4

0

0

-1

0

1

1

0

0

0

0

0

16 9 5 9 2 9 20 − 9 4 − 19 1 − 19 2 19 20 − 19

1 9 2 − 9 1 9 1 − 9 1 76 7 − 38 9 76 7 − 38

−

2 5

0

1

0

0

0

1

1

0

0

0

0

0

9 76 13 38 5 76 25 − 38

−

284 99 11 37 , , ,0,0,0) và H(x) min= ( ≈ 097931 ) vậy giá trị lớn 76 76 38 29

284 29

c) Áp dụng nguyên lý độ lệch bù để tìm nghiệm của bài toán (D,f) o Ta thấy 99 >0 nên 5X1+2X2+4X3=5 76 11 Y2= >0 nên X1-4X2+3X3=-3 76 37 Y3= >0 nên 2X1+X2-2X3=2 38

Y1=

Giải hệ



25



38

 3x1 + 2 x2 + 5 x3 = 5  x1 = 3 8  x − 4 x + 3x = − 3   1 2 3  20 Ta được  x2 =   19  2 x1 + x2 − 2 x3 = 2 7   x j ≥ 0( j = 1..3) x =   3 o Mặt khác 25 >0 nên phải có 2Y1+Y2+Y3=6 39 20  X2= >0 nên phải có 2Y1-4Y2+Y3=3 19

 X1=

Võ Quang Hòa Lớp 07T4 – Nhóm 12B

Trang 7

Trường Đại học Bách Khoa Đà Nẳng Khoa Công nghệ Thông Tin  X3=

Bài tập toán chuyên đề

 

7 >0 nên phải có 5 y1 + 3 y 2 − 2 y 3 = 5 38

Các điều kiện này đúng vì Y1,Y2,Y3 thực sự là nghiệm của hệ

 3 y1 + y2 + 2 y3 = 6   2 y1 − 4 y2 + y3 = 3  5y + 3y − 2 y = 5  1 2 3 Vậy (D,f) có nghiệm đối ngẫu với Câu 3 : Giải bài toán vận tải 1 bj ai

~ ( D, g ) là

(X1,X2,X3)=(

25 20 7 , , ) 39 19 38

90

70

65

75

120

9

3

5

7

80

5

2

8

6

100

6

3

4

2

bj

90

70

120

80

+

80

10

ai

3

9

100

65

2

6

3

Vi

5

7

0

8

6

4

25

75

4

2

6

5

3

90

70

65

75

120

10

70

40

80

80

Ui

9

40

70

5

75

1

F(x)=1360 bj ai

100 Ui

Võ Quang Hòa Lớp 07T4 – Nhóm 12B

3

5

7

0

5

2

8

6

4

6

3

9

0

+

9

Vi

3

25

75

4

5

2

1

3 Trang 8

Trường Đại học Bách Khoa Đà Nẳng Khoa Công nghệ Thông Tin

Bài tập toán chuyên đề

 

F(x)=1150

Võ Quang Hòa Lớp 07T4 – Nhóm 12B

Trang 9

Trường Đại học Bách Khoa Đà Nẳng Khoa Công nghệ Thông Tin

bj

Bài tập toán chuyên đề



90

70

65

120

0

70

50

80

80

100

10

Ui

7

ai

9 5

Vi

3

5

7

0

2

8

6

2

15

3

6

75

75

4

3

1

2

5

3

F(x)min=1130 2: bj

30

20

50

30

35

2

8

6

2

25

5

2

1

3

50

9

5

4

6

30

20

50

30

35

2

8

6

2

25

5

2

1

3

50

9

5

4

6

20

0

0

0

0

ai

Bổ sung trạm phát a4 có trọng tải là 20 bj ai

Võ Quang Hòa Lớp 07T4 – Nhóm 12B

Trang 10

Trường Đại học Bách Khoa Đà Nẳng Khoa Công nghệ Thông Tin

Bài tập toán chuyên đề



Giải bj ai 35

30

30

25 50

50

2

8

5

2

9

20 Ui

20

6

20

2

5

3

1

25

5

4

0

0

4

Vi

5

25

0

6

30

5 6

20 0

4 3 0 6

6

F(x)min=325

Võ Quang Hòa Lớp 07T4 – Nhóm 12B

Trang 11