第四章网络计划

第四章网络计划第1页，共76页，2023年，2月20日，星期三最小生成树(TheMinimumSpanningTree)

树(无圈的连通图)是图论中结构最简单但十分重要的图.有着广泛的应用.如铁路专用线,管理组织机构,学科分类和一般决策过程往往都可以用树来表示.树的基本概念:如果无向图是连通的，且不包含圈，则该图为树（Tree）

.第2页，共76页，2023年，2月20日，星期三最小生成树(TheMinimumSpanningTree)定义若连通图G的生成子图是一棵树,则称该树为G的生成树(Spanningtree

)．最小生成树:连通图G的每条边上有非负权W(e)．一棵生成树所有树枝上权的总和，称为这可棵生成树的权．具有最小权的生成树称为最小生成树．第3页，共76页，2023年，2月20日，星期三最小生成树的应用

许多网络问题都可归结为最小生成树问题．如设计长度最小的公路网把若干城市相联；设计用料最省的电话线网把有关单位联系起来等．例4-2-1

电信网络的设计某高科技公司准备铺设先进的光纤网络.为其核心部门提供高速通信.部门位置分布,线路分布及每条线路的铺设成本如下图.请设计一个网络方案,各部门互通且网络总成本最低.第4页，共76页，2023年，2月20日，星期三最小生成树BAECDFG227545414317

实际上是要确定需要铺设哪些光缆使得提供给每两个部门之间的高速通信的总成本最低.这是一个最小生成树问题.第5页，共76页，2023年，2月20日，星期三Kruskal算法

每步从未选的边中选取边e，使它与已选边不构成圈，且e是未选边中的最小权边，直到选够n-1条边止．这个算法称为避圈法.BAECDFG227545414317最低成本=1+1+2+2+3+5=14第6页，共76页，2023年，2月20日，星期三最小生成树问题的典型应用电信网络的设计低负荷运输网络的设计,使得网络中提供链接的部分(如公路,铁路等)的总成本最小.高压输电线路的设计电器设备线路网络(如数字计算机系统)的设计,使得线路总长度最短.连接多个场所的管道网络设计.第7页，共76页，2023年，2月20日，星期三最短路问题(TheShortestPathProblem)

最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型，如设备更新、管道铺设、线路安排等等。最短路问题的一般描述：设G=(V,E)为连通图，且任意一边(vi,vj)的权为lij,求一条通路，使该通路的权L()=最小。第8页，共76页，2023年，2月20日，星期三Dijkstra算法

目前被认为是求无负权网络最短路问题的最好方法。算法的基本思路：若序列{vs,v1,…,vn-1,vn}是从vs到vn的最短路，则序列{vs,v1,…,vn-1}必为从vs到vn-1的最短路。第9页，共76页，2023年，2月20日，星期三整数规划模型假设图有n个顶点，现需要从顶点1到顶点n的最短路。设决策变量为xij,当xij=1时，说明边（i,j）在最短路径上，否则xij=0.其数学表达式为：第10页，共76页，2023年，2月20日，星期三

例4-2-2设备更新问题某工厂使用一台设备,每年年初工厂都要作出决定,是继续使用旧的,要付维修费;若购买一台新设备,要付购买费.试制定一个5年的更新计划,使总的支出最少.该设备各年的购买费及不同机器役龄时的残值与维修费见下表.最短路问题的应用第11页，共76页，2023年，2月20日，星期三项目第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值43210最短路问题的应用第12页，共76页，2023年，2月20日，星期三

11+(5+6+8)-2=28第一年初购买费11，三年的维修费用5，6，8，减去3年役龄机器的残值2。v1v2v3v4v5v6

用点vi表示第i年年初购进一台设备,边(vi,vj)上的数字表示第i年初购进设备用到第j年初.边上的权为使用期间的总费用.5年的更新计划最终转化为最短路问题.第13页，共76页，2023年，2月20日，星期三最短路问题的求解v1v2v3v4v5v61.决策变量xij,若经过经过边vi-vj,则xij=1,否则为0.即定义xij为一个0-1变量.2.目标函数minZ=.cij边vi-vj的权值.第14页，共76页，2023年，2月20日，星期三最短路问题的求解v1v2v3v4v5v63.约束条件起点:

有出度无入度,始于该点必有出-入

=1.中间点:

有入有出,若过该点必有出-入

=0.终点:

有入无出,终于该点必有出-入

