经济学Ch6网络模型课件

运筹学

Operations

ResearchChapter6网络模型NetworkModeling6.1最小(支撑)树问题Minimal(Spanning)TreeProblem6.2最短路问题ShortestPathProblem

6.3最大流问题MaximalFlowProblem

5v1v2v3v4v5v6843752618图6－1运筹学中研究的图具有下列特征：（1）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系。（2）强调点与点之间的关联关系，不讲究图的比例大小与形状。（3）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义。（4）建立一个网络模型，求最大值或最小值。5v1v2v3v4v5v6843752618图6－1运筹学中边用[vi,vj]表示或简记为[i，j]，集合记为如图6－1所示，点集合记为边上的数字称为权，记为w[vi,vj]、w[i，j]或wij，集合记为连通的赋权图称为网络图，记为G＝｛V，E，W｝5v1v2v3v4v5v6843752618图6－1边用[vi,vj]表示或简记为[i，j]，集合记为如图6－16.1最小(支撑)树问题

Minimal(Spanning)TreeProblem6.1最小(支撑)树问题6.1.1树的概念一个无圈并且连通的无向图称为树图或简称树(Tree)。组织机构、家谱、学科分支、因特网络、通讯网络及高压线路网络等都能表达成一个树图。可以证明：（1）一棵树的边数等于点数减1；（2）在树中任意两个点之间添加一条边就形成圈；（3）在树中去掉任意一条边图就变为不连通。在一个连通图G中，取部分边连接G的所有点组成的树称为G的部分树或支撑树(SpanningTree

)。图6－2是图6－1的部分树。v1v2v3v4v5v64321图6－276.1最小树问题

Minimaltreeproblem6.1.1树的概念一个无圈并且连通的无向图称为树图或简称树6.1.2最小部分树将网络图G边上的权看作两点间的长度（距离、费用、时间），定义G的部分树T的长度等于T中每条边的长度之和，记为C(T)。G的所有部分树中长度最小的部分树称为最小部分树，或简称为最小树。最小部分树可以直接用作图的方法求解，常用的有破圈法和加边法。破圈法：任取一圈，去掉圈中最长边，直到无圈。6.1最小树问题

Minimaltreeproblem6.1.2最小部分树将网络图G边上的权看作两点间的长度（距5v1v2v3v4v5v6843752618图6－1【例6-1】用破圈法求图6－1的最小树。图6－4图6－4就是图6－1的最小部分树，最小树长为C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同6.1最小树问题

Minimaltreeproblem5v1v2v3v4v5v6843752618图6－1【例6-加边法：取图G的n个孤立点｛v1，v2，…，vn}作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n－1条边）

v1v2v3v4v5v643521图6－5在图6－5中，如果添加边[v1,v2]就形成圈｛v1,v2,v4｝，这时就应避开添加边[v1,v2]，添加下一条最短边[v3,v6]。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等5v1v3v515v2v4v684375268×MinC(T)=156.1最小树问题

Minimaltreeproblem【例6-2】用加边法求图6－1的最小树图6－1加边法：取图G的n个孤立点｛v1，v2，…，vn}作为一个下一节：最短路问题1.树、支撑树、最小支撑树的概念2.掌握求最小树的方法：（1）破圈法（2）加边法6.1最小树问题

Minimaltreeproblem下一节：最短路问题1.树、支撑树、最小支撑树的概念6.1最6.2最短路问题ShortestPathProblem6.2最短路问题最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题求最短路有两种算法：一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德)矩阵算法。最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路6.2.1最短路问题的网络模型6.2最短路问题ShortestPathProblem

最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题①②③④⑤⑥⑦610123214675811165图6－69【例6-3】图6－6中的权cij表示vi到vj的距离（费用、时间），从v1修一条公路或架设一条高压线到v7，如何选择一条路线使距离最短，建立该问题的网络数学模型。6.2最短路问题ShortestPathProblem

①②③④⑤⑥⑦610123214675811165图6－69【解】设xij为选择弧(i，j)的状态变量，选择弧(i，j)时xij＝1，不选择弧(i，j)时xij＝0，得到最短路问题的网络模型：6.2最短路问题ShortestPathProblem

