第九章网络优化模型

第九章网络优化模型第1页，共70页，2023年，2月20日，星期三教学要求：掌握图论基础，掌握最短路问题，最大流问题和最小费用流问题等网络优化模型及其基本算法。会应用模型和方法解决一些管理中的基本问题第2页，共70页，2023年，2月20日，星期三目录图与网络树最短路问题最大流问题最小费用流问题第一节图与网络第3页，共70页，2023年，2月20日，星期三12341234一、图的概念及分类图是由作为研究对象的有限个集合和表达这些顶点之间关系的m条线的集合组成的,记顶点集合为V={v1,v2,……vn}，线集合为L={l1,l2,….lm}图则记为G=(V，L)，线又分为弧和边，顶点也称为结点弧是由一对有序的顶点组成，表示两个顶点之间可能运动的方向取消弧的方向就变成了边，边是只要任两点之间有连线，两个方向均可使用，弧可作为城市道路的单行道，边则是双行道第一节图与网络第4页，共70页，2023年，2月20日，星期三顶点、弧、有向图、无向图、链、道路、环、连通图、连通子图、次的基本概念1234123412345213次道路顶点无向图链有向图弧环连通图弧是由一对有序的顶点组成，表示了两个顶点之间可能运动的方向连通子图

由顶点集和弧组成的图称为有向图

由顶点集和边组成的图称为无向图

链有一序列弧，如果每一个弧与前一个弧恰有一个公共顶点，则称这一序列弧为一个链。

道路如果链中每一个弧的终点是下面一个弧的起点，则这个链称为一个道路。

环连接a点与b点的一条链，如果a与b是同一个点时，称此链为环。

连通图一个图中任意两点间至少有一个链相连，则称此图为连通图。

任何一个不连通图都可以分为若干个连通子图，每一个子图称为原图的一个分图。

次:以a点为顶点的边的条数称为顶点的次

第一节图与网络第5页，共70页，2023年，2月20日，星期三点或边带有某种数量指标的图叫网络图，简称网络。与点或边有关的某些数量指标，我们经常称之为权，权可以代表如距离、费用、容量等。左图可以看作：从发电厂（节点1）向某城市（节点6）输送电力，必须通过中转站（节点2，3，4，5）转送，边上数字代表两节点间的距离。电力公司希望选择合适的中转站，使从电厂到城市的传输路线最短。一个输油管道网。节点1表示管道的起点，节点6表示管道的终点，节点2到5表示中转站，旁边的数字表示该段管道能通过的最大输送量。应怎样安排输油线路，使从节点1到节点6的总输送量最大？一张城市分布图。现在要在各城市之间架设电话线，应如何架设，使各城市之间既能通话，又使总的架设路线最短？二、网络第一节图与网络第6页，共70页，2023年，2月20日，星期三一、树：连通且不含环的无向图

