资源描述：
《动态规划-图论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、§1 动态规划模型AB1B2C1C2C3D1D2E536337263871如图所示，给定一个线路网络，两点之间连线上的数字表示两点间距离，试求一条从A到E的路线，使总距离为最短。Mattlab求解：首先利用Excel建立两个工作表edge和n分别存储图的上三角阵和顶点数量。其中edge=999995299999999999999999999999999999999999999999999937999999999999999999999999999999999999999963999999999999999999999999999999999999
2、999999999699999999999999999999999999999999999999993899999999999999999999999999999999999999991999999999999999999999999999999999999999999999399999999999999999999999999999999999999997999999999999999999999999999999999999999999999n=9,然后在Matlab调入以上数据。同时将自编的动态规划软件“dynamic.m”调入当前目录之中
3、，在Matlab命令窗口输入dynamic,回车后则在窗口显示出路径Path和距离distance§2 最小生成树253147650604565524050703042例1某工厂要架设局域网联通工厂各个部门。已知工厂有7个部门，各个部门间铺设网线的距离如上图所示，计算出铺设网线的最短距离。Matlab的算法：首先，将上图的邻接矩阵存储为G,顶点数存储为N；即：G=999995060999999999999999999995099999999996540999999999960999999999952999999999945999996552999
4、99503042999994099999509999970999999999999999999993070999999999999999999994542999999999999999N=7,然后调入到Matlab命令窗口中，另外将自编程序prim.m存放到当前目录中，最后，输入prim后回车。打开变量result，即可看见最小生成树的连接方式。例2某六个城市之间的道路网如下图所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。v5v6v2v4627535441V1v3§3 最短路例3如下图所示的交通网络，边上的权重代表城
5、市之间的距离，求城市1到其他城市的最短路径。12354101003010502060Matlab的算法：首先，将上图的邻接矩阵存储为G,顶点数存储为N；即：G=999991099999301009999999999509999999999999999999999999999991099999999992099999999999999999999999996099999N=5，然后调入到Matlab命令窗口中，另外将自编程序dijkstra.m存放到当前目录中，最后，输入dijkstra后回车。打开变量path，即可看见最最短路的连接方式。例4:如
6、下图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交通网到达v8，要寻求是总路程最短的线路。v6v4v2v8v7v963623410231262410V1V3v5§4 网络最大流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<=
7、2,x7<=5,x8<=21.始点Vs和收点Vt容量的要求：X1+x2<=8,x7+x8<=72.流量平衡要求总流入量和总流出量相同：X1+x2-x7-x8=03.内节点流入量和流出量相同：X1+x5-x3-x4=0X2+x3-x6=0X6-x5-x8=0X4-x7=0目标函数为：maxz=x1+x2软件求解：Matlab函数：linprog(线性规划),ip（整数规划）Lindo软件求解结果如下：OBJECTIVEFUNCTIONVALUE1)5.000000VARIABLEVALUEREDUCEDCOSTX13.0000000.000000X
8、22.0000000.000000X30.0000001.000000X43.0000000.000000X50.0000000.000
