Giáo trình Quy hoạch tuyến tính - Chương 2: Giải thuật đơn hình

 được thực hiện giống như phương pháp hai pha. 
IV- QUY HOẠCH TUYẾN TÍNH SUY BIẾN 
 Khi thực hiện thuật toán đơn hình trường hợp bất thường có thể xảy ra là khi 
xác định biến ra thì tồn tại tỷ số 0
a
b
ik
i = , tức là tồn tại bi=0, hay không có tỷ số nào 
dương thật sự. Người ta xem đây là trường hợp suy biến. Khi một bảng đơn hình rơi 
vào tình trạng suy biến thì có thể gây khó khăn mà cũng có thể không khi ta tiếp tục 
thực hiện thuật toán đơn hình. 
1- Các ví dụ về quy hoạch tuyến tính suy biến 
Ví dụ 1 : xét quy hoạch tuyến tính : 
0x,x
0x2
6x3
2x2x
xx7z(x) min
21
1
1
21
21
≥
⎪⎩
⎪⎨
⎧
≤−
≤−
≤−
−+=
Đưa bài toán về dạng chuẩn : 
0x,x
0xx2
6xx3
2xx2x
xx7z(x) min
21
51
41
321
21
≥
⎪⎩
⎪⎨
⎧
=+−
=+−
=+−
−+=
với ma trận hệ số là : 
GIẢI THUẬT ĐƠN HÌNH 
59 
x1 x2 x3 x4 x5 b 
1 -2 1 0 0 2 
-3 0 0 1 0 6 
-2 0 0 0 1 0 
có chứa ma trận đơn vị. Áp dụng thuật toán đơn hình cải tiến ta được : 
cB iB x1 x2 x3 x4 x5 b 
0 3 1 -2 1 0 0 2 
0 4 -3 0 0 1 0 6 
0 5 -2 0 0 0 1 0 
Tc 1 -1 0 0 0 
T
c 1 -1 0 0 0 
w=7 
Đây là trường hợp suy biến, biến vào là x2, nó được tăng lên đến mức vẫn thỏa 
những điều kiện về dấu của các biến trong cơ sở x3, x3, x5 . Đó là : 
⎪⎩
⎪⎨
⎧
≥+=
≥+=
≥+=
0x00x
0x06x
0x22x
23
24
23
 ⇔ 
⎪⎪⎩
⎪⎪⎨
⎧
≥∀
≥∀
−≥
0x
0x
2
2
x
2
2
2
Như vậy x2 có thể lớn tùy ý nên hàm mục tiêu không bị giới nội. Vậy bài toán 
không có phương án tối ưu. Trường hợp này ở bảng đơn hình không có tỷ số nào 
dương thật sự để xác định biến ra. 
Ví dụ 2 : xét quy hoạch tuyến tính : 
0x,x
0x2
6x3
2x2x
xx7z(x) min
21
1
1
21
21
≥
⎪⎩
⎪⎨
⎧
≤−
≤−
≤+
−+=
Đưa bài toán về dạng chuẩn : 
0x,x
0xx2
6xx3
2xx2x
xx7z(x) min
21
51
41
321
21
≥
⎪⎩
⎪⎨
⎧
=+−
=+−
=++
−+=
với ma trận hệ số là : 
GIẢI THUẬT ĐƠN HÌNH 
60 
x1 x2 x3 x4 x5 b 
1 2 1 0 0 2 
-3 0 0 1 0 6 
-2 0 0 0 1 0 
có chứa ma trận đơn vị. Áp dụng thuật toán đơn hình cải tiến ta được : 
cB iB x1 x2 x3 x4 x5 b 
0 3 1 2 1 0 0 2 
0 4 -3 0 0 1 0 6 
0 5 -2 0 0 0 1 0 
Tc 1 -1 0 0 0 
T
c 1 -1 0 0 0 
w=7 
cB iB x1 x2 x3 x4 x5 b 
-1 2 
2
1 1 
2
1 0 0 1 
0 4 -3 0 0 1 0 6 
0 5 -2 0 0 0 1 0 
Tc 1 -1 0 0 0 
T
c 2
3 0 
2
1 0 0 
w=6 
Đây là bảng đơn hình tối ưu. 
 Ví dụ 3 : xét quy hoạch tuyến tính : 
