动态规划-图论.doc

1动态规划模型AB1B2C1C2C3D1D2E536337263871如图所示，给定一个线路网络，两点之间连线上的数字表示两点间距离，试求一条从A到E的路线，使总距离为最短。Mattlab求解：首先利用Excel建立两个工作表edge和n分别存储图的上三角阵和顶点数量。其中edge=999995299999999999999999999999999999999999999999999937999999999999999999999999999999999999999963999999999999999999999999999999999999999999999699999999999999999999999999999999999999993899999999999999999999999999999999999999991999999999999999999999999999999999999999999999399999999999999999999999999999999999999997999999999999999999999999999999999999999999999n=9,然后在Matlab调入以上数据。同时将自编的动态规划软件“dynamic.m”调入当前目录之中，在Matlab命令窗口输入dynamic,回车后则在窗口显示出路径Path和距离distance2最小生成树253147650604565524050703042例1 某工厂要架设局域网联通工厂各个部门。已知工厂有7个部门，各个部门间铺设网线的距离如上图所示，计算出铺设网线的最短距离。Matlab的算法： 首先，将上图的邻接矩阵存储为G,顶点数存储为N；即：G=99999506099999999999999999999509999999999654099999999996099999999995299999999994599999655299999503042999994099999509999970999999999999999999993070999999999999999999994542999999999999999N=7,然后调入到Matlab命令窗口中，另外将自编程序prim.m存放到当前目录中，最后，输入prim后回车。打开变量result，即可看见最小生成树的连接方式。 例2 某六个城市之间的道路网如下图所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。v5v6v2v4627535441V1v3 3最短路例3 如下图所示的交通网络，边上的权重代表城市之间的距离，求城市1到其他城市的最短路径。12354101003010502060Matlab的算法： 首先，将上图的邻接矩阵存储为G,顶点数存储为N；即：G=999991099999301009999999999509999999999999999999999999999991099999999992099999999999999999999999996099999N=5，然后调入到Matlab命令窗口中，另外将自编程序dijkstra.m存放到当前目录中，最后，输入dijkstra后回车。打开变量path，即可看见最最短路的连接方式。例4: 如下图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交通网到达v8，要寻求是总路程最短的线路。v6v4v2v8v7v963623410231262410V1V3v54网络最大流VsV2V3VtV1V4(3,x1)(1,x3)(4,x4)(5,x7)(5,x2)(2,x6)(1,x5)(2,x8)如上图所示，每条弧相关的括号中，第一个数据表示该条弧的容量，第二个表示该弧流量，最大流量必须满足以下条件的限制：1. 可行性条件：xi=0, x1=3, x2=5, x3=1, x4=4, x5=1,x6=2, x7=5, x8=22. 始点Vs和收点Vt容量的要求：X1+x2=8, x7+x8=73. 流量平衡要求总流入量和总流出量相同：X1+x2-x7-x8=04. 内节点流入量和流出量相同：X1+x5-x3-x4=0X2+x3-x6=0X6-x5-x8=0X4-x7=0目标函数为：max z=x1+x2软件求解：Matlab函数：linprog(线性规划), ip（整数规划） Lindo软件求解结果如下： OBJECTIVE FUNCTION VALUE 1) 5.000000 VARIABLE VALUE REDUCED COST X1 3.000000 0.000000 X2 2.000000 0.000000 X3 0.000000 1.000000 X4 3.000000 0.000000 X5 0.000000 0.000000 X6 2.000000 0.000000 X7 3.000000 0.000000 X8 2.000000 0.000000例5.如下图所示为一城市水管网络流量图，试求一条从始点Vs到收点Vt的最大流v3v1vtv2v4vs1735108611453 5最小费用最大流问题网络最大流只考虑了流量的问题，实际在运用时还有“费用”因素存在。人们总是希望在得到最大流的同时，使费用最少，这就是最小费用最大流问题VsV2V3VtV1V4(3,2，x1)(1,1，x3)(4,，5，x4)(5,1，x7)(5,3，x2)(2,4，x6)(1,2，x5)(2,2，x8)如上图所示：括号里第一个数字表示最大容量，第二个数字表示单位流量的费用，第三个表示待求实际流量。从前面可知，网络的最大流问题的解不唯一，我们可以分别计算两次线性规划求出最小费用最大流，求解过程如下：（1） 建立求解最大流的线性规划模型，求出最大流（2） 将求出的最大流作为已知限制条件，构建求解最小费用最大流的线性规划模型。 由前面已经求出最大流为5，则将x1+x2=5作为增加的约束条件，另将目标函数改为：Min z=2x1+3x2+x3+5x4+2x5+4x6+x7+2x8即线性模型如下：Min 2x1+3x2+x3+5x4+2x5+4x6+x7+2x8stx1=3x2=5x3=1x4=4x5=1x6=2x7=5x8=2X1+x2=8x7+x8=7X1+x2-x7-x8=0X1+x5-x3-x4=0X2+x3-x6=0X6-x5-x8=0X4-x7=0x1+x2=5运用Lindo求解，可得结果如下： OBJECTIVE FUNCTION VALUE 1) 42.00000 VARIABLE VALUE REDUCED COST X1 3.000000 0.000000