ðH Công nghiệp Tp.HCM 23/12/2010
Quy ho
ạch tuyến tính ðại học
& Cao ñẳng 1
Chương I
BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
Bài 1. MỘT SỐ BÀI TOÁN DẪN ðẾ
N
BÀI TOÁN QHTT.
1.Bài toán lập kế hoạch sản xuất khi tài
nguyên hạn chế.
Một xí nghiệp dự ñịnh sản xuất hai loại
sản phẩm A và B. Các sản phẩm này ñược
chế tạo từ ba loại nguyên liệu I, II và III .
Số lượng các nguyên liệu I, II, và III mà
xí nghiệp có là 8, 24, 12. Số lượng các
nguyên liệu cần ñể sản xuất một ñơn vị sản
phẩm A, B ñược cho ở bảng sau ñây.
061B
402A
III
(<=12)
II (<=24)I (<=8)
Cần lập một kế hoạch sản xuất,( tức là
tính xem nên sản xuất bao nhiêu ñơn vị sản
phẩm từng loại) ñể lãi thu ñược là nhiều
nhất.
Biết sản phẩm A lãi 3 triệu ñồng cho một
ñơn vị sản phẩm, sản phẩm B lãi 5 triệu
ñồng cho một ñơn vị sản phẩm .
Lập kế hoạch.

≤


≤


≥ ≥

ðH Công nghiệp Tp.HCM 23/12/2010
Quy ho
ạch tuyến tính ðại học
& Cao ñẳng 2
Có ba xí nghiệp may I, II, III cùng có
thể sản xuất áo vét và quần.
Nếu ñầu tư 1000 USD vào XN I thì
cuối kỳ sẽ cho 35 áo vét và 45 quần
Nếu ñầu tư 1000 USD vào XN II thì cuối
kỳ sẽ cho 40 áo vét và 42 quần
Nếu ñầu tư 1000 USD vào XN III thì cuối
kỳ sẽ cho 43 áo vét và 30 quần
Lượng vải và số giờ công ñể sx một áo
hoặc một quần cho ở bảng sau.
2.5 m vải
15 giờ công
2.6 m vải
12 giờ công
2.8 m vải
10 giờ công
Quần
3.8 m vải

ñ
ộ
ng
4. Tổng số vốn ñầu tư nhỏ nhất .
Lập kế hoạch.
Giả sử x
j
(ñơn vị là 1000 USD) là số
vốn ñầu tư vào các XN I, II, III.
a) Số áo vét thu ñược ở ba XN là
35x
1
+40x
2
+43x
3
b) Số quần thu ñược ở ba XN là
45x
1
+42x
2
+30x
3
c) Tổng số vải cần ñể may áo vét là
1 2 3
3.5 35 4 40 3.8 43
m x m x m x
× + × + ×
d) Tổng số vải cần ñể may quần là
1 2 3

Ta có bài toán nh
ư
sau
ðH Công nghiệp Tp.HCM 23/12/2010
Quy ho
ạch tuyến tính ðại học
& Cao ñẳng 3
(
)
min
1 2 3
248.5 269.2 238.4 10 000 (1)
1 2 3
1150 1144 1224 52 000 (2)
1 2 3
45 42 30 35 40 43 (3)
1 2 3 1 2 3
35 40 43 1500 (4)
1 2 3
x x x
x x x
x x x
x x x x x x
x x x
+ +
+ + ≤


+ + ≤


= + + →

+ + ≤

+ + ≤


+ − ≥


+ + ≥


≥ ∀ =

2. Bài toán vận tải (Dạng tổng quát là bài
tóan phân phối).
Có một loại hàng cần ñược chuyên chở
từ hai kho (trạm phát) P
1
và P
2
tới ba nơi
tiêu thụ (trạm thu) T
1
, T
2
, T
3
.

ij
là lượng hàng vận chuyển từ kho P
i
ñến nơi nhận T
j
.
Ta có ma trận chi phí vận chuyển là
11 12 13
21 22 23
5 2 3
2
x x x
x x x
 
 
 
Tổng chi phí
11 12 13 21 22 23
5 2 3 2
f x x x x x x
= + + + + +
11 12 13
21 22 23
x x x
x x x
 
 
 
Ma trận phương án
1 1 1 2 1 3

5 2 3 2 min
30
75
35
25
45
0 ,
ij
f x x x x x x
x x x
x x x
x x
x x
x x
x i j
= + + + + + →
+ + =


+ + =


+ =


+ =


+ =


