Trường Đại Học Công Nghiệp TP Hồ Chí Minh
Bài 1: Giải bài tập quy hoạch tuyến tính bằng phương pháp đơn hình
Giải
f(x) = x
1
- 2x
2
+ 2x
3
+0 x
4
 min
x
j
≥ 0, j = 1 4
Ta có cơ sở đơn vị là: {}.
Ta có bảng đơn hình sau:
Cơ sở Hệ
Số
Phương
án
1 -2 2 0
x
1
x
2
x
3
x
4
A

5
 min
x
j
≥ 0, j = 1 ,5
Trong hệ ràng buộc đã có sẵn cơ sở đơn vị
Cơ sở Hệ số Phương
án
-5 -4 0 0 2
x
1
x
2
x
3
x
4
x
5
A
1
A
2
A
3
-4
-5
0
10
12

4
+ 0x
5
+0x
6
 min
x
j
≥ 0, j = 1 ,5
Giải
Trong hệ ràng buộc đã có cơ sở đơn vị (A
5
, A
6
, A
4
)
Phương án cực biên ban đầu x = (0, 0, 0, 4, 3, 3)
Ta lập bảng đơn hình
Cơ
Sở
Hệ
Số
Phương
án
-2 -4 1 -1 0 0
x
1
x
2

0
1
1
0
0
0
1
0
f(x) -3 2 3 -5 0 0 0
A
2
A
6
A
4
-4
0
-1
4/3
5/3
5/3
1/3
5/3
-1/3
1
0
0
0
-1
4

19/5
0
0
1
2/5
-1/5
-2/5
-1/5
3/5
1/5
f(x) -8 0 0 -22/5 0 -4/5 -3/5
Đã xuất hiện dấu hiệu tối ưu
Phương án tối ưu là x=(1, 1, 0, 2, 0, 0)
Giá trị tối ưu; f(x) = -8
Bài 4:Giải bài tập quy hoạch tuyến tính bằng phương pháp đơn hình
f(x) = x
1
- x
2
+ 2x
3
– 2x
4
- 3x
6
 min
x
j
≥ 0, j = 1 ,6
Giải

1
-1
0
A
1
A
2
A
5
2
12
9
1
0
0
0
1
0
1
0
4
1
1
2
0
0
1
-1
1
3

5
f(x) -14 -2 0 -3 0 0 3
-1
2
0
A
2
A
3
A
5
3
8
1
0,6
-0,2
-0,4
0
1
0
1,4
-1,8
0,4
1
0
0
0,2
-0,4
0,2
0

)
Phương án cực biên ban đầu: x = (5, 3, 5, 0, 0, 0)
Bảng đơn hình
Cơ
Sở
Hệ
Số
Phương
án
-1 1 -1 -1 2 2
x
1
x
2
x
3
x
4
x
5
x
6
A
1
A
2
A
5
-1
1

1
+ 3x
2
- x
3
 min
x
j
≥ 0, j = 1 ,3
Giải
Ta đưa bài toán về dạng chính tắc:
f(x) = -2x
1
+ 3x
2
- x
3
+ 0x
4
+ 0x
5
+ 0x
6
 min
