运筹学 图与网络分析 1

第十章       图与网络 赵 玮

主要内容： 10.1 基本概念 10.2 最短路问题 （一）Bellman最优化原理 （二）Dijustra算法（双括号法） 10.1 基本概念 10.2 最短路问题 （一）Bellman最优化原理 （二）Dijustra算法（双括号法） （三）通信线路布施问题 （四）设备更新问题 10.3 最小生成树 （一）基本概念与理论 （二）Kruskal算法（加边法、破圈法） （三）丢边法（破圈法） 3

主要内容： 10.4 最大流问题 （一）基本概念 （二）双标号算法 10.5 最小费用最大流 （二）求解算法 4

§ 10.1 基本概念 1 图 def1：一个无向图（简称为图）G是一个有序的二元组，记为G=(V, E)。其中 V={V1…Vn}称为G的点集合，E=(eij)称为G的边集合，evj为连接VV与Vj的边。 5

若N和E均为有限集合，则称为G为有限图，否则称无限图。 若G中既没有有限回路（圈），也没有两条边连接同一对点，则称G为简单图。如右图之（a），右图之（b）不是简单图。 若G为简单图，且G中每个点对之间均有一条边相连，则称G为完全图。如图（a）是简单图，但不是完全图。 图 a 图 b 6

|V|=n表示G中节点个数为n，此节点个数n也称为图G的阶 |A|=m表示有向图G中弧的个数为m def 2：一个有向图G是一个有序的二元组，记为G=(V, A)，其中V=(V1V2…Vn)称为G的点集合，A={aij}称为G的弧（有向边）集合，aij是以Vi指向Vj的一条弧。 |V|=n表示G中节点个数为n，此节点个数n也称为图G的阶 |A|=m表示有向图G中弧的个数为m 任一顶点相关联（连接）的边的数目称为该顶点的次数 7

2 连通图 def 3：在有向图G中,一个点和边的交替序列{Vi eij Vj…Vk ekl Vl} 称为G中从点Vi到Vl的一条路，记为A，其中Vi为此路A的起点，Vj为路A的终点；若路A的起点与终点重合,则称A为回路；又若G中点Vi与Vj间存在一条路，则称点Vi与Vj是连通的；若G中任何二点都是连通的，则称G为连通图，或图G为连通的。在无向图中有对应的概念。 有向图 路 回路 无向图 链 圈 8

def 4：设有两个图：G1= (V1, E1) ，G2= (V2, E2)若有 ，则称G1为G2的子图， 3 子图 def 4：设有两个图：G1= (V1, E1) ，G2= (V2, E2)若有 ，则称G1为G2的子图， 记作 ；若有 V1=V2而 ,则称图 G1= (V1, E1) 是图G2= (V2, E2)的生成子图（支撑 子图）。 9

例：下示图G1是图G的子图，图G2是图G的生成子图。 V1 V3 V2 V4 V1 V1 V3 V2 V4 V2 V4 （a）图G （b）图G1 （c）图G2 10

4 赋权图（加权图）与网路 def 5：设G是一个图（或有向图），若对G的每一条边（或弧）eij都赋予一实数ωij，称其为该边（弧）的权，则G连同其他弧上的权集合称为一个赋权图，记作G= (V, E, W) 或G= (V, A, W)，此中W={ωij}，ωij为对应边（弧）eij的权。若G= (V, E, W) （或(V, A, W)）为赋权图，且在G的V中指定一个发点（常记为Vs）和一个收点（记为Vt），其余点称为中间点，则称这样指定了发点与收点的赋权图G为网络。 11

§ 10.2 最短路问题 def 6：设G =（V, A, W）为一个赋权有向图，Vs为指定发点，Vt为指定收点，其余为中间点，P为G中以Vs到Vt的一条有向路，则称 为路P的长度，若有 则称 为G中从Vs到Vt的最 短路， 为该最短路的长度（此中F为G中 所有从Vs到Vt的全体有向路的集合）。 12

最短路问题在企业厂址上选择，厂址布 局，设备更新，网络线路安装等工程设计与 企业管理中有重要应用。 13

（一）Bellman最优化原理 1 命题1：若P是网络G中从Vs到Vt的一条最小路，Vl是P中除Vs与Vt外的任何一个中间点，则沿P从Vs到Vl的一条路P1亦必是Vs到Vl的最小路。 P1 Vs V1 Vl V2 Vt P2 14

