TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP
Khoa: KHOA HỌC CƠ BẢN
BÀI GIẢNG
QUY HO CH TUY N Ạ Ế
T NHÍ
GV: ThS. HÀ ANH DŨNG

Chương I: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
Chương II: BÀI TOÁN VẬN TẢI

Chương III: MÔ HÌNH SƠ ĐỒ MẠNG LƯỚI

CHƯƠNG I:
BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
I.Khái niệm về BT QHTT
1.Các ví dụ dẫn đến BT QHTT
Ví dụ 1: Bài toán lập kế hoạch sản xuất
Giả sử xí nghiệp X cần lập kế hoạch sản xuất giấy. Nguyên liệu chính để
sản xuất giấy là bột gỗ và chất hồ keo. Xí nghiệp có thể sản xuất ba loại
giấy A, B, C. Mức tiêu hao nguyên liệu để sản xuất ra 1 tấn giấy A, B, C
và giá bán một tấn mỗi loại được cho trong bảng sau: ( được gọi là Bảng
hệ số kỹ thuật )
Nguyên liệu Hiện có A B C
Bột gỗ (tấn) 5500 tấn 1.5 1.8 1.6
Chất hồ keo (kg) 6800 kg 2.0 3.0 2.4
Giá bán (triệu/ tấn) 27 36 30

Bài toán được đặt ra là với nguyên vật liệu hiện có như trên thì Xí
nghiệp cần phải sản xuất bao nhiêu tấn giấy mỗi loại để số tiền thu được
là tối đa. Gọi x

1
, x
2
, x
3
là số tấn giấy A, B, C cần sản xuất ( x
1
, x
2
, x
3
≥ 0 ).
Ta có bài toán sau: tìm x
1
, x
2
, x
3
sao cho:

f(x) = 27x
1
+ 36x
2
+ 30x
3
→ max
1.5x
1
+ 1.8x

2
+ 1.6x
3
≤ 5500
2x
1
+ 3x
2
+ 2.4x
3
≤ 6800
x
1
, x
2
, x
3
≥

0

Ví dụ 2: Bài toán dinh dưỡng
Mỗi người chúng ta mỗi ngày, để có thể sinh hoạt và hoạt động bình
thường, cần tiêu thụ ít nhất 60g protit, 50g lipid và 220g glucid. Các
thành phần dinh dưỡng này có trong 1g cá và 1g thịt như trong bảng dưới
đây. Biết rằng giá 1g cá và 1g thịt là 50 và 90 VNĐ. Vậy mỗi ngày ta cần
mua bao nhiêu gam thịt, cá sao cho số tiền phải chi là ít nhất nhưng vẫn
đảm bảo lượng dinh dưỡng cần thiết. Gọi x
1
và x

2
là số gam cá thịt cần
mua trong ngày ( x
1
, x
2
≥ 0). Ta cần giải bài toán sau: tìm x
1
, x
2
sao cho:

Chất dinh dưỡng Cá Thịt
Protit (gam) 0.2 0.3
Lipid (gam) 0.1 0.1
Glucid (gam) 0.6 0.5
f(x) = 50x
1
+ 90x
2
→ min
0.2x
1
+ 0.3x
2
≥ 60
0.1x
1
+ 0.1x
2

≥ 50
0.6x
1
+ 0.5x
2
≥ 220
x
1
, x
2
≥ 0
Từ các ví dụ trên đây ta thành lập Bài toán quy hoạch tuyến tính (BT
QHTT) tổng quát.

2. Bài toán QHTT
a. BT QHTT dạng tổng quát
Tìm các giá trị x
1
, x
2
,…x
n
sao cho:
( )
( )
( )
n
j j
j 1
n

ij j i
j 1
f x c x min (max) (1)
a x b i = 1, (2)
0
x 0 1, (3)
Tùy ý
j
m
j n
=
=
= →
 ≥
 

 
≤

 

 
=
  

≥
 

 


≤ =
 

 

 

∑
∑
Trong đó (1) là hàm mục tiêu, (2) là các ràng buộc chung, (3) là các
ràng buộc về dấu.

