运筹学课件图与网络分析

运筹学课件图与网络分析第一页，共一百五十五页，编辑于2023年，星期二8.4最短路问题

最短路问题是重要的最优化问题之一，本节以赋权有向图为例，介绍最短路问题。第二页，共一百五十五页，编辑于2023年，星期二8.4.1有向图

设D=(V,A)是一个有向图，对于D中的一条弧a=(u,v)，称u为a的始点、v为a的终点，称弧a是从u指向v的。若从D中去掉所有弧上的箭头，就得到一个无向图，称之为D的基础图，记为G(D)。类似于无向图，可以定义简单有向图、多重有向图。第三页，共一百五十五页，编辑于2023年，星期二有向图及其基础图v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v8第四页，共一百五十五页，编辑于2023年，星期二路与回路

给出D中的一个点、弧交替序列如果这个序列在基础图G(D)中所对应的点、边序列是一条链，则称这个点、弧交替序列是D的一条链。类似定义圈和初等链(圈)。如果是D的一条链，并且对t=1,2,…,k-1，均存在，称之为从的一条路。若路的起点和终点相同，则称之为回路。类似定义初等路(回路)。…,,i1v,i1v,i1a,i2v,v,i2aik-1v,ik-1a,ikv…,,i1v,i1v,i1a,i2v,v,i2aik-1v,ik-1a,ikv()it+1v,itvi1a=()ikvi1v到第五页，共一百五十五页，编辑于2023年，星期二8.4.2最短路问题

给定一个赋权有向图，

即给了一个有向图D=(V,A)，对每一条弧a=(vi,vj)，相应地有权w(a)=wij。又给定D中的两个顶点vs,vt

，设P是D中从vs到vt的一条路，定义路P的权是P中所有弧的权之和，记为w(P)。最短路问题就是要在所有从vs到vt的路中求一条权最小的路P0，路P0的权称为从vs到vt的距离，记为d=(vs,vt)。第六页，共一百五十五页，编辑于2023年，星期二引例v1v2v3v4v5v6v7235195733862已知如下图所示的单行线交通网，第七页，共一百五十五页，编辑于2023年，星期二设有向图D=(V,A)，若D中的一条路是一条从的最短路，则其中任一条子路

,(r=1~k-1,s=2~k)

是从的最短路（最短路的子路必是最短路）。k1iiP…,,i1v,i1v,i2vikv=

()ikvi1v到最短路性质ir+1v,sriiP…,,v,irisv=

()is-1v,isvirv到i1vir+1vi2virvisvikvis-1vik-1v第八页，共一百五十五页，编辑于2023年，星期二8.4.3最短路算法第九页，共一百五十五页，编辑于2023年，星期二Dijkstra算法适用条件：弧a=(vi,vj)的权wij≥0的赋权有向图，边e=[vi,vj]的权wij≥0的赋权无向图。在这种情况下，图中任一条路的权不小于其子路的权。求解特点：可以求得某点到其他各点的最短路。求解技术：图的收缩。第十页，共一百五十五页，编辑于2023年，星期二引例v1v2v3v4v5v6v7235195833862第十一页，共一百五十五页，编辑于2023年，星期二算法的要点v1v2v3v4v5v6v7235195833862v1v3v4v5v6v711,v24,v2351583386第十二页，共一百五十五页，编辑于2023年，星期二v1v3v4v5v6v711,v24,v2351583386第十三页，共一百五十五页，编辑于2023年，星期二v1v3v5v6v758338611,v24,v28,v4第十四页，共一百五十五页，编辑于2023年，星期二v1v5v6v738611,v28,v412,v37,v3第十五页，共一百五十五页，编辑于2023年，星期二v1v6v711,v212,v310,v515,v56第十六页，共一百五十五页，编辑于2023年，星期二v1v716,v615,v5第十七页，共一百五十五页，编辑于2023年，星期二路径上溯v1v2v3v4v5v6v7235195733862第十八页，共一百五十五页，编辑于2023年，星期二Dijkstra算法的程序(i)令k=0,Sk=,

T(vs)=0,(vs)=0

,

对每一个vj=vs,令T(vj)=+¥,(vj)=M，转入(ii)。(ii)令T()=min{T(vj)|vjSk}。若T()<+¥

，则把的T标号变为

P标号P()=T()，令Sk+1=Sk{}。若Sk=V，计算终止，d(vs,vj)=P(vj),vjSk。若SkV，令l=ik

