兰州交通大学：《管理运筹学》课程教学资源（授课教案，无图版）第十章网络的流.pdf

第十章网络的流网络模型的很多问题可以归结为网络流问题。第九章中介绍的最短路问题，本质上也是网络流问题，属于网络流问题的一类特殊问题。而多数网络流向题又是线性规划的特殊类型.都可以建立对应的线性规划或整数规划摸型。那么为什么要用网络流的方法代替线性规划，不用线性规划的一般求解方法，而要另外建立一些算法呢？由于实际问题中抽象出来的网络流模型是一类具有特殊结构的问题，利用其特性常常可以研究、寻求一些较单纯形法更为有效的方法去求解，又由于网络模型的直观性常常可以通过顶点一边的关系代数学模型来措述一个实际问题，更易于接受.网络流题是图论的重要方面，在广泛的领域里具有重要的应用。这一章我们以运输网络为例，介绍网络的流及其它有关问题。主要内容是：流和割的概念。最大流最小制定理，确定最大流的标记法，最小费用流以及最小费用最大流的网络模型。 S10.1基本概念和定理一、流设G=(W,E)为一有向图，顶点V表示一些城市（或中转站），边集E表示连接顶点的道路。给每边e∈E(G)赋予一个非负整数c(e) c,),或简记为c4,通常称为容量，它表示在一定时间内这条边货物的最大通过量则称G为一个网络，现在假定在网络中有一点s有大批货物要通过网络运送到网络的另一点t.s点我们称为网络的源，通常假定它没有射入边t点称为汇，假定它没有射出边.除了源和汇以外的点称为G的中间顶点.这样的网络就是在物资运输问题中常用的数学榄型，常常称为运输网络。在运输网络中边可以用来表示城市之间的公路或铁路，电信局之间的通讯线路等，边的容量则可以表示输送的物资量，速率公路或铁路上通过的车辆数或信息量等等。图10-1表示一个具有一个源s,一个汇t以及4个中间顶点，2，，”的运输网络.边旁的数字为c· 图10-1 假如，我们把网络中的边视为交通网中的道路，每条道路都有一定输送货物的能力即容量，问题就成为如何在该运输网络中寻找最佳运输方案一个货物运输方案，可以用网络上的一个可行流来表示。所谓网络上的流是指定义在边集合E上的一个函数f(e)=f(,),并称f(e)为 1

