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.
THệ VIEN ẹIEN Tệ TRệẽC TUYEN

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

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
có n vector độc lập tuyến tính lập thành cơ sở của nó.
mix
i
i

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)
, y >+< x
(2)
, y>. ∀x
(1)
, x
(2)
, y ∈ R

, 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
xxxx
1
2
,
( )
0,lim
)0()(

* 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
cú th trớch ra mt dóy con {x
(ki)
} hi t ti phn t thuc C. Tp C l Compact
khi v ch khi C úng v gii ni. Tp Compact M ca tp úng C cng úng
trong C. Tp con úng M ca tp Compact cng Compact.
Hm f(x) liờn tc trờn tp Compact C thỡ s t cc tr trờn tp y.
1.1.3 Tp li
Cho hai im a, b R
n

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
thon món bt phng trỡnh
tuyn tớnh a
1
x
1
+ a
2
x

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*

C nu tn ti lõn cn m U ca
x* sao cho f(x*) f(x): xC U
Mnh 1: Bt k im cc tiu a phng no ca hm li trờn tp li
cng l im cc tiu tuyt i.
H qu: Bt k im cc i a phng no ca hm lừm cng l cc i
tuyt i.
Mnh 2: Cc i ca mt hm li (nu cú) trờn mt tp li cú im cc
biờn bao gi cng t ti mt im cc biờn.
1.2 Bi toỏn Quy hoch tuyn tớnh
QHTT bt ngun t nhng nghiờn cu ca nh toỏn hc Nga ni ting,

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 Nu bi toỏn Max cú phng ỏn ti u l x* thỡ bi toỏn min cng cú
phng ỏn l x* v f
min
=-

f
max
Tht vy, vỡ x* l phng ỏn ti u ca bi toỏn Max nờn ta cú:
Chng t x* l phng ỏn ti u ca bi toỏn Min v

Dxxcxc
hayDxxcxcf
n
j
jj
n
j
jj
j
n
j
j
n
j
jj

=


==
==
,
,
11
*
11
*
max

=

j
jij
=
==

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

-Dng chun: -Dng chớnh tc: a bi toỏn QHTT v dng chun hoc dng chớnh tc.
Bt k QHTT no cng cú th a v mt trong hai dng chun hoc chớnh
tc nh cỏc phộp bin i tuyn tớnh sau:
i) Mt rng buc Cú th a v rng buc bng cỏch nhõn hai v vi (-1) v
vit li
ii) Mt rng buc ng thc


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



=
=

=

n
j


=
1
ij
n
j
ij
bxa

=
1
.''
1
ij
n
j
ij
bxa

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

Cú th a v rng buc ng thc bng cỏch a vo bin ph y
i
0: V nguyờn tc, ỏp dng nhiu ln cỏc phộp bin i (i), (ii) v (iii) ta cú th
a mt bi toỏn QHTT bt k v dng chun, sau ú ỏp dng nhiu ln phộp
bin i (iv) ta s a nú v dng chớnh tc.

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
1
,c
2
) cho n khi vic dch chuyn tip theo lm
cho ng mc khụng cũn ct D na thỡ dng. im ca D (cú th nhiu im)
i
n
j
ijij
byxa =+

=
1



=

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

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 nhưng 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 tốn QHTT là tập lồi.

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
j
, j=1, ..., n l cỏc vector ct ca ma trn A.
Khi y h rng buc Ax =b cú th vit:
x
1
A
1
+ x
2
A
2
+ ... + x
n
A
n
= b
(1.4)

Mnh 3: Nu cỏc vector A
1
, A

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
> 0 lp thnh h
c lp tuyn tớnh. Vỡ ma trn A cú m dũng nờn t õy suy ra rng im cc
biờn khụng cú quỏ m thnh phn dng.
Cỏc mnh 3 v mnh 4 cú th gp li thnh mt mnh sau:
Mnh 5: x =(x
1
,x
2
...,x
n
) l phng ỏn cc biờn ca QHTT di dng
chớnh tc thỡ cn v l cỏc vector ct A
j
ca ma trn A ng vi cỏc thnh phn
x
j
> 0 l c lp tuyn tớnh.
1.2.3 Phng phỏp n hỡnh gii bi toỏn QHTT
C s ca phng phỏp ny c G.B. Dantzig cụng b nm 1947 cú tờn
gi l phng phỏp n hỡnh. S d cú tờn gi nh vy l vỡ nhng bi toỏn u

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

= b
(1.7)

x 0
(1.8)

