运筹学ppt课件Ch6网络模型.ppt

运 筹 学 Operations Research,Chapter 6 网络模型Network Modeling,6.1 最小(支撑)树问题 Minimal(Spanning)Tree Problem6.2 最短路问题 Shortest Path Problem 6.3 最大流问题 Maximal Flow Problem6.4 旅行售货员与中国邮路问题 Traveling Salesman and China Carrier Problem,2023/9/16,5,v1,v2,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,图61,运筹学中研究的图具有下列特征：（1）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系。（2）强调点与点之间的关联关系，不讲究图的比例大小与形状。（3）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义。（4）建立一个网络模型，求最大值或最小值。,2023/9/16,边用vi,vj表示或简记为i，j，集合记为,如图61所示，点集合记为,边上的数字称为权，记为wvi,vj、wi，j或wij，集合记为,连通的赋权图称为网络图，记为 GV，E，W,5,v1,v2,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,图61,6.1 最小(支撑)树问题 Minimal(Spanning)Tree Problem,2023/9/16,树的概念,一个无圈并且连通的无向图称为树图或简称树(Tree)。组织机构、家谱、学科分支、因特网络、通讯网络及高压线路网络等都能表达成一个树图。,可以证明：（1）一棵树的边数等于点数减1；（2）在树中任意两个点之间添加一条边就形成圈；（3）在树中去掉任意一条边图就变为不连通。,在一个连通图G中，取部分边连接G的所有点组成的树称为G的部分树或支撑树(Spanning Tree)。图62是图61的部分树。,6.1 最小树问题 Minimal tree problem,2023/9/16,6.1.2 最小部分树,将网络图G边上的权看作两点间的长度（距离、费用、时间），定义G的部分树T的长度等于T中每条边的长度之和，记为C(T)。G的所有部分树中长度最小的部分树称为最小部分树，或简称为最小树。,最小部分树可以直接用作图的方法求解，常用的有破圈法和加边法。破圈法：任取一圈，去掉圈中最长边，直到无圈。,6.1 最小树问题 Minimal tree problem,2023/9/16,5,v1,v2,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,图61,【例6.1】用破圈法求图61的最小树。,图64,图64就是图61的最小部分树，最小树长为 C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同,6.1 最小树问题 Minimal tree problem,2023/9/16,加边法：取图G的n个孤立点v1，v2，vn作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）,v1,v2,v3,v4,v5,v6,图65,在图65中，如果添加边v1,v2就形成圈v1,v2,v4，这时就应避开添加边v1,v2，添加下一条最短边v3,v6。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等,Min C(T)=15,6.1 最小树问题 Minimal tree problem,2023/9/16,下一节：最短路问题,1.树、支撑树、最小支撑树的概念2.掌握求最小树的方法：（1）破圈法（2）加边法,作业：P149 T 1，4，5,6.1 最小树问题 Minimal tree problem,6.2 最短路问题 Shortest Path Problem,2023/9/16,最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题,求最短路有两种算法：一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法 另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德)矩阵算法。,最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路,最短路问题的网络模型,6.2 最短路问题 Shortest Path Problem,2023/9/16,6,10,12,3,2,14,6,7,5,8,11,16,5,图66,9,【例6.3】图66中的权cij表示vi到vj的距离（费用、时间），从v1修一条公路或架设一条高压线到v7，如何选择一条路线使距离最短，建立该问题的网络数学模型。,6.2 最短路问题 Shortest Path Problem,2023/9/16,【解】设xij为选择弧(i，j)的状态变量，选择弧(i，j)时xij1，不选择弧(i，j)时xij0，得到最短路问题的网络模型：,6.2 最短路问题 Shortest Path Problem,2023/9/16,有向图的狄克斯屈拉(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 最短路问题 Shortest Path Problem,2023/9/16,6,10,12,3,2,14,6,7,5,8,11,16,5,图66,9,0,6,10,12,9,20,9,18,6,16,12,17,16,24,32,18,29,29,【例6.4】用Dijkstra算法求图66 所示v1到v7的最短路及最短路长,v1 到v7的最短路为：p17=v1,v2,v3,v5,v7，最短路长为L17=29,6.2 最短路问题 Shortest Path Problem,14,2023/9/16,从上例知，只要某点已标号，说明已找到起点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中边标号：ki，j=b(i)+cij,(4)选一个点标号:返回到第(2)步。,(2)找出所有一端vi已标号另一端vj未标号的边集合 B=i，j如果这样的边不存在或vt已标号则计算结束；,6.2 最短路问题 Shortest Path Problem,2023/9/16,【例6.5】求图6-10所示v1到各点的最短路及最短距离,0,4,5,2,2,3,10,3,9,6,12,6,4,11,6,6,18,8,12,24,8,24,18,所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。,图6-10,6.2 最短路问题 Shortest Path Problem,2023/9/16,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 经过k1步到达点vr 的最短距离为，vr 经过k1步到达点vj 的最短距离为，则 vi 经k步 到达vj 的最短距离为,(6.1),6.2 最短路问题 Shortest Path Problem,2023/9/16,最短距离矩阵记为,(4)比较矩阵Lk与Lk1，当LkLk1时得到任意两点间的最短距离矩阵Lk。设图的点数为n并且cij0，迭代次数k由式(6.3)估计得到。,(6.2),(6.3),6.2 最短路问题 Shortest Path Problem,2023/9/16,【例6.6】图6-14是一张8个城市的铁路交通图，铁路部门要制作一张两两城市间的距离表。这个问题实际就是求任意两点间的最短路问题。,【解】(1)依据图6-14,写出任意两点间一步到达距离表L1。见表6.1所示。本例n=8，因此计算到L3,图6-14,6.2 最短路问题 Shortest Path Problem,2023/9/16,表6-1 最短距离表 L1,6.2 最短路问题 Shortest Path Problem,2023/9/16,表6-2 最短距离表L2,计算说明：L(2)ij等于表6-1中第i行与第j列对应元素相加取最小值。如,6.2 最短路问题 Shortest Path Problem,2023/9/16,表6-3计算示例:等于表6-2中第i行与第j列对应元素相加取最小值。例如，v3经过三步（最多三个中间点4条边）到达v6的最短距离是,表6-3 最短距离表L3,6.2 最短路问题 Shortest Path Problem,2023/9/16,【例6.7】求图615中任意两点间的最短距离。【解】图615是一个混合图，有3条边的权是负数,有两条边无方向。依据图615,写出任意两点间一步到达距离表L1。表中第一列的点表示弧的起点，第一行的点表示弧的终点，无方向的边表明可以互达，见表6-4所示。计算过程见表6-56-7。,4,4,5,7,4,3,2,7,10,2,8,图615,1,5,6.2 最短路问题 Shortest Path Problem,2023/9/16,表6-4一步到达距离表L1,6.2 最短路问题 Shortest Path Problem,2023/9/16,表6-7 最短距离表L4,经计算L4L5，L4是最优表。表6-7不是对称表，vi到vj与vj到vi的最短距离不一定相等。对于有负权图情形，公式(6.3)失效。,6.2 最短路问题 Shortest Path Problem,2023/9/16,6.2.4 最短路应用举例,6.2 最短路问题 Shortest Path Problem,【例6.8】设备更新问题。企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几年后卖掉重新购置新设备。已知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年的设备购置和维护总费用最小。（1）第4年年末设备一定处理掉；（2）第4年年末设备不处理。,【解】画网络图。用点(1,i,j)表示第1年年初购置设备使用到第i年年初更新，经过若干次更新使用到第j年年初，第1年年初和第5年年初分别用及表示。使用过程用弧连接起来，弧上的权表示总费用(购置费维护费残值)，如图616所示,2023/9/16,6.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.1,0.9,1.5,0.7,3.6,2.8,1.7,-0.2,1.9,1.1,2.1,0.3,-0.6,-0.6,网络图616说明：如图中点(1,3)表示第1年购置设备使用两年到第3年年初更新购置新设备，这时有2种更新方案，使用1年到第4年年初、使用2年到第5年年初,更新方案用弧表示，点（1,2,3）表示第1年购置设备使用一年到第二年年初又更新，使用一年到第三年初再更新，这时仍然有2种更新方案，使用1年到第4年年初和使用2年到第5年年初。,2023/9/16,6.2 最短路问题 Shortest Path Problem,点（1,3）和点（1,2,3）不能合并成一个点，虽然都是第三年年初购置新设备，购置费用相同，但残值不同。点(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。,费用表见教材P135表6-8。,2023/9/16,6,图616,(1,2,3),(1,4),(1,3,4),(1,2,4),(1,2,3,4),(1,2),(1,3),第一年,第二年,第三年,第四年,5.1,0.9,1.5,0.7,3.6,2.8,1.7,-0.2,1.9,1.1,2.1,0.3,-0.6,-0.6,2023/9/16,6.2 最短路问题 Shortest Path Problem,（2）第四年末不处理设备：将图616第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万元。,2023/9/16,【例6.9】服务网点设置问题。以图614为例，现提出这样一个问题，在交通网络中建立一个快速反应中心，应选择哪一个城市最好。类似地，在一个网络中设置一所学校、医院、消防站、购物中心，还有厂址选择、总部选址、公司销售中心选址等问题都属于最佳服务网点设置问题。,【解】对于不同的问题，寻求最佳服务点有不同的标准。像图614只有两点间的距离，可以采用“使最大服务距离达到最小”为标准，计算步骤如下。第一步：利用Floyd算法求出任意两点之间的最短距离表（表63）。第二步：计算最短距离表中每行的最大距离的最小值，即,6.2 最短路问题 Shortest Path Problem,2023/9/16,引用例6.6计算的结果，对表33每行取最大值再取最小值，见表69倒数第二列。,表69,表69中倒数第二列最小值为12，位于第7行，则v7为网络的中心，最佳服务点应设置在v7。,6.2 最短路问题 Shortest Path Problem,2023/9/16,如果每个点还有一个权数，例如一个网点的人数、需要运送的物质数量、产量等，这时采用“使总运量最小”为标准，计算方法是将上述第二步的最大距离改为总运量，总运量的最小值对应的点就是最佳服务点。表69中最后一行是点vj的产量，将各行的最小距离分别乘以产量得到总运量，例如，08065018653220，见表69最后一列，最小运量为2450，最佳服务点应设置在v4。,6.2 最短路问题 Shortest Path Problem,2023/9/16,下一节：最大流问题,6.2 最短路问题 Shortest Path Problem,1.最短路的概念及应用。2.有向图、无向图一点到各点最短路的Dijkstra算法3.任意两点最短路的Floyd算法4.本节介绍了两个应用：设备更新问题和最佳服务点设置问题,作业：P149 T 2,6,7,8,9,6.3 最大流问题Maximal Flow Problem,2023/9/16,6.3 最大流问题Maximal Flow Problem,6.3.1 基本概念,8,14,5,6,3,3,8,10,7,6,3,图618,4,图618所示的网络图中定义了一个发点v1，称为源(source，supply node），定义了一个收点v7，称为汇（sink，demand node），其余点v2，v3，v6为中间点，称为转运点(transshipment nodes)。如果有多个发点和收点，则虚设发点和收点转化成一个发点和收点。图中的权是该弧在单位时间内的最大通过能力，称为弧的容量(capacity)。最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。,2023/9/16,设cij为弧（i，j）的容量，fij为弧（i，j）的流量。容量是弧（i，j）单位时间内的最大通过能力，流量是弧（i，j）单位时间内的实际通过量，流量的集合f=fij称为网络的流。发点到收点的总流量记为v=val(f)，v也是网络的流量。,图618最大流问题的线性规划数学模型为,6.3 最大流问题Maximal Flow Problem,2023/9/16,满足下例3个条件的流fij 的集合 f=fij 称为可行流,发点vs流出的总流量等于流入收点vt的总流量,6.3 最大流问题Maximal Flow Problem,2023/9/16,链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。,前向弧：与链的方向相同的弧称为前向弧。,后向弧：与链的方向相反的弧称为后向弧。,增广链:设 f 是一个可行流，如果存在一条从vs到vt的链，满足：,1.所有前向弧上fijCij,2.所有后向弧上fij0,则该链称为增广链,容量,流量,6.3 最大流问题Maximal Flow Problem,2023/9/16,步骤如下：,第二步：对点进行标号找一条增广链。（1）发点标号（）（2）选一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查：A如果弧的方向向前（前向弧）并且有fij0，则vj标号:jfji当收点已得到标号时，说明已找到增广链，依据vi 的标号反向跟踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算结束。,第一步：找出第一个可行流，例如所有弧的流量fij=0,6.3.2 Ford-Fulkerson标号算法,6.3 最大流问题Maximal Flow Problem,2023/9/16,第三步：调整流量（1）求增广链上点vi 的标号的最小值，得到调整量,（2）调整流量,得到新的可行流f1，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止,【定理6.1】可行流f是最大流的充分必要条件是不存在发点到收点的增广链,6.3 最大流问题Maximal Flow Problem,2023/9/16,8,14,5,6,3,3,8,10,7,6,3,图619,(10),(6),(3),(6),(3),(7),(0),(6),(1),4,(3),(1),(7),【例6.10】求图618发点v1到收点v7的最大流及最大流量,【解】给定初始可行流，见图6-19,6.3 最大流问题Maximal Flow Problem,2023/9/16,8,14,5,6,3,3,8,10,7,6,3,图620(b),(10),(6),(3),(6),(3),(7),(0),(6),(1),4,(3),(1),(7),2,3,3,7,第一轮标号：,c12f12,v2标号2,增广链(1,2)，(3,2)，(3,4)，(4,7),+=(1,2)，(3,4)，(4,7),=(3，2)，调整量为增广链上点标号的最小值min，2，3，3，72,6.3 最大流问题Maximal Flow Problem,2023/9/16,8,14,5,6,3,3,8,10,7,6,3,图621,(10),(8),(1),(6),(3),(7),(2),(6),(1),4,(5),(1),(7),调整后的可行流：,6.3 最大流问题Maximal Flow Problem,2023/9/16,8,14,5,6,3,3,8,10,7,6,3,图622,(10),(8),(1),(6),(3),(7),(2),(6),(1),4,(5),(1),(7),4,4,1,5,第二轮标号：,增广链(1,3)，(3,4)，(4,7)，调整量为 min，4，1，51,6.3 最大流问题Maximal Flow Problem,2023/9/16,8,14,5,6,3,3,8,10,7,6,3,图623,(11),(8),(1),(6),(3),(7),(3),(6),(1),4,(6),(1),(7),调整后得到可行流：,6.3 最大流问题Maximal Flow Problem,2023/9/16,8,14,5,6,3,3,8,10,7,6,3,图622,(11),(8),(1),(6),(3),(7),(3),(6),(1),4,(6),(1),(7),3,1,4,第三轮标号：,增广链(1,3)，(3,6)，(6,4)，(4,7)，调整量为 min，3，1，2，41,2,6.3 最大流问题Maximal Flow Problem,2023/9/16,8,14,5,6,3,3,8,10,7,6,3,图625,(12),(8),(1),(6),(3),(8),(3),(6),(2),4,(7),(1),(7),调整后得到可行流：,6.3 最大流问题Maximal Flow Problem,2023/9/16,8,14,5,6,3,3,8,10,7,6,3,图622,(12),(8),(1),(6),(3),(8),(3),(6),(2),4,(7),(1),(7),2,第四轮标号：,v7得不到标号，不存在v1到 v7的增广链，图6-22所示的可行流是最大流，最大流量为 vf12+f138+12=20,4,6.3 最大流问题Maximal Flow Problem,2023/9/16,无向图最大流标号算法,无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端vi已标号另一端vj未标号的边只要满足 Cijfij0 则vj就可标号（Cijfij）,【例】求下图v1到则v7标的最大流,7,(10),(6),(10),(8),(2),(3),(7),(6),(5),(13),(0),(13),2,3,9,9,3,6.3 最大流问题Maximal Flow Problem,2023/9/16,3,7,7,1,V=29,10,5,6,6,6.3 最大流问题Maximal Flow Problem,1,2023/9/16,截集 将图G（V，E）的点集分割成两部分,称为一个截集，截集中所有弧的容量之和称为截集的截量。,下图所示的截集为,6.3 最大流问题Maximal Flow Problem,2023/9/16,又如下图所示的截集为,上图所示的截集为,所有截量中此截量最小且等于最大流量，此截集称为最小截集。,【定理】最大流量等于最小截集的截量。,6.3 最大流问题Maximal Flow Problem,2023/9/16,6.3.4 最小费用流,满足流量达到一个固定数使总费用最小，就是最小费用流问题。另一个问题是满足流量到达最大使总费用最小，称为最小费用最大流问题。,图627是一个运输网络图，将工厂v1，v2及v3的物质(数量不限)运往v6，v4和v5是中转点，弧上的数字为（cij，dij)。,设弧（i,j）的单位流量费用为dij0，弧的容量为cij0,设可行流f的一条增广链为，称,为增广链的费用。第一个求和式是增广链中前向弧的费用之和，第二个求和式是增广链中后向弧的费用之和。d()最小的增广链称为最小费用增广链。,6.3 最大流问题Maximal Flow Problem,2023/9/16,(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),图627,图628,(12,3),(2)制定使运量最大并且总运费最小的运输方案，属于最小费用最大流问题,6.3 最大流问题Maximal Flow Problem,2023/9/16,设给定的流量为v。最小费用流的标号算法步骤如下。第1步：取初始流量为零的可行流f(0)0，令网络中所有弧的权等于dij得到一个赋权图D，用Dijkstra算法求出最短路，这条最短路就是初始最小费用增广链。,第2步：调整流量。在最小费用增广链上调整流量的方法与前面最大流算法一样，前向弧上令jcijfij，后向弧上令jfij，调整量为=minj。调整后得到最小费用流f(k)，流量为v(k)v(k1)，当v(k)v时计算结束，否则转第3步继续计算。,第3步：作赋权图D并寻找最小费用增广链。,6.3 最大流问题Maximal Flow Problem,2023/9/16,(1)对可行流f(k1)的最小费用增广链上的弧（i，j）作如下变动,第一种情形：当弧（i，j）上的流量满足0fijcij时，在点vi与vj之间添加一条方向相反的弧（j，i），权为（dij）。第二种情形：当弧（i，j）上的流量满足fijcij时将弧（i，j）反向变为（j，i）,权为（bij）。不在最小费用增广链上的弧不作任何变动，得到一个赋权网络图D。（2）求赋权图D从发点的收点的最短路，如果最短路存在，则这条最短路就是f(k1)的最小费用增广链，转第2步。赋权图D的所有权非负时，可用Dijkstra算法求最短路，存在负权时用Floyd算法。（3）如果赋权图D不存在从发点到收点的最短路，说明v(k1)已是最大流量，不存在流量等于v的流，计算结束。,6.3 最大流问题Maximal Flow Problem,2023/9/16,【例6.11】对图628，制定一个运量v15及运量最大总运费最小的运输方案。【解】令所有弧的流量等于零，得到初始可行流f(0)0，流量v(0)0，总运费d(f(0)=0。,3,5,4,2,4,6,3,12,图629,s,0,0,0,(a)f(0)，赋权图D0,最小费用增广链1：s,见图629(a),6.3 最大流问题Maximal Flow Problem,2023/9/16,调整量4，对f(0)0进行调整得到f(1)，括号（）内的数字为弧的流量，网络流量v(1)4，总运费 d(f(1)04243420如图629(b)。,图629,图中：（cij，dij)(fij),6.3 最大流问题Maximal Flow Problem,2023/9/16,3,5,4,2,4,6,3,12,图629,s,0,0,0,(c)f(1)，赋权图D1,3,(3)v(1)415，没有得到最小费用流。在图629(b)中，弧(s,1)和(4,6)满足条件0fijcij，添加两条边(1,s)和(6,4)，权分别为“0”和“3”，边(1,s)可以去掉，弧(1,4)上有fijcij说明已饱和，将弧(1,4)反向变为(4,1)，权为“2”，如图629(c)。,6.3 最大流问题Maximal Flow Problem,2023/9/16,(12,3),(3,5),(3,4),(1,6),(2,3),(9,12),图629,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)24375344如图629(d)。,6.3 最大流问题Maximal Flow Problem,2023/9/16,(4)v(2)715，对最小费用增广链2上的弧进行调整，在图629(c)中，弧(s,2)和(4,6)满足条件0fijcij，添加两条边(2,s)和(6,4)，权分别为“0”和“3”，边(2,s)可以去掉，弧(6,4)已经存在，弧(2,4)上有fijcij说明已饱和，将弧(2,4)反向变为(4,2)，权为“5”，如图629(e)。,3,5,4,2,4,6,3,12,图629,s,0,0,0,(e)f(2)，赋权图D2,3,6.3 最大流问题Maximal Flow Problem,2023/9/16,用Floyd算法得到最小费用增广链3：s，调整量1，调整后得到最小费用流f(3)，流量v(3)8，总运费 d(f(3)2438536153如图629(f)。,(12,3),(3,5),(3,4),(1,6),(2,3),(9,12),图629,s,(10,0),(6,0),(3,0),(f)f(3),(4),(4),(8),(6,4),(4,2),(3),(3),(1),(1),6.3 最大流问题Maximal Flow Problem,2023/9/16,(5)类似地，得到图629(g),3,5,4,2,4,6,3,12,图629,s,0,0,0,(g)f(3)，赋权图D3,3,(12,3),(3,5),(3,4),(1,6),(2,3),(9,12),图629,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。见图629(h),6.3 最大流问题Maximal Flow Problem,2023/9/16,最小费用增广链5：s,调整量6，取5，流量v(5)v15得到满足，最小费用流见图629(j)，问题1计算结束。,3,5,4,2,4,6,3,12,图629,s,0,0,0,(i)f(4)，赋权图D4,3,12,(12,3),(3,5),(3,4),(1,6),(2,3),(9,12),图629,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)由图629(g)及(h),得到图 629(i),6.3 最大流问题Maximal Flow Problem,2023/9/16,(7)求最小费用最大流。对图629(i)的最小费用增广链5，取调整量6对流量调整，得到图630(a)及赋权图630(b),(12,3),(3,5),(3,4),(1,6),(2,3),(9,12),图630,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 最大流问题Maximal Flow Problem,2023/9/16,3,5,4,2,4,6,3,12,图630,s,0,0,0,(b)f(5)，赋权图D5,3,12,(8)图630(b)的最小费用增广链6：s，,6.3 最大流问题Maximal Flow Problem,2023/9/16,(12,3),(3,5),(3,4),(1,6),(2,3),(9,12),图630,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)，见图630(c)。,6.3 最大流问题Maximal Flow Problem,2023/9/16,赋权图见图630（d）。图630(d)不存在从vs发点到v6的最短路，则图630(c)的流就是最小费用最大流，最大流量v=17，最小的总运费为d(f)=4446534161323899176,3,5,4,2,4,6,3,12,图630,s,0,0,0,(d)f(6)，赋权图D6,3,4,3个工厂分别运送10、4及3个单位物质到v6，总运量为17，运费为176,6.3 最大流问题Maximal Flow Problem,2023/9/16,最大流应用举例,1.二分图的最大匹配问题,【例6.12】某公司需要招聘5个专业的毕业生各一个，通过本人报名和筛选，公司最后认为有6人都达到录取条件。这6人所学专业见表6-10,表中打“”表示该生所学专业。公司应招聘哪几位毕业生，如何分配他们的工作,表6-10,6.3 最大流问题Maximal Flow Problem,2023/9/16,A,B,C,D,E,s,t,(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),图632,【解】画出一个二分图，虚设一个发点和一收点，每条弧上的容量等于1，问题为求发点到收点的最大流，求解结果之一见图632。公司录取第26号毕业生，安排的工作依次为管理信息、企业管理、市场营销、工程管理和计算机。,6.3 最大流问题Maximal Flow Problem,2023/9/16,【例6.13】某市政工程公司在未来58月份内需完成4项工程：A.修建一条地下通道、B.修建一座人行天桥、C.新建一条道路及D.道路维修。工期和所需劳动力见表6-11。该公司共有劳动力120人，任一项工程在一个月内的劳动力投入不能超过80人，问公司如何分配劳动力完成所有工程，是否能按期完成,表6-12,【解】将工程计划用网络图633表示。设点v5、v6、v7、v8分别表示58月份，Ai、Bi、Ci、Di表示工程在第i个月内完成的部分，用弧表示某月完成某项工程的状态，弧的容量为劳动力限制。就是求图633从发点到收点的最大流问题。,6.3 最大流问题Maximal Flow Problem,2023/9/16,A5,B6,C7,D8,s,t,图633,A6,C5,A7,C6,B7,C8,A,B,C,D,120,120,120,120,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,100,80,200,80,(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 最大流问题Maximal Flow Problem,2023/9/16,Ford-Fulkerson标号算法求解得到图633，括号内的数字为弧的流量。每个月的劳动力分配见表6-13。5月份有剩余劳动力20人，4项工程恰好按期完成,表6-13,6.3 最大流问题Maximal Flow Problem,2023/9/16,下一节：旅行售货员与中国邮路问题,1.最大流的概念：容量、流量、可行流、最大流、前向弧、后向弧、增广链、截集、截量、最小截量与最大流量的关系、最小费用流、最小费用最大流。2.有向图、无向图最大流的Ford-Fulkerson标号算法3.最小费用流、最小费用最大流的算法4.本节介绍了两个应用：最大匹配问题和劳动力合理配置问题,作业：P149 T 3，10，11,6.3 最大流问题Maximal Flow Problem,6.4 旅行售货员与中国邮路问题 Traveling Salesman and China Carrier Problem,2023/9/16,6.4 旅行售货员与中国邮路问题,6.4.1 旅行售货员问题(Traveling salesman problem),【例6.14】某电动汽车公司与学校合作，拟定在校园内开通无污染无噪音的“绿色交通”路线