网络优化 钢管运输_.ppt

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

2、划、非光滑优化等. 离散优化： 网络规划、整数规划、动态规划 等. 不确定规划： 随机规划、模糊规划等.,1. 网 络 优 化 简 介,网络: 电话通信网络 运输服务网络 能源和物质分派网络 计算机信息网络等等 网络优化就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益 .,网络：数学模型- 图 网络优化就是研究与（赋权）图有关的最优化问题,网络优化问题的例子,例1.2 运输问题(Transportation Problem) 某种原材料有M 个产地，现在需要将原材料从产地运往N 个使用这些原材料的工厂. 假定M 个产地的产量和N 家工厂的需要量已知，单位产品从任一产地到

3、任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？,例1.1 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来， 使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市. 假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？,例1.3 中国邮递员问题(CPP-Chinese Postman Problem) 一名邮递员负责投递某个街区的邮件. 如何为他(她)设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国复旦大学 管梅谷教授1960年首先提

4、出的，所以国际上称之为中国邮递员问题.,例1.4 旅行商问题 (TSP-Traveling Salesman Problem) 一名推销员准备前往若干城市推销产品. 如何为他(她)设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这一问题的研究历史十分悠久，通常称之为旅行商问题.,上述问题特点： （1）与图形有关，或易于用图形方式表示 （2）优化问题：从若干可能的安排或方案中寻求某种意义下的最优安排或方案,旅行商问题的枚举求解 设城市数为30个 所有可能的路线有30！种 设计算机每秒进行100亿（=1010)次枚举,计算机计算花费时间： 30! / 1010 2.65*

