2022数学建模竞赛培训网络优化

网络(Network)：数学模型、数学结构----图优化(Optimization):从若干可能的方案中寻求某种意义下的最优方案与图论有联系，也有区别（侧重点不同）网络优化就是研究与（赋权）图有关的最优化问题图论：图的性质

网络优化：与（赋权）图有关的优化问题组合数学组合优化网络优化

简介图的基本概念图G=(V，A)，其中顶点集V= 弧集A=弧例：公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市.假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？

网络优化问题的例子

131325463421246赋权图“直接方式”：总经理直接传达；“接力方式”：总经理只给某些部门经理打电话，而让这些得到信息的部门经理打电话将信息进一步传达给其他某些部门经理，依此类推，最后将信息传达到所有部门经理.如何决定传达信息的途径使得信息快速准确？信息传播是有向的，有一个“根”。信息传播途径（忽略方向时）是一棵树。以上结构称为树形图，上面这样一类问题称为最小树形图问题.例：信息传播最小树形图例最短路问题

一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地.从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路.网络优化问题的例子

AF566744513BEDC甲地乙地实例例：工程项目统筹问题

大型复杂工程项目往往被分成许多子项目,子项目之间有一定的先后顺序(偏序)要求,每一子项目需要一定的时间完成.网络的每条弧表示一个子项目,如果以弧长表示每一子项目需要的时间,则最早完工时间对应于网络中的最长路(关键路线).工程上所谓的关键路线法.项目网络不含圈（其最长路问题和最短路问题都是可解的）(开始)AF(结束)566744513B

EDC实例例：最大流/最小费用流

从甲地到乙地的公路网纵横交错，每天每条路上的通车量有上限.从甲地到乙地的每天最多能通车多少辆?

考虑每条路上的通行成本,如何确定某个车队的具体行车路线,使总成本最小?(甲)AF(乙)566744513B

EDC例：

运输问题(TransportationProblem)某种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工厂.假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？

网络优化问题的例子

ST特殊的最小费用流问题（二部图,|S|=M,|T|=N）例：指派问题(AssignmentProblem)一家公司经理准备安排N名员工去完成N项任务，每人一项.由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的.如何分配工作方案可以使总回报最大？网络优化问题的例子

ST特殊的最小费用流问题（二部图，|S|=|T|=N）例：匹配问题(MatchingProblem)

在一次有m个大学毕业生和n家公司参加的供需见面会上，每个毕业生愿意加入到若干家公司中的一家工作，而每个公司愿意接收若干毕业生中的一人到公司工作.那么，最后最多有多少人可以在这次供需见面会上找到工作（即最多有多少家公司可以在这次供需见面会上招聘到员工）？如果每个毕业生到每一家公司工作将会产生的效益不同，那么，为了使得最后产生的总效益最大，最多有多少人可以在这次供需见面会上找到工作？网络优化问题的例子

例：中国邮递员问题

一名邮递员负责投递某个街区的邮件.如何设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国学者管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题.网络优化问题的例子

例：旅行商问题(TSP-TravelingSalesmanProblem)

一名推销员准备前往若干城市推销产品.如何为他(她)设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这一问题的研究历史十分悠久，通常称之为旅行商问题.

网络优化问题的例子

BACDEFGHI例：套汇（Arbitrage）问题 在外汇市场上，将1单位的某种货币通过多次兑换，获得多于1单位的同种货币，称为套汇。如：1单位的A货币＝(兑换)46.4单位B货币1单位的B货币＝(兑换)2.5单位C货币1单位的C货币＝(兑换)0.0091单位A货币则:1单位的A货币＝(通过三次兑换获得)46.4＊2.5＊0.0091=1.0556单位A货币网络优化问题的例子

可以变成检测负圈的问题 现在假设给定了若干种货币及其两两之间的兑换率，请你帮助找到一种套汇方式（或判定该外汇市场上不存在套汇的可能）。套汇:46.4＊2.5＊0.0091=1.0556>1两边取倒数(乘积<1)，再取对数（求和<0）可以变成检测负圈的问题套汇（Arbitrage）问题化乘积为求和的技术，也常用于“可靠性问题”可能是完全有向图；弧上的权就是汇率的倒数的对数值！例：逃生路线问题n*n网格节点上有m个房间，逃到边上节点就算逃生成功如何规划逃生路线，使这些路线互不相交？网络优化问题的例子