x
j
≥ 0, j = 1 ,6
Trong hệ ràng buộc đã có sẵn cơ sở đơn vị (A
4
, A

15
20
10
1
3
4
-5
2
0
1
-2
1
1
0
0
0
1
0
0
0
1
f(x) 0 2 -3 1 0 0 0
A
4
A
5
A
1
0
0

0
-1
5
40
10
-3
11
4
-5
2
0
0
0
1
1
0
0
0
1
0
-1
2
1
f(x) -10 -2 -3 0 0 0 -1
Đã xuất hiện dấu hiệu tối ưu:
Phương án tối ưu là x=(0,0,10,5,40,0)
Giá trị tối ưu; f(x) = -10
NHÓM: 10 Trang 4
Trường Đại Học Công Nghiệp TP Hồ Chí Minh
Bài 7: Giải bài tập quy hoạch tuyến tính bằng phương pháp đơn hình

1
A
3
1
2
6
8
1
0
1
2
0
1
4
5
f(x) 0 7 0 14
A
4
A
3
0
2
3/2
1/2
1/4
-5/4
1/4
3/4
0
1

0
1
-1/2
1/2
3/2
5/2
f(x) -6 0 0 -7/2 -7/2
Đã xuất hiện phương án tối ưu
Phương án tối ưu là x=(2, 4, 0, 0)
Giá trị tối ưu; f(x) = - 6
Bài 8: Giải bài tập quy hoạch tuyến tính bằng phương pháp đơn hình
f(x) = 2x
1
+ 3x
2
+ x
3
 max
x
j
≥ 0, j = 1 ,3
Giải
NHÓM: 10 Trang 5
Trường Đại Học Công Nghiệp TP Hồ Chí Minh
Ta đưa bài toán về dạng chính tắc:
f(x) = 2x
1
+ 3x
2
+ x

4
x
5
x
6
A
4
A
5
A
6
0
0
0
6
7
5
1
2
-1
-5
2
2
1
-2
1
1
0
0
0

0
1
0
5/2
-1
1/2
f(x) 15 -7/2 0 1/2 0 0 3/2
A
4
A
1
A
2
0
2
3
39/2
2/3
17/6
0
1
0
0
0
1
2
-1
0
1
0

1/2
0
1/4
7/12
1/6
1
2/3
1/3
f(x) 469/12 0 0 0 3/2 23/12 10/3
Đã xuất hiện phương án tối ưu
Phương án tối ưu là x=(125/12, 17/6, 39/4, 0, 0, 0)
Giá trị tối ưu; f(x) = 469/12
Bài 9:Giải bài tập quy hoạch tuyến tính bằng phương pháp đơn hình
f(x) = 2x
1
+ x
2
+ x
3
+ 3x
4
 max
x
j
≥ 0, j = 1 ,4
Giải
Ta đưa bài toán về dạng chính tắc:
f(x) = 2x
1
+ x

4
x
5
A
1
A
5
2
0
16
8
1
0
2
1
1
4
0
2
0
1
f(x) 32 0 3 1 -3 0
A
1
A
4
2
3
16
4

1
- 4x
2
+ x
3
+ x
4
 min
x
j
≥ 0, j = 1 ,6
Trong hệ ràng buộc đã có cơ sở đơn vị (A
5
, A
6
, A
4
)
Phương án cực biên ban đầu x = (0, 0, 0, 4, 3, 3)
Ta lập bảng đơn hình
Cơ sở Hệ số Phương
án
-2 -4 1 1 0 0
x
1
x
2
x
3
x

f(x) 3 2 6 3 0 0 0
A
2
A
6
A
4
-4
0
1
4/3
5/3
1/3
1/3
5/3
-2/3
1
0
0
0
-1
4
0
0
1
1/3
-1/3
-2/3
0
1

1
0
f(x) -21/4 ½ 0 0 -3/4 -9/6 0
A
2
A
1
A
3
-4
-2
1
26/27
10/9
29/108
0
1
0
1
0
0
0
0
1
-1/18
1/6
5/18
11/27
-2/9
-11/54

- M(x
7
+ x
8
) max
x
j
≥ 0, j = 1 ,8
Trong hệ ràng buộc đã có cơ sở đơn vị
Ta lập bảng đơn hình
Cơ sở Hệ số Phương
án
1 -7 -2 6 0 0 -M -M
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
A

2
-M
-7
1
3
-1/5
2/5
0
1
2/5
1/5
-7/5
4/5
-1
0
3/5
-1/5
1
0
-3/5
1/5
1/5 0 -2/5 7/5 1 -3/5 0 8/5
-19/5 0 3/5 -58/5 0 7/5 0 -7/5
A
6
A
2
0
-7
5/3

3
3
1
0
1
-4
-1
1
0
4
1
-1
0
60 0 0 0 0 0 0 1 1
5 25 8 0 -6 0 -6 1
Vậy bài toan này không có phương án tối ưu
Bài 12:Giải bài tập quy hoạch tuyến tính bằng phương pháp đơn hình
f(x) = 4x
1
+ 6x
2
+ 5x
3
+ 3x
4
 min
x
j
≥ 0, j = 1 ,4
Giải

2
x
3
x
4
x
5
x
6
x
7
x
8
A
7
A
8
M
M
5
3
1
1
1
4
3
2
2
1
-1

1/3
0
1
1/3
2/3
-2/3
-1/3
1
0
2/3
1/3
-1
0
0 0 0 0 0 0 -1 -1
-7/3 -13/3 0 1/3 -5/3 0 5/3 0
A
4
A
3
3
5
1
1
-1
1
-10
7
0
1
1

3
+ 0x
4
+ 0x
5
 min
x
j
≥ 0, j = 1 ,5
Trong hệ ràng buộc đã có cơ sở đơn vị (A
3
, A
4
, A
5
)
Phương án cực biên ban đầu x = ( 0, 0, 0, 3, 2, 7)
Ta lập bảng đơn hình
Cơ sở Hệ số Phương
án
15 19 0 0 0
x
1
x
2
x
3
x
4
x

Phương án tối ưu là x= (0, 0, 3, 2, 7)
NHÓM: 10 Trang 10
Trường Đại Học Công Nghiệp TP Hồ Chí Minh
Giá trị tối ưu; f(x) = 0
Bài 14:Giải bài tập quy hoạch tuyến tính bằng phương pháp đơn hình
f(x) = 2x
1
+ x
2
+ x
3
+ 3x
4
 max
x
j
≥ 0, j = 1 ,4
Giải
Ta đưa bài toán về dạng chính tắc:
f(x) = 2x
1
+ x
2
+ x
3
+ 3x
4
 max
x
j

6
2
0
0
16
8
20
1
0
0
-2
2
1
1
4
2
0
1
3
0
1
0
0
0
1
f(x) 32 0 -5 1 -3 0 0
A
1
A
2

Bài 15:Giải bài tập quy hoạch tuyến tính bằng phương pháp đơn hình
f(x) = 3x
1
+ 3x
2
+ 2x
3
+ 7x
4
 max
x
j
≥ 0, j = 1 ,5
Giải
Ta đưa bài toán về dạng chính tắc:
NHÓM: 10 Trang 11
Trường Đại Học Công Nghiệp TP Hồ Chí Minh
f(x) = 3x
1
+ 3x
2
+ 2x
3
+ 7x
4
+ 0x
5
+ 0x
6
+ 0x

6
A
7
0
0
15
19
3
1
2
2
1
1
3
4
2
1
1
0
0
1
f(x) 0 -3 -3 -2 -7 0 0 0
A
6
A
4
0
7
3/4
19/4

1
5/9
1/9
0
0
-1/3
1/3
f(x) 101/3 0 7/9 -1/9 0 22/9 0 4/3
A
3
A
4
2
7
3
4
9
-2
2
0
1
0
0
1
5
-1
0
0
-3
1

4
)
NHÓM: 10 Trang 12
Trường Đại Học Công Nghiệp TP Hồ Chí Minh
Phương án cực biên ban đầu x = (0, 0, 54, 12)
Ta lập bảng đơn hình
Cơ sở Hệ số Phương án -3 -6 0 0
x
1
x
2
x
3
x
4
A
3
A
4
0
0
54
12
9
-3
6
4
1
0
0