■ Một số khái niệm cơ bản:
Phương án (PA): Vectơ X = (x
1
, x
2
, , x
n
) thoả mãn tất cả các ràng buộc
của bài toán gọi là một PA.
Ràng buộc có dấu “=” được gọi là ràng buộc “chặt”; ràng buộc có dấu
“≤” hoặc “≥” là ràng buộc “lỏng”.
Phương án tối ưu (PATƯ ): Một PA mà tại đó giá trị hàm mục tiêu đạt
giá trị nhỏ nhất (min) hoặc lớn nhất (max) được gọi là PATƯ.
b. BT QHTT dạng chính tắc
( )








=≥
==
→=
∑
∑
=
=
)n1,(j0x
)m1,(ibxa
(max)min xcxf
j
i
n
1j
jij
n
1j
jj
BT QHTT dạng chính tắc là bài toán có các ràng buộc chung là chặt,
còn các ràng buộc về dấu là không âm.

Mọi BT QHTT tổng quát đều có thể đưa về bài toán dạng chính tắc
tương đương. “Tương đương” ở đây có nghĩa là giá trị của hàm mục tiêu
trong hai bài toán là như nhau và một PA của BT này cũng là PA của BT
kia.
● Cách đưa bài toán tổng quát về dạng chính tắc

- Nếu một ràng buộc có dấu “≤” thì ta cộng vào vế trái một biến phụ
không âm x
n+i
để được ràng buộc chặt.
- Nếu một ràng buộc có dấu “≥” thì ta trừ đi vế trái một biến phụ không
âm x
n+i
để được ràng buộc chặt.
- Các biến phụ không tham gia trong hàm mục tiêu.
- Nếu biến x
j
≤ 0 thì đổi biến x
j
’= − x
j
≥ 0.
- Nếu x
j
có dấu tùy ý thì đặt x
j
= x
j
’− x
j
’’, với x
j
’, x
j
’’≥ 0.


Ví dụ: Đưa bài toán sau về dạng chính tắc:
f(x) = –2x
1
+ x
2
+ 3x
3
+ 5x
4
⇒ min
x
1
– 3x
2
+ 5x
3
– x
4
≤ 16
2x
1
– x
2
– 2x
3
+ 2x
4
≥ – 4
4x
1

+ 3x
2
+ x
3
+ x
4
= 9
x
1
, x
2
≥ 0, x
3
≤ 0









- Ta sẽ cộng vào vế trái ràng buộc 1 biến phụ x
5
, trừ đi vế trái ràng buộc
2 biến phụ x
6
.
- Đặt x

3
’= – x
3
≥ 0, x
4
= x
4
’ – x
4
’’, x
4
’, x
4
’’ ≥ 0.
Ta được bài toán chính tắc tương đương sau:
f(x) = –2x
1
+ x
2
– 3x
3
’ + 5x
4
’ – 5x
4
’’ ⇒ min
x
1
– 3x
2

– 5x
3
’ – x
4
’ + x
4
’’ + x
5
= 16
2x
1
– x
2
+ 2x
3
’ + 2x
4
’ – 2x
4
’’ – x
6
= –4
4x
1
+ 3x
2
– x
3
’ + x
4

’ – x
4
’’ = 9
x
1
, x
2
, x
3
’, x
4
’, x
4
’’, x
5
, x
6
≥ 0










c. BT QHTT dạng chuẩn
( )

n
j j
j 1
1 1m 1 m 1 1m 2 m 2 1n n 1
2 2m 1 m 1 2m 2 m 2 2n n 2
m mm 1 m 1 mm 2 m 2
f x c x min (max)
x a x a x a x b
x a x a x a x b

x a x a x
=
+ + + +
+ + + +
+ + + +
= →
+ + + + =
+ + + + =
+ + +
∑
mn n m
j
a x b
x 0 (j 1,n), b 0 ( 1, )
i
i m







+ =


≥ = ≥ =

Bài toán dạng chuẩn là bài toán dạng chính tắc có vế phải không âm và
mỗi phương trình đều có một biến số với hệ số bằng 1 đồng thời không
có trong các phương trình khác. Các biến đó được gọi là biến cơ sở (biến
cô lập).
Các biến cơ sở là x
1
, x
2
,…x
m
. Biến không phải là cơ sở được gọi là phi
cơ sở (biến tự do).



Nghiệm riêng cơ bản (cơ sở) là nghiệm riêng của hệ phương trình
tuyến tính khi ta cho các biến phi cơ sở (tự do) bằng 0.
Phương án cực biên (PACB) của BT QHTT là nghiệm riêng cơ bản
của hệ các ràng buộc chung và thỏa mãn các ràng buộc về dấu. Ở dạng
chuẩn ta có PACB là X
0
= ( b
1

, b
2
,….,b
m
, 0, 0,….,0 ).
3. Phép khử Gauss-Jordan (G-J):
Cho hệ phương trình tuyến tính tổng quát:
11 1 12 2 1 1 1
21 1 22 2 2 2 2
1 1 2 2





v v n n
v v n n
r r rv v rn n r
a x a x a x a x b
a x a x a x a x b
a x a x a x a x b
+ + + + + =
+ + + + + =
+ + + + + =
1 2 2


mn m mv v mn n m
a x a x a x a x b










+ + + + + =


Ta có ma trận mở rộng:

[ ]
11 12 1 1 1
21 22 2 2 2
1 2
1 2






v n
v n
r r rv rn r
m m mv mn m
a a a a b
a a a a b

a a a a b
a a a a b
 
 ÷
 ÷
 ÷
 ÷
 ÷
 ÷
 ÷
 ÷
 
Giả sử cần chọn x
v
là biến cơ sở của hàng thứ r ta chọn phần tử a
rv
là
Phần tử trục. Đánh dấu phần tử trục bằng dấu [ ]. Lưu ý phần tử trục
phải khác 0. Hàng chứa phần tử trục được gọi là Hàng xoay, cột chứa
phần tử trục được gọi là Cột xoay.
Phép khử G-J gồm 3 bước sau đây:
-
Chia hàng xoay cho a
rv
,
-
Cho các phần tử khác trên cột xoay bằng 0 ,
- Các phần tử không thuộc hàng xoay và cột xoay được tính lại theo
qui tắc hình chữ nhật như sau:


'
ij ij
. (1)
iv
rj
rv
a
a a a
a
= −
a
rv
a
rj



a
iv
a
ij



Như vậy ta được ma trận mới:
' ' ' '
11 12 1 1
' ' ' '
21 22 2 2
' ' ' '

1 2
' ' ' '
1 2
0
0

1

0
n
n
r r rn r
m m mn m
a a a b
a a a b
a a a b
a a a b
 
 ÷
 ÷
 ÷
 ÷
 ÷
 ÷
 ÷
 ÷
 
Thực chất, phép khử trên chính là phép biến đổi sơ cấp: lấy hàng i trừ
đi k
i

lần hàng r, trong đó k
i
= a
iv
/ a
rv
, nên phép khử Gauss-Jordan là phép
biến đổi tương đương.

Lưu ý:
- Nếu trên hàng xoay có phần tử 0 thì cả cột chứa phần tử 0 đó giữ
nguyên,
- Nếu trên cột xoay có sẵn phần tử 0 thì cả hàng chứa phần tử 0 đó giữ
nguyên. Hai tính chất này suy ra từ công thức (1) ở trên.
Ví dụ: Tìm các nghiệm riêng cơ bản của hệ phương trình sau:
x
2
+ 2x
3
= 2
x
1
+ 2x
2
+ 3x
3
= 5
4x
1
+ 3x

2
+ 2x
3
=10
Ta biến đổi ma trận mở rộng:
[ ]
[ ] [ ]
0 1 2 2
0 1 2 2 0 1 2 2
1 2 3 5 1 0 1 1 1 0 1 1
4 3 2 10
4 0 4 4 0 0 0 0
 
   
 ÷
 ÷  ÷
− −
 ÷
 ÷  ÷
 ÷
 ÷  ÷
−
   
 
: :
Từ bảng thứ 3 ta có nghiệm riêng cơ bản X
1
= ( 1, 2, 0 ). Biến đổi tiếp
với phần tử trục (-1) ta có:


[ ]
2 1 0 4
1 1/ 2 0 2
0 1/ 2 1 1
1 0 1 1
 
 
 ÷
 ÷
− −
 
 
:
Từ bảng 4 ta có X
2
= ( 0, 4, -1 ) và từ bảng 5 ta có X
3
= ( 2, 0, 1 ).
4. Các tính chất của BT QHTT
Định lý 1: Số PACB của BT QHTT dạng chính tắc là hữu hạn và
trong đó m là số phương trình độc lập tuyến tính và cũng chính là hạng
của hệ ràng buộc chung.
,
m
n
C
≤

Định lý 2: Số thành phần dương của 1 PACB không vượt quá m (vì có
thể có biến cơ sở bằng 0 ). Nếu số thành phần dương đúng bằng m thì

PACB đó là không suy biến, nếu số thành phần dương nhỏ hơn m thì
PACB đó là suy biến.
Định lý 3: Một PA là PACB nếu các véc tơ cột ứng với các thành phần
khác không là độc lập tuyến tính.
Định lý 4: BT QHTT dạng tổng quát nếu có PA và hạng của hệ các
ràng buộc (kể cả ràng buộc về dấu) là n thì sẽ có PACB (Giao điểm của
n mặt siêu phẳng biên).
Hệ quả: BT QHTT dạng chính tắc nếu có PA thì sẽ có PACB (các ràng
buộc về dấu có hạng = n).

Định lý 5: BT QHTT có PATƯ khi và chỉ khi nó có PA và hàm mục
tiêu bị chặn dưới với bài toán tìm min ( chặn trên với bài toán tìm max ).
II. PHƯƠNG PHÁP ĐƠN HÌNH
1. Đặc điểm của tập PA
Định lý 1: Tập PA của BT QHTT dạng chính tắc là một không gian lồi.
Tức là nếu X
1
và X
2
là 2 PA thì X = α.X
1
+ ( 1 – α ).X
2
với 0 ≤ α ≤ 1
cũng là PA.
Định lý 2: Nếu f(X
1
) ≤ f(X
2
) thì f(X

1
) ≤ f(X) ≤ f(X
2
) với mọi X thuộc
cạnh X
1
X
2
.
Hệ quả 1: Nếu f(X
1
) = f(X
2
) thì f(X
1
) = f(X) = f(X
2
) với mọi X thuộc
cạnh X
1
X
2
.
Hệ quả 2: Nếu X
1
và X
2
là 2 PATƯ thì mọi X = α.X
1
+ ( 1 – α ).X

2
với
0 ≤ α ≤ 1 cũng là PATƯ.
Hệ quả 3: PATƯ chỉ có thể là các điểm cực biên (PACB), cạnh biên
hoặc một phần của siêu phẳng biên.

3. Trường hợp BT QHTT có dạng chuẩn
a. Bài toán tìm f
min

Thuật toán dưới đây áp dụng cho bài toán QHTT ở dạng chuẩn, tức là
mỗi phương trình có một biến cơ sở, không mất tính tổng quát ta giả thiết
các biến cơ sở đó là: { x
1
, x
2
,…, x
m
} và PACB xuất phát là X
0
= (b
1
, b
2
,
…,b
m
,0,0, ,0). Thuật toán giải BT QHTT f
min
gồm các bước sau:

Bước 1: Lập bảng đơn hình xuất phát:
2. Ý tưởng của phương pháp đơn hình
Nội dung của phương pháp đơn hình là tìm PATƯ ở các PACB (xem Hệ
quả 3 ở trên). Cụ thể là xuất phát từ một PACB, đánh giá xem PACB đó
tối ưu chưa, nếu chưa phải là PATƯ thì ta tìm PACB tốt hơn (có giá trị
hàm mục tiêu tốt hơn), cứ như vậy tới khi tìm được PATƯ, hoặc sẽ kết
luận được rằng không tồn tại PATƯ. Vì số PACB là hữu hạn nên số
bước thực hiện cũng hữu hạn.

Cơ sở Hệ số
cơ sở
PACB x
1
x
2
… x
r
… x
m
x
m+1
… x
k
… x
v
… x
n
c
1
c

2
… c
r
… c
m
c
m+1
… c
k
…

c
v
… c
n
x
1
x
2
…
x
r
…
x
m
c
1
c
2
…

c
r
…
c
m
b
1
b
2
…
b
r
…
b
m
1 0 … 0 … 0 a
1,m+1
… a
1k
… a
1v
… a
1n
0 1 … 0 … 0 a
2,m+1
… a
2k
… a
2v
… a

2n
……………………………………………….
0 0 … 1 … 0 a
r,m+1
… a
rk
… a
rv
… a
rn
…………………………………………………………
0 0 … 0 … 1 a
m,m+1
…a
mk
…a
mv
a
mn

f(x) Δ
0
0 0 … 0 … 0 ∆
m+1
… ∆
k
… ∆
v
… ∆
n

Hàng dưới cùng được gọi là hàng đặc trưng, trong đó:
là giá trị của hàm mục tiêu ứng với PACB
X
0
.
0
1
m
i i
i
c b
=
∆ =
∑
1
m
k i ik k
i
c a c
=
∆ = −
∑
là ước lượng của biến x
k
. Ta thấy nếu x
k
là biến cơ sở
thì ∆
k
= 0.


∀
Bước 2: Kiểm tra dấu hiệu tối ưu:
∀
+ Nếu ∆
k
≤ 0 thì X
0
là PATƯ và f
min
= Δ
0
. Thuật toán kết thúc.
+ Nếu ∆
k
> 0 mà a
ik
≤ 0 thì bài toán không có PATƯ.
∃
+ Nếu với mỗi ∆
k
> 0 đều có ít nhất một a
ik
> 0 thì chuyển sang bước 3.
Bước 3: Cải tiến PACB:
- Ta sẽ đưa một biến mới vào cơ sở, đồng thời sẽ loại một biến ra khỏi
cơ sở để được PACB mới tốt hơn với giá trị của hàm mục tiêu nhỏ hơn.
- Để cải thiện nhiều nhất ta sẽ chọn biến có ước lượng dương lớn nhất
để đưa vào cơ sở. Giả sử ∆
v

> 0 lớn nhất thì x
v
sẽ được đưa vào cơ sở.
- Trên cột v ta sẽ chọn phần tử trục (giả sử là a
rv
) theo hai điều kiện sau:
a
rv
> 0 và tỷ số (b
r
/ a
rv
) là nhỏ nhất. Ta đánh dấu phần tử trục a
rv
bằng
dấu [ ]. Cột v sẽ là cột xoay, còn hàng r là hàng xoay.
- Thực hiện phép khử G – J với phần tử trục a
rv
ta được bảng đơn hình
mới. Trên hàng xoay ta có biến cơ sở mới là x
v
, biến cơ sở cũ trên hàng
xoay bị loại ra khỏi cơ sở (các biến cơ sở khác giữ nguyên) thay x
v
vào
vị trí ở cột thứ nhất, và c
v
vào vị trí ở cột thứ hai. Sau đó trở lại bước 2.
Vì số PACB là hữu hạn nên sau hữu hạn bước thì thuật toán kết thúc.



- Các giá trị trên hàng đặc trưng cũng được tính lại theo qui tắc hình
chữ nhật.
Lưu ý:
- Nếu mọi ước lượng của các biến phi cơ sở < 0 thì PATƯ là duy nhất.
- Nếu Δ
k
= 0 với k không thuộc cơ sở thì PATƯ không phải là duy
nhất, vì nếu ta chọn cột k là cột xoay thì các giá trị trên hàng đặc trưng
vẫn giữ nguyên (xem lại lưu ý 2 ở trang 9). Như vậy biến x
k
có thể được
đưa vào cơ sở và ta được PATƯ mới.
∃
Ví dụ 1: Giải bài toán sau bằng phương pháp đơn hình:
f(x) = 2x
1
+ 3x
2
– x
3
– 1/2x
4
⇒ min
x
1
– x
2
+ x
3

+ 1/2x
4
= 18
x
2
– 4x
3
+ 8x
4
≤ 8
–2x
2
+ 2x
3
– 3x
4
≤ 20
x
j
≥ 0 (j =1…4)

Trước tiên ta đưa bài toán về dạng chính tắc bằng cách cộng vào ràng
buộc hai và ba hai biến phụ x
5
và x
6
. Ta có:
f(x) = 2x
1
+ 3x

2
– x
3
– 1/2x
4
⇒ min
x
1
– x
2
+ x
3
+ 1/2x
4
= 18
x
2
– 4x
3
+ 8x
4
+ x
5
= 8
– 2x
2
+ 2x
3
– 3x
4

+ x
6
= 20
x
j
≥ 0 (j = 1…6)









Bài toán trên có dạng chuẩn, các biến cơ sở là {x
1
, x
5
, x
6
} và PACB
xuất phát là X
0
= (18, 0, 0, 0, 8, 20), do đó ta có thể lập ngay được bảng
đơn hình xuất phát:


CS HS PA x
1

x
2
x
3
x
4
x
5
x
6
CB 2 3 – 1 – 1/2 0 0
x
1
2 18 1 – 1 1 1/2 0 0
x
5
0 8 0 1 – 4 8 1 0
x
6
0 20 0 – 2 2 – 3 0 1
f(x) 36 0 0 0−5 3/23
Ở bảng 1 ta thấy PACB tương ứng chưa tối ưu. Ước lượng dương lớn
nhất là ∆
3
= 3, biến x
3
sẽ

được đưa vào cơ sở. Tỷ số 20/2 < 18/1 nên
phần tử [2] được chọn là phần tử trục, biến x

6
bị loại khỏi cơ sở (vì trên
mỗi hàng chỉ có 1 biến cơ sở).

CS

HS PA x
1
x
2
x
3
x
4
x
5
x
6
CB
2 3 – 1 – 1/2 0 0
x
1
2 18 1 –1 1 1/2 0 0
x
5
0 8 0 1 – 4 8 1 0
x
6
0 20 0 –2 [2] –3 0 1
f(x) 36 0 –5 3 3/2 0 0

x
1
2
x
5
0
x
3
10
0
−1
1
−3/2
0
1/2
1
0
0
0
0
1
8
0
2 −1/2
48
−3 2 2
f(x)
6
0
0

0−2 6 −3/2
–1

CS HS PA x
1
x
2
x
3
x
4
x
5
x
6
CB
2 3 – 1 – 1/2 0 0
x
1
2 8 1 0 0 [2] 0 – 1/2
x
5
0 48 0 −3 0 2 1 2
x
3
-1 10 0 – 1 1 – 3/2 0 1/2
f(x) 6 0 – 2 0 6 0 – 3/2
4 1/2 0 0 1 0
−1/4
0

1
0
0
1
0
40 −1 −3
5/2
16 3/4 −1 1/8
f(x)
−18
0 0
0
−3
−2
0
Ở bảng cuối ta thấy ∀∆
k
≤ 0 nên PA tương ứng PATƯ: X
1
= (0, 0, 16,
4, 40, 0) và f
min
= –18.
x
4
-1/2
x
5
0
x

3
-1

Ở bảng cuối ta thấy PATƯ X
1
không phải là duy nhất vì ∆
6
= 0 nên
ta có thể đưa x
6
vào cơ sở.
CS HS PA x
1
x
2
x
3
x
4
x
5
x
6
CB
2 3 – 1 – 1/2 0 0
x
4
-1/2 4 1/2 0 0 1 0 -1/4
x
5

0 40 -1 −3 0 0 1 [5/2]
x
3
-1 16 3/4 – 1 1 0 0 1/8
f(x) -18 -3 – 2 0 0 0 0

x
4
-1/2 8 2/5 -3/10 0 1 1/10 0
x
6
0 16 -2/5 -6/5 0 0 2/5 1
x
3
-1 14 4/5
-17/20
1 0
-1/20
0
f(x) -18 -3 -2 0 0 0 0