[经济学]Ch6网络模型课件.ppt

1、 运运 筹筹 学学 Operations ResearchChapter 6 网络模型网络模型Network Modeling6.1 最小最小(支撑支撑)树问题树问题 Minimal(Spanning)Tree Problem6.2 最短路问题最短路问题 Shortest Path Problem 6.3 最大流问题最大流问题 Maximal Flow ProblemCh6 网络模型网络模型 Network Model5v1v2v3v4v5v6843752618图图61运筹学中研究的图具有下列特征：运筹学中研究的图具有下列特征：（1）用点表示研究对象，用边（有方向或无方向）表示对）用点表示研究

2、对象，用边（有方向或无方向）表示对象之间某种关系。象之间某种关系。（2）强调点与点之间的关联关系，不讲究图的比例大小与）强调点与点之间的关联关系，不讲究图的比例大小与形状。形状。（3）每条边上都赋有一个权，其图称为赋权图。实际中权）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的可以代表两点之间的距离、费用、利润、时间、容量等不同的含义。含义。（4）建立一个网络模型，求最大值或最小值。）建立一个网络模型，求最大值或最小值。Ch6 网络模型网络模型 Network Model126,Vv vv边用边用vi,vj表示或简记为表示或简记为i，j，集

3、合记为，集合记为如图如图61所示，点集合记为所示，点集合记为12,13,5 6E，边上的数字称为权，记为边上的数字称为权，记为wvi,vj、wi，j或或wij，集合记为，集合记为12131456,Wwwww连通的赋权图称为网络图，记为连通的赋权图称为网络图，记为 GV，E，W5v1v2v3v4v5v6843752618图图616.1 最小最小(支撑支撑)树问题树问题 Minimal(Spanning)Tree ProblemCh6 网络模型网络模型 Network Model6.1.1树的概念树的概念 一个无圈并且连通的无向图称为树图或简称树一个无圈并且连通的无向图称为树图或简称树(Tree)

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

5、树。部分树。v1v2v3v4v5v64321图图6276.1 最小树问题最小树问题 Minimal tree problemCh6 网络模型网络模型 Network Model6.1.2 最小部分树最小部分树将网络图将网络图G边上的权看作两点间的长度（距离、费用、时间），边上的权看作两点间的长度（距离、费用、时间），定义定义G的部分树的部分树T的长度等于的长度等于T中每条边的长度之和，记为中每条边的长度之和，记为C(T)。G的所有部分树中长度最小的部分树称为的所有部分树中长度最小的部分树称为最小部分树最小部分树，或简称，或简称为为最小树最小树。最小部分树可以直接用作图的方法求解，常用的有破圈法

6、和最小部分树可以直接用作图的方法求解，常用的有破圈法和加边法。加边法。破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。6.1 最小树问题最小树问题 Minimal tree problemCh6 网络模型网络模型 Network Model5v1v2v3v4v5v6843752618图图61【例【例6-1】用破圈法求图】用破圈法求图61的最小树。的最小树。图图64图图64就是图就是图61的最小部分树，最小树长为的最小部分树，最小树长为 C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去当一个圈中有多个相同的最长边时

7、，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同度相同 6.1 最小树问题最小树问题 Minimal tree problemCh6 网络模型网络模型 Network Model加边法加边法：取图：取图G的的n个孤立点个孤立点v1，v2，vn作为一个支撑作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）条边）v1v2v3v4v5v643521图图65在图在图65中，如果添加边中，如果添加边v1,v2就形成圈就形成圈v1,v2,

8、v4，这时就，这时就应避开添加边应避开添加边v1,v2，添加下一条最短边，添加下一条最短边v3,v6。破圈法和加边。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等法得到树的形状可能不一样，但最小树的长度相等 5v1v3v515v2v4v684375268Min C(T)=156.1 最小树问题最小树问题 Minimal tree problem【例【例6-2】用加边法求图】用加边法求图61的最小树的最小树图图61Ch6 网络模型网络模型 Network Model下一节：最短路问题下一节：最短路问题1.树、支撑树、最小支撑树的概念树、支撑树、最小支撑树的概念2.掌握求最小树的方法：掌