Lợn (400)
14118
Bò (480)
Nấu chín ngoài
giờ
250 (tấn)
Nấu chín
420
(tấn)
Tươi
440
(tấn)
ðây là một dạng của bài toán vận tải,
nhưng ta tìm phương án ñể có “cước phí”
vận chuyển lớn nhất.
Ký hiệu theo thứ tự là
lượng thịt Bò, Lợn, Cừu dưới dạng Tươi,
Nấu chín, Nấu chín ngoài giờ mà nhà máy
sẽ sản xuất trong ngày. Ta có bài toán :
= =
, 1,3; 1,3
ij
x i j
= + + + + +
+ + →
11 12 13 21 22 23
31 32 33
8 11 14 4 7 12
4 9 13 max
f x x x x x x

420
250
0, ,
ij
x x x
x x x
x x x
x x x
x x x
x x x
x i j
ðH Công nghiệp Tp.HCM 23/12/2010
Quy ho
ạch tuyến tính ðại học
& Cao ñẳng 5
Một phân xưởng có 2 công nhân nữ và
3 công nhân nam. Phân xưởng cũng có 1
máy tiện lọai I, 2 máy tiện lọai II và 2 máy
tiện lọai III. Năng suất (chi tiết / ngày) của
các công nhân ñối với mỗi lọai máy tiện
ñược cho trong bảng sau:
Bài tóan 3:
1198Nữ
(2)
7810Nam
(3)
Máy lọai III
(2 máy)
Máy lọai II
(2 máy)

; (3)
0; , 0; , ; .
n i
n i
n i
j j j
a x a x a x b i I
a x a x a x b i I
a x a x a x b i I
x j J x j J x R j J
+ + + ≤ ∈


+ + + ≥ ∈


+ + + = ∈

≥ ∈ ≤ ∈ ∈ ∈
Trong ñó rời nhau và
, rời nhau và .
1 2 3
, ,
I I I
{
}
1 2 3
1,2, ,
I I I m
∪ ∪ =

x x
x R
x
= + − + →
+ ≤


− − ≤ −


+ + ≥


+ − + =

≥
∈
≤
{
}
{
}
{
}
{
}
{
}
{
}

x x x x R x
= + − + →
+ + ≤


− − − ≥ −


+ + + ≤


+ − + + =


+ + + ≥

≥ ∈ ≤
{
}
{
}
{
}
{
}
{
}
{
}
1 2 3 1 2 3

tiêu ñạt giá trị nhỏ nhất (nếu là bài toán
min), hoặc hàm mục tiêu lớn nhất (nếu là
bài toán max) ñược gọi là phương án tối ưu
của bài toán QHTT.
3. Dạng chính tắc của bài toán Quy
hoạch tuyến tính:
Bài toán Quy hoạch tuyến tính có
dạng sau ñây, gọi là dạng chính tắc
1
1
( ) , max (min)
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
=
=
= = 〈 〉 →
= =
≥ =
∑
∑

n
m m mn
a a a
a a a
A
a a a
 
 
 
=
 
 
 
1 1
2 2
,

n m
x b
x b
x b
x b
   
   
   
= =
   
   
   
1

1 2 3
1 2 3
( ) 4 5 max
4 5 4
4 5 3
0, 1,2,3.
j
f x x x x
x x x
x x x
x j
= + + →
+ + ≤


+ + ≥

≥ =
1 2 3
1 2 3
1 2 3
1 2 3
( ) 4 7 5 min
4
2 5 3
0, 0,
f x x x x
x x x
x x x
x x x R

+ ≤

≥
Biểu diễn tập phương án trên mặt phẳng
x0y, ta ñược tứ giác OABC.
C
O
A
B
O(0,0); A(0,4); B(3,2); C(5,0). Hàm mục tiêu có dạng
của một ñường thẳng: f=4x
1
+ x
2
. Cho f=0 ta có ñường
thẳng ñi qua gốc tọa ñộ.
Tịnh tiến ñường thằng (d) theo một hướng
nào ñó sẽ làm cho giá trị hàm mục tiêu
tăng, ngược lại sẽ làm hàm mục tiêu giảm.
Ở bài toán này ta cần làm cho hàm mục tiêu
tăng. Rõ ràng ñi theo hướng mũi tên sẽ làm
cho hàm mục tiêu tăng.
( ) (0;0) 0; ( ) (0;4) 4;
( ) (3;2) 14; ( ) (5;0) 20
f O f f A f
f B f f C f
= = = =
= = = =
Hàm mục tiêu ñạt giá trị max là 20 tại
ñiểm C(5;0).

1 2
1 2
( ) 3 3 max
6
3 3
, 0
f x x x
x x
x x
x x
= + →
+ ≤


+ ≥

≥
2)
3) Một công ty sản xuất hai loại sơn nội
thất và sơn ngoài trời. Nguyên liệu ñể sản
xuất gồm hai loại A, B với trữ lượng là 6
tấn và 8 tấn tương ứng. ðể sản xuất một tấn
sơn nội thất cần 2 tấn nguyên liệu A và 1
tấn nguyên liệu B. ðể sản xuất một tấn sơn
ngoài trời cần 1 tấn nguyên liệu A và 2 tấn
nguyên liệu B. Qua ñiều tra thị trường công
ty biết rằng nhu cầu sơn nội thất không hơn
sơn ngoài trời quá 1 tấn, nhu cầu cực ñại
của sơn nội thất là 2 tấn.
Giá bán một tấn sơn nội thất là 2000 USD,

