[理学]2010建模培训网络优化数学建模培训.ppt

数学建模 主讲 薛长虹 E-mail 地址: chxue180@126.com QQ: 315165 数学建模网上之家 薛老师主页： 《长虹雪苑》之数学建模天地 http:// chxue . 全国数学建模主委会主页： 电邮地址： chxue180@126.com chxue180@163.com chxue180@ chxue180@ chxue180@ 315165@ 网络优化的评注 许多实际问题可以直接用网络优化建模 许多实际问题可能用到网络优化建模 许多实际问题是网络优化的变种 网络优化问题通常可以用整数规划建模 西气东送（钢管运输）问题（CUMCM-2000B) 西气东送（钢管运输）问题（CUMCM-2000B) 二次规划（常用解法） 最小费用流问题？ （清华大学队，获网易杯） 线性模型（网络规模较大，有现成算法） 非线性模型（网络规模较小，需要自己设计算法） 基本问题 ---- 最小运费矩阵的计算 两种运输方式（铁路／公路）混合最短路问题 是普通最短路问题的变种，需要自己设计算法 铁路／公路混合运输最短路问题 最小运费矩阵算法（四川大学/清华大学等队） Dijkstra算法 或 Floyd-Warshall算法 铁路最短路问题 最短路 ==〉铁路最小运费矩阵 公路最短路问题 最短路 ==〉公路最小运费矩阵 铁路/公路混合运输最短路问题 铁路/公路混合运输网络 最短路 ==〉铁路/公路混合运输最小运费矩阵 * * 网 络 优 化 简 介 网络：网络社会 ---- 计算机信息网络？ 电话通信网络 运输服务网络 能源和物质分派网络 人际关系网络 等等 网络优化就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益 网络(Network)：数学模型、数学结构 ---- 图 优化(Optimization) : 从若干可能的方案中寻求某种意义下的最优方案 与图论有联系，也有区别（侧重点不同） 网络优化就是研究与（赋权）图有关的最优化问题 图论： 图的性质 网络优化： 与（赋权）图有关的优化问题 组合数学 组合优化 网 络 优 化 简 介 图与网络 – 基本概念 图G=(V，A)，其中顶点集V= 弧集A= 弧 例： 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来， 使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市. 假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？ 网络优化问题的例子 1 1 3 2 5 4 6 3 8 5 2 4 7 最小(生成)树 也称为 最小(支撑)树 “直接方式”：总经理直接传达； “接力方式”：总经理只给某些部门经理打电话，而让这些得到信息的部门经理打电话将信息进一步传达给其他某些部门经理，依此类推，最后将信息传达到所有部门经理. 如何决定传达信息的途径？ 信息传播是有向的，有一个“根”。 信息传播途径（忽略方向时）是一棵树。 以上结构称为树形图，上面这样一类问题称为最小树形图问题. 例： 信息传播 最小树形图 – 例 例 最短路问题（SPP-Shortest Path Problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地. 从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路. 网络优化问题的例子 A F 5 6 6 7 4 4 5 1 3 B E D C 例：计划评审技术, (又称网络计划技术或统筹法) 大型复杂工程项目(Project)往往被分成许多子项目,子项目之间有一定的先后顺序(偏序)要求, 每一子项目需要一定的时间完成. PERT网络的每条弧表示一个子项目,如果以弧长表示每一子项目需要的时间,则最早完工时间对应于网络中的最长路 (关键路线). 工程上所谓的关键路线法(CPM: Critical Path Method)基本上也是计划评审技术的一部分. 项目网络不含圈（其最长路问题和最短路问题都是可解的） (开始) A F (结束) 5 6 6 7 4 4 5 1 3 B E D C 例：最大流 / 最小费