大学精品课件：6网络模型.ppt

1、运筹学运运 筹筹 学学运运 筹筹 学学 OperationsResearch Chapter6网络模型网络模型NetworkModeling6.1最小最小(支撑支撑)树问题树问题Minimal(Spanning)TreeProblem6.2最短路问题最短路问题ShortestPathProblem6.3最大流问题最大流问题MaximalFlowProblem6.4旅行售货员与中国邮路问题旅行售货员与中国邮路问题TravelingSalesmanandChinaCarrierProblem图论是专门研究图的理论的一门数学分支，属于离散数图论是专门研究图的理论的一门数学分支，属于离散数学范畴，与运

2、筹学有交叉，它有学范畴，与运筹学有交叉，它有200多年历史，大体可划分多年历史，大体可划分为三个阶段：为三个阶段：第一阶段是从十八世纪中叶到十九世纪中叶，处于萌芽第一阶段是从十八世纪中叶到十九世纪中叶，处于萌芽阶段，多数问题围绕游戏而产生，最有代表性的工作是所谓阶段，多数问题围绕游戏而产生，最有代表性的工作是所谓的的Euler七桥问题，即一笔画问题。七桥问题，即一笔画问题。第二阶段第二阶段从十九世纪中叶到二十世纪中叶，这时，图论问题从十九世纪中叶到二十世纪中叶，这时，图论问题大量出现，如大量出现，如Hamilton问题，地图染色的四色问题以问题，地图染色的四色问题以及可平面性问题等，这时，也出

3、现用图解决实际问题，及可平面性问题等，这时，也出现用图解决实际问题，如如Cayley把树应用于化学领域，把树应用于化学领域，Kirchhoff用树去研究用树去研究电网络等电网络等.第三阶段第三阶段二十世纪中叶以后，由生产管理、军事、交通、运输、二十世纪中叶以后，由生产管理、军事、交通、运输、计算机网络等方面提出实际问题，以及大型计算机使大规计算机网络等方面提出实际问题，以及大型计算机使大规模问题的求解成为可能，特别是以模问题的求解成为可能，特别是以Ford和和Fulkerson建立建立的网络流理论，与线性规划、动态规划等优化理论和方法的网络流理论，与线性规划、动态规划等优化理论和方法相互渗透，

4、促进了图论对实际问题的应用。相互渗透，促进了图论对实际问题的应用。哥尼斯堡（现名加里宁格勒）是欧洲一个城市，哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如有没有办法从某处（如A）出发，经过各桥一次且仅一次最出发，经过各桥一次且仅一次最后回到原地呢？后回到原地呢？ABCD数学家数学家Euler在在1736年巧妙地给出了这个问题的答案，年巧妙地给出了这个问题的答案，并因此奠

5、定了图论的基础，并因此奠定了图论的基础，Euler把把A、B、C、D四块陆地四块陆地分别收缩成四个顶点，把桥表示成连接对应顶点之间的边，分别收缩成四个顶点，把桥表示成连接对应顶点之间的边，问题转化为从任意一点出发，能不能经过各边一次且仅一问题转化为从任意一点出发，能不能经过各边一次且仅一次，最后返回该点。这就是著名的次，最后返回该点。这就是著名的Euler问题。问题。无向连通图无向连通图G为欧拉图为欧拉图的充要条件是的充要条件是G中所有顶点中所有顶点的度数都是偶数。的度数都是偶数。例例:有有7个人围桌而坐，如果要求每次相邻的人都与以前个人围桌而坐，如果要求每次相邻的人都与以前完全不同，试问不同

6、的就座方案共有多少种？完全不同，试问不同的就座方案共有多少种？用顶点表示人，用边表示两者相邻，因为最初任何两个人用顶点表示人，用边表示两者相邻，因为最初任何两个人都允许相邻，所以任何两点都可以有边相连。都允许相邻，所以任何两点都可以有边相连。假定第一次就座方案是假定第一次就座方案是（1，2，3，4，5，6，7，1），那么第二次就座方案），那么第二次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这就不允许这些顶点之间继续相邻，只能从图中删去这些边。些边。1 12 23 34 45 56 67 7假定第二次就座方案是假定第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案）