1
2/27
1/18
-1/9
1/6
f(x) -108/3 0 0 -5/9 -2/3
Đã xuất hiện phương án tối ưu
Phương án tối ưu là x= (8/3, 5, 0, 0 )
Giá trị tối ưu; f(x) = -108/3
Bài 17: Giải bài tập quy hoạch tuyến tính bằng phương pháp đơn hình
f(x) = 5x
1
+ 4x
2
+ 5x
3
+ 2x
4
+x
5
+ 3x
6
 min
x
j
≥ 0, j = 1 ,6
Giải
Trong hệ ràng buộc đã có cơ sở đơn vị (A
4
, A

150
60
36
2
4
1
4
2
0
3
3
1
1
0
0
0
1
0
0
0
1
f(x) 468 6 6 7 0 0 0
A
4
A
3
A
6
2
5

4
3
50
30
36
-6
2
1
0
1
0
-3
3/2
1
1
0
0
-2
1/2
0
0
0
1
NHÓM: 10 Trang 13
Trường Đại Học Công Nghiệp TP Hồ Chí Minh
f(x) 328 -6 0 -2 0 -3 0
Đã xuất hiện phương án tối ưu
Phương án tối ưu là x= (0, 30, 0, 50, 0, 36 )
Giá trị tối ưu; f(x) = 328
Bài 18: Giải bài tập quy hoạch tuyến tính bằng phương pháp đơn hình

, A
5
, A
6
)
Phương án cực biên ban đầu x = (0, 0, 0, 3, 7, 10)
Ta lập bảng đơn hình
Cơ sở Hệ số Phương
án
2 -4 1 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
A
4
A
5
A
6
0
0

