数学建模网络优化ppt课件.ppt

《数学建模网络优化ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模网络优化ppt课件.ppt（54页珍藏版）》请在三一办公上搜索。

1、数学建模,网络(Network)：数学模型、数学结构 - 图,优化(Optimization) : 从若干可能的方案中寻求某种意义下的最优方案,与图论有联系，也有区别（侧重点不同）,网络优化就是研究与（赋权）图有关的最优化问题,图论：图的性质,网络优化：与（赋权）图有关的优化问题,组合数学,组合优化,网 络 优 化 简 介,图的基本概念,图G=(V，A)，其中顶点集V= 弧集A= 弧,例： 公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来， 使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市. 假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决

2、定在哪些城市间修建高速公路，使得总成本最小？,网络优化问题的例子,赋权图,“直接方式”：总经理直接传达；“接力方式”：总经理只给某些部门经理打电话，而让这些得到信息的部门经理打电话将信息进一步传达给其他某些部门经理，依此类推，最后将信息传达到所有部门经理. 如何决定传达信息的途径使得信息快速准确？,信息传播是有向的，有一个“根”。,信息传播途径（忽略方向时）是一棵树。,以上结构称为树形图，上面这样一类问题称为最小树形图问题.,例： 信息传播,最小树形图,例 最短路问题一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地. 从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条

3、线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路.,网络优化问题的例子,甲地,乙地,实例,例：工程项目统筹问题,大型复杂工程项目往往被分成许多子项目,子项目之间有一定的先后顺序(偏序)要求, 每一子项目需要一定的时间完成. 网络的每条弧表示一个子项目,如果以弧长表示每一子项目需要的时间,则最早完工时间对应于网络中的最长路 (关键路线). 工程上所谓的关键路线法.,项目网络不含圈（其最长路问题和最短路问题都是可解的）,实例,例：最大流 / 最小费用流,从甲地到乙地的公路网纵横交错，每天每条路上的通车量有上限. 从甲地到乙地的每天最多能通车多少辆?,考虑每条

4、路上的通行成本,如何确定某个车队的具体行车路线,使总成本最小?,例： 运输问题(Transportation Problem)某种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工厂. 假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？,网络优化问题的例子,特殊的最小费用流问题（二部图,|S|=M, |T|=N）,例： 指派问题(Assignment Problem)一家公司经理准备安排N名员工去完成N项任务，每人一项. 由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的. 如何分配

5、工作方案可以使总回报最大？,网络优化问题的例子,特殊的最小费用流问题（二部图，|S|=|T|=N）,例：匹配问题(Matching Problem)在一次有m个大学毕业生和n家公司参加的供需见面会上，每个毕业生愿意加入到若干家公司中的一家工作，而每个公司愿意接收若干毕业生中的一人到公司工作. 那么，最后最多有多少人可以在这次供需见面会上找到工作（即最多有多少家公司可以在这次供需见面会上招聘到员工）？如果每个毕业生到每一家公司工作将会产生的效益不同，那么，为了使得最后产生的总效益最大，最多有多少人可以在这次供需见面会上找到工作？,网络优化问题的例子,例：中国邮递员问题一名邮递员负责投递某个街区的

6、邮件. 如何设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国学者管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题.,网络优化问题的例子,例：旅行商问题(TSP-Traveling Salesman Problem)一名推销员准备前往若干城市推销产品. 如何为他(她)设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这一问题的研究历史十分悠久，通常称之为旅行商问题.,网络优化问题的例子,例：套汇（Arbitrage）问题 在外汇市场上，将1单位的某种货币通过多次兑换，获得多于1单位的同种货币，称为套汇。如：

7、1单位的A货币(兑换) 46.4单位B货币1单位的B货币(兑换) 2.5单位C货币 1单位的C货币(兑换) 0.0091单位A货币 则: 1单位的A货币 (通过三次兑换获得)46.42.50.0091=1.0556单位A货币,网络优化问题的例子,可以变成检测负圈的问题,现在假设给定了若干种货币及其两两之间的兑换率，请你帮助找到一种套汇方式（或判定该外汇市场上不存在套汇的可能）。,套汇: 46.42.50.0091=1.0556 1两边取倒数(乘积1)，再取对数（求和0）可以变成检测负圈的问题,套汇（Arbitrage）问题,化乘积为求和的技术，也常用于“可靠性问题”,可能是完全有向图；弧上的权