，把k换成k+1，转入(iii)。若T()=+¥

，计算终止。d(vs,vj)=P(vj),vjSk;d(vs,vj)=T(vj)=+¥

,vjSk。

(iii)考查每个使(vl,vj)A并且vjSk的点vj，若T(vj)>P(vl)+wlj，则把T(vj)修改为P(vl)+wlj，把(vj)修改为l，转入(ii)。ikvvi

kvi

kvi

kvi

kvi

kvi

kvi

kvi

kv第十九页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v7235195833862(0,0)(2,1)5,1¥,M¥,M3

,1¥,M路长标号路径标号P标号T标号第二十页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v7235195833862(0,0)¥,M¥,M¥,M¥,M¥,M¥,M路长标号路径标号第二十一页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v72351958338620,0¥,M¥,M¥,M¥,M¥,M¥,Mv1v2v3v4v5v6v72351958338620,0¥,M¥,M¥,M¥,M¥,M¥,M(0,0)2,15,13,1第二十二页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v7235195833862(0,0)(2

,1)4,211,2¥

,M3,1¥,Mv1v2v3v4v5v6v7235195833862(0,0)2,15,1¥,M¥,M3

,1¥,M(2,1)8,4(3,1)4,211,2第二十三页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)11,2¥

,M(3,1)7,3v1v2v3v4v5v6v7235195833862(0,0)(2,1)4,211,2¥,M(3

,1)8

,4(7,3)(4,2)7,310,515,5第二十四页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)(10,5)15,5(3,1)(7,3)v1v2v3v4v5v6v7235195833862(0,0)(2,1)(4,2)10,515,5(3

,1)(7

,3)(10,5)(15,5)第二十五页，共一百五十五页，编辑于2023年，星期二最小树与最短路v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)(10,5)（15,5）(3,1)(7,3)v1v2v3v4v5v6v7235195833862(0,0)(2,1)(4,2)（10,5）（15,5）(3

,1)(7

,3)第二十六页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v72351958338620,0¥,M¥,M¥,M¥,M¥,M¥,M(0,0)2,13,15,1(0,0)(2,1)4,2(2,1)(3,1)8,4(3,1)11,2(4,2)(4,2)7,3(7,3)(7,3)10,515,5(10,5)(15,5)(10,5)(15,5)第二十七页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v72351958338620,0¥,M¥,M¥,M¥,M¥,M¥,Mv1v2v3v4v5v6v72351958338620,0¥,M¥,M¥,M¥,M¥,M¥,M(0,0)2,15,13,1第二十八页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v7235195833862(0,0)(2

,1)4,211,2¥

,M3,1¥,Mv1v2v3v4v5v6v7235195833862(0,0)2,15,1¥,M¥,M3

,1¥,M(2,1)8,4(3,1)4,211,2第二十九页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)11,2¥

,M(3,1)7,3v1v2v3v4v5v6v7235195833862(0,0)(2,1)4,211,2¥,M(3

,1)8

,4(7,3)(4,2)7,310,515,5第三十页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)(10,5)15,5(3,1)(7,3)v1v2v3v4v5v6v7235195833862(0,0)(2,1)(4,2)10,515,5(3

,1)(7

,3)(10,5)(15,5)第三十一页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v72351958338620,0¥,M¥,M¥,M¥,M¥,M¥,M(0,0)2,13,15,1(0,0)(2,1)4,2(2,1)(3,1)8,4(3,1)11,2(4,2)(4,2)7,3(7,3)(7,3)10,515,5(10,5)(15,5)(10,5)(15,5)第三十二页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v72351958338620,0¥,M¥,M¥,M¥,M¥,M¥,M(0,0)2,13,15,1(0,0)(2,1)4,2(2,1)(3,1)8,4(3,1)11,2(4,2)(4,2)7,3(7,3)(7,3)10,515,5(10,5)(15,5)(10,5)(15,5)第三十三页，共一百五十五页，编辑于2023年，星期二最小树与最短路v1v2v3v4v5v6v7235195833862(0,0)(2

,1)(4,2)(10,5)（15,5）(3,1)(7,3)(0,0)(2,1)(4,2)（10,5）（15,5）(3

,1)(7

,3)v1v2v3v4v5v6v7235195833862第三十四页，共一百五十五页，编辑于2023年，星期二应用举例