✂✁✂✄ ☎✂✆✂✝✂✞ ✟✡✠☞☛☞✌☞✍☞✎☞✏☞✑☞✒☞✓☞✔✖✕☞✗✖✘✙✟✚✠☞✛✖✑✖✒☞✜✣✢☞✤✖✥✙✦✚✧☞★✖✍✖✩☞✪✖✫☞✑✖✒, ✬☞✭☞✮☞✯ ✰✟✡✠☞✛☞✑☞✒, ✱☞✲ ✟✡✠☞✛☞✑☞✒☞✍☞✳☞✴☞✵☞✶✖✑☞✒✖✜✸✷✖✏✖✹✙✟✚✠☞✛✖✑✖✒☞✺✰☞✻✖✼✖✽☞✾✍☞✵✖✶ ✴☞✌, ✿✓☞✔☞❀☞❁☞❂☞❃☞✍✻☞✼☞✽☞✾✖❄✖❅✹✽☞✾☛✖✌☞✜✣❆✖❇☞✘✖❈☞❇✖❉✖❊✙✟✚✠☞✛✖✍✖❋☞●✖❍☞■✻ ✼✖✽✖✾, ❏ ❊✻✖✼✖✽✖✾✍✖✳✖❑✖▲✖▼✖❋◆●, ✷✖❉✖❖✖P✖❀✖❁✖✳✖◗✖❘✖●✖❙? ❚✚✲✖❯✖❱✑✖✒❲✦✚❳✖❨ ❩☞❬✍✙✟✡✠☞✛☞☛☞✌✰✳☞✴✖❭☞❪✖✵☞✶✖✗✖❫☞✍✖✑☞✒, ❴ ❊☞❵☞✵✼☞❛☞❛✓☞✔☞❜☞❝☞❞✣❡✖▲☞✳✖◗☞❢✖❣ ❤✖✐●✖❥✖✘✖❪✖❦✖✍✖❋✖●✖❧✖▲✖▼, ✺ ❚✚✲ ✟✚✠✖☛✖✌✖✍✖♠✖♥✼ , ❛✖❛✓✖✔✖♦✖♣✖q✖r – s ✍✖t✖✉ ❍✖■✖✹✖✈✖☛✖✌❬✖✇✖①✳✖②❯✖❱✑✖✒, ❥✖③✲✖④✖⑤✜✡✟✚✠✖✛✖✑✖✒✰✖⑥✖⑦✍✖⑧✖❉◆❋✖⑨, ⑩✖❶✖❷ ✍✖❸✖❹✖❺✖❭✖❪✖⑧✖❉✖✍✖❃✖❊✖✜ ❻✳✖✥✖❼✖❽✖✔✖❾✖❿❲✟✚✠✖✘✖➀, ✧✖★❲✟✚✠✖✍✖✛✖➁✖❵✖➂✖❪✖t✖✑✖✒✖✜➄➃◆❉❲➅✚➆✰ : ✛✖➇✖➈✖✍ ➉◆➊, ✩◆➋◆✛◆✩◆➌◆➈◆➍◆➎, ➏➍◆✩◆➋◆✛◆✍◆➐◆➑◆●, ✩◆➌◆➒◆❊◆✛◆✔◆➁◆✩◆➌◆➒◆❊◆✩◆➋◆✛◆✍➓✟➔✠ ☛✖✌✖✜ §10.1 →↔➣↔↕↔➙↔➛↔➜↔➝ ➞➠➟➢➡ ➤ G = (V, E) ✘✖✳✖❪❲➥⑥ , q✖r V ➦✖➧✳✖◗✖➨✖➩ (❄ ✦✚➫✖➭), s✖➯ E ➦✖➧✖➲✖④q✖r ✍✖➳✖✫✖✜➄➵✖➸s e ∈ E(G) ➺✖➻✳✖②✖➼✖➽❅✹ c(e) = c(vi , vj ), ❄✖➾➑✖✘ ci,j , ♦❛✖➚✘➶➪ ➹ , ➂➦✖➧✖⑩✳✖➍✖➘✖➴❲➅❻✖➷s✖➬✖➮✍✖✩✖➋✖♦✖♣✖➱, ✃➚ G ✘✖✳✖②❲✟✚✠✖✜❒❐⑩✖❮➍ ⑩ ✟✚✠ ✦✚❪✖✳✖r s ❪✖➋✖❰➬✖➮❉✖♦✖♣❲✟✚✠✖❾✖Ï✖Ð❲✟✚✠✖✍✖❖✖✳✖r t✜ s r✖❼✖❽➚✘❲✟✚✠✖✍ÒÑ, ♦❛ ❮ ➍✖➂✖Ó✖❪✖Ô✖Õs;t r➚✘×Ö, ❮ ➍✖➂✖Ó✖❪✖Ô❩ s ✜ÙØ✖Ú✖Û✖➇✖Ü✖✔✖P✖✍✖r➚✘ G ✍×Ý✖Þ ß✖à✜ ❻✖á✍❲✟✚✠✖â✰ ⑩✖➮✖ã❾✖❿✖✑✖✒❲✦❛❊✖✍✖✹✖✈✖☛✖✌, ❛✖❛✖➚✘×ä✖å✖æ✖ç✖✜ ⑩❾✖❿❲✟✚✠❲✦s ✓✖✔✖❊❬➦✖➧➨✖➩✖è✖➴✖✍✖é✖✫❄✖ê✫ , ë✚ì✖íè✖➴✖✍✖♦✖î✻✫✖ï, s ✍✖➆✖➱✃✓✖✔ ➦✖➧❿✖Ï✖✍➮✖ã➱ , ð✖ñ, é✖✫❄✖ê✫ ✮♦✖♣✖✍✖ò✖ó✖✹❄ì✖ô➱✖ï✖ï✖✜ ⑥ 10–1 ➦◆➧✳◆②◆❭◆❪◆✳◆②◆Û s, ✳◆②◆Ü t ✔◆➁ 4 ②➓✦➔➴◆q◆r v1, v2, v3, v4 ✍◆❾◆❿➓✟ ✠✖✜ s✖õ✍✖✹✖ö✖✘ ci,j ✜ ⑥ 10–1 ❮✖÷, ❼✖❽✖ø❲✟✚✠❲✦✚✍s✖ù✘✖ú✖♦❲✟✖✦✚✍✖➳✖✫, ➸➷➳✖✫✿ ❪✖✳✖➍✖❿✖Ï➬✖➮✍✖û✖ü✖ý ➆✖➱, ✑✖✒✖â✖þ✖✘÷✖ÿ✖⑩✁❾✖❿❲✟✚✠❲✦✚❡✁✂✖✩✁✄✖❾✖❿✖❋✁☎✖✜ ✳✖②➬✖➮❾✖❿✖❋✁☎, ✓✖✔✖❊❲✟✚✠✮ ✍✖✳✖②✖✓✁✆✖✛❬➦✖➧✜ ✝✁✞ ✟✚✠✮ ✍✠✟, ✰✁✡➍✁☛⑩✖s✖➯✁☞ E ✮ ✍✖✳✖②✁✌✖✹ f(e) = f(vi , vj ), ✍➚ f(e) ✘ 1

