网络优化 钢管运输

《网络优化 钢管运输》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、网络优化NetworkOptimization理学院数学学科赫孝良与优化有关的数学建模竞赛题逢山开路（1994）飞行管理（1995）洗衣机节水最优捕鱼策略（1996）工件的截断切割（1997）投资收益和风险灾情巡视路线（1998）自动化车床管理（1999）钢管订购计划（2000）基金使用计划（2001）车灯线光源的优化设计（2002）露天矿生产的车辆安排（2003）奥运会临时超市网点设计（2004）DVD在线租赁（2005）艾滋病疗法的评价及疗效的预测（2006）乘公交，看奥运（2007）最优化包括：连续优化：线性规划、二次规划、非线性规划、多目标规划、非光滑优化等.离散优化：网络规划、整数

2、规划、动态规划等.不确定规划：随机规划、模糊规划等.1.网络优化简介网络实例电话通信网络运输服务网络能源和物质分派网络计算机信息网络等等网络优化就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益.网络的数学模型——图网络优化就是研究与（赋权）图有关的最优化问题网络优化问题的例子例1.2运输问题(TransportationProblem)某种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工厂.假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？例1.1公路连接问题某一地区有若干个

3、主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市.假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？例1.3中国邮递员问题(CPP-ChinesePostmanProblem)一名邮递员负责投递某个街区的邮件.如何为他(她)设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？(复旦大学管梅谷教授1960年提出)，国际上称之为中国邮递员问题.例1.4旅行商问题(TSP-TravelingSalesmanProblem)一名推销员准备前往若干城市推销

4、产品.如何为他(她)设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这一问题的研究历史十分悠久，通常称之为旅行商问题.上述问题的特点：（1）与图形有关，或易于用图形方式表示.（2）优化问题：从若干可能的方案中寻求某种意义下的最优方案.旅行商问题的枚举法求解计算机计算花费时间：30!/1010≈2.65*1032/1010=2.65*1022(秒)=2.65*1022/(365*24*60*60)(年)>8.4*1013(年)枚举法求解是不可行的！设城市数为30个所有可能的路线有30！种设计算机每秒进行100亿（=1010)次枚举2图与网络2.1定义一个图(Graph

5、)G是由一个非空有限集合V(G)和V(G)中某些元素的无序对集合A(G)构成的二元组，记为G=(V(G)，A(G)).其中V(G)称为图G的结点集，V(G)中的每一个元素称为该图的一个结点或顶点；A(G)称为图G的边集，A(G)中的每一个元素称为该图的一条边.记号V(G)和A(G)简记为V和A，而记图G=（V，A）.有向图:对图G中的每条边赋予一个方向.(有序对;边称弧）例2.1有向图G=(V，A)，顶点集边集边赋权图:对图G中的每条边赋予一个或多个实数，得到的图.网络:有向赋权图称为有向网络,简称网络(Network).ABP1P2P3Q1Q2Q3456467112243例2.2A，B城间

6、道路行车时间图图的阶(Order):顶点的个数.顶点的度（Degree）:与顶点相连的边数.(出度,入度).环:端点相同的边称为环.相邻点:有边联结的两个顶点称为相邻的顶点.相邻边:有一个公共顶点的边.多重边:若一对顶点之间有两条以上的边联结，则这些边称为多重边．简单图(SimpleGraph):没有环、且没有多重边的图.2.2基本概念链：由两两相邻的点及其相关联的边构成的点边序列；如：v0,e1,v1,e2,v2,e3,v3,…,vn-1,en,vn；v0,vn分别称为链的起点和终点.路(Path):图的不包含重复顶点的链.(有向路)圈(Cycle):起点和终点重合的路.(有向圈)连通图(

7、ConnectedGraph)：图中任意两点之间至少有一条路，否则称作不连通图。树(tree):无圈连通图称为树,无圈图称为森林.链：路：Kn的边的数量为n(n-1)/2完全图(CompleteGraph)：若图G的任意两个顶点间有且只有一条边相连，则称其为完全图.n阶完全图记为Kn.二分图(BibartiteGraph).若图G=(V，E)的顶点集V可以表示成两个互不相交的非空子集S，T的并集，且使得G中每