树的性质：任意两顶点之间必有一条且仅有一条链。去掉任一条边，则树成为不连通图。不相邻的两个顶点间添上一条边，恰好得到一个环。如果树有n个结点，则边的数目刚好为n-1第二节树第7页，共70页，2023年，2月20日，星期三部分图生成子图部分树如果V1V，E1E则称G1为G的部分图；设G=(V，E)和G1=(V1，E1)如果G1=(V1，E1)，G=(V，E)，并且V1V，,则称G1为G的生成子图；如果G=(V，E)的部分图G1=(V，E1)是树，则称G1为G的一个部分树。二、部分图、生成子图、部分树第二节树第8页，共70页，2023年，2月20日，星期三求连通图部分树的方法(1)破圈法：在G中任取一个圈，去掉圈中的任何一条边，对余下的图重复这一步，直到无圈为止，最后得到一棵部分树第二节树第9页，共70页，2023年，2月20日，星期三求连通图部分树的方法(2)避圈法：在G中任取一条边e1，找一条与e1不构成圈的边e2，然后再找一条与{e1,e2}不构成圈的边e3、、、直到无边可选为止V1V3V2V5V4V6e1e2e3e6e7e5e8e8e4第二节树第10页，共70页，2023年，2月20日，星期三1325464332322最小生成树不一定唯一三、最小生成树：设有一连通图G=(V，L)，对于每一条边e=(vi,vj),有一个权wij，一棵生成树所有树枝上权的总和，称为这个生成树的权，具有最小权的生成树称为最小生成树，简称最小树第二节树第11页，共70页，2023年，2月20日，星期三(1)最小生成树的求法破圈法:每一步任找一个圈，划去权值为最大的边，直到图中没圈为止，即得最小树V1V3V2V5V4V6651532447第二节树第12页，共70页，2023年，2月20日，星期三(2)最小生成树的求法避圈法:每一步从未选的边中，选一条权值最小的边，使已选出的边不构成圈直至不能进行为止，即得最小树V1V3V2V5V4V6651532447第二节树第13页，共70页，2023年，2月20日，星期三V1V4V2V5V7V864523854V3V64543637练习：用破圈法或避圈法求下图的最小生成树，并指出其权重和

第二节树第14页，共70页，2023年，2月20日，星期三避圈法：V1V4V2V5V7V864523854V3V64543637最小生成树如上图红线所示，最小权重为：4+3+3+3+4+5+2=24第二节树第15页，共70页，2023年，2月20日，星期三破圈法：V1V4V2V5V7V864523854V3V64543637最小生成树如上图所示，最小权重为：4+3+3+3+4+5+2=24第二节树第16页，共70页，2023年，2月20日，星期三练习：下图是6个城市的交通图，为将部分道路改造成高速公路，使各个城市均能通达，又要使高速公路的总长度最小，应如何做使总长度最小,总长度是多少?第二节树第17页，共70页，2023年，2月20日，星期三避圈法求解：第二节树最优改造路线如上图红线所示，最短路径为：1400第18页，共70页，2023年，2月20日，星期三求下面两个连通图的最小生成树：第二节树第19页，共70页，2023年，2月20日，星期三第二节树第20页，共70页，2023年，2月20日，星期三某地有10个村庄，它们之间的交通道路如下图所示，图中边旁权为道路长度(单位：百米)，现在要沿道架设电线，实现村村通电话工程，问应如何架设电线才能使总长度最短？第二节树第21页，共70页，2023年，2月20日，星期三解：本题实质是最小树问题，利用避圈法可求得最短路线，如下图粗线所示：最优架设路线如上图粗线所示，架设电线最短长度为18(百米)。第二节树第22页，共70页，2023年，2月20日，星期三某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如图所示，图中vi表示7个学院办公室，图中的边为可能联网的途径，边上的所赋的权数为这条路线的长度，单位为百米，请设计一个网络能联系7个学院办公室，并使总的线路长度为最短V1V6V5104873V2V7335V4V3124第23页，共70页，2023年，2月20日，星期三V1V6V5104873V2V7335V4V312破圈法求解：4最短路径如上图所示，最短为：19百米第24页，共70页，2023年，2月20日，星期三V1V6V5104873V2V7335V4V312避圈法求解：最短路径如上图所示，最短为：19百米4第25页，共70页，2023年，2月20日，星期三图与网络树最短路问题最大流问题最小费用流问题第三节最短路问题第26页，共70页，2023年，2月20日，星期三特点：从一特殊的节点出发，找出从该节点到网络中任何其它节点的最短路径问题某人买了一辆价值1200美元的新车，一辆车每年的维护费用依赖于年初时的车龄，具体费用见下表。为了避免旧车的高维护费用，他决定卖掉旧车买新车。旧车的价格依赖于交易时的车龄，见下表。为计算简单起见，假设任何时间新车的价格不变均为1200美元。他希望在今后5年内的净费用最小（即：净费用=购买价+维护价-售出价）。

