KILOBOOKS.COM

LI M U

Cựng vi s phỏt trin mnh m ca khoa hc k thut, cỏc bi toỏn ti u
xut hin ngy cng nhiu v tớnh phc tp ca chỳng ngy cng ln. Phm vi
v kh nng ng dng ca cỏc bi toỏn ti u cng ngy cng a dng v phong
phỳ.
Lp bi toỏn ti u quan trng c nghiờn cu u tiờn v c ng dng
nhiu nht l bi toỏn quy hoch tuyn tớnh (linear programming). ú l mụ
hỡnh toỏn hc ca mt lp rng ln cỏc bi toỏn ng dng trong kinh t v k
thut. Do ú cu trỳc ca lp bi toỏn quy hoch tuyn tớnh cú nhiu tớnh cht
rt tt v mt toỏn hc, ngi ta ó tỡm c cỏc thut gii rt hu hiu cho bi
toỏn ny. Nm 1947 nh toỏn hc M G.B. Dantzig ó nghiờn cu v xut ra
thut toỏn n hỡnh (simplex method) gii bi toỏn quy hoch tuyn tớnh.
Thut toỏn n hỡnh c phỏt trin mnh m trong nhng nm sau ú v c
xem l mt phng phỏp kinh in gii cỏc bi toỏn quy hoch tuyn tớnh.
õy l mt phng phỏp c s dng cú th núi l rng rói nht. Cú ba lý do
chớnh:
Mt l: Rt nhiu vn thc t, trong nhiu lnh vc khỏc nhau cú th a
v bi toỏn quy hoch tuyn tớnh.
Hai l: Trong nhiu phng phỏp gii cỏc bi toỏn phi tuyn, bi toỏn
tuyn tớnh xut hin nh l mt bi toỏn ph cn phi gii trong nhiu bc lp.
Ba l: Phng phỏp n hỡnh l phng phỏp hiu qu gii bi toỏn quy
hoch tuyn tớnh.
Ngy nay, bng thut toỏn n hỡnh v cỏc dng ci biờn ca chỳng, ngi
ta cú th gii rt nhanh cỏc bi toỏn QHTT c ln.
Lp cỏc bi toỏn vn ti l trng hp c bit ca quy hoch tuyn tớnh,
bi vy cú th dựng cỏc phng phỏp ca quy hoch tuyn tớnh gii. Tuy
nhiờn, do tớnh cht c thự riờng ca nú, ngi ta xõy dng cỏc phng phỏp
gii riờng.

