Chương I
BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
Bài 3. TÍNH CHẤT CỦA TẬP
PHƯƠNG ÁN VÀ TẬP PHƯƠNG ÁN
TỐI ƯU CỦA BÀI TOÁN QUY
HOẠCH TUYẾN TÍNH
1. Tập hợp lồi.
a) Khái niệm tổ hợp lồi:

Giả sử
1 2
, , ,
m n
x x x R
∈
. Điểm
n
x R
∈
được gọi là tổ hợp lồi của các điểm
1 2
, , ,
m
x x x
nếu tồn tại
1 2 1 2
, , , 0, 1
m m
λ λ λ λ λ λ
≥ + + + =

 
= + +
 ÷
 
≥ + + =
b) Định nghĩa tập lồi: Tập được
gọi là tập lồi, nếu
n
L R
⊆
, (1 ) , ;0 1x y L x y L
λ λ λ λ
∀ ∈ ⇒ + − ∈ ∀ ≤ ≤
Nói cách khác, tập L là tập lồi, nếu
đoạn thẳng nối hai điểm trong L nằm gọn
trong L.

Ví dụ: Trong mặt phẳng, đoạn thẳng, đường
thẳng, tia, toàn bộ mặt phẳng, nửa mặt
phẳng, đa giác lồi, tam giác, hình tròn, hình
elip đều là các tập lồi.
Trong không gian, đoạn thẳng,
đường thẳng, mặt phẳng, đa diện lồi, hình
cầu… là các tập lồi.
c) Điểm cực biên của một tập lồi:
Điểm x
0
được gọi là điểm cực biên của
tập lồi L, nếu:


4 0, 4 0, 5 0x y x y x y− = − = + − =
Miền trong của tam giác OAB là tập các
điểm (x,y) thỏa hệ bất phương trình:
4 0
4 0
5
x y
x y
x y
− ≥


− ≤


+ ≤


Chẳng hạn chứng minh điểm B(4,1) là điểm
cực biên
(1 ) , , ,0 1.B X Y X Y OAB
λ λ λ
= + − ∈∆ < <
1 1 2 2
(4,1) ( , ) (1 )( , )x y x y
λ λ
= + −
1 1 2 2
( , ), ( , )x y x y
Trong đó thỏa hệ phương trình

3. Tính chất của bài toán Quy hoạch
tuyến tính dạng chính tắc:
Xét bài toán Quy hoạch tuyến tính
dạng chính tắc:
( ) min
0,
f x
Ax b
x
→
=
≥
Trong đó A là ma trận cấp và
m n
×
1 2
1 2

n
n
x A x A x A b
+ + + =

a) Định nghĩa 1: Giả sử
0
10 20 0
( , , , )
n
x x x x
=

0, 1,3.
j
f x x x
x x x
x x x
x j
= − − →
+ − =


− + =

≥ =
1 2 3
1 2 3
x A x A x A b
+ + =
Ta có:
trong đó
1 2 3
2 1 1 5
, , ,
1 1 4 2
A A A b
−
       
= = = =
 ÷  ÷  ÷  ÷
−
       

22 7
0, ,
3 3
x
 
=
 ÷
 
là một phương án của
bài toán
1 2 3
5
22 7
0. . .
2
3 3
A A A b
 
+ + = =
 ÷
 
Vậy hệ véctơ liên kết của x
1
là:
2 3
,A A

b) Định lý 3: Giả sử
là một phương án khác không của bài
toán Quy hoạch tuyến tính dạng chính

Ví dụ: Xét bài toán Quy hoạch tuyến tính
1 2 3
1 2 3
1 2 3
4 min
2 5
2 5
0, 1,3.
j
f x x x
x x x
x x x
x j
= + + →
+ − =


− + =

≥ =
Ta có là một phương án cực
biên của bài toán, vì hệ véctơ liên kết
với nó là
0
(0,5,5)x
=
2 3
2 1
;
1 2

Nhưng không phải là phương án cực
biên, vì hệ véctơ liên kết với nó là

1 2 3
1 2 1
; ;
1 1 2
A A A
−
     
= = =
 ÷  ÷  ÷
−
     
hệ véctơ này phụ thuộc tuyến tính.
e) Hệ quả 2: Số thành phần dương của
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 tối đa là
bằng m (m là số dòng của matrận A).
f) Định lý 4: Nếu bài toán Quy hoạch tuyến
tính dạng chính tắc có tập phương án khác
rỗng thì nó có ít nhất một phương án cực
biên.

Các định lý trên đây đã chỉ ra cho chúng ta
cách thành lập 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 là:
- Xác định các hệ gồm m véctơ độc lập
tuyến tính, của hệ các véctơ cột của A. Hệ

x x x
x j
= + + →
+ + =


− + =

≥ =

Giải:
1 2 3 4
1 0 1 1
, , ,
0 1 1 2
A A A A
       
= = = =
 ÷  ÷  ÷  ÷
−
       
Có tất cả 4 véctơ cột của A là
Từ đó lấy được 6 hệ con độc lập tuyến
tính là
{ } { } { }
{ } { } { }
1 2 1 3 1 4
2 3 2 4 3 4
; , ; , ; ,
; , ; , ;

3
9 1
,0,0,
2 2
x
 
=
 ÷
 
4
(0,6,5,0)x
=
5
(0, 9,0,5)x
= −
6
(0,0,3,2)x
=
Loại bỏ các véctơ có thành phần âm ta
được 4 phương án cực biên là

1
(5,1,0,0)x
=
3
9 1
,0,0,
2 2
x
 

- Lần lượt thử các phương án cực biên ta
suy ra phương án tối ưu và giá trị tối ưu
của hàm mục tiêu.
Ví dụ: Giải bài toán QHTT
1 3 4
1 3 4
2 3 4
2 5 min
5
2 1
0, 1,4 .
j
f x x x
x x x
x x x
x j
= + + →
+ + =


− + =

≥ =

Giải: Ví dụ này ta đã xét ở trên.
- Tập phương án không rỗng là hiển nhiên.
- Hàm mục tiêu bị chặn dưới bởi 0, vì
1 3 4
2 5 0f x x x
= + + >