Trong ú A l ma trn kớch thc mxn v gi s rng hng ca ma trn A
l m (iu ny khụng lm mt tớnh tng quỏt). x l mt vector.
Gi s x l mt phng ỏn cc biờn no ú. Ta ký hiu:
J* = {j| x
j
> 0}

(1.9)

Vỡ cỏc vector A
j
, jJ* l c lp tuyn tớnh nờn |J*| m (|J*| l s s phn
t
x
j
>0).

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
, x
2
,...x
m
, 0,...0) v c s ca nú A
1,
, A
2
,...A
m
.
i vi phng ỏn cc biờn ny ta cú: vi giỏ tr ca hm mc tiờu:

Ta tớnh cỏc i lng sau:

Kớ hiu:

nh lý 1.1: (Tiờu chun ti u). Nu i vi phng ỏn cc biờn
x=(x
1
,x
2

=>=

=
( )
13.1
1
0

=
=
m
j
jj
zxc
( )
14.1
1

=
=
m
j
kjjk
Zcz
( )
15.1
1
k
m
j

0
.
Cụng thc tỡm phng ỏn x:
Nhõn (1.10) vi

no ú ta cú:
Ly (1.12) tr i (1.19) tng v ta cú:
Nu cỏc h s ca cỏc vector A
j
, j=1,.....,m v A
k
trong (1.20) khụng õm,
khi ú ta cú mt phng ỏn mi x m i vi nú hm mc tiờu f cú giỏ tr
Trong (1.12) tt c cỏc bin x
j
, j=1,...,m u dng. Vỡ vy cú th tỡm c

> 0 sao cho
Nu i vi ch s k m
k
< 0, tn ti z
jk
> 0, jJ thỡ giỏ tr

ln nht cũn
tho món (1.22) cú th xỏc nh bi h thc : Nu ta thay


=










>=


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

)19.1(
1
kj
m
j
jk
AAz

=

=

-

z
jk
trong (1.22) s khụng
õm

>0, ngha l ta luụn cú phng ỏn

>0, nhng t (1.21) ta d thy giỏ
tr hm mc tiờu tin ti + khi

tin ti +.
Trong thc hnh Dantzig ó chng minh rng cỏc bc lp s gim ỏng k
nu ta thay vector A
s
tho món:
v khi ú vector A
r
c xỏc nh theo cụng thc:
Ta cú phng ỏn cc biờn mi x m cỏc thnh phn ca nú cú dng:
nu j r
nu j=r
v c s ca nú l
Trờn c s lý thuyt ó nhn c, ta chuyn sang xột thut toỏn n hỡnh.
Thut toỏn n hỡnh
Gi s ta ó a QHTT v dng chớnh tc:

cx=Z max
Ax=b










>=

( )






=
,/
,/
'
rsr
jsrsrj
j
zx
zzxx
x
( )
26.1

< 0 v z
jk
0, jJ thỡ bi toỏn QHTT
khụng cú li gii ti u (Z khụng b chn trờn). Dng thut toỏn.
i vi mi kJ sao cho
k
< 0 u tn ti j

J: z
jk
> 0. Khi ú
chn ch s s theo tiờu chun:
a vector A
s
vo c s.
Bc 4: Tỡm vector loi khi c s. Xỏc nh
V a vector A
r
ra khi c s.
Bc 5: Chuyn sang phng ỏn cc biờn mi v c s mi. C s mi l
{A
j
,j J} vi J= J\{r} z{s}. Phng ỏn cc biờn mi x c tớnh theo
(1.26), khai
trin ca cỏc vộc t A
k
theo cỏc c s mi c tớnh theo cụng thc (1.28).
Quay lờn bc 2.
Chỳ ý. i vi bi toỏn min thỡ tiờu chun ti u l







>= 0min

{ }
Jk
kks
>= ,0max
{ }
0,, = xbAxxc
THệ VIEN ẹIEN Tệ TRệẽC TUYEN

Ta ó cú cụng thc (1.26) tớnh cỏc thnh phn ca x. Bõy gi ta thit
lp cụng thc tớnh cỏc s z
jk
. Ta cú:
Mt khỏc
Thay biu thc ca A
r
vo ta c: õy l cụng thc biu din A
k
qua c s mi J =J\{r}{s}. Bi vy ta cú:
nu jr


... c
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
r

...
0
...
0
...
0

0
...
1
...
0
...
0

0
...
0
...
1
...
0

0
...
0
...
0
...
1

jn
...
z
rn
.
..
z
m
n

f
0... 0... 0... 0 ...
k
...
s
...
n








=
=




A
z
z
zAzA
z
z
AzA +








=








+=

,,,


+==

jkk
ccz =


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

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 tố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
, 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

, A
2
, ..., A
m
, nghĩa là J = {1,2, ..., m}. { }
0min <∆∆=∆
kks










>==
0min
js
js
j
rs
r
r
z
z

với các 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í chun chở một đơn vị hàng từ điểm phát (i) đến điểm thu (j).
x
ij
- lượng hàng chun chở từ (i) đến (j).
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à:

∑ ∑
∑
∑
= =
=
=
m
i
n
j
jiji
ij
m
i
jij
n
j
iij
Ibaba
njmix
njbx
miax
1 1
1
1
)(;0,
)4.2(,1;,1,0
)3.2(,1,
)2.2(,1,
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN

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.
Định nghĩa 1: Vector X thỏa mãn (2.7), (2.8) được gọi là một phương án
của BTVT.
Một phương án đạt cực tiểu (2.6) gọi là phương án tối ưu.
Một phương án X gọi là phương án cơ sở nếu vector cột P
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.

+=++
+=++
+=+++
=+++
=+++
=+++
nm
m
m
m
bxxx
bxxx
bxxx
axxx
axxx
axxx
nmnnn
m
m
mmnmm
n
n





≥
=
><

biờn, sau mt s hu hn bc ta phi i ti mt phng ỏn cc biờn ti u.
nh ngha 2:
- Mt ụ (i,j) m x
ij
gi l ụ s dng.
- Tp cỏc ụ sau c gi l mt dõy truyn trong T
(i
1
,j
1
), (i
1
,j
2
), (i
2
,j
2
), (i
2
,j
3
), ..., (i
s
,j
s+1
)
(2.9)

hoc: (i

= i
1

Gi G l tp hp cỏc ụ s dng:
G = {(i,j) | x
ij
> 0 } |G| m+n-1
- Mt phng ỏn X ca BTVT ó cho c gi l khụng thoỏi húa nu
|G| = m+n-1
Ngc li l thoỏi húa nu |G| m+n-1
- Nu mt tp hp con thc s ca G lp thnh chu trỡnh thỡ ta cú mt chu
trỡnh con ca G.
njmi
S
ba
x
ji
ij
,1;,1, ===
njb
S
ab
S
ba
x
mia
S
ba
S
ba




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

nh lý 2.2: H thng vector P
ij
ca BTVT l c lp tuyn tớnh khi v ch
khi cỏc ụ tng ng vi cỏc vector ca h thng khụng to thnh chu trỡnh.
Chng minh: Cn. Ký hiu P
ij
= { P
ij
(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

isj1
= 0
tc l h P
ij
ph thuc tuyn tớnh, mõu thun vi gi thit.
: Gi s G khụng lp thnh chu trỡnh. Ta phi chng minh h P
ij
l c
lp tuyn tớnh.
Bng phn chng, gi s h P
ij
l ph thuc tuyn tớnh. Mi vector P
ij
cú
dng:
(
1
, ...,
i
, ...,
m
,
m+1
, ...,
m+j
, ...,
m+n
)
vi thnh phn
i

iu ú xy ra khi v ch khi tp cỏc ụ s dng tng ng khụng lp thnh chu
trỡnh.
nh lý 2.3: Gi s X l mt phng ỏn ca BTVT v tp G ca nú lp
thnh chu trỡnh, th thỡ bao gi cng cú th iu chnh c X chuyn sang
mt phng ỏn mi X khụng xu hn m tp G khụng lp thnh chu trỡnh.
THệ VIEN ẹIEN Tệ TRệẽC TUYEN

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)
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







∉
∈−
∈+
=
−
+
Kjix
Kjix
Kjix
x
ij
ij
ij
ij
θ
θ









'
),(
'
XC
K
xc
K
cxcxcXC
i j
ji
ijij
ji
ijijij
i j
ijij
≤−++=><
∑∑ ∑∑∑∑
−+
∈∈
θ
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN

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

- Nu x
11
= a
1
thỡ ta xúa hng 1. Lp bng mi cú b
1
= b
1
- x
11
. Tip tc
quỏ trỡnh, bt u t ụ (2,1).
- Nu x
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

- x
1s
.
Nu x
1s
= b
s
thỡ xúa ct s ri tip tc quỏ trỡnh, v ly a
1
= a
1
- 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

)
mxn
tng ng l ti u. Mun vy, phi chng
minh:
<C, X> <C, X> X = (x
ij
)
mxn(2.16)
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

+=+==
j
jj
i i
ii
j
ijji
i j
ijij
bvauxvuxcxf
(x
ij
> 0

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