8、就是汇率的倒数的对数值！,例：逃生路线问题n*n网格节点上有m个房间，逃到边上节点就算逃生成功如何规划逃生路线，使这些路线互不相交？,网络优化问题的例子,可以变成最大流问题,m个房间是供应节点（源，供应量为）只有边上节点可以是吸收节点（汇，吸收量为 ）多源多汇，容易变成单源单汇每条边容量为每个节点容量为（通过增加节点和边，变成边容量）,逃生路线问题,变成最大流问题,其他目标？,例：空间实验问题某航天公司计划进行一次空间载人飞行，宇航员将在飞行中进行一系列科学实验。目前该公司收到了多个不同的科学实验申请，完成每个实验要求携带相应的一种或多种仪器设备（不同的实验所需要的仪器设备中有些可能是相同的，

9、而另外有些可能是不同的）。已知完成每个实验后公司所得到的相应报酬（不同实验的报酬可能不同），并已知飞行器携带每种仪器设备的相应费用（不同仪器设备的费用可能不同）。公司希望你帮助选定此次飞行究竟从事哪些科学实验，以及需要携带哪些仪器设备，使此次飞行的总利润最大（总利润=总报酬总费用）。,网络优化问题的例子,可以变成最大流问题,空间实验问题,最大流(最小割)问题,设备 实验,n个实验(报酬pi)m类设备(成本ci),计划有限割有限割的容量：,例: 学生分区问题假设某个城市分为L个区, 每个区有若干男孩和若干女孩需要上学. 假设每个区有一所小学, 每所小学所能容纳的学生总数已知, 并且按照规定, 每

10、所小学所能容纳的男孩和女孩比例不能太大或太小. 假设每两个区之间的路程已知(同一区内认为路程近似为0), 如何为需要上学的小孩分配学校, 使得所有小孩上学所走的总路程最少?,网络优化问题的例子,可以变成最小费用流的问题,L=2为例：bi 男孩； gi 女孩； ui 学校容量(p,q)男孩比例上下限； dij距离,学生分区问题,最小费用流问题,b1b2g1g2,(0,u1)(0,u2),t,容量,d11d12d21d22d11d12d21d22,(pu1,qu1),(pu2,qu2),费用为,例: 一类排序(Scheduling)问题某车间接受了p项不同的加工任务，要求在车间的q台完全相同的机器

11、上加工每项任务所需要的加工时间是相同的，且只需要在其中的任何一台机器上加工完成即可每项任务在同一时刻不能在两个或两个以上的机器上加工，且每项任务的加工都必须一次完成（即一旦开始加工，加工中不能间断每台机器在同一时刻不能加工两项或两项以上的任务从当前时刻开始计时，如果第 j 项任务的完工时间为tj，则该车间的信誉损失为cj(tj)（假设该函数为增函数）车间希望制订一个加工计划，使总的信誉损失最小,网络优化问题的例子,可以变成最小费用流的问题,一类排序(Scheduling)问题,个工件；q台机器;加工时间a,每台机器加工的工件数：r=p/q (不妨设为整数),工件加工位置,变成最小费用流的问题,

12、网络优化问题的建模与求解,最短路问题一般数学模型设图中有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的一条最短路。,LINGO程序,! We have a network of 7 cities. We want to find the length of the shortest route from city 1 to city 7;sets:

13、 ! Here is our primitive set of seven cities; cities/A, B1, B2, C1, C2, C3, D/; ! The Derived set roads lists the roads that exist between the cities; roads(cities, cities)/ A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 C1,D C2,D C3,D/: w, x;endsets,data: ! Here are the distances that correspond to

14、above links; w = 2 4 3 3 1 2 3 1 1 3 4;enddatan=size(cities); ! The number of cities;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;,Global optimal solution found. Objective value: 6.000000 Total solver

