Giáo trình Lý thuyết cơ bản về quy hoạch tuyến tính - Chương 2: Giải thuật đơn hình

GIẢI THUẬT ĐƠN HÌNH 
34 
CHƯƠNG II 
GIẢI THUẬT ĐƠN HÌNH 
 Chương này trình bày một cách chi tiết nội dung của giải thuật đơn hình. Sau 
phần cơ sở lý thuyết của giải thuật là các ví dụ tương ứng. Các ví dụ được trình bày 
đúng theo các bước của giải thuật. Kiến thức trong chương này cần thiết cho việc lập 
trình giải quy hoạch tuyến tính trên máy tính. 
 Nội dung chi tiết của chương bao gồm : 
I- GIẢI THUẬT ĐƠN HÌNH CƠ BẢN 
 1- Cơ sở xây dựng giải thuật đơn hình cơ bản 
 2- Định lý về sự hội tụ 
 3- Giải thuật đơn hình cơ bản 
 4- Chú ý trong trường hợp suy biến 
II- GIẢI THUẬT ĐƠN HÌNH CẢI TIẾN 
 1- Một cách tính ma trận nghịch đảo 
 2- Quy hoạch tuyến tính dạng chuẩn 
 3- Giải thuật đơn hình cải tiến 
 4- Phép tính trên dòng - Bảng đơn hình 
III- PHƯƠNG PHÁP BIẾN GIẢ CẢI BIÊN 
 1- Bài toán cải biên 
 a- Cải biên bài toán quy hoạch tuyến tính 
 b- Quan hệ giữa bài toán xuất phát và bài toán cải biên 
 2- Phương pháp hai pha 
 3- Phương pháp M vô cùng lớn 
IV- QUY HOẠCH TUYẾN TÍNH SUY BIẾN 
1- Các ví dụ về quy hoạch tuyến tính suy biến 
2- Xử lý quy hoạch tuyến tính suy biến 
GIẢI THUẬT ĐƠN HÌNH 
35 
CHƯƠNG II: GIẢI THUẬT ĐƠN HÌNH 
I- GIẢI THUẬT ĐƠN HÌNH CƠ BẢN 
 Chương này trình bày một phương pháp để giải bài toán quy hoạch tuyến tính 
đó là phương pháp đơn hình. Phương pháp đơn hình được George Bernard Dantzig 
đưa ra năm 1947 cùng lúc với việc ông khai sinh ra quy hoạch tuyến tính. Đây là một 
phương pháp thực sự có hiệu quả để giải những bài toán quy hoạch tuyến tính cở lớn 
trong thực tế. Với cách nhìn hiện đại ý tưởng của phương pháp đơn hình rất đơn giản. 
Có nhiều cách tiếp cận phương pháp đơn hình, chương này trình bày một trong các 
cách đó. 
 1- Cơ sở xây dựng giải thuật đơn hình cơ bản 
 Xét bài toán quy hoạch tuyến tính chính tắc : 
⎩⎨
⎧
≥
=
=
0x
bAx
xcz(x) max T
 Giả sử rằng B0 là một cơ sở khả thi xuất phát của bài toán ( không nhất thiết là 
m cột đầu tiên của ma trận A ) . Thuật toán đơn hình cơ bản được xây dựng dựa trên 
các bước sau : 
 a- Gán B = B0 và l=0 ( số lần lặp ) 
 b- l = l+1 
 c- Với cơ sở hiện thời B tính : 
⎥⎦
⎤⎢⎣
⎡
=
==
−
0x
bBx
x
N
1
B : phương án cơ sở khả thi tương ứng 
 bBb 1−= 
NBccc 1TN
T
N
T
N
−−= : dấu hiệu tối ưu 
 d- Nếu 0NBccc 1TB
T
N
T
N ≤−= − thì giải thuật dừng và bài toán có 
phương án tối ưu là x . 
 Ngược lại, nếu tồn tại s sao cho 0c s > ( sc là thành phần thứ s 
của Nc ) thì sang bước e 
GIẢI THUẬT ĐƠN HÌNH 
36 
 e- Tính : s
