资源描述：
《运筹优化问题及算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、网络优化问题及算法简介胡智全华中师范大学数学与统计学学院.Hu_zhiq@yahoo.com.cn数学建模题目类型：B.运筹学1994B锁具装箱1998B灾情巡视路线2000B钢管订购和运输2001B公交车调度2003B露天矿生产的车辆安排2007B乘公交，看奥运2008?汶川地震图论的起源：Konigsberg七桥问题七桥问题：能否从某块陆地出发，经过每座桥一次且仅一次，最后回到原出发地？Euler：陆地→点，两点间的桥梁→线七桥问题→图中Euler圈问题。图与网络图：有序对（V，E），V：顶点集，E：边集。赋权图G=（V，E，w),w:E→R+点→人，边→两个人相互认识点→球
2、队，有向边(x,y)→x胜y点→城市，边→城市间的道路，w(e)→道路e的长度，修建道路e的费用等。图与网络中的传统优化问题1.最短路问题实例:边赋权图G=(V,E,w),点s,t∈V可行解:G中所有s-t路目标：极小化路上所有边的权和.算法：Dijkstra1959图与网络中的传统优化问题1.最短路问题：Dijkstra算法图与网络中的传统优化问题2.最小支撑树问题2.最小支撑树问题----破圈法(Rosenstiehl1967)2.最小支撑树问题----避圈法(Rosenstiehl1967)图与网络中的传统优化问题3.最大匹配问题实例:边赋权图G=(V,E,w)可行解:G中
3、的边独立集M目标：极小化M上所有边的权和.算法：Edmonds1965图与网络中的传统优化问题4.中国邮路问题中国邮路问题：管梅谷1960一个邮递员送信时，要走遍他所负责的每条街道，完成送信任务后回到邮局.他应按什么样的路线走，使走的总里程最短?实例:边赋权图G=（V，E，w)可行解:通过G中所有边的圈（未必是简单的）目标：极小化圈上所有边的权和.4.中国邮路问题算法：Edmonds,Johnson1973图与网络中的传统优化问题5.货郎问题货郎问题：一个推销员要到若干个城市推销货物，然后回到出发点.他应该如何选择旅行路线，使每个城市通过一次且仅一次，并且总的里程最短?实例:边赋
4、权图G=(V,E,w)可行解:通过G中所有顶点一次且仅一次的圈目标：极小化圈上所有边的权和.近似算法：两边交换算法、三边交换算法、(欧氏距离下)1.5近似算法5.货郎问题：(欧氏距离下)1.5近似算法FindaMSTofG.SayT.FindaminimumcostperfectMatchingM,onthesetofodd-degreeverticesofG.AddMtoTandobtainanEuleriangraphM∪T.LetμbeitsEuler-tourOutputthetourthatvisittheverticesofGintheorderoftheirfirs
5、tpearanceinμ.例：通讯网络中的优化问题1.经典最小Steiner树问题问题：给定平面上若干个点，如何将它们连接起来使得连线长度最短？解的结构：该问题的解一定有树的结构(Steiner树)，而且可能会引入一些新的点(Steiner点)例：经典最小Steiner树问题定理（M.R.Gareyetal,1979）最小Steiner树问题是NP-难解的.定理（J.B.Kruskal,1956;R.C.Prim,1967）最小生成树问题是多项式时间内可解的.定理（D.-Z.Duetal,1979）最小生成树与最小Steiner树权重之比不超过通讯网络中的优化问题；2.网络上的S
6、teiner树问题实例:边赋权图G=(V,E,w)和顶点集合的一个子集S.可行解:连接集合S上所有顶点的树T(Steiner树).目标：极小化树T上所有边的权和.应用背景：在通讯服务中经常需要把信息从一个源点传到多个收点，即多播传输(multicast),如有线电视服务（vido-on-demand）,或者要把一组点联接起来（groupcommunication）,如电视/电话会议（tele-conference）.这里的核心问题就是如何把这些点连接起来.定理（M.R.Gareyetal,1979）网络上的最小Steiner树问题是NP-难解的.通讯网络中的优化问题；3.最少St
7、einer点的Steiner树问题问题:给定平面上若干个点和一个正实数R，如何将它们连接起使每段长度不超过R且所引入的Steiner点最少.应用背景：1)在通讯网络的具体设计中，我们通常还要考虑其它实际因素.例如：如果连接两点的通讯线路太长，那么信号在传输过程中会有所衰竭.一个解决方法就是在长线路中放置信号放大器(amplifier).很自然地产生了一个组合优化问题:就是如何设计网络使得所需要的信号放大器最少？2)消防车、战备仓库的选址动态规划动态规划(DynamicProgra
