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


). 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
, ..., x
n
), R

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
(i)
, i =1, ..., m.
Trong R
n

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
, x
2
, ..., x
n

)0()(
=

xx
k
k


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

=
=><==
n
i
ii
yxyxyxyxyx
1
2
,,



)(
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
đợc gọi là một đa tạp affine nếu với hai điểm bất kỳ
x, y M thì toàn bộ đờng thẳng đi qua hai điểm đó cũng thuộc M.
Tức là x + (1-)y M : x,y M, R.
* Một siêu phẳng trong không gian R

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ửa không gian đợc cho bởi a
1
x
1
+ a
2

* Hàm f(x) xác định trên C đạt cực tiểu tuyệt đối tại x* C nếu
Trang: 6
.
...
....................
...
...
2211
22222121
11212111







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

f(x
*
) f(x): xC

( )
Dx
xcxf
j
n
j
j

=

=
min
1
( )
Dx
xcxf
j
n
j
j

=

=
max
1
( )
1.1max
1


max
Thật vậy, vì x* là phơng án tối u của bài toán Max nên ta có:
Chứng tỏ x* là phơng án tối u của bài toán Min và
Dạng chuẩn và dạng chính tắc.
Ngời ta thờng xét bài toán quy hoạch tuyến tính dới hai dạng sau:
-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:
i) Một ràng buộc
Trang: 8
Dxxcxc
hayDxxcxcf
n
j
jj
n
j
jj
j
n
j
j
n
j
jj

=


j
jj
,...,1,0
,...,1,
max
1
1
=
=



=
=
njx
mibxa
xc
j
i
n
j
jij
j
n
j
j
,...,1,0
,...1,
max
1

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ố:
Từ ý nghĩa hình học ta biết rằng mỗi bất phơng trình tuyến tính a
i1
x
1
+a
i2
x
2

b
i
xác
định một nửa mặt phẳng.
Trang: 9
i
n
j
jij
bxa =

=1
i
n
j
jiji
n

=1
.''
1
ij
n
j
ij
bxa

=



=
=+
=
+
2,1,0
,...,1,
max
2111
2211
jx
mibxaxa
D
xcxc
j
iii

Nh vậy miền ràng buộc D đợc xác định nh là giao của một nửa mặt phẳng và sẽ

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
1
+5x
2
=10. Đờng mức này đi qua hai điểm (0,2) và (2.5,0). Ta
có x*=(3,2), f
max
=22

Trang: 10
0,0
3
72
82
21
2
21
21






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
đa diện không giới nội.
Nếu D là một đa diện lồi thì bài toán có phơng án, hơn nữa giá trị tối u của hàm
mục tiêu trên đa diện lồi là hữu hạn và việc tìm phơng án tối u đa đến việc chọn các
điểm của đa diện D có số đỉnh (điểm cực biên hay phơng án cực biên) hữu hạn.
Mệnh đề 2: Hàm mục tiêu của bài toán QHTT sẽ đạt Max tại điểm cực biên của
tập D. Nếu hàm mục tiêu không chỉ nhận Max tại một điểm cực biên của tập lồi D
mà tại nhiều điểm cực biên thì nó sẽ đạt giá trị cực đại tại những điểm là tổ hợp lồi
của các điểm đó.
Ký hiệu A
j
, j=1, ..., n là các vector cột của ma trận A.
Khi ấy hệ ràng buộc Ax =b có thể viết:
x
1
A
1
+ x
2
A
2
+ ... + x
n
A
n
= b (1.4)
Mệnh đề 3: Nếu các vector A

là điểm cực biên của tập lồi đa diện D.
Mệnh đề 4: Nếu x =(x
1
,x
2
,...,x
n
) là điểm cực biên của tập lồi đa diện D thì các
vector A
j
trong biểu diễn (1.4) ứng với các thành phần x
j
> 0 lập thành hệ độc lập
Trang: 11

tuyến tính. Vì ma trận A có m dòng nên từ đây suy ra rằng điểm cực biên không có
quá m thành phần dơng.
Các mệnh đề 3 và mệnh đề 4 có thể gộp lại thành một mệnh đề sau:
Mệnh đề 5: Để x =(x
1
,x
2
...,x
n
) là phơng án cực biên của QHTT dới dạng chính
tắc thì cần và đủ là các vector cột A
j
của ma trận A ứng với các thành phần x
j
> 0 là

1
njxx
j
n
j
j
==

=