=-1.10-1第15页，共76页，2023年，2月20日，星期三最短路问题的LINGO求解Model:Sets:Nodes/v1,v2,v3,v4,v5,v6/;OnRoute(Nodes,Nodes)/v1,v2v1,v3v1,v4v1,v5v1,v6v2,v3v2,v4v2,v5v2,v6v3,v4v3,v5v3,v6v4,v5v4,v6v5,v6/:Cost,x;EndsetsData:Cost=121928405913202941142130152215;EndDataN=@size(Nodes);Min=@sum(OnRoute:Cost*x);@for(Nodes(i)|i#ne#1#and#i#ne#N:@sum(OnRoute(i,j):x(i,j))=@sum(OnRoute(j,i):x(j,i)));@sum(OnRoute(i,j)|i#eq#1:x(i,j))=1;@sum(OnRoute(i,j)|j#eq#N:x(i,j))=1;@for(OnRoute(i,j):@bin(x(i,j)));End第16页，共76页，2023年，2月20日，星期三最短路问题的LINGO求解第17页，共76页，2023年，2月20日，星期三

最大流问题(MaximalFlowProblem)VtVsV1V2V3V421434242233

将左图看作输油管道，Vs,Vt

为起始点和终止点，中间各点为中转站，每条边的权代表该条管道的最大输油能力，问如何安排各条管道的输油量，才能使从Vs到Vt的总输油量最大？第18页，共76页，2023年，2月20日，星期三

最大流问题(MaximalFlowProblem)VtVsV1V2V3V421434242233

一般来说，管道的容量有限，实际流量不一定等于容量，问题讨论如何充分地利用装置的能力，以取得最大的流量，这类寻优问题称为最大流问题。第19页，共76页，2023年，2月20日，星期三容量网络

VtVsV1V2V3V421434242233任意一条边上的权Cij0，称为容量.入度为0的点为发点（源source）出度为0点为收点（汇sink）有向连通图G=<V,E,C>称为容量网络。中间点(转运点)第20页，共76页，2023年，2月20日，星期三可行流任意一条边（Vi,Vj）上的流量为fij,集合f={fij}为网络G上的一个流。VtV4VsV1V2V321434242233f12fs1f2tW一个流f={fij},当fij=Cij，则称流f

对边(Vi,Vj)是饱和的，否则称f对(Vi,Vj)不饱和。第21页，共76页，2023年，2月20日，星期三可行流

满足下列条件的流f为可行流：(1)容量限制条件：0fijCijV4VtVsV1V2V321434242233f12fs1f2tW第22页，共76页，2023年，2月20日，星期三可行流

(2)平衡条件：对于中间点vi,有收,发点有

W为网络的总流量，从源发出的物资的输入量等于汇的输入量。最大流问题就是在容量网络中，寻找流量最大的可行流。

V4VtVsV1V2V321434242233f12fs1f2tW第23页，共76页，2023年，2月20日，星期三最小割集边割集

割集(S,S’)中所有起点在S,终点在S’的边的容量之和，称为（S,S’)的割集容量，记作C(S,S’).

如上图C(S,S’)=4+2+3=9,C(T,T’)=4+3+4=11.容量网络G的割集有多个，容量最小者为G的最小割.VtVsV1V2V3V421434242233SVtVsV1V2V3V421434242233S’TT’第24页，共76页，2023年，2月20日，星期三最大流-最小割定理由割集的定义不难看出，在容量网络中割集是由Vs到Vt的必经之路，无论拿掉哪个割集，Vs到Vt便不再相通，所以任何一个可行流的流量不会超过任一割集的容量，也即网络的最大流与最小割满足以下定理。VtVsV1V2V3V421434242233TT’VtVsV1V2V3V421434242233TT’第25页，共76页，2023年，2月20日，星期三最大流-最小割定理定理设f为网络G=<V,E,C>的任一可行流，流量为W，（S,S’）是分离Vs,Vt的任一割集，则有WC(S,S’).最大流-最小割定理

任一个网络G中，从vs到vt的最大流的流量等于分离vs,vt的最小割的容量。第26页，共76页，2023年，2月20日，星期三最大流问题(MaximalFlowProblem)最小割的意义，网络从发点到收点的各通路中，由容量决定其通过的能力，最小割则是这些路中的咽喉部分（瓶颈），其容量最小，它决定了整个网络的最大通过能力。要提高整个网络的运输能力，必须首先改造这个咽喉部分的通过能力。第27页，共76页，2023年，2月20日，星期三线性规划求解最大流问题