若P1不是从Vs到Vl的最小路，则存在另一条 Vs 证明（反证）： 若P1不是从Vs到Vl的最小路，则存在另一条 Vs 到Vl的路P2使W(P2)<W(P1)，若记路P中从Vl到Vt的路为P3。则有W(P2) + W(P3)<W(P1) + W(P3)=W(P)，此说明G中存在一条从Vs沿P2到Vl沿P3再到Vt的更小的一条路，这与P使G中从Vs到Vt的一条最小路矛盾。 15

⑴ 为求得Vs到Vt的最短路，可先求得Vs到中间点的最短路，然后由中间点再逐步过渡到终点Vt。 2 算法思想： 设G中从Vs到Vt的最小路P：Vs…Vj…Vk…Vt，则由上述命题知：P不仅是从Vs到Vt的最小路，而且从Vs到P中任意中间点的最短路也在P上，为此可采用如下求解思路： ⑴ 为求得Vs到Vt的最短路，可先求得Vs到中间点的最短路，然后由中间点再逐步过渡到终点Vt。 16

⑵ 在计算过程中，需要把V中“经判断为最短路 P途径之点i”和“尚未判断是否为最短路P途径 之点j”区分开来，可设置集合I和J,前者归入 I，后者归入J，并令算法初始时，I中仅包含 Vs，其他点全在J中，然后随着求解过程的进 行，I中的点逐渐增加（相应J中的点逐渐减 少），直到终点Vt归入I（相应J=φ），此时 迭代结束。I称为已标号集合,J称为未标号集合。 17

⑷ 为在计算机上实现上述求解思想，还需引入G中各点间一步可达距离阵D=(dij)n×n，此中 |V|=n ⑶ 为区分中间点Vk是否已归入I中以及逆向求解最短路的方便，可在归入I中的点Vj上方给予双标号（lj, Vk），此中lj表示从Vs到Vj最短路的距离，而Vk则为从Vs到Vj最短路P中Vj的前一途径点。 ⑷ 为在计算机上实现上述求解思想，还需引入G中各点间一步可达距离阵D=(dij)n×n，此中 |V|=n 18

⑸ 以下介绍的是适用于弧权为正值的有向网络中求最短有向路的Dijkstra算法，又称双括号法。事实上该算法亦适用于弧权为负值的有向网络求最短路问题。 19

（二）Dijkstra算法（双括号法） 图 一 由图G建立一步可达距离阵D=(dij)n×n 给V1(Vs)括号(l1,Vk)=(0,s)给出已标号集合I和未标号集合J的元素 对于给定的I和J，确定集合A={aij |Vi∈I，Vj ∈J} 计算距离 给Vk括号(lk ,Vh) lk=lh + Whk I=I + {Vk} J=J – {Vk} N A=φ 或 J＝φ Y 从Vt 逆向搜索双括号，可得最小路P途径各点及最小路距离 图 一 END 20

例1（教材208页）求G的最短路， 图G形如下形。 解：利用上述Dijkstra算法步骤可得表一所示求 解过程，并有最短路P：V6 V4 V3 V1， 最短距离|P|=2+1+5=8。 图（一） 5 1 2 21

表一（例1 求解过程） 22

例2 求如下G之最小路 V1 V2 V6 V8 2 7 4 6 7 3 3 6 V3 1 1 3 6 6 图 二 V4 V5 V7 23

解 表 二 24

表三 （例2求解过程） 25

最短路长 |P1|=2+7+4=13 |P2|=2+3+3+1+4=13 由表三知 V1 V8 最短路P1：V8 V6 V2 V1 最短路P2：V8 V6 V5 V3 V2 V1 最短路长 |P1|=2+7+4=13 |P2|=2+3+3+1+4=13 4 7 2 4 1 3 3 2 26

（三）通信线路布设问题（教材P209） 例3. 甲、乙两地之间的公路网络如图三，电信公司准备在甲、乙两地沿公路沿线架设一光缆线，问应如何架设此线路方案，以使光缆线路架设总长度最短？ 图 三 27

G={V,E,W},V={V1V2V3V4V5V6V7}，本例G为无向图，求解过程见表四 解：本例之一步可达距离阵如 W= G={V,E,W},V={V1V2V3V4V5V6V7}，本例G为无向图，求解过程见表四 28

