动态规划运筹学课程设计

1、综 合 设 计 报 告综合设计五 动态规划算法学生姓名：曾 俊 扬学 号：200840204219年级专业：2008级信息与计算科学2班指导老师：王明春 老师学 院：理学院评阅成绩：评阅意见：成绩评定教师签名： 时间：湖南·长沙提交日期：2011年6月动态规划之最短线路问题1设计目的、要求 熟悉动态规划的相关概念，掌握使用动态规划的基本方法求解生活实际问题。本设计主要研究最短路问题，利用JAVA实现最短路算法。2设计原理在求解的各个阶段，利用了k阶段与k+1阶段之间的递推关系：3采用软件、设备4设计内容1.动态规划基本认识：动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题

2、的一种方法。该方法是由美国数学家贝尔曼(RBellman)等人在本世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支动态规划。他的名著动态规划于1957年出版，该书是动态规划的第一本著作。动态规划是现代企业管理中的一种重要决策方法，在工程技术、经济管理、工农业生产及军事及其它部们都有广泛的应用，并且获得了显著的效果。动态规划可用于解决最优路径问题、资源分配问题、生产计划与库存问题、投资分配问题、装载问题、设备更新与维修问题、排序问题及生产过程的最优控制等。由于它所具有独特的解

3、题思路，在处理某些优化问题时，常常比线性规划或非线性规划方法更有效。本设计从实际问题展开对动态规划算法最短路问题的实现。2.实际问题：某工厂需要把一批货物从城市A运到城市E，中间可经过B1 、B2、B3、C1、C2、C3、D1、D2等城市，各城市之间的交通线和距离如下图所示，问应该选择一条什么路线，使得从A到E的距离最短？3.分析求解：基本概念及相关符号(1) 阶段把所给问题的过程，按时间和空间特征划分成若干个相互联系的阶段，以便按次序去求每个阶段的解，阶段总数一般用字母n表示，用字母k表示阶段变量。(2) 状态状态表示每个阶段开始时系统所处的自然状况或客观条件，它描述了研究问题过程状况。描述

4、各阶段状态的变量称为状态变量，常用字母sk表示第k阶段的状态变量，状态变量的取值范围称为状态集，用Sk表示。(3) 决策当系统在某阶段处于某种状态，可以采取的行动（或决定、选择），从而确定下一阶段系统将到达的状态，称这种行动为决策。描述决策的变量，称为决策变量。常用字母u k(sk)表示第k阶段系统处于状态sk时的决策变量。决策变量的取值范围称为决策集，用Dk(sk)表示。下面利用动态规划的逆推归纳法，将问题从最后一个城市E逐步推算到第一个城市A，在此表示第k阶段从城市sk到城市E最短路。1）当 k = 4 时，由于第四阶段只有两个城市 D1、D2 显然，。2）当 k = 3 时，s3取值C1

5、、C2、C3 ,从C1出发到E有两条路，一条是经过D1到E，另一条是经过D2到E ，显然：即从到E的最短距离是7，相应的决策为，最短路线是。 同理 3）当 k = 2 时，s2的取值为B1、B2、B3，从B1出发到E有三条路，分别是经过C1、C2、C3到E，则有：同理4）当k = 1时，s1的只有一个取值为A. 从A出发到E有三条路，分别经过B1、B2、B3到E，则有：于是得到从A到E的最短距离17，为了找出最短路线，按计算的顺序逆推回去，可得到最优策略为：，最短路线是AB1C2D2E。4.代码实现：利用MyEclipse采用java语言实现对实际问题的代码求解（1）创建了两个类Node、St

6、atusNode是节点类，对应于各城市，包含节点标识（id）、指向（所指向的节 点）以及对应的权值即距离三个属性，方法getW()用于获得两节点之间的距离。Status是阶段类，对应于各决策阶段，包含阶段标识（id)、节点数、节点三个属性。创建各节点，生成各阶段状态。遍历各状态中的各节点：for(int i=s.length-1;i>=0;i-)System.out.print("k="+(i+1)+"时，");for(int j=0;j<si.nodeNum;j+)String str = si.nodej.id;System.out.pr