车龄每年的维护费用交易费用012345200040005000900012000700060002000100002112第三节最短路问题第27页，共70页，2023年，2月20日，星期三结点i表示第i年的年初，当i<j时，弧(i,j)表示第i年年初购买一辆新车并一直用到第j年年初。弧的长度cij表示：如果第i年年初购买一辆新车并这辆车在第j年年初卖掉更换一辆新新，从第i年年初到第j年年初期间总的净费用，于是有cij=(i,i+1,..j-1年的维护费用）＋（第i年年初购买新车的费用）－（第j年年初该车的交易费用）1234567777712121221313144122121第三节最短路问题第28页，共70页，2023年，2月20日，星期三车龄每年的维护费用交易费用01234520004000500090001200070006000200010000c12=2+12-7=7c13=2+4+12-6=12c14=2+4+5+12-2=21c15=2+4+5+9+12-1=31c16=2+4+5+9+12+12-0=44c23=2+12-7=7c24=2+4+12-6=12c25=2+4+5+12-2=21c26=2+4+5+9+12-1=31c34=2+12-7=7c35=2+4+12-6=12c36=3+4+5+12-2=21c45=2+12-7=7c46=2+4+12-6=12c56=2+12-7=71234567777712121221313144122121第三节最短路问题第29页，共70页，2023年，2月20日，星期三Dijkstra最短路算法：假设每个弧的权是非负的，即wij≥0，给每个支点vi记一个数(称标号)，标号分临时性标号T和永久性标号P，永久性标号表示从v1到该点vi的最短路权，得到永久性标号的不再改变标号，临时性标号表示从开始点v1到该点vi的最短路权的上界，算法每一步都把某一点的T标号改为P标号，开始时给初始支点v1标号记为0，即P(v1)=0，其他支点(记为临时性标号)的标号记为+∞，即T(vi)=+∞,若vi点是刚得到P标号的点，考虑L中与vi点相连的弧(vi,vj)且vj是T标号，对vj的标号进行如下更改：T(vj)=min{T(vj),P(vi)+Wij}比较所有具有T标号的点，把最小者改为P标号，当存在两个以上最小者时，可以同时改为P标号，直到全部点均改为P标号为止第三节最短路问题第30页，共70页，2023年，2月20日，星期三

例：从发电厂（记为节点1）向某城市（记为节点6）输送电，必须通过中转站（记为节点2，3，4，5）转送。图给出了两节点间的距离。电力公司希望选择合适的中转站，使从电厂到城市的传输路线最短。即从节点1到节点6的最短路径。这就是一个最短路问题。第三节最短路问题第31页，共70页，2023年，2月20日，星期三1325464332322第0步：P(1)=0,T(i)=+∞；第1步：与1相连的标号为2,3，均是T标号，修改2,3的标号，T(2)=min{T(2),P(1)+w12}=4,T(3)=3；在所有的T标号中，3的标号最小，改3的标号为P(3)=3；第2步：修改与3相连的T标号；在所有剩下的T标号中，2的标号最小，改为P(2)=4；第3步：修改与2相连的T标号；在所有剩下的T标号中，5的标号最小，改为P(5)=6；第4步：修改与5相连的T标号；在所有剩下的T标号中，4的标号最小，改为P(4)=7；第5步：修改与4相连的T标号；只剩下节点6是T标号，修改6的标号，P(6)=8。从节点6开始回退，得到最短路。P(1)=0T(3)=+∞T(2)=+∞T(3)=3T(5)=+∞P(3)=3T(5)=6T(2)=4T(4)=+∞T(6)=+∞P(2)=4T(4)=7P(5)=6T(6)=8P(4)=7P(6)=8P(6)=8P(5)=6P(3)=3P(1)=0第三节最短路问题第32页，共70页，2023年，2月20日，星期三P(1)=0T(2)=+∞T(4)=+∞T(3)=+∞T(5)=+∞T(6)=+∞T(7)=+∞第2步：与4相连的标号为2,3,5,6，均是T标号，修改2,3,5,6的标号，T(2)=min{T(2),P(4)+w42}=4,T(3)=min{T(3),P(4)+w43}=3T(5)=min{T(5),P(4)+w45}=7T(6)=min{T(6),P(4)+w46}=9在所有的T标号中，3的标号最小，改3的标号为P(3)=3；T(2)=4T(3)=3T(4)=2P(4)=2第1步：与1相连的标号为2,3，4，均是T标号，修改2,3,4的标号，T(2)=min{T(2),P(1)+w12}=4,T(3)=min{T(3),P(1)+w13}=3T(4)=min{T(4),P(1)+w14}=2在所有的T标号中，4的标号最小，改4的标号为P(4)=2；T(2)=4T(3)=3T(5)=7T(6)=9第3步：与3相连的是T标号,为5，修改5的标号，T(5)=min{T(5),P(3)+w35}=6在所有的T标号中，2的标号最小，改2的标号为P(2)=4；P(3)=3T(5)=6第4步：与2相连的是T标号,为6，修改6的标号，T(6)=min{T(6),P(4)+w46}=9在所有的T标号中，5的标号最小，改5的标号为P(5)=6；P(2)=4P(5)=6第5步：与5相连的是T标号,为6,7，修改6,7的标号，T(6)=min{T(6),P(5)+w56}=8T(7)=min{T(7),P(5)+w56}=12在所有的T标号中，6的标号最小，改6的标号为P(6)=8；1325464352326722572T(6)=8T(7)=12第6步：与6相连的是T标号,为7，修改7的标号，T(7)=min{T(7),P(6)+w67}=10在所有的T标号中，7的标号最小，改7的标号为P(7)=10；P(6)=8T(7)=10P(7)=10最短路径为P(7)-P(6)-P(5)-P(3)-P(1)最短路长度为10；T(6)=9求1到7的最短路第三节最短路问题第33页，共70页，2023年，2月20日，星期三1325465462352572求1到6的最短路最短路径为1－3－5－6长度为9第三节最短路问题第34页，共70页，2023年，2月20日，星期三用Excel求解最短路算法净流量=流出该节点的流量—流入该节点的流量

中间节点的平衡值为0，起点为1，终点为-1。各个点的净流量等于平衡值最短路平衡流第三节最短路问题第35页，共70页，2023年，2月20日，星期三P(6)=8P(5)=6P(3)=3P(1)=0第三节最短路问题第36页，共70页，2023年，2月20日，星期三

城市出租车公司在纽约市为出租车司机已经确定了10个搭乘车站。为了减少运行时间，提高服务质量以及最大化利用公司的车队，管理方希望出租车司机尽可能地选择最短路线。使用下面公路与街道的网络图，请说明司机从车站1到车站10应选择什么样的路线。运行时间如图所示。第三节最短路问题第37页，共70页，2023年，2月20日，星期三这里我们仅通过Excel电子表格求解，在表格中，我们并不是把每一对连接的点都输入进去，比如，我们输入了从V7到V10，很明显不需要再输入从V7到V8，从V8到V10这两对点对，因为他们加起来的距离明显要比前者长。

第三节最短路问题第38页，共70页，2023年，2月20日，星期三最优路线为：1－５－４－６－７－10，最短距离是25第三节最短路问题第39页，共70页，2023年，2月20日，星期三图与网络树最短路问题最大流问题最小费用流问题第四节最大流问题第40页，共70页，2023年，2月20日，星期三最大流量问题：给了一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出发点到收点的最大流量第四节最大流问题第41页，共70页，2023年，2月20日，星期三V1V4V2V5V76634252V3V62321例：某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如图所示，由于管理的直径的变化，它的各段管道(vi,vj)的流量（容量）cij也是不一样的，cij的单位为万加仑/小时，如果使用这个网络系统从采地v1向销地v7运送石油，问每小时能运行多少加仑石油？第四节最大流问题第42页，共70页，2023年，2月20日，星期三设弧(vi,vj)上流量为fij，网络上总的流量为F，则有目标函数：maxF=f12+f14约束条件：f12=f23+f14f14=f43+f46+f47f23+f43=f35+f36f25+f35=f57f36+f46=f67f57+f67+f47=f12+f14fij≤cijfij≥0i=1,2,,,6j=2,3,,,,7守恒条件小于容量的可行流可行流中一组流量最大的称为最大流第四节最大流问题第43页，共70页，2023年，2月20日，星期三最大流问题网络图论的解法1、对网络上弧的容量的表示作改进，对条一条弧(vi,vj)的容量用一对数据cij,0标在弧(vi,vj)上，以cij靠近vi点，0靠近vj点，表示从vi到vj容许通过的容量为cij，而从vj到vi容许通过的容量为0，这样可能省云弧的方向vivjcijvivjcijc0对于存在两条相反的弧(vi,vj)和(vj,vi)，也可以用一条过和一对数组cij，cji来表示它们的容量vivjcijvivjcijcji第四节最大流问题第44页，共70页，2023年，2月20日，星期三V1V4V2V5V76634252V3V6232100000000000第四节最大流问题第45页，共70页，2023年，2月20日，星期三求最大流的基本算法（1）找出一条从发点到收点的路，在这条路上的每条弧顺流方向的容量都大于零，如果不存在这样的路，则已求得最大流（2）找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf(3)在这条路上，减少每条弧的顺流容量pf，同时增加这些弧的逆流容量pf,返回步骤（1）由于所选路不一样，计算过程也不一样，但最终结果是一样的，为了使算法快捷有效，我们一般在步骤（1）中尽量选择包含弧数最少的路第四节最大流问题第46页，共70页，2023年，2月20日，星期三第一次迭代选择路为v1-v4-v7，弧（v4,v7)的顺流容量为2，决定pf=2，改进网络流量V1V4V2V5V76634252V3V62321000000000000422F=2第四节最大流问题第47页，共70页，2023年，2月20日，星期三第二次迭代选择路为v1-v2-v5－v7，弧（v2,v5)的顺流容量c35=3，决定pf=3，改进网络流量V1V4V2V5V763452V3V623210000000000422F=5032333第四节最大流问题第48页，共70页，2023年，2月20日，星期三第三次迭代选择路为v1-v4-v6－v7，弧（v4,v6)的顺流容量c46=1，决定pf=1，改进网络流量V1V4V2V5V742V3V623210000000422F=6032333303113第四节最大流问题第49页，共70页，2023年，2月20日，星期三第四次迭代选择路为v1-v4-v3－v6－v7，弧（v3,v6)的顺流容量c36=2，决定pf=2，改进网络流量V1V4V2V5V72V3V6232000002F=803233330311311015223第四节最大流问题第50页，共70页，2023年，2月20日，星期三第五次迭代选择路为v1-v2-v3－v5－v7，弧（v2,v3)的顺流容量c23=2，决定pf=2，改进网络流量V1V4V2V5V72V3V620002F=10032333011101522310005225第四节最大流问题第51页，共70页，2023年，2月20日，星期三V1V4V2V5V7V3V602F=1003011101522310005225网络图中，逆流就是流过每条路径的流量第四节最大流问题第52页，共70页，2023年，2月20日，星期三24531142010519152730流量容量