0x,x,x
0xxx
1x
2
1
x
2
1
x
2
3
x2x
2
1
-3w(x) min
321
321
31
321
≥
⎪⎩
⎪⎨
⎧
≤−+−
≤+
+−+=
Đưa bài toán về dạng chuẩn : 
0x,x,x,x,x
0xxxx
1xx
2
1
x
2
1
x
2
3
x2x
2
1
-3w(x) min
54321
5321
431
321
≥
⎪⎩
⎪⎨
⎧
=+−+−
=++
+−+=
với ma trận hệ số : 
GIẢI THUẬT ĐƠN HÌNH 
61 
x1 x2 x3 x4 x5 b 
2
1 0 
2
1 1 0 1 
-1 1 1 0 1 0 
có chứa ma trận đơn vị . Áp dụng giải thuật đơn hình cải tiến : 
cB iB x1 x2 x3 x4 x5 b 
0 4 
2
1 0 
2
1 1 0 1 
0 5 -1 1 1 0 1 0 
Tc 
2
1 -2 
2
3 0 0 
T
c 2
1 -2 
2
3 0 0 
w=-3 
x2 vào , x5 ra 
cB iB x1 x2 x3 x4 x5 b 
0 4 
2
1 0 
2
1 1 1 
-2 2 -1 1 -1 0 0 
Tc 
2
1 -2 
2
3 0 0 
T
c 2
3− 0 
2
1− 0 2 
w=-3 
x1 vào , x4 ra 
cB iB x1 x2 x3 x4 x5 b 
2
1 1 1 0 1 2 0 2 
-2 2 0 1 0 2 1 2 
Tc 
2
1 -2 
2
3 0 0 
T
c 0 0 1 3 2 
w=-6 
Đây là bảng đơn hình tối ưu 
Ví dụ 4 : xét quy hoạch tuyến tính 
GIẢI THUẬT ĐƠN HÌNH 
62 
0x,x,x,x
1x
0xx5,0x5,1x5,0
0x9x5,2x5,5x5,0
x24x9x57x10z(x) min
4321
1
4321
4321
4321
≥
⎪⎩
⎪⎨
⎧
≤
≤+−−
≤+−−
+++−=
 Đưa bài toán về dạng chuẩn 
0x,x,x,x,x,x,x
1xx
0xxx5,0x5,1x5,0
0xx9x5,2x5,5x5,0
x24x9x57x10w(x) min
7654321
71
64321
54321
4321
≥
⎪⎩
⎪⎨
⎧
=+
=++−−
=++−−
+++−=
với ma trận hệ số 
x1 x2 x3 x4 x5 x6 x7 b 
0,5 -5,5 -2,5 9 1 0 0 0 
0,5 -1,5 -0,5 1 0 1 0 0 
1 0 0 0 0 0 1 1 
có chứa ma trận đơn vị . Áp dụng phương pháp đơn hình cải tiến 
cB iB x1 x2 x3 x4 x5 x6 x7 b 
0 5 0,5 -5,5 -2,5 9 1 0 0 0 
0 6 0,5 -1,5 -0,5 1 0 1 0 0 
0 7 1 0 0 0 0 0 1 1 
Tc -10 57 9 24 0 0 0 
T
c -10 57 9 24 0 0 0 
w=0 
x1 vào , x5 ra 
cB iB x1 x2 x3 x4 x5 x6 x7 b 
-10 1 1 -11 -5 18 2 0 0 0 
0 6 0 4 2 -8 -1 1 0 0 
0 7 0 11 5 -18 -2 0 1 1 
Tc -10 57 9 24 0 0 0 
T
c 0 -53 -41 204 20 10 0 
w=0 
x2 vào , x6 ra 
cB iB x1 x2 x3 x4 x5 x6 x7 b 
-10 1 1 0 0,5 -4 -0,75 2,75 0 0 
57 2 0 1 0,5 -2 -0,25 0,25 0 0 
0 7 0 0 -0,5 4 0,75 -2,75 1 1 
Tc -10 57 9 24 0 0 0 
T
c 0 0 -14,5 98 6,75 13,25 0 
w=0 
x3 vào , x1 ra 
cB iB x1 x2 x3 x4 x5 x6 x7 b 
GIẢI THUẬT ĐƠN HÌNH 
63 
9 3 2 0 1 -8 -1,5 5,5 0 0 
57 2 -1 1 0 2 0,5 -2,5 0 0 
0 7 1 0 0 0 0 0 1 1 
Tc -10 57 9 24 0 0 0 
T
c 29 0 0 -18 -15 93 0 
w=0 
x4 vào , x2 ra 
cB iB x1 x2 x3 x4 x5 x6 x7 b 
9 3 -2 4 1 0 0,5 -4,5 0 0 
24 4 -0,5 0,5 0 1 0,25 -1,25 0 0 
0 7 1 0 0 0 0 0 1 1 
Tc -10 57 9 24 0 0 0 
T
c 20 9 0 0 -10,5 70,5 0 
w=0 
x5 vào , x3 ra 
cB iB x1 x2 x3 x4 x5 x6 x7 b 
0 5 -4 8 2 0 1 -9 0 0 
24 4 0,5 -1,5 -0,5 1 0 1 0 0 
0 7 1 0 0 0 0 0 1 1 
Tc -10 57 9 24 0 0 0 
T
c -22 93 21 0 0 -24 0 
w=0 
x6 vào , x4 ra 
cB iB x1 x2 x3 x4 x5 x6 x7 b 
0 5 0,5 -5,5 -2,5 9 1 0 0 0 
0 6 0,5 -1,5 -0,5 1 0 1 0 0 
0 7 1 0 0 0 0 0 1 1 
Tc -10 57 9 24 0 0 0 
T
c -10 57 9 24 0 0 0 
w=0 
 Bảng đơn hình hiện thời giống với bảng đơn hình xuất phát : đây là hiện tượng 