Trong việc nghiên cứu các bài tốn tối ưu nói chung, giải tích lồi giữ một
vai trò rất quan trọng. Nó được sử dụng làm cơ sở tốn học trong việc xây dựng
các thuật tốn.
Quy hoạch tuyến tính là một trong những lớp bài tốn tối ưu được nghiên
cứu trọng vẹn cả về phương diện lý thuyết lẫn thực hành, Bài tốn vận tải là một
dạng đặc biệt của QHTT. Do đó chương này nhằm giới thiệu một số khái niệm
và kiến thức cơ bản về giải tích lồi và QHTT.
1.1 Một số khái niệm về giải tích lồi
1.1.1 Khơng gian Euclude
Một vector n chiều trên trường số thực là một bộ được sắp thứ tự gồm n số
thực x=(x
1
, x
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 tốn trên các vector:
Phép cộng: x+y=(x
1
+y
1

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

là tổ hợp tuyến tính của các vector e
(1)
, e
(2)
, ..., e
(n)
. Ta gọi tích vô hướng của hai
vector x=(x
1
, x
2
, ..., x
n
) và y=(y
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)

k=1, 2, ... được gọi là có giới hạn x
(0)
khi k → ∞ và viết
lim x
(k)
= x
(0)
, nếu
Hình cầu tâm a bán kính ρ là tập S={x∈R
n
:x-a≤ ρ }. Hình cầu này tạo
nên ρ- lân cận của điểm a, hay gọi là lân cận của a.
* Nếu tập A⊂R
n
chứa cùng với điểm x một lân cận của nó thì x gọi là điểm
trong của A. Nếu trong lân cận bất kỳ của x ∈ A có các điểm của A và các điểm
không thuộc A thì x gọi là điểm biên của tập hợp A.
* Một tập A⊂R
n
gọi là giới nội nếu nó được chứa trong một hình cầu tâm O
nào đó, tức là tồn tại số ρ đủ lớn sao cho với mọi x∈A,x≤ ρ. Một dãy {x
(k)
}
hội tụ thì bao giờ cũng giới nội.
∑
=
=><=
n
i
i

yxyxyxyxyx
1
2
,,
ρ

THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
KILOBOOKS.COM

* Mt tp hp GR
n
c gi l m nu vi mi xG u tn ti mt hỡnh
cu tõm x nm gn trong G. Mt tp FR
n
c gi l úng nu vi mi dóy hi
t{x
(k)
} F ta u cú:
Fx
k
k


)(
lim

Mt tp cha mi im biờn ca nú l tp úng.
* Tp C c gi l tp Compact nu t mi dóy vụ hn {x
(k)
} thuc C u

n
) R
n
tha món phng trỡnh tuyn tớnh
a
1
x
1
+ a
2
x
2
+ ... + a
n
x
n
= trong ú a
1
, a
2
, ..., a
n
, R
* Tp hp cỏc im x=(x
1
, x
2
, ..., x
n
) R

n
c gi l tp li nu cựng vi vic cha hai im x, y nú
cha c on thng cha hai im y, tc l cha tt c cỏc im cú dng:
x + (1-)y, 0 1
Vớ d v cỏc tp li: Khụng gian Euclide, cỏc na khụng gian, mt phng,
na mt phng, hỡnh ch nht, hỡnh vuụng, hỡnh elip, hỡnh hp, hỡnh cu ...

THệ VIEN ẹIEN Tệ TRệẽC TUYEN
KILOBOOKS.COM

* Mt tp hp l giao ca mt s hu hn cỏc na khụng gian úng c
gi l tp li a din.
Mnh : Giao ca hai tp li l mt tp li.
H qu 1. Giao ca mt s bt k tp hp li l tp li.
H qu 2. Min cha nghim ca mt h bt phng trỡnh tuyn tớnh dng.
l mt tp li (a din li). Mt tp li a din gii ni gi l mt a din.
Giao ca tt c cỏc tp li cha tp X gi l bao li ca nú, ký hiu [X]
1.1.4 Hm li
* Mt hm s f(x) xỏc nh trờn tp li C R
n
c gi l hm li trờn C,
nu vi mi x, y C v 0 1 ta cú f(x + (1-)y) f(x) + (1-)f(y).
* Hm f(x) c gi l hm li cht nu vi mi x, y C v 0 1 ta
cú. f(x + (1-)y) < f(x) + (1-)f(y).
* Hm f(x) c gi l hm lừm (lừm cht) nu - f(x) l hm li (li cht)
* Hm f(x) xỏc nh trờn C t cc tiu tuyt i ti x* C nu
f(x
*
) f(x): xC
* Hm f(x) t cc tiu a phng ti x*

+++
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa

THệ VIEN ẹIEN Tệ TRệẽC TUYEN
KILOBOOKS.COM

nghiờn cu v xut phng phỏp n hỡnh (Simplex method) gii bi toỏn
QHTT. Nm 1952 phng phỏp n hỡnh ó c chy trờn mỏy tớnh in t
ca M.
1.2.1 Bi toỏn quy hoch tuyn tớnh
Bi toỏn tng quỏt.
nht quỏn lp lun ta xột bi toỏn tỡm cc i, sau ú ta xột cỏch chuyn
bi toỏn tỡm cc tiu sang tỡm cc i. Bi toỏn tng quỏt ca QHTT cú dng:
Ký hiu: A=(a
ij
)
mxn
l ma trn vi cỏc phn t a
ij
(1.1) gi l hm mc tiờu, (1.2) l cỏc rng buc.
Nu gp bi toỏn Min, tc l Thỡ gi nguyờn rng buc v a v bi toỏn Max bng cỏch


( )
Dx
xcxf
j
n
j
j

=

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

=

j
j
xc
( ) ( )
( )
3.1,...,1,0
2.1...,,1,,,
1
njx
mibxa
j
i
n
j
jij
=
==

=

THệ VIEN ẹIEN Tệ TRệẽC TUYEN
KILOBOOKS.COM

-Dng chun: -Dng chớnh tc:

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



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

j
jij
bxabxa

== 11
,
0,0, =
++
jjjjj
xxxxx với
ij
n
j
ij
bxa

=
1
ij
n
j
ij
bxa

=
1
.''
1
ij
n


xỏc nh mt na mt phng.
Nh vy min rng buc D c xỏc nh nh l giao ca mt na mt
phng v s l mt a giỏc li trờn mt phng. Phng trỡnh c
1
x
1
+c
2
x
2
=

khi


thay i s xỏc nh trờn mt phng cỏc ng thng song song vi nhau m ta
s gi l cỏc ng mc (vi giỏ tr mc

). Mi im D s nm
trờn mt ng mc vi mc
Bi toỏn t ra cú th phỏt biu theo ngụn ng hỡnh hc nh sau: trong s
cỏc ng mc ct tp D, hóy tỡm ng mc vi gớa tr ln nht.
Nu dch chuyn song song cỏc ng mc theo hng vector phỏp tuyn
ca
chỳng thỡ giỏ tr mc s tng, nu dch chuyn theo hng ngc li
thỡ giỏ tr mc s gim. Vỡ vy gii bi toỏn t ra, ta cú th tin hnh nh
sau.
Bt u t mt ng mc ct D, ta dch chuyn song song cỏc ng mc
theo hng vector phỏp tuyn (c

iii
( )
21
, xxx =
.
2211
xcxc +=

( )
21
, ccn =

THệ VIEN ẹIEN Tệ TRệẽC TUYEN
KILOBOOKS.COM

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 tốn.
Ví dụ: Xét bài tố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

≥≥





≤
≤+
≤+
xx
x
xx
xx
y
n
*x
x

THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
KILOBOOKS.COM

Nu D l mt a din li thỡ bi toỏn cú phng ỏn, hn na giỏ tr ti u
ca hm mc tiờu trờn a din li l hu hn v vic tỡm phng ỏn ti u a
n vic chn cỏc im ca a din D cú s nh (im cc biờn hay phng ỏn
cc biờn) hu hn.
Mnh 2: Hm mc tiờu ca bi toỏn QHTT s t Max ti im cc biờn
ca tp D. Nu hm mc tiờu khụng ch nhn Max ti mt im cc biờn ca tp
li D m ti nhiu im cc biờn thỡ nú s t giỏ tr cc i ti nhng im l t
hp li ca cỏc im ú.
Ký hiu A

2
A
2
+...+x
n
A
n
=b
trong ú x
j
>
0, j=1,...k thỡ im
x=(x
1
,x
2
,...,x
k
,0,...,0)
l im cc biờn ca tp li a din D.
Mnh 4: Nu x =(x
1
,x
2
,...,x
n
) l im cc biờn ca tp li a din D thỡ
cỏc vector A
j
trong biu din (1.4) ng vi cỏc thnh phn x

j
==

=

THệ VIEN ẹIEN Tệ TRệẽC TUYEN
KILOBOOKS.COM

M tp hp cỏc im xR
n
tho món cỏc rng buc trờn l mt n hỡnh
trong khụng gian n chiu.
ng li chung v c s ca thut toỏn.
i) ng li chung.
Phng phỏp n hỡnh da trờn hai nhn xột sau: nu bi toỏn QHTT cú
phng ỏn ti u, a din li D cú mt s hu hn nh. Nh vy phi tn ti
thut toỏn hu hn. Thut toỏn gm hai giai on:
- Giai on 1: Tỡm mt phng ỏn cc biờn (mt nh).
- Giai on 2: Kim tra iu kin ti u i phng ỏn tỡm c giai
on 1. Nu iu kin ti u c tho món thỡ phng ỏn ú l ti u. Nu
khụng, ta chuyn sang phng ỏn cc biờn mi sao cho ci tin giỏ tr hm mc
tiờu. Tip theo li kim tra iu kin ti u i vi phng ỏn mi.
Ngi ta thc hin mt dóy cỏc th tc nh vy cho n khi nhn c
phng ỏn ti u, hoc n tỡnh hung bi toỏn khụng cú phng ỏn ti u.
ii) C s ca thut toỏn.
Xột bi toỏn QHTT di dng chớnh tc:
< c, x > max
(1.6)