7、，那么第三次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这就不允许这些顶点之间继续相邻，只能从图中删去这些边。些边。假定第三次就座方案是假定第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案），那么第四次就座方案就不允许这些顶点之间继续相邻，只能从图中删去这就不允许这些顶点之间继续相邻，只能从图中删去这些边，只留下些边，只留下7点孤立点，所以该问题只有三个就座方点孤立点，所以该问题只有三个就座方案。案。例例10-3：哈密顿（：哈密顿（Hamilton）回路是十九世纪英国数回路是十九世纪英国数学家哈密顿提出，给出一个正学家哈密顿提出，给出一个正12面体图形，共有面体图

8、形，共有20个个顶点表示顶点表示20个城市，要求从某个城市出发沿着棱线寻个城市，要求从某个城市出发沿着棱线寻找一条经过每个城市一次而且仅一次，最后回到原处找一条经过每个城市一次而且仅一次，最后回到原处的周游世界线路（并不要求经过每条边）。的周游世界线路（并不要求经过每条边）。例例10-4：一个班级的学生共计选修：一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修六门课程，其中一部分人同时选修D、C、A，一部分人同时选修一部分人同时选修B、C、F，一部分人同时一部分人同时选修选修B、E，还有一部分人同时选修还有一部分人同时选修A、B，期终期终考试要求每天考一门课，六天内考

9、完，为了减轻考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。计一个考试日程表。解：以每门课程为一个顶点，共同被选修的课程之解：以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿因此，作图的补图，问题是在图中寻找一条哈密顿道路，如道路，如CEAFDB，就是一个符合要求就是一个符合要求的考试课程表

10、。的考试课程表。图论是专门研究图的理论的一门数学分支，主要研图论是专门研究图的理论的一门数学分支，主要研究点和线之间的究点和线之间的几何关系。几何关系。设设G=（V，E，）其中：其中：V=（v1，v2，.vm）是）是m个顶点集合；个顶点集合；E=（e1，e2，.en）是）是n条边集合。条边集合。是描述边与顶点之间关系的函数是描述边与顶点之间关系的函数称称G=（V，E，）为为一个图，如果它满足：一个图，如果它满足：（1）V非空；非空；（2）E是一个不与是一个不与V中顶点相交的边集合；中顶点相交的边集合；（3）是关联函数。是关联函数。V，E，称为图的三要素。称为图的三要素。说明：说明：（1）V非空

11、，即没有顶点的图不讨论；非空，即没有顶点的图不讨论；（2）E无非空条件，即允许没有边；无非空条件，即允许没有边；（3）条件（）条件（2）是指点只在边的端点）是指点只在边的端点处相交；处相交；（4）任一条边必须与一对顶点关联，）任一条边必须与一对顶点关联，反之不然。反之不然。6.1最小最小(支撑支撑)树问题树问题Minimal(Spanning)TreeProblem5v1v2v3v4v5v6843752618图图61运筹学中研究的图具有下列特征：运筹学中研究的图具有下列特征：（1）用点表示研究对象，用边（有方向或无方向）表示对）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系。象之

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

13、示，点集合记为12,13,5 6E，边上的数字称为权，记为边上的数字称为权，记为wvi,vj、wi，j或或wij，集合记为集合记为12131456,Wwwww连通的赋权图称为网络图，记为连通的赋权图称为网络图，记为 GV，E，W5v1v2v3v4v5v6843752618图图616.1最小树问题最小树问题Minimaltreeproblem6.1.1树的概念树的概念一个无圈并且连通的无向图称为树图或简称树一个无圈并且连通的无向图称为树图或简称树(Tree)。组织机组织机构、家谱、学科分支、因特网络、通讯网络及高压线路网络等构、家谱、学科分支、因特网络、通讯网络及高压线路网络等都能表达成一个树图