例8.第三十五页，共一百五十五页，编辑于2023年，星期二第三十六页，共一百五十五页，编辑于2023年，星期二网络模型的要素设置用点vi代表第i年年初i=1~6;用弧(vi

,

vi)表示第i年年初购买一台新设备用到第j年年初报废j=(i+1)~n；用弧的权wij作为设备的购置费与维修费之和如w13=c1+(d1+d2)=11+(5+6)=22wij=ci+j-it1å=dt第三十七页，共一百五十五页，编辑于2023年，星期二设备更新问题的网络模型v1v2v3v4v5v6161617171822304159222330314123第三十八页，共一百五十五页，编辑于2023年，星期二设备更新问题的网络模型v1v2v3v4v5v61616171718223041592223303141第三十九页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6161617171822304159222330314123第四十页，共一百五十五页，编辑于2023年，星期二第四十一页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v7v863822-111-26-1-1-3-2-5-31第四十二页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v7v8第四十三页，共一百五十五页，编辑于2023年，星期二v1v2v3v4v5v6v7v8第四十四页，共一百五十五页，编辑于2023年，星期二第四十五页，共一百五十五页，编辑于2023年，星期二迭代算法d(vs,vj)=min{d

(vs,vi)+wij|iV}(i)当t=1，令

d(1)(vs,vj)=wsj,jV(ii)对t=2,3,…,使

d(t)(vs,vj)=min{d(t-1)(vs,vi)+wij|iV},jV(iii)若

t=k，有

d(k)(vs,vj)=d(k-1)(vs,vj),jV

则{d(k)(vs,vj)|jV}即为vs到各点vj的最短路的权。第四十六页，共一百五十五页，编辑于2023年，星期二wij算例第四十七页，共一百五十五页，编辑于2023年，星期二wij算例第四十八页，共一百五十五页，编辑于2023年，星期二wij算例第四十九页，共一百五十五页，编辑于2023年，星期二最短路路径v1v2v3v4v5v6v7v863822-111-26-1-1-3-2-5-31第五十页，共一百五十五页，编辑于2023年，星期二8.5网络最大流问题

在图论的应用中，特别是在交通运输、信息传递方面，网络最大流问题占有重要地位。这个问题也是网络理论的中心问题之一。第五十一页，共一百五十五页，编辑于2023年，星期二vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)运输网络第五十二页，共一百五十五页，编辑于2023年，星期二vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)8.5.1问题的提出输送量是否可以增加？输送量究竟能增加到多大？第五十三页，共一百五十五页，编辑于2023年，星期二8.5.2问题的形式基本概念容量网络网络流及弧流量点的流量发点和收点带发、收点的容量网络可行流问题的数学模型第五十四页，共一百五十五页，编辑于2023年，星期二容量网络

给定一个有向图D=(V,A)，对D中每一条弧(vi,vj)

A

，赋一个非负的容量c(vi,vj)≥0(或简写为cij)，记C={cij}。D和C构成的网络称为容量网络，记作D=(V,A,C)。vsvtv2v4v1v3cs1=3cs2=6c12=5c24=4c41=1c13=5c43=2c3t=6c4t=3第五十五页，共一百五十五页，编辑于2023年，星期二网络流及弧流量

一个容量网络D，给出一个运输方案，则D中每条弧(vi,vj)上的运输量叫作这条弧的弧流量，记作f(vi,vj)(简写为fij)，所有弧的弧流量组成的集合f={fij}称为一个网络流，简记为f。一个网络流f表示容量网络D

上一个运输方案。vsvtv2v4v1v3fs1=3fs2

=2

f12=2

f24=4

f41=1

f13=2f43=0

f3t

=2

f4t

=3

第五十六页，共一百五十五页，编辑于2023年，星期二网络流模型C={cs1=4,cs2=6,c12=5,…,c3t=6,c4t=3}f={fs1=3,fs2=2,f12=2,…,f3t=2,c4t=3}vsvtv2v4v1v3(cs1,fs1)(cs2,fs2)(c12,f12)(c24,f24)(c41,f41)(c13,f13)(c43,f43)(c3t,f3t

)(c4t,f4t

)第五十七页，共一百五十五页，编辑于2023年，星期二vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)网络流模型(算例)C={cs1=4,cs2=6,c12=5,…,c3t=6,c4t=3}f={fs1=3,fs2=2,f12=2,…,f3t=2,c4t=3}第五十八页，共一百五十五页，编辑于2023年，星期二点的流量