0
0
3/2
11/2
5/2
1/2
-9/2
-5/2
1
0
0
2
-5
8
1/2
-1/2
-5/2
0
1
0
0
0
1
f(x) -6 -4 0 -9 -2 0 0
Đã xuất hiện phương án tối ưu
Phương án tối ưu là x= (0, 3/2, 0, 0, 11/2, 5/2)
Giá trị tối ưu; f(x) = -6
Bài 19: Giải bài tập quy hoạch tuyến tính bằng phương pháp đơn hình
NHÓM: 10 Trang 14
Trường Đại Học Công Nghiệp TP Hồ Chí Minh

)
Phương án cực biên ban đầu x = (0, 0, 8, 5, 36,)
Ta lập bảng đơn hình
Cơ sở Hệ số Phương
án
50 60 0 0 0
x
1
x
2
x
3
x
4
x
5
A
3
A
4
A
5
0
0
0
8
5
36
1
1

0
0
½
-1/2
-2
0
1
0
0
0
1
f(x) 240 -20 0 30 0 0
A
2
A
1
A
5
60
50
0
3
2
6
0
1
0
1
0
0

+ x
2
- x
3
+ M(x
5
+ x
6
+ x
7
)

 min
x
j
≥ 0, j = 1 ,7
Trong hệ ràng buộc đã có cơ sở đơn vị (A
6
, A
5
, A
7
)
Phương án cực biên ban đầu x = (0, 0, 0, 0, 10, 12, 20,)
Ta lập bảng đơn hình
Cơ sở Hệ số Phương
án
2 -1 -1 0 0 M M
x
1

-1
0
0
0
1
0
1
0
0
0
0
1
f(x) 32M -3M -2 -3M-1 3/2M+1 -M 0 0 0
A
3
A
5
A
7
-1
0
M
6
16
23
-2
-4
0
-1/2
3/2

Giải
Ta đưa bài toán về dạng chính tắc
f(x) = -3x
1
- 2x
2
- 4x
3
+ 0x
4
+ 0x
5
 min
x
j
≥ 0, j = 1 ,5
Trong hệ ràng buộc đã có cơ sở đơn vị (A
6
, A
5
, A
7
)
Phương án cực biên ban đầu x = (0, 0, 0, 8, 10, 13)
Ta lập bảng đơn hình
Cơ sở Hệ số Phương -3 -2 4 0 0
NHÓM: 10 Trang 16
Trường Đại Học Công Nghiệp TP Hồ Chí Minh
án x
1

1
0
0
0
1
f(x) -32 -5 -2 0 0 0
Đã xuất hiện phương án tối ưu
Phương án tối ưu là x=(0, 0, 8, 10, 13 )
Giá trị tối ưu; f(x) = -32
Bài 22: Giải bài tập quy hoạch tuyến tính bằng phương pháp đơn hình
f(x) = -4x
1
+ 5x
2
- 3x
3
 min