14、都能表达成一个树图。可以证明：可以证明：（1）一棵树的边数等于点数减）一棵树的边数等于点数减1；（2）在树中任意两个点之间添加一条边就形成圈；）在树中任意两个点之间添加一条边就形成圈；（3）在树中去掉任意一条边图就变为不连通。）在树中去掉任意一条边图就变为不连通。在一个连通图在一个连通图G中，中，取部分边连接取部分边连接G的所的所有点组成的树称为有点组成的树称为G的的部分树部分树或或支撑树支撑树(SpanningTree)。图图62是图是图61的的部分树。部分树。v1v2v3v4v5v64321图图6276.1最小树问题最小树问题Minimaltreeproblem6.1.2最小部分树最小部分

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

16、problem5v1v2v3v4v5v6843752618图图61【例例6.1】用破圈法求图用破圈法求图61的最小树。的最小树。图图64图图64就是图就是图61的最小部分树，最小树长为的最小部分树，最小树长为C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同度相同6.1最小树问题最小树问题Minimaltreeproblem加边法加边法：取图：取图G的的n个孤立点个孤立点v1，v2，vn作

17、为一个支撑作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）条边）v1v2v3v4v5v643521图图65在图在图65中，如果添加边中，如果添加边v1,v2就形成圈就形成圈v1,v2,v4，这时就这时就应避开添加边应避开添加边v1,v2，添加下一条最短边添加下一条最短边v3,v6。破圈法和加边破圈法和加边法得到树的形状可能不一样，但最小树的长度相等法得到树的形状可能不一样，但最小树的长度相等5v1v3v515v2v4v684375268MinC(T)=156.1最小树问题最小树问题Minimaltreeprobl

18、em下一节：最短路问题下一节：最短路问题1.树、支撑树、最小支撑树的概念树、支撑树、最小支撑树的概念2.掌握求最小树的方法：掌握求最小树的方法：（1）破圈法）破圈法（2）加边法）加边法作业：作业：P149T1，4，56.1最小树问题最小树问题Minimaltreeproblem6.2最短路问题最短路问题ShortestPathProblem最短路问题在实际中具有广泛的应用，如管道铺设、线路选择最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题路问题求最短路有两种算法：求最短路有

19、两种算法：一是求从某一点至其它各点之间最短离的一是求从某一点至其它各点之间最短离的狄克斯屈拉狄克斯屈拉(Dijkstra)算法算法另一种是求网络图上任意两点之间最短路的另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德弗洛伊德)矩阵算法。矩阵算法。最短路问题，就是从给定的网络图中找出一点到各点或任意两最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路点之间距离最短的一条路6.2.1最短路问题的网络模型最短路问题的网络模型6.2最短路问题最短路问题ShortestPathProblem610123214675811165图图669【例例6.3】图图66中的权中的

20、权cij表示表示vi到到vj的距离（费用、时间），从的距离（费用、时间），从v1修一条公路或架设一条高压线到修一条公路或架设一条高压线到v7，如何选择一条路线使距离如何选择一条路线使距离最短，建立该问题的网络数学模型。最短，建立该问题的网络数学模型。6.2最短路问题最短路问题ShortestPathProblem【解解】设设xij为选择弧为选择弧(i，j)的状态变量，选择弧的状态变量，选择弧(i，j)时时xij1，不不选择弧选择弧(i，j)时时xij0，得到最短路问题的网络模型：得到最短路问题的网络模型：(,)12(,)(,)57131467min102,3,610(,)ijiji jEijk

21、ii jEk iEijZc xxxxxxixxxi jE或1，6.2最短路问题最短路问题ShortestPathProblem6.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)找出所有已标号找出所有已标