2 ✎✑✏✓✒✕✔✓✖✑✗✓✘ s (vi , vj ) ✮ ✍✙✟➹ (❪✖➘✯ ➾✁✚✁✛ fij )✜ ⑥ 10–2 ✝ ➧ ✍✖❾✖❿✖❋✁☎, â✖✓✁✜✛✖✰✖⑥ 10–1 ✮ ✍✖✳✖②✖✛, ➸➷s✖✮✍✖✢✁✢✖②✖✹✖ö✖â ✰◆s◆✮✍◆❾◆❿◆➱, ➚✘◆✛◆➱, ý fs1 = 3, fs2 = 1, f13 = 1, f14 = 1, f12 = 1, f24 = 2, f43 = 1, f3t = 2,f4t = 2✜ ⑥ 10–2 ✔ ⑥ 10–2 ✘✖➀, ✣ ✷✖③✁✤, ⑩❾✖❿❲✟✚✠✖✍❯✖❱✑✖✒❲✦, ❂ ✲ ✛✖❪✁✥✖②✖❉✖▲: ✳✰➸ s ✮ ✍☞✛☞➱❏ û✧✦☞♣☞s✍✖✩✖➋☞♦✖♣☞û✖ü (ýs ✍☞➆☞➱); ✢✰✦✡➴☞r☞✍☞✛☞➱☞✘✧★☞✜✪✩✖✘✙✦✚➴ r✧✫✧✬☞➫☞❾✛❊ , ✭ ❩ r☞✍☞✛☞➱✧✮☞ï, ✝✔☞❼☞❽✧✯✙✦✡➴☞r☞✍☞✛☞➱✖✘✧★✖✜✸❖✖P, ✰ r☞✍✧✱☞✛ ❩ ➱✖➇✁✲✖r✖✍✁✱✖✛✖Õ✖➱✁✳✁✮✖ï, ✯ ✰❻②✖❋✁☎✖✍✁✴✖❾✖❿✖➱✖✜✵✩✁✶✖❪: ❂ ✲ ✟✚✠ G ✮➵❩ ✍✁✷✁✸✖✔✁✹➷✁✺✍✖✳✁✻✖✛➚✘✖✓✁✆✖✛: 1. ➆✖➱✁✼✁✽➷✁✺, ❂✁✾✁✿s e = (i, j) ∈ E ❪ 0 ≤ fij ≤ cij (10.1) 2. ✦✚➴✖r✁❀✁❁➷✁✺, ❂✖➸✖②❲✦✚➴✖r vi(i 6= s,t) ❪ X (vi,vj )∈E fij = X (vj ,vi)∈E fji (10.2) ❂✔ v(f) ➦✖➧ ✟✚✠✁❃ s → t ✍✖✛✖➱ (✛✁❄), ✃❪ Xfij − Xfji = ( v(f), ❅ i = s ➘ −v(f), ❅ i = t ➘ (10.3) ✾✖✳❲✟✚✠ G, ❆✁❇✁❈✖⑩✳✖②✖✓✁✆✖✛✖✜✵✩✖✘◆❂✲✝❪✖✍s e, ➍✁☛ fij = 0, ✃ f ✣✁❉✷ ✸ ✮①✥✖②➷✁✺, ➚✘❋❊✁✟✖✜❒✛✁❄ v(f) = 0✜❒✷✖❾✖❿❲✟✚✠✖✍✖➃✖❉✖✑✖✒✰❉✁✂❩ ➂✖✍✖✳✖②✖✩ ➋✖✛, ý⑩✷✁✸✖➆✖➱✁✼✁✽✖➇❲✦✚➴✖r✁❀✁❁✖✍➷✁✺✹ , ● ✛✁❄ v(f) ❍ Ð✖✩✖➋✖✜ ➆✖➱✁✼✁✽➷✁✺✰ ✳✖②❏ï✁■, ✝✔✖✩✖➋✖✛✖✑✖✒✰✳✖②✁❏✖✌✖✍✻✖✼✖✽✖✾✑✖✒✖✜ ✩✁✶, ✟✚✠✖✛✖✍✻✖✼✖✽✖✾☛✖✌✖✓✖✔ ➦✖➧✘ max z = v(f) ✷✁✸    Pfij − Pfji =    v(f), ❅ i = s ➘ 0, ❅ i 6= s,t ➘ −v(f), ❅ i = t ➘ 0 ≤ fij ≤ ci,j , ❵❲✦(vi , vj ) ∈ E

§10.1 ❑✁▲✁▼✁◆✁❖✁P✁◗ 5 ❂❊ v(f ∗ ) ➦✖➧ ✟✚✠❲✦✓❃✖Û s Ð t ✍✖✩✖➋✖✛, ✃❪ : v(f ∗ ) = f ∗ (V1, V 1) − f ∗ (V 1, V1) (10.8) ❊ K∗ ➦✖➧✩✖➌✖➈✖✜✵❾✁❿✖➈✖✍➉✖➊,v(f ∗ ) ❃✖➌✲ï ✲ ✟✚✠❲✦✚✩✖➌✖➈✖✍✖➆✖➱ c(K∗ ), ý v(f ∗ ) = f ∗ (V1, V 1) − f ∗ (V 1, V1) ≤ c(K∗ ) (10.9) ❚✚➦ 10–1 ❧❩ ✟✚✠⑥ 10–3 ✦✓❃✖Û s Ð✖Ü t ✍✖✩✖➋✖✛✖➱❏✦✖♣ 14 ❣✁➀✖✜ ➁➟♦➂➄➃➠➡➄➂➆➅✠♥➆➇✠➈ ➉⑨✑➊✓➋✡❩ , ❂ f ∗ ✘✁✷✁✸✁✹❘➷✁✺✍✖✛: v(f ∗ ) = max{v(f)|f✘ G ✍✖✳✖②✖✛}, ✃➚ f ∗ ✘ G ✍✙❶✁➌✁✟✖✜ ❂ K∗ ✘✁✷✁✸✁✹❘➷✁✺✍✖➈: c(K∗ ) = min{c(K)|K✘ G ✍✖✳✖②✖➈}, ✃➚ K∗ ✘✙❶✁❸✁❺✖✜ ❂✟✚✠ G ✦ ❚ Û s Ð✖Ü t ✍✖✛✖➱❍ Ð✖✩✖➋✁❄✁✫✖û✖ï✲✩✖➌✖➈ K ✍✖➆✖➱, ý v(f ∗ ) = c(K∗ )✜ ❻â✰✁➍✁➎ ✍ Ford-Fulkerson ✍✖✩✖➋✖✛✖✩✖➌✖➈✖➍✖➎✖✜ ❻✰✖⑥➇❲✟✚✠◆➎⑦❋✖⑨◆✍✖✳ ②☞⑧☞❉☞➍☞➎, ✯ ✰✹☞⑨☞❉✧➏①✍☞❊☞➐☞➑✖●☞▲❲✟✡✠✖✩✖➋☞✛✖✍✧➐✁❿☞✜ ⑩✁➑①❻②✖➍✖➎☞è➉r✖✧ ★✁➒✖✛✁➓✖✍➉✖➊✜ ⑩ ✟✚✠ G ✦ , ➤ Q ✰✳➷❃✖Û s Ð✖Ü t ✍✁➓, ✃✖⑩❻✖➷➓ Q ✮✁✍❛✁➔ Q ✍✖❋❲➥✚✳✁→ ✍s, ➚✘➉➥s, ⑩ Q ✮✁✍❛✁➔ Q ✍✖❋❲➥✓✮✁➣✖✍s ➚✘✁↔❲➥s ✜ ➀÷✖⑩⑥ 10–3 ✦ , q✖r✁↕❘ sv1v3v4t ❫✖þ✖✳➷➓ , ❵❲✦ (s, v1),(v1, v3),(v4,t) ✰➉➥ s,(v3, v4) ✰↔❲➥s ✜ ÷✁➙ Q ✰❃ s Ð t ✍✖✳➷➓ ,fij ✰ G ✍✖✳✖②✖✓✁✆✖✛, ✷✁✸: 1. 0 ≤ fij < ci,j , ❅ (i, j) ✰ Q ✍➉➥s; 2. 0 < fij ≤ ci,j , ❅ (i, j) ✰ Q ✍✁↔❲➥s; ✃➚✶✁➓✖✘✙➛✁✟✁➜✖✜ ÷✁➙✖⑩ ✟✚✠ G ✮✁❈✖⑩✳➷➒✖✛✁➓ Q, ⑩➉➥s ✦ fij < ci,j , ⑩ ↔❲➥s ✦ fij > 0, ✃✓ ➝✁➞✳✁➟❅➌✖✍✁➠✖✹ θ: θ = min ( ci,j − fi,j , ❅ (i, j) ✰ Q ✍➉➥s, fi,j , ❅ (i, j) ✰ Q ✍✁↔❲➥s ❉ ↔ , ➡✁➢➉➥s✖✮✍✖✛✿✁➤ θ, ↔❲➥s✖✮✍✖✛✿❼ θ, ❏✖⑩➒✖✛✁➓✮ ✍s, ✛❏✁❳✜ ❊✖❘✁■➦✖➧â✰ : f 0 i,j =    fi,j + θ, ❅ (i, j) ✰ Q ✍➉➥s; fi,j − θ, ❅ (i, j) ✰ Q ✍✁↔❲➥s; fi,j , ❵✖➂

兰州交通大学：《管理运筹学》课程教学资源（授课教案，无图版）第十章 网络的流

兰州交通大学：《管理运筹学》课程教学资源（授课教案，无图版）第十章网络的流