以点vi作为起点的弧的集合记作(vi,V

)，这些弧的流量之和称为点vi的流出量，记作f(vi,V

)，即

以点vi作为终点的弧的集合记作(V,vi),这些弧的流量之和称为点vi的流入量，记作f(V,vi)，即

点vi的流出量与流入量之差称为点vi的(净)流量，即

f(vi,V

)-

f(V,vi)f(vi,V

)=fijå(vi,vj)Î(vi,V

)

f(V,vi

)=fjiå(vj,vi)Î(V,

vi)

第五十九页，共一百五十五页，编辑于2023年，星期二点的流量举例(v1,V)={(v1,v2),(v1,v3)}(V,v1

)={(vs

,v1),(v4,v1)}点v1的流出量：f(v1,V)=f12+f13=2+2=4点v1的流入量：f(V,v1

)=fs1+f41=3+1=4点v1的(净)流量：f(v1,V)-f(V,v1

)=4-4=

0vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)第六十页，共一百五十五页，编辑于2023年，星期二

发点和收点第六十一页，共一百五十五页，编辑于2023年，星期二发点和收点举例收点vt

:(vt

,V)=

,

(V,vt);f(vt

,V)=0,f(V,vt)0.vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)发点vs

:(vs

,V),

(V,vs)=;f(vs

,V)0,f(V,vs)=0.第六十二页，共一百五十五页，编辑于2023年，星期二带发、收点的容量网络第六十三页，共一百五十五页，编辑于2023年，星期二可行流

若网络上的一个流f={fij}满足下述条件：

(i)容量限制条件：对每条弧(vi,vj)

A

，

0≤

fij≤

cij

(ii)平衡条件：对每个中间点vi

A(i

s,t

)f(vi,V

)-

f(V,vi)=0

则f称为一个可行流，而发点的流出量(或收点的流入量)称为f的流量，记为v(f)或v

，即

v(f)=

f(vs,V

)

或

v(f)=

f(V,vt)第六十四页，共一百五十五页，编辑于2023年，星期二最大流问题的数学模型maxv(f)=

f(vs,V

)s.t.f(vi,V

)-

f(V,vi)=0(i

s,t

)0≤fij≤

cij

第六十五页，共一百五十五页，编辑于2023年，星期二数学模型举例maxv=fs1

+fs2s.t.f12+f13

-fs1-f41=0f24-fs2-f12=0f3t-f13-f43=0f41+f43+f4t

-f24=00≤

fij≤

cijvsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)第六十六页，共一百五十五页，编辑于2023年，星期二最大流问题与线性规划问题网络最大流问题平衡条件容量限制条件流量式可行流流的弧流量最大流最大流量中间点的个数弧的条数线性规划问题约束方程变量限制条件目标函数可行解解的分量最优解最优值约束方程的个数变量的个数第六十七页，共一百五十五页，编辑于2023年，星期二8.5.3问题的求解第六十八页，共一百五十五页，编辑于2023年，星期二1.求增广链的标号法第六十九页，共一百五十五页，编辑于2023年，星期二饱和弧与零流弧

给出一个可行流f={fij}，按照弧流量与其上界或下界的关系，可将弧分类：若fij=cij，则弧(vi

,vj

)称为饱和弧；否则，fij<cij，弧(vi

,vj

)称为非饱和弧。若fij=0，则弧(vi

,vj

)称为零流弧；否则，fij

>0，弧(vi

,vj

)称为非零流弧。

饱和弧必定是非零流弧，反之不然；零流弧必定是非饱和弧，反之不然。第七十页，共一百五十五页，编辑于2023年，星期二vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)饱和弧与零流弧举例零流弧：(v4,v3)非零流弧：其余的弧饱和弧：(v2,v4),(v4,v1),(v4,vt)非饱和弧:其余的弧第七十一页，共一百五十五页，编辑于2023年，星期二前向弧与后向弧第七十二页，共一百五十五页，编辑于2023年，星期二vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)前向弧与后向弧举例

=(vs,v2,v1,v3,vt)+={(vs,v2),(v1,v3),(v3,vt)}-={(v1,v2)}第七十三页，共一百五十五页，编辑于2023年，星期二增广链