最大流问题的核心是对可行流进行最大寻优。由可行流的定义可知，其容量限制条件及平衡条件为其约束条件，总流量求最大为目标函数，因此可列出对应的线性规划模型。vsvtv1v2v3v4v5v6(5,5)(4,2)(3,2)(5,2)(3,3)(3,0)(4,2)(3,3)(5,4)(2,2)(2,2)W第28页，共76页，2023年，2月20日，星期三线性规划求解最大流问题(LINGO)MODEL:SETS:NODES/1..8/;!边集ARCS,CAP为容量,FLOW为流量;ARCS(NODES,NODES)/1,21,31,42,52,63,63,74,75,8,6,87,88,1/:CAP,FLOW;ENDSETS!网络的总流量W=FLOW(8,1);MAX=FLOW(8,1);!容量限制约束;@FOR(ARCS(I,J):FLOW(I,J)<CAP(I,J));!节点平衡条件;@FOR(NODES(I):@SUM(ARCS(J,I):FLOW(J,I))=@SUM(ARCS(I,J):FLOW(I,J)));DATA:!W=CAP(8,1)设一个大数1000，表示容量无限;CAP=5,4,3,5,3,3,2,2,4,3,5,1000;ENDDATAEND第29页，共76页，2023年，2月20日，星期三最大流问题的应用例4-2-3某河流中有几个岛屿，将两岸及岛屿用点表示，相互间有桥梁联系以边表示。如图，A与F表示两岸，B,C,D,E为岛屿，边上的数字为之间的桥梁数。在一次敌对的军事行动中，问至少应炸断几座桥及哪几座桥梁，才能完全切断两岸的交通联系？第30页，共76页，2023年，2月20日，星期三最大流问题的应用ADFECB221213111分析:将边上的数字看成是容量，该问题为求容量网络的最小割问题。由最小割和最大流的关系，找到最大流即能够明确最小割。

第31页，共76页，2023年，2月20日，星期三最大流问题的应用结果:可以采用求最大量流的方法计算可得到的最大流为3，分析得出其最小割为(A,E),(D,F),(D,E)

ADFECB221213111第32页，共76页，2023年，2月20日，星期三最大流问题的典型应用通过配送网络的流量最大化通过从供应商到处理设施的公司供应网络的流量最大化通过管道运输系统的油的流量最大化通过交通网络的车辆的流量最大化…第33页，共76页，2023年，2月20日，星期三最小费用流问题(TheMinimumCostFlowProblem)最小费用流问题的一般提法：已知容量网络G=(V,E,C),每条边(vi,vj)除了已给出容量cij外，还给出了单位流量的费用dij（0），记G=(V,E,C,D).

求G的一个可行流f={fij},使得流量W(f)=W,且总费用最小，即在流量限制下的成本费用最小。特别地，当要求f为最大流时，问题即为最小费用最大流问题。第34页，共76页，2023年，2月20日，星期三线性规划解最小费用流问题流量约束，可行流f

的流量为W.第35页，共76页，2023年，2月20日，星期三线性规划解最小费用流问题v1v2v3v4v5(10,4)(8,1)(10,3)(5,2)(2,6)(7,1)(4,2)(1000,0)(CAP,COST)第36页，共76页，2023年，2月20日，星期三线性规划解最小费用流问题最优解v1v2v3v4v5(10,4)(8,1)(10,3)(5,2)(2,6)(7,1)(4,2)(1000,0)28573310第37页，共76页，2023年，2月20日，星期三最小费用流的典型应用应用类型供应商转运点需求点配送网络的运作货源中间存储设施客户废弃物处理废弃物源处理设施废弃物掩埋点供应网络的运作供应商中间仓库加工设备工厂协调产品组合工厂某特定的产品生产某特定产品市场现金流管理某特定时间现金来源短期投资期权特定时间对现金的需求第38页，共76页，2023年，2月20日，星期三运输问题(TransportationProblem)问题的一般描述：某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？第39页，共76页，2023年，2月20日，星期三产销平衡第40页，共76页，2023年，2月20日，星期三产销平衡第41页，共76页，2023年，2月20日，星期三产销平衡的数学模型其中cij表示从i到j的单位运费，决策变量xij为从i到j的运量。第42页，共76页，2023年，2月20日，星期三产销不平衡问题的数学模型供大于求供小于求第43页，共76页，2023年，2月20日，星期三转运问题TransshipmentProblem

例4-2-4可转运问题厂商A和厂商B为供货厂商，商店A和商店B为可转运商店，其中商店C和商店D为单纯需求商店。运费和转运运费（元/件）如下表。问题：如何发送商品可以使总运费最少？

第44页，共76页，2023年，2月20日，星期三转运问题TransshipmentProblem

第45页，共76页，2023年，2月20日，星期三转运问题TransshipmentProblem分析：店A和店B作为转运商店，应能够转运所有供货量，即150+200=350。因此对于点店A和店B的需求分别为50+350和80+350.而供货量为350。于是建立下列平衡表格。依据该表格建立运输问题的线性规划模型。见..\案例\可转运问题.xls第46页，共76页，2023年，2月20日，星期三转运问题TransshipmentProblem

第47页，共76页，2023年，2月20日，星期三转运问题TransshipmentProblem

第48页，共76页，2023年，2月20日，星期三转运问题TransshipmentProblem

可转运问题计算的关键可转运的商店自己到自己的运费率等于0；可转运商店的供给在供给的基础上加上一个足够大的数量M（例中为350）；在可转运商店的需求基础上也加上该足够大的数量M，加上的数量与供给加上的数量保持一致。