R R
Ví dụ 3.1: 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.
2. ð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:
1 2 1 2 1 2
0 0
(1 ) , ;
0 1.
x x x x x L x x x
λ λ
λ
= + − ∈ ⇒ = =
< <
Ví dụ 3.2:Trong R, cho ñoạn [1, 4]. Hai
ñiểm 1; 4 là hai ñiểm cực biên.
Ta sẽ chứng minh x=y=1.
1 (1 ) , , [1;4],0 1.
x y x y
λ λ λ
= + − ∈ < <
Giải: Giả sử



+ ≤

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
ở trên.
1 2
1 2
4 (1 )
1 (1 )
x x
y y
λ λ
λ λ
= + −


6
3 3
, 0
f x x x
x x
x x
x x
= + →
+ ≤


+ ≥

≥
4. 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

.
hệ véctơ
{
}
j
A
Ví dụ 3.5: 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
4 2
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

3 3
A A A b
 
+ + = =
 
 
Vậy hệ véctơ liên kết của x
0
là:
1 2
,
A A
và ta có
1
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

là một phương án cực biên.
0
10 20 0
( , , , )
n
x x x x
=
c) Hệ quả 1: Số 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à hữu hạn.
d) ðịnh nghĩa 2: 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 ñược gọi là không suy biến nếu
số thành phần dương của nó bằng m.
Nếu số thành phần dương ít hơn m thì
phương án cực biên này gọi là suy biến.
Ví dụ 3.6: 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

x =
1
1
1
A
 
=
 
 
hệ một véctơ này ñộc lập tuyến tính.
Nhưng ñây không phải là phương án
cực biên không suy biến vì số thành phần
dương của nó là 1.
2
(1,4,4)
x =
là một phương án của bài toán.
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
−
     
= = =
     
−
     

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ệ
này hữu hạn và tối ña là hệ con.
!
!( )!
m
n
n
C
m n m
=
−
- Biểu diễn véctơ b theo các hệ con ở
trên, ta ñược các hệ số biểu diễn. Thành
lập véctơ x có các thành phần là hệ số
biểu diễn. Khi ñó x là một phương án.
ðH Công nghiệp Tp.HCM 23/12/2010
Quy ho
ạch tuyến tính ðại học
& Cao ñẳng 11
- Loại ñi những véctơ x có thành phần
âm, các véctơ còn lại là các phương án
cực biên.
Ví dụ 3.7: Tìm tất cả các phương án cực
biên của tập phương án của bài toán
1 3 4
1 3 4
2 3 4
2 5 min

}
{
}
{
}
{ } { } { }
1 2 1 3 1 4
2 3 2 4 3 4
; , ; , ; ,
; , ; , ;
A A A A A A
A A A A A A
Biểu diễn véctơ theo các hệ ñộc
lập tuyến tính này, ta có
5
1
b
 
=
 
 
1 2 1 3 1 4
2 3 2 4 3 4
9 1
5 6
2 2
6 5 9 5 3 2
b A A b A A b A A
b A A b A A b A A
= + = − = +

(5,1,0,0)
x =
3
9 1
,0,0,
2 2
x
 
=
 
 
4
(0,6,5,0)
x =
6
(0,0,3,2)
x =
g) ðịnh lý 5: Nếu bài toán Quy hoạch
tuyến tính dạng chính tắc có phương án tối
ưu thì nó sẽ có ít nhất một phương án cực
biên là phương án tối ưu.
h) ðịnh lý 6: Nếu tập phương án của bài
toán Quy hoạch tuyến tính không rỗng và
là một ña diện lồi thì bài toán sẽ có ít nhất
một phương án tối ưu là phương án cực
biên.
i) ðịnh lý 7: ðiều kiện cần và ñủ ñể bài
toán Quy hoạch tuyến tính có phương án
tối ưu là tập phương án không rỗng và hàm
mục tiêu bị chặn dưới (nếu là bài toán min)

ðH Công nghiệp Tp.HCM 23/12/2010
Quy ho
ạch tuyến tính ðại học
& Cao ñẳng 12
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 0
f x x x
= + + >
Theo ñịnh lý 7 bài toán có phương án
tối ưu. Theo ñịnh lý 5 bài toán có phương
án cực biên là phương án tối ưu.
Theo ví dụ trên có tất cả các phương án
cực biên là:
1
(5,1,0,0)
x =
3
9 1
,0,0,
2 2
x
 