可以变成最大流问题逃生成功没有逃生路线m个房间是供应节点（源，供应量为１）只有边上节点可以是吸收节点（汇，吸收量为１）多源多汇，容易变成单源单汇每条边容量为１每个节点容量为１（通过增加节点和边，变成边容量）逃生路线问题变成最大流问题逃生成功没有逃生路线其他目标？例：空间实验问题某航天公司计划进行一次空间载人飞行，宇航员将在飞行中进行一系列科学实验。目前该公司收到了多个不同的科学实验申请，完成每个实验要求携带相应的一种或多种仪器设备（不同的实验所需要的仪器设备中有些可能是相同的，而另外有些可能是不同的）。已知完成每个实验后公司所得到的相应报酬（不同实验的报酬可能不同），并已知飞行器携带每种仪器设备的相应费用（不同仪器设备的费用可能不同）。公司希望你帮助选定此次飞行究竟从事哪些科学实验，以及需要携带哪些仪器设备，使此次飞行的总利润最大（总利润=总报酬－总费用）。

网络优化问题的例子

可以变成最大流问题空间实验问题最大流(最小割)问题设备实验n个实验(报酬pi)m类设备(成本ci)12…m12…ncipist计划

有限割有限割的容量：ST例:学生分区问题假设某个城市分为L个区,每个区有若干男孩和若干女孩需要上学.假设每个区有一所小学,每所小学所能容纳的学生总数已知,并且按照规定,每所小学所能容纳的男孩和女孩比例不能太大或太小.假设每两个区之间的路程已知(同一区内认为路程近似为0),如何为需要上学的小孩分配学校,使得所有小孩上学所走的总路程最少?网络优化问题的例子

可以变成最小费用流的问题L=2为例：bi

男孩；gi

女孩；ui

学校容量(p,q)男孩比例上下限；dij距离学生分区问题最小费用流问题b1b2g1g2(0,u1)(0,u2)t容量d11d12d21d22d11d12d21d22(pu1,qu1)(pu2,qu2)费用为０例:一类排序(Scheduling)问题某车间接受了p项不同的加工任务，要求在车间的q台完全相同的机器上加工每项任务所需要的加工时间是相同的，且只需要在其中的任何一台机器上加工完成即可每项任务在同一时刻不能在两个或两个以上的机器上加工，且每项任务的加工都必须一次完成（即一旦开始加工，加工中不能间断每台机器在同一时刻不能加工两项或两项以上的任务从当前时刻开始计时，如果第j项任务的完工时间为tj，则该车间的信誉损失为cj(tj)（假设该函数为增函数）车间希望制订一个加工计划，使总的信誉损失最小网络优化问题的例子

可以变成最小费用流的问题一类排序(Scheduling)问题12…p12…r11…1-q-q

…-q

p个工件；q台机器;加工时间ac1(a)c1(2a)c1(ra)c2(a)c2(2a)cp(2a)c2(ra)cp(a)cp(ra)每台机器加工的工件数：r=p/q(不妨设为整数)工件加工位置变成最小费用流的问题网络优化问题的建模与求解最短路问题