1
s ABA −= ( As là cột thứ s của A ) 
 Nếu 0As ≤ thì giải thuật dừng và phương án tối ưu không giới nội. 
 Ngược lại, nếu tồn tại sis Aa ∈ mà 0ais > thì tính : 
rs
r
is
is
i
s
a
b
0a , 
a
b
 minx =
⎭⎬
⎫
⎩⎨
⎧ >=∧ ( i = 1 → m) 
 isa là các thành phần của sA . 
 là thành phần thứ s của phương án mới . sx
∧ ∧
x
 f- Gọi xt là biến tương ứng với cột thứ r của cơ sở B. Khi đó biến xs sẽ 
nhận giá trị ( vào cơ sở ), biến x0x s >∧ t sẽ nhận giá trị ( ra khỏi cơ sở ). Như 
vậy phương án mới tương ứng với cơ sở mới ( thay đổi cơ sở ) được xác định 
như sau : 
0x t =∧
∧
x
∧
B
 = B ∪ { t } - { s } ∧B
 g- Gán B = và quay về b . 
∧
B
 Về mặt hình học, giải thuật này được hiểu như là một quá trình duyệt qua các 
điểm cực biên của đa diện lồi S các phương án khả thi của bài toán. 
 Về mặt đại số, giải thuật này được hiểu như là một quá trình xác định một 
chuỗi các ma trận cơ sở kề B0 B1 B2 ......... mà các phương án cơ sở tương ứng x0 x1 
x2........ là ngày càng tốt hơn, tức là : 
 z(x0) < z(x1) < z(x2) ............. 
 Chú ý : 
 Nếu cơ sở ban đầu B0 chính là m cột đầu tiên của ma trận A thì trong giải 
thuật trên t chính là r . 
 2- Định lý về sự hội tụ 
 Với giả thiết bài toán không suy biến, giải thuật đơn hình trên đây sẽ hội tụ về 
phương án tối ưu sau một số hữu hạn lần lặp. 
 Bằng sự thống kê người thấy rằng nói chung giải thuật đơn hình sẽ hội tụ với 
số lần lặp ít nhất phải là từ m đến 3m ( m là số ràng buộc ) . 
GIẢI THUẬT ĐƠN HÌNH 
37 
 3- Giải thuật đơn hình cơ bản 