表四 （例3求解过程） 29

② 还可得到自V1（甲）到任一中间点之最短路，例如 V1 V4 最短路由表四可知为 P14 V4 V5 V3 V1 |P14|=18 ① 由表四可得 最短路P： V7 V6 V5 V3 V1 最短距离 |P|=10+4+2+6=22 ② 还可得到自V1（甲）到任一中间点之最短路，例如 V1 V4 最短路由表四可知为 P14 V4 V5 V3 V1 |P14|=18 6 2 4 10 30

（四）设备更新问题（教材P212） 例4. 某公司设备管理部门欲制定一个五年期某设备的更新计划，要求给出这五年中购置该设备的年份及购置新设备的使用年限。 在此五年中购置该设备的年初价格见表五，设备使用不同年限的维护费见表六。 31

表五 （单位：万元） 表六 （单位：万元/年） 年份 1 2 3 4 5 年初价格 11 12 13 表六 （单位：万元/年） 使用年数 0～1 1～2 2～3 3～4 4～5 年维护费用 5 6 8 11 18 32

aij —i年初购进之新设备使用到第j年初（j-1年末） ωij—i年初购进之新设备使用到第j年初（j-1年末） 之总费用 解：设 Vi —i年初购进一台新设备 aij —i年初购进之新设备使用到第j年初（j-1年末） ωij—i年初购进之新设备使用到第j年初（j-1年末） 之总费用 根据表五与表六之有关数据可计算 ωij 详可 参见表七；由表七可得W阵如表八；由表八可得 有向图四；将表八可转换成一步可达阵如表九， 求解过程见表10。 33

表七 （W 计算过程） 34

35

表八 费用阵（单位：万元） j ωij i 36

图四 （设备更新有向图） 37

表 九 38

表10 设备更新求解过程 min 39

40

由表10可知最短费用流（相当于最短路） P： V6 V3 V1 | P| = 53万元 V4 41

公司五年期设备更新方案有两个：A与B，总费用均为53万元。 结论： 公司五年期设备更新方案有两个：A与B，总费用均为53万元。 A 方案：第1年初购置设备使用到第3年初（第2年末），第3年初再购置新设备使用到第 5年末（第6年初） B 方案：第1年初购置设备使用到第4年初（第3年末），第4年初再购置新设备使用到第5年末（第6年初） 42

§10.3 最小生成树 最小生成树在网络（电信网、公路网等）设计与企业管理中有重要应用。 43

（一）基本概念与理论 def 7：无圈的连通图（无向图）称为树，常 记为符号T。如图五的（a）为树，（b）有圈， （c）不连通，故（b）（c）均非树。 V2 V1 V5 V4 V6 V3 V2 V1 V5 V4 V6 V3 V2 V1 V5 V4 V6 V3 （a） （b） （c） 图 五 44

def 8：若T是图G的一个生成子图而且又是一 棵树，则称树T是图G的一个生成树（又称支 撑树）；又若树T=(V1,E1)为图 G=(V,E,W)的 一个生成树，令 称为树T的权 （或长度），则G中具最小权的生成树称为G 的最小生成树，亦即若有 则有 T* 为G 的最小生成树，此中F为G的全 体生成树的集合。 45

Th1：设T=(V,E)是|V|≥ 3的一个无向图，则下列六个关于树的定义是等价的： ⑴ T连通且无圈 路相连 ⑶ T连通且有n-1条边，此中n= |V| ⑷ T有n-1条边且无圈，此中n= |V| ⑸ T无圈，但在T中任两个不相邻的顶点间添加 一条边，则可构成一条回路 ⑹ T连通，但去掉任一条边后就不连通，即树T 是连通且边数最小的图 46

（二）Kruskal算法（加边法，破圈法） 1. 算法思想： ① 由Th1(4)结论：若|V| = n ，则树T有n-1条边且 无圈 ② 由def 8，最小生成树T*是具有最小权的生成树 故可E中各边按权大小排列设为W1≤ W2≤ … ≤ Wm，对应？边依次为a1,a2, … am，然后将 a1,a2, … 依次进入集合S，直到获得S的生成树T 为止（树的判断可由Th1(4)结论），则此树T必 为最小生成树。 47