Ax

j
, j J}sao cho J
J*. H thng ú gi l c s ca x, cỏc vector {A
j
, j J} v cỏc bin {x
j
, j J}
c gi l cỏc vector v cỏc bin c s tng ng. Cỏc vector v cỏc bin A
j
,
x
j
, j J gi l cỏc vector v cỏc bin phi c s tng ng.
Nu x khụng thoỏi hoỏ thỡ tn ti mt c s duy nht, ú l J=J*.
Mi vector A
k
phi c s cú th biu din di dng t hp tuyn tớnh ca
cỏc vector c s:

Trong ú cỏc h s z
jk
c xỏc nh duy nht bi vic gii h phng
trỡnh: Bi toỏn QHTT c gi l khụng thoỏi hoỏ nu tt c cỏc phng ỏn cc
biờn ca nú u khụng thoỏi hoỏ.
Gi s bi toỏn khụng thoỏi hoỏ v ta ó tỡm c mt phng ỏn cc biờn
x=(x
1

Chỳ ý:
( )
11.1,1, miaaz
ikij
Jj
jk
==


( )
10.1


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

=
( )
13.1

16.1,.....,2,1,0 nk
k
=

THệ VIEN ẹIEN Tệ TRệẽC TUYEN
KILOBOOKS.COM

Trong (1.10) nu A
j
l mt vector c s, khi ú tn ti ch mt h s
z
jj
=1, tt c cỏc h s khỏc u bng 0 v ta cú:

v trong thc hnh kim tra iu kin ti u ca phng phỏp cc biờn x
ta ch cn kim tra

k
0, kJ
(1.18)

Ngi ta cú th chng minh rng nu bi toỏn khụng thoỏi hoỏ thỡ (1.16)
cng l iu kin cn ca ti u.
nh lý 1.2: Nu tn ti mt ch s k sao cho
k
< 0 thỡ ngi ta cú th tỡm
c ớt nht mt phng ỏn x m i vi nú Z > Z
0
.
Cụng thc tỡm phng ỏn x:

thỡ thnh phn th r s bng 0:
x
r
-

o
z
rk
=0.
( )
17.1,0 Jjcc
jjj
==
( )
23.10min
0
rk
r
jk
jk
j
Jj
z
x
z
z
x
=



bAAzx
kj
m
j
jkj
=+

=

)21.1('
0
k
ZZ =

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


THệ VIEN ẹIEN Tệ TRệẽC TUYEN
KILOBOOKS.COM

Nh vy ta nhn c phng ỏn mi x vi c s A
j
, jJ\ {r}{k}=J.
Nu z
jk
0, j J thỡ tt c cỏc thnh phn x
j
-

Bc 1: Xõy dng bng n hỡnh xut phỏt. Tỡm mt phng ỏn cc biờn
xut phỏt x v c s ca nú A
j
, jJ.
Xỏc nh cỏc s z
jk
bi h phng trỡnh:
i vi mi k J , tớnh cỏc c lng:
{ }
( )
24.10min <=
kk
k
s
( )
25.1,0min
rs
r
js
js
j
s
z
x
Jjz
z
x
=



27.1\', srJJjA
j
=
kj
Jj
jk
AAz =


kj
Jj
jkk
ccz =



THệ VIEN ẹIEN Tệ TRệẽC TUYEN
KILOBOOKS.COM

Cũn vi jJ thỡ
j
= 0.
Tớnh giỏ tr hm mc tiờu
Bc 2: Kim tra ti u.
Nu
k
0, k J thỡ x l phng ỏn ti u, dng thut toỏn. Trỏi li,
chuyn sang bc 3.
Bc 3: Tỡm vector a vo c s. Cú hai kh nng xy ra:
Tn ti kJ sao cho


k
0 (k) v vector A
s
c chn a vo c s theo cụng thc:
Cụng thc i c s v bng n hỡnh.
Ta xột cỏc cụng thc chuyn t phng ỏn cc biờn x vi c s J sang
phng ỏn cc biờn x vi c s J.
{ }
0min <=
kks


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

qua c s mi J =J\{r}{s}. Bi vy ta cú:
nu jr

nu j=r

Sau khi cú z
jk
ta tớnh:
d tớnh toỏn, trong mi bc lp ta thit lp bng n hỡnh (xem bng
1.1).
Nu tt c cỏc s trong dũng cui (tr hm mc tiờu f) u khụng õm, ngha
l
k
0 k, khi ú x l phng ỏn ti u.
Bng 1.1
c
j

C


s


Ph
ỏn

c
1
... c

...
c
r
...
c
m

A
1
...
A
j
...
A
r
.
..
A
m

x
1
...
x
j
...
x
r
...
x

0
...
1

z
1k
...
z
jk
...
z
rk
...
z
mk

z
1s
...
z
js
...
z
rs
.
..
z
ms

z





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



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






=
rsrk
jsrsrkjk
jk
zz
zzzz
z
( )
29.1''

, j ≠ r gọi là phần tử quay.
Các cơng thức (1.26), (1.29) gọi là các cơng thức đổi cơ sở. Bảng đơn hình
mới suy được từ bảng cũ bằng cách thay c
r
, A
r
trong dòng quay bằng c
s
, A
s
. Sau
đó thực hiện các phép biến đổi dưới đây:
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
Lưu ý 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ũ.
Tồ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 khi thực hiện phép quay ta có một phương án mới và một cơ sở mới. Nếu
chưa đạt u cầ nghĩa là còn ∆

rs
r
r
z
z
x
z
x
θ

THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
KILOBOOKS.COM

CHƯƠNG 2. BÀI TỐN VẬN TẢI VÀ BÀI TỐN VẬN TẢI MỞ RỘNG

2.1 Bài tốn vận tải hai chỉ số
2.1.1 Phát biểu bài tốn và tính chất
Có m địa điểm A
1
, 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

Bài tốn đặt ra là: xác định những đại lượng x
ij
cho mọi con đường (i,j) sao
cho tổng chi phí chun chở là nhỏ nhất với giả thiết là:
Tức là lượng hàng phát ra bằng đúng lượng hàng u cầu ở các điểm thu
(điều kiện cân bằng thu phát).
Dạng tốn học của BTVT là:
Hệ rằng buộc (2.2), (2.3) có m + n phương trình, m x n ẩn, tuy nhiên do (I)
nên bất kỳ phương trình nào trong m + n phương trình cũng là hệ quả của các
∑∑
= =
→
m
i
n
j
ijij
xc
1 1
)1.2(min











1
1
)(;0,
)4.2(,1;,1,0
)3.2(,1,
)2.2(,1,

THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
KILOBOOKS.COM

phương trình còn lại và có thể bỏ đi. Thật vậy, hệ rằng buộc có thể viết dạng
(2.5).
Giả sử ta cộng các phương trình từ thứ (m+1) tới thứ (m+n) rồi trừ đi tổng
các phương trình từ thứ (2) tới thứ (m) thì ta được phương trình thứ (1). Do đó
số phương trình cực đại của hệ (2.2), (2.3) không quá m + n-1.
Ký hiệu ma trận của hệ (2.5) là A.
X = (x
11
, x
12
, ..., x
ij,
..., x
mn
) - Vector cột mxn thành phần.
C = (c
11
, c
12
, ..., c

ij
của ma trận A
tương ứng với các x
ij
> 0 là độc lập tuyến tính.
Định lý 2.1: BTVT luôn có phương án tối ưu.
Chứng minh:
1) Trước hết ta chứng minh BTVT luôn có phương án.
2) Sau đó chứng minh rằng miền rằng buộc giới nội.
)5.2(
)(
.....
)2(
)1(...
)(...
.....
)2(...
)1(...
21
222212
112111
21
222221
111211







n





≥
=
><
)8.2(0
)7.2(
)6.2(,min
X
PAX
XC

THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
KILOBOOKS.COM

a) t :
Ta thy:
Lp thnh mt phng ỏn, vỡ rng x
ij
0
b) Vỡ cỏc h s trong (2.2), (2.3) v cỏc i lng a
i
, b
j
khụng õm v hu
hn nờn mi x

