I HÅC THI NGUYN
TR×ÍNG I HÅC KHOA HÅC
Ph¤m B¡ T¼nh
BI TON VN TI CÂ HN CH
KH NNG L×U THÆNG V ÙNG DÖNG
Chuy¶n Ngh nh: TON ÙNG DÖNG
M¢ sè: 60.46.01.12
LUN VN THC S TON HÅC
Th¡i Nguy¶n - 2013
Soá hoùa bôûi trung taâm hoïc lieäu
http://www.lrc-tnu.edu.vn/
1
Möc löc
Líi nâi ¦u
Ch÷ìng 1. BI TON VN TI C KH NNG L×U
THÆNG HN CH
5
. . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.1.
B i to¡n v t½nh ch§t . . . . . . . . . . . . . . . . . . . .
5
1.2.
Ph÷ìng ¡n cüc bi¶n ban ¦u . . . . . . . . . . . . . . . .
9
1.3.
Ti¶u chu©n tèi ÷u . . . . . . . . . . . . . . . . . . . . . .
10
1.4.
Thuªt to¡n gi£i . . . . . . . . . . . . . . . . . . . . . . .
10
1.5.
V½ dö minh håa . . . . . . . . . . . . . . . . . . . . . . .
11
Ch÷ìng 2. BI TON VN TI VÎI L×ÑNG CUNG BÀ
CHN D×ÎI
18
2.1.
Nëi dung b i to¡n . . . . . . . . . . . . . . . . . . . . . .
18
2.2.
B i to¡n t÷ìng ÷ìng v t½nh ch§t
. . . . . . . . . . . .
21
2.3.
Thuªt to¡n gi£i . . . . . . . . . . . . . . . . . . . . . . .
25
2.4.
V½ dö minh håa . . . . . . . . . . . . . . . . . . . . . . .
28
Ch÷ìng 3. BI TON VN TI VÎI L×ÑNG CUNG BÀ
CHN
32
3.1.
Nëi dung b i to¡n . . . . . . . . . . . . . . . . . . . . . .
32
3.2.
T½nh ch§t nghi»m cõa b i to¡n
. . . . . . . . . . . . . .
34
3.3.
Thuªt to¡n gi£i . . . . . . . . . . . . . . . . . . . . . . .
36
3.4.
V½ dö minh håa . . . . . . . . . . . . . . . . . . . . . . .
40
3.5.
Tr÷íng hñp têng qu¡t
. . . . . . . . . . . . . . . . . . .
42
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
. . . . . . . . . . . . . . . . . . . . . .
50
K¸t luªn
T i li»u tham kh£o
Soá hoùa bôûi trung taâm hoïc lieäu
http://www.lrc-tnu.edu.vn/
2
LÍI NÂI U
Mæ h¼nh b i to¡n vªn t£i cê iºn vîi l÷ñng cung ð c¡c nìi giao h ng
(gåi l c¡c tr¤m ph¡t) v l÷ñng c¦u ð c¡c nìi nhªn h ng (gåi l c¡c tr¤m
thu) ành tr÷îc ¢ r§t quen thuëc trong lþ thuy¸t tèi ÷u tuy¸n t½nh. B i
to¡n vªn t£i d¤ng n y câ nhi·u ùng döng rëng r¢i trong thüc ti¹n v ¢
÷ñc nhi·u ng÷íi quan t¥m nghi¶n cùu v ùng döng (xem [4], [5]).
Mët mð rëng tü nhi¶n cõa b i to¡n vªn t£i l khæng qui ành tr÷îc
l÷ñng cung cõa c¡c tr¤m ph¡t v l÷ñng c¦u cõa tr¤m thu m cho ph²p
l÷ñng cung cõa méi tr¤m ph¡t hay/v l÷ñng c¦u cõa méi tr¤m thu câ
thº thay êi trong mët kho£ng cho tr÷îc. Khi â ta g°p b i to¡n vªn
t£i vîi r ng buëc hai ph½a v· l÷ñng cung (cõa c¡c tr¤m ph¡t) v l÷ñng
c¦u (cõa c¡c tr¤m thu). Mæ h¼nh mð rëng n y n£y sinh tø mët sè ùng
döng, trong â câ v§n · i·u h nh m¤ng xe buþt ð c¡c th nh phè.
B¬ng c¡ch dòng kÿ thuªt th¶m ©n sè phö, ta câ thº ÷a b i to¡n vªn
t£i vîi r ng buëc hai ph½a èi vîi l÷ñng cung (c¦u) v· b i to¡n vªn t£i
cê iºn vîi mët sè bi¸n câ r ng buëc cªn tr¶n, tùc l qui v· b i to¡n
vªn t£i câ h¤n ch¸ kh£ n«ng l÷u thæng v do â câ thº ¡p döng ph÷ìng
ph¡p th¸ và ¢ bi¸t º gi£i b i to¡n.
Luªn v«n n y · cªp tîi b i to¡n vªn t£i câ h¤n ch¸ kh£ n«ng l÷u
thæng, tr¼nh b y thuªt to¡n th¸ và gi£i b i to¡n v ùng döng v o xû lþ
b i to¡n vªn t£i vîi r ng buëc hai ph½a trong hai tr÷íng hñp: a) l÷ñng
cung (hay c¦u) bà ch°n d÷îi bði mët sè khæng ¥m; b) l÷ñng cung (hay
c¦u) bà ch°n (c£ tr¶n v d÷îi). Tr÷íng hñp khi c£ l÷ñng cung v l÷ñng
c¦u ·u thay êi công s³ ÷ñc · cªp tîi.
Luªn v«n gçm líi nâi ¦u, ba ch÷ìng, k¸t luªn v danh möc t i li»u
tham kh£o.
Ch÷ìng 1 vîi ti¶u · "B i to¡n vªn t£i câ h¤n ch¸ kh£ n«ng l÷u
Soá hoùa bôûi trung taâm hoïc lieäu
http://www.lrc-tnu.edu.vn/
3
thæng" tr¼nh b y nëi dung v c¡c t½nh ch§t cõa b i to¡n vªn t£i, trong
â l÷ñng h ng vªn chuyºn tø méi tr¤m ph¡t ¸n méi tr¤m thu khæng
÷ñc v÷ñt qu¡ mët mùc giîi h¤n qui ành tr÷îc (do n«ng lüc ph÷ìng ti»n
vªn chuyºn câ h¤n ho°c do n«ng lüc c¦u ÷íng tr¶n tuy¸n vªn chuyºn
â bà h¤n ch¸ ...). Ti¸p â, · cªp tîi ph÷ìng ph¡p t¼m ph÷ìng ¡n cüc
bi¶n ban ¦u cõa b i to¡n. Sau â, tr¼nh b y cì sð lþ luªn v nëi dung
thuªt to¡n th¸ và (mët bi¸n thº cõa thuªt to¡n ìn h¼nh xû lþ b i to¡n
câ bi¸n bà ch°n tr¶n) gi£i b i to¡n. Cuèi ch÷ìng n¶u ra v½ dö sè minh
håa thuªt to¡n gi£i ¢ tr¼nh b y. C¡c ki¸n thùc ð ch÷ìng n y s³ c¦n ¸n
ð c¡c ch÷ìng sau º xû lþ v gi£i b i to¡n vªn t£i vîi r ng buëc hai ph½a.
Ch÷ìng 2 vîi ti¶u · "B i to¡n vªn t£i vîi l÷ñng cung bà ch°n d÷îi"
x²t b i to¡n vªn t£i, trong â gi£ thi¸t l÷ñng cung cõa c¡c tr¤m ph¡t
khæng qui ành tr÷îc m ch¿ bà ch°n d÷îi (lîn hìn mët mùc tèi thiºu
n o â, th÷íng l sè d÷ìng), cán l÷ñng c¦u cõa c¡c tr¤m thu ¢ bi¸t
tr÷îc. N¶u mæ h¼nh to¡n håc cõa b i to¡n v n¶u c¡ch ÷a v· b i to¡n
vªn t£i câ h¤n ch¸ kh£ n«ng l÷u thæng. Sau â tr¼nh b y ti¶u chu©n tèi
÷u v thuªt to¡n gi£i b i to¡n. Cuèi ch÷ìng n¶u v½ dö sè minh håa thuªt
to¡n ¢ tr¼nh b y.
Ch÷ìng 3 vîi ti¶u · "B i to¡n vªn t£i vîi l÷ñng cung bà ch°n" x²t
b i to¡n vªn t£i, trong â gi£ thi¸t l÷ñng cung cõa c¡c tr¤m ph¡t khæng
qui ành tr÷îc m thay êi trong mët kho£ng cho tr÷îc, tùc l l÷ñng
cung bà ch°n (c£ tr¶n v d÷îi), cán l÷ñng c¦u cõa c¡c tr¤m thu ¢ bi¸t
tr÷îc. B i to¡n x²t ð ¥y mð rëng hìn æi chót so vîi b i to¡n x²t ð
ch÷ìng 2 v do â c¡ch xû lþ công phùc t¤p hìn. N¶u mæ h¼nh to¡n
håc cõa b i to¡n v n¶u c¡ch ÷a v· b i to¡n vªn t£i câ h¤n ch¸ kh£
n«ng l÷u thæng. Sau â tr¼nh b y ti¶u chu©n tèi ÷u v thuªt to¡n gi£i
b i to¡n. Cuèi ch÷ìng n¶u v½ dö sè minh håa thuªt to¡n gi£i.
Do thíi gian v ki¸n thùc cán h¤n ch¸ n¶n chc chn luªn v«n cán câ
nhúng sai sât nh§t ành, k½nh mong quþ th¦y cæ v c¡c b¤n âng gâp þ
ki¸n º t¡c gi£ ti¸p töc ho n thi»n luªn v«n n y.
Nh¥n dàp n y, t¡c gi£ xin b y tä láng bi¸t ìn s¥u sc ¸n Th¦y h÷îng
Soá hoùa bôûi trung taâm hoïc lieäu
http://www.lrc-tnu.edu.vn/
4
d¨n GS - TS Tr¦n Vô Thi»u ¢ tªn t¼nh h÷îng d¨n v gióp ï tæi trong
suèt qu¡ tr¼nh l m luªn v«n.
T¡c gi£ xin gûi tîi c¡c Th¦y, cæ ð Vi»n To¡n håc, c¡c Th¦y, cæ khoa
To¡n, pháng o t¤o sau ¤i håc tr÷íng ¤i håc Khoa håc- ¤i håc
Th¡i Nguy¶n công nh÷ c¡c Th¦y cæ tham gia gi£ng d¤y khâa Cao håc
2011 - 2013 líi c£m ìn s¥u sc v· cæng lao gi£ng d¤y v t¤o måi i·u
ki»n thuªn lñi cho t¡c gi£ trong suèt qu¡ tr¼nh håc tªp t¤i tr÷íng.
T¡c gi£ công xin ch¥n th nh c£m ìn Sð Gi¡o döc v o t¤o t¿nh
H Giang, Ban gi¡m hi»u, c¡c tê chùc o n thº, tê chuy¶n mæn, nhâm
To¡n tr÷íng THPT Li¶n Hi»p còng b¤n b± çng nghi»p v gia ¼nh ¢
t¤o måi i·u ki»n gióp ï, ëng vi¶n t¡c gi£ ho n th nh luªn v«n n y.
Th¡i Nguy¶n, ng y 01 th¡ng 8 n«m 2013
T¡c gi£
Ph¤m B¡ T¼nh
Soá hoùa bôûi trung taâm hoïc lieäu
http://www.lrc-tnu.edu.vn/
5
Ch֓ng 1
BI TON VN TI CÂ KH
NNG L×U THÆNG HN CH
Ch÷ìng n y · cªp tîi b i to¡n vªn t£i câ kh£ n«ng l÷u thæng h¤n
ch¸. N¶u mæ h¼nh v c¡c t½nh ch§t cõa b i to¡n. Ti¸p â, n¶u ph÷ìng
ph¡p t¼m ph÷ìng ¡n cüc bi¶n ban ¦u cõa b i to¡n. Sau â, tr¼nh b y
cì sð lþ luªn v nëi dung thuªt to¡n th¸ và (mët bi¸n thº cõa thuªt to¡n
ìn h¼nh) gi£i b i to¡n. Cuèi ch÷ìng n¶u v½ dö sè minh håa thuªt to¡n
gi£i. Nëi dung cõa ch÷ìng ÷ñc tham kh£o chõ y¸u tø c¡c t i li»u [1],
[4] v [5].
1.1. B i to¡n v t½nh ch§t
Gi£ sû c¦n vªn chuyºn mët lo¤i h ng (xi m«ng ch¯ng h¤n) tø m kho
chùa h ng (gåi l c¡c tr¤m ph¡t) tîi n hë ti¶u thö (gåi l c¡c tr¤m thu).
ai > 0 (i =
thu j l bj > 0
Cho bi¸t l÷ñng h ng câ (gåi l l÷ñng cung) ð tr¤m ph¡t i l
1, 2, ... , m) v l÷ñng h ng c¦n (gåi l l÷ñng c¦u) ð tr¤m
(j = 1, 2, ... , n). Chi ph½ vªn chuyºn mët ìn và h ng tø tr¤m ph¡t i
tîi tr¤m thu j l
cij ≥ 0.
Ngo i ra, do i·u ki»n v· ÷íng s¡ ho°c h¤n
ch¸ v· ph÷ìng ti»n vªn chuyºn n¶n tø i tîi j ch¿ ÷ñc vªn chuyºn tèi a
dij ≥ 0
ìn và h ng (dij gåi l kh£ n«ng l÷u thæng tr¶n tuy¸n i - j). V§n
· l c¦n vªn chuyºn bao nhi¶u ìn và h ng tø méi tr¤m ph¡t tîi méi
tr¤m thu sao cho khæng v÷ñt qu¡ kh£ n«ng l÷u thæng tr¶n méi tuy¸n,
måi tr¤m ph¡t giao h¸t h ng, måi tr¤m thu nhªn õ h ng v têng chi
ph½ vªn chuyºn l nhä nh§t?
Mæ h¼nh to¡n håc cõa b i to¡n vªn t£i vîi kh£ n«ng l÷u thæng h¤n
Soá hoùa bôûi trung taâm hoïc lieäu
http://www.lrc-tnu.edu.vn/
6
ch¸ câ d¤ng nh÷ sau (xij l l÷ñng h ng vªn chuyºn c¦n t¼m):
m X
n
X
cij xij → min
(cüc tiºu têng chi ph½ c÷îc vªn chuyºn)
(1.1)
i=1 j=1
vîi c¡c i·u ki»n
n
X
j=1
m
X
xij = ai , i = 1, 2, ..., m (måi
xij = bj, j = 1, 2, ..., n (måi
tr¤m ph¡t giao h¸t h ng)
tr¤m thu nhªn õ h ng)
(1.2)
(1.3)
i=1
0 ≤ xij ≤ dij , i = 1, 2, ..., m, j = 1, 2, ..., n
(l÷ñng h ng vªn chuyºn khæng ¥m v khæng v÷ñt qu¡
kh£ n«ng l÷u thæng
(1.4)
dij )
Gi£ thi¸t b i to¡n (1.1) - (1.4) thäa m¢n i·u ki»n c¥n b¬ng cung c¦u:
m
X
ai =
i=1
n
X
bj
(têng cung b¬ng têng c¦u).
(1.5)
j=1
xij ≥ 0 suy ra xij ≤ min {ai , bj } vîi måi i, j
n¶n d¹ d ng th§y r¬ng n¸u måi kh£ n«ng l÷u thæng dij ≥ min {ai , bj } th¼
÷ìng nhi¶n câ thº bä i·u ki»n xij ≤ dij v khi â (1.1) - (1.5) trð th nh
Tø i·u ki»n (1.2), (1.3) v
b i to¡n vªn t£i thæng th÷íng (khæng h¤n ch¸ kh£ n«ng l÷u thæng). Ch¿
g°p khâ kh«n khi câ nhúng
dij ≤ min {ai , bj }.
Ch÷ìng n y s³ x²t b i
to¡n vªn t£i trong tr÷íng hñp n y.
R§t ti¸c khæng câ i·u ki»n c¦n v õ º b i to¡n (1.1) - (1.5) gi£i
÷ñc, nh÷ trong b i to¡n vªn t£i thæng th÷íng, m ch¿ câ i·u ki»n c¦n
v i·u ki»n õ ri¶ng.
D¹ th§y r¬ng mët i·u ki»n õ º b i to¡n (1.1) - (1.5) gi£i ÷ñc l
dij ≥ min {ai , bj }
vîi måi i,j.
(1.6)
º ÷a ra i·u ki»n c¦n cho (1.1) - (1.5) gi£i ÷ñc, khæng gi£m têng
qu¡t ta câ thº gi£ thi¸t
dij ≤ min {ai , bj }
Soá hoùa bôûi trung taâm hoïc lieäu
vîi måi i v j, bði v¼ vîi
http://www.lrc-tnu.edu.vn/
7
dij ≥ min {ai , bj }
th¼ r ng buëc
xij ≤ dij
trð n¶n khæng c¦n thi¸t. B¬ng
c¡ch cëng (1.4) theo måi j v so s¡nh vîi (1.2); sau â cëng (1.4) theo
måi i v so s¡nh vîi (1.3) ta nhªn ÷ñc mët
i·u ki»n c¦n
º b i to¡n
(1.1) - (1.5) gi£i ÷ñc l
ai ≤
n
X
dij , ∀i = 1, ..., m v bj ≤
j=1
m
X
dij , ∀j = 1, ..., n.
(1.7)
i=1
N¸u vi ph¤m (1.7) (tùc
dij
khæng õ lîn so vîi nhu c¦u vªn chuyºn)
th¼ dò câ i·u ki»n c¥n b¬ng cung c¦u (1.5), b i to¡n v¨n s³ khæng câ
ph÷ìng ¡n thäa m¢n (1.2) - (1.4), do â b i to¡n s³ khæng gi£i ÷ñc.
Trong thüc h nh, º b i to¡n gi£i ÷ñc th÷íng ng÷íi ta ph£i i·u ch¿nh
dij
d¦n c¡c h» sè
mët c¡ch th½ch hñp.
Tuy nhi¶n, i·u ki»n (1.7) khæng l i·u ki»n õ º (1.1) - (1.5) gi£i
÷ñc, nh÷ ch¿ ra ð v½ dö ìn gi£n sau.
V½ dö 1.1
. X²t b i to¡n vªn t£i vîi m = 3 tr¤m ph¡t v n = 3 tr¤m
thu. L÷ñng cung cõa c¡c tr¤m ph¡t v l÷ñng c¦u cõa c¡c tr¤m thu l¦n
l÷ñt l 1, 3 v 4. Kh£ n«ng l÷u thæng
dij ≤ min {ai , bj }
(i, j = 1, 2, 3)
÷ñc cho trong B£ng 1.1.
Rã r ng · (1.2) thäa m¢n vîi i = 2, 3 ph£i câ
xij = dij
vîi måi i = 2,
3 v måi j = 1, 2, 3. Nh÷ng khi â s³ vi ph¤m r ng buëc (1.3) vîi j = 1.
Vªy khæng thº câ
xij
thäa m¢n (1.1) - (1.4) vîi måi i, j = 1, 2, 3 v
b i to¡n (1.1) - (1.5) l khæng gi£i ÷ñc.
Kþ hi»u
Aij ∈ Rm+n
l v²ctì h» sè cõa bi¸n
xij .
D¹ th§y r¬ng v²ctì
n y câ hai th nh ph¦n b¬ng 1 t¤i h ng i v h ng m + j, cán måi th nh
ph¦n kh¡c b¬ng 0.
Soá hoùa bôûi trung taâm hoïc lieäu
http://www.lrc-tnu.edu.vn/
8
º cho gån, ta ghi l¤i dú li»u cõa b i to¡n d÷îi d¤ng mët b£ng chú
nhªt, gåi l
b£ng vªn t£i
(B£ng 1.2). B£ng gçm m h ng (i = 1, ... , m)
v n cët (j = 1, ... , n). Ché giao nhau ð h ng i, cët j gåi l æ (i, j). Méi
h ng t÷ìng ùng vîi mët tr¤m ph¡t, méi cët t÷ìng ùng vîi mët tr¤m
thu. Sè ghi ð ¦u méi h ng l l÷ñng cung, sè ghi ð ¦u méi cët l l÷ñng
c¦u. Chi ph½ vªn chuyºn
dij
cij
ghi ð gâc tr¶n b¶n tr¡i, kh£ n«ng l÷u thæng
ghi ð gâc tr¶n b¶n ph£i, l÷ñng h ng vªn chuyºn
xij
s³ ghi ð giúa h ng
d÷îi cõa æ (i, j). Æ (i, j) biºu thà tuy¸n vªn chuyºn tø tr¤m ph¡t i tîi
tr¤m thu j. °t
cij = ∞
ho°c
dij = 0
n¸u khæng thº vªn chuyºn h ng tø
i ¸n j.
Sau ¥y nhc l¤i mët sè kh¡i ni»m quen dòng. Ma trªn
x = {xij }m×n
ph÷ìng ¡n cõa b i to¡n (1.1) - (1.5). Mët
ph÷ìng ¡n ¤t cüc tiºu (1.1) gåi l ph÷ìng ¡n tèi ÷u hay líi gi£i. Ph÷ìng
¡n x gåi l ph÷ìng ¡n cüc bi¶n n¸u c¡c v²ctì Aij ùng vîi xij thäa m¢n 0 <
xij < dij l ëc lªp tuy¸n t½nh hay tªp hñp æ G = {(i, j) : 0 < xij < dij }
khæng t¤o th nh chu tr¼nh. Ph÷ìng ¡n cüc bi¶n x gåi l khæng suy bi¸n
n¸u G câ óng m + n - 1 æ, tr¡i l¤i x gåi l suy bi¸n.
thäa m¢n (1.2) - (1.4) gåi l mët
Soá hoùa bôûi trung taâm hoïc lieäu
http://www.lrc-tnu.edu.vn/
9
1.2. Ph÷ìng ¡n cüc bi¶n ban ¦u
V½ dö 1.2
. T¼m ph÷ìng ¡n cüc bi¶n ban ¦u cho b i to¡n vªn t£i vîi
dú li»u cho trong B£ng 1.3.
• H ng thù nh§t: Bt ¦u tø æ (1, 1), ta ph¥n v o æ n y l÷ñng h ng:
x11 = min {a1 , b1 , d11 } = min {40, 25, 15} = 15 = d11 (15 tæ ªm, m u
ä).
Ti¸p â, ph¥n v o æ (1, 2) l÷ñng h ng:
x12 = min {a1 − 15, b2 , d12 } = min {25, 30, 20} = 20 = d12
(20 tæ ªm,
m u ä).
Cuèi còng, ph¥n v o æ (1, 3) l÷ñng h ng:
x13 = min {a1 − 15 − 20, b3 , d13 } = min {5, 40, 25} = 5 < d13
(æ cì sð
"•").
•
•
H ng thù hai: L¦n l÷ñt ph¥n h ng v o c¡c æ (2. 1), (2. 2) v (2. 3).
H ng thù ba: L¦n l÷ñt ph¥n h ng v o c¡c æ (3. 3) v (3. 4).
°t
xij = 0
cho t§t c£ c¡c æ cán l¤i (khæng ÷ñc ph¥n phèi h ng).
K¸t qu£ l ta ÷ñc ph÷ìng ¡n cüc bi¶n (gçm 6 æ cì sð "•") ghi ð B£ng
1.3.
Trong æ (i, j): sè ghi ð gâc tr¶n b¶n tr¡i l
ph£i l
dij
v sè ghi ð h ng d÷îi l
xij
cij ,
sè ghi ð gâc tr¶n b¶n
(sè in ªm m u ä ch¿
Æ cì sð ¡nh d§u "•".
Soá hoùa bôûi trung taâm hoïc lieäu
http://www.lrc-tnu.edu.vn/
xij = dij ).
10
1.3. Ti¶u chu©n tèi ÷u
Gi£ sû
x0 = x0ij m×n
l mët ph÷ìng ¡n cüc bi¶n cõa b i to¡n (1.1) -
G = (i, j) : 0 ≤ x0ij ≤ dij gçm m + n 1 æ khæng chùa chu tr¼nh. Gi£ sû ui , vj l c¡c th¸ và h ng, cët thäa m¢n
h» ph÷ìng tr¼nh ui +vj = cij vîi måi (i, j) ∈ G. Kþ hi»u ∆ij = ui +vj −cij
vîi måi (i, j) ∈
/ G (∆ij = 0, ∀ (i, j) ∈ G). ành lþ sau cho ta mët d§u
0
hi»u nhªn bi¸t khi n o x l ph÷ìng ¡n tèi ÷u.
0
0
(D§u hi»u tèi ÷u). Ph÷ìng ¡n x =
xij m×n l tèi
÷u cõa (1.1) - (1.5) khi ∆ij ≤ 0 vîi måi (i, j) ∈
/ G, x0ij = 0 v ∆ij ≥
0 vîi måi (i, j) ∈
/ G, x0ij = dij .
(1.5) t÷ìng ùng vîi tªp æ cì sð
ành lþ 1.1
1.4. Thuªt to¡n gi£i
B֔c 0
(Khði
t¤o).
X¥y
düng
ph֓ng
¡n
cüc
bi¶n
ban
¦u
x0 = x0ij m×n . Tªp æ chån cì sð t÷ìng ùng vîi x0 l G0 =
(i, j) : 0 ≤ x0ij ≤ dij gçm (m + n - 1) ph¦n tû v khæng chùa chu tr¼nh,
ngh¾a l h» v²ctì {Aij : (i, j) ∈ G0 } ëc lªp tuy¸n t½nh. °t ch¿ sè váng
l°p k = 0.
B֔c 1
ùng vîi
. T½nh c¡c th¸ và
Gk ,
ui
(i = 1, ... , m) v
vj
(j = 1, ... , n) t֓ng
b¬ng c¡ch gi£i h» ph÷ìng tr¼nh (d¤ng tam gi¡c):
ui + vj = cij , ∀ (i, j) ∈ Gk .
B֔c 2
câ
. T½nh c¡c ÷îc l÷ñng
∆ij = 0, ∀ (i, j) ∈ Gk )
B֔c 3
∆ij = ui + vj − cij , ∀ (i, j) ∈
/ Gk
(Ta luæn
.
. (Kiºm tra i·u ki»n tèi ÷u)
∆ij ≤ 0 vîi måi (i, j) ∈
/ Gk , xkij = 0 v ∆ij ≥ 0 vîi måi (i, j) ∈
/
Gk , xkij = dij th¼ døng thuªt to¡n: xk l ph÷ìng ¡n tèi ÷u ( ành lþ 1.1).
N¸u
N¸u tr¡i l¤i, chuyºn sang B÷îc 4.
B֔c 4
. ( i·u ch¿nh ph÷ìng ¡n)
4a) Æ i·u ch¿nh (r,s) l æ ¤t max trong biºu thùc
∆ = max ∆ij
vîi
(i, j) ∈
/ Gk , xkij = 0, −∆ij
Soá hoùa bôûi trung taâm hoïc lieäu
vîi
(i, j) ∈
/ Gk , xkij = dij > 0.
http://www.lrc-tnu.edu.vn/
11
4b) Lªp chu tr¼nh C t¤o n¶n bði æ (r, s) vîi c¡c æ thuëc
h¤n b¬ng c¡ch lo¤i d¦n c¡c æ treo cõa
Gk ∪ {(r, s)}
Gk
(ch¯ng
).
C1 (tªp æ l´) v C2
(r, s) ∈ C2 n¸u xkrs =
4c) Ph¥n ho¤ch tªp C th nh hai tªp con ríi nhau
(tªp æ ch®n) vîi qui ÷îc
(r, s) ∈ C1
n¸u
xkrs = 0 v
drs .
4d) X¡c ành l÷ñng i·u ch¿nh h theo cæng thùc
h = min dij − xkij
(i, j) ∈ C1 , xkij
vîi
vîi
(i, j) ∈ C2 ≥ 0.
Æ (p, q) ¤t min tr÷íng hñp biºu thùc tr¶n s³ bà lo¤i.
B֔c 5
. X¥y düng ph÷ìng ¡n cüc bi¶n mîi theo cæng thùc
xk+1
ij
k
xij + h khi (i, j) ∈ C1 ,
xkij − h khi (i, j) ∈ C2 ,
=
k
xij
khi (i, j) ∈
/ C.
v tªp æ chån t÷ìng ùng
T«ng
k ←k+1
Gk+1 = (Gk \ {(p, q)}) ∪ {(r, s)}.
v trð l¤i B÷îc 1 thüc hi»n váng l°p k mîi.
1.5. V½ dö minh håa
V½ dö 1.3
. Gi£i b i to¡n vªn t£i câ kh£ n«ng l÷u thæng h¤n ch¸ vîi
v²ctì cung a, v²ctì c¦u b, ma trªn c÷îc ph½
n«ng l÷u thæng
D = {dij }3×4
C = {cij }3×4
v ma trªn kh£
nh÷ sau.
a = (40, 50, 60)T , b = (25, 30, 40, 55)T
2 10 12 2
15 20 25 30
C = 5 1 2 10 , D = 20 25 30 30
20 3 10 15
15 25 35 55
Gi£i. V½ dö n y câ m = 3 tr¤m ph¡t, n = 4 tr¤m thu v thäa m¢n
i·u ki»n c¥n b¬ng cung c¦u (40 + 50 + 60 = 25 + 30 + 40 + 55). Xu§t
ph¡t tø ph÷ìng ¡n cüc bi¶n ban ¦u
G0
x0
cho ð B£ng 1.3 vîi tªp æ cì sð
= (1, 3), (2, 1), (2, 2), (2, 3). (3, 3), (3, 4), gçm 6 æ khæng chùa chu
tr¼nh v gi¡ trà h m möc ti¶u
Soá hoùa bôûi trung taâm hoïc lieäu
f x0 = 1285.
http://www.lrc-tnu.edu.vn/
12
Váng l°p 0
B֔c 1
.
. C¡c th¸ và t÷ìng ùng vîi
x0 :
u0 = (0, −10, −2) , v 0 = (15, 11, 12, 17)
B֔c 2
∆ij = ui + vj − cij ghi ð ma trªn ∆0 d÷îi
15 20 5 0
13 1 0 15
x0 = 10 10 30 0 , ∆0 = 0 0 0 −3
0 0 5 55
−7 6 0 0
. C¡c sè
B֔c 3
x0 ch÷a tèi ÷u v¼ cán ∆14 = 15 > 0 vîi (1, 4) ∈
/
= 6 > 0 vîi (3, 2) ∈
/ G0 , x32 = 0 (hai sè d÷ìng g¤ch
. Ph÷ìng ¡n
G0 , x14 = 0
v
ch¥n trong
∆0 ).
B֔c 4
¥y:
∆32
.
∆14 = max {∆14 , ∆32 } = 15 > 0.
b) Chu tr¼nh i·u ch¿nh gçm 4 æ C = {(1, 4), (3, 4), (3, 3), (1, 3)}
c) C¡c æ l´ C1 = {(1, 4), (3, 3)} v c¡c æ ch®n C2 = {(3, 4), (1, 3)}.
d14 − x014 = 30, x034 = 55,
d) L÷ñng i·u ch¿nh
h = min
= 5.
d33 − x033 = 30, x013 = 5
a) Æ i·u ch¿nh (r, s) = (1, 4) vîi
Æ lo¤i (p, q) = (1. 3).
B֔c 5
x1 (ghi ð
G1 = {(1, 4) , (2, 1) , (2, 2) , (2, 3) . (3, 3) , (3, 4)}
f x0 = 1258.
. Ph÷ìng ¡n cüc bi¶n mîi
Váng l°p 1
B֔c 1
d÷îi) vîi tªp æ cì sð
v
f x1
= 1210 <
.
. C¡c th¸ và t÷ìng ùng vîi
x1 :
u1 = (0, 5, 13) , v 1 = (0, −4, −3, −3, 2) .
B֔c 2
∆ij = ui + vj − cij ghi ð ma trªn ∆1 d÷îi ¥y:
15 20 0 5
−2 −14 −15 0
x1 = 10 10 30 0 , ∆1 = 0
0
0 −3
0 0 10 50
−7 6
0
0
. C¡c sè
B֔c 3
. Ph÷ìng ¡n
G1 , x132 = 0
x1
(sè d÷ìng g¤ch ch¥n trong
Soá hoùa bôûi trung taâm hoïc lieäu
∆32 = 6 > 0
∆11 = −2 < 0
ch÷a tèi ÷u v¼ cán
∆1 ),
http://www.lrc-tnu.edu.vn/
vîi
vîi
(3, 2) ∈
/
(1, 1) ∈
/
13
G1 , x111 = d11
v
g¤ch ngang tr¶n
B֔c 4
∆12 = −14 < 0
trong ∆1 ).
vîi
(1, 2) ∈
/ G1 , x112 = d12
(hai sè ¥m
.
a) Æ i·u ch¿nh (r, s) = (1, 2) vîi:
−∆12 = max {−∆11 = 2, −∆12 = 14, ∆32 = 6} = 14 > 0.
b) Chu tr¼nh i·u ch¿nh gçm 6 æ:
C = {(1, 2), (1, 4), (3, 4), (3, 3), (2, 3), (2, 2)} .
c)
C¡c
æ
C1 = {(1, 4), (3, 3), (2, 2)},
l´
c¡c
æ
ch®n
C2
=
= 15.
Æ
{(1, 2), (3, 4), (2, 3)}.
d) L÷ñng i·u ch¿nh
h = min
x112 = 20, d14 − x114 = 25, x134 = 50,
d33 − x133 = 25, x123 = 30, d22 − x122 = 15
lo¤i (p, q) = (2. 2).
B֔c 5
x2 (ghi ð d÷îi) vîi tªp æ cì sð
G2 = {(1, 2), (1, 4), (2, 1), (2, 3).(3, 3), (3, 4)} v f (x2 ) = 1000 < f (x1 ) =
. Ph÷ìng ¡n cüc bi¶n mîi
1210.
Váng l°p 2
B֔c 1
.
. C¡c th¸ và t÷ìng ùng vîi
x2 :
u2 = (0, 5, 13) , v 2 = (0, 10, −3, 2) .
B֔c 2
∆ij = ui + vj − cij ghi ð ma trªn ∆2 d÷îi ¥y:
15 5 0 20
−2 0 −15 0
x2 = 10 25 15 0 , ∆2 = 0 9
0 −3
0 0 25 35
−7 20 0
0
. C¡c sè
B֔c 3
G1 , x232
G2 , x211
x2
∆32 = 20 > 0 vîi (3, 2) ∈
/
= 0 (sè d÷ìng g¤ch ch¥n trong ∆2 ) , v ∆11 = −2 < 0 vîi (1, 1) ∈
/
= d11 (sè ¥m g¤ch ngang tr¶n trong ∆2 ).
. Ph÷ìng ¡n
Soá hoùa bôûi trung taâm hoïc lieäu
ch÷a tèi ÷u v¼ cán
http://www.lrc-tnu.edu.vn/
14
B֔c 4
.
a) Æ i·u ch¿nh (r, s) = (3, 2) vîi:
∆32 = max {−∆11 = 2, ∆32 = 20} = 20 > 0.
b) Chu tr¼nh i·u ch¿nh gçm 4 æ:
C = {(3, 2), (1, 2), (1, 4), (3, 4)} .
c) C¡c æ l´
C1 = {(3, 2), (1, 4)},
c¡c æ ch®n
C2 = {(1, 2), (3, 4)}.
d) L÷ñng i·u ch¿nh
h = min d32 − x232 = 25, x212 = 5, d14 − x214 = 10, x234 = 35 = 5.
Æ
lo¤i (p, q) = (1, 2).
B֔c 5
x3 (ghi ð d÷îi) vîi tªp æ cì
G3 = {(1, 4), (2, 1), (2, 3), (3, 2).(3, 3), (3, 4)} v f (x3 ) = 900 < f (x2 )
. Ph÷ìng ¡n cüc bi¶n mîi
sð
=
1000.
Váng l°p 3.
B֔c 1
. C¡c th¸ và t÷ìng ùng vîi
x3 :
u3 = (0, 5, 13) , v 3 = (0, −10, −3, 2) .
B֔c 2
∆ij = ui + vj − cij ghi ð ma trªn ∆3 d÷îi ¥y:
15 0 0 25
−2 −20 −15 0
x3 = 10 25 15 0 , ∆3 = 0 −6
0 −3 .
0 5 25 30
−7 0
0
0
. C¡c sè
B֔c 3
x3 ch÷a tèi ÷u v¼ cán ∆11 = −2 < 0 vîi (1, 2) ∈
/
3
= −6 < 0 vîi (2, 2) ∈
/ G3 , x22 = d22 (hai sè ¥m g¤ch
. Ph÷ìng ¡n
G3 , x311 = d11
ngang tr¶n
B֔c 4
∆22
trong ∆3 ).
v
.
a) Æ i·u ch¿nh (r, s) = (2, 2) vîi:
−∆22 = max {−∆11 = 2, −∆22 = 6} = 6.
C = {(2, 2), (2, 3), (3, 3), (3, 2)}.
C1 = {(2, 3), (3, 2)}, c¡c æ ch®n C2 = {(2, 2), (3, 3)}.
b) Chu tr¼nh i·u ch¿nh gçm 6 æ
c) C¡c æ l´
Soá hoùa bôûi trung taâm hoïc lieäu
http://www.lrc-tnu.edu.vn/
15
d) L÷ñng i·u ch¿nh:
h = min x322 = 25, d23 − x323 = 15, x333 = 25, d32 − x332 = 20 = 15.
Æ lo¤i (p, q) = (2. 3).
B֔c 5
x4 (ghi ð d÷îi)
G4 = {(1, 4), (2, 1), (2, 2), (3, 2).(3, 3), (3, 4)} v f (x4 ) =
. Ph÷ìng ¡n cüc bi¶n mîi
vîi tªp æ cì sð
810 <
f (x3 )
=
900.
Váng l°p 4.
B֔c 1
. C¡c th¸ và t÷ìng ùng vîi
x4 :
u4 = (0, 11, 13) , v 4 = (−6, −10, −3, 2)
B֔c 2
∆ij = ui + vj − cij ghi ð ma trªn ∆4 d÷îi ¥y:
15 0 0 25
−8 −20 −15 0
x4 = 10 10 30 0 , ∆4 = 0
0
6 −3 .
0 20 10 30
−13 0
0
0
. C¡c sè
B֔c 3
. Ph÷ìng ¡n
G4 , x411 = d11
B֔c 4
x4
∆11 = −8 < 0 vîi (1, 1) ∈
/
∆4 ).
ch÷a tèi ÷u v¼ cán
(sè ¥m g¤ch ngang tr¶n trong
.
a) Æ i·u ch¿nh (r, s) = (1, 1) vîi
−∆11 = 8 > 0
b) Chu tr¼nh i·u ch¿nh gçm 6 æ:
C = {(1, 1), (1, 4), (3, 4), (3, 2), (2, 2), (2, 1)} .
c)
C¡c
æ
l´
C1 = {(1, 4), (3, 2), (2, 1)},
c¡c
æ
ch®n
C2 = {(1, 1), (3, 4), (2, 2)}.
d) L÷ñng i·u ch¿nh
h = min
x411 = 15, d14 − x414 = 5, x434 = 30,
d32 − x432 = 5, x422 = 10, d21 − x421 = 10
= 5.
Æ lo¤i
(p, q) = (1. 4).
B֔c 5
x5 (ghi ð d÷îi) vîi tªp æ cì
G5 = {(1, 1), (2, 1), (2, 2), (3, 2), (3, 3), (3, 4)} v f (x5 ) = 770 < f (x4 )
. Ph÷ìng ¡n cüc bi¶n mîi
810.
Soá hoùa bôûi trung taâm hoïc lieäu
http://www.lrc-tnu.edu.vn/
sð
=
16
Váng l°p 5.
B֔c 1
. C¡c th¸ và t÷ìng ùng vîi
x5 :
u5 = (0, 3, 5) , v 5 = (2, −2, 5, 10)
B֔c 2
∆ij = ui + vj − cij ghi ð ma trªn ∆5 d÷îi ¥y:
10 0 0 30
0 −12 −7 8
x5 = 15 5 30 0 , ∆5 = 0
0
6 3 .
0 25 10 25
−13 0
0 0
. C¡c sè
B֔c 3
. Ph÷ìng ¡n
G5 , x524 = 0
B֔c 4
x5
ch÷a tèi ÷u v¼ cán
(sè d÷ìng g¤ch ch¥n trong
∆5
∆24 = 3 > 0
vîi
(2, 4) ∈
/
).
.
∆24 = 3 > 0.
b) Chu tr¼nh i·u ch¿nh gçm 4 æ C = {(2, 4), (3, 4), (3, 2), (2, 2)}.
c) C¡c æ l´ C1 = {(2, 4), (3, 2)}, c¡c æ ch®n C2 = {(3, 4), (2, 2)}.
a) Æ i·u ch¿nh (r, s) = (2, 4) vîi
d) L÷ñng i·u ch¿nh
h = min d24 − x524 = 30, x534 = 25, d32 − x532 = 0, x522 = 5 = 0.
Æ lo¤i (p, q) = (3, 2).
B֔c 5
x6 (ghi ð d÷îi) vîi tªp æ cì
G6 = {(1, 1), (2, 1), (2, 2), (2, 4).(3, 3), (3, 4)} v f (x6 ) = f (x5 ) = 770.
. Ph÷ìng ¡n cüc bi¶n mîi
Váng l°p 6
B֔c 1
. C¡c th¸ và t÷ìng ùng vîi
sð
x6 :
u6 = (0, 3, 8) , v 6 = (2, −2, 2, 7)
B֔c 2
∆ij = ui + vj − cij ghi ð ma trªn ∆6 d÷îi ¥y:
10 0 0 30
0 −12 −10 5
x6 = 15 5 30 0 , ∆6 = 0
0
3 0 .
0 25 10 25
−10 3
0 0
. C¡c sè
B֔c 3
∆ij ≤ 0 vîi måi (i, j) ∈
/ G6 , x6ij = 0
(c¡c sè ¥m g¤ch ch¥n trong ∆6 ), ∆ij ≥ 0 vîi måi (i, j) ∈
/ G6 , x6ij = dij
(c¡c sè d÷ìng g¤ch ngang tr¶n trong ∆6 ).
opt
Vªy x
= x6 , fopt = f x6 = 770.
. Ph÷ìng ¡n
x6
Soá hoùa bôûi trung taâm hoïc lieäu
tèi ÷u v¼
http://www.lrc-tnu.edu.vn/
17
Tâm l¤i, ch÷ìng n y ¢ tr¼nh b y tâm tt c¡c k¸t qu£ v· b i to¡n
vªn t£i câ kh£ n«ng l÷u thæng h¤n ch¸: mæ h¼nh v c¡c t½nh ch§t cõa
b i to¡n, ph÷ìng ph¡p t¼m ph÷ìng ¡n cüc bi¶n ban ¦u cõa b i to¡n,
ti¶u chu©n tèi ÷u v thuªt to¡n th¸ và gi£i b i to¡n. Cuèi ch÷ìng, n¶u
v½ dö sè minh håa thuªt to¡n gi£i. Nâi chung, thuªt to¡n gi£i b i to¡n
vªn t£i câ h¤n ch¸ kh£ n«ng l÷u thæng phùc t¤p hìn æi chót so vîi b i
to¡n vªn t£i khæng h¤n ch¸ kh£ n«ng l÷u thæng.
Soá hoùa bôûi trung taâm hoïc lieäu
http://www.lrc-tnu.edu.vn/
18
Ch֓ng 2
BI TON VN TI VÎI
L×ÑNG CUNG BÀ CHN D×ÎI
Ch÷ìng n y tr¼nh b y mæ h¼nh to¡n håc cõa b i to¡n vªn t£i, trong
â l÷ñng cung cõa c¡c tr¤m ph¡t khæng qui ành tr÷îc m bà ch°n tr¶n
v d÷îi, cán l÷ñng c¦u cõa c¡c tr¤m thu ¢ bi¸t tr÷îc. Sau â x²t tr÷íng
hñp ìn gi£n khi l÷ñng cung cõa c¡c tr¤m ph¡t ch¿ bà ch°n d÷îi bði sè
khæng ¥m. N¶u c¡ch ÷a v· b i to¡n g¦n vîi b i to¡n vªn t£i thæng
th÷íng v x²t t½nh ch§t nghi»m cõa b i to¡n. Sau â tr¼nh b y ti¶u
chu©n tèi ÷u v thuªt to¡n gi£i. Cuèi ch÷ìng n¶u v½ dö sè minh håa. Nëi
dung cõa ch÷ìng ÷ñc tham kh£o chõ y¸u tø c¡c t i li»u [1], [3] v [5].
2.1. Nëi dung b i to¡n
º thuªn ti»n cho vi»c kh£o s¡t, ð ¥y ta s³ mæ t£ b i to¡n vªn t£i
vîi l÷ñng cung cõa c¡c tr¤m ph¡t bà ch°n (tr¶n v d÷îi) nh÷ sau.
Gi£ sû câ mët lo¤i h ng (ch¯ng h¤n l÷ìng thüc, xi m«ng, v.v ...) c¦n
vªn chuyºn tø m iºm cung c§p (gåi l c¡c tr¤m ph¡t), kþ hi»u i = 1, 2,
... , m, tîi n iºm ti¶u thö (gåi l c¡c tr¤m thu), j = 1, 2, ... , n. Cho bi¸t
kh£ n«ng cung c§p h ng cõa tr¤m ph¡t i thuëc kho£ng cho tr÷îc
ai l mùc
(0 ≤ ai ≤ ai )
ai
Trong â
cung tèi thiºu v
ph¡t i
, nhu c¦u ti¶u thö h ng cõa tr¤m thu j l
[ai , ai ].
l mùc cung tèi a cõa tr¤m
bj > 0
(bj cè ành) v c÷îc ph½ vªn chuyºn mët ìn và h ng tø tr¤m ph¡t i tîi
tr¤m thu j l
cij ≥ 0.
B i to¡n °t ra l h¢y t¼m mët ph÷ìng ¡n vªn chuyºn h ng tø c¡c
tr¤m ph¡t tîi c¡c tr¤m thu sao cho têng chi ph½ vªn chuyºn l nhä nh§t?
Soá hoùa bôûi trung taâm hoïc lieäu
http://www.lrc-tnu.edu.vn/
19
º £m b£o cho b i to¡n gi£i ÷ñc, ta gi£ thi¸t
m
X
ai ≤
i=1
n
X
bj ≤
j=1
m
X
ai
(2.1)
i=1
B i to¡n tr¶n câ thº di¹n t£ d÷îi d¤ng mæ h¼nh to¡n håc nh÷ sau:
m X
n
X
f (x) ≡
(P )
cij xij → min,
(2.2)
xij − xi0 = ai , i = 1, 2, ..., m,
(2.3)
xij = bj , j = 1, 2, ...,n,
(2.4)
i=1 j=1
n
X
j=1
m
X
i=1
trong â
thu j,
xij
xi0
xij ≥ 0, i = 1, ..., m, j = 1, ..., n,
(2.5)
0 ≤ xi0 ≤ ei ≡ ai − ai , i = 1, 2, ..., m,
(2.6)
biºu thà l÷ñng h ng c¦n vªn chuyºn tø tr¤m ph¡t i tîi tr¤m
l têng l÷ñng h ng chuyºn i tø tr¤m ph¡t i (tîi måi tr¤m
ai ≤ ai + xi0 ≤ ai , i =
1, 2, ..., m. V¼ th¸, i·u ki»n (2.3) câ thº vi¸t l¤i th nh ai ≤ xi1 +...+xin ≤
ai vîi måi i. Do â, (P) cán ÷ñc gåi l b i to¡n vªn t£i vîi r ng buëc
hai ph½a v· l÷ñng cung cõa c¡c tr¤m ph¡t.
thu) v÷ñt mùc cung tèi thiºu
ai .
Tø (2.6) suy ra
Kþ hi»u
s1 = a1 + a2 + ... + am (têng cung
s2 = a1 + a2 + ... + am (têng cung
d = b1 + b2 + ... + bn (têng c¦u).
tèi thiºu),
tèi a),
Trong [2] c¡c t¡c gi£ ¢ sû döng mæ h¼nh tr¶n º mæ t£ b i to¡n ph¥n
bê tèi ÷u c¡c trung t¥m i·u h nh (depot), i = 1, 2, ... , m, qu£n lþ
c¡c tuy¸n xe buþt, j = 1, 2, ... , n, nh¬m gi£m ¸n mùc th§p nh§t têng
qu¢ng ÷íng xe ch¤y khæng t£i (bi¸n
t¥m i qu£n lþ v
xij = 0
xij = 1
n¸u tuy¸n xe j do trung
n¸u tr¡i l¤i), nhí â cho ph²p ti¸t ki»m kho£ng
10% chi ph½ vªn h nh, trong â ai
v
ai
l giîi h¤n d÷îi v giîi h¤n tr¶n
cho sè tuy¸n xe buþt m trung t¥m i ÷ñc ph²p qu£n lþ, i·u ki»n (2.4)
Soá hoùa bôûi trung taâm hoïc lieäu
http://www.lrc-tnu.edu.vn/
- Xem thêm -
.PDF 
51 
42 
79 