xoay vòng . 
2- Xử lý trường hợp suy biến 
 Theo các ví dụ trên, trong trường hợp quy hoạch tuyến tính suy biến thì sau 
một số lần lặp có thể phương án nhận được vẫn như cũ mà không có sự thay đổi nào, 
có thể phương án nhận được tốt hơn, có thể phương án nhận được là một phương án 
đã nhận trước đó rồi và từ đó cứ xoay vòng mãi. Do đó nếu không có biện pháp phòng 
ngừa thì thuật toán đơn hình sẽ có thể kéo dài vô tận. 
 Khi thực hiện thuật toán đơn hình thì hiện tượng suy biến xảy ra khi có sự tình 
cờ khử lẫn nhau làm cho tồn tại ib nào đó bằng 0. Trong trường hợp này có thể có 
nhiều biến thỏa điều kiện của biến ra. Gặp trường hợp này cần phải lựa chọn biến ra 
sao cho tránh được hiện tượng xoay vòng. 
GIẢI THUẬT ĐƠN HÌNH 
64 
 Người ta thường dùng phương pháp nhiễu loạn, phương pháp từ vựng để tránh 
sự tình cờ khử lẫn nhau này. Trong thực tiển tính toán người ta đã đề ra một quy tắc 
xử lý khá đơn giản, gọi là quy tắc Bland, khi dùng giải thuật đơn hình giải các quy 
hoạch tuyến tính suy biến, đó là : 
 Với xk là biến vào , biến ra xr được chọn là biến có chỉ số nhỏ nhất thỏa điều 
kiện chọn biến ra : 
m)1,2,...,(i 0a , 
a
b
 min ik
ik
i =
⎭⎬
⎫
⎩⎨
⎧ > 
 Ví dụ : 
 Xét quy hoạch tuyến tính suy biến : 
0x,x,x,x,x,x,x
2x9xxx
0x
3
2
x
6
1
xx
2
1
x
0x12xx2x
3
1
x
x16xx2x
3
4
w(x) min
7654321
7653
76542
76541
7654
≥
⎪⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
=−++
=+−−+
=+−−+
+−+−−=
 Áp dụng quy tắc Bland ta thấy : 
cB iB x1 x2 x3 x4 x5 x6 x7 b 
0 1 1 0 0 
3
1 -2 -1 12 0 
0 2 0 1 0 
2
1 -1 
6
1− 
3
2 0 
0 3 0 0 1 0 1 1 -9 2 
cT 0 0 0 
3
4− 2 -1 16 
T
c 0 0 0 3
4− 2 -1 16 
w=0 
 Biến ra có thể là x1 hay x2 . Chọn x1 
cB iB x1 x2 x3 x4 x5 x6 x7 b 
3
4− 4 3 0 0 1 -6 -3 36 0 
GIẢI THUẬT ĐƠN HÌNH 
65 
0 2 
2
3− 1 0 0 2 
3
4 
3
34− 0 
0 3 0 0 1 0 1 1 -9 2 
cT 0 0 0 
3
4− 2 -1 16 
T
c 4 0 0 0 -6 -5 64 
w=0 
 Biến ra là x2 
cB iB x1 x2 x3 x4 x5 x6 x7 b 
3
4− 4 
2
3− 3 0 1 0 1 2 0 
2 5 
4
3− 
2
1 0 0 1 
3
2 
3
17− 0 
0 3 
4
3 
2
1− 1 0 0 
3
1 
3
10− 2 
cT 0 0 0 
3
4− 2 -1 16 
T
c 2
1− 3 0 0 0 -1 30 
w=0 
 Biến ra có thể là x4 hay x5 . Chọn x4
cB iB x1 x2 x3 x4 x5 x6 x7 b 
-1 6 
2
3− 3 0 1 0 1 2 0 
2 5 
4
1 
2
3− 0 
3
2− 1 0 -7 0 
0 3 
4
5 
2
3− 1 
3
1− 0 0 -4 2 
cT 0 0 0 
3
4− 2 -1 16 
T
c -2 6 0 1 0 0 32 
w=0 
 Biến ra là x5 
cB iB x1 x2 x3 x4 x5 x6 x7 b 
-1 6 0 -6 0 -3 6 1 -40 0 
0 1 1 6 0 
3
8− 4 0 -28 0 
GIẢI THUẬT ĐƠN HÌNH 
66 
0 3 0 6 1 3 -5 0 31 2 
cT 0 0 0 
3
4− 2 -1 16 
T
c 0 -6 0 3
13− 81 0 -24 
w= 
 Biến ra là x3
cB iB x1 x2 x3 x4 x5 x6 x7 b 
-1 6 0 
31
54 
31
40 
31
27 
31
14− 1 0 
31
80 
0 1 1 
31
18− 
31
28 
93
4 
31
16− 0 0 
31
56 
16 7 0 
31
6 
31
1 
31
3 
31
5− 0 1 
31
2 
cT 0 0 0 
3
4− 2 -1 16 
T
c 0 31
42 
31
24 
93
187−
31
128 0 0 
w=
31
48− 
 Đến đây không còn hiện tượng suy biến. 
 Biến vào là x7
GIẢI THUẬT ĐƠN HÌNH 
67 
CÂU HỎI CHƯƠNG 2 
1- Trình bày cơ sở lý thuyết của thuật toán đơn hình cơ bản. 
2- Định nghĩa quy hoạch tuyến chuẩn. 
3- Trình bày các bước lập bảng đơn hình theo phép toán trên dòng . 
4- Cải biên một quy hoạch tuyến tính tổng quát như thế nào ? . Cách giải quy hoạch 
tuyến tính cải biên và quy hoạch tuyến tính gốc. 
GIẢI THUẬT ĐƠN HÌNH 
68 
BÀI TẬP CHƯƠNG 2 
1- Tìm phương án tối ưu của bài toán sau đây bằng phương pháp đơn hình cơ bản 
 a)- b)- 