9、握求最小树的方法：（1）破圈法）破圈法 （2）加边法）加边法6.1 最小树问题最小树问题 Minimal tree problem6.2 最短路问题最短路问题 Shortest Path ProblemCh6 网络模型网络模型 Network Model最短路问题在实际中具有广泛的应用，如管道铺设、线路选择最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题路问题 求最短路有两种算法：求最短路有两种算法：一是求从某一点至其它各点之间最短离的一是求从某一点至其它各点之间最短离的狄克

10、斯屈拉狄克斯屈拉(Dijkstra)算法算法 另一种是求网络图上任意两点之间最短路的另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德弗洛伊德)矩阵算法。矩阵算法。最短路问题，就是从给定的网络图中找出一点到各点或任意两最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路点之间距离最短的一条路 6.2.1最短路问题的网络模型最短路问题的网络模型6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model610123214675811165图图669【例【例6-3】图】图66中的权中的权cij表示表示

11、vi到到vj的距离（费用、时间），从的距离（费用、时间），从v1修一条公路或架设一条高压线到修一条公路或架设一条高压线到v7，如何选择一条路线使距离，如何选择一条路线使距离最短，建立该问题的网络数学模型。最短，建立该问题的网络数学模型。6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model【解】【解】设设xij为选择弧为选择弧(i，j)的状态变量，选择弧的状态变量，选择弧(i，j)时时xij1，不，不选择弧选择弧(i，j)时时xij0，得到最短路问题的网络模型：，得到最短路问题的网络模型：(,)12(,)(,)571314

12、67min102,3,610(,)ijiji jEijkii jEk iEijZc xxxxxxixxxi jE或1，6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model6.2.2有向图的狄克斯屈拉有向图的狄克斯屈拉(Dijkstra)标号算法标号算法点标号：点标号：b(j)起点起点vs到点到点vj的最短路长；的最短路长；边标号：边标号：k(i，j)=b(i)+cij，步骤：步骤：(1)令起点的标号；令起点的标号；b(s)0。先求有向图的最短路，设网络图的起点是先求有向图的最短路，设网络图的起点是vs,终点是终点是vt