容量网络：标有弧容量的网络。网络流的两个条件：每个弧的流量不能超过该弧的最大通过能力，即容量；中间支点的流量为零。可行流：中间点的流量为零。而发点和收点的流量必须相等。156104610150可行流第四节最大流问题第53页，共70页，2023年，2月20日，星期三增广链13425201051419152730156104610150饱和弧非饱和弧零弧增广链增广链:

设f是一个可行流，C是从发点Vs到收点Vt的一条链，若C满足以下条件，则称C为一条增广链：(1)在弧(vi,vj)∈C+上，0≤fij≤cij，即C+(弧的方向与链的方向一致

)中每一条弧是非饱和弧(2)在弧(vi,vj)∈C+上，0≤fij≤cij，即C-(弧的方向与链的方向相反

)中每一条弧是非零流弧

C＋中每一条弧是非饱和弧;C－中每一条弧是非零流弧。

第四节最大流问题第54页，共70页，2023年，2月20日，星期三21st28811任给一个包含收点但不包含发点的支点集V*，则称i(弧起点)不属于V*，j(弧终点)属于V*的弧(i,j)的全体为割集。割集的容量是割集中所有弧的容量的总和。如果将割集从网络中移去，则就不可能有从起点到终点的路径。一个网络可能有许多割集。任何从发点到收点的可行流小于等于任何割集的容量。