定义设f是一个可行流，是从vs到vt的一条链，若满足下述条件，称之为(关于可行流f

的)一条增广链。+中每一条弧是非饱和弧；-中每一条弧是非零流弧。vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)第七十四页，共一百五十五页，编辑于2023年，星期二可行流f={fij}的调整对于可行流f={fij}，若存在增广链，则可对f的弧流量fij作如下调整：确定调整量，令1=min{cij-

fij|(vi

,vj

)+}2=min{fij|(vi

,vj

)-}=min{1,

2}调整弧流量fij，令

fij+

(vi

,vj

)+fij-

(vi

,vj

)-fij

(vi

,vj

)fij´=第七十五页，共一百五十五页，编辑于2023年，星期二可行流调整举例可行流的增广链

=(vs,v2,v1,v3,vt)+={(vs,v2),(v1,v3), (v3,vt)}-={(v1,v2)}确定调整量，令1=min{cs2

-

fs2,

c13

-

f13,

c3t-

f3t

}=min{6-2,5-2,6-2}=32=min{f12}=min{2

}=2=min{3

,

2

}=2vsvtv2v4v1v3(4,3)(6,2+2)(5,2-2)(4,4)(1,1)(5,2+2

)(2,0)(6,2+2)(3,3)第七十六页，共一百五十五页，编辑于2023年，星期二网络流f´={fij´}的验证对于调整后的网络流f´={fij´}，不难验证f´={fij´}是一个可行流v(f´)=v(f)+>v(f)

fsl+flm+fnm-fnt+vsvlvmvnvt第七十七页，共一百五十五页，编辑于2023年，星期二找增广链的标号法

对于可行流f={fij}，可用下述标号找增广链。

(0)首先给发点vs标号“

0”。

(1)选取标号无括号的点vi，如果这样的点不存在，则没有关于可行流f的增广链；否则，转(2)。

(2)检查选取的点vi：

(i)对于所有以vi为起点的弧(vi

,vj

)，若fij<cij且终点vj

没有标号，则给vj标号“+vi”；

(ii)对于所有以vi为终点的弧(vk,vi

)，若fki

>0且起点vk

没有标号，则给vk标号“-vi”；

(iii)给点vi的标号打上括号，转(3)。

(3)若收点vs被标号，则依据标号采用“反向追踪”的方法找出可行流f

的增广链；否则，转(1)。第七十八页，共一百五十五页，编辑于2023年，星期二找增广链的标号法

对于可行流f={fij}，可用下述标号找增广链。

(0)首先给发点vs标号“

0”。

(1)选取标号无括号的点vi，如果这样的点不存在，则没有关于可行流f

的增广链；否则，转(2)。

(2)检查选取的点vi：

(i)对于所有以vi为起点的弧(vi

,vj

)，若fij<cij且终点vj

没有标号，则给vj标号“+vi”；

(ii)对于所有以vi为终点的弧(vk,vi

)，若fki

>0且起点vk

没有标号，则给vk标号“-vi”；

(iii)给点vi的标号打上括号，转(3)。

(3)若收点vs被标号，则依据标号采用“反向追踪”的方法找出可行流f

的增广链；否则，转(1)。第七十九页，共一百五十五页，编辑于2023年，星期二0+vs+vs+v1-v1+v3标号法找增广链(正向标号)(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)vsvtv2v4v1v3第八十页，共一百五十五页，编辑于2023年，星期二vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)0+vs+vs+v1-v1+v3标号法找增广链(反向追踪)第八十一页，共一百五十五页，编辑于2023年，星期二0,+¥-v2,2+vs

,4+v1,2-v1,1+v3,2vsvtv2v4v1v3(4,4)(6,2)(5,2)(4,4)(1,1)(5,3)(2,0)(6,3)(3,3)标号法找增广链(之二)第八十二页，共一百五十五页，编辑于2023年，星期二vsvtv2v4v1v3(4,4)(6,4)(5,0)(4,4)(1,1)(5,5)(2,0)(6,5)(3,3)0,+¥+vs

,2标号法找增广链(之三)第八十三页，共一百五十五页，编辑于2023年，星期二2.最大流算法(Ford,Fulkerson)

步1

给出初始可行流f={fij}，(一般为零流，即fij=0)；

步2

用标号法找当前可行流f的增广链

，若不存在关于f的增广链

，则f为最大流，计算停止。否则，记中的前向弧为+、后向弧为-；

步3

对当前可行流f进行调整，令=min{min{cij-

fij|aij

+},

min{fij|aij

-}}