一般数学模型 设图中有n个顶点，求顶点1到顶点n的最短路。设决策变量xij，当xij=1时为弧(i,j)位于顶点1到顶点n的路上；否则xij=0。为弧(i,j)上的权。实例1 现有A、B1、B2、C1、C2、C3、D共7个城市，点与点之间的连线表示城市间有道路相连。连线旁的数字表示道路的长度。求城市A到城市D的一条最短路。AB1B2C1C2C3D23333211144LINGO程序!Wehaveanetworkof7cities.Wewanttofindthelengthoftheshortestroutefromcity1tocity7;sets:!Hereisourprimitivesetofsevencities;cities/A,B1,B2,C1,C2,C3,D/;!TheDerivedset"roads"liststheroadsthatexistbetweenthecities;roads(cities,cities)/A,B1A,B2B1,C1B1,C2B1,C3B2,C1B2,C2B2,C3C1,DC2,DC3,D/:w,x;endsetsdata:!Herearethedistancesthatcorrespondtoabovelinks;w=24331231134;enddatan=@size(cities);!Thenumberofcities;min=@sum(roads:w*x);@for(cities(i)|i#ne#1#and#i#ne#n:@sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i)));@sum(roads(i,j)|i#eq#1:x(i,j))=1;Globaloptimalsolutionfound.Objectivevalue:6.000000Totalsolveriterations:0VariableValueReducedCostX(A,B1)1.0000000.000000X(A,B2)0.0000001.000000X(B1,C1)1.0000000.000000X(B1,C2)0.0000002.000000X(B1,C3)0.0000001.000000X(B2,C1)0.0000000.000000X(B2,C2)0.0000003.000000X(B2,C3)0.0000002.000000X(C1,D)1.0000000.000000X(C2,D)0.0000000.000000X(C3,D)0.0000000.000000计算结果最短路是AB1C1D最短路长是6个单位。Globaloptimalsolutionfound.Objectivevalue:6.000000Totalsolveriterations:0VariableValueReducedCostX(A,B1)1.0000000.000000X(A,B2)0.0000001.000000X(B1,C1)1.0000000.000000X(B1,C2)0.0000002.000000X(B1,C3)0.0000001.000000X(B2,C1)0.0000000.000000X(B2,C2)0.0000003.000000X(B2,C3)0.0000002.000000X(C1,D)1.0000000.000000X(C2,D)0.0000000.000000X(C3,D)0.0000000.000000网络优化问题的建模与求解最大流问题

一般数学模型设G（V，A）为有向图，若在V中有两个不同的顶点子集S和T，而在边集A上定义一个非负权值c，则称G为一个网络。称S中的顶点为源，T中的顶点为汇，即非源又非汇的顶点称为中间点，称c为G的容量函数，容量函数在边a上的值称为容量，弧(u,v)的容量记为c(u,v),求顶点S到顶点T的最大流。设决策变量fij，fij时为通过弧(i,j)上的流量；实例2现需要将城市s的石油通过管道运送到城市t，中间有4个中转站v1、v2、v3、v4，城市与中转站的连接以管道的容量如图，求从城市s到城市t的最大流。sv1v4t(9)v2v3(7)(8)(5)(2)(9)(6)(5)(10)最大流模型本题是一个源和一个汇的网络。 网络G中每一个条边(u,v)有一个容量c(u,v),边(u,v)有一个通过流记为f(u,v).其满足0≤f(u,v)≤c(u,v).对于所有中间点u，流入的总量应等于流出的总量。LINGO程序sets:nodes/s,1,2,3,4,t/;arcs(nodes,nodes)/s,1s,21,21,32,43,23,t4,34,t/:c,f;endsetsdata:c=8759925610;enddatamax=flow;@for(nodes(i)|i#ne#1#and#i#ne#@size(nodes):@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0);@sum(arcs(i,j)|i#eq#1:f(i,j))=flow;@for(arcs:@bnd(0,f,c));计算结果Globaloptimalsolutionfound.Objectivevalue:14.00000Totalsolveriterations:3VariableValueReducedCostFLOW14.000000.000000C(S,1)8.0000000.000000C(S,2)7.0000000.000000C(1,2)5.0000000.000000C(1,3)9.0000000.000000C(2,4)9.0000000.000000C(3,2)2.0000000.000000C(3,T)5.0000000.000000C(4,3)6.0000000.000000C(4,T)10.000000.000000F(S,1)7.0000000.000000F(S,2)7.0000000.000000F(1,2)2.0000000.000000F(1,3)5.0000000.000000F(2,4)9.000000-1.000000F(3,2)0.0000000.000000F(3,T)5.000000-1.000000F(4,3)0.0000001.000000F(4,T)9.0000000.000000sv1v4t(9,9)v2v3(7,7)(8,7)(5,2)(2,0)(9,5)(6,0)(5,5)(10,9)该网络的最大流为14，括号中第一个数字为容量，第二个数字为流量网络优化问题的建模与求解工程项目统筹计划问题某项目工程由11项作业组成（分别用代号A，B，…，K表示），其计划完成时间及作业间相互关系如下表：作业计划完成时间/天紧前作业作业计划完成时间/天紧前作业A5---G21B，EB10---H35B，EC11---I25B，ED4BJ15F，G，IE4AK20F，GF15C，D问题一：建立计划网络图，建立模型求出总工期最短的工程项目作业计划。问题二：进一步得到每个项目作业的最早开工时间、作业关键路径。问题三：若要求工程在49天内完成，为提前完成工程，有些作业需要加快进度、缩短工期，而这样需要额外增加费用，如下表所示，那么如何安排作业才能使额外增加的总费用最少。作业(i,j)计划完成时间/天最短完成时间/天缩短1天增加的费用/元作业(i,j)计划完成时间/天最短完成时间/天缩短1天增加的费用/元B(1,3)108700H(5,8)3530500C(1,4)118400I(5,7)2522300E(2,5)43450J(7,8)1512400G(5,6)2116600K(6,8)2016500问题4在实际中若每作业的完成受到一些意外因素的干扰，事先不能确定，只能根据以往的经验进行估计，通常情况下，对完成一项作业可以给出三个时间上的估计值：最乐观的估计值(a)，最悲观的估计值(b)，最可能的估计值(m).设tij是完成作业(i,j)的实际时间，其期望与方差的计算公式为若各项作业完成的三个估计时间如表所示，求在规定52天的时间内完成全部作业的概率。进一步，如果完成全部作业的概率大于等于95%，那么工期至少需要多少天？问题1的建模与求解建立计划网络图⑧④⑤⑥⑦①③②ABCDEFGHJKI5435152025211011154建立模型设xi事件i的开始时间，1为最初事件，n为最终事件。设tij是作业(i,j)的计划时间，H是所有事件的集合，G是所有作业的集合。目标函数为总工期最短，约束条件：事件j的开始时间小于等于事件i开始时间加作业(i,j)计划时间tij。LINDO程序minx8-x1subjectto2)x2-x1>=53)x3-x1>=104)x4-x1>=115)x5-x2>=46)x4-x3>=47)x5-x3>=08)x6-x4>=159)x6-x5>=2110)x7-x5>=2511)x8-x5>=3512)x7-x6>=013)x8-x6>=2014)x8-x7>=15endObjectivevalue:51.00000Totalsolveriterations:1VariableValueReducedCostX851.000000.000000X10.0000000.000000X25.0000000.000000X310.000000.000000X414.000000.000000X510.000000.000000X631.000000.000000X735.000000.000000计算结果问题二的建模与求解目标函数：作业的开始时间尽量的早引进作业对应弧上的松弛变量sij，且这样就可以得到作业的最迟开工时间。当最早开工时间与最迟开工时间相同时，就得到项目的关键路径。sets:events/1..8/:x;operate(events,events)/!ABCDE0FGHI0JK;1,21,31,43,42,53,54,65,65,85,76,77,86,8/:s,t;endsetsdata:t=510114401521352501520;enddatamin=@sum(events:x);@for(operate(i,j):s(i,j)=x(j)-x(i)-t(i,j));LINGO程序计算结果VariableValueReducedCostX(1)0.0000008.000000X(2)5.0000000.000000X(3)10.000000.000000X(4)14.000000.000000X(5)10.000000.000000X(6)31.000000.000000X(7)35.000000.000000X(8)51.000000.000000S(1,2)0.0000001.000000S(1,3)0.0000006.000000S(1,4)3.0000000.000000S(3,4)0.0000001.000000S(2,5)1.0000000.000000S(3,5)0.0000004.000000S(4,6)2.0000000.000000S(5,6)0.0000002.000000S(5,8)6.0000000.000000S(5,7)0.0000001.000000S(6,7)4.0000000.000000S(7,8)1.0000000.000000S(6,8)0.0000001.000000

x(1)=0，A，B，C的最早开工时间是0x(2)=5，E的最早开工时间是5x(3)=10，D的最早开工时间是10…x(8)=51，总最短工期是51天松驰变量s(i,j)>0，说明还有剩余时间，作业(i,j)的开工时间还可以推迟，例如s(1,4)=3，作业C可推迟3天。又由于s(4,6)=2，后继的作业F可推迟2天，所以作业C最多可推迟5天。关键路线：①③⑤⑥⑧求关键路线的最长路线模型设xij为0-1变量，当作业(i,j)位于关键路线上取1，否则取0，数学模型为：sets:events/1..8/:d;operate(events,events)/1,21,31,43,42,53,54,65,65,85,76,77,86,8/:t,x;endsetsdata:t=510114401521352501520;d=1000000-1;enddatamax=@sum(operate:t*x);@for(events(i):@sum(operate(i,j):x(i,j))-@sum(operate(j,i):x(j,i))=d(i););LINGO程序计算结果

Globaloptimalsolutionfound.Objectivevalue:51.00000Totalsolveriterations:0VariableValueReducedCostX(1,2)0.0000000.000000X(1,3)1.0000000.000000X(1,4)0.0000005.000000X(3,4)0.0000002.000000X(2,5)0.0000001.000000X(3,5)1.0000000.000000X(4,6)0.0000000.000000X(5,6)1.0000000.000000X(5,8)0.0000006.000000X(5,7)0.0000001.000000X(6,7)0.0000005.000000X(7,8)0.0000000.000000X(6,8)1.0000000.000000关键路线：①③⑤⑥⑧问题3的建模与求解工程要求在49天内完成。 设xi事件i的开始时间，tij是作业(i,j)的计划时间，mij是作业(i,j)的最短时间，yij是作业(i,j)可能减少和时间，d为要求完成的天数，1为最初事件，n为最终事件。建立模型：LINDO程序min700y13+400y14+450y25+600y56+300y57+500y58+500y68+400y78subjectto2)x2-x1>=53)x3-x1+y13>=104)x4-x1+y14>=115)x5-x2+y25>=46)x4-x3>=47)x5-x3>=08)x6-x4>=159)x6-x5+y56>=2110)x7-x5+y57>=2511)x8-x5+y58>=3512)x7-x6>=013)x8-x6+y68>=2014)x8-x7+y78>=1515)x8-x1<=49endsuby132suby143suby251suby565suby573suby585suby684suby783计算结果Globaloptimalsolutionfound.Objectivevalue:1200.000Totalsolveriterations:5VariableValueReducedCostY131.0000000.000000Y140.000000400.0000Y250.000000450.0000Y560.000000100.0000Y570.000000100.0000Y580.000000500.0000Y681.0000000.000000Y780.000000200.0000X25.0000000.000000X10.0000000.000000X39.0000000.000000X413.000000.000000X59.0000000.000000X630.00