设G=(V,A,W)， |V| = n ， |A| = m S— 待生成的集合 i — S中进入最小生成树的边序号 j — 逐个进入S的G的边序号 ei+1 — S中进入最小生成树的边 j Wj aj akl 1 W1 a1 a23 2 W2 a2 a55 … m Wm am a76 表 11 48

对G中各边按权大小顺序排列，不妨设为W1≤ W2≤ … ≤ Wm 填写Wj对应的各边aj 表11 S=φ ，i = 0，j=1 Y |S| = n-1 N Y {aj} ∪ S构成回路？ N ei+1=aj S={ei+1} ∪ S i=i +1 j=j+1 T*=S 打印T* j=j+1 END 图 六 49

例5（教材P218） 某大学准备对其所属的 7 个学院办公室计算机联网．这个网络的可能联通的途径如图七所示，图中V1，…，V7表示7个学院办公室，边eij为可能联网的途径。边上所赋的权数为这条路线的长度（单位：百米）。试设计一局域网既能联结七个学院办公室，又能使网络线路总长度为最短。 50

解：依据各边权自小到大排列建立表12，求解过程见表13，由表13得知最小生成树 Wj aj akl T* W1 a1 a23 * W2 a2 a35 W3 a3 a27 W4 a4 a17 W5 a5 a67 W6 a6 a37 W7 a7 a56 W8 a8 a57 W9 a9 a43 W10 a10 a45 W11 a11 a16 图七 G={V,E,W}, |V| =7, |E| = 11 W=(ωij) ωij见图 解：依据各边权自小到大排列建立表12，求解过程见表13，由表13得知最小生成树 T*={a1,a2,a3,a4,a5,a9} W(T*)=1+2+3+3+7=19 表 12 51

表13 （例5求解过程） 52

例 6. 利用加边法求图八所示的无向图G之最小生成树 Wj aj akl T* W1 a1 a12 * W2 a2 a13 W3 a3 a45 W4 a4 a23 W5 a5 a25 W6 a6 a24 W7 a7 a34 W8 a8 a35 V2 3 1 4 V1 V4 2 V5 2 4 2 4 V3 图 八 解：G={V,E,V}， |V| = 5 |E| = 8 表 14 53

表 15 （例6求解过程） 54

（三）丢边法（破圈法） 1. 算法原理： 丢边法与加边法相反，加边法是以不形成回路为准则将S=φ逐步加边以形成树，而由于按边权愈小愈优先加进去，故为最小生成树，而丢边法则是S= E以不形成回路为准则逐步丢边以形成树，由于是按边权愈大愈优先丢掉，故同样为最小生成树。 55

设G=(V,E,W)， |V| = n， |E| = m， S — 待生成的集合（逐步丢边） i — S中丢掉边的序号 j — S中保留边的序号 ei+1 — S中丢到的边 e1— S中丢到的边的全体（集合） fj+1 — S中保留的边 D — S中保留边的集合 56

由于边个数为m，树含边的个数为n-1，故丢 掉（形成回路）边的个数为 m-(n-1)=m-n+1，以 此为程序出口，标志着最小生成树形成 依次从大到小按列同例5表12。 57

G=(V,E,W)，|V| = n，|E| = m， S= E，i=0，j=0，E1=φ, D=φ S中是否有包含al 的一个回路 N 图 九 Y i=i +1 ei=al S= S -{ei} E1=E1∪{ei} j=j +1 fj=al D=D∪{fi+1} T*=S-E1 打印T*的边序列 END N Y i≥ m-n-1 58

T*=S-{e1~e5}={a1,a2,a3,a4,a5,a9}与前加边法求解 相同，详可参考教材P218的六个图。 例6. （同例5）用丢边法求解 求解过程见表16，由于m-n+1=11-(7-1)=5 故i=5时程序终止，由表知 T*=S-{e1~e5}={a1,a2,a3,a4,a5,a9}与前加边法求解 相同，详可参考教材P218的六个图。 59

表16 （例6求解价格） 5=i=m-n+1 60