得到新的可行流f´={fij´

}(以f´代替f)，转步2。

fij+

(vi

,vj

)+fij-

(vi

,vj

)-fij

(vi

,vj

)fij´=第八十四页，共一百五十五页，编辑于2023年，星期二11,012,06,06,03,06,09,05,03,08,0v4vsvtv1v6v3v2v50第八十五页，共一百五十五页，编辑于2023年，星期二11,012,06,06,03,06,09,05,03,08,0v4vsvtv1v6v3v2v50,+¥+vs,12+vs,6+v1,11+v2,6+v2,6+v3,3+v4,61第八十六页，共一百五十五页，编辑于2023年，星期二11,012,06,66,03,06,69,65,03,08,0v4vsvtv1v6v3v2v520,+¥+vs,12+v1,11+v3,8+v3,3+v4,3第八十七页，共一百五十五页，编辑于2023年，星期二11,312,36,66,03,06,69,95,03,08,3v4vsvtv1v6v3v2v530,+¥+vs,9+v1,8+v3,5+v3,3+v6,3-v4,5第八十八页，共一百五十五页，编辑于2023年，星期二11,612,66,66,03,36,69,95,33,08,3v4vsvtv1v6v3v2v50,+¥+vs,6+v1,5+v3,5+v5,3-v4,5+v2,54第八十九页，共一百五十五页，编辑于2023年，星期二11,912,96,36,33,36,69,95,33,38,6v4vsvtv1v6v3v2v550,+¥+vs,3+v1,2+v3,2-v4,2第九十页，共一百五十五页，编辑于2023年，星期二8.5.4问题的论证

截集与最大流

增广链与最大流第九十一页，共一百五十五页，编辑于2023年，星期二1.截集与最大流设ST=V,ST=，则S,T称为V的一个剖分；并把始点在S中，终点在T中的所有弧的集合记为(S,T)。vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)ST第九十二页，共一百五十五页，编辑于2023年，星期二截集

定义8.6对于容量网络D=(V,A,C)，若D的点集V被剖分为两个非空的子集Vk和Vk

，使vsVk,vtVk

，则把弧集(Vk,Vk

)称为D

中(分离vs和vt)的截集。

vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)VkVk第九十三页，共一百五十五页，编辑于2023年，星期二必经之道

定义8.6对于容量网络D=(V,A,C)，若D的点集V被剖分为两个非空的子集Vk和Vk，使vsVk，vtVk

，则把弧集(Vk,Vk

)称为D

中(分离vs和vt)的截集。

vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)VkVk第九十四页，共一百五十五页，编辑于2023年，星期二第九十五页，共一百五十五页，编辑于2023年，星期二截量

定义8.6对于截集(Vk,Vk

)，把截集(Vk,Vk)中所有弧的容量之和称为这个截集的容量(简称为截量)，记为c(Vk,Vk

)，即相应地，把截集(Vk,Vk)中所有弧的流量之和记为f(Vk,Vk

)，即cijå(vi,vj)Î(Vk,Vk)c

(Vk,Vk

)=fijå(vi,vj)Î(Vk,Vk)f

(Vk,Vk

)=第九十六页，共一百五十五页，编辑于2023年，星期二截集及其截量V1={vs

,v1

,v2},V1={v3,v4

,vt

}(V1

,V1)={(v1

,v3),(v2

,v4)}c(V1,V1

)=c13+c24=5+4=9f(V1,V1

)=f13+f24=2+4=6vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)第九十七页，共一百五十五页，编辑于2023年，星期二vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)截集的分划V1={vs

,v1

,v2},V1={v3,v4

,vt

}(V1

,V1)={(v1

,v3),(v2

,v4)}c(V1,V1

)=c13+c24=5+4=9f(V1,V1

)=f13+f24=2+4=6第九十八页，共一百五十五页，编辑于2023年，星期二vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)截集及其截量(二)V2={vs

,v1

,v2,v3},V2={v4

,vt

}(V2

,V2)={(v2

,v4),(v1

,v3)}c(V2,V2

)=c24+c3t=4+6=10f(V2,V2

)=f24+f3t=4+2=6第九十九页，共一百五十五页，编辑于2023年，星期二截集的计数Cp-2åi=0ip-2第一百页，共一百五十五页，编辑于2023年，星期二vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)截集与反向弧V1={vs

,v1

,v2},V1={v3,v4

,vt

}(V1

,V1)={(v1

,v3),(v2

,v4)}(V1,V1)={(v4

,v1)}c(V1,V1)=f41=1第一百零一页，共一百五十五页，编辑于2023年，星期二流量与截量