2
,j
3
), ..., (i
s
,j
s+1
)
(2.9)

hoc: (i
1
,j
1
), (i
2
,j
1
), (i
2
,j
2
), (i
3
,j
2
), ..., (i
s+1
,j
s

njb
S
ab
S
ba
x
mia
S
ba
S
ba
x
j
m
i
ij
m
i
ji
m
i
ij
i
n
j
ji
n
j
ji
n

(i,j) G}. Gi s P
ij
l h c lp
tuyn tớnh, ta phi chng minh G khụng lp thnh chu trỡnh.
Bng phn chng, nu cú mt chu trỡnh to nờn bi cỏc ụ tng ng vi
mt s vector ca h P
ij
thỡ nú cú dng:
(i
1
,j
1
), (i
1
,j
2
), (i
2
,j
2
), (i
2
,j
3
), ..., (i
s
,j
s+1
) vi j
s+1

, ...,
i
, ...,
m
,
m+1
, ...,
m+j
, ...,
m+n
)
vi thnh phn
i
=
m+j
= 1 cũn cỏc ta khỏc bng 0.
Nu h P
ij
ph thuc tuyn tớnh, tc l cú mt t hp tuyn tớnh ca cỏc
vector P
ij
bng 0. iu ú cú ngha l trong thnh phn ca t hp ny ngoi
vector dng P
i1j1
, phi cú cỏc vector P
i1jk
v vector P
iej1
. Nhng iu ú chng t
rng cỏc ụ {(i,j)} tng ng vi h thng P