x
j
≥ 0, j = 1 ,3
Giải
Ta đưa bài toán về dạng chính tắc
f(x) = -4x
1
+ 5x
2
- 3x
3
+ 0x
4

x
6
A
4
A
5
A
6
0
0
0
9
16
12
2
1
2
-3
4
1
-2
-4
3
1
0
0
0
1
0
0

0
0
1
f(x) -18 0 1 7 -2 0 0
A
1
A
5
A
3
-4
0
-3
51/10
133/10
3/5
1
0
0
-7/10
97/10
4/5
0
0
1
1/5
-11/10
-1/5
0
1

4
+ 0x
5
+ 0x
6
 max
x
j
≥ 0, j = 1 ,6
Trong hệ ràng buộc đã có cơ sở đơn vị (A
4
, A
5
, A
6
)
Phương án cực biên ban đầu x = (0, 0, 0, 6, 9, 7)
Ta lập bảng đơn hình
Cơ sở Hệ số Phương
án
1 2 3 0 0 0
x
1
x
2
x
3
x
4
x

0
0
1
f(x) 0 -1 -2 -3 0 0 0
A
4
A
3
A
6
0
3
0
1/2
9/2
5/2
1/3
3/2
5/2
-4
2/2
-1
0
1
0
1
0
0
-1/2
1/2

4
+ 0x
5
+ 0x
6
 min
NHÓM: 10 Trang 18
Trường Đại Học Công Nghiệp TP Hồ Chí Minh
x
j
≥ 0, j = 1 ,6
Trong hệ ràng buộc đã có cơ sở đơn vị ( A
5
, A
6
)
Phương án cực biên ban đầu x = (0, 0, 0, 0, 7, 5)
Ta lập bảng đơn hình
Cơ sở Hệ số Phương
án
2 4 3 1 0 0
x
1
x
2
x
3
x
4
x

- 5x
2
- 4x
3
+ 2x
4
 max
x
j
≥ 0, j = 1 ,4
Giải
Ta đưa bài toán về dạng chính tắc
f(x) = 3x
1
- 5x
2
- 4x
3
+ 2x
4
+ 0x
5
+ 0x
6
 max