=
 
 
4
(0,6,5,0)

1) Cho bài toán (P)
a) ðưa bài toán (P) về dạng chính tắc; ta
gọi bài toán này là (Q).
b) Liệt kê tất cả các phương án cực biên
của (Q).
c) Tìm phương án tối ưu của (Q).
1 2
1 2
1 2
1 2
( ) 4 m ax
5
2 3 12
; 0.
f x x x
x x
x x
x x
= + →
+ ≤


+ ≤

≥
2) Tương tự bài 1) với các bài toán:
1 2 3
1 2 3
1 2 3
j

+ ≥


+ ≥

≥ =
a)
b)
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
=
=

n m
n
x x x x b b b b
c c c c
= =
=
Trong ñó:
ðH Công nghiệp Tp.HCM 23/12/2010
Quy ho
ạch tuyến tính ðại học
& Cao ñẳng 13
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

Nếu x không phải là phương án tối ưu thì ta
tìm phương án cực biên khác tốt hơn tức là
phương án làm cho giá trị hàm mục tiêu nhỏ
hơn.
Muốn vậy ta phải xây dựng một cơ sở mới,
ñơn giản nhất là thay thế một véctơ trong cơ sở
cũ bằng một véctơ nằm ngoài cơ sở cũ.
1
, , 1,
m
j
j i ij
i
z c x c x j n
=
= = 〈 〉 =
∑
ðặ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

cơ sở liên kết của phương án cực biên
sao cho và thì bài toán Quy
hoạch tuyến tính dạng chính tắc 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.
10 20 0
( ; ; ; ;0;0; ;0)
m
x x x x=
0
j
∆ >
0
j
x
≤
Ví dụ 4.1: Xét bài toán QHTT
1 2 3
1 3
2 3
( ) 6 9 min
2 6
8
0, 1,2,3.
j
f x x x x
x x
x x
x j
= + + →

j m
j j mj
A x A x A x A
= + + +
1 2
( ; ; ; )
j
j j mj
x x x x
=
1 1 2 1 2 1
11 21
1. 0. (1,0)
A x A x A A A x= + = + ⇒ =
2 1 2 1 2 2
12 22
0. 1. (0,1)
A x A x A A A x= + = + ⇒ =
3 1 2 1 2 3
13 23
2. 1. (2,1)
A x A x A A A x= + = + ⇒ =
1
,
m
j
j j j i ij j j
i
z c c x c c x c
=

ðể dễ thấy ta sắp xếp các phép toán lên
bảng sau:
54f(x)
2
1
0
1
1
0
6
8
1
6
A
1
A
2
9
x
3
6
x
2
1
x
1
P. ánHệ sốCơ sở
1
0
∆ =

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
   
= =
   
   
Ta xác ñịnh các véctơ x
j
:
1 1 3 1 3 1
11 31

, (7,9),(0,1) 9 0
z 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) 0
x
= − − ≤
ðH Công nghiệp Tp.HCM 23/12/2010
Quy ho
ạch tuyến tính ðại học
& Cao ñẳng 15
0
1
-2
-1
1
0
5
7
7
9
A
1

thức ñã biết.
Chẳng hạn ví dụ sau.
Ví dụ 4.3: Cho bài toán
Chứng minh là phương án cực
biên, tối ưu của bài tóan ñã cho.
= − + + + →
+ + + =


− + + =


− + + =

≥ =
1 2 3 4
1 2 3 4
1 2 3 4
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

131 131 131
x x x
x B A
−
= = =
 
= =
 
 
1 2 3
4
4 4
0
1176
, 0
131
c x c
∆ = ∆ = ∆ =
−
∆ = − = <
Vậy x là phương án cực biên, tối ưu.
4. ðịnh lý 3:
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.

A
s
như sau:
0 0
min : 0
i s
ik
ik sk
x x
x
x x
θ
 
= > =
 
 
Trong ñó x
ik
là hệ số biểu diễn của
A
k
theo cơ sở liên kết của p. án x.
ðH Công nghiệp Tp.HCM 23/12/2010
Quy ho
ạch tuyến tính ðại học
& Cao ñẳng 16
Và khi ñó phương án mới x
’
ñược
xác ñịnh theo công thức:

f x x x x x
x x x
x x x
x j
= − + + →
+ + =


+ + + =

≥ =
Với p. án x=(6,0,8,0) cơ sở liên kết là:
1 3
1 0
,
0 1
A A
   
= =
   
   
Trước tiên ta xem x có phải p. án tối
ưu hay không.
ðể 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
∆
1407022f(x)
4
5

j
ñều có hệ số dương.
Do ñó có thể tìm p. án mới tốt hơn.
0
j
∆ >
Véctơ ñưa vào thay thế ñó là A
4
.
0 10 30
4
4 14 34
min : 0 min ,
i
i
i
x x x
x
x x x
θ
   