Ký hiệu: θ = min{x
ij
(i,j) ∈ K
-
}
(2.12)

Ta chuyển X → X’ như sau:
Rõ ràng X’ vẫn còn là phương án của BTVT vì rằng:
Vì mỗi hàng hay cột chỉ chứa 2 ô sử dụng nên θ và (-θ) triệt tiêu nhau.
Hàm mục tiêu không tăng vì
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. Nếu còn chu trình nào khác ta lại phá bằng cách tương tự. Vì
vậy ta luôn có thể giả thiết rằng phương án đang xét có các ô sử dụng không lập
thành chu trình.
Hệ quả: Mọi phương án X đều có thể chuyển về phương án cức biên X’
không xấu hơn X.
2.1.2 Cách tìm phương án xuất phát
)11.2(
_
),(),(
∑∑
∈∈

x
ij
ij
ij
ij
θ
θ











==
==
∀≥
∑
∑
=
=
m
i
jij
n
j

≤−++=><
∑∑ ∑∑∑∑
−+
∈∈
θ

THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
KILOBOOKS.COM

Phng phỏp gúc tõy bc.
Lp bng T, ta ghi s liu vo bng ú, luụn xut phỏt t ụ gúc trờn, bờn
trỏi.

b
j

a
i
b
1
... b
j
... b
n
a
1
x
j

...

11
= b
1
thỡ ta xúa ct 1. Lp bng mi cú a
1
= a
1
- x
11
. Tip tc quỏ
trỡnh, bt u t ụ (1,2).
Mt ln phõn phi nh vy ta c mt ti lng x
ij
> 0 v b bt i c
mt hng (hoc ct) ca bng T. Bng mi cui cựng ch cũn li mt ụ (m, n) v
do cõn bng thu phỏt nờn cc ti t c hng, c ct sau khi phõn phi lng
cũn li. Do ú ta xúa c ct n v hng m i. Tng s hng v ct l m + n mi
ln phõn phi b i c 1 hng (hoc ct), ln cui cựng b c ct n v hng m,
nờn phng ỏn thu c cú khụng quỏ m + n - 1 ụ s dng, khụng lp thnh chu
trỡnh, tc l cú phng ỏn cc biờn.
Phng phỏp cc phớ ti thiu trong ton bng.
Quỏ trỡnh bin i v phõn phi hon ton ging nh phng phỏp trờn ch khỏc
l trong mi bc ta khụng chn ụ gúc tõy bc m chn ụ cú cc phớ nh
nht trong ton bng.
Phng phỏp cc tiu cc phớ theo hng.
Bt u t hng 1: Gi s c
1s
= min c
ik
, k = 1, ..., n

- x
1s
.
Phng phỏp cc tiu cc phớ theo ct.
Tng t nh phng phỏp trờn, nhng xut phỏt t ct th 1.
Dựng cỏc phng phỏp trờn tỡm phng ỏn xut phỏt, trong mt s ln
cỏc trng hp, s bc lp dn ti nghim gim i khỏ nhiu, nht l khi gii
BTVT m s im phỏt v thu rt ln.
2.1.3 Thut toỏn
Tiờu chun ti u
nh lý 2.4: Phng ỏn X ca BTVT l ti u cỏc s u
i
, i = 1, ..., m v
v
j
, j = 1, ..., n sao cho:
u
i
+ v
j
c
ij
(i,j)T

(2.14)
u
i
+ v
j
= c

Mt khỏc do (2.14), (2.15) tc l:
u
i
+ v
j
< c
ij
vi x
ij
= 0
u
i
+ v
j
= c
ij
vi x
ij
> 0

Nờn ta cú: T (2.17) v (2.18) ta cú (2.16).
b) Cn:
)17.2()()'(
'''

+=+=+=
j

ij
> 0

)

THệ VIEN ẹIEN Tệ TRệẽC TUYEN