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

《数学建模网络优化课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？网络优化问题的例子131325463421246赋权图“直接方式”：总经理直接传达；“接力方式”：总经理只给某些部门经理打电话，而让这些得到信息的部门经理打电话将信息进一步传达给其他某些部门经理，依此类推，最后将信息传达到所有部门经理.如何决定传达信息的途径使得信息快速准确？信息传播是有向的，有一个“根”。信息传播途径（忽略方向时）是一棵树。以上结构称为树形图，上面这样一类问题称为最小树形图问题.例：信息传

3、播最小树形图例最短路问题一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地.从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路.网络优化问题的例子AF566744513BEDC甲地乙地实例例：工程项目统筹问题大型复杂工程项目往往被分成许多子项目,子项目之间有一定的先后顺序(偏序)要求,每一子项目需要一定的时间完成.网络的每条弧表示一个子项目,如果以弧长表示每一子项目需要的时间,则最早完工时

4、间对应于网络中的最长路(关键路线).工程上所谓的关键路线法.项目网络不含圈（其最长路问题和最短路问题都是可解的）(开始)AF(结束)566744513BEDC实例例：最大流/最小费用流从甲地到乙地的公路网纵横交错，每天每条路上的通车量有上限.从甲地到乙地的每天最多能通车多少辆?考虑每条路上的通行成本,如何确定某个车队的具体行车路线,使总成本最小?(甲)AF(乙)566744513BEDC例：运输问题(TransportationProblem)某种原材料有M个产地，现在需要将原材料从产地运往N个使用

5、这些原材料的工厂.假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？网络优化问题的例子ST特殊的最小费用流问题（二部图,

6、S

7、=M,

8、T

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

10、S

11、=

12、T

13、=N）例

14、：匹配问题(MatchingProblem)在一次有m个大学毕业生和n家公司参加的供需见面会上，每个毕业生愿意加入到若干家公司中的一家工作，而每个公司愿意接收若干毕业生中的一人到公司工作.那么，最后最多有多少人可以在这次供需见面会上找到工作（即最多有多少家公司可以在这次供需见面会上招聘到员工）？如果每个毕业生到每一家公司工作将会产生的效益不同，那么，为了使得最后产生的总效益最大，最多有多少人可以在这次供需见面会上找到工作？网络优化问题的例子例：中国邮递员问题一名邮递员负责投递某个街区的邮件.如何设计

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

16、汇市场上，将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.