Chương I
BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
Bài 4. PHƯƠNG PHÁP ĐƠN HÌNH
1. Giới thiệu chung: Ta xét bài toán
QHTT dạng chính tắc:
1
1
( ) , min (max)
1,
0 1, .
n
j j
j
n
ij j i
j
j
f x c x c x
a x b i m
x j n
=
=
= = 〈 〉 →
= =
≥ =
∑
∑

Hoặc viết dưới dạng:
( ) , min (max)

Giả sử bài toán đang xét ta đã biết
một phương án cực biên dạng :
10 20 0
( ; ; ; ;0;0; ;0)
m
x x x x=
0
0, 1,
j
x j m> =
trong đó
cơ sở liên kết của
x là
1 2
, , ,
m
A A A
1 2
10 20 0

m
m
x A x A x A b+ + + =
1 10 2 20 0
( )
m m
f x c x c x c x= + + +
Giá trị hàm mục tiêu là:
1 2
1 2

=
= = 〈 〉 =
∑
Đặt:
j j j
z c∆ = −
Từ hai véctơ:
10 20 0
1 2
( ; ; ; ;0;0; ;0)
( ; ; ; )
m
j
j j mj
x x x x
x x x x
=
=

2. Định lý 1.( Dấu hiệu tối ưu)
Nếu là một
phương án cực biên của bài toán Quy
hoạch tuyến tính dạng chính tắc sao cho :

thì x là phương án tối ưu, và ngược lại.
10 20 0
( ; ; ; ;0;0; ;0)
m
x x x x=
0, 1,

j
f x x x x
x x
x x
x j
= + + →
+ =


+ + =

≥ =
với phương án cực biên x=(6,8,0).
Xét xem x có phải là phương án tối ưu hay
không ?
Giải:
Véctơ x có cơ sở liên kết là:
1 2
1 0
,
0 1
A A
   
= =
 ÷  ÷
   

Ta xác định các véctơ x
j
:

Lần lượt thay j=1,2,3 ta có :

1
1 1 1 1
, (1,6),(1,0) 1z c c x c∆ = − = 〈 〉 − = 〈 〉 −
1.1 6.0 1 0= + − =
2
2 2 2 2
, (1,6),(0,1) 6z c c x c∆ = − = 〈 〉 − = 〈 〉 −
1.0 6.1 6 0= + − =
3
3 3 3 3
, (1,6),(2,1) 9z c c x c∆ = − = 〈 〉 − = 〈 〉 −
1.2 6.1 9 1= + − = −
Ta thấy tất cả các với mọi j. Vậy x
là phương án tối ưu và giá trị tối ưu là:
f(x)=1.6+6.8+9.0=54.
0
j
∆ ≤

Để dễ thấy ta sắp xếp các phép toán lên
bảng sau:
Cơ sở Hệ số P. án 1
x
1
6
x
2
9

( ) 7 26 9 min
2 5
7
0, 1,2,3.
j
f x x x x
x x
x x
x j
= − + →
− =


− + =

≥ =
với phương án cực biên x=(5,0,7).
Xét xem x có phải là phương án tối ưu hay
không ?
Giải:
Véctơ x có cơ sở liên kết là:
1 3
1 0
,
0 1
A A
   
= =
 ÷  ÷
   

, (7,9),(0,1) 9 0z c c x c∆ = − = 〈 〉 − = 〈 〉 − =
Ta thấy và .Vậy bài
toán không có phương án tối ưu. Rõ hơn
là hàm mục tiêu không bị chặn dưới trên
tập phương án.
2
0∆ >
2
( 2, 1) 0x = − − ≤

Cơ sở Hệ số P. án 7
x
1
-26
x
2
9
x
3
A
1
A
3
7
9
5
7
1
0
-2

1 2 3 4
( ) 4 3 7 8 min
3 3 4 5 21
7 6 8
2 5 2 15
0, 1,4.
j
f x x x x x
x x x x
x x x x
x x x x
x j
( )
1,2,3,0x =
Giải: Phương án này có hệ véctơ liên kết
là
=
1
(3,7,2);A
= − −
2
(3, 1, 1);A
=
3
(4,1,5)A

Dễ thấy đây là hệ độc lập tuyến tính nên là
phương án cực biên.
− = − ≠
−

Nếu tồn tại véctơ ngoài cơ sở
liên kết của phương án cực biên
sao cho , và với mỗi j mà ta
luôn tìm được ít nhất một , thì khi
đó ta có thể tìm được một phương án cực
biên mới tốt hơn x, nghĩa là phương án
này làm cho hàm mục tiêu nhỏ hơn
phương án x.
j
A
10 20 0
( ; ; ; ;0;0; ;0)
m
x x x x=
0
j
∆ >
0
j
∆ >
0
ij
x >

Cách xây dựng phương án mới như sau:
Thay thế một véctơ trong cơ sở cũ
bằng một véctơ nằm ngoài cơ sở cũ.
Véctơ đưa vào thay thế ứng với
lớn nhất. Giả sử đó là A
k

Và khi đó phương án mới x
’
được
xác định theo công thức:
10 1 20 2 0
( ; ; ; ; ; ;0; ;0)
j j m mj
x x x x x x x
θ θ θ θ
′
= − − −
Phương án x
’
tốt hơn x.
Đến đây ta xem x
’
như x và kiểm tra x
’

có thỏa định lý 1, hay định lý 2 không.
Nếu không ta lại xây dựng một phương
án mới tốt hơn …
Hoặc có thể biểu diễn véctơ b theo cơ
sở mới này ta có p. án mới x
’
.

Ví dụ: Xét bài toán QHTT
1 2 3 4
1 2 4

Để thuận tiện ta sắp xếp các phần tử lên
bảng và tính toán các ta có:
j
∆
Cơ
sở
Hệ số P. án 1
x
1
-2
x
2
2
x
3
0
x
4
A
1
A
3
1
2
6
8
1
0
1
2

   
   
6 8 3
min ,
4 5 2
 
= =
 
 
10
14
x
x
=
Vậy A
1
bị thay ra.
P. Án mới x
’
được xác định như sau:
Cơ sở mới là A
3
, A
4
. Biểu thị véctơ
theo cơ sở này ta được
6
8
b
 

= = − + =
 ÷
 
Rõ ràng p. án này tốt hơn x.
Bây giờ xem x
’
như x. Ta kiểm tra xem x
’
có phải là p. án tối ưu không.

Ta xác định các véctơ x
j
:
1 3 4 3 4 1
31 41
5 1 5 1
. . ,
4 4 4 4
A x A x A A A x
− −
 
= + = + ⇒ =
 ÷
 
2 3 4 3 4 2
32 42
3 1 3 1
,
4 4 4 4
A x A x A A A x