5、1032/1010= 2.65*1022 (秒) = 2.65*1022 / (365*24*60*60) (年) 8.4*1013 (年),2 图与网络,2.1定义 一个图(Graph ) 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中的每条边赋予一个方向. (有序对; 边称弧） 赋权图: 对图G中的

6、每条边赋予一个或多个实数，得到的图. 网 络:有向赋权图称为有向网络,简称网络 (Network).,例2.1,有向图 G=(V，A)，,顶点集,边集,边,赋权图: 对图G中的每条边赋予一个或多个实数，得到的图.,网 络:有向赋权图称为有向网络,简称网络 (Network).,图的阶(Order) :顶点的个数. 顶点的度（Degree）:与顶点相连的边数. (出度,入度). 环:端点相同的边称为环. 相邻点: 有边联结的两个顶点称为相邻的顶点. 相邻边: 有一个公共端点的边. 多重边: 若一对顶点之间有两条以上的边联结，则这些边称为重边 简单图(Simple Graph): 没有环、且没有多

7、重边的图.,2.2基本概念,链：由两两相邻的点及其相关联的边构成的点边序列；如： v0 , e1 , v1 , e2 , v2 , e3 , v3 , , vn-1 , en , vn ； v0 , vn 分别称为链的起点和终点 . 路 (Path):图的不包含重复顶点的链. (有向路) 圈(Cycle): 起点和终点重合的路.(有向圈) 连通图(Connected Graph) ： 图中任意两点之间至少有一 条路，否则称作不连通图。 树(tree): 无圈连通图称为树,无圈图称为森林.,Kn的边的数量为 n(n-1)/2,完全图(Complete Graph) ： 若图G的任意两个顶点间有且

8、只有一条边相连，则称其为完全图. n阶完全图记为Kn.,二分图(Bibartite Graph). 若图G=(V，E)的顶点集V可以表示成两个互不相交的非空子集S，T的并集，且使得G中每一条边的一个端点在S中，另一端点在T 中，则称G为二部图/二分图(Bibartite Graph). 当|S|=p，|T|=q，且S与T中任意两对顶点都相邻时，称G为完全二部图，记为Kp,q.,Kp,q的边的数量为 pq,子图(Subgraph): G=（V，A） 称为G的子图(Subgraph),图的支撑子图 (又称生成子图): 包含G 的所有顶点的子图.,2.3 图与网络的数据结构,(1) 邻接矩阵(Adj

9、acency Matrix)表示法,设 G=(V，A)是一个有向图. |V|=n，|A|=m,例,对于网络中的权，也可以用类似邻接矩阵的矩阵表示. 只是此时一条边所对应的元素不再是1，而是相应的权而已. 如果网络中每条边赋有多种权，则可以用多个矩阵表示这些权.,(2) 关联矩阵(Incidence Matrix)表示法,图G=(V，A)的关联矩阵B是如下定义的：B是一个 的矩阵，即,每行元素1的个数正好是对应顶点的出度， 每行元素-1的个数正好是对应顶点的入度.,在关联矩阵的所有元素中，只有2m个为非零元.,例,如果网络中每条弧赋有一个权，我们可以把关联矩阵增加一行, 把每一条弧所对应的权存贮

10、在增加的行中. 如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条弧所对应的权存贮在增加的行中.,(4) 邻接表 (Adjacency Lists)表示法,图的邻接表是图的所有节点的邻接表的集合; 而对每个节点，它的邻接表就是它的所有出边.,对于有向图G=（V，A），一般用A（i）表示节点i的邻接表，即节点i的所有出弧构成的集合或链表（实际上只需要列出弧的另一个端点，即弧的头）.,几点说明,（1）邻接表方法常用. 邻接表方法增加或删除一条边所需的计算工作量很少,（2）当网络不是简单图，而是具有多重边时，邻接矩阵法是不能采用的. 其他方法则可以推广到可以处理多重边的情形.,（

11、3）无向图处理类似. 如无向图的关联矩阵只含有元素0和+1. 在邻接表中，每条边会被存贮两次; 等等.,3 网络优化与整数规划的关系,例（续例1.2） 指派问题(Assignment Problem) 一家公司经理准备安排N名员工去完成N项任务，每人一项. 由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的. 如何分配工作方案可以使总回报最大？,许多网络优化问题可以用整数规划(IP)来建模,3.1整数线性规划(简称整数规划（IP）)的标准形式,，A是行满秩的，且,3.2 整数规划问题的求解,1 整数规划(IP)问题 松弛为 线性规划问题(LP) 2 分支定界法,IP的LP松

12、弛的最优解什么时候一定是整数解呢？,假设线性规划问题中等式约束个数等于决策变量个数(m=n), 则此时的等式约束构成一个线性方程组Ax=b.,如果方阵A为整数矩阵且b为整数向量, 则det(A)和det(Aj)都是整数. 如果还有det(A) = 1或-1, 则解x一定是整数向量.,定理3.1 设在线性规划问题（3.2）中A为整数矩阵，且A 满行秩，则下面三个条件等价： （1）对每个基矩阵B，其行列式det（B）=1或-1. （2）对任何整数向量b，其可行域 的每个极点都是整数向量. （3）对每个基矩阵B，其逆矩阵也是整数矩阵.,证明 略,3.3全么模矩阵,定义 如果一个矩阵A的任何子方阵的行

13、列式的值都等于0，1或-1，则称A是全么模的（TU：Totally Unimodular，又译为全单位模的），或称A是全么模矩阵.,定理3.2 （全么模矩阵的性质）下列命题等价： A是全么模矩阵. -A是全么模矩阵. AT是全么模矩阵. （A，A）是全么模矩阵. （A，I） ，（A，0）是全么模矩阵.,全么模矩阵的元素只能取0，1和-1.,A为全么模矩阵,整数向量b时的整数规划问题实际上等价于对应的LP松弛问题（单纯形算法）.,定理3.3 设A是由0，1和-1组成的矩阵，如果下面两个条件同时成立，则A为全么模矩阵. （1）A的每一列至多含有两个非零元素. （2）A的行可以分为A1，A2两个集合

14、，使得：如果A的一列中有两个符号不同的元素，则相应的两行在同一集合A1或A2中；如果A的一列中有两个符号相同的元素，则相应的两行分别位于两个集和A1和A2中.,充分条件,推论 （1）一个有向图的关联矩阵为全么模矩阵. （2）一个无向图的关联矩阵为全么模矩阵，当且仅当该图为二部图.,当采用整数规划来描述网络优化问题时，其约束矩阵一般是有向图的关联矩阵或它的简单变形，一般都是全么模矩阵. 因此可以认为，许多网络优化问题都是一类特殊的整数规划，其LP松弛与原问题有相同的最优解.,网络优化处于线性规划和整数规划的结合点上，或者说处于连续优化和离散优化（组合优化）的结合点上.,3.4 全么模阵与网络优化

15、的关系,例1：一个线路网络图，从A到E要修建一条石油管道，必须 在B、C、D处设立加压站。各边上的数为长度，现需要找一条路使总长度最短。,4.1最短路问题的例子和意义,许多实际问题都可以转化为最短路问题 其有效算法经常在其它网络优化问题中作为子算法调用,4.最短路问题(Shortest Path Problem),例2 计划评审技术, PERT(Project Evaluation 权为负的圈称为负圈; 权为0的圈称为零圈. 对一个有向圈， 它的权就是圈上所有弧上的权的和. 本章的圈一般都是指有向圈, 我们直接将正有向圈简称为“正圈”， 负有向圈简称为“负圈”， 零有向圈简称为“零圈”, 而“

16、无圈”指的是不存在有向圈.,s,t,xij 是变量, 当xij =1时，表示弧（i，j）位于s-t路上，当xij =0时，表示弧（i，j）不在s-t路上. wij 表示弧（i，j）上的权.,4.3 最短路问题的数学描述,关联矩阵是全么模矩阵，因此0-1变量可以松弛为区间0,1中的实数,不含负圈，变量直接松弛为所有非负实数,思考：为什么xij 可以不限定为0，1？,Bellman方程(最短路方程),一般情况下直接求解最短路方程是相当困难的.,定理5.1 对于只含正有向圈的连通有向网络，从起点s到任一顶点j都存在最短路，它们构成以起点s为根的树形图（称为最短路树（Tree of Shortest

17、Paths）或最短路树形图（Shortest Path Arborescence）长度可以由Bellman方程唯一确定.,最短路树（树形图）,4.4最短路算法,算法通过不断修改这些标号，进行迭代计算. 当算法结束时，距离标号表示的是从起点到该顶点的最短路长度.,(1) Dijkstra算法 (1959, 正费用网络） 基本思想： 对于V 中每一个顶点j，赋予两个数值（通常称为“标号”）： 1.距离标号u(j):记录的是从起点到该顶点的最短路长度的上界； 2.前趋标号p（j）:记录的是当起点s到该顶点j 的一条路长 取到该上界时，该条路中顶点j 前面的那个节点.,Dijkstra算法,STEP1

18、. 如果S=V, 则 为节点s到节点j的最短路路长(最短路可以通过数组p所记录的信息反向追踪获得), 结束.,STEP0. (初始化) 令S= ，=V， ；对V 中的顶点j(j s)令初始距离标号 .,STEP2. 从 中找到距离标号最小的节点i，把它从 删除，加入S. 对于所有从i出发的弧 , 若 ，则令 . 转STEP1.,一般费用网络,(2) Bellman - Ford算法 (Ford,1956),计算从起点到所有其它顶点的最短路: 相当于迭代法解Bellman方程,钢管订购与运输问题,问题： 要铺设一条 的输送天然气的主管道, 如图一所示(见下页)。经筛选后可以生产这种主管道钢管的

19、钢厂有 . 图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。 为方便计，1km主管道钢管称为1单位钢管。,一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂 在指定期限内能生产该钢管的最大数量为 个单位，钢管出厂销价1单位钢管为 万元，如下表： 1单位钢管的铁路运价如下表：,160,150,155,160,155,155,160,3000,2000,2000,2000,1000,800,800,7,6,5,4,3,2,1,i,32,29,26,23,20,运

20、价(万元),451500,401450,351400,301350,300,里程(km),1000km以上每增加1至100km运价增加5万元。,（1）请制定一个主管道钢管的订购和运输计划，使总费用最小(给出总费用)。 （2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。 （3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。,问题：,公路运输费用为1单位钢管每公里0.1万元（不足整公里部

21、分按整公里计算）。 钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。,1.购买、运输钢管 都是整单位。 2. 沿铺设主管道已有公路或者有施工公路。 3.钢厂先将钢管运输到各个结点Aj,再由Aj向各个方向运输。 4. 在主管道上，每公里卸1单位的钢管。 5.在求解钢厂的价格对总价的影响时，认为钢管的单价只会在一个小范围内变化，在求解钢厂的生产上限对总价的影响时，亦是如此。,一 基本假设,二.问题分析,将钢管先运输到各个结点（运输费用），然后再将钢管从各个结点运 往具体铺设地点（铺设费用).,钢管从钢厂si到运输结点Aj的费用包括钢管的销价钢管的铁路运输费用和钢管的公路运输费用。在费

22、用最小时，对钢管的订购和运输进行分配，可得出问题的最佳方案。,符号说明： Si：第个钢厂；i=1,.7 si：第个钢厂的最大产量； i=1,.7 Aj ：输送管道（主管道）上的第j个点； j=1,.15 Ajj+1; 相邻点Aj与Aj+1之间的距离； pi：第i个钢厂1单位钢管的销价； i=1,.7 xij：钢厂Si向第j个点运输的钢管量； i=1,.7, j=1,.15 yj：运输点Aj向Aj+1点方向铺设的钢管量；j=1,.14 (t1=0) aij：1单位钢管从钢厂Si运到点Aj的最少总费用，即公路运费铁路运费和钢管销价之和； i=1,.7,j=1,.15 bj ： 公路和铁路的相交点；

23、 j=1,.17 ：,三模型的建立与求解 1 问题一的订购和运输方案 1) 单位钢管从钢厂Si运到点Aj的最少总费用aij 根据图 一，借助求最短路的方法(Djikstra算法) 求aij， 方法一 赋权图： 赋边权：(K, L, V) K: K=1(铁路）， K= （公路） L：路程 V: f(K,L) 阶段运费 方法二 由于钢管从钢厂运到运输点要通过铁路和公路运输，而铁路运输费用是分段函数，与全程运输总距离有关。又由于钢厂直接与铁路相连，所以可先求出钢厂Si到铁路与公路相交点bj的最短路径(借助求最短路的方法) 。,依据钢管的铁路运价表，算出钢厂Si到铁路与公路相交点bj的最小铁路运输费用

24、，并把该费用作为边权赋给从钢厂Si到bj的边。 再将与bj相连的公路、运输点Aj及其与之相连的要铺设管道的线路（也是公路）添加到图上，根据单位钢管在公路上的运价规定，得出每一段公路的运费，并把此费用作为边权赋给相应的边。以S1为例得图四,图四 钢管从钢厂S1运到各结点的费用权值图,根据图 四，借助求最短路的方法求得aij,求出单位钢管从S1到Aj的最少运输费用(单位：万元)依次为： 170.7，160.3，140.2，98.6，38，20.5，3.1，21.2， 64.2， 92， 96，106，121.2，128，142 加上单位钢管的销售价，得出从钢厂S1购买单位钢管运输到点Aj的最小费用(单位：万元)依次为： 330.3，320.3，300.2，258.6，198，180.5，163.1，181.2， 224.2，252，256，266，281.2，288，302 同理，可求出从钢厂S2,S7购买单位钢管运输到点A7的最小总费用,从各钢厂购买单位钢管运输到点Aj的最小总费用(aij),2)建立模型 运输总费用可分为两部分： 运输总费用=钢厂到各结点的运输费用+铺设费用。 运输费用： 设结点Aj向钢厂Si订购xij单位钢管，则钢管从钢厂运到运输点所需的费用为ai