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

《数学建模网络优化ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模网络优化ppt课件.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、a6a图图G=(V，A)，其中顶点集其中顶点集V V= = 弧集弧集A A= = 弧弧,54321vvvvv,654321aaaaaa),(211vva ),(212vva ),(323vva ),(434vva ),(145vva ),(336vva 例：例： 公路连接问题公路连接问题某一地区有若干个主要城市，现准备修建高速公路某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，把这些城市连接起来， 使得从其中任何一个城市使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市都可以经高速公路直接或间接到达另一个城市. 假假定已经知道了任意两个城市之间修建高速公路的成定已经

3、知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？使得总成本最小？ 网络优化问题的例子网络优化问题的例子 131325463421246赋权图赋权图“直接方式直接方式”：总经理直接传达；：总经理直接传达；“接力方式接力方式”：总经理只给某些部门经理打电话，而让这些：总经理只给某些部门经理打电话，而让这些得到信息的部门经理打电话将信息进一步传达给其他某些部得到信息的部门经理打电话将信息进一步传达给其他某些部门经理，依此类推，最后将信息传达到所有部门经理门经理，依此类推，最后将信息传达到所有部门经理. 如何

4、决定传达信息的途径使得信息快速准确？如何决定传达信息的途径使得信息快速准确？ 信息传播是有向的，有一个信息传播是有向的，有一个“根根”。信息传播途径（忽略方向时）是一棵树。信息传播途径（忽略方向时）是一棵树。以上结构称为树形图，上面这样一类问题称为最小树形图问题以上结构称为树形图，上面这样一类问题称为最小树形图问题. 例：例： 信息传播信息传播最小树形图最小树形图 例例 最短路问题最短路问题一名货柜车司机奉命在最短的时间内将一车货物从一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地甲地运往乙地. 从甲地到乙地的公路网纵横交错，因此有多从甲地到乙地的公路网纵横交错，因此有多种行车路线，这

5、名司机应选择哪条线路呢？假设货柜车的种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行运行速度是恒定的速度是恒定的，那么这一问题相当于需要找到一条从，那么这一问题相当于需要找到一条从甲地到乙地的最短路甲地到乙地的最短路.网络优化问题的例子网络优化问题的例子 A A F F 5 5 6 6 6 6 7 7 4 4 4 4 5 5 1 1 3 3 B B E E D D C C 甲地甲地乙地乙地实例实例例：工程项目统筹问题例：工程项目统筹问题大型复杂工程项目往往被分成许多子项目大型复杂工程项目往往被分成许多子项目, ,子项目之间有子项目之间有一定的先后顺序一定的先后顺序( (偏序偏序) )要求

6、要求, , 每一子项目需要一定的时间完成每一子项目需要一定的时间完成. . 网络的每条弧表示一个子项目网络的每条弧表示一个子项目, ,如果以弧长表示每一子项目需要如果以弧长表示每一子项目需要的时间的时间, ,则最早完工时间对应于网络中的最长路则最早完工时间对应于网络中的最长路 ( (关键路线关键路线). ). 工程上所谓的关键路线法工程上所谓的关键路线法. .项目网络不含圈（其最长路问题和最短路问题都是可解的）项目网络不含圈（其最长路问题和最短路问题都是可解的） ( (开始开始) A ) A F (F (结束结束) ) 5 5 6 6 6 6 7 7 4 4 4 4 5 5 1 1 3 3 B

7、 B E E D D C C 实例实例例：最大流例：最大流 / / 最小费用流最小费用流从甲地到乙地的公路网纵横交错，每天每条路上从甲地到乙地的公路网纵横交错，每天每条路上的通车量有上限的通车量有上限. 从甲地到乙地的每天最多能通车多少从甲地到乙地的每天最多能通车多少辆辆?考虑每条路上的通行成本考虑每条路上的通行成本, ,如何确定某个车队的如何确定某个车队的具体行车路线具体行车路线, ,使总成本最小使总成本最小? ? ( (甲甲) A ) A F (F (乙乙) ) 5 5 6 6 6 6 7 7 4 4 4 4 5 5 1 1 3 3 B B E E D D C C 例：例： 运输问题运输问

8、题(Transportation Problem)某种原材料有某种原材料有M个产地，现在需要将原材料从产地运往个产地，现在需要将原材料从产地运往N个个使用这些原材料的工厂使用这些原材料的工厂. 假定假定M个产地的产量和个产地的产量和N家工厂的家工厂的需要量已知，单位产品从任一产地到任一工厂的的运费已需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？知，那么如何安排运输方案可以使总运输成本最低？ 网络优化问题的例子网络优化问题的例子 ST特殊的最小费特殊的最小费用流问题用流问题（二部图（二部图,|S|=M, |T|=N）例：例： 指派问题指派问题(A

9、ssignment Problem)一家公司经理准备安排一家公司经理准备安排N名员工去完成名员工去完成N项任务，项任务，每人一项每人一项. 由于各员工的特点不同，不同的员工去由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的完成同一项任务时所获得的回报是不同的. 如何分如何分配工作方案可以使总回报最大？配工作方案可以使总回报最大？ 网络优化问题的例子网络优化问题的例子 ST特殊的最小特殊的最小费用流问题费用流问题（二部图，（二部图，|S|=|T|=N）例：匹配例：匹配问题问题(Matching Problem)在一次有在一次有m个大学毕业生和个大学毕业生和n家公司参加的供需

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

11、最后产生的总效益最大，最多有多少人可以在这次供需见面会上找到工作？以在这次供需见面会上找到工作？网络优化问题的例子网络优化问题的例子 例：中国邮递员问题例：中国邮递员问题一名邮递员负责投递某个街区的邮件一名邮递员负责投递某个街区的邮件. . 如何如何设计一条最短的投递路线设计一条最短的投递路线( (从邮局出发，经过投递从邮局出发，经过投递区内每条街道至少一次，最后返回邮局区内每条街道至少一次，最后返回邮局) )？由于这？由于这一问题是我国学者管梅谷教授一问题是我国学者管梅谷教授19601960年首先提出的，年首先提出的，所以国际上称之为所以国际上称之为中国邮递员问题中国邮递员问题. . 网络优

12、化问题的例子网络优化问题的例子 例：例：旅行商问题旅行商问题(TSP-Traveling Salesman Problem)一名推销员准备前往若干城市推销产品一名推销员准备前往若干城市推销产品. 如何为他如何为他(她她)设计一条最短的旅行路线设计一条最短的旅行路线(从驻地出发，经过每个城市从驻地出发，经过每个城市恰好一次，最后返回驻地恰好一次，最后返回驻地)？这一问题的研究历史十分悠久，？这一问题的研究历史十分悠久，通常称之为通常称之为旅行商问题旅行商问题. 网络优化问题的例子网络优化问题的例子 BACDEFGHI例：例：套汇（套汇（Arbitrage）问题）问题 在外汇市场上，将在外汇市场上

13、，将1单位的某种货币通过多次兑单位的某种货币通过多次兑换，获得多于换，获得多于1单位的同种货币，称为套汇。如：单位的同种货币，称为套汇。如：1单位的单位的A货币货币(兑换兑换) 46.4单位单位B货币货币1单位的单位的B货币货币(兑换兑换) 2.5单位单位C货币货币 1单位的单位的C货币货币(兑换兑换) 0.0091单位单位A货币货币 则则: 1单位的单位的A货币货币 (通过三次兑换获得通过三次兑换获得)46.42.50.0091=1.0556单位单位A货币货币网络优化问题的例子网络优化问题的例子 可以变成检测负圈的可以变成检测负圈的问题问题现在假设给定了若干种货币及其两两之间的兑现在假设给定

14、了若干种货币及其两两之间的兑换率，请你帮助找到换率，请你帮助找到一种一种套汇方式（或判定该外汇市套汇方式（或判定该外汇市场上不存在套汇的可能）。场上不存在套汇的可能）。 套汇套汇: 46.42.50.0091=1.0556 1两边取倒数两边取倒数(乘积乘积1)，再取对数（求和，再取对数（求和= 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

15、) x8 - x6 = 2014) x8 - x7 = 15end Objective value: 51.00000 Total solver 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计算结果计算结果问题二的建模与求解问

