数学建模网络优化

数学建模•网络(Network)：数学模型、数学结构----图•优化(Optimization):从若干可能的方案中寻求某种意义下的最优方案•与图论有联系，也有区别（侧重点不同）•网络优化就是研究与（赋权）图有关的最优化问题图论：图的性质网络优化：与（赋权）图有关的优化问题组合数学组合优化网络优化简介图的基本概念5a1a1v2v3a3v4a4v5v2a6a图G=(V，A)，其中顶点集V=弧集A=弧},,,,{54321vvvvv},,,,,{654321aaaaaa),(211vva),(212vva),(323vva),(434vva),(145vva),(336vva例：公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市.假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？网络优化问题的例子131325463421246赋权图“直接方式”：总经理直接传达；“接力方式”：总经理只给某些部门经理打电话，而让这些得到信息的部门经理打电话将信息进一步传达给其他某些部门经理，依此类推，最后将信息传达到所有部门经理.如何决定传达信息的途径使得信息快速准确？信息传播是有向的，有一个“根”。信息传播途径（忽略方向时）是一棵树。以上结构称为树形图，上面这样一类问题称为最小树形图问题.例：信息传播最小树形图例最短路问题一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地.从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路.网络优化问题的例子AF566744513BEDC甲地乙地实例例：工程项目统筹问题大型复杂工程项目往往被分成许多子项目,子项目之间有一定的先后顺序(偏序)要求,每一子项目需要一定的时间完成.网络的每条弧表示一个子项目,如果以弧长表示每一子项目需要的时间,则最早完工时间对应于网络中的最长路(关键路线).工程上所谓的关键路线法.项目网络不含圈（其最长路问题和最短路问题都是可解的）(开始)AF(结束)566744513BEDC实例例：最大流/最小费用流从甲地到乙地的公路网纵横交错，每天每条路上的通车量有上限.从甲地到乙地的每天最多能通车多少辆?考虑每条路上的通行成本,如何确定某个车队的具体行车路线,使总成本最小?(甲)AF(乙)566744513BEDC例：运输问题(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.05561两边取倒数(乘积1)，再取对数（求和0）可以变成检测负圈的问题套汇（Arbitrage）问题化乘积为求和的技术，也常用于“可靠性问题”•可能是完全有向图；•弧上的权就是汇率的倒数的对数值！例：逃生路线问题•n*n网格节点上有m个房间，逃到边上节点就算逃生成功•如何规划逃生路线，使这些路线互不相交？网络优化问题的例子可以变成最大流问题逃生成功没有逃生路线•m个房间是供应节点（源，供应量为１）•只有边上节点可以是吸收节点（汇，吸收量为１）•多源多汇，容易变成单源单汇•每条边容量为１•每个节点容量为１（通过增加节点和边，变成边容量）逃生路线问题变成最大流问题逃生成功没有逃生路线其他目标？例：空间实验问题•某航天公司计划进行一次空间载人飞行，宇航员将在飞行中进行一系列科学实验。目前该公司收到了多个不同的科学实验申请，完成每个实验要求携带相应的一种或多种仪器设备（不同的实验所需要的仪器设备中有些可能是相同的，而另外有些可能是不同的）。•已知完成每个实验后公司所得到的相应报酬（不同实验的报酬可能不同），并已知飞行器携带每种仪器设备的相应费用（不同仪器设备的费用可能不同）。•公司希望你帮助选定此次飞行究竟从事哪些科学实验，以及需要携带哪些仪器设备，使此次飞行的总利润最大（总利润=总报酬－总费用）。网络优化问题的例子可以变成最大流问题空间实验问题最大流(最小割)问题设备实验n个实验(报酬pi)m类设备(成本ci)12…m12…ncipist•计划有限割•有限割的容量：TiiTiiiiTiiSiicppcpST例:学生分区问题•假设某个城市分为L个区,每个区有若干男孩和若干女孩需要上学.•假设每个区有一所小学,每所小学所能容纳的学生总数已知,并且按照规定,每所小学所能容纳的男孩和女孩比例不能太大或太小.•假设每两个区之间的路程已知(同一区内认为路程近似为0),如何为需要上学的小孩分配学校,使得所有小孩上学所走的总路程最少?网络优化问题的例子可以变成最小费用流的问题•L=2为例：bi男孩；gi女孩；ui学校容量•(p,q)男孩比例上下限；dij距离学生分区问题最小费用流问题b1b2g1g2(0,u1)(0,u2)t),0(容量d11d12d21d22d11d12d21d22(pu1,qu1)(pu2,qu2)),0(),0(费用为０例:一类排序(Scheduling)问题•某车间接受了p项不同的加工任务，要求在车间的q台完全相同的机器上加工•每项任务所需要的加工时间是相同的，且只需要在其中的任何一台机器上加工完成即可•每项任务在同一时刻不能在两个或两个以上的机器上加工，且每项任务的加工都必须一次完成（即一旦开始加工，加工中不能间断•每台机器在同一时刻不能加工两项或两项以上的任务•从当前时刻开始计时，如果第j项任务的完工时间为tj，则该车间的信誉损失为cj(tj)（假设该函数为增函数）•车间希望制订一个加工计划，使总的信誉损失最小网络优化问题的例子可以变成最小费用流的问题一类排序(Scheduling)问题12…p12…r11…1-q-q…-qp个工件；q台机器;加工时间ac1(a)c1(2a)c1(ra)c2(a)c2(2a)cp(2a)c2(ra)cp(a)cp(ra)每台机器加工的工件数：r=p/q(不妨设为整数)工件加工位置变成最小费用流的问题网络优化问题的建模与求解EjixniniixxtsxwijnEijjjinEjijijEjiijij),(,0,10111.min),(1),(1),(ijw1.最短路问题一般数学模型设图中有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/;!TheDerivedsetroadsliststheroadsthatexistbetweenthecities;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.0000