15、iterations: 0 Variable Value Reduced Cost X( A, B1) 1.000000 0.000000 X( A, B2) 0.000000 1.000000 X( B1, C1) 1.000000 0.000000 X( B1, C2) 0.000000 2.000000 X( B1, C3) 0.000000 1.000000 X( B2, C1) 0.000000 0.000000 X( B2, C2) 0.000000 3.000000 X( B2, C3) 0.000000 2.000000 X( C1, D) 1.000000 0.000000

16、X( C2, D) 0.000000 0.000000 X( C3, D) 0.000000 0.000000,计算结果,最短路是A B1 C1 D最短路长是6个单位。,Global optimal solution found. Objective value: 6.000000 Total solver iterations: 0 Variable Value Reduced Cost X( A, B1) 1.000000 0.000000 X( A, B2) 0.000000 1.000000 X( B1, C1) 1.000000 0.000000 X( B1, C2) 0.00000

17、0 2.000000 X( B1, C3) 0.000000 1.000000 X( B2, C1) 0.000000 0.000000 X( B2, C2) 0.000000 3.000000 X( B2, C3) 0.000000 2.000000 X( C1, D) 1.000000 0.000000 X( C2, D) 0.000000 0.000000 X( C3, D) 0.000000 0.000000,网络优化问题的建模与求解,最大流问题一般数学模型设G（V，A）为有向图，若在V中有两个不同的顶点子集S和T，而在边集A上定义一个非负权值c，则称G为一个网络。称S中的顶点为源，T

18、中的顶点为汇，即非源又非汇的顶点称为中间点，称c为G的容量函数，容量函数在边a上的值称为容量，弧(u,v)的容量记为c(u,v),求顶点S到顶点T的最大流。设决策变量fij，fij时为通过弧(i,j)上的流量；,实例2,现需要将城市s的石油通过管道运送到城市t，中间有4个中转站v1、v2、v3、v4，城市与中转站的连接以管道的容量如图，求从城市s到城市t的最大流。,最大流模型,本题是一个源和一个汇的网络。网络G中每一个条边(u,v)有一个容量c (u,v),边(u,v)有一个通过流记为f (u,v).其满足0f (u,v)c (u,v).对于所有中间点u，流入的总量应等于流出的总量。,LING

19、O程序,sets: nodes/s,1,2,3,4,t/; arcs(nodes, nodes)/ s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/: c, f;endsetsdata: c = 8 7 5 9 9 2 5 6 10;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,

20、 c);,计算结果,Global optimal solution found. Objective value: 14.00000 Total solver iterations: 3 Variable Value Reduced Cost FLOW 14.00000 0.000000 C( S, 1) 8.000000 0.000000 C( S, 2) 7.000000 0.000000 C( 1, 2) 5.000000 0.000000 C( 1, 3) 9.000000 0.000000 C( 2, 4) 9.000000 0.000000 C( 3, 2) 2.000000 0.

21、000000 C( 3, T) 5.000000 0.000000 C( 4, 3) 6.000000 0.000000 C( 4, T) 10.00000 0.000000 F( S, 1) 7.000000 0.000000 F( S, 2) 7.000000 0.000000 F( 1, 2) 2.000000 0.000000 F( 1, 3) 5.000000 0.000000 F( 2, 4) 9.000000 -1.000000 F( 3, 2) 0.000000 0.000000 F( 3, T) 5.000000 -1.000000 F( 4, 3) 0.000000 1.0

22、00000 F( 4, T) 9.000000 0.000000,该网络的最大流为14，括号中第一个数字为容量，第二个数字为流量,网络优化问题的建模与求解,工程项目统筹计划问题某项目工程由11项作业组成（分别用代号A，B，K表示），其计划完成时间及作业间相互关系如下表：,问题一：建立计划网络图，建立模型求出总工期最短的工程项目作业计划。问题二：进一步得到每个项目作业的最早开工时间、作业关键路径。问题三：若要求工程在49天内完成，为提前完成工程，有些作业需要加快进度、缩短工期，而这样需要额外增加费用，如下表所示，那么如何安排作业才能使额外增加的总费用最少。,问题4 在实际中若每作业的完成受到一些