x 0 (1.8)
Trong đó A là ma trận kích thớc mxn và giả sử rằng hạng của ma trận A là m
(điều này không làm mất tính tổng quát). x là một vector.
Giả sử x là một phơng án cực biên nào đó. Ta ký hiệu:
J* = {j| x
j
> 0} (1.9)
Vì các vector A
j
, jJ* là độc lập tuyến tính nên |J*| m (|J*| là số số phần tử
x
j
>0).
* Phơng án cực biên x đợc gọi là không thoái hoá nếu | J* |= m, thoái hoá nếu
|J*| < m.
Ta chọn một hệ thống m vector độc lập tuyến tính {A
j
, j J}sao cho J J*.
Hệ thống đó gọi là cơ sở của x, các vector {A
j

,...A
m
.
Đối với phơng án cực biên này ta có:
với giá trị của hàm mục tiêu:
Trang: 13
( )
11.1,1, miaaz
ikij
Jj
jk
==


( )
10.1


=
Jj
jjkk
AzA
( )
12.1,....,1,0,
1
mjxbAx
j
m
j
jj

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ó:
Nếu các hệ số của các vector A
j
, j=1,.....,m và A
k
trong (1.20) không âm, khi đó
ta có một phơng án mới x mà đối với nó hàm mục tiêu f có giá trị
Trang: 14
( )
14.1

j
jk
AAz

=

=
( )
)20.1(
1
bAAzx
kj
m
j
jkj
=+

=

)21.1('
0 k
ZZ =


Trong (1.12) tất cả các biến x
j
, j=1,...,m đều dơng. Vì vậy có thể tìm đợc

> 0
sao cho


z
jk
trong (1.22) sẽ không âm

>0, nghĩa là ta luôn có phơng án

>0, nhng từ (1.21) ta dễ thấy giá trị hàm mục
tiêu tiến tới + khi

tiến tới +.
Trong thực hành Dantzig đã chứng minh rằng các bớc lặp sẽ giảm đáng kể nếu
ta thay vector A
s
thoả mãn:
và khi đó vector A
r
đợc xác định theo công thức:
Ta có phơng án cực biên mới x mà các thành phần của nó có dạng:
nếu j r
nếu j=r
và cơ sở của nó là
Trên cơ sở lý thuyết đã nhận đợc, ta chuyển sang xét thuật toán đơn hình.
Thuật toán đơn hình
Giả sử ta đã đa QHTT về dạng chính tắc:
Trang: 15
( )
23.10min
0
rk

( )
25.1,0min
rs
r
js
js
j
s
z
x
Jjz
z
x
=










>=

( )




cx=Z max
Ax=b
x0
Bớc 1: Xây dựng bảng đơn hình xuất phát. Tìm một phơng án cực biên xuất
phát x và cơ sở của nó A
j
, jJ.
Xác định các số z
jk
bởi hệ phơng trình:
Đối với mỗi k J , tính các ớc lợng:
Còn với jJ thì
j
= 0.
Tính giá trị hàm mục tiêu
Bớc 2: Kiểm tra tối u.
Nếu
k
0, k J thì x là phơng án tối u, dừng thuật toán. Trái lại, chuyển
sang bớc 3.
Bớc 3: Tìm vector đa vào cơ sở. Có hai khả năng xảy ra:
Tồn tại kJ sao cho
k
< 0 và z
jk
0, jJ thì bài toán QHTT không có
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

xcZ
0
rs
r
js
rs
j
s
z
x
z
z
x
=






>= 0min


Và đa vector A
r
ra khỏi cơ sở.
Bớc 5: Chuyển sang phơng án cực biên mới và cơ sở mới. Cơ sở mới là {A
j
,j
J} với J= J\{r} z{s}. Phơng án cực biên mới x đợc tính theo (1.26), khai

Để dễ tính toán, trong mỗi bớc lặp ta thiết lập bảng đơn hình (xem bảng 1.1).
Trang: 17
{ }
Jk
kks
>= ,0max








=
=




rjJj
jjss
rs
r
Jj
jjss
AzA
z
A
AzA





=








+=

,,,


+==
rjJj
rrkjjkj
Jj
jkk
AzAzAzA
,,
( )
( )
,28.1
,/
,/

Bảng 1.1
c
j
Cơ
sở
Ph
án
c
1
... c
j
... c
r
... c
m
... c
k
... c
s
... c
n
A
a
... A
j
... A
r
... A
m
...A

m
x
1
.
..
x
j
.
..
x
r
.
..
x
m
1 .
..
0 .
..
0 .
..
0
0 .
..
1 .
..
0 .
..
0
0 .

z
js
.
..
z
rs
.
..
z
ms
z
1n
...
z
jn
.
..
z
rn
.
..
z
mn
f
0... 0... 0... 0 ...
k
...
s
...
n

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.
Trang: 18
{ }
0min <=
kks










>== 0min
js
js
j
rs
r
r
z
z
x
z
x


, A
2
, ..., A
n
cùng sản xuất một loại hàng hóa với các lợng hàng
tơng ứng là a
1
, a
2
, ..., a
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

xc
1 1
)1.2(min













=>
==
==
==



= =
=
=
m
i
n
j

..., x
mn
) - Vector cột mxn thành phần.
C = (c
11
, c
12
, ..., c
ij,
..., 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

21
222221
111211















+=++
+=++
+=+++
=+++
=+++
=+++
nm
m
m
m
bxxx
bxxx

j
ji
baS
1 1
0

a) Đặt :
Ta thấy:
Lập thành một phơng án, vì rằng x
ij
0
b) Vì các hệ số trong (2.2), (2.3) và các đại lợng a
i
, b
j
không âm và hữu hạn nên
mọi x
ij
đều bị chặn trên. Thực vậy 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

,j
1
), (i
2
,j
2
), (i
3
,j
2
), ..., (i
s+1
,j
s
) (2.10)
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

ji
m
i
ij
i
n
j
ji
n
j
ji
n
j
ij
,1,
,1,
1
11
1
11
====
====




=
==
=
==

2
,j
3
), ..., (i
s
,j
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

P
i1j1
, phải có các vector P
i1jk
và vector P
iej1
. 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.
Đ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:
Trang: 23

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
+

_
),(),(



+
K
c
K
c
ji
ij
ji
ij
)13.2(
),(,
),(,
),(,









+
=


i
jij
n
j
iij
ij
njbx
miax
jix
1
'
1
'
'
,1,
,1,
),(,0
),()(',
),(
'
),(
'
XC
K
xc
K
cxcxcXC
i j
ji
ijij

a
m
Ta bắt đầu phân phối vào ô (1,1) lợng hàng:
x
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

Nếu x
1s
= a
1
thì xóa dòng 1 rồi tiếp tục quá trình từ dòng 2, b
s
= b
s
- x
1s
.
Nếu x
1s
= b
s
thì xóa cột s rồi tiếp tục quá trình, và lấy a
1
= a
1
- x
1s
.
Trang: 25