运筹学-网络模型课件

运筹学

Operations

Research

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

6.3最大流问题MaximalFlowProblem6.4旅行售货员与中国邮路问题

TravelingSalesmanandChinaCarrierProblem

3/17/20235v1v2v3v4v5v6843752618图6－1运筹学中研究的图具有下列特征：（1）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系。（2）强调点与点之间的关联关系，不讲究图的比例大小与形状。（3）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义。（4）建立一个网络模型，求最大值或最小值。3/17/2023边用[vi,vj]表示或简记为[i，j]，集合记为如图6－1所示，点集合记为边上的数字称为权，记为w[vi,vj]、w[i，j]或wij，集合记为连通的赋权图称为网络图，记为G＝｛V，E，W｝5v1v2v3v4v5v6843752618图6－13/17/20236.1.1树的概念一个无圈并且连通的无向图称为树图或简称树(Tree)。组织机构、家谱、学科分支、因特网络、通讯网络及高压线路网络等都能表达成一个树图。可以证明：（1）一棵树的边数等于点数减1；（2）在树中任意两个点之间添加一条边就形成圈；（3）在树中去掉任意一条边图就变为不连通。在一个连通图G中，取部分边连接G的所有点组成的树称为G的部分树或支撑树(SpanningTree

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

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

Minimaltreeproblem3/17/20235v1v2v3v4v5v6843752618图6－1【例6.1】用破圈法求图6－1的最小树。图6－4图6－4就是图6－1的最小部分树，最小树长为C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同6.1最小树问题

Minimaltreeproblem3/17/2023下一节：最短路问题1.树、支撑树、最小支撑树的概念2.掌握求最小树的方法：（1）破圈法（2）加边法作业：P149T1，4，56.1最小树问题

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

3/17/2023【解】设xij为选择弧(i，j)的状态变量，选择弧(i，j)时xij＝1，不选择弧(i，j)时xij＝0，得到最短路问题的网络模型：6.2最短路问题ShortestPathProblem

3/17/20236.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

3/17/2023②③④⑤⑥⑦610123214675811165图6－690610129209186①161217162432182929【例6.4】用Dijkstra算法求图6－6所示v1到v7的最短路及最短路长v1到v7的最短路为：p17=｛v1,v2,v3,v5,v7｝，最短路长为L17=296.2最短路问题ShortestPathProblem

143/17/2023【例6.5】求图6-10所示v1到各点的最短路及最短距离①②③④⑤⑥⑦⑧4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。图6-106.2最短路问题ShortestPathProblem

3/17/20236.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

3/17/2023最短距离矩阵记为(4)比较矩阵Lk与Lk－1，当Lk＝Lk－1时得到任意两点间的最短距离矩阵Lk。设图的点数为n并且cij≥0，迭代次数k由式(6.3)估计得到。(6.2)(6.3)6.2最短路问题ShortestPathProblem

3/17/2023v1v2v3v4v5v6v7v8v106∞5∞4∞∞v260328∞∞∞v3∞30∞7∞∞16v452∞09123∞v5∞8790∞106v64∞∞12∞02∞v7∞∞∞3102012v8∞∞16∞6∞120表6-1最短距离表L16.2最短路问题ShortestPathProblem

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

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

3/17/2023表6-4一步到达距离表L1v1v2v3v4v5v6v7v105∞∞

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

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

3/17/20236.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。费用表见教材P135表6-8。3/17/2023①⑤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.63/17/20236.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万元。3/17/2023【例6.9】服务网点设置问题。以图6－14为例，现提出这样一个问题，在交通网络中建立一个快速反应中心，应选择哪一个城市最好。类似地，在一个网络中设置一所学校、医院、消防站、购物中心，还有厂址选择、总部选址、公司销售中心选址等问题都属于最佳服务网点设置问题。【解】对于不同的问题，寻求最佳服务点有不同的标准。像图6－14只有两点间的距离，可以采用“使最大服务距离达到最小”为标准，计算步骤如下。第一步：利用Floyd算法求出任意两点之间的最短距离表（表6－3）。第二步：计算最短距离表中每行的最大距离的最小值，即6.2最短路问题ShortestPathProblem

3/17/2023引用例6.6计算的结果，对表3－3每行取最大值再取最小值，见表6－9倒数第二列。v1v2v3v4v5v6v7v8MaxLij总运量v10695144618183220v2603287514142465v39305710813132955v4525095315152450v514879012106143780v647105120214142960v76583102012122560v818141315614120185040产量8050704030356065表6－9表6－9中倒数第二列最小值为12，位于第7行，则v7为网络的中心，最佳服务点应设置在v7。6.2最短路问题ShortestPathProblem

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

3/17/2023下一节：最大流问题6.2最短路问题ShortestPathProblem

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

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

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

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

=06.3.2Ford-Fulkerson标号算法6.3最大流问题MaximalFlowProblem3/17/2023第三步：调整流量（1）求增广链上点vi

的标号的最小值，得到调整量（2）调整流量得到新的可行流f1，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止【定理6.1】可行流f是最大流的充分必要条件是不存在发点到收点的增广链6.3最大流问题MaximalFlowProblem3/17/2023①②③④⑤⑥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最大流问题MaximalFlowProblem3/17/2023①②③④⑤⑥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最大流问题MaximalFlowProblem3/17/2023①②③④⑤⑥814563381076⑦3图6－21(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)调整后的可行流：6.3最大流问题MaximalFlowProblem3/17/2023①②③④⑤⑥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最大流问题MaximalFlowProblem3/17/2023①②③④⑤⑥814563381076⑦3图6－23(11)(8)(1)(6)(3)(7)(3)(6)(1)4(6)(1)(7)调整后得到可行流：6.3最大流问题MaximalFlowProblem3/17/2023①②③④⑤⑥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最大流问题MaximalFlowProblem3/17/2023①②③④⑤⑥814563381076⑦3图6－25(12)(8)(1)(6)(3)(8)(3)(6)(2)4(7)(1)(7)调整后得到可行流：6.3最大流问题MaximalFlowProblem3/17/2023①②③④⑤⑥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最大流问题MaximalFlowProblem3/17/2023无向图最大流标号算法无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端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最大流问题MaximalFlowProblem3/17/20237①②③④⑤⑥⑦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最大流问题MaximalFlowProblem13/17/2023截集将图G＝（V，E）的点集分割成两部分称为一个截集，截集中所有弧的容量之和称为截集的截量。①②③④⑤⑥68441226796411322306下图所示的截集为6.3最大流问题MaximalFlowProblem3/17/2023①②③④⑤⑥68441226796401322106又如下图所示的截集为上图所示的截集为所有截量中此截量最小且等于最大流量，此截集称为最小截集。【定理】最大流量等于最小截集的截量。6.3最大流问题MaximalFlowProblem3/17/20236.3.4最小费用流满足流量达到一个固定数使总费用最小，就是最小费用流问题。另一个问题是满足流量到达最大使总费用最小，称为最小费用最大流问题。图6－27是一个运输网络图，将工厂v1，v2及v3的物质(数量不限)运往v6，v4和v5是中转点，弧上的数字为（cij，dij)。设弧（i,j）的单位流量费用为dij≥0，弧的容量为cij≥0设可行流f的一条增广链为μ，称为增广链μ的费用。第一个求和式是增广链中前向弧的费用之和，第二个求和式是增广链中后向弧的费用之和。d(μ)最小的增广链称为最小费用增广链。6.3最大流问题MaximalFlowProblem3/17/2023(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最大流问题MaximalFlowProblem3/17/2023设给定的流量为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最大流问题MaximalFlowProblem3/17/2023(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最大流问题MaximalFlowProblem3/17/2023【例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最大流问题MaximalFlowProblem3/17/2023调整量θ＝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最大流问题MaximalFlowProblem3/17/2023354－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最大流问题MaximalFlowProblem3/17/2023(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最大流问题MaximalFlowProblem3/17/2023(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最大流问题MaximalFlowProblem3/17/2023用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最大流问题MaximalFlowProblem3/17/2023(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最大流问题MaximalFlowProblem3/17/2023最小费用增广链μ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最大流问题MaximalFlowProblem3/17/2023(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最大流问题MaximalFlowProblem3/17/20233－5－4－24－6－312图6－30①②③④⑤⑥s000(b)f(5)，赋权图D5－3－12(8)图6－30(b)的最小费用增广链μ6：s→②→⑤→⑥，6.3最大流问题MaximalFlowProblem3/17/2023(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最大流问题MaximalFlowProblem3/17/2023赋权图见图6－30（d）。图6－30(d)不存在从vs发点到v6的最短路，则图6－30(c)的流就是最小费用最大流，最大流量v=17，最小的总运费为d(f)=4×4＋4×6＋5×3＋4×1＋6×1＋3×2＋3×8＋9×9＝1763－5－4－24－6－3－12图6－30①②③④⑤⑥s000(d)f(6)，赋权图D6－3－43个工厂分别运送10、4及3个单位物质到v6，总运量为17，运费为1766.3最大流问题MaximalFlowProblem3/17/20236.3.5最大流应用举例1.二分图的最大匹配问题【例6.12】某公司需要招聘5个专业的毕业生各一个，通过本人报名和筛选，公司最后认为有6人都达到录取条件。这6人所学专业见表6-10,表中打“√”表示该生所学专业。公司应招聘哪几位毕业生，如何分配他们的工作毕业生A.市场营销B.工程管理C.管理信息D.计算机E.企业管理1√√2√√3√√4√√5√√6√√表6-106.3最大流问题MaximalFlowProblem3/17/2023①②③④⑤⑥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最大流问题MaximalFlowProblem3/17/2023【例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-12【解】将工程计划用网络图6－33表示。设点v5、v6、v7、v8分别表示5～8月份，Ai、Bi、Ci、Di表示工程在第i个月内完成的部分，用弧表示某月完成某项工程的状态，弧的容量为劳动力限制。就是求图6－33从发点到收点的最大流问题。6.3最大流问题MaximalFlowProblem3/17/2023⑤⑥⑦⑧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最大流问题MaximalFlowProblem3/17/2023

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

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

80

6120

4080

71208040

8120

4080合计(人)46010080200806.3最大流问题MaximalFlowProblem3/17/2023下一节：旅行售货员与中国邮路问题1.最大流的概念：容量、流量、可行流、最大流、前向弧、后向弧、增广链、截集、截量、最小截量与最大流量的关系、最小费用流、最小费用最大流。2.有向图、无向图最大流的Ford-Fulkerson标号算法3.最小费用流、最小费用最大流的算法4.本节介绍了两个应用：最大匹配问题和劳动力合理配置问题作业：P149T3，10，116.3最大流问题MaximalFlowProblem3/17/20236.4旅行售货员与中国邮路问题

TravelingSalesmanandChinaCarrierProblem3/17/20236.4旅行售货员与中国邮路问题6.4.1旅行售货员问题(Travelingsalesmanproblem)【例6.14】某电动汽车公司与学校合作，拟定在校园内开通无污染无噪音的“绿色交通”路线。图6－34是某大学教学楼和学生宿舍楼的分布图，其中C、F之间是两条单向通道，边上的数字为汽车通过两点间的正常时间（分钟）。电动汽车公司如何设计一条路线，使汽车通过每一处教学楼和宿舍楼一次后总时间最少。ABCDEF42.5332.81.61.82.64.22.21.5【解】求解过程略（见教材P145）。电动汽车公司的行车路线是A→B→F→E→D→C→A，汽车在校园行驶一圈需要15.6分钟。3/17/20236.4旅行售货员与中国邮路问题6.4.2中国邮路问题(Chinacarrierproblem)

【例6.15】求解图6－35（a）的中国邮路问题35v1v2v4v5v6v74752618图6－35v341(a)3/17/20236.4旅行售货员与中国邮路问题5v1v2v4v5v6v743752618v34141图6－36【解】最优解如图6-3614图6-36为最短欧拉回路，重复经过了[1，2]和[6，7]两条边3/17/2023TheEndofChapter6作业:P150T12(1)Hamilton回路、Euler回路。(2)旅行售货员问题(3)中国邮路问题6.4旅行售货员与中国邮路问题3/17/2023第6章部分习题答案3/17/2023v1v2v4v5v6v82685214v341v7v9v10327735234(a)图6－41习题6.4解答3/17/2023v1v2v4v5v6v8221v31v7v9v1025234(a)图6－41有4个解，minC(T)=21习题6.4解答3/17/2023v1v2v4v5v6v843721v33154v7v9v10562733234图6－41(b)习题6.4习题6.4解答3/17/2023v1v2v4v5v6v8321v331v7v9v102323图6－41(b)习题6.4解答3/17/2023BCDEFG451438686865AH1013图6－42(a)I922习题6.63/17/2023BCDEFG451438686865AH1013图6－42(a)I922习题6.6(a)求A到H、I的最短路及最短路长

【解】用Dijkstra算法

0(8)(12)(14)(14)(10)(13)(9)(12)(5)(6)5689(22)12(14)(21)(22)14(28)2221习题6.63/17/2023BCDEFG451438686865AH1013图6－42(b)I922习题6.6(b)求A到H、I的最短路及最短路长

习题6.63/17/2023BCDEFG451438686865AH1013图6－42(b)I922习题6.6(b)求A到H、I的最短路及最短路长

【解】用Dijkstra算法

(6)0(8)(12)(14)(14)(10)(13)(9)(12)(5)56891113(11)20(21)(20)(21)(27)21习题6.63/17/2023习题6.7已知某设备可继续使用5年，也可以在每年年末卖掉重新购置新设备。已知5年年初购置新设备的价格分别为3.5、3.8、4.0、4.2和4.5万元。使用时间在1～5年内的维护费用分别为0.4、0.9、1.4、2.3和3万元。试确定一个的设备更新策略，使5年的设备购置和维护总费用最小

①②③④⑤⑥3.94.24.44.64.94.86.28.511.56.56.78.85.35.55.10(3.9)(4.8)(6.2)(8.5)(11.5)3.9(8.1)(9)(10.4)(12.7)4.8(9.2)(10.1)6.2(11.7)(10.8)8.5(11.5)(13.4)11.5习题6.73/17/2023243654121438108.8965194.85图6－433/17/2023图6－44234567530318152091615188139151020223056.10如图6－44，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量习题6.10解答3/17/2023图6－4423456753031815209161518813915102022305【解】给出一个初始流，如下图所示(15)(15)(15)(15)(15)(15)(15)(20)(5)(5)(5)(0)(0)(0)(0)(0)习题6.10解答3/17/2023图6－4423456753031815209161518813915102022305第一轮标号：得到一条增广链，调整量等于5，如下图所示(15)(15)(15)(15)(15)(15)(15)(20)(5)(5)(5)(0)(0)(0)(0)(0)∞59157习题6.10解答3/17/2023图6－4423456753031815209161518813915102022305调整流量。第二轮标号：得到一条增广链，调整量等于2，如下图所示(15)(15)(20)(20)(20)(15)(15)(20)(5)(5)(5)(0)(5)(0)(0)(0)∞102082习题6.10解答3/17/2023图6－4423456753031815209161518813915102022305调整流量。第三轮标号：得到一条增广链，调整量为3，如下图所示(15)(15)(20)(22)(20)(15)(15)(20)(7)(5)(5)(0)(5)(0)(2)(2)∞818153810习题6.10解答3/17/2023图6－4423456753031815209161518813915102022305调整流量。第四轮标号：不存在增广链，最大流量等于45，如下图所示(15)(15)(20)(22)(20)(12)(15)(23)(10)(5)(8)(0)(5)(3)(5)(2)∞81515最小截集{(3,7),(4,7),(6,9),(8,10)，最小截量等于453510习题6.10解答3/17/2023A1(4,6)(5,4)(10,7)(7,7)(8,10)(8,5)(4,5)(15,6)(3,3)A2A3C2C1B2B1图6－456.11将3个天然气田A1、A2、A3的天然气输送到2个地区C1、C2，中途有2个加压站B1、B2，天然气管线如图6－45所示。输气管道单位时间的最大通过量cij及单位流量的费用dij标在弧上(cij,dij)。求(1)流量为22的最小费用流；（2）最小费用最大流。习题6.11解答3/17/2023A1(4,6)(5,4)(10,7)(7,7)(8,10)(8,5)(4,5)(15,6)(3,3)A2A3C2C1B2B1【解】1.虚拟一个发点和一个收点AC(4,0)(15,0)(8,0)(14,0)(18,0)T6.11－1习题6.11解答3/17/2023A16477105563A2A3C2C1B2B12.fij=0,最短路p1={A,A2,B1,C2,C}，L1=8AC00000T6.11－2习题6.11解答3/17/2023A1(4,6)(5,4)(10,7)(7,7)(8,10)(8,5)(4,5)(15,6)(3,3)A2A3C2C1B2B13.在最小费用链上调整流量,调整量等于3，红色的为弧的流量AC(4,0)(15,0)(8,0)(14,0)(18,0)(3)(3)(3)(3)T6.11－3习题6.11解答3/17/2023A1647710556－3A2A3C2C1B2B14.调整权系数，求最短路AC00000－5T6.11－4习题6.11解答3/17/2023A1(4,6)(5,4)(10,7)(7,7)(8,10)(8,5)(4,5)(15,6)(3,3)A2A3C2C1B2B15.在最小费用链上调整流量,调整量等于5AC(4,0)(15,0)(8,0)(14,0)(18,0)(3)(3)(8)(8)T6.11－5(5)(5)习题6.11解答3/17/2023A164771056－3A2A3C2C1B2B16.调整权系数，