x
j
≥ 0, j = 1 ,6
Trong hệ ràng buộc đã có cơ sở đơn vị ( A
5

5
3
3
2
1
2
1
0
0
1
f(x) 0 -3 5 4 -2 0 0
A
1
A
6
3
0
6
9
1
0
5/2
½
3/2
1/2
½
3/2
½
-1/2
0

2
- 5x
3
+ 0x
4
+ 0x
5
+ 0x
6
 min
x
j
≥ 0, j = 1 ,6
Trong hệ ràng buộc đã có cơ sở đơn vị (A
4
, A
5
, A
6
)
Phương án cực biên ban đầu x = (0, 0, 0, 8, 9, 15)
Ta lập bảng đơn hình
Cơ sở Hệ số Phương
án
-2 3 -5 0 0 0
x
1
x
2
x

0
0
1
0
0
0
1
f(x) 0 2 -3 5 0 0 0
A
4
A
5
A
3
0
0
-5
28
4
5
14/3
10/3
2/3
5/3
-2/3
-1/3
0
0
1
1

Trong hệ ràng buộc đã có cơ sở đơn vị (A
1
, A
2
, A
3
)
Phương án cực biên ban đầu x = (2, 12, 9, 0, 0, 0)
Ta lập bảng đơn hình
Cơ sở Hệ số Phương
án
1 -1 0 -2 2 -3
x
1
x
2
x
3
x
4
x
5
x
6
A
1
A
2
A
3

3
-2
-1
0
2
10
5
1
-1
-2
0
1
0
0
0
1
1
0
0
1
-1
2
-1
2
5
f(x) -14 -2 0 0 0 -3 3
A
4
A
2

Bài 28: Giải bài tập quy hoạch tuyến tính bằng phương pháp đơn hình
f(x) = x
2
- 3x
3
+ 2x
5
 min
x
j
≥ 0, j = 1 ,6
Giải
Trong hệ ràng buộc đã có cơ sở đơn vị (A
1
, A
4
, A
6
)
Phương án cực biên ban đầu x = (7, 0, 0,12, 0, 10)
Ta lập bảng đơn hình
Cơ sở Hệ số Phương
án
0 1 -3 0 2 0
x
1
x
2
x
3

0 10 0 -5 3 0 1 1
f(x) 0 0 -1 3 0 -2 0
A
1
A
3
A
6
0
-3
0
10
3
1
1
0
0
0
-1
-2
0
1
0
1/4
1/4
1/4
1
0
1
0

x
2
x
3
x
4
x
5
x
6
A
4
A
5
A
6
0
0
0
7
10
12
-1
3
4
3
-4
-2
1
8

8
0
1
0
0
0
1
0
1/4
-3/4
1/4
f(x) -9 0 ½ -2 0 0 -3/4
A
2
A
5
A
1
1
0
-3
4
11
5
0
0
1
1
0
0

lãi là lớn nhất:
Biết rằng là 40 triệu đồng cho một đơn vị sản phẩm loại A, 41 triệu đồng cho một
đơn vị sản phẩm loại B, 47 triệu đồng cho một đơn vị sản phẩm loại C.
Giải
Gọi x
1
, x
2
, x
3
lần lượt là số đơn vị sản phẩm A, B, C theo bài ra ta có bài toán quy
hoạch tuyến tính
f(x) = 40x
1
+ 41x
2
+ 47x
3
 max
x
j
≥ 0, j = 1 ,3
Từ bài toán trên ta có bài toán phụ:
f(x) = 40x
1
+ 41x
2
+ 47x
3
+ 0x

x
5
x
6
A
4
A
5
A
6
0
0
0
57
88
52
4
1
3
2
6
2
3
5
3
1
0
0
0
1

1
0
f(x) 2444/3 7 -29/9 0 0 0
A
4
A
2
A
3
0
41
47
5
1/2
51/3
1
-3/2
2
0
1
0
0
0
1
1
0
0
f(x) 4917/3 -15/2 0 0 0
A
1

 max
x
j
≥ 0, j = 1 ,3
Giải
Ta đưa bài toán về dạng chính tắc
f(x) = 20x
1
+ 21x
2
+ 45x
3
+ 0x
4
+ 0x
5
+ 0x
6
 max
x
j
≥ 0, j = 1 ,6
Trong hệ ràng buộc đã có cơ sở đơn vị (A
4
, A
5
, A
6
)
Phương án cực biên ban đầu x = (0, 0, 0, 55, 66, 42)

3
4
2
5
3
0
0
1
0
0
1
f(x) 0 -20 -21 -45 0 0 0
A
4
A
3
A
6
0
45
0
77/5
66/5
12/5
2/5
1/5
12/5
-2/5
4/5
-2/5

-1/6
0
1
0
1
0
0
-1/2
1/4
-1/4
-1/6
-1/12
5/12
f(x) 605 0 79/6 0 0 25/4 55/72
Đã xuất hiện phương án tối ưu
Phương án tối ưu là x=(1, 0, 13, 15, 0, 0)
Giá trị tối ưu; f(x) = 605
Bài 32: Giải bài tập quy hoạch tuyến tính bằng phương pháp đơn hình
f(x) = -2x
1
- 6x
2
+ x
3
– 3x
4
 min
x
j
≥ 0, j = 1 ,3

x
1
x
2
x
3
x
4
x
5
x
6
A
5
A
6
A
4
0
0
-3
5
4
3
1
2
0
4
2
1

0
0
-1
3
0
0
1
1/4
-1/2
-1/4
0
1
0
NHÓM: 10 Trang 25