Website: Email : Tel (: 0918.775.368

lời mở đầu
Cùng với sự phát triển mạnh mẽ của khoa học kỹ thuật, các bài toán tối u xuất
hiện ngày càng nhiều và tính phức tạp của chúng ngày càng lớn. Phạm vi và khả
năng ứng dụng của các bài toán tối u cũng ngày càng đa dạng và phong phú.
Lớp bài toán tối u quan trọng đợc nghiên cứu đầu tiên và đợc ứng dụng nhiều
nhất là bài toán quy hoạch tuyến tính (linear programming). Đó là mô hình toán học
của một lớp rộng lớn các bài toán ứng dụng trong kinh tế và kỹ thuật. Do đó cấu trúc
của lớp bài toán quy hoạch tuyến tính có nhiều tính chất rất tốt về mặt toán học, ngời
ta đã tìm đợc các thuật giải rất hữu hiệu cho bài toán này. Năm 1947 nhà toán học
Mỹ G.B. Dantzig đã nghiên cứu và đề xuất ra thuật toán đơn hình (simplex method)
để giải bài toán quy hoạch tuyến tính. Thuật toán đơn hình đợc phát triển mạnh mẽ
trong những năm sau đó và đợc xem là một phơng pháp kinh điển để giải các bài
toán quy hoạch tuyến tính. Đây là một phơng pháp đợc sử dụng có thể nói là rộng rãi
nhất. Có ba lý do chính:
Một là: Rất nhiều vấn đề thực tế, trong nhiều lĩnh vực khác nhau có thể đa về
bài toán quy hoạch tuyến tính.
Hai là: Trong nhiều phơng pháp giải các bài toán phi tuyến, bài toán tuyến tính
xuất hiện nh là một bài toán phụ cần phải giải trong nhiều bớc lặp.
Ba là: Phơng pháp đơn hình là phơng pháp hiệu quả để giải bài toán quy hoạch
tuyến tính.
Ngày nay, bằng thuật toán đơn hình và các dạng cải biên của chúng, ngời ta có
thể giải rất nhanh các bài toán QHTT cỡ lớn.
Lớp các bài toán vận tải là trờng hợp đặc biệt của quy hoạch tuyến tính, bởi vậy
có thể dùng các phơng pháp của quy hoạch tuyến tính để giải. Tuy nhiên, do tính
chất đặc thù riêng của nó, ngời ta xây dựng các phơng pháp giải riêng.
Thông thờng khi nói đến bài toán vận tải ta thờng liên hệ ngay đến bài toán vận
tải hai chỉ số, bởi đây là bài toán vận tải kinh điển có những phơng pháp giải hay.
Bên cạnh đó, ngời ta còn xét một số các bài toán vận tải mở rộng nh bài toán vận tải
Trang: 1

2
, ..., x
n
). Các x
i
, i =1, ..., n gọi là các thành phần hay toạ độ của vector. Ví
dụ x=(4,5,10,20).
Hai vectơ x và y gọi là bằng nhau x=y, nếu x
i
=y
i
, i =1, ..., n.
Xét hai phép toán trên các vector:
Phép cộng: x+y=(x
1
+y
1
, x
2
+y
2
, ..., x
n
+y
n
)
Phép nhân: x=(x
1
, x
2


=
=
m
i
i
i
xx
1
)(

với ít nhất một
i
0 thì x gọi là tổ hợp tuyến tính của các
x
(i)
, i =1, ..., m. Hơn nữa nếu
i
> 0, i =1, ..., m và

=
=
m
i
i
1
1

thì x gọi là tổ hợp lồi
của các x

1
, y
2
, ..., y
n
), ký hiệu, <x,y>, là một số bằng.
Tích vô hớng là một dạng song tuyến tính, đối xứng, không âm, tức là:
1. <x,y> = <y, x>. x,y R
n
2. <x
(1)
+ x
(2)
, y >=< x
(1)
, y >+< x
(2)
, y>. x
(1)
, x
(2)
, y R
n
3. <x,y> = <x,y>. x,y R
n
4. <x,x> 0, x R
n
dấu bằng xẩy ra khi và chỉ khi x= 0.
Độ dài của vector x=(x
1

2
,
( )
0,lim
)0()(
=

xx
k
k


=
=><
n
i
ii
yxyx
1
,
k
( ) ( )

=
=><==
n
i
ii
yxyxyxyxyx
1

Fx
k
k


)(
lim

Một tập chứa mọi điểm biên của nó là tập đóng.
* Tập C đợc gọi là tập Compact nếu từ mọi dãy vô hạn {x
(k)
} thuộc C đều có thể
trích ra một dãy con {x
(ki)
} hội tụ tới phần tử thuộc C. Tập C là Compact khi và chỉ
khi C đóng và giới nội. Tập Compact M của tập đóng C cũng đóng trong C. Tập con
đóng M của tập Compact cũng Compact.
Hàm f(x) liên tục trên tập Compact C thì sẽ đạt cực trị trên tập ấy.
1.1.3 Tập lồi
Cho hai điểm a, b R
n
. Ta gọi đờng thẳng qua a, b là tập điểm có dạng
xR
n
: x = a + (1-)b, R.
Đoạn thẳng nối hai điểm a, b là tập lồi các điểm có dạng
xR
n
:x = x + (1-)y, 0 1
* Một tập MR

n
= trong đó a
1
, a
2
, ..., a
n
, R
* Tập hợp các điểm x=(x
1
, x
2
, ..., x
n
) R
n
thoản mãn bất phơng trình tuyến tính
a
1
x
1
+ a
2
x
2
+ ... + a
n
x
n
đợc gọi là nửa không gian đóng.

n
đợc gọi là hàm lồi trên C, nếu
với mọi x, y C và 0 1 ta có f(x + (1-)y) f(x) + (1-)f(y).
* Hàm f(x) đợc gọi là hàm lồi chặt nếu với mọi x, y C và 0 1 ta có. f(x
+ (1-)y) < f(x) + (1-)f(y).
* Hàm f(x) đợc gọi là hàm lõm (lõm chặt) nếu - f(x) là hàm lồi (lồi chặt)
Trang: 6
.
...
....................
...
...
2211
22222121
11212111







+++
+++
+++
nnnnnn
nn
nn
bxaxaxa
bxaxaxa

mxn
là ma trận với các phần tử a
ij
(1.1) gọi là hàm mục tiêu, (1.2) là các rằng buộc.
Nếu gặp bài toán Min, tức là
Trang: 7
( )
Dx
xcxf
j
n
j
j

=

=
min
1
( )
1.1max
1


=
j
n
j
j
xc

-Dạng chuẩn:
-Dạng chính tắc:
Đa bài toán QHTT về dạng chuẩn hoặc dạng chính tắc.
Bất kỳ QHTT nào cũng có thể đa về một trong hai dạng chuẩn hoặc chính tắc
nhờ các phép biến đổi tuyến tính sau:
Trang: 8
( )
Dx
xcxf
j
n
j
j

=

=
max
1
Dxxcxc
hayDxxcxcf
n
j
jj
n
j
jj
j
n
j

xc
j
i
n
j
jij
n
j
jj
,...,1,0
,...,1,
max
1
1
=
=



=
=
njx
mibxa
xc
j
i
n
j
jij
j

Về nguyên tắc, áp dụng nhiều lần các phép biến đổi (i), (ii) và (iii) ta có thể đa
một bài toán QHTT bất kỳ về dạng chuẩn, sau đó áp dụng nhiều lần phép biến đổi
(iv) ta sẽ đa nó về dạng chính tắc.
Giải bài toán QHTT bằng phơng pháp hình học.
Xét bài toán QHTT dới dạng chuẩn với hai biến số:
Trang: 9

=

n
j
ijij
bxa
1
i
n
j
jij
bxa
=

=
1
i
n
j
jiji
n
j
jij

n
j
ij
bxa


=
1
.''
1
ij
n
j
ij
bxa


=



=
=+
=
+
2,1,0
,...,1,
max
2111
2211

=

khi

thay đổi sẽ xác
định trên mặt phẳng các đờng thẳng song song với nhau mà ta sẽ gọi là các đờng
mức (với giá trị mức

). Mỗi điểm D sẽ nằm trên một đờng mức với mức
Bài toán đặt ra có thể phát biểu theo ngôn ngữ hình học nh sau: trong số các đ-
ờng mức cắt tập D, hãy tìm đờng mức với gía trị lớn nhất.
Nếu dịch chuyển song song các đờng mức theo hớng vector pháp tuyến của
chúng thì giá trị mức sẽ tăng, nếu dịch chuyển theo hớng ngợc lại thì giá
trị mức sẽ giảm. Vì vậy để giải bài toán đặt ra, ta có thể tiến hành nh sau.
Bắt đầu từ một đờng mức cắt D, ta dịch chuyển song song các đờng mức theo h-
ớng vector pháp tuyến (c
1
,c
2
) cho đến khi việc dịch chuyển tiếp theo làm cho đờng
mức không còn cắt D nữa thì dừng. Điểm của D (có thể nhiều điểm) nằm trên đờng
mức cuối cùng này sẽ là lời giải tối u cần tìm, còn giá trị của hàm mục tiêu tại đó
chính là giá trị tối u của bài toán.
Ví dụ: Xét bài toán:
f(x)= 4x
1
+5x
2
max
Xét đờng mức: 4x

( )
21
, xxx
=
.
2211
xcxc
+=

( )
21
,ccn
=
y
n
*x
x
Website: Email : Tel (: 0918.775.368

và x* là một đỉnh của D. Qua phơng pháp hình học ta thấy rằng:
- Nếu quy hoạch tuyến tính có phơng án tối u thì có ít nhất một đỉnh là tối u. Sở
dĩ nói ít nhất vì có trờng hợp đờng mức ở vị trí giới hạn trùng với một cạnh của D thì
tất cả các điểm trên cạnh này là phơng án tối u, trong đó có hai đỉnh.
- Nếu miền ràng buộc D giới nội và khác rỗng thì chắc chắn có phơng án tối u.
- Nếu miền ràng buộc không giới nội nhng hàm mục tiêu bị chặn trên ở trên
miền ràng buộc thì cũng chắc chắn có phơng án tối u.
1.2.2 Một số tính chất chung
Mệnh đề 1: Tập hợp tất cả các phơng án của một bài toán QHTT là tập lồi.
Tập lồi D các phơng án của một bài toán QHTT xác định bởi toàn bộ các ràng
buộc (1.2) và (1.3). Tập D có thể là rỗng, hoặc là một đa diện lồi hoặc là một tập lồi

k
là độc lập tuyến tính và thoả mãn
x
1
A
1
+x
2
A
2
+...+x
n
A
n
=b
trong đó x
j
>
0, j=1,...k thì điểm
Trang: 11
Website: Email : Tel (: 0918.775.368

x=(x
1
,x
2
,...,x
k
,0,...,0)
là điểm cực biên của tập lồi đa diện D.

phơng pháp đơn hình. Sở dĩ có tên gọi nh vậy là vì những bài toán đầu tiên đợc giải
bằng phơng pháp đó có các ràng buộc dạng:
Mà tập hợp các điểm xR
n
thoả mãn các ràng buộc trên là một đơn hình trong
không gian n chiều.
Đờng lối chung và cơ sở của thuật toán.
i) Đờng lối chung.
Phơng pháp đơn hình dựa trên hai nhận xét sau: nếu bài toán QHTT có phơng
án tối u, đa diện lồi D có một số hữu hạn đỉnh. Nh vậy phải tồn tại thuật toán hữu
hạn. Thuật toán gồm hai giai đoạn:
- Giai đoạn 1: Tìm một phơng án cực biên (một đỉnh).
- Giai đoạn 2: Kiểm tra điều kiện tối u đối phơng án tìm đợc ở giai đoạn 1. Nếu
điểu kiện tối u đợc thoả mãn thì phơng án đó là tối u. Nếu không, ta chuyển sang ph-
ơng án cực biên mới sao cho cải tiến giá trị hàm mục tiêu. Tiếp theo lại kiểm tra điều
kiện tối u đối với phơng án mới.
Ngời ta thực hiện một dãy các thủ tục nh vậy cho đến khi nhận đợc phơng án tối
u, hoặc đến tình huống bài toán không có phơng án tối u.
Trang: 12
( )
5.1,...,1,0,1
1
njxx
j
n
j
j
==

=

, j J} đợc gọi
là các vector và các biến cơ sở tơng ứng. Các vector và các biến A
j
, x
j
, j J gọi là các
vector và các biến phi cơ sở tơng ứng.
Nếu x không thoái hoá thì tồn tại một cơ sở duy nhất, đó là J=J*.
Mỗi vector A
k
phi cơ sở có thế biểu diễn dới dạng tổ hợp tuyến tính của các
vector cơ sở:
Trong đó các hệ số z
jk
đợc xác định duy nhất bởi việc giải hệ phơng trình:
Bài toán QHTT đợc gọi là không thoái hoá nếu tất cả các phơng án cực biên của
nó đều không thoái hoá.
Giả sử bài toán không thoái hoá và ta đã tìm đợc một phơng án cực biên x=(x
1
,
x
2
,...x
m
, 0,...0) và cơ sở của nó A
1,
, A
2
,...A
m

m
,0...0) các điều kiện sau đợc thỏa mãn
thì x* là phơng án tối u.
Chú ý:
Trong (1.10) nếu A
j
là một vector cơ sở, khi đó tồn tại chỉ một hệ số z
jj
=1, tất
cả các hệ số khác đều bằng 0 và ta có:
và trong thực hành để kiểm tra điều kiện tối u của phơng pháp cực biên x ta chỉ
cần kiểm tra