= > =
   
   
6 8 3
min ,
4 5 2
 
= =
 

     
= = +
     
     
Từ ñó ta có p. án mới là:
1 3
0,0, ,
2 2
x
 
′
=
 
 
Giá trị hàm mục tiêu lúc này là:
1 3 1
( ) 0,0, , 0 2.0 2. 1
2 2 2
f x f
 
′
= = − + =
 
 
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.

j j
c x c
∆ = 〈 〉 −
Lần lượt thay j=1, 2, 3, 4 ta có :
4 3 4 3 4 3
34 44
0. 1. (0,1)
A x A x A A A x= + = + ⇒ =
ðH Công nghiệp Tp.HCM 23/12/2010
Quy ho
ạch tuyến tính ðại học
& Cao ñẳng 17
1
1 1 1 1
5 1 7
, (2,0), , 1
4 4 2
z c c x c
− −
 
∆ = − = 〈 〉 − = 〈 〉 − =
 
 
2
2 2 2 2
3 1 7
, (2,0), , ( 2)
4 4 2
z c c x c
 

A
3
0
x
4
2
x
3
-2
x
2
1
x
1
P. ánHệ sốCơ
sở
Ta liên hệ hai bảng này với nhau:
1407022f(x)
4
5
0
1
1
2
1
0
6
8
1
2

1/2
0
2
A
4
A
3
5. Phương pháp ñơn hình cho bài toán
chính tắc có sẵn ma trận ñơn vị:
Xét bài toán chính tắc:
( ) , min
0
f x c x
Ax b
x
= 〈 〉 →
=
≥
Trong ñó A có sẵn một ma trận ñơn vị cấp
m. Không mất tính tổng quát có thể giả sử
ñó là m cột ñầu , và phương
án cực biên x trong bước lặp ñầu tiên là:
1 2
, , ,
m
A A A
1 2
( , , , ,0,0, ,0) 0
m
x b b b

mk
x
1m+1
x
2m+1
…
x
sm+1
x
mm+1
0
0

0

1
0
1

0

0
1
0

0

0
b
1

x
n
c
k
x
k
…c
m+1
x
m+1
c
m
x
m
…c
2
x
2
c
1
x
1
Ph
án
H.
số
c
j
Cơ
sở

∆ = =
Thuật toán ñơn hình ñược thực hiện một số
bước như sau:
Bước 1: Nếu thì phương án
ñang xét là tối ưu.
Nếu mà ứng với j này
thì bài toán không có phương án tối ưu.
0 , 1,
j
j n
∆ ≤ ∀ =
0
j
∆ >
0, 1,
ij
x i m
≤ ∀ =
Nếu không thỏa bước 1 ta sang bước 2.
Bước 2:
i) Xác ñịnh ,véctơ
ñưa vào thay thế .
{
}
max / 0
k j j
∆ = ∆ ∆ >
k
A
ii) Xác ñịnh véctơ ñưa ra khỏi cơ sở

0, 1,5.
j
f x x x x x x
x x x
x x x
x x x
x j
= − − + + + →
+ + =


+ + =


+ + + =

≥ =
Giải: ðây là bài toán QHTT dạng chính
tắc mà ma trận A có sẵn ma trận ñơn vị.
-19-14000-98f(x)
1
3
1
2
1
3
0
0
1
0

số cj
Cơ
sở
200-4-5
Bài toán ñã có dấu hiệu tối ưu, phương
án tối ưu là , giá trị tối ưu
-98.
(10,12,15,0,0)
x
=
Ví dụ 4.6: Giải bài toán
1 2 3 4 5 6
1 2 5
1 2 3 6
2 3 4
( ) 2 4 0 0 min
3 4
2 3
4 3
0, 1,6.
j
f x x x x x x x
x x x
x x x x
x x x
x j
= − − + − + + →
+ + =



1
1
1
2
0
4
3
3
0
0
-1
A5
A6
A4
x6x5x4x3x2x1PaHscs
00-11-4-2
0-10-501-7f(x)
0
1
0
1/3
-1/3
-1/3
0
0
1
0
-1
4
1

0
1
0
1
1
2
-4
-2
-1
A2
A1
A4
ðH Công nghiệp Tp.HCM 23/12/2010
Quy ho
ạch tuyến tính ðại học
& Cao ñẳng 19
Ví dụ 4.7: Giải bài toán
1 2 3
1 2 3
1 2 3
1 3
( ) 2 3 min
5 15
3 2 2 20
4 10
0, 1,3.
j
f x x x x
x x x
x x x

f x x x x x x x
x x x x
x x x x
x x x
x j
= − + − + + + →
− + + =


+ − + =


+ + =