第49页，共76页，2023年，2月20日，星期三任意可转运问题如果在转运点处是有费用的，比方说装卸费用和临时存储费用，那么我们不能利用在同一转运点处“自己到自己”的费用为0来简化处理。这时，需要进行一些技术性处理，以引入“转运点费用”因素。第50页，共76页，2023年，2月20日，星期三任意转运问题的扩展表运费率供1……供m求1……求n供给供1c1a1………………供mcmam求1cm+10…………0求ncm+n0需求000bm+1……bm+nci为转运点的转运费用第51页，共76页，2023年，2月20日，星期三任意转运问题产出点和销售点都可以转运。xij

表示i

到j

货物数量，ti

表示流出的货物数量，tj

表示流入的货物数量，cij表示运费率，ci表示转运点费用率。目标函数为：第52页，共76页，2023年，2月20日，星期三约束条件(1)产地i的供量，i＝1,…,m，净产出量为ai，转运量为ti，满足以下条件：销地i

的转运量，i＝m+1,…,m+n，转运输出为ti，满足以下条件：第53页，共76页，2023年，2月20日，星期三约束条件(2)销地j的需求，j＝m+1,…,m+n，净输入量为bj，转运量为tj，满足以下条件：产地j的转运量，j＝1,…,m，转运输入量为tj，满足：第54页，共76页，2023年，2月20日，星期三可转运点的数学处理形式假定为产销平衡运输问题，即假设为了便于处理，对上述转运问题的线性规划模型进行以下数学变换。第55页，共76页，2023年，2月20日，星期三可转运点的数学处理形式产地i的供量，i＝1,…,m，满足：令改写为等式两边同加上（Q-ti）第56页，共76页，2023年，2月20日，星期三销地i的转出量，i＝m+1,…,m+n，满足：其中改写为第57页，共76页，2023年，2月20日，星期三产地j的转入量，j＝1,…,m，满足：其中改写为第58页，共76页，2023年，2月20日，星期三销地j的需求，j＝m+1,…,m+n，，满足：其中表示点

j到点

j自己的数量。改写为第59页，共76页，2023年，2月20日，星期三处理后的任意转运问题的扩展表运量供1……供m求1……求n供给供1Q-t1a1+Q………………供mQ-tmam+Q求1Q-tm+1Q……………求nQ-tm+nQ需求Q…Qbm+1+Q……bm+n+Q第60页，共76页，2023年，2月20日，星期三目标函数改写为满足：略去常数项后：原：第61页，共76页，2023年，2月20日，星期三目标函数改写为特别注意：与运费率cii对应的符号取负值！满足：第62页，共76页，2023年，2月20日，星期三处理后的任意转运问题的运费表运费率供1……供m求1……求n供给供1-c1a1+Q………………供m-cmam+Q求1-cm+1Q……………求n-cm+nQ需求Q…Qbm+1+Q……bm+n+Q第63页，共76页，2023年，2月20日，星期三注意Q的取值可以随意，不过，要保证最大可能的转运量得以通过，同时又保证tj

为正。目标函数中舍弃常数项后，计算出的结果不是实际最优解，而是实际最优解与常数项的差额。实际最优解常数项计算出的结果第64页，共76页，2023年，2月20日，星期三例4-2-5任意可转运问题:下图为一个运输系统,包括二个产地1,2,二个销地4,5及一个中间转运站3,各产地的产量及销量在箭头上标明,节点连线表示运输的路线,运输成本单价见线上数字.转运费在节点上标明.试确定最优运输方案.12345103040205322564541335第65页，共76页，2023年，2月20日，星期三运费率表格运费率产地1产地2转运3销地4销地5发送量产地1－4532MQ+10产地25－12M4Q+40转运332－355Q销地42M5－36Q销地5M456－5Q接收量QQQQ+30Q+20说明：1.M表示一个足够大的正数,运费无限大表明二者间无路径可达.2.总发送量=总接收量=Q=50第66页，共76页，2023年，2月20日，星期三EXCEL建模求解..\案例\任意转运问题.xlsSUMPRODUCT(B10:F14,B17:F21)+Q*SUM(B7:F7)第67页，共76页，2023年，2月20日，星期三结果分析运量产地1产地2转运3销地4销地5发送量产地1501060产地250202090转运3302050销地45050销地55050接收量5050508070Q-t1第68页，共76页，2023年，2月20日，星期三实际结果运量产地1产地2转运3销地4销地5发送量产地101010产地20202040转运320200销地400销地500接收量0003020

由产地1运10单位到销地4；由产地2运20单位到销地5；由由产地2运20单位到转运3，再转运至销地4。转运量第69页，共76页，2023年，2月20日，星期三实际结果运量产地1产地2转运3销地4销地5发送量产地