k
0, kJ (1.18)
Ngời ta có thể chứng minh rằng nếu bài toán không thoái hoá thì (1.16) cũng
là điều kiện cần của tối u.
Định lý 1.2: Nếu tồn tại một chỉ số k sao cho
k
< 0 thì ngời ta có thể tìm đợc ít
nhất một phơng án x mà đối với nó Z > Z
0
.
Công thức tìm phơng án x:
Nhân (1.10) với

nào đó ta có:
Lấy (1.12) trừ đi (1.19) từng vế ta có:
Trang: 14
( )

Zcz
( )
15.1
1
k
m
j
jjkkkk
cczcZ
==

=
( )
16.1,.....,2,1,0 nk
k
=
( )
17.1,0 Jjcc
jjj
==
)19.1(
1
kj
m
j
jk
AAz

=


jk
> 0, jJ thì giá trị

lớn nhất còn thoả
mãn (1.22) có thể xác định bởi hệ thức :
Nếu ta thay

trong (1.20) và (1.21) bởi

o
thì thành phần thứ r sẽ bằng 0:
x
r
-

o
z
rk
=0.
Nh vậy ta nhận đợc phơng án mới x với cơ sở A
j
, jJ\ {r}{k}=J.
Nếu z
jk
0, j J thì tất cả các thành phần x
j
-

z
jk

x
z
z
x
=










>=


{ }
( )
24.10min
<=
kk
k
s
( )
25.1,0min
rs
r
js

,/
'
rsr
jsrsrj
j
zx
zzxx
x
( )
26.1
{ } { } ( )
27.1\', srJJjA
j
=
( )
29.3,.....,1,0:' mjzxx
jkjj
==

)21.1('
0 k
ZZ
=

)22.1(,.....,1,0:' mjzxx
jkjj
==

Website: Email : Tel (: 0918.775.368


lời giải tối u (Z không bị chặn trên). Dừng thuật toán.
Đối với mỗi kJ sao cho
k
< 0 đều tồn tại j

J: z
jk
> 0. Khi đó chọn chỉ
số s theo tiêu chuẩn:
Đa vector A
s
vào cơ sở.
Trang: 16
{ }
0min
<=
kks
kj
Jj
jk
AAz
=


kj
Jj
jkk
ccz
=


cực biên x với cơ sở J.
Ta đã có công thức (1.26) để tính các thành phần của x. Bây giờ ta thiết lập
công thức tính các số z
jk
. Ta có:
Mặt khác
Thay biểu thức của A
r
vào ta đợc:
Đây là công thức biểu diễn A
k
qua cơ sở mới J =J\{r}{s}. Bởi vậy ta có:
nếu jr

nếu j=r
Trang: 17
rs
r
js
rs
j
s
z
x
z
z
x
=



Jj
jjss
AzA
z
A
AzA
,
1
s
rs
rk
j
rjJj
js
rk
jk
rjJj
jjss
rs
rk
riJj
jjkk
A
z
z
A
z
z
zAzA
z

jkk
AzAzAzA
,,
( )
( )
,28.1
,/
,/
'






=
rsrk
jsrsrkjk
jk
zz
zzzz
z
( )
29.1''
'
kj
Jj
jkk
ccz
=

m
... c
k
... c
s
... c
n
A
a
... A
j
... A
r
... A
m
...A
k
... A
s
... A
n
c
1
.
..
c
j
.
..
c

m
1 .
..
0 .
..
0 .
..
0
0 .
..
1 .
..
0 .
..
0
0 .
..
0 .
..
1 .
..
0
0 .
..
0 .
..
0 .
..
1
z

jn
.
..
z
rn
.
..
z
mn
f
0... 0... 0... 0 ...
k
...
s
...
n
Nếu dòng cuối (không kể f ) có những số âm thì xem thử có cột nào cắt dòng
cuối ở một số âm mà mọi số trong cột đó đều âm hay không. Nếu có cột nào nh thế
thì bài toán không có phơng án tối u. Nếu trái lại thì chọn cột sao cho
Rồi chọn ( trong số các dòng cắt cột s ở những số dơng ) dòng r sao cho:
Cột s gọi là cột quay. Vector A
r
đợc đa vào cơ sở. Dòng r gọi là dòng quay.
Vector A
r
bị đa ra khỏi cơ sở.
Phần tử z
rs
> 0 là giao của cột quay và dòng quay gọi là phần tử chính của phép
quay. Các phần tử z

js
js
j
rs
r
r
z
z
x
z
x

Website: Email : Tel (: 0918.775.368

i) Chia mỗi phần tử ở dòng quay cho phần tử chính đợc số 1 ở vị trí của z
rs
cũ.
Kết quả thu đợc là dòng chính.
ii) Lấy mỗi dòng khác trừ đi tích của dòng chính nhân với phần tử quay tơng
ứng đợc số 0 ở mọi vị trí còn lại của cột quay.
Dòng mới = dòng cũ tơng ứng - dòng chính x phần tử quay
Lu ý rằng sau phép quay thì ở vị trí
s
ta thu đợc số 0 vì lúc này A
s
trở thành
vector đơn vị cơ sở, nghĩa là ta đã làm mất số âm nhỏ nhất ở dòng cuối của bảng cũ.
Toàn thể phép biến đổi trên gọi là phép quay xung quanh phần tử chính z
rs
. Sau

n
.
Có n nơi tiêu thụ loại hàng hóa đó B
1
, B
2
, ..., B
n
với các yêu cầu tơng ứng là b
1
,
b
2
, ..., b
n
.
Để đơn giản ta sẽ gọi
A
i
là điểm phát i, i=1, ..., m
B
j
là điểm thu j, j=1, ..., n
Hàng có thể chở từ một điểm phát bất kỳ (i) đến một điểm thu bất kỳ (j)
Ký hiệu:
c
ij
- chi phí chuyên chở một đơn vị hàng từ điểm phát (i) đến điểm thu (j).
x
ij




=>
==
==
==



= =
=
=
m
i
n
j
jiji
ij
m
i
jij
n
j
iij
Ibaba
njmix
njbx
miax
1 1

..., c
mn
) - Vector hàng mxn thành phần.
P = (a
1
,

a
2
, ..., a
m
, b
1
, b
2
, ..., b
n
) - Vector cột vế phải.
Ta đa BTVT về dạng.
Ta gọi P
ij
là cột của ma trận A ứng với biến x
ij
. Vector này có 2 thành phần bằng
1 tại dòng thứ i và dòng thứ m+j còn các thành phần khác bằng 0.
Trang: 21
)5.2(
)(
.....
)2(

=+++
=+++
nm
m
m
m
bxxx
bxxx
bxxx
axxx
axxx
axxx
nmnnn
m
m
mmnmm
n
n






=
><
)8.2(0
)7.2(
)6.2(,min
X

ij
không thể lớn hơn các số tơng ứng a
i
, b
j
.
Vì vậy miền rằng buộc là khác rỗng và giới nội (đa diện lồi). Đa diện này có 1
số hữu hạn đỉnh. Theo thuật toán đơn hình, xuất phát từ một phơng án cực biên, sau
một số hữu hạn bớc ta phải đi tới một phơng án cực biên tối u.
Định nghĩa 2:
- Một ô (i,j) mà x
ij
gọi là ô sử dụng.
- Tập các ô sau đợc gọi là một dây truyền trong T
(i
1
,j
1
), (i
1
,j
2
), (i
2
,j
2
), (i
2
,j
3

m
i
n
j
ji
baS
1 1
0
njmi
S
ba
x
ji
ij
,1;,1,
===
njb
S
ab
S
ba
x
mia
S
ba
S
ba
x
j
m

=
==
=
==
Website: Email : Tel (: 0918.775.368

Mỗi cặp ô liền nhau trong dây truyền đợc xếp trong một hàng hoặc trong một
cột.
Dây truyền đợc gọi là kín hay là một chu trình nếu: j
s+1
= j
1
hoặc i
s+1
= i
1
Gọi G là tập hợp các ô sử dụng:
G = {(i,j) | x
ij
> 0 } |G| m+n-1
- Một phơng án X của BTVT đã cho đợc gọi là không thoái hóa nếu
|G| = m+n-1
Ngợc lại là thoái hóa nếu |G| m+n-1
- Nếu một tập hợp con thực sự của G lập thành chu trình thì ta có một chu trình
con của G.
Định lý 2.2: Hệ thống vector P
ij
của BTVT là độc lập tuyến tính khi và chỉ khi
các ô tơng ứng với các vector của hệ thống không tạo thành chu trình.
Chứng minh: Cần. Ký hiệu P

s+1
) với j
s+1
= j
s

khi đó rõ ràng:
P
i1,j1
- P
i1j2
+ P
i2j2
- ... - P
isjs
- P
isj1
= 0
tức là hệ P
ij
phụ thuộc tuyến tính, mâu thuẫn với giả thiết.
Đủ: Giả sử G không lập thành chu trình. Ta phải chứng minh hệ P
ij
là độc lập
tuyến tính.
Bằng phản chứng, giả sử hệ P
ij
là phụ thuộc tuyến tính. Mỗi vector P
ij
có dạng:

. Nhng điều đó chứng tỏ rằng các ô {(i,j)} t-
ơng ứng với hệ thống P
ij
lập thành chu trình.
Trang: 23
Website: Email : Tel (: 0918.775.368

Điều này trái với giả thiết. Vậy hệ P
ij
là độc lập tuyến tính.
Hệ quả: Vector X là phơng án cực biên khi và chỉ khi tập các ô sử dụng tơng
ứng không lập thành chu trình.
Chứng minh: Coi BTVT là một QHTT thì X là phơng án cực biên khi và chỉ khi
các vector P
ij
ứng với x
ij
> 0 là độc lập tuyến tính, theo định lý 2.2 thì điều đó xẩy ra
khi và chỉ khi tập các ô sử dụng tơng ứng không lập thành chu trình.
Định lý 2.3: Giả sử X là một phơng án của BTVT và tập G của nó lập thành chu
trình, thế thì bao giờ cũng có thể điều chỉnh đợc X để chuyển sang một phơng án mới
X không xấu hơn mà tập G không lập thành chu trình.
Chứng minh:
Giả sử K là một chu trình nào đó của G ta phân ra trong K tập các ô chẵn K
+
và
tập các ô lẻ K
-
(xen kẽ nhau). Không giảm tổng quát có thể coi:
(nếu không ta quy ớc lại các ô chẵn và lẻ trên K)









+
=

+
Kjix
Kjix
Kjix
x
ij
ij
ij
ij











'
),(
'
XC
K
xc
K
cxcxcXC
i j
ji
ijij
ji
ijijij
i j
ijij
++=><

+


Website: Email : Tel (: 0918.775.368

Do phép biến đổi (2.13) và xác định bởi (2.12), sẽ có một ô thuộc K
-
trớc đây
x
ij
> 0 bây giờ x
ij
= 0. Ta loại ô đó ra khỏi G do đó khỏi K và phá đợc chu trình K.

11
= min(a
1
, b
1
)
- Nếu x
11
= a
1
thì ta xóa hàng 1. Lập bảng mới có b
1
= b
1
- x
11
. Tiếp tục quá
trình, bắt đầu từ ô (2,1).
- Nếu x
11
= b
1
thì ta xóa cột 1. Lập bảng mới có a
1
= a
1
- x
11
. Tiếp tục quá trình,
bắt đầu từ ô (1,2).