16、题二的建模与求解目标函数：作业的开始时间尽量的早目标函数：作业的开始时间尽量的早 Hiix Gjitxxsjiijij ,引进作业对应弧上的松弛变量引进作业对应弧上的松弛变量sij，且，且 这样就可以得到作业的最迟开工时间。当最这样就可以得到作业的最迟开工时间。当最早开工时间与最迟开工时间相同时，就得到项目早开工时间与最迟开工时间相同时，就得到项目的关键路径。的关键路径。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

17、,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 Reduced 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

18、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 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(

19、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的最早开工时间是的最早开工时间是5x(3)=10，D的最早开工时间是的最早开工时间是10 x(8)=51，总最短工期是，总最短工期是51天天松驰变量松驰变量s(i,j)0，说明还有剩余时间，说明还有剩余时间，作业作业(i,j)的开工时间还可以推迟，例的开工时间

20、还可以推迟，例如如s(1,4)=3，作业，作业C可推迟可推迟3天。又由天。又由于于s(4,6)=2，后继的作业，后继的作业F可推迟可推迟2天，天，所以作业所以作业C最多可推迟最多可推迟5天。天。关键路线：关键路线：求关键路线的最长路线模型求关键路线的最长路线模型 设设xij为为0-1变量，当作业变量，当作业(i,j)位于关键路线上取位于关键路线上取1，否，否则取则取0，数学模型为：，数学模型为： Gjiijijxt),(maxGjixniniixxtsjiGjijjiGjijij ),(, 10, 10111.,),(1),(1或或sets: events/1.8/: d; operate(e

21、vents, 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;endsetsdata: 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.

22、 Objective value: 51.00000 Total solver iterations: 0 Variable Value Reduced Cost X( 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(

23、 5, 8) 0.000000 6.000000 X( 5, 7) 0.000000 1.000000 X( 6, 7) 0.000000 5.000000 X( 7, 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为要求完成的天数，为要求完成的

24、天数，1为最初事件，为最初事件，n为最为最终事件。终事件。建立模型：建立模型： Gjiijijyc),(minHiGjimtydxxHiGjityxxtsijijijnijijij ,),(,0,),(,.1LINDO程序程序min 700y13 + 400y14 + 450y25 + 600y56 + 300y57 + 500y58 + 500y68 + 400y78 subject to2) x2 - x1 = 53) x3 - x1 + y13 = 104) x4 - x1 + y14 = 115) x5 - x2 + y25 = 46) x4 - x3 = 47) x5 - x3 =

25、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 = 49endsub y13 2sub y14 3 sub y25 1sub y56 5sub y57 3sub y58 5sub y68 4sub y78 3计算结果计算结果Global optimal solution found. Objective value: 1200.000 Tot

26、al 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.000000 0.000000 X1 0.000000 0.000000 X3 9.000000 0.000000 X4 13.000

27、00 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) 最早开工时间和最迟开工时间最早

28、开工时间和最迟开工时间A (1,2) 0, 0G (5,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为规定工

29、期。为规定工期。模型算法：模型算法：计算出各作业时间的期望与方差；计算出各作业时间的期望与方差；计算出关键路径；计算出关键路径；计算关键路径的期望与方差的估计值；计算关键路径的期望与方差的估计值；利用分布函数利用分布函数psn(x)计算完成作业的计算完成作业的概率与完成整个项目的时间。概率与完成整个项目的时间。 关键路线关键路线),(jiijtT 关键路线关键路线),()()(jiijtETET 64ijijijijbmatE 362ijijijabtD 关键路线关键路线),(2)()(jiijtDTDS STddTPLINGO程序程序sets: events/1.8/: d; operate

30、(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; limit = 52;enddatafor(operate:

31、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