≥ =
Lúc này ma trận A ñã có sẵn một ma trận
ñơn vị, cho nên sắp xếp các các phần tử
lên bảng ñơn hình và tính toán ta có bảng
sau:
0001-320f(x)
0
0
1
0
1
0
1
0
0
1

-11/4
1/4
-5
2
0
0
0
1
25/2
25/2
5/2
0
0
-2
A4
A5
A1
-1000-3-2-10f(x)
-1
2
1
0
1
0
1
0
0
0
0
1

x
→
=
≥
sao cho thì x là phương án tối
ưu.
0, 1,
j
j n
∆ ≥ ∀ =
ðịnh lý 2
’
: Nếu tồn tại véctơ A
j
ngoài cơ sở
liên kết của phương án cực biên
x=(x
10
,x
20
,…,x
m0
,0,0, 0) sao cho và
thì bài toán Quy hoạch tuyến tính
dạng chính tắc không có phương án tối ưu.
Rõ hơn là hàm mục tiêu không bị chặn trên
,
trên tập phương án.
0
j

∆ <
0
ij
x
>
{
}
min / 0
k j j
∆ = ∆ ∆ <
ðH Công nghiệp Tp.HCM 23/12/2010
Quy ho
ạch tuyến tính ðại học
& Cao ñẳng 20
Ví dụ 4.8: Giải bài toán
1 2 3
1 2 3
1 2
1 2
( ) 2 3 max
5 6
2 2 7
2 5
0, 1,3.
j
f x x x x
x x x
x x
x x
x j

j
f x x x x
x x x
x x x
x x x
x j
= + + →
− + =


+ + =


− + + =

≥ =
Lúc này ma trận A ñã có sẵn một ma trận
ñơn vị, cho nên sắp xếp các các phần tử lên
bảng ñơn hình và tính toán ta có bảng sau:
000-8-16f(x)
0
0
1
0
1
0
1
0
0
-5

3
-1/2
37/2
2
5/2
1
0
3
A3
A4
A2
7/35/300088/3f(x)
2
-1/3
1/3
1/2
1/3
1/6
1
0
0
0
0
1
0
1
0
39/2
2/3
17/6

1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
( ) 5 2 7 8 max
2 3 4 5 20
8 6 9
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
61 163 73
0, , ,
60 60 60
x
 
=
 
 
6. Thuật toán ñơn hình cho bài toán
chính tắc không có sẵn ma trận ñơn vị:
Giả sử bài toán chính tắc
( ) min
(*)
0
f x


≥ =
Giả sử ma trận A còn thiếu m véctơ ñơn vị.
Ta thêm vào m ẩn giả x
m+1
, x
m+2
, ,x
m+n
.
Khi ñó bài toán có dạng như sau:
1 2
( ) min
( )
0
n n n m
f x Mx Mx Mx
Bx b M
x
+ + +
+ + + + →
=
≥
Trong ñó B là ma trận cấp mx(m+n) với n
cột ñầu là ma trận A, m cột sau là m véctơ
ñơn vị. x là véctơ có n+m thành phần . M là
một số dương rất lớn; lớn hơn bất kỳ số nào
cần so sánh. Ta có các kết qủa sau.
ðH Công nghiệp Tp.HCM 23/12/2010
Quy ho

=
Nhận xét: ðịnh lý 4 phần a) chỉ có một
chiều. Phản ñảo của phần a) là: Có phương
án cực biên tối ưu của bài toán (M) mà có
những ẩn giả khác không thì bài toán (*) vô
nghiệm (không có phương án).
Mục b) là hai chiều và chúng ta hay áp
dụng chiều ngược lại: bài toán (M) có
phương án tối ưu
1 2
( , , , ,0,0, ,0)
n
x x x x
=
thì bài toán (*) có phương án tối ưu
1 2
( , , , )
n
x x x x
=
Khi giải bài toán (M) bằng phương pháp
ñơn hình thì các biểu thức f và có chứa
tham số M . Ở dòng cuối của bảng ñơn hình
ta chia làm hai dòng, dòng trên ghi các hệ
số ñứng trước M, dòng cuối ghi các hệ số
tự do. , vì M là số dương rất lớn
nên khi so sánh các số ta có quy ước
sau:
∆
j j j

δ γ
> ∀

∆ = + > ⇔

= >


;
.
k j k j
k k k j j j
k j k j
M M
δ δ γ γ
δ γ δ γ
δ δ γ γ
> ∀

∆ = + > ∆ = + ⇔

= >


Ví dụ 4.10: Xét lại bài toán ở trên
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
( ) 3 3 min

1 2 3 4 6
1 2 3 4 7
( ) 3 3 min
2 2
2 6 3 3 9
6
0, 1,7.
j
f x x x x x Mx Mx Mx
x x x x x
x x x x x
x x x x x
x j
= − + + − + + + →
+ − + + =


− + + + =


− + − + =