7、intln(si.nodej.id+"到终点"+nodenode.length-1.id+"的最短距离为:"+f(s,i,si.nodej);System.out.println("最短路线 为:"+str+shortline(s,i,si.nodej);5原始程序、数据 在主程序中使用节点类Node创建所有节点并用阶段类Status创建所有阶段：节点创建：Node node = new Node10;node9 = new Node("E",new Node,new int);node8 = new Node(&

8、quot;D2",new Nodenode9,new int3);.node1 = new Node("B1",new Nodenode4,node5,node6,new int6,4,5);node0 = new Node("A",new Nodenode1,node2,node3,new int8,9,6);阶段生成：Status s = new Status4;s0 = new Status(1,1,new Nodenode0);.s3 = new Status(4,2,new Nodenode7,node8);点到终点的最短距离：pri

9、vate static int f(Status s,int a,Node node) int ary = new intnode.nextnode.length;if(sa.id=s.length)ary0 = node.getW(node.nextnode0);elsefor(int i=0;i<node.nextnode.length;i+)aryi=node.getW(node.nextnodei)+f(s,a+1,node.nextnodei); ary0 = min(ary);return ary0;最短路线输出：private static String shortline

10、(Status s,int a,Node node) int ary = new intnode.nextnode.length;if(sa.id=s.length)return ""+node.nextnode0.id; elseint k = 0;for(int i=0;i<node.nextnode.length;i+)aryi=node.getW(node.nextnodei)+f(s,a+1,node.nextnodei);if(aryi<ary0)k = i;ary0 = aryi;return ""+node.nextnodek

11、.id + shortline(s,a+1,node.nextnodek);6结果分析程序运行截图：得到如下结果：最短路线顺序为：。最短距离为17。参考文献1 何坚勇.运筹学基础M.北京:清华大学出版社，2000：12-152 胡运权.运筹学教程M.北京:清华大学出版社, 2004：54-593 韩伯棠.管理运筹学M.北京:高等教育出版社，2000：25-304 吴祈宗.运筹学M.北京:机械工程出版社，2000：11-155 钱颂迪.运筹学M.北京:清华大学出版社，2001：36-396 李荣均.运筹学（MBA工商管理教材）M.北京.华南理工大学出版社，2002：44-48附录（主要是源程序）

12、package work;public class Node String id; Node nextnode; int w; public Node(String id,Node nextnode,int w)this.id = id;this.nextnode = nextnode;this.w = w; public int getW(Node n)for(int i=0;i<this.nextnode.length;i+)if(this.nextnodei.id=n.id)return this.wi;return 0; package work;public class Sta

13、tus int id; int nodeNum; Node node; public Status(int id,int nodeNum,Node node)this.id = id;this.nodeNum = nodeNum;this.node = node; package work;import java.util.Arrays;import ;public class ShortLineDemo public static void main(String args) Node node = new Node10;node9 = new Node("E",new

14、Node,new int);node8 = new Node("D2",new Nodenode9,new int3);node7 = new Node("D1",new Nodenode9,new int4);node6 = new Node("C3",new Nodenode7,node8,new int1,3);node5 = new Node("C2",new Nodenode7,node8,new int6,2);node4 = new Node("C1",new Nodenode7,

15、node8,new int3,5);node3 = new Node("B3",new Nodenode4,node5,node6,new int7,8,7);node2 = new Node("B2",new Nodenode4,node5,node6,new int8,7,6);node1 = new Node("B1",new Nodenode4,node5,node6,new int6,4,5);node0 = new Node("A",new Nodenode1,node2,node3,new int8,

16、9,6);Status s = new Status4;s0 = new Status(1,1,new Nodenode0);s1 = new Status(2,3,new Nodenode1,node2,node3);s2 = new Status(3,3,new Nodenode4,node5,node6);s3 = new Status(4,2,new Nodenode7,node8);for(int i=s.length-1;i>=0;i-)System.out.print("k="+(i+1)+"时，");for(int j=0;j<

17、;si.nodeNum;j+)String str = si.nodej.id;System.out.println(si.nodej.id+"到终点"+nodenode.length-1.id+"的最短距离为:"+f(s,i,si.nodej);System.out.println("最短路线为:"+str+shortline(s,i,si.nodej);System.out.println();private static String shortline(Status s,int a,Node node) int ary = n

18、ew intnode.nextnode.length;if(sa.id=s.length)return ""+node.nextnode0.id; elseint k = 0;for(int i=0;i<node.nextnode.length;i+)aryi = node.getW(node.nextnodei)+f(s,a+1,node.nextnodei);if(aryi<ary0)k = i;ary0 = aryi;return ""+node.nextnodek.id + shortline(s,a+1,node.nextnodek); private static int f(Status s,int a,N