§ 10.4 最大流问题 由前知，一个指定了收点和发点的赋权图 G 称为网络，在网络设计中研究网络的流量具有现实意义，如交通网络的车流流量，通信网络中的话务流量，金融网络中的现金流量，控制网络中的信息流量，供电网络中的电流流量等。人们也常常希望知道在既定网络中能允许通过的最大流量，以便对该网络的利用程序作出评价，这就是所谓的网络最大流问题。求解方法有双标号法，对偶图法等。 61

（一）基本概念 1．网络中弧的容量与流量 def9：对于一个指定收、发点的赋权有向（无向）图或网络N＝（V，A，C），弧aij∈A的最大允许通过能力称为该弧的容量，记为cij（cij≥0），全体cij构成之集合记为C；而通过边aij的实际流量成为流量，记为fij，故有0≤fij≤cij。显然若fij≥cij则网络N在aij边将发生堵塞现象，这是人们希望能避免的现象。 62

f ={fij∣aij∈A}为网络N上的流函数，简称网 络流；满足如下条件的网络流称为可行流，其 2．可行流与最大流 def10：设有网络N＝（V，A，C），称 f ={fij∣aij∈A}为网络N上的流函数，简称网 络流；满足如下条件的网络流称为可行流，其 中v（f）为网络N可行流的总流量（净流入量）。 63

说明：进入节点vj的流量＝自节点vj流出的流量； fij≡0之零流亦满足上述条件，故零流以为可行流。 （1）容量限制条件： （2）流量守恒条件： 说明：进入节点vj的流量＝自节点vj流出的流量； fij≡0之零流亦满足上述条件，故零流以为可行流。 64

3．顺向弧、逆向弧与可增路 def11：设f是网络N的一可行流，P是N中从vs到vt的一条路，对于路P途经的各弧，若弧的方向与路的方向相同，则称该弧为顺向弧，若弧的方向与路的方向相反，则称该弧为逆向弧。若在路P的一切顺向弧（vi，vj）上有fij＜cij，在路P的一切逆向弧（vj，vi）上有fji＞0，则称路 P是一条关于f的可增路。 65

说明： （1）由def 11得知：若在路P中，存在一条顺向弧（vi，vj）有fij＝cij（此时称弧为饱和弧），或者在路P中存在一条逆向弧（vj，vi）有fji＝0，则称路P为不可增路； （2）在图10所示的网络N中有一可行流f={fij∣aij∈A}，用蓝字标记，红字标记各弧的容量cij。表17给出了四条从v1到v7的路是否可增路的判别理由。（此f满足流量守恒条件与容量限制条件，如 66

图 10 67

表 17 j v1到v7的路 可增路？ 理由 1 v1v2v5v7 √ 顺向弧有fij＜cij 2 v1v2v5v3v6v7 表 17 j v1到v7的路 可增路？ 理由 1 v1v2v5v7 √ 顺向弧有fij＜cij 2 v1v2v5v3v6v7 顺向弧fij＜cij 逆向弧有f35＞0 3 v1v4v7 × 顺向弧有f47＝c47 4 v1v2v3v4v7 顺向弧有f23＝c23，f47＝c47 68

（3）可增路的内涵可通过下例得知 在图10之可行流f中，对于路 v1v2v5v3v6v7 途经的各弧中，若f12，f23增加一个单位流量，f35减少一个单位流量，利用流量守恒条件，可得一个如图11的新的可行流 ，并有v（ ）= 10＞9 = v（f）。 图11 69

fij＜cij之条件，实际上说明沿该弧（vi，vj）还 可提高流量 △ij＝cij－fij＞0，另一方面，为提 由上可知在def11中可增路要求顺向弧 fij＜cij之条件，实际上说明沿该弧（vi，vj）还 可提高流量 △ij＝cij－fij＞0，另一方面，为提 高流量v（f）还要求该路的逆向弧降低流量，而 fji＞0正说明了该逆向弧可降低fji个单位。 70

（二）双标号算法 1．算法思想（见图12） 图 12 给定N＝{V，A，C}，任取一可行流f＝{fij}，若无可行流，可取零流。l＝1 在f中任取一可增路pl 利用标号规则与调整规则对沿着路p的各弧作最大可能调整 是否对N中所有 路均作调整 打印经调整后的最大流f*及最大流量v（f*） 取N的一条新可增路pl l＝l＋1 END 图 12 71