13、,以以vi为起为起点点vj为终点的弧记为（为终点的弧记为（i，j）,距离为距离为cij(2)找出所有找出所有vi已标号已标号vj未标号的弧集合未标号的弧集合 B=(i，j)，如果这样，如果这样的弧不存在或的弧不存在或vt已标号则计算结束；已标号则计算结束；(3)计算集合计算集合B中弧中弧k(i，j)=b(i)+cij的标号的标号(4)选一个点标号选一个点标号 返回到第返回到第(2)步。步。)(,),(|),(min)(lbvBjijiklblj处标号在终点6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model6101232

14、14675811165图图6690610129209186161217162432182929【例【例6-4】用】用Dijkstra算法求图算法求图66 所示所示v1到到v7的最短路及最短路长的最短路及最短路长 v1 到到v7的最短路为：的最短路为：p17=v1,v2,v3,v5,v7，最短路长为，最短路长为L17=29 6.2 最短路问题最短路问题 Shortest Path Problem 14Ch6 网络模型网络模型 Network Model从上例知，只要某点已标号，说明已找到起点从上例知，只要某点已标号，说明已找到起点vs到该点的最短路到该点的最短路线及最短距离，因此可以将每个点标号

15、，求出线及最短距离，因此可以将每个点标号，求出vs到任意点的最短到任意点的最短路线，如果某个点路线，如果某个点vj不能标号，说明不能标号，说明vs不可不可达达vj。6.2.3 无向图最短路的求法无向图最短路的求法无向图最短路的求法只将上述步骤（无向图最短路的求法只将上述步骤（2）改动一下即可。）改动一下即可。点标号：点标号：b(i)起点起点vs到点到点vj的最短路长；的最短路长；边标号：边标号：k(i，j)=b(i)+cij，步骤：步骤：(1)令起点的标号；令起点的标号；b(s)0。(3)计算集合计算集合B中边标号：中边标号：ki，j=b(i)+cij)(,|,min)(lbvBjijiklb

16、lj处标号在端点(4)选一个点标号选一个点标号:返回到第返回到第(2)步。步。(2)找出所有一端找出所有一端vi已标号另一端已标号另一端vj未标号的边集合未标号的边集合 B=i，j如如果这样的边不存在或果这样的边不存在或vt已标号则计算结束；已标号则计算结束；6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model【例【例6-5】求图】求图6-10所示所示v1到各点的最短路及最短距离到各点的最短路及最短距离4526178393261216180452231039612641166188122482418所有点都已标号，点上的

17、标号就是所有点都已标号，点上的标号就是v1到该点的最短距离，最短路到该点的最短距离，最短路线就是红色的链。线就是红色的链。图图6-106.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model6.2.4 最短路的最短路的Floyd算法算法 Floyd算法基本步骤算法基本步骤:(1)写出写出vi一步到达一步到达vj 的距离矩阵的距离矩阵 ，L1也是一步到达的也是一步到达的最短距离矩阵。如果最短距离矩阵。如果vi 与与vj 之间没有边关联，则令之间没有边关联，则令cij=+(1)1()ijLL(2)计算二步最短距离矩阵。设计算二步

18、最短距离矩阵。设vi 到到vj 经过一个中间点经过一个中间点vr 两步到达两步到达vj，则，则vi到到vj的最短距离为的最短距离为(2)minijirrjrLcc最短距离矩阵记为最短距离矩阵记为(2)2()ijLL(3)计算计算k步最短距离矩阵。设步最短距离矩阵。设 vi经过中间点经过中间点vr 到达到达vj，vi 经过经过k1步到达点步到达点vr 的最短距离为的最短距离为 ，vr 经过经过k1步到达点步到达点vj 的最短的最短距离为距离为 ，则，则 vi 经经k步步 到达到达vj 的最短距离为的最短距离为(1)krjL(1)krjL(6-1)6.2 最短路问题最短路问题 Shortest P

19、ath Problem Ch6 网络模型网络模型 Network Model()(1)(1)minkkkijirrjrLLL最短距离矩阵记为最短距离矩阵记为()()kkijLL(4)比较矩阵比较矩阵Lk与与Lk1，当，当LkLk1时得到任意两点间的最短距时得到任意两点间的最短距离矩阵离矩阵Lk。设图的点数为设图的点数为n并且并且cij0，迭代次数，迭代次数k由式由式(6-3)估计得到。估计得到。(6-2)121221kknlg(1)1lg 2nkk(6-3)6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model634521

20、2789326121610【例【例6-6】图】图6-14是一张是一张8个城市的铁路交通图，铁路部门要制作个城市的铁路交通图，铁路部门要制作一张两两城市间的距离表。这个问题实际就是求任意两点间的最一张两两城市间的距离表。这个问题实际就是求任意两点间的最短路问题。短路问题。【解】【解】(1)依据图依据图6-14,写出写出任意两点间一步到达距离任意两点间一步到达距离表表L1。见表。见表6-1所示。本例所示。本例n=8，因此计，因此计算到算到L3 图图6-14lg72.807lg26.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Mod

21、elv1v2v3v4v5v6v7v8v10 06 65 54 4v26 60 03 32 28 8v33 30 07 71616v45 52 20 09 912123 3v58 87 79 90 010106 6v64 412120 02 2v73 310102 20 01212v816166 612120 0表表6-1 最短距离表最短距离表 L16.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model表表6-2 最短距离表最短距离表L2v1v2v3v4v5v6v7v8v106951446v26032810514v39305

22、71713v4525095315v514879012106v64105120214v765173102012v8141315614120计算说明：计算说明：L(2)ij等于表等于表6-1中第中第i行与第行与第j列对应元素相加取最小值。如列对应元素相加取最小值。如 4341134223433344434553466347734883min,min 5,23,0,0,97,12,3,165Lcccccccccccccccc(2)6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model表表6-3计算示例计算示例:等于表等于表6-2

23、中第中第i行与第行与第j列对应元素相加取最小值。例如，列对应元素相加取最小值。例如，v3经过三步（最多三个中间点经过三步（最多三个中间点4条边）到达条边）到达v6的最短距离是的最短距离是表表6-3 最短距离表最短距离表L3v1v2v3v4v5v6v7v8v10695144618v2603287514v39305710813v4525095315v514879012106v647105120214v76583102012v818141315614120(3)ijL2222363116322633363886min,min 94,310,0,55,712,0,172,131410LLLLLLLLL

24、 (3)(2)(2)(2)(2)6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model【例【例6-7】求图】求图615中任意两点间的最短距离。中任意两点间的最短距离。【解】图【解】图615是一个混合图，有是一个混合图，有3条边的权是负数条边的权是负数,有两条边有两条边无方向。依据图无方向。依据图615,写出任意两点间一步到达距离表写出任意两点间一步到达距离表L1。表。表中第一列的点表示弧的起点，第一行的点表示弧的终点，无方中第一列的点表示弧的起点，第一行的点表示弧的终点，无方向的边表明可以互达，见表向的边表明可以互达，见表

25、6-4所示。计算过程见表所示。计算过程见表6-56-7。445743271028图图615156.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model表表6-4一步到达距离表一步到达距离表L1v1v2v3v4v5v6v7v105 4v2042v34072v440107v5103v6508v7206.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model表表6-7 最短距离表最短距离表L4v1v2v3v4v5v6v7v10593419v2204-2635v36

26、4021072v44990857v5-14720-35v69141051308v786241290经计算经计算L4L5，L4是最优表。表是最优表。表6-7不是对称表，不是对称表，vi到到vj与与vj到到vi的的最短距离不一定相等。对于有负权图情形，公式最短距离不一定相等。对于有负权图情形，公式(6-3)失效。失效。6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model6.2.4 最短路应用举例最短路应用举例6.2 最短路问题最短路问题 Shortest Path Problem【例【例6-8】设备更新问题。企业在使用某设备

27、时，每年年初可购】设备更新问题。企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几年后卖掉重新购置新设备。已置新设备，也可以使用一年或几年后卖掉重新购置新设备。已知知4年年初购置新设备的价格分别为年年初购置新设备的价格分别为2.5、2.6、2.8和和3.1万元。设万元。设备使用了备使用了14年后设备的残值分别为年后设备的残值分别为2、1.6、1.3和和1.1万元，使万元，使用时间在用时间在14年内的维修保养费用分别为年内的维修保养费用分别为0.3、0.8、1.5和和2.0万万元。试确定一个设备更新策略，在下例两种情形下使元。试确定一个设备更新策略，在下例两种情形下使4年的设备年的设备

28、购置和维护总费用最小。购置和维护总费用最小。（1）第）第4年年末设备一定处理掉；年年末设备一定处理掉；（2）第）第4年年末设备不处理。年年末设备不处理。【解】画网络图。用点【解】画网络图。用点(1,i,j)表示第表示第1年年初购置设备使用到第年年初购置设备使用到第i年年初更新，经过若干次更新使用到第年年初更新，经过若干次更新使用到第j年年初，第年年初，第1年年初和年年初和第第5年年初分别用年年初分别用及及表示。使用过程用弧连接起来，弧上的表示。使用过程用弧连接起来，弧上的权表示总费用权表示总费用(购置费维护费残值购置费维护费残值)，如图，如图616所示所示 Ch6 网络模型网络模型 Netwo

29、rk Model6.2 最短路问题最短路问题 Shortest Path Problem 6图图616(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网络图网络图616说明：如图中点说明：如图中点(1,3)表示第表示第1年购置设备使用两年到第年购置设备使用两年到第3年年初更新年年初更新购置新设备，这时有购置新设备，这时有2种更新方案，使用种更新方案，使用1年到第年到第4年年初、使用年年初、使用2年到第年到第5年年年年初初,更新方案用弧表示，

30、点（更新方案用弧表示，点（1,2,3）表示第）表示第1年购置设备使用一年到第二年年初年购置设备使用一年到第二年年初又更新，使用一年到第三年初再更新，这时仍然有又更新，使用一年到第三年初再更新，这时仍然有2种更新方案，使用种更新方案，使用1年到第年到第4年年初和使用年年初和使用2年到第年到第5年年初。年年初。Ch6 网络模型网络模型 Network Model6.2 最短路问题最短路问题 Shortest Path Problem 点（点（1,3）和点（）和点（1,2,3）不能合并成一个点，虽然都是第三年）不能合并成一个点，虽然都是第三年年初购置新设备，购置费用相同，但残值不同。点年初购置新设备

31、，购置费用相同，但残值不同。点(1,3)的残值的残值等于等于1.6(使用了两年使用了两年)，点，点(1,2,3)的残值等于的残值等于2(使用了一年使用了一年)。点。点（1,3）到点（）到点（1,3,4）的总费用为）的总费用为第三年的购置费第一年的维护费设备使用两年后的残值第三年的购置费第一年的维护费设备使用两年后的残值2.8+0.31.6=1.5点（点（1,3）到点）到点的总费用为的总费用为第三年的购置费第一年的维护费第二年的维护费设备使第三年的购置费第一年的维护费第二年的维护费设备使用两年后的残值第四年末的残值用两年后的残值第四年末的残值2.8+0.3+0.81.61.6=0.7。费用表见教

32、材表费用表见教材表6-8。Ch6 网络模型网络模型 Network Model6图图616(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.6Ch6 网络模型网络模型 Network Model6.2 最短路问题最短路问题 Shortest Path Problem（2）第四年末不处理设备：）第四年末不处理设备：将图将图616第第4年的数据换成表年的数据换成表6-8最最后一列，求点后一列，求点到点到点的最短路。最短路线为：的最短路。最短路线为：

33、(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万元

34、。万元。Ch6 网络模型网络模型 Network Model【例【例6-9】服务网点设置问题。以图】服务网点设置问题。以图614为例，现提出这样一为例，现提出这样一个问题，在交通网络中建立一个快速反应中心，应选择哪一个个问题，在交通网络中建立一个快速反应中心，应选择哪一个城市最好。类似地，在一个网络中设置一所学校、医院、消防城市最好。类似地，在一个网络中设置一所学校、医院、消防站、购物中心，还有厂址选择、总部选址、公司销售中心选址站、购物中心，还有厂址选择、总部选址、公司销售中心选址等问题都属于最佳服务网点设置问题。等问题都属于最佳服务网点设置问题。【解】【解】对于不同的问题，寻求最佳服务点有

35、不同的标准。像对于不同的问题，寻求最佳服务点有不同的标准。像图图614只有两点间的距离，可以采用只有两点间的距离，可以采用“使最大服务距离达到使最大服务距离达到最小最小”为标准，计算步骤如下。为标准，计算步骤如下。第一步：利用第一步：利用Floyd算法求出任意两点之间的最短距离表算法求出任意两点之间的最短距离表（表（表63）。）。第二步：计算最短距离表中每行的最大距离的最小值，即第二步：计算最短距离表中每行的最大距离的最小值，即 ijjiLLmaxmin6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model引用例引用例6-

36、6计算的结果，对表计算的结果，对表63每行取最大值再取最小值，见每行取最大值再取最小值，见表表69倒数第二列。倒数第二列。v1v2v3v4v5v6v7v8Max Lij总运量总运量v10695144618183220v2603287514142465v39305710813132955v4525095315152450v514879012106143780v647105120214142960v76583102012122560v818141315614120185040产量产量8050704030356065表表69表表69中倒数第二列最小值为中倒数第二列最小值为12，位于第，位于第7行，则

37、行，则v7为网络的中为网络的中心，最佳服务点应设置在心，最佳服务点应设置在v7。6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model如果每个点还有一个权数，例如一个网点的人数、需要运送的如果每个点还有一个权数，例如一个网点的人数、需要运送的物质数量、产量等，这时采用物质数量、产量等，这时采用“使总运量最小使总运量最小”为标准，计算为标准，计算方法是将上述第二步的最大距离改为总运量，总运量的最小值方法是将上述第二步的最大距离改为总运量，总运量的最小值对应的点就是最佳服务点。对应的点就是最佳服务点。表表69中最后一行是点中最

38、后一行是点vj的产量，将各行的最小距离分别乘以产的产量，将各行的最小距离分别乘以产量求和得到总运量，例如，量求和得到总运量，例如，08065018653220，见表见表69最后一列，最小运量为最后一列，最小运量为2450，最佳服务点应设置在，最佳服务点应设置在v4。6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model下一节：最大流问题下一节：最大流问题6.2 最短路问题最短路问题 Shortest Path Problem 1.最短路的概念及应用。最短路的概念及应用。2.有向图、无向图一点到各点最短路的有向图、无向图一点

39、到各点最短路的Dijkstra算法算法3.任意两点最短路的任意两点最短路的Floyd算法算法4.本节介绍了两个应用：设备更新问题和最佳服务点设置问题本节介绍了两个应用：设备更新问题和最佳服务点设置问题6.3 最大流问题最大流问题Maximal Flow ProblemCh6 网络模型网络模型 Network Model6.3 最大流问题最大流问题Maximal Flow Problem6.3.1 基本概念基本概念8145633810763图图6184图图618所示的网络图中定义了一个所示的网络图中定义了一个发点发点v1，称为源，称为源(source，supply node），定义了一个），定义

40、了一个收点收点v7，称为汇（，称为汇（sink，demand node），其余），其余点点v2，v3，v6为为中间点中间点，称为，称为转运点转运点(transshipment nodes)。如果。如果有多个发点和收点，则虚设发点和收点转化成一个发点和收点。图中有多个发点和收点，则虚设发点和收点转化成一个发点和收点。图中的权是该弧在单位时间内的最大通过能力，称为弧的的权是该弧在单位时间内的最大通过能力，称为弧的容量容量(capacity)。最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。的方

41、向运送到收点，使总运输量最大。Ch6 网络模型网络模型 Network Model设设cij为弧（为弧（i，j）的容量，）的容量，fij为弧（为弧（i，j）的流量。）的流量。容量是弧（容量是弧（i，j）单位时间内的）单位时间内的最大通过能力最大通过能力，流量是弧（，流量是弧（i，j）单位时间内的单位时间内的实际通过量实际通过量，流量的集合，流量的集合f=fij称为网络的流。发点称为网络的流。发点到收点的总流量记为到收点的总流量记为v=val(f)，v也是网络的也是网络的流量流量。图图618最大流问题的线性规划数学模型为最大流问题的线性规划数学模型为),(000max67475713121312

42、jicfvfffffffffvijijmvmjvimmm所有弧所有中间点6.3 最大流问题最大流问题Maximal Flow ProblemCh6 网络模型网络模型 Network Model满足下例满足下例3个条件的流个条件的流fij 的集合的集合 f=fij 称为可行流称为可行流 1)0(,)ijijfci j（所有弧(3)stsjitvvvff发点发点vs流出的总流量等于流入收点流出的总流量等于流入收点vt的总流量的总流量(2)mmimmjmvvffv所有中间点6.3 最大流问题最大流问题Maximal Flow ProblemCh6 网络模型网络模型 Network Model链：链：

43、从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。从发点到收点的方向规定为链的方向。前向弧：前向弧：与链的方向相同的弧称为前向弧。与链的方向相同的弧称为前向弧。后向弧：后向弧：与链的方向相反的弧称为后向弧。与链的方向相反的弧称为后向弧。增广链增广链:设设 f 是一个可行流，如果存在一条从是一个可行流，如果存在一条从vs到到vt的链，满足：的链，满足：1.所有前向弧上所有前向弧上fij0则该链称为增广链则该链称为增广链前向弧前向弧后向弧后向弧容量容量流量流量这是一条增这是一条增广链广链84469（5）(2

44、)(3)(4)(6)6.3 最大流问题最大流问题Maximal Flow ProblemCh6 网络模型网络模型 Network Model步骤如下：步骤如下：第二步：对点进行标号找一条增广链。第二步：对点进行标号找一条增广链。（1）发点标号）发点标号（）（2）选一个点）选一个点 vi 已标号并且另一端未标号的弧沿着某条链向收已标号并且另一端未标号的弧沿着某条链向收点检查：点检查：A如果弧的方向向前（前向弧）并且有如果弧的方向向前（前向弧）并且有fij0，则，则vj标号标号:jfji当收点已得到标号时，说明已找到增广链，依据当收点已得到标号时，说明已找到增广链，依据vi 的标号反向跟的标号反向

45、跟踪得到一条增广链。当收点不能得到标号时，说明不存在增广踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算结束。链，计算结束。第一步：第一步：找出第一个可行流，例如所有弧的流量找出第一个可行流，例如所有弧的流量fij=06.3.2 Ford-Fulkerson标号算法标号算法6.3 最大流问题最大流问题Maximal Flow ProblemCh6 网络模型网络模型 Network Model第三步：调整流量第三步：调整流量（1）求增广链上点）求增广链上点vi 的标号的最小值，得到调整量的标号的最小值，得到调整量 minjj（2）调整流量）调整流量),(),(),(1jifjifj

46、iffijijij得到新的可行流得到新的可行流f1，去掉所有标号，返回到第二步从发点重新，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止标号寻找增广链，直到收点不能标号为止【定理【定理6.1】可行流可行流f是最大流的充分必要条件是不存在发点到是最大流的充分必要条件是不存在发点到收点的增广链收点的增广链 6.3 最大流问题最大流问题Maximal Flow ProblemCh6 网络模型网络模型 Network Model8145633810763图图619(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)【例【例6-10】求图】求图618发点

47、发点v1到收点到收点v7的最大流及最大流量的最大流及最大流量【解】给定初始可行流，见图【解】给定初始可行流，见图6-196.3 最大流问题最大流问题Maximal Flow ProblemCh6 网络模型网络模型 Network Model8145633810763图图620(b)(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)2337第一轮标号：第一轮标号：c12f12,v2标号标号2cij=fij，v4、v5不能标号不能标号后向弧后向弧f320,v3标号标号3=f32增广链增广链(1,2)，(3,2)，(3,4)，(4,7),+=(1,2)，(3,4)，(4,7

48、),=(3，2)，调整量为增广链上点标号的最小值，调整量为增广链上点标号的最小值min，2，3，3，726.3 最大流问题最大流问题Maximal Flow ProblemCh6 网络模型网络模型 Network Model8145633810763图图621(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)调整后的可行流：调整后的可行流：6.3 最大流问题最大流问题Maximal Flow ProblemCh6 网络模型网络模型 Network Model8145633810763图图622(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)

49、4415第二轮标号：第二轮标号：Cij=fij，v4、v5不能标号，返回到不能标号，返回到v3增广链增广链(1,3)，(3,4)，(4,7)，调整量为，调整量为 min，4，1，516.3 最大流问题最大流问题Maximal Flow ProblemCh6 网络模型网络模型 Network Model8145633810763图图623(11)(8)(1)(6)(3)(7)(3)(6)(1)4(6)(1)(7)调整后得到可行流：调整后得到可行流：6.3 最大流问题最大流问题Maximal Flow ProblemCh6 网络模型网络模型 Network Model8145633810763图图

50、622(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，4126.3 最大流问题最大流问题Maximal Flow ProblemCh6 网络模型网络模型 Network Model8145633810763图图625(12)(8)(1)(6)(3)(8)(3)(6)(2)4(7)(1)(7)调整后得到可行流：调整后得到可行流：6.3 最大流问题最大流问题Maximal Flow ProblemCh6 网络模型网络模型 Network Mo