23、意外因素的干扰，事先不能确定，只能根据以往的经验进行估计，通常情况下，对完成一项作业可以给出三个时间上的估计值：最乐观的估计值(a)，最悲观的估计值(b)，最可能的估计值(m). 设tij是完成作业(i,j)的实际时间，其期望与方差的计算公式为,若各项作业完成的三个估计时间如表所示，求在规定52天的时间内完成全部作业的概率。进一步，如果完成全部作业的概率大于等于95%，那么工期至少需要多少天？,问题1的建模与求解,建立计划网络图,建立模型,设xi事件i的开始时间，1为最初事件，n为最终事件。设tij是作业(i,j)的计划时间，H是所有事件的集合，G是所有作业的集合。目标函数为总工期最短，约束条

24、件：事件j的开始时间小于等于事件i开始时间加作业(i,j)计划时间tij 。,LINDO程序,min x8-x1subject to2) 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 = 15end,Objective value: 51.00000 Total sol

25、ver iterations: 1 Variable Value Reduced Cost X8 51.00000 0.000000 X1 0.000000 0.000000 X2 5.000000 0.000000 X3 10.00000 0.000000 X4 14.00000 0.000000 X5 10.00000 0.000000 X6 31.00000 0.000000 X7 35.00000 0.000000,计算结果,问题二的建模与求解,目标函数：作业的开始时间尽量的早,引进作业对应弧上的松弛变量sij，且,这样就可以得到作业的最迟开工时间。当最早开工时间与最迟开工时间相同时，

26、就得到项目的关键路径。,sets: events/1.8/: x; operate(events, events)/ ! A B C D E 0 F G H I 0 J K; 1,2 1,3 1,4 3,4 2,5 3,5 4,6 5,6 5,8 5,7 6,7 7,8 6,8 /: s, t;endsetsdata: t = 5 10 11 4 4 0 15 21 35 25 0 15 20;enddatamin=sum(events : x);for(operate(i,j): s(i,j)=x(j)-x(i)-t(i,j);,LINGO程序,计算结果,Variable Value Red

27、uced Cost X( 1) 0.000000 8.000000 X( 2) 5.000000 0.000000 X( 3) 10.00000 0.000000 X( 4) 14.00000 0.000000 X( 5) 10.00000 0.000000 X( 6) 31.00000 0.000000 X( 7) 35.00000 0.000000 X( 8) 51.00000 0.000000 S( 1, 2) 0.000000 1.000000 S( 1, 3) 0.000000 6.000000 S( 1, 4) 3.000000 0.000000 S( 3, 4) 0.000000

28、 1.000000 S( 2, 5) 1.000000 0.000000 S( 3, 5) 0.000000 4.000000 S( 4, 6) 2.000000 0.000000 S( 5, 6) 0.000000 2.000000 S( 5, 8) 6.000000 0.000000 S( 5, 7) 0.000000 1.000000 S( 6, 7) 4.000000 0.000000 S( 7, 8) 1.000000 0.000000 S( 6, 8) 0.000000 1.000000,x(1)=0，A，B，C的最早开工时间是0,x(2)=5，E的最早开工时间是5,x(3)=10

29、，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,2 1,3 1,4 3,4 2,5 3,5 4,6 5,6 5,8 5,7 6,7 7,8 6,8 /: t, x;endse

30、tsdata: t = 5 10 11 4 4 0 15 21 35 25 0 15 20; d = 1 0 0 0 0 0 0 -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程序,计算结果,Global optimal solution found. Objective value: 51.00000 Total solver iterations: 0 Variable Value Reduced Cost X(

31、1, 2) 0.000000 0.000000 X( 1, 3) 1.000000 0.000000 X( 1, 4) 0.000000 5.000000 X( 3, 4) 0.000000 2.000000 X( 2, 5) 0.000000 1.000000 X( 3, 5) 1.000000 0.000000 X( 4, 6) 0.000000 0.000000 X( 5, 6) 1.000000 0.000000 X( 5, 8) 0.000000 6.000000 X( 5, 7) 0.000000 1.000000 X( 6, 7) 0.000000 5.000000 X( 7,

32、8) 0.000000 0.000000 X( 6, 8) 1.000000 0.000000,关键路线：,问题3的建模与求解,工程要求在49天内完成。设xi事件i的开始时间，tij是作业(i,j)的计划时间，mij是作业(i,j)的最短时间，yij是作业(i,j)可能减少和时间，d为要求完成的天数，1为最初事件，n为最终事件。建立模型：,LINDO程序,min 700y13 + 400y14 + 450y25 + 600y56 + 300y57 + 500y58 + 500y68 + 400y78 subject to2) x2 - x1 = 53) x3 - x1 + y13 = 104)