≥ =
Lúc này ma trận A ñã có sẵn một ma
trận ñơn vị, cho nên sắp xếp các các phần
tử lên bảng ñơn hình và tính toán ta có bảng
sau
:
0
0

2
-6
-1
1
2
1
2
9
6
M
M
M
A5
A6
A7
x
7
x
6
x
5
x
4
x
3
x
2
x
1
PaHSCS

-1
5
2
2
-10
3
1
0
0
2
5
4
-3
M
M
A1
A6
A7
ðH Công nghiệp Tp.HCM 23/12/2010
Quy ho
ạch tuyến tính ðại học
& Cao ñẳng 22
0
0
-7/5
0
-6/5
-3
-12/5
-2

3
1
2
-3
3
M
A1
A3
A7
-3 1 3 -1 M M M
-1
7
-1
-14/5
-1
-
22/5
0
-94/5
0
0
0
0
0
0
0
8
f(x)
0
2

1 2 3
1 2 3
( ) 2 3 min
3 4 5
2 5 12
0, 1,2,3.
j
f x x x x
x x x
x x x
x j
= + + →
+ + =


+ + =

≥ =
1 2 3 4
1 2 3 4
1 2 4
1 2 4
( ) 4 2 3 7 max
3 14
2 5 4 22
3 7 23
0, 1,4 .
j
f x x x x x
x x x x

= − − − →
+ + + =


+ + ≤


+ + ≤

≥ =
3)
4) Bài tập 16; 17 trang 66; 67 Giáo trình.
5) Một xí nghiệp dự ñịnh sản xuất ba loại
sản phẩm A, B và C. Các sản phẩm này
ñược chế tạo từ ba loại nguyên liệu I, II và
III . Số lượng các nguyên liệu I, II và III mà
xí nghiệp có lần lượt là 57, 88, 30 ñơn vị
nguyên liệu. Số ñơn vị nguyên liệu cần ñể
sản xuất một ñơn vị sản phẩm A, B, C ñược
cho ở bảng sau ñây
153C
162B
314A
IIIIII
Hỏi Xí nghiệp nên sản xuất bao nhiêu ñơn vị sản
phẩm A, B, C ñể thu ñược tổng số lãi nhiều nhất
(với giả thiết các sản phẩm làm ra ñều bán hết),
nếu biết rằng lãi 35 triệu ñồng cho một ñơn vị
sản phẩm loại A, lãi 40 triệu ñồng cho một ñơn
vị sản phẩm loại B, lãi 40 triệu ñồng cho một

7) Một công ty sản xuất hai loại thực phẩm A, B
. Nguyên liệu ñể sản xuất gồm ba loại Bột,
ðường, Dầu thực vật, với trữ lượng tương ứng
là 30 tấn,12 tấn, 6 tấn . ðể sản xuất 1 tấn thực
phẩm loại A cần 0.5 tấn Bột, 0.5 tấn ðường, 0.2
tấn Dầu thực vật. ðể sản xuất 1 tấn thực phẩm
loại B cần 0.8 tấn Bột, 0.4 tấn ðường, 0.4 tấn
Dầu thực vật. Giá bán một tấn thực phẩm A là
4000 USD, giá bán một tấn thực phẩm B là
4500
USD.
Hỏi cần sản xuất mỗi loại thực phẩm bao
nhiêu tấn ñể có doanh thu lớn nhất ?
Chương II
LÝ THUYẾT ðỐI NGẪU
Bài 1. BÀI TOÁN ðỐI NGẪU VÀ MỘT
SỐ TÍNH CHẤT
1. ðịnh nghĩa bài toán ñối ngẫu:
Cho bài toán Quy hoạch tuyến tính, ta
gọi là bài toán (P), ñối ngẫu của bài
toán (P) là bài toán mà ta gọi là (Q),
cho tương ứng ở bảng sau :
Bài toán ñối ngẫuChỉ sốBài toán gốc
( ) , min
f x c x= →
( ) , max
g y b y
= 〈 〉 →
1
n

ij j i
j
a x b
=
=
∑
3
i I
∈
i
y
∈
ℝ
0
j
x
≥
1
j J
∈
1
m
ij i j
i
a y c
=
≤
∑
0
j

f x c x= →
( ) , min
g y b y
= 〈 〉 →
1
n
ij j i
j
a x b
=
≤
∑
1
i I
∈
0
i
y
≥
1
n
ij j i
j
a x b
=
≥
∑
2
i I
∈

a y c
=
≥
∑
0
j
x
≤
2
j J
∈
1
m
ij i j
i
a y c
=
≤
∑
j
x
∈
ℝ
3
j J
∈
1
m
ij i j
i


+ + + − + =


+ + + + − ≥


+ + − + + =


+ + + + ≤