22、号vi未未标号标号vj的弧集合的弧集合B=(i，j)，如果这样如果这样的弧不存在或的弧不存在或vt已已标号则计算结束；标号则计算结束；(3)计算集合计算集合B中弧中弧k(i，j)=b(i)+cij的标号的标号(4)选一个点标号选一个点标号返回到第返回到第(2)步。步。)(,),(|),(min)(lbvBjijiklblj处标号在终点6.2最短路问题最短路问题ShortestPathProblem610123214675811165图图6690610129209186161217162432182929【例例6.4】用用Dijkstra算法求图算法求图66所示所示v1到到v7的最短路及最短路长

23、的最短路及最短路长v1到到v7的最短路为：的最短路为：p17=v1,v2,v3,v5,v7，最短路长为最短路长为L17=296.2最短路问题最短路问题ShortestPathProblem14从上例知，只要某点已标号，说明已找到起点从上例知，只要某点已标号，说明已找到起点vs到该点的最短路到该点的最短路线及最短距离，因此可以将每个点标号，求出线及最短距离，因此可以将每个点标号，求出vs到到任意点的最短任意点的最短路线，如果某个点路线，如果某个点vj不能标号，说明不能标号，说明vs不可不可达达vj。6.2.3无向图最短路的求法无向图最短路的求法无向图最短路的求法只将上述步骤（无向图最短路的求法只

24、将上述步骤（2）改动一下即可。）改动一下即可。点标号：点标号：b(i)起点起点vs到点到点vj的最短路长；的最短路长；边标号：边标号：k(i，j)=b(i)+cij，步骤：步骤：(1)令起点的标号；令起点的标号；b(s)0。(3)计算集合计算集合B中边中边标号：标号：ki，j=b(i)+cij)(,|,min)(lbvBjijiklblj处标号在端点(4)选一个点标号选一个点标号:返回到第返回到第(2)步。步。(2)找出所有一端找出所有一端vi已标号另一端已标号另一端vj未标号的边集合未标号的边集合B=i，j如如果这样的边不存在或果这样的边不存在或vt已已标号则计算结束；标号则计算结束；6.2

25、最短路问题最短路问题ShortestPathProblem【例例6.4】求图求图6-10所示所示v1到各点的最短路及最短距离到各点的最短路及最短距离4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是所有点都已标号，点上的标号就是v1到该点的最短距离，最短路到该点的最短距离，最短路线就是红色的链。线就是红色的链。图图6-106.2最短路问题最短路问题ShortestPathProblem6.2.4最短路的最短路的Floyd算法算法Floyd算法基本步骤算法基本步骤:(1)写出写出vi一步到达一步到达vj 的距离矩阵的距

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

27、达点步到达点vj 的最短的最短距离为距离为，则，则 vi 经经k步步 到达到达vj 的最短距离为的最短距离为(1)krjL(1)krjL(6.1)6.2最短路问题最短路问题ShortestPathProblem()(1)(1)minkkkijirrjrLLL最短距离矩阵记为最短距离矩阵记为()()kkijLL(4)比较矩阵比较矩阵Lk与与Lk1，当，当LkLk1时得到任意两点间的最短距时得到任意两点间的最短距离矩阵离矩阵Lk。设图的点数为设图的点数为n并且并且cij0，迭代次数迭代次数k由式由式(6.3)估计得到。估计得到。(6.2)121221kknlg(1)1lg 2nkk(6.3)6.2

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

29、1v2v3v4v5v6v7v8v10 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最短路问题最短路问题ShortestPathProblem表表6-2最短距离表最短距离表L2v1v2v3v4v5v6v7v8v106951446v26032810514v3930571713v4525095315v514879012106v6410512

30、0214v765173102012v8141315614120计算说明：计算说明：L(2)ij等于表等于表6-1中第中第i行与第行与第j列对应元素相加取最小值。如列对应元素相加取最小值。如4341134223433344434553466347734883min,min 5,23,0,0,97,0,10,6165Lcccccccccccccccc (2)6.2最短路问题最短路问题ShortestPathProblem表表6-3计算示例计算示例:等于表等于表6-2中第中第i行与第行与第j列对应元素相加取最小值。例如，列对应元素相加取最小值。例如，v3经过三步（最多三个中间点经过三步（最多三个中间

31、点4条边）到达条边）到达v6的最短距离是的最短距离是表表6-3最短距离表最短距离表L3v1v2v3v4v5v6v7v8v10695144618v2603287514v39305710813v4525095315v514879012106v647105120214v76583102012v818141315614120(3)ijL2222363116322633363886min,min 94,310,0,55,712,0,172,131410LLLLLLLLL (3)(2)(2)(2)(2)6.2最短路问题最短路问题ShortestPathProblem表表6-4一步到达距离表一步到达距离表L

32、1v1v2v3v4v5v6v7v105 4v2042v34072v440107v5103v6508v7206.2最短路问题最短路问题ShortestPathProblem表表6-7最短距离表最短距离表L4v1v2v3v4v5v6v7v10593419v2204-2635v364021072v44990857v5-14720-35v69141051308v786241290经计算经计算L4L5，L4是最优表。表是最优表。表6-7不是对称表，不是对称表，vi到到vj与与vj到到vi的的最短距离不一定相等。对于有负权图情形，公式最短距离不一定相等。对于有负权图情形，公式(6.3)失效。失效。6.2最

33、短路问题最短路问题ShortestPathProblem6.2.4最短路应用举例最短路应用举例6.2最短路问题最短路问题ShortestPathProblem【例例6.8】设备更新问题。企业在使用某设备时，每年年初可购设备更新问题。企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几年后卖掉重新购置新设备。已置新设备，也可以使用一年或几年后卖掉重新购置新设备。已知知4年年初购置新设备的价格分别为年年初购置新设备的价格分别为2.5、2.6、2.8和和3.1万元。设万元。设备使用了备使用了14年后设备的残值分别为年后设备的残值分别为2、1.6、1.3和和1.1万元，使万元，使用时间在用时间

34、在14年内的维修保养费用分别为年内的维修保养费用分别为0.3、0.8、1.5和和2.0万万元。试确定一个设备更新策略，在下例两种情形下使元。试确定一个设备更新策略，在下例两种情形下使4年的设备年的设备购置和维护总费用最小。购置和维护总费用最小。（1）第）第4年年末设备一定处理掉；年年末设备一定处理掉；（2）第）第4年年末设备不处理。年年末设备不处理。【解解】画网络图。用点画网络图。用点(1,i,j)表示第表示第1年年初购置设备使用到第年年初购置设备使用到第i年年初更新，经过若干次更新使用到第年年初更新，经过若干次更新使用到第j年年初，第年年初，第1年年初和年年初和第第5年年初分别用年年初分别用

35、及及表示。使用过程用弧连接起来，弧上的表示。使用过程用弧连接起来，弧上的权表示总费用权表示总费用(购置费维护费残值购置费维护费残值)，如图，如图616所示所示6.2最短路问题最短路问题ShortestPathProblem点（点（1,3）和点（）和点（1,2,3）不能合并成一个点，虽然都是第三年）不能合并成一个点，虽然都是第三年年初购置新设备，购置费用相同，但残值不同。点年初购置新设备，购置费用相同，但残值不同。点(1,3)的残值的残值等于等于1.6(使用了两年使用了两年)，点，点(1,2,3)的残值等于的残值等于2(使用了一年使用了一年)。点。点（1,3）到点（）到点（1,3,4）的总费用为

36、）的总费用为第三年的购置费第一年的维护费设备使用两年后的残值第三年的购置费第一年的维护费设备使用两年后的残值2.8+0.31.6=1.5点（点（1,3）到点）到点的总费用为的总费用为第三年的购置费第一年的维护费第二年的维护费设备使第三年的购置费第一年的维护费第二年的维护费设备使用两年后的残值第四年末的残值用两年后的残值第四年末的残值2.8+0.3+0.81.61.6=0.7。费用表见教材费用表见教材P135表表6-8。6.2最短路问题最短路问题ShortestPathProblem（2）第四年末不处理设备：）第四年末不处理设备：将图将图616第第4年的数据换成表年的数据换成表6-8最最后一列，

37、求点后一列，求点到点到点的最短路。最短路线为：的最短路。最短路线为：(1,2)(1,2,3)，最短路长为，最短路长为5.6，即总费用为，即总费用为5.6万元。万元。更新方案与第一种情形相同。更新方案与第一种情形相同。（1）第四年末处理设备：）第四年末处理设备：求点求点到点到点的最短路。用的最短路。用Dijkstra算法得到最短路线为：算法得到最短路线为：(1,2)(1,2,3)，最短路长为，最短路长为4。4年总费用最小的设备更新方案是：第年总费用最小的设备更新方案是：第1年购置设备使用年购置设备使用1年，年，第第2年更新设备使用年更新设备使用1年后卖掉，第年后卖掉，第3年购置设备使用年购置设备

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

39、服务点有不同的标准。像对于不同的问题，寻求最佳服务点有不同的标准。像图图614只有两点间的距离，可以采用只有两点间的距离，可以采用“使最大服务距离达到使最大服务距离达到最小最小”为标准，计算步骤如下。为标准，计算步骤如下。第一步：利用第一步：利用Floyd算法求出任意两点之间的最短距离表算法求出任意两点之间的最短距离表（表（表63）。）。第二步：计算最短距离表中每行的最大距离的最小值，即第二步：计算最短距离表中每行的最大距离的最小值，即 ijjiLLmaxmin6.2最短路问题最短路问题ShortestPathProblem引用例引用例6.6计算的结果，对表计算的结果，对表33每行取最大值再取

40、最小值，见每行取最大值再取最小值，见表表69倒数第二列。倒数第二列。v1v2v3v4v5v6v7v8Max Lij总运量总运量v10695144618183220v2603287514142465v39305710813132955v4525095315152450v514879012106143780v647105120214142960v76583102012122560v818141315614120185040产量产量8050704030356065表表69表表69中倒数第二列最小值为中倒数第二列最小值为12，位于第，位于第7行，则行，则v7为网络的中为网络的中心，最佳服务点应设置在心

41、，最佳服务点应设置在v7。6.2最短路问题最短路问题ShortestPathProblem如果每个点还有一个权数，例如一个网点的人数、需要运送的如果每个点还有一个权数，例如一个网点的人数、需要运送的物质数量、产量等，这时采用物质数量、产量等，这时采用“使总运量最小使总运量最小”为标准，计算为标准，计算方法是将上述第二步的最大距离改为总运量，总运量的最小值方法是将上述第二步的最大距离改为总运量，总运量的最小值对应的点就是最佳服务点。对应的点就是最佳服务点。表表69中最后一行是点中最后一行是点vj的产量，将各行的最小距离分别乘以产的产量，将各行的最小距离分别乘以产量得到总运量，例如，量得到总运量，

42、例如，08065018653220，见，见表表69最后一列，最小运量为最后一列，最小运量为2450，最佳服务点应设置在，最佳服务点应设置在v4。6.2最短路问题最短路问题ShortestPathProblem下一节：最大流问题下一节：最大流问题6.2最短路问题最短路问题ShortestPathProblem1.最短路的概念及应用。最短路的概念及应用。2.有向图、无向图一点到各点最短路的有向图、无向图一点到各点最短路的Dijkstra算法算法3.任意两点最短路的任意两点最短路的Floyd算法算法4.本节介绍了两个应用：设备更新问题和最佳服务点设置问题本节介绍了两个应用：设备更新问题和最佳服务点设

43、置问题作业：作业：P149T2,6,7,8,96.3最大流问题最大流问题MaximalFlowProblem6.3最大流问题最大流问题MaximalFlowProblem6.3.1基本概念基本概念8145633810763图图6184图图618所示的网络图中定义了一个所示的网络图中定义了一个发点发点v1，称为源称为源(source，supplynode），），定义了一个定义了一个收点收点v7，称为汇（称为汇（sink，demandnode），），其余其余点点v2，v3，v6为为中间点中间点，称为，称为转运点转运点(transshipmentnodes)。如果如果有多个发点和收点，则虚设发点和收

44、点转化成一个发点和收点。图中有多个发点和收点，则虚设发点和收点转化成一个发点和收点。图中的权是该弧在单位时间内的最大通过能力，称为弧的的权是该弧在单位时间内的最大通过能力，称为弧的容量容量(capacity)。最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。的方向运送到收点，使总运输量最大。设设cij为弧（为弧（i，j）的容量，的容量，fij为弧（为弧（i，j）的流量。的流量。容量是弧（容量是弧（i，j）单位时间内的单位时间内的最大通过能力最大通过能力，流量是弧（，流量是弧（i，j）单位时

45、间内的单位时间内的实际通过量实际通过量，流量的集合，流量的集合f=fij称为网络的流。发点称为网络的流。发点到收点的总流量记为到收点的总流量记为v=val(f)，v也是网络的也是网络的流量流量。图图618最大流问题的线性规划数学模型为最大流问题的线性规划数学模型为),(000max67475713121312jicfvfffffffffvijijmvmjvimmm所有弧所有中间点6.3最大流问题最大流问题MaximalFlowProblem满足下例满足下例3个条件的流个条件的流fij的集合的集合f=fij 称为可行流称为可行流1)0(,)ijijfci j（所有弧(3)stsjitvvvff发

46、点发点vs流出的总流量等于流入收点流出的总流量等于流入收点vt的总流量的总流量(2)mmimmjmvvffv所有中间点6.3最大流问题最大流问题MaximalFlowProblem链：链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。从发点到收点的方向规定为链的方向。前向弧：前向弧：与链的方向相同的弧称为前向弧。与链的方向相同的弧称为前向弧。后向弧：后向弧：与链的方向相反的弧称为后向弧。与链的方向相反的弧称为后向弧。增广链增广链:设设f是一个可行流，如果存在一条从是一个可行流，如果存在一条从vs到到

47、vt的链，满足：的链，满足：1.所有前向弧上所有前向弧上fij0则该链称为增广链则该链称为增广链前向弧前向弧后向弧后向弧容量容量流量流量这是一条增这是一条增广链广链84469（5）(2)(3)(4)(6)6.3最大流问题最大流问题MaximalFlowProblem步骤如下：步骤如下：第二步：对点进行标号找一条增广链。第二步：对点进行标号找一条增广链。（1）发点标号）发点标号（）（2）选一个点）选一个点vi 已标号并且另一端未标号的弧沿着某条链向收已标号并且另一端未标号的弧沿着某条链向收点检查：点检查：A如果弧的方向向前（前向弧）并且有如果弧的方向向前（前向弧）并且有fij0，则，则vj标号标

48、号:jfji当收点已得到标号时，说明已找到增广链，依据当收点已得到标号时，说明已找到增广链，依据vi 的标号反向跟的标号反向跟踪得到一条增广链。当收点不能得到标号时，说明不存在增广踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算结束。链，计算结束。第一步：第一步：找出第一个可行流，例如所有弧的流量找出第一个可行流，例如所有弧的流量fij=06.3.2Ford-Fulkerson标号算法标号算法6.3最大流问题最大流问题MaximalFlowProblem第三步：调整流量第三步：调整流量（1）求增广链上点）求增广链上点vi 的标号的最小值，得到调整量的标号的最小值，得到调整量 mi

49、njj（2）调整流量）调整流量),(),(),(1jifjifjiffijijij得到新的可行流得到新的可行流f1，去掉所有标号，返回到第二步从发点重新去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止标号寻找增广链，直到收点不能标号为止【定理定理6.1】可行流可行流f是最大流的充分必要条件是不存在发点到是最大流的充分必要条件是不存在发点到收点的增广链收点的增广链6.3最大流问题最大流问题MaximalFlowProblem8145633810763图图619(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)【例例6.10】求图求图618发点发点

50、v1到收点到收点v7的最大流及最大流量的最大流及最大流量【解解】给定初始可行流，见图给定初始可行流，见图6-196.3最大流问题最大流问题MaximalFlowProblem8145633810763图图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),=(3，2)，调整量为增广链上点标号的最小值调整量为增广链上点