V*割集任何割集的容量是从起点到终点的最大流的上界。如果能找到一个可行流和一个割集使得割集从起点到终点的容量等于可行流的流量，则该可行流就是一个最大流。最大流---最小割定理

V*={1,t}割集是{(s,1)，(2,t)}

支点集V*={1,2,t},割集？{(s,1)，(s,2)}

第四节最大流问题第55页，共70页，2023年，2月20日，星期三求最大流的标号算法从一个可行流f={fij}出发，（若网络中没有给定f，则可以设f是零流）需要经过标号过程与调整过程。1．标号过程在这个过程中，网络中的点或是标号点或是未标号点。每个标号点的标号包含两部分：第一标号表示它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量用的。标号过程开始时，总是先给发点Vs标上(0,+∞)。其余各点标号的规则是：设vi是已标号的点，检查与Vj点关联的另一顶点未标号的弧：（1）如果在弧(vi,vj)上（即前向弧），fij<cij，则给vj标号(vi,l(vj))，其中l(vj)=min{l(vi),cij-fij}。如果fij=cij，则vj不标号。（2）如果在弧(vj,vi)上（即后向弧），fji>0，则给vj标号(-vi,l(vj))，其中l(vj)=min{l(vi),fji}，负号说明经后向弧到。如果fij=0，则vi不标号。重复上述步骤，直到被vj标上号，表明得到一条从vi到vj的增广链C，转入调整过程。第四节最大流问题第56页，共70页，2023年，2月20日，星期三求最大流的标号算法2．调整过程由收点标号算出的作为调整量（即）。对增广链各弧的调整如下：