定理8.6对于容量网络D，设

f={fij}是任一可行流，(Vk,Vk

)是任一截集，则

v(f)

≤

c(Vk,Vk

)第一百零二页，共一百五十五页，编辑于2023年，星期二最大流与最小截集

推论8.6设f*={f*ij}是D上的一个可行流，(Vk*,Vk*)是一个截集，若

v(f*)

=

c(Vk*,Vk*)

则f*是最大流，而(Vk*,Vk*)是最小截集。第一百零三页，共一百五十五页，编辑于2023年，星期二2.增广链与最大流

定理8.6可行流f*是最大流的充分必要条件是，不存在关于f*的增广链。第一百零四页，共一百五十五页，编辑于2023年，星期二最大流量与最小截集量第一百零五页，共一百五十五页，编辑于2023年，星期二截集及其截量V1={vs

,v1

,v2},V1={v3,v4

,vt

}(V1

,V1)={(v1

,v3),(v2

,v4)}c(V1,V1

)=c13+c24=5+4=9f(V1,V1

)=f13+f24=2+4=6vsvtv2v4v1v3(4,3)(6,2)(5,2)(4,4)(1,1)(5,2)(2,0)(6,2)(3,3)第一百零六页，共一百五十五页，编辑于2023年，星期二8.5.5网络等价变换第一百零七页，共一百五十五页，编辑于2023年，星期二1.无向网络vivjc(vi,vj)vivjcij=c(vi,vj)

cji

=c(vi,vj)

第一百零八页，共一百五十五页，编辑于2023年，星期二2.顶点具有容量vic(vi)vi’vi”c(vi’,vi”)=

c(vi)第一百零九页，共一百五十五页，编辑于2023年，星期二多个源或汇vsvtvs1vs2vt1vt2vt3+¥+¥+¥+¥+¥第一百一十页，共一百五十五页，编辑于2023年，星期二作业

求网络D的最大流和最小截集。1312629436582v5vsvtv2v3v4v1v6第一百一十一页，共一百五十五页，编辑于2023年，星期二8.6最小费用最大流问题bs1

,cs1vsvtv1v2v3b23

,c23bs2

,cs2b21

,c21b13

,c13b1t,c1tb3t

,c3t第一百一十二页，共一百五十五页，编辑于2023年，星期二vsvtv1v2v34

,103

,101

,82,56

,21,72

,4vsvtv1v2v34

,103

,101

,82,56

,21,72

,44

,103

,101

,82,56

,21,72

,4vsvtv1v2v3第一百一十三页，共一百五十五页，编辑于2023年，星期二vsvtv1v2v3431-2612vsvtv1v2v34

,103

,101

,82,56

,21,72

,4vsvtv1v2v30055050-1-1第一百一十四页，共一百五十五页，编辑于2023年，星期二vsvtv1v2v343-26-12vsvtv1v2v34

,103

,101

,82,56

,21,72

,4vsvtv1v2v320550701-1-4第一百一十五页，共一百五十五页，编辑于2023年，星期二vsvtv1v2v34

,103

,101

,82,56

,21,72

,4vsvtv1v2v34

,103

,101

,82,56

,21,72

,4vsvtv1v2v34

,103

,101

,82,56

,21,72

,4第一百一十六页，共一百五十五页，编辑于2023年，星期二vsvtv1v2v34

,103

,101

,82,56

,21,72

,4vsvtv1v2v34

,103

,101

,82,56

,21,72

,4vsvtv1v2v34

,103

,101

,82,56

,21,72

,4第一百一十七页，共一百五十五页，编辑于2023年，星期二5.计算机方法简介第一百一十八页，共一百五十五页，编辑于2023年，星期二5.计算机方法简介第一百一十九页，共一百五十五页，编辑于2023年，星期二露天矿鸟瞰（三维模型）第一百二十页，共一百五十五页，编辑于2023年，星期二矿床块段模型第一百二十一页，共一百五十五页，编辑于2023年，星期二矿床经济模型

ji1234567891-1-1-2-1-1-1-1-102-1-1-211.85.2-23153-11.540.50.60.7第一百二十二页，共一百五十五页，编辑于2023年，星期二露天矿开采模型

j