2．调整步骤 （见图13） 图13 寻找一可增路pl， l＝1 vs标号（s，∞），沿pl寻找vs的下一相邻节点vj 按标号规则对vj进行双标号（vj，l（vj）） vs＝vt 沿pl从收点vt开始反向搜索途经各弧，按调整规则作流量调整 抹去pl上各点之双标号，从而由原可行流f调整为新可行流f1，并有v（f）＜v（f1） 是否还有新的可增路 打印并输出经调整后的最大流f*＝{fij∣aij∈A}，最大流量v（f*） 结束 l＝l＋1 取N的新的可增路pl j＝k，i＝j 沿pl寻找vj的相邻的一点vk N Y 2．调整步骤 （见图13） Y N 图13 72

1o 若（vi，vj）为顺向弧，且fij<cij，则给vj 标号（vi＋，l（vj）），其中l（vj）＝ 3．标号与调整规则 （1）标号规则： 1o 若（vi，vj）为顺向弧，且fij<cij，则给vj 标号（vi＋，l（vj）），其中l（vj）＝ min（l（vi），cij－fij）； 2o 若（vi，vj）为逆向弧，且fji>0，则给vj标 号（vi－，l（vj）），其中l（vj）＝ min（l（vi），fji）； 3o 若（vi，vj）为顺向弧但fij＝cij或（vi，vj） 为逆向弧但fji＝0，此时沿该弧的路线停止标号。 73

1o 若（vi，vj）为顺向弧，则对pl路径的顺向弧作调整，其调整量△ij＝fij＋l（v）； （2）调整规则： 1o 若（vi，vj）为顺向弧，则对pl路径的顺向弧作调整，其调整量△ij＝fij＋l（v）； 2o 若（vi，vj）为逆向弧，则对pl途经的逆向弧作调整，其调整量△ji＝fji－l（v）； 3o G中不在pl路上的各弧不作调整。 74

4．例7（教材P219） 某石油公司拥有一管道网络，使用此管道网络可将石油从采地v1运往销地v7，由于各地的地质条件等不同，因而其管道直径有所不同，从而使各弧的容量cij（单位：万加仑/小时）不同，对于如图14所示的管道网络N＝（V，A，C），问每小时从v1往v7能运送多少加仑石油？ 75

图 14 76

解1：若设弧（vi，vj）上的流量为fij，网络N上总流量为F，则可建立如下LP： max F ＝ f12 ＋ f14 f12 ＝ f23 ＋ f25 f14 ＝ f43 ＋ f46 ＋ f47 f23 ＋ f43 ＝ f35 ＋ f36 s．t f25 ＋ f35 ＝ f57 f36 ＋ f46 ＝ f67 f47 ＋ f57 ＋ f67 ＝ f12 ＋ f14 fij≤cij i＝1～6，j＝1～7 fij≥0 i＝1～6，j＝1～7 C阵 v1 v2 v3 v4 v5 v6 v7 v1 v2 v3 v4 v5 v6 v7 0 6 0 6 0 0 0 0 0 2 0 3 0 0 0 0 0 0 2 2 0 0 0 3 0 0 3 2 0 0 0 0 0 0 5 0 0 0 0 0 0 0 77

利用单纯形法可解得最大流： f*＝{f12＝5，f14＝5，f23＝2，f25＝3， f43＝2，f46＝1，f47＝2，f35＝2， f36＝2，f57＝5，f67＝3，v（f*）＝10} 78

求解中寻找了五条可增路，其标号过程与增流过程见表18，表18中各可增路及其流量调整过程见图15。 解2：（采用双标号法求最大流） 求解中寻找了五条可增路，其标号过程与增流过程见表18，表18中各可增路及其流量调整过程见图15。 求解结果与解1相同。 79

80

81

82

83

图15 84

表18 （例7求解过程） l 可增路pl 第二个标号l（vj） 可调整量l（vt） 标号图 调整图 网络流量v（f） 1 v1v4v7 表18 （例7求解过程） l 可增路pl 第二个标号l（vj） 可调整量l（vt） 标号图 调整图 网络流量v（f） 1 v1v4v7 l（v4）＝6，l（v7）＝2 2 （a） （b） v1v2v3v5v7 l（v2）＝6，l（v3）＝2 l（v5）＝2，l（v7）＝2 （c） （d） 4 3 v1v4v6v7 l（v4）＝4，l（v6）＝1 l（v7）＝2 （e） （f） 5 v1v2v5v7 l（v2）＝4，l（v5）＝3 l（v7）＝3 （g） （h） 8 v1v4v3v6v7 l（v4）＝3，l（v3）＝3 l（v6）＝2，l（v7）＝2 （i） （j） 10 已无可增路 END 85