≥ ≤ ∈ ≥ ∈ ≤
Ví dụ 1.2: Viết bài toán ñối ngẫu của bài
toán sau ñây:
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4
1 2 3 4 5
1 2 3 4 5
( ) 23 9 19 71 23 max
14 4 14 3 4
7 3 7 8 3
17 10 6 17 6 7
2 12 3 3
4 5 4 2
9 11 8 5 4 1

ạch tuyến tính ðại học
& Cao ñẳng 24
2. Mối quan hệ giữa bài toán gốc và bài
toán ñối ngẫu:
Trong phần này ta chỉ xét bài toán gốc
dạng min.
2.1. ðịnh lý 1: Cho x, y theo thứ tự là
phương án của bài toán gốc và ñối ngẫu ta
có hay tương ñương .
( ) ( )
f x g y
≥
, ,
c x b y
≥
2.2. ðịnh lý 2: Nếu cả hai bài toán gốc và
ñối ngẫu ñều có tập phương án không rỗng
thì cả hai bài toán ñều có phương án tối ưu
và giá trị tối ưu của các hàm mục tiêu là
bằng nhau.
2.5. ðịnh lý 5: (ðịnh lý ñộ lệch bù) Các
phương án của bài toán gốc và ñối
ngẫu ñều là phương án tối ưu ñiều kiện cần
và ñủ là
, , 0
b Ax y c yA x
− = − =
,
x y
1

Ví dụ 1.3: Bài toán Quy hoạch tuyến tính
1 2 3 4
1 2 4
2 3 4
( ) 2 2 0 min
4 6
( )
2 5 8
0, 1,2,3,4;
j
f x x x x x
x x x
P
x x x
x j
= − + + →
+ + =


+ + + =

≥ =
có phương án tối ưu là và giá
tr
ị
t
ố
i
ưu
l

2
4 5 0
,
g y y y
y
y y
y
y y
y y
= + →
≤


+ ≤ −


≤


+ ≤

∈
ℝ
Bài toán ñối ngẫu (Q) là:
Phương án tối ưu của bài toán (Q) ñược
tìm từ hệ phương trình
(
)
( )
( )


− − + =



− + =


− + =

Thế các giá trị của ñã biết
vào hệ phương trình ta ñược
(2,4,0,0)
x =
(
)
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
1 2 4 1
1
2





− + =

− + =
 
⇔
 
− − + =
− − + =


− + =
− + =


− + =

− + =

x x x y
y
y
x x x y
y y
y y x
y y
y y x

− + =
 
⇔
 
−
=
− − + =
 


ðH Công nghiệp Tp.HCM 23/12/2010
Quy ho
ạch tuyến tính ðại học
& Cao ñẳng 25
Vậy phương án tối ưu của bài toán ñối
ngẫu là: và giá trị tối ưu là:
( )
1 2
3
, 1,
2
y y y
−
 
= =
 
 
1 2
3
( ) 6 8 6.1 8. 6

1 2 3
1 2 3
1 2 3
( ) 3 2 7 max
3 3 15
4 19
, , 0
g y y y y
y y y
y y y
y y y
= + + →
+ + ≤


+ + ≤

≥
Nhận thấy bài toán này dễ hơn. Ta giải
bài toán ñối ngẫu.
1 2 3 4 5
1 2 3 4
1 2 3 5
1 2 3 4 5
( ) 3 2 7 0 0 max
3 3 15
4 19
, , , , 0
= + + + + →
+ + + =

=………. .
Ta sẽ tìm phương án tối ưu của bài toán
gốc. Dùng ñịnh lý ñộ lệch bù.
Bây giờ ta giải bài toán gốc và làm cách
như trên ñể tìm lại phương án tối ưu của
bài toán ñối ngẫu.
Thêm vào hai ẩn phụ và ba ẩn giả, sau ñó sắp xếp các
phần tử lên bảng ñơn hình và tính toán ta ñược.
15 19 0 0 0 M M M

Co So CJ Ph.An A1 A2 A3 A4 A5 A6 A7 A8

A6 M 3 3 1 -1 0 0 1 0 0
A7 M 2 1 1 0 -1 0 0 1 0
A8 M 7 3 4 0 0 -1 0 0 1

(M) 7 6 -1 -1 -1 0 0 0
-15 -19 0 0 0 0 0 0

A1 15 1 1 1/3 -1/3 0 0 1/3 0 0
A7 M 1 0 2/3 1/3 -1 0 -1/3 1 0
A8 M 4 0 3 1 0 -1 -1 0 1

(M) 0 11/3 4/3 -1 -1 -7/3 0 0
0 -14 -5 0 0 5 0 0

A1 15 5/9 1 0 -4/9 0 1/9 4/9 0 -1/9
A7 M 1/9 0 0 1/9 -1 2/9 -1/9 1 -2/9
A2 19 4/3 0 1 1/3 0 -1/3 -1/3 0 1/3