Bài toán vận tải có hạn chế khả năng lưu thông và ứng dụng

„I HÅC THI NGUYN

TR×ÍNG „I HÅC KHOA HÅC

Ph¤m B¡ T¼nh

B€I TON VŠN TƒI C H„N CH

KHƒ N‹NG L×U THÆNG V€ ÙNG DÖNG

Chuy¶n Ngh nh: TON ÙNG DÖNG

M¢ sè: 60.46.01.12

LUŠN V‹N TH„C Sž TON 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

Ch÷ìng 1. B€I TON VŠN TƒI C KHƒ N‹NG L×U

THÆNG H„N CH 5

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. B€I TON VŠN TƒI VÎI L×ÑNG CUNG BÀ

CHN 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. B€I TON VŠN TƒI VÎI L×ÑNG CUNG BÀ

CHN 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

K¸t luªn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

T i li»u tham kh£o . . . . . . . . . . . . . . . . . . . . . . 50

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 ch­c ch­n 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 s­c ¸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 s­c 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/