【解】设xij为选择弧(i，j)的状态变量，选择弧(i，j6.2.2有向图的狄克斯屈拉(Dijkstra)标号算法点标号：b(j)—起点vs到点vj的最短路长；边标号：k(i，j)=b(i)+cij，步骤：(1)令起点的标号；b(s)＝0。先求有向图的最短路，设网络图的起点是vs,终点是vt,以vi为起点vj为终点的弧记为（i，j）,距离为cij(2)找出所有vi已标号vj未标号的弧集合B={(i，j)}，如果这样的弧不存在或vt已标号则计算结束；(3)计算集合B中弧k(i，j)=b(i)+cij的标号(4)选一个点标号返回到第(2)步。6.2最短路问题ShortestPathProblem

6.2.2有向图的狄克斯屈拉(Dijkstra)标号算法点标②③④⑤⑥⑦610123214675811165图6－690610129209186①161217162432182929【例6-4】用Dijkstra算法求图6－6所示v1到v7的最短路及最短路长v1到v7的最短路为：p17=｛v1,v2,v3,v5,v7｝，最短路长为L17=296.2最短路问题ShortestPathProblem

14②③④⑤⑥⑦610123214675811165图6－690从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj。6.2.3无向图最短路的求法无向图最短路的求法只将上述步骤（2）改动一下即可。点标号：b(i)—起点vs到点vj的最短路长；边标号：k(i，j)=b(i)+cij，步骤：(1)令起点的标号；b(s)＝0。(3)计算集合B中边标号：k[i，j]=b(i)+cij(4)选一个点标号:返回到第(2)步。(2)找出所有一端vi已标号另一端vj未标号的边集合B={[i，j]}如果这样的边不存在或vt已标号则计算结束；6.2最短路问题ShortestPathProblem

从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线【例6-5】求图6-10所示v1到各点的最短路及最短距离①②③④⑤⑥⑦⑧4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。图6-106.2最短路问题ShortestPathProblem

【例6-5】求图6-10所示v1到各点的最短路及最短距离①②6.2.4最短路的Floyd算法Floyd算法基本步骤:(1)写出vi一步到达vj

的距离矩阵，L1也是一步到达的最短距离矩阵。如果vi与vj之间没有边关联，则令cij=+∞(2)计算二步最短距离矩阵。设vi到vj经过一个中间点vr两步到达vj，则vi到vj的最短距离为最短距离矩阵记为(3)计算k步最短距离矩阵。设vi经过中间点vr

到达vj，vi经过k－1步到达点vr的最短距离为，vr经过k－1步到达点vj

的最短距离为，则vi经k步

到达vj的最短距离为(6-1)6.2最短路问题ShortestPathProblem

6.2.4最短路的Floyd算法Floyd算法基本步骤最短距离矩阵记为(4)比较矩阵Lk与Lk－1，当Lk＝Lk－1时得到任意两点间的最短距离矩阵Lk。设图的点数为n并且cij≥0，迭代次数k由式(6-3)估计得到。(6-2)(6-3)6.2最短路问题ShortestPathProblem

最短距离矩阵记为(4)比较矩阵Lk与Lk－1，当Lk＝Lk63①②③④⑤⑥⑦⑧45212789326121610【例6-6】图6-14是一张8个城市的铁路交通图，铁路部门要制作一张两两城市间的距离表。这个问题实际就是求任意两点间的最短路问题。【解】(1)依据图6-14,写出任意两点间一步到达距离表L1。见表6-1所示。本例n=8，，因此计算到L3

图6-146.2最短路问题ShortestPathProblem

63①②③④⑤⑥⑦⑧45212789326121610【例6v1v2v3v4v5v6v7v8v106∞5∞4∞∞v260328∞∞∞v3∞30∞7∞∞16v452∞09123∞v5∞8790∞106v64∞∞12∞02∞v7∞∞∞3102012v8∞∞16∞6∞120表6-1最短距离表L16.2最短路问题ShortestPathProblem

v1v2v3v4v5v6v7v8v106∞5∞4∞∞v260表6-2最短距离表L2v1v2v3v4v5v6v7v8v106951446∞v26032810514v393057∞1713v4525095315v514879012106v6410∞5120214v765173102012v8∞141315614120计算说明：L(2)ij等于表6-1中第i行与第j列对应元素相加取最小值。如6.2最短路问题ShortestPathProblem

表6-2最短距离表L2v1v2v3v4v5v6v7v8v1表6-3计算示例:等于表6-2中第i行与第j列对应元素相加取最小值。例如，v3经过三步（最多三个中间点4条边）到达v6的最短距离是表6-3最短距离表L3v1v2v3v4v5v6v7v8v10695144618v2603287514v39305710813v4525095315v514879012106v647105120214v76583102012v8181413156141206.2最短路问题ShortestPathProblem

表6-3计算示例:等于表6-2中第i行与第j列对【例6-7】求图6－15中任意两点间的最短距离。【解】图6－15是一个混合图，有3条边的权是负数,有两条边无方向。依据图6－15,写出任意两点间一步到达距离表L1。表中第一列的点表示弧的起点，第一行的点表示弧的终点，无方向的边表明可以互达，见表6-4所示。计算过程见表6-5～6-7。①②③④⑤⑥⑦44574－3－271028图6－15－156.2最短路问题ShortestPathProblem

【例6-7】求图6－15中任意两点间的最短距离。①②③④⑤⑥表6-4一步到达距离表L1v1v2v3v4v5v6v7v105∞∞

4∞∞v2∞04－2∞∞∞v3∞407∞∞2v44∞∞010∞7v5－1∞∞∞0－3∞v6∞∞∞5∞08v7∞∞2∞∞∞06.2最短路问题ShortestPathProblem

表6-4一步到达距离表L1v1v2v3v4v5v6v7v10表6-7最短距离表L4v1v2v3v4v5v6v7v10593419v2204-2635v364021072v44990857v5-14720-35v69141051308v786241290经计算L4＝L5，L4是最优表。表6-7不是对称表，vi到vj与vj到vi的最短距离不一定相等。对于有负权图情形，公式(6-3)失效。6.2最短路问题ShortestPathProblem

表6-7最短距离表L4v1v2v3v4v5v6v7v1056.2.4最短路应用举例6.2最短路问题ShortestPathProblem

【例6-8】设备更新问题。企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几年后卖掉重新购置新设备。已知4年年初购置新设备的价格分别为2.5、2.6、2.8和3.1万元。设备使用了1～4年后设备的残值分别为2、1.6、1.3和1.1万元，使用时间在1～4年内的维修保养费用分别为0.3、0.8、1.5和2.0万元。试确定一个设备更新策略，在下例两种情形下使4年的设备购置和维护总费用最小。（1）第4年年末设备一定处理掉；（2）第4年年末设备不处理。【解】画网络图。用点(1,i,…,j)表示第1年年初购置设备使用到第i年年初更新，经过若干次更新使用到第j年年初，第1年年初和第5年年初分别用①及⑤表示。使用过程用弧连接起来，弧上的权表示总费用(购置费＋维护费－残值)，如图6－16所示6.2.4最短路应用举例6.2最短路问题【例6-8】设6.2最短路问题ShortestPathProblem

①⑤6图6－16(1,2,3)(1,4)(1,3,4)(1,2,4)(1,2,3,4)(1,2)(1,3)第一年第二年第三年第四年5.10.91.50.73.62.81.7-0.21.91.12.10.3-0.6-0.6网络图6－16说明：如图中点(1,3)表示第1年购置设备使用两年到第3年年初更新购置新设备，这时有2种更新方案，使用1年到第4年年初、使用2年到第5年年初,更新方案用弧表示，点（1,2,3）表示第1年购置设备使用一年到第二年年初又更新，使用一年到第三年初再更新，这时仍然有2种更新方案，使用1年到第4年年初和使用2年到第5年年初。6.2最短路问题①⑤6图6－16(1,2,3)(1,4)6.2最短路问题ShortestPathProblem

点（1,3）和点（1,2,3）不能合并成一个点，虽然都是第三年年初购置新设备，购置费用相同，但残值不同。点(1,3)的残值等于1.6(使用了两年)，点(1,2,3)的残值等于2(使用了一年)。点（1,3）到点（1,3,4）的总费用为第三年的购置费＋第一年的维护费－设备使用两年后的残值＝2.8+0.3－1.6=1.5点（1,3）到点⑤的总费用为第三年的购置费＋第一年的维护费＋第二年的维护费－设备使用两年后的残值－第四年末的残值＝2.8+0.3+0.8－1.6－1.6=0.7。费用表见教材表6-8。6.2最短路问题点（1,3）和点（1,2,3）不能合并成①⑤6图6－16(1,2,3)(1,4)(1,3,4)(1,2,4)(1,2,3,4)(1,2)(1,3)第一年第二年第三年第四年5.10.91.50.73.62.81.7-0.21.91.12.10.3-0.6-0.6①⑤6图6－16(1,2,3)(1,4)(1,3,4)(1,6.2最短路问题ShortestPathProblem

（2）第四年末不处理设备：将图6－16第4年的数据换成表6-8最后一列，求点①到点⑤的最短路。最短路线为：①→(1,2)→(1,2,3)→⑤，最短路长为5.6，即总费用为5.6万元。更新方案与第一种情形相同。（1）第四年末处理设备：求点①到点⑤的最短路。用Dijkstra算法得到最短路线为：①→(1,2)→(1,2,3)→⑤，最短路长为4。4年总费用最小的设备更新方案是：第1年购置设备使用1年，第2年更新设备使用1年后卖掉，第3年购置设备使用2年到第4年年末，4年的总费用为4万元。6.2最短路问题（2）第四年末不处理设备：将图6－16第【例6-9】服务网点设置问题。以图6－14为例，现提出这样一个问题，在交通网络中建立一个快速反应中心，应选择哪一个城市最好。类似地，在一个网络中设置一所学校、医院、消防站、购物中心，还有厂址选择、总部选址、公司销售中心选址等问题都属于最佳服务网点设置问题。【解】对于不同的问题，寻求最佳服务点有不同的标准。像图6－14只有两点间的距离，可以采用“使最大服务距离达到最小”为标准，计算步骤如下。第一步：利用Floyd算法求出任意两点之间的最短距离表（表6－3）。第二步：计算最短距离表中每行的最大距离的最小值，即6.2最短路问题ShortestPathProblem

【例6-9】服务网点设置问题。以图6－14为例，现提出这样一引用例6-6计算的结果，对表6－3每行取最大值再取最小值，见表6－9倒数第二列。v1v2v3v4v5v6v7v8MaxLij总运量v10695144618183220v2603287514142465v39305710813132955v4525095315152450v514879012106143780v647105120214142960v76583102012122560v818141315614120185040产量8050704030356065表6－9表6－9中倒数第二列最小值为12，位于第7行，则v7为网络的中心，最佳服务点应设置在v7。6.2最短路问题ShortestPathProblem

引用例6-6计算的结果，对表6－3每行取最大值再取最小值，见如果每个点还有一个权数，例如一个网点的人数、需要运送的物质数量、产量等，这时采用“使总运量最小”为标准，计算方法是将上述第二步的最大距离改为总运量，总运量的最小值对应的点就是最佳服务点。表6－9中最后一行是点vj的产量，将各行的最小距离分别乘以产量求和得到总运量，例如，0×80＋6×50＋…＋18×65＝3220，见表6－9最后一列，最小运量为2450，最佳服务点应设置在v4。6.2最短路问题ShortestPathProblem

如果每个点还有一个权数，例如一个网点的人数、需要运送的物质数下一节：最大流问题6.2最短路问题ShortestPathProblem

1.最短路的概念及应用。2.有向图、无向图一点到各点最短路的Dijkstra算法3.任意两点最短路的Floyd算法4.本节介绍了两个应用：设备更新问题和最佳服务点设置问题下一节：最大流问题6.2最短路问题1.最短路的概念及应用6.3最大流问题MaximalFlowProblem6.3最大流问题6.3最大流问题MaximalFlowProblem6.3.1基本概念①②③④⑤⑥814563381076⑦3图6－184图6－18所示的网络图中定义了一个发点v1，称为源(source，supplynode），定义了一个收点v7，称为汇（sink，demandnode），其余点v2，v3，…，v6为中间点，称为转运点(transshipmentnodes)。如果有多个发点和收点，则虚设发点和收点转化成一个发点和收点。图中的权是该弧在单位时间内的最大通过能力，称为弧的容量(capacity)。最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。6.3最大流问题6.3.1基本概念①②③④⑤⑥81456设cij为弧（i，j）的容量，fij为弧（i，j）的流量。容量是弧（i，j）单位时间内的最大通过能力，流量是弧（i，j）单位时间内的实际通过量，流量的集合f={fij}称为网络的流。发点到收点的总流量记为v=val(f)，v也是网络的流量。图6－18最大流问题的线性规划数学模型为6.3最大流问题MaximalFlowProblem设cij为弧（i，j）的容量，fij为弧（i，j）的流量。图满足下例3个条件的流fij的集合f={fij

}称为可行流发点vs流出的总流量等于流入收点vt的总流量6.3最大流问题MaximalFlowProblem满足下例3个条件的流fij的集合f={fij}称为链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。前向弧：与链的方向相同的弧称为前向弧。后向弧：与链的方向相反的弧称为后向弧。增广链:设f是一个可行流，如果存在一条从vs到vt的链，满足：1.所有前向弧上fij<Cij2.所有后向弧上fij>0则该链称为增广链①②③④⑤⑥前向弧后向弧容量流量这是一条增广链84469（5）(2)(3)(4)(6)6.3最大流问题MaximalFlowProblem链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从步骤如下：第二步：对点进行标号找一条增广链。（1）发点标号（∞）（2）选一个点vi已标号并且另一端未标号的弧沿着某条链向收点检查：A．如果弧的方向向前（前向弧）并且有fij<cij，则vj标号:θj＝cij－fijB．如果弧的方向指向vi（后向弧）并且有fji>0，则vj标号:

θj＝fji当收点已得到标号时，说明已找到增广链，依据vi

的标号反向跟踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算结束。第一步：找出第一个可行流，例如所有弧的流量fij

=06.3.2Ford-Fulkerson标号算法6.3最大流问题MaximalFlowProblem步骤如下：第二步：对点进行标号找一条增广链。第一步：找出第第三步：调整流量（1）求增广链上点vi

的标号的最小值，得到调整量（2）调整流量得到新的可行流f1，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止【定理6.1】可行流f是最大流的充分必要条件是不存在发点到收点的增广链6.3最大流问题MaximalFlowProblem第三步：调整流量（2）调整流量得到新的可行流f1，去掉所有标①②③④⑤⑥814563381076⑦3图6－19(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)【例6-10】求图6－18发点v1到收点v7的最大流及最大流量【解】给定初始可行流，见图6-196.3最大流问题MaximalFlowProblem①②③④⑤⑥814563381076⑦3图6－19(10)(①②③④⑤⑥814563381076⑦3图6－20(b)(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)∞2337第一轮标号：c12>f12,v2标号2cij=fij，v4、v5不能标号后向弧f32>0,v3标号θ3=f32增广链μ＝{(1,2)，(3,2)，(3,4)，(4,7)},μ+={(1,2)，(3,4)，(4,7)},μ－={(3，2)}，调整量为增广链上点标号的最小值θ＝min{∞，2，3，3，7}＝26.3最大流问题MaximalFlowProblem①②③④⑤⑥814563381076⑦3图6－20(b)(1①②③④⑤⑥814563381076⑦3图6－21(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)调整后的可行流：6.3最大流问题MaximalFlowProblem①②③④⑤⑥814563381076⑦3图6－21(10)(①②③④⑤⑥814563381076⑦3图6－22(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)∞4415第二轮标号：Cij=fij，v4、v5不能标号，返回到v3增广链μ＝μ＋＝{(1,3)，(3,4)，(4,7)}，调整量为θ＝min{∞，4，1，5}＝16.3最大流问题MaximalFlowProblem①②③④⑤⑥814563381076⑦3图6－22(10)(①②③④⑤⑥814563381076⑦3图6－23(11)(8)(1)(6)(3)(7)(3)(6)(1)4(6)(1)(7)调整后得到可行流：6.3最大流问题MaximalFlowProblem①②③④⑤⑥814563381076⑦3图6－23(11)(①②③④⑤⑥814563381076⑦3图6－22(11)(8)(1)(6)(3)(7)(3)(6)(1)4(6)(1)(7)∞314第三轮标号：增广链μ＝μ＋＝{(1,3)，(3,6)，(6,4)，(4,7)}，调整量为θ＝min{∞，3，1，2，4}＝126.3最大流问题MaximalFlowProblem①②③④⑤⑥814563381076⑦3图6－22(11)(①②③④⑤⑥814563381076⑦3图6－25(12)(8)(1)(6)(3)(8)(3)(6)(2)4(7)(1)(7)调整后得到可行流：6.3最大流问题MaximalFlowProblem①②③④⑤⑥814563381076⑦3图6－25(12)(①②③④⑤⑥814563381076⑦3图6－22(12)(8)(1)(6)(3)(8)(3)(6)(2)4(7)(1)(7)∞2第四轮标号：v7得不到标号，不存在v1到v7的增广链，图6-22所示的可行流是最大流，最大流量为v＝f12+f13＝8+12=20Cij=fij，v4、v5不能标号Cij=fij，v4、v6不能标号46.3最大流问题MaximalFlowProblem①②③④⑤⑥814563381076⑦3图6－22(12)(无向图最大流标号算法无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端vi已标号另一端vj未标号的边只要满足Cij－fij>0则vj就可标号（Cij－fij）【例】求下图v1到则v7标的最大流7①②③④⑤⑥⑦1292085148691316(10)(6)(10)(8)(2)(3)(7)(6)(5)(13)(0)(13)∞239936.3最大流问题MaximalFlowProblem无向图最大流标号算法无向图不存在后向弧，可以理解为所有弧都是7①②③④⑤⑥⑦1292085148691316(12)(6)(10)(8)(4)(3)(7)(6)(7)(13)(2)(15)∞37717①②③④⑤⑥⑦1292085148691316(12)(7)(10)(8)(4)(3)(7)(6)(8)(13)(3)(16)V=29∞105666.3最大流问题MaximalFlowProblem17①②③④⑤⑥⑦1292085148691316(12)(6截集将图G＝（V，E）的点集分割成两部分称为一个截集，截集中所有弧的容量之和称为截集的截量。①②③④⑤⑥68441226796411322306下图所示的截集为6.3最大流问题MaximalFlowProblem截集将图G＝（V，E）的点集分割成两部分称为一个截集，截①②③④⑤⑥68441226796401322106又如下图所示的截集为上图所示的截集为所有截量中此截量最小且等于最大流量，此截集称为最小截集。【定理】最大流量等于最小截集的截量。6.3最大流问题MaximalFlowProblem①②③④⑤⑥68441226796401322106又如下图6.3.4最小费用流满足流量达到一个固定数使总费用最小，就是最小费用流问题。另一个问题是满足流量到达最大使总费用最小，称为最小费用最大流问题。图6－27是一个运输网络图，将工厂v1，v2及v3的物质(数量不限)运往v6，v4和v5是中转点，弧上的数字为（cij，dij)。设弧（i,j）的单位流量费用为dij≥0，弧的容量为cij≥0设可行流f的一条增广链为μ，称为增广链μ的费用。第一个求和式是增广链中前向弧的费用之和，第二个求和式是增广链中后向弧的费用之和。d(μ)最小的增广链称为最小费用增广链。6.3最大流问题MaximalFlowProblem6.3.4最小费用流满足流量达到一个固定数使总费用最小，就(1)制定一个总运量等于15总运费最小的运输方案；属于最小费用流问题(3,5)(6,4)(4,2)(3,4)(1,6)(2,3)(9,12)①②③④⑤⑥(12,3)(3,5)(6,4)(4,2)(3,4)(1,6)(2,3)(9,12)①②③④⑤⑥s(10,0)(6,0)(3,0)图6－27图6－28(12,3)

(2)制定使运量最大并且总运费最小的运输方案，属于最小费用最大流问题6.3最大流问题MaximalFlowProblem(1)制定一个总运量等于15总运费最小的运输方案；属设给定的流量为v。最小费用流的标号算法步骤如下。第1步：取初始流量为零的可行流f(0)＝{0}，令网络中所有弧的权等于dij得到一个赋权图D，用Dijkstra算法求出最短路，这条最短路就是初始最小费用增广链μ。第2步：调整流量。在最小费用增广链上调整流量的方法与前面最大流算法一样，前向弧上令θj＝cij－fij，后向弧上令θj＝fij，调整量为θ=min{θj}。调整后得到最小费用流f(k)，流量为v(k)＝v(k－1)＋θ，当v(k)＝v时计算结束，否则转第3步继续计算。第3步：作赋权图D并寻找最小费用增广链。6.3最大流问题MaximalFlowProblem设给定的流量为v。第2步：调整流量。在最小费用增广链上调整流(1)对可行流f(k－1)的最小费用增广链上的弧（i，j）作如下变动第一种情形：当弧（i，j）上的流量满足0<fij<cij时，在点vi与vj之间添加一条方向相反的弧（j，i），权为（－dij）。第二种情形：当弧（i，j）上的流量满足fij＝cij时将弧（i，j）反向变为（j，i）,权为（－bij）。不在最小费用增广链上的弧不作任何变动，得到一个赋权网络图D。（2）求赋权图D从发点的收点的最短路，如果最短路存在，则这条最短路就是f(k－1)的最小费用增广链，转第2步。赋权图D的所有权非负时，可用Dijkstra算法求最短路，存在负权时用Floyd算法。（3）如果赋权图D不存在从发点到收点的最短路，说明v(k－1)已是最大流量，不存在流量等于v的流，计算结束。6.3最大流问题MaximalFlowProblem(1)对可行流f(k－1)的最小费用增广链上的弧（i，j）【例6-11】对图6－28，制定一个运量v＝15及运量最大总运费最小的运输方案。【解】令所有弧的流量等于零，得到初始可行流f(0)＝{0}，流量v(0)＝0，总运费d(f(0))=0。354246312图6－29①②③④⑤⑥s000(a)f(0)，赋权图D0最小费用增广链μ1：s→①→④→⑥,见图6－29(a)6.3最大流问题MaximalFlowProblem【例6-11】对图6－28，制定一个运量v＝15及运量最大总调整量θ＝4，对f(0)＝{0}进行调整得到f(1)，括号（）内的数字为弧的流量，网络流量v(1)＝4，总运费d(f(1))＝0×4＋2×4＋3×4＝20如图6－29(b)。图6－29(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)①②③④⑤⑥s(10,0)(6,0)(3,0)(b)f(1)(4)(4)(4)(6,4)(4,2)图中：（cij，dij)(

fij

)6.3最大流问题MaximalFlowProblem调整量θ＝4，对f(0)＝{0}进行调整得到f(1)，括号354－246312图6－29①②③④⑤⑥s000(c)f(1)，赋权图D1－3(3)v(1)＝4<15，没有得到最小费用流。在图6－29(b)中，弧(s,1)和(4,6)满足条件0<fij<cij，添加两条边(1,s)和(6,4)，权分别为“0”和“－3”，边(1,s)可以去掉，弧(1,4)上有fij＝cij说明已饱和，将弧(1,4)反向变为(4,1)，权为“－2”，如图6－29(c)。6.3最大流问题MaximalFlowProblem354－246312图6－29①②③④⑤⑥s000(c)(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)图6－29①②③④⑤⑥s(10,0)(6,0)(3,0)(d)f(2)(4)(4)(7)(6,4)(4,2)(3)(3)图中：（cij，dij)(fij

)用Floyd算法得到最小费用增广链μ2：s→②→④→⑥，调整量θ＝3，调整后得到最小费用流f(2)，流量v(2)＝7，总运费d(f(2))＝2×4＋3×7＋5×3＝44如图6－29(d)。6.3最大流问题MaximalFlowProblem(12,3)(3,5)(3,4)(1,6)(2,3)(9,1(4)v(2)＝7<15，对最小费用增广链μ2上的弧进行调整，在图6－29(c)中，弧(s,2)和(4,6)满足条件0<fij<cij，添加两条边(2,s)和(6,4)，权分别为“0”和“－3”，边(2,s)可以去掉，弧(6,4)已经存在，弧(2,4)上有fij＝cij说明已饱和，将弧(2,4)反向变为(4,2)，权为“－5”，如图6－29(e)。3－54－246312图6－29①②③④⑤⑥s000(e)f(2)，赋权图D2－36.3最大流问题MaximalFlowProblem(4)v(2)＝7<15，对最小费用增广链μ2上的弧进行调用Floyd算法得到最小费用增广链μ3：s→③→④→⑥，调整量θ＝1，调整后得到最小费用流f(3)，流量v(3)＝8，总运费d(f(3))＝2×4＋3×8＋5×3＋6×1＝53如图6－29(f)。(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)图6－29①②③④⑤⑥s(10,0)(6,0)(3,0)(f)f(3)(4)(4)(8)(6,4)(4,2)(3)(3)(1)(1)6.3最大流问题MaximalFlowProblem用Floyd算法得到最小费用增广链μ3：s→③→④→⑥，调整(5)类似地，得到图6－29(g)3－54－24－6312图6－29①②③④⑤⑥s000(g)f(3)，赋权图D3－3(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)图6－29①②③④⑤⑥s(10,0)(6,0)(3,0)(h)f(4)(4)(4)(8)(6,4)(4,2)(3)(3)(3)(1)(2)(2)最小费用增广链μ4：s→③→⑤→⑥，调整量θ＝2，流量v(4)＝10。见图6－29(h)6.3最大流问题MaximalFlowProblem(5)类似地，得到图6－29(g)3－54－24－6312图最小费用增广链μ5：s→①→⑤→⑥,调整量θ＝6，取θ＝5，流量v(5)＝v＝15得到满足，最小费用流见图6－29(j)，问题1计算结束。3－54－24－6－312图6－29①②③④⑤⑥s000(i)f(4)，赋权图D4－3－12(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)图6－29①②③④⑤⑥s(10,0)(6,0)(3,0)(j)f(5)(9)(4)(8)(6,4)(4,2)(3)(3)(3)(1)(2)(7)(5)(6)由图6－29(g)及(h),得到图6－29(i),6.3最大流问题MaximalFlowProblem最小费用增广链μ5：s→①→⑤→⑥,调整量θ＝6，取θ＝5，(7)求最小费用最大流。对图6－29(i)的最小费用增广链μ5，取调整量θ＝6对流量调整，得到图6－30(a)及赋权图6－30(b)(12,3)(3,5)(3,4)(1,6)(2,3)(9,12)图6－30①②③④⑤⑥s(10,0)(6,0)(3,0)(a)f(5)(10)(4)(8)(6,4)(4,2)(3)(3)(3)(1)(2)(8)(6)6.3最大流问题MaximalFlowProblem(7)求最小费用最大流。对图6－29(i)的最小费用增广链μ3－5－4－24－6－312图6－30①②③④⑤⑥s000(b)f(5)，赋权图D5－3－12(8)图6－30(b)的最小费用增广链μ6：s→②→⑤→⑥，6.3最大流问题MaximalFlowProblem3－5－4－24－6－312图6－30①②③④⑤⑥s000((12,3)(3,5)(3,4)(1,6)(2,3)(9,12)图6－30①②③④⑤⑥s(10,0)(6,0)(3,0)(c)f(6)(10)(4)(8)(6,4)(4,2)(4)(3)(3)(1)(2)(9)(6)(1)调整量θ＝1，流量v(6)＝17，最小费用流为f(6)，见图6－30(c)。6.3最大流问题MaximalFlowProblem(12,3)(3,5)(3,4)(1,6)(2,3)(9,1赋权图见图6－30（d）。图6－30(d)不存在从vs发点到v6的最短路，则图6－30(c)的流就是最小费用最大流，最大流量v=17，最小的总运费为d(f)=2×4＋4×6＋5×3＋4×1＋6×1＋3×2＋3×8＋12×9＝1953－5－4－24－6－3－12图6－30①②③④⑤⑥s000(d)f(6)，赋权图D6－3－43个工厂分别运送10、4及3个单位物质到v6，总运量为17，运费为1956.3最大流问题MaximalFlowProblem赋权图见图6－30（d）。图6－30(d)不存在从vs发点到6.3.5最大流应用举例1.二分图的最大匹配问题【例6-12】某公司需要招聘5个专业的毕业生各一个，通过本人报名和筛选，公司最后认为有6人都达到录取条件。这6人所学专业见表6-10,表中打“√”表示该生所学专业。公司应招聘哪几位毕业生，如何分配他们的工作毕业生A.市场营销B.工程管理C.管理信息D.计算机E.企业管理1√√2√√3√√4√√5√√6√√表6-106.3最大流问题MaximalFlowProblem6.3.5最大流应用举例1.二分图的最大匹配问题【例6-1①②③④⑤⑥ABCDEst(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)图6－32【解】画出一个二分图，虚设一个发点和一收点，每条弧上的容量等于1，问题为求发点到收点的最大流，求解结果之一见图6－32。公司录取第2～6号毕业生，安排的工作依次为管理信息、企业管理、市场营销、工程管理和计算机。6.3最大流问题MaximalFlowProblem①②③④⑤⑥ABCDEst(1)(1)(1)(1)(1)(1【例6-13】某市政工程公司在未来5～8月份内需完成4项工程：A.修建一条地下通道、B.修建一座人行天桥、C.新建一条道路及D.道路维修。工期和所需劳动力见表6-11。该公司共有劳动力120人，任一项工程在一个月内的劳动力投入不能超过80人，问公司如何分配劳动力完成所有工程，是否能按期完成工期需要劳动力（人月）A.地下通道5～7月100B.人行天桥6～7月80C.新建道路5～8月200D.道路维修8月80表6-11【解】将工程计划用网络图6－33表示。设点v5、v6、v7、v8分别表示5～8月份，Ai、Bi、Ci、Di表示工程在第i个月内完成的部分，用弧表示某月完成某项工程的状态，弧的容量为劳动力限制。就是求图6－33从发点到收点的最大流问题。6.3最大流问题MaximalFlowProblem【例6-13】某市政工程公司在未来5～8月份内需完成4项工程⑤⑥⑦⑧A5B6C7D8st图6－33A6C5A7C6B7C8ABCD12012012012080808080808080808080808080808080808080801008020080(100)(120)(120)(120)(20)(80)(40)(80)(0)(40)(80)(0)(40)(80)(20)(80)(80)(40)(80)(80)(40)(0)(40)(80)(100)(80)(200)(80)6.3最大流问题MaximalFlowProblem⑤⑥⑦⑧A5B6C7D8st图6－33A6C5A7C6B7C

Ford-Fulkerson标号算法求解得到图6－33，括号内的数字为弧的流量。每个月的劳动力分配见表6-12。5月份有剩余劳动力20人，4项工程恰好按期完成

表6-12月份投入劳动力项目A(人)项目B(人)项目C(人)项目D(人)510020

80

6120

4080

71208040

8120

4080合计(人)46010080200806.3最大流问题MaximalFlowProblemFord-Fulkerson标号算法求解得到图6－33，括1.最大流的概念：容量、流量、可行流、最大流、前向弧、后向弧、增广链、截集、截量、最小截量与最大流量的关系、最小费用流、最小费用最大流。2.有向图、无向图最大流的Ford-Fulkerson标号算法3.最小费用流、最小费用最大流的算法4.本节介绍了两个应用：最大匹配问题和劳动力合理配置问题6.3最大流问题MaximalFlowProblemTheEndofChapter61.最大流的概念：容量、流量、可行流、最大流、前向弧、后向弧

运筹学

Operations

ResearchChapter6网络模型NetworkModeling6.1最小(支撑)树问题Minimal(Spanning)TreeProblem6.2最短路问题ShortestPathProblem

6.3最大流问题MaximalFlowProblem

5v1v2v3v4v5v6843752618图6－1运筹学中研究的图具有下列特征：（1）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系。（2）强调点与点之间的关联关系，不讲究图的比例大小与形状。（3）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义。（4）建立一个网络模型，求最大值或最小值。5v1v2v3v4v5v6843752618图6－1运筹学中边用[vi,vj]表示或简记为[i，j]，集合记为如图6－1所示，点集合记为边上的数字称为权，记为w[vi,vj]、w[i，j]或wij，集合记为连通的赋权图称为网络图，记为G＝｛V，E，W｝5v1v2v3v4v5v6843752618图6－1边用[vi,vj]表示或简记为[i，j]，集合记为如图6－16.1最小(支撑)树问题

Minimal(Spanning)TreeProblem6.1最小(支撑)树问题6.1.1树的概念一个无圈并且连通的无向图称为树图或简称树(Tree)。组织机构、家谱、学科分支、因特网络、通讯网络及高压线路网络等都能表达成一个树图。可以证明：（1）一棵树的边数等于点数减1；（2）在树中任意两个点之间添加一条边就形成圈；（3）在树中去掉任意一条边图就变为不连通。在一个连通图G中，取部分边连接G的所有点组成的树称为G的部分树或支撑树(SpanningTree

)。图6－2是图6－1的部分树。v1v2v3v4v5v64321图6－276.1最小树问题

Minimaltreeproblem6.1.1树的概念一个无圈并且连通的无向图称为树图或简称树6.1.2最小部分树将网络图G边上的权看作两点间的长度（距离、费用、时间），定义G的部分树T的长度等于T中每条边的长度之和，记为C(T)。G的所有部分树中长度最小的部分树称为最小部分树，或简称为最小树。最小部分树可以直接用作图的方法求解，常用的有破圈法和加边法。破圈法：任取一圈，去掉圈中最长边，直到无圈。6.1最小树问题

Minimaltreeproblem6.1.2最小部分树将网络图G边上的权看作两点间的长度（距5v1v2v3v4v5v6843752618图6－1【例6-1】用破圈法求图6－1的最小树。图6－4图6－4就是图6－1的最小部分树，最小树长为C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同6.1最小树问题

Minimaltreeproblem5v1v2v3v4v5v6843752618图6－1【例6-加边法：取图G的n个孤立点｛v1，v2，…，vn}作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n－1条边）

v1v2v3v4v5v643521图6－5在图6－5中，如果添加边[v1,v2]就形成圈｛v1,v2,v4｝，这时就应避开添加边[v1,v2]，添加下一条最短边[v3,v6]。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等5v1v3v515v2v4v684375268×MinC(T)=156.1最小树问题

Minimaltreeproblem【例6-2】用加边法求图6－1的最小树图6－1加边法：取图G的n个孤立点｛v1，v2，…，vn}作为一个下一节：最短路问题1.树、支撑树、最小支撑树的概念2.掌握求最小树的方法：（1）破圈法（2）加边法6.1最小树问题

Minimaltreeproblem下一节：最短路问题1.树、支撑树、最小支撑树的概念6.1最6.2最短路问题ShortestPathProblem6.2最短路问题最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题求最短路有两种算法：一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德)矩阵算法。最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路6.2.1最短路问题的网络模型6.2最短路问题ShortestPathProblem

最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题①②③④⑤⑥⑦610123214675811165图6－69【例6-3】图6－6中的权cij表示vi到vj的距离（费用、时间），从v1修一条公路或架设一条高压线到v7，如何选择一条路线使距离最短，建立该问题的网络数学模型。6.2最短路问题ShortestPathProblem

①②③④⑤⑥⑦610123214675811165图6－69【解】设xij为选择弧(i，j)的状态变量，选择弧(i，j)时xij＝1，不选择弧(i，j)时xij＝0，得到最短路问题的网络模型：6.2最短路问题ShortestPathProblem

【解】设xij为选择弧(i，j)的状态变量，选择弧(i，j6.2.2有向图的狄克斯屈拉(Dijkstra)标号算法点标号：b(j)—起点vs到点vj的最短路长；边标号：k(i，j)=b(i)+cij，步骤：(1)令起点的标号；b(s)＝0。先求有向图的最短路，设网络图的起点是vs,终点是vt,以vi为起点vj为终点的弧记为（i，j）,距离为cij(2)找出所有vi已标号vj未标号的弧集合B={(i，j)}，如果这样的弧不存在或vt已标号则计算结束；(3)计算集合B中弧k(i，j)=b(i)+cij的标号(4)选一个点标号返回到第(2)步。6.2最短路问题ShortestPathProblem

6.2.2有向图的狄克斯屈拉(Dijkstra)标号算法点标②③④⑤⑥⑦610123214675811165图6－690610129209186①161217162432182929【例6-4】用Dijkstra算法求图6－6所示v1到v7的最短路及最短路长v1到v7的最短路为：p17=｛v1,v2,v3,v5,v7｝，最短路长为L17=296.2最短路问题ShortestPathProblem

14②③④⑤⑥⑦610123214675811165图6－690从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj。6.2.3无向图最短路的求法无向图最短路的求法只将上述步骤（2）改动一下即可。点标号：b(i)—起点vs到点vj的最短路长；边标号：k(i，j)=b(i)+cij，步骤：(1)令起点的标号；b(s)＝0。(3)计算集合B中边标号：k[i，j]=b(i)+cij(4)选一个点标号:返回到第(2)步。(2)找出所有一端vi已标号另一端vj未标号的边集合B={[i，j]}如果这样的边不存在或vt已标号则计算结束；6.2最短路问题ShortestPathProblem

从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线【例6-5】求图6-10所示v1到各点的最短路及最短距离①②③④⑤⑥⑦⑧4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。图6-106.2最短路问题ShortestPathProblem

【例6-5】求图6-10所示v1到各点的最短路及最短距离①②6.2.4最短路的Floyd算法Floyd算法基本步骤:(1)写出vi一步到达vj

的距离矩阵，L1也是一步到达的最短距离矩阵。如果vi与vj之间没有边关联，则令cij=+∞(2)计算二步最短距离矩阵。设vi到vj经过一个中间点vr两步到达vj，则vi到vj的最短距离为最短距离矩阵记为(3)计算k步最短距离矩阵。设vi经过中间点vr

到达vj，vi经过k－1步到达点vr的最短距离为，vr经过k－1步到达点vj

的最短距离为，则vi经k步

到达vj的最短距离为(6-1)6.2最短路问题ShortestPathProblem

6.2.4最短路的Floyd算法Floyd算法基本步骤最短距离矩阵记为(4)比较矩阵Lk与Lk－1，当Lk＝Lk－1时得到任意两点间的最短距离矩阵Lk。设图的点数为n并且cij≥0，迭代次数k由式(6-3)估计得到。(6-2)(6-3)6.2最短路问题ShortestPathProblem

最短距离矩阵记为(4)比较矩阵Lk与Lk－1，当Lk＝Lk63①②③④⑤⑥⑦⑧45212789326121610【例6-6】图6-14是一张8个城市的铁路交通图，铁路部门要制作一张两两城市间的距离表。这个问题实际就是求任意两点间的最短路问题。【解】(1)依据图6-14,写出任意两点间一步到达距离表L1。见表6-1所示。本例n=8，，因此计算到L3

图6-146.2最短路问题ShortestPathProblem

63①②③④⑤⑥⑦⑧45212789326121610【例6v1v2v3v4v5v6v7v8v106∞5∞4∞∞v260328∞∞∞v3∞30