33、 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 = 20,14) x8 - x7 + y78 = 1515) x8 - x1 = 49endsub y13 2sub y14 3 sub y25 1sub y56 5sub y57 3sub y58 5sub y68 4sub y78 3,

34、计算结果,Global optimal solution found. Objective value: 1200.000 Total solver iterations: 5 Variable Value Reduced Cost Y13 1.000000 0.000000 Y14 0.000000 400.0000 Y25 0.000000 450.0000 Y56 0.000000 100.0000 Y57 0.000000 100.0000 Y58 0.000000 500.0000 Y68 1.000000 0.000000 Y78 0.000000 200.0000 X2 5.00

35、0000 0.000000 X1 0.000000 0.000000 X3 9.000000 0.000000 X4 13.00000 0.000000 X5 9.000000 0.000000 X6 30.00000 0.000000 X7 34.00000 0.000000 X8 49.00000 0.000000,作业(1,3)B 压缩一天的工期，作业(6,8)k压缩1天的工期，这样可在49天完工，需要多花1200元。,同前的两问的模型可编程求出相应的关键路径、各作业的最早开工时间和最迟开工时间。程序略计算结果：作业(i,j) 最早开工时间和最迟开工时间A (1,2) 0, 0G (5,

36、6) 9, 9B (1,3) 0, 0H (5,8) 9, 14C (1,4) 0, 4I (5,7) 9, 9D (3,4) 9, 12J (7,8) 34, 34E (2,5) 5, 6K (6,8) 30, 30F (4,6) 13, 15,关键路线：,问题4的建模与求解,设tij是完成作业(i,j)的实际时间（是一随机变量）最乐观的估计值(a)，最悲观的估计值(b)，最可能的估计值(m)设T为最短工期，d为规定工期。模型算法：计算出各作业时间的期望与方差；计算出关键路径；计算关键路径的期望与方差的估计值；利用分布函数psn(x)计算完成作业的概率与完成整个项目的时间。,LINGO程序,

37、sets: events/1.8/: d; operate(events, events)/ ! A B C D E 0 F G H I 0 J K; 1,2 1,3 1,4 3,4 2,5 3,5 4,6 5,6 5,8 5,7 6,7 7,8 6,8 /: a, m, b, et, dt, x;endsetsdata: a = 3 8 8 2 3 0 8 18 26 18 0 12 11; m = 5 9 11 4 4 0 16 20 33 25 0 15 21; b = 7 16 14 6 5 0 18 28 52 32 0 18 25; d = 1 0 0 0 0 0 0 -1; li

38、mit = 52;enddata,for(operate: et = (a+4*m+b)/6; dt = (b-a)2/36; );max = Tbar;Tbar = sum(operate: et*x);for(events(i): sum(operate(i,j): x(i,j) - sum(operate(j,i): x(j,i) =d(i););S2=sum(operate: dt*x);p=psn(limit-Tbar)/S);psn(days-Tbar)/S) = 0.95;,计算结果,Variable Value Reduced Cost LIMIT 52.00000 0.000000 TBAR 41.00000 0.000000 S 2.185814 0.000000 P 0.9999998 0.000000 DAYS 369.3934 0.000000,完成作业52天关键路线的期望时间为41天，标准差为2.185852天完成全部作业的概率0.9999998,