增广链以外各弧流量不变。去掉所有标号，对新的可行流，重新进入标号过程。直到标号过程中断。当前流就是最大流。第四节最大流问题第57页，共70页，2023年，2月20日，星期三vsv2v1v3vt32223(0,+∞)

找到初始可行流。给网络中的各个点标号：总是先给发点vs标上(0,+∞)。其余各点标号的规则是：设vi是已标号的点，检查与点vi关联的另一顶点未标号的弧：（1）如果在弧(vi,vj)上（即前向弧），fij<cij，则给vj标号(vi,l(vj))，其中l(vj)=min{l(vi),cij-fij}。如果fij=cij，则vj不标号。（2）如果在弧(vj,vi)上（即后向弧），fij>0，则给vj标号(-vi,l(vj))，其中l(vj)=min{l(vi),fji}，负号说明经后向弧到vi。如果fji=0，则vj不标号。调整：按照第一标号找到增广链，按第二标号的最小值调整可行流，得到新的可行流。重复标号过程，直到没有增广链，即得到最大流。2112114(vs,2)(v3,1)(-v2,1)(v1,1)222022如下图所示，弧上数字表示该弧的容量，求该网络的最大流。增广链以外各弧流量不变

第四节最大流问题第58页，共70页，2023年，2月20日，星期三vsv2v1v3vt32223(0,+∞)重复标号过程。给网络中的各个点标号：先给发点vs标上(0,+∞)。检查vs给v2标上(vs,1)，检查v2,在弧(v2,vt)上,f2t=c2t=2,不满足标号条件，在弧(v1