§ 10.5 最小费用最大流 在很多网络（电信网络、运输网络、计算机网络）的分析与设计问题中，人们除关心网络的系统容量外还要考虑费用问题，以便建立一个高效、低耗的网络系统。这就是最小费用最大流问题的研究。 86

（一）基本概念 def12：设网络N＝｛V, A｝，除对每一弧a∈A规定了其容量c(a)外，还给定一个数b(a) ≥ 0称为弧a的单位流量费用，即有网络N＝｛V, A, c, b｝称其为带费用（代价）的网络。设f是N上的一个可行流（从vs到vt），称 为可行流f的费用。 将N上所有流量等于v0的可行流中费用最小的可行流f称为流量为v0的最小费用流，进一步当v0又是N中最大流的流量时，则称此f为最小费用最大流。 87

例8 某石油公司管道网，由于输油管道的长短不一，故对于不同的地段（路径）有不同的容量限制cij之外，还有不同的单位流量费用bij，该cij的单位为万加仑/小时，bij的单位为百元/万加仑，管道网络如图16所示，图中括号内的数字表示（cij，bij）。 88

解1：设fij表示aij上实际流量，则由定义12可建立如下LP max s.t 89

此解与例7的解显然不同，它是在考虑了费用目标后的结果。 总费用b(f)=145 此解与例7的解显然不同，它是在考虑了费用目标后的结果。 90

算法原理：最小费用最大流之算法有多种，以下介绍一种比较易理解的算法。 （二）求解算法 算法原理：最小费用最大流之算法有多种，以下介绍一种比较易理解的算法。 定理3：设f是流量为v0的最小费用流，p是关于f 的可增路中费用最小的可增路。可增容量为δ 则沿p增容δ后所得到的可行流 即为 的最小费用流。 若将N中弧aij的单位费用bij作为该弧的弧长，则上述定理中的“可增路中费用最小”可理解为“可增容的最短路”。（∵此中最短的含义即为路径各弧的费用和最小） 利用上述定理可得如下算法步骤。 91

2.算法步骤 图 17 92

3、例8 解2：求解过程见表19，表19各最短路的增容过程见图18。 表 19 l 关于fl－1的可增容最短路pl 最短路长 ︱pl︱ 可调容量 l（vt） 系统容量 v（f） 总费用 1 v1v4v6v7 10 2 v1v4v7 11 3 32 v1v4v3v6v7 12 5 56 4 v1v4v3v5v7 16 6 72 v1v2v5v7 17 9 123 v1v2v3v5v7 22 145 对于图18的求解过程可用表20中之定理内容来解释此算法原理。 93

94

95

96

图18 97

（1）最小费用最大流f*＝{fij}，与解1计算结果相同； 结论： （1）最小费用最大流f*＝{fij}，与解1计算结果相同； （2）最小费用 b(f)= 4×6＋6×3＋3×4＋1×5＋3×2＋2×4 ＋2×3＋5×7＋3×4＋1×3＋2×8 = 145 与解1计算结果相同。 98

p是关于f的可增容（可增容量为δ）最短路 表 20 f是容量为v0的最小费用流 p是关于f的可增容（可增容量为δ）最短路 则沿p增容δ后所得的可 行流 为容量为v0＋δ 的 最小费用 f0是 0 p1 f0 1 p1 f1 1 f1是 1 p2 f0 2 p2 f2 3 f2是 2 p3 f0 2 p3 f3 5 f3是 3 p4 f0 1 p4 f4 6 f4是 4 p5 f0 3 p5 f5 9 f5是 5 p6 f0 1 p6 f6 10 99

此中需要说明的是：p1是f0的可增容最短路，为什么不是f1的可增容最短路？这是由于f1沿 p1已不可能再增容。（因为f1是由 f0沿p1增容而得，至少有一弧，如a46已饱和，c46＝f46＝1），故p1是最短路（关于bij）但非可增容。综合二者说明p1不是f1的可增容最短路（或说 p1是f1的不可增容最短路）。 100