⎪⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
≥
≤+
≤+
≤+
+=
0x,x
30x25x
14x2x
4xx-
x23xz max
21
21
21
21
21
⎪⎪
⎪⎪
⎩
⎪⎪
⎪⎪
⎨
⎧
≥
≤+
≤+
≤+
≤+
−=
0x,x
1x5x
5x4x
3x32x
4x2x
x2-2xz min
21
21
21
21
21
21
c)- 
⎪⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
≥
=+−
=−++
=++++
++=
0x,x,x,x,x
1xxx
2xxxx
5xxxxx
x2xxwmin
54321
543
5432
54321
531
2- Tìm phương án tối ưu của bài toán sau bằng phương pháp đơn hình cải tiến 
a) max z = 5x1 + 3x2 
2x1 + 2x2 ≤ 80 
x1 ≤ 30 
x1, x2 ≥ 0 
b) max z = x1 + 2x2
2x1 + 3x2 ≤ 7 
x1 - x2 ≤ 1 
x1 ≥ 0, x2 ≥ 0 
c) max z = 5x1 + 3x2 + x3 
2x1 + 3x2 - x3 ≤ 4 
3x1 - x2 + 2x3 ≤ 2 
x1 + x2 + 3x3 ≤ 5 
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 
3- Tìm phương án tối ưu của các bài toán sau bằng phương pháp biến giả cải biên. 
a) max z = 3x1 - x2 
2x1 + x2 ≤ 100 
GIẢI THUẬT ĐƠN HÌNH 
69 
x1 ≥ 10 
x2 ≥ 0 
b) min w = 3x1 + x2 
 x1 + x2 ≥ 3 
 2x1 ≥ 5 
 x1, x2 ≥ 0 
c) max z = 3x1 + x2 - 3x3 
 x1 + 2x2 - x3 = 2 
 -10x2 + 5x3 = 5 
 -3x2 + 2 x3 = 4 
 xi ≥ 0, ∀i = 1→3 
 d)- e)- 
⎪⎪⎩
⎪⎪⎨
⎧
≥
≤+−
−≤−−−
+=
0x,x,x
1xxx2
2xxx
x62xz max
321
321
321
21
⎪⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
≥
≤+
−≤+−
≥+
−=
0x,x
4x2x
1xx
3xx
x3-xw min
21
21
21
21
21
 f)- g)- 
⎪⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
≥
≤+−
−≤+−
−≤−−
+=
0x,x
2x2x
1xx
3xx
x3xz max
21
21
21
21
21
⎪⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
≥
≤
−≤−−
−≤+−
+=
0x,x
1x
2x2x
1xx
x2xw min
21
2
21
21
21