Xét bài toán quy hoạch tuyến tính chính tắc 
⎩⎨
⎧
≥
=
=
 0x
 bAx
 xc)x(zmin/max T
 Giả sử rằng sau khi hoán vị các cột trong A ta chọn được ma trận cơ sở B thoả 
sự phân hoạch sau đây : 
 A = [ B N ] 
]c c[c NB
T = 
 ]x x[x NB
T =
 Giải thuật đơn hình cơ bản được thực hiện như sau : 
a- Tính ma trận nghịch đảo B-1
 b- Tính các tham số : 
 . Phương án cơ sở khả thi tốt hơn 
⎥⎥⎦
⎤
⎢⎢⎣
⎡
=
===
−
0x
bbBx
x
N
1
B 
 . Giá trị hàm mục tiêu B
T
B xc)x(z =
 . Ma trận = B
__
N -1N 
 c- Xét dấu hiệu tối ưu : 
__
T
B
T
N
1T
B
T
N
T
N NccNBccc −=−= − 
 - Nếu 0c
T
N ≤ thì kết thúc giải thuật với phương án tối ưu là : 
 ⎥⎥⎦
⎤
⎢⎢⎣
⎡
=
===
−
0x
bbBx
x
N
1
B 
 và giá trị hàm mục tiêu là : 
B
T
B xc)x(z = 
 - Nếu tồn tại Ns cc ∈ mà 0cs > thì sang bước d. 
d- Xác định chỉ số của phần tử pivot trong ma trận N 
. Xác định chỉ số cột s của pivot 
 { }Nks c0c max c ∈>= 
GIẢI THUẬT ĐƠN HÌNH 
38 
 Nếu 0Nis ≤ thì giải thuật dừng, bài toán không có phương án tối ưu. 
Ngược lại thì tiếp tục. 
. Xác định chỉ số dòng r của pivot 
m)1,2,...,(i 
N
b
0N , 
N
b
 min
rs
r
is
is
i ==
⎭⎬
⎫
⎩⎨
⎧ > 
 Phần tử rsN trong ma trận được gọi là phần tử pivot 
__
N
 Trong trường hợp bài toán min 
c- Xét dấu hiệu tối ưu : 
__
T
B
T
N
1T
B
T
N
T
N NccNBccc −=−= − 
- Nếu ≥TNc 0 thì kết thúc giải thuật với phương án tối ưu là : 
 ⎥⎥⎦
⎤
⎢⎢⎣
⎡
=
===
−
0x
bbBx
x
N
1
B
 và giá trị hàm mục tiêu là : 
B
T
B xc)x(z = 
 - Nếu tồn tại Ns cc ∈ mà 0cs < thì sang bước d. 
d- Xác định chỉ số của phần tử pivot trong ma trận N 
. Xác định chỉ số cột s của pivot 
 { }Nkks c0c |c| max c ∈<= 
 Nếu 0Nis ≤ thì giải thuật dừng, bài toán không có phương án tối ưu. 
Ngược lại thì tiếp tục. 
. Xác định chỉ số dòng r của pivot 
m)1,2,...,(i 
N
b
0N , 
N
b
 min
rs
r
is
is
i ==
⎭⎬
⎫
⎩⎨
⎧ > 
 Phần tử rsN trong ma trận được gọi là phần tử pivot 
__
N
e- Thực hiện các hoán vị : 
. Cột thứ s trong ma trận N với cột thứ r trong ma trận B 
. Phần tử thứ s trong với phần tử thứ r trong TNc
T
Bc
. Biến xs trong với biến xTNx r trong 
T
Bx
f- Quay về (a) 
GIẢI THUẬT ĐƠN HÌNH 
39 
Ví dụ : Tìm phương án tối ưu cho bài toán quy hoạch tuyến tính chính tắc sau đây 
bằng giải thuật đơn hình cơ bản 
⎪⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
=≥
=++−
=++
=+−
+=
1,2,3,4,5)(j 0x
2xx2x
6xx2x
3xxx
xx2)x(z max
j
521
421
321
21
 Ta có : 
 [ ]
[ ]
T
B
T
N
T
T
B
T
N
54321
T
c c 
 0 0 0| 1 2 c
x x 
xxx|xxx
B N 
2
6
3
b 
10 0|2 1
0 1 0|2 1
 0 0 1|11
A
=
=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−
=
Lần lặp1 
 a- Tính ma trận nghịch đảo B-1
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
==−
100
010
001
BB 1 
b- Tính các tham số 
. Phương án cơ sở khả thi tốt hơn : 
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢
⎣
⎡
⎥⎥⎦
⎤
⎢⎢⎣
⎡=⎥⎥⎦
⎤
⎢⎢⎣
⎡=
=
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
==
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=
=
−
0
0
x
x
x
b
2
6
3
2
6
3
1 0 0
0 1 0
0 0 1
bB
x
x
x
x
x
2
1
N
1
5
4
3
B
. Giá trị hàm mục tiêu : 
GIẢI THUẬT ĐƠN HÌNH 
40 
[ ] 0
2
6
3
 000xc)x(z B
T
B =
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
== 
 . Tính ma trận : 
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−
=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
== − 
2 1
2 1 
11 
2 1
2 1 
11 
100
010
001
NBN 1
__
c- Xét dấu hiệu tối ưu : 
 [ ] [ ] [ 12 
2 1
2 1 
 11 
 00012Nccc
__
T
B
T
N
T
N =
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−
−=−= ] 
 Chuyển sang bước d 
 d- Xác định chỉ số của pivot 
 . Xác định chỉ số cột pivot s : 
 { }Nks c0c max c ∈>= { } 1__c2 1 , 2 max === 
Vậy s=1 
Ma trận cột s=1 trong ma trận N là 
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
−
=
1
1 
1 
N1 
. Xác định chỉ số dòng pivot r : 
11
1
21
2
11
1
is
i
N
b
3
1
6
,
1
3
min
N
b
,
N
b
 min
N
b
 min ==⎭⎬
⎫
⎩⎨
⎧=
⎭⎬
⎫
⎩⎨
⎧=
⎭⎬
⎫
⎩⎨
⎧
 Vậy r = 1 
 e- Hoán vị 
. Cột thứ s=1 trong ma trận N và cột thứ r=1 trong ma trận B 
. Phần tử thứ s=1 trong với phần tử thứ r=1 trong TNc
T
Bc
. Biến thứ s=1 trong với biến thứ r=1 trong TNx
T
Bx
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−
=→
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−
=
101|20
011|20
001|11
A
100|21
010|21
001|11
A 
 [ ] [ ]002|10c 000|12c TT =→= 
 [ ] [ ]54123T54321T xxx|xx xxxx|xxx =→= 
GIẢI THUẬT ĐƠN HÌNH 
41 
f- Quay về bước a 
Lần lặp 2 
 a. Tính ma trận nghịch đảo B-1
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
= −
101
011
001
B 
101
011
001
B 1 
b- Tính các tham số 
. Phương án cơ sở khả thi tốt hơn : 
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢
⎣
⎡
⎥⎥⎦
⎤
⎢⎢⎣
⎡=⎥⎥⎦
⎤
⎢⎢⎣
⎡=
=
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
−==
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=
=
−
0
0
x
x
x
b
5
3
3
2
6
3
1 0 1
0 1 1
0 0 1
bB
x
x
x
x
x
2
3
N
1
5
4
1
B
. Giá trị hàm mục tiêu : 
[ ] 6
5
3
3
 002xc)x(z B
T
B =
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
== 
 . Tính ma trận : 
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡ −
=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡ −
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
== − 
1 1
3 1- 
11 
2 0
2 0 
11 
101
011-
001
NBN 1
__
c- Xét dấu hiệu tối ưu : 
 [ ] [ ] [ 3 2
1 1
3 1- 
 11 
 0 0 210Nccc
__
T
B
T
N
T
N −=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡ −
−=−= ] 
 Chuyển sang bước d 
 d- Xác định chỉ số của pivot 
 . Xác định chỉ số cột pivot s : 
 { }Nks c0c max c ∈>= { } 2__c3 3 max === 
Vậy s=2 
GIẢI THUẬT ĐƠN HÌNH 
42 
Ma trận cột s=2 trong ma trận N là 
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=
1 
3 
1- 
N2 
. Xác định chỉ số dòng pivot r : 
22
2
23
3
22
2
is
i
N
b
1
1
5
,
3
3
min
N
b
,
N
b
 min
N
b
 min ==⎭⎬
⎫
⎩⎨
⎧=
⎭⎬
⎫
⎩⎨
⎧=
⎭⎬
⎫
⎩⎨
⎧
 Vậy r = 2 
 e- Hoán vị 
. Cột thứ s=2 trong ma trận N và cột thứ r=2 trong ma trận B 
. Phần tử thứ s=2 trong với phần tử thứ r=2 trong TNc
T
Bc
. Biến thứ s=2 trong với biến thứ r=2 trong TNx
T
Bx
121|00
021|10
011|01
A
101|20
011|20
001|11
A
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−
=→
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−
= 
 [ ] [ ]012|00c 002|10c TT =→= 
 [ ] [ ]52143T54123T xxx|xx xxxx|xxx =→= 
f- Quay về bước a 
Lần lặp 3 
 a. Tính ma trận nghịch đảo B-1
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
−=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
= −
1 
3
1
- 
3
4
0 
3
1
3
1
0 
3
1
3
2
B 
121
021
01-1
B 1 
b- Tính các tham số 
. Phương án cơ sở khả thi tốt hơn : 
GIẢI THUẬT ĐƠN HÌNH 
43 
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
⎥⎥⎦
⎤
⎢⎢⎣
⎡=⎥⎥⎦
⎤
⎢⎢⎣
⎡=
=
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
−==
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎣
⎡
=
=
−
0
0
x
x
x
b
4
1
4
2
6
3
1 
3
1- 
3
4 
0 
3
1 
3
1
0 
3
1 
3
2 
bB
x
x
x
x
x
4
3
N
1
5
2
1
B
. Giá trị hàm mục tiêu : 
[ ] 9
4
1
4
 012xc)x(z B
T
B =
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
== 
 . Tính ma trận : 
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
−=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
−== −
3
1- 
3
4
3
1 
3
1
3
1 
3
2
0 0
1 0 
01 
1 
3
1- 
3
4 
0 
3
1 
3
1
0 
3
1 
3
2 
NBN 1
__
c- Xét dấu hiệu tối ưu : 
 [ ] [ ] [ ] 01- 1
3
1
- 
3
4
3
1
3
1
3
1
3
2
 0 1 200Nccc
__
T
B
T
N
T
N <−=
⎥⎥
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢
⎣
⎡
−−=−= : dừng 
 Vậy phương án tối ưu sẽ là : 
⎪⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
⎥⎦
⎤⎢⎣
⎡=⎥⎦
⎤⎢⎣
⎡=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
0
0
x
x
x
4
1
4
x
x
x
x
4
3
N
5
2
1
B
Giá trị hàm mục tiêu là z(x) = 9 với x1 = 4 và x2 = 1 
GIẢI THUẬT ĐƠN HÌNH 
44 
 4- Chú ý trong trường hợp suy biến 
 Trong trường hợp bài toán suy biến, nghĩa là 0br = , ta có : 
 0
a
b
x
rs
r
s ==∧ 
cho nên giá trị của hàm mục tiêu không thay đổi khi thay đổi cơ sở, vì : 
 )x(zxc)x(z)x(z ss =+= ∧∧ 
 Vậy thì, có thể sau một số lần thay đổi cơ sở lại quay trở về cơ sở đã gặp và 
lặp như vậy một cách vô hạn. Người ta có nhiều cách để khắc phục hiện tượng này 
bằng cách xáo trộn một chút các dữ liệu của bài toán, sử dụng thủ tục từ vựng, quy tắc 
chọn pivot để tránh bị khử. 
II- GIẢI THUẬT ĐƠN HÌNH CẢI TIẾN 
 1- Một cách tính ma trận nghịch đảo 
 Trong giải thuật đơn hình cơ bản hai ma trận kề B và chỉ khác nhau một cột 
vì vậy có thể tính ma trận nghịch đảo một cách dễ dàng từ B
∧
B
1
B
−∧
-1 . Để làm điều đó 
chỉ cần nhân (bên trái) B-1 với một ma trận đổi cơ sở được xác định như sau : 
rcôt 
r dòng 
1..
a
a
..00
............
0..
a
1
..00
............
0..
a
a
..10
0..
a
a
..01
rs
ms
rs
rs
2s
rs
1s
↑
→
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎦
⎤
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎢⎢
⎣
⎡
−
−
−
=µ
 Khi đó : 
1
1^
BB −
−
µ= 
 Ta thấy rằng ma trận đổi cơ sở µ được thiết lập giống như một ma trận đơn vị 
mxm, trong đó cột r có các thành phần được xác định như sau : 
GIẢI THUẬT ĐƠN HÌNH 
45 
rs
is
a
a− : đối với thành phần i ≠ r. 
rsa
1 : đối với thành phần r . 
 Khi mà ma trận cở sở xuất phát là ma trận đơn vị, sau một số bước đổi cơ sở 
B0 B1 B2 ....... Bq tương ứng với các ma trận đổi cơ sở µ0 µ1 µ2 ....µq-1 người ta có 
cách tính ma trận nghịch đảo như sau : 
 [ ] 1q101q ........B −− µµµ=
 2- Quy hoạch tuyến tính dạng chuẩn 
 Quy hoạch tuyến tính dạng chuẩn là quy hoạch tuyến tính chính tắc mà trong 
đó có thể rút ra một ma trận cơ sở là ma trận đơn vị. Quy hoạch tuyến tính chuẩn có 
dạng : 
⎩⎨
⎧
≥
=
=
0x
bx N] I[
xc)x(z maxmin/ T
 3- Giải thuật đơn hình cải tiến 
Từ những kết quả trên người ta xây dựng giải thuật đơn hình cải tiến đối với 
bài toán qui hoạch tuyến tính (max) dạng chuẩn như sau : 
a- Khởi tạo 
 AA0 = 
 bb0 = 
b- Thực hiện bước lặp với k = 0,1,2, ... 
 . Xác định phương án cơ sở khả thi : 
 ⎥⎥⎦
⎤
⎢⎢⎣
⎡
=
=
=
0x
bx
x
k
k
N
kBk 
 . Tính giá trị hàm mục tiêu : 
 kTBB
T
B
k bcxc)x(z
kkk
== 
. Xét dấu hiệu tối ưu : 
 kTB
TT
k Accc
k
−= 
 - Nếu 0c
T
k ≤ thì giải thuật dừng và : 
GIẢI THUẬT ĐƠN HÌNH 
46 
⎥⎥⎦
⎤
⎢⎢⎣
⎡
=
=
=
0x
bx
x
k
k
N
kBk là phương án tối ưu 
 kTBB
T
B
k bcxc)x(z
kkk
== là giá trị hàm mục tiêu 
 - Ngược lại thì sang bước (c) 
c- Cập nhật các giá trị mới : 
.Tính pivot 
.Tính ma trận chuyển cơ sở µk
.Tính kk1k AA µ=+ 
.Tính kk1k bb µ=+ 
.Tăng số lần lặp k=k+1. 
Quay về bước b 
 Ví dụ 
Giải bài toán quy hoạch tuyến tính sau đây bằng phương pháp đơn hình cải 
tiến : 
1,2,3,4,5)(j 0x
2x2xx
6x2xx
3xxx
x2xz(x)max 
j
521
421
321
21
=≥
⎪⎪⎩
⎪⎪⎨
⎧
=++−
=++
=+−
+=
Bước khởi tạo 
00
00
B N 
2
6
3
b 
100|21
010|21
001|11
AA
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−
==
[ ]
T
B
T
N
T
00
c c 
000|12c =
Bước lặp k=0 
⎥⎥
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢⎢
⎢
⎣
⎡
=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
==
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
==
0x
2
6
3
b
x
x
x
x
x
0
0
N
0
5
4
3
B0 
GIẢI THUẬT ĐƠN HÌNH 
47 
 [ ] 0
2
6
3
 0 0 0bc)x(z 0TB
0
0
=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
== 
[ ] [ ] [ 0 0 0 1 2
1 0 0 2 1
0 1 0 2 1 
 0 0 1 1- 1 
 0 0 00 0 0 1 2Accc 0TB
TT
0
0
=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−=−= ] 
 suy ra pivot : 
⎥⎥
⎥
⎦
⎤
⎢⎢
 ... ng án tối ưu . 
Hai phương pháp biến giả cải biên thương dùng là phương pháp hai pha và 
phương pháp M vô cùng lớn . 
GIẢI THUẬT ĐƠN HÌNH 
53 
 2- Phương pháp hai pha 
Pha 1 
Tìm phương án tối ưu cho bài toán cải biên với hàm mục tiêu cải biên 
là : 
min (tổng tất cả biến giả cải biên) 
Pha 2 
Tìm phương án tối ưu cho bài toán xuất phát với phương án cơ sở khả thi xuất 
phát là phương án tối ưu tìm được ở pha 1. Ở pha 2 này các biến giả cải biên bị loại ra 
khỏi ma trận các hệ số ràng buộc, và vectơ chi phí được cập nhật lại, do đó dấu hiệu 
tối ưu cũng được cập nhật lại 
Đây là phương pháp thuận lợi cho việc lập trình ứng dụng giải thuật đơn hình 
cải tiến. 
Ví dụ : Xét bài toán quy hoạch tuyến tính 
1,2,3)(j 0x
3
7
x3x2x
3
8
x2x2x
xx4x3)x(z max
j
321
321
321
=≥
⎪⎪⎩
⎪⎪⎨
⎧
≥++
≤++
++=
Đưa bài toán về dạng chính tắc bằng cách thêm biến phụ x4 , x5 ta được 
1,2,3,4,5)(j 0x
3
7
xx3x2x
3
8
xx2x2x
xx4x3)x(z max
j
5321
4321
321
=≥
⎪⎪⎩
⎪⎪⎨
⎧
=−++
=+++
++=
 Ma trận các hệ số ràng buộc là : 
 A= không chứa ma trận đơn vị ⎥⎦
⎤⎢⎣
⎡
−1 0 3 2 1
0 1 2 2 1
 Áp dụng phương pháp đơn hình cải biên hai pha như sau : 
 Pha 1 
GIẢI THUẬT ĐƠN HÌNH 
54 
Thêm biến giả (cải biên ) x6 ≥ 0 vào ràng buộc thứ hai để được ma trận đơn vị 
. Khi đó bài toán cải biên có dạng : 
6)1,2,3,4,5,(j 0x
3
7
xxx3x2x
3
8
xx2x2x
x)x(w min 
j
65321
4321
6
=≥
⎪⎪⎩
⎪⎪⎨
⎧
=+−++
=+++
=
Có ma trận các ràng buộc là : 
 có chứa ma trận đơn vị ⎥⎦
⎤⎢⎣
⎡
−= 1 1 0 3 2 1
0 0 1 2 2 1
A
Giải bài toán cải biên bằng giải thuật đơn hình cải tiến 
Khởi tạo 
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=⎥⎦
⎤⎢⎣
⎡
−=
3
7
3
8
b 
110321
001221
A 00 
 [ ]100000cT = 
Bước lặp k=0 
0B
c 
0B
i x1 x2 x3 x4 x5 x6 0b 
0 4 1 2 2 1 0 0 
3
8 
1 6 1 2 3 0 -1 1 
3
7 
cT 0 0 0 0 0 1 w(x0) 
T
0c -1 -2 -3 0 1 0 
3
7 
Bước lặp k= 1 
1B
c 
1B
i x1 x2 x3 x4 x5 x6 1b 
0 4 
3
1 
3
2 0 1 
3
2 
3
2− 
9
10 
0 3 
3
1 
3
2 1 0 
3
1− 
3
1 
9
7 
cT 0 0 0 0 0 1 w(x1) 
T
1c 0 0 0 0 0 1 0 
 Ta được phương án tối ưu . Xong pha 1 . Chuyển sang pha 2. 
 Pha 2 
GIẢI THUẬT ĐƠN HÌNH 
55 
 Loại bỏ biến giả cải biên x6 ≥ 0 
 Khởi tạo 
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
=
9
7
9
10
b
3
1
01
3
2
3
1
3
2
10
3
2
3
1
A
0
0
 [ ]00143 c T =
 Bước lặp k=0 
0B
c 
0B
i x1 x2 x3 x4 x5 0b 
0 4 
3
1 
3
2 0 1 
3
2 
9
10 
1 3 
3
1 
3
2 1 0 
3
1− 
9
7 
cT 3 4 1 0 0 z(x0) 
T
0c 3
8 
3
10 0 0 
3
1 
9
7 
Bước lặp k=1 
1B
c 
1B
i x1 x2 x3 x4 x5 1b 
0 4 0 0 -1 1 1 
3
1 
4 2 
2
1 1 
2
3 0 
2
1− 
6
7 
cT 3 4 1 0 0 z(x1) 
T
1c 1 0 -5 0 2 3
14 
 Bước lặp k=2 
2B
c 
2B
i x1 x2 x3 x4 x5 2b 
0 5 0 0 -1 1 1 
3
1 
4 2 
2
1 1 1 
2
1 0 
3
4 
cT 3 4 1 0 0 z(x2) 
T
2c 1 0 -3 -2 0 3
16 
 Bước lặp k=3 
3B
c 
3B
i x1 x2 x3 x4 x5 3b 
GIẢI THUẬT ĐƠN HÌNH 
56 
0 5 0 0 -1 1 1 
3
1 
3 1 1 2 2 1 0 
3
8 
cT 3 4 1 0 0 z(x3) 
T
3c 0 -2 -5 -2 0 8 
 Kết quả của bài toán đã cho : 
 . Phương án tối ưu 
⎪⎪
⎪⎪
⎩
⎪⎪
⎪⎪
⎨
⎧
=
=
=
=
=
3
1
x
0x
0x
0x
3
8
x
5
4
3
2
1
 . Giá trị hàm mục tiêu z(x)=z(x3)= 8 
 3- Phương pháp M vô cùng lớn 
 Phương pháp M vô cùng lớn ( M là số vô cùng lớn ) tương tự như 
phương pháp hai pha, ngoại trừ ở pha 1 hàm mục tiêu cải biên có dạng sau đây cho 
bài toán max/min 
max [z(x) - M*( tổng các biến giả cải biên) ] 
min [z(x) + M*( tổng các biến giả cải biên) ] 
Bằng phương pháp này, trong quá trình tối ưu, các biến giả cải biên sẽ được 
loại dần ra khỏi ma trận cơ sở : tất cả đều bằng 0. Nếu trong quá trình tìm phương án 
tối ưu mà không loại bỏ được các biến giả cải biên ra khỏi cơ sở thì bài toán vô 
nghiệm. 
So với phương pháp hai pha thì phương pháp này tránh được việc phải cập 
nhật lại dữ liệu cho bài toán gốc nhưng không tiện lợi bằng trong lập trình ứng dụng. 
Ví dụ : Xét bài toán tương tự như trên 
GIẢI THUẬT ĐƠN HÌNH 
57 
1,2,3,4,5)(j 0x
3
7
xx3x2x
3
8
xx2x2x
xx4x3)x(z max
j
5321
4321
321
=≥
⎪⎪⎩
⎪⎪⎨
⎧
=−++
=+++
++=
Thêm biến giả cải biên x6 ≥ 0 vào ràng buộc thứ hai đồng thời cải biên hàm mục 
tiêu theo như trên ta được : 
6)1,2,3,4,5,(j 0x
3
7
xxx3x2x
3
8
xx2x2x
Mxxx4x3)x(wmax 
j
65321
4321
6321
=≥
⎪⎪⎩
⎪⎪⎨
⎧
=+−++
=+++
−++=
Tìm phương án tối ưu cho bài toán cải biên này bằng phương pháp đơn hình 
cải tiến 
Khởi tạo 
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=⎥⎦
⎤⎢⎣
⎡
−=
3
7
3
8
b 
110321
001221
A 00 [ ]M00143cT −= 
 Bước lặp k=0 
0B
c 
0B
i 1x 2x 3x 4x 5x 6x 0b 
0 4 1 2 2 1 0 0 
3
8 
-M 6 1 2 3 0 -1 1 
3
7 
cT 3 4 1 0 0 -M w(x0) 
T
0c 3+M 4+2M 1+3M 0 -M 0 3
M7−
Bước lặp k= 1 
1B
c 
1B
i 1x 2x 3x 4x 5x 6x 1b 
0 4 
3
1 
3
2 0 1 
3
2 
3
2− 
9
10 
1 3 
3
1 
3
2 1 0 
3
1−
3
1 
9
7 
cT 3 4 1 0 0 -M w(x1)
T
1c 3
8 
3
10 0 0 
3
1 M
3
5 −− 
9
7 
GIẢI THUẬT ĐƠN HÌNH 
58 
 Do x6 = 0 (vì ngoài cơ sở) nên bị loại ra khỏi bảng và ta tiếp tục tìm phương 
án tối ưu cho bài toán gốc đã cho có phương án cơ sở khả thi được khởi tạo như sau : 
0B
c 
1B
i 1x 2x 3x 4x 5x 0b 
0 4 
3
1 
3
2 0 1 
3
2 
9
10 
1 3 
3
1 
3
2 1 0 
3
1− 
9
7 
cT 3 4 1 0 0 z(x0) 
T
0c 3
8 
3
10 0 0 
3
1 
9
7 
 Các bước tiếp theo đượ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