动态规划--运筹学课程设计.doc

湖 南 农 业 大 学 综 合 设 计 报 告 综合设计五 动态规划算法 学生姓名：曾 俊 扬 学 号：200840204219 年级专业：2008级信息与计算科学2班 指导老师：王明春 老师 学 院：理学院 评阅成绩： 评阅意见： 成绩评定教师签名： 时间： 湖南·长沙 提交日期：2011年6月 动态规划之最短线路问题 1设计目的、要求 熟悉动态规划的相关概念，掌握使用动态规划的基本方法求解生活实际问题。本设计主要研究最短路问题，利用JAVA实现最短路算法。 2设计原理 在求解的各个阶段，利用了k阶段与k+1阶段之间的递推关系： 3采用软件、设备 微型电子计算机、MyEclipse 6.5 4设计内容 1.动态规划基本认识： 动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼(R．Bellman)等人在本世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支——动态规划。他的名著《动态规划》于1957年出版，该书是动态规划的第一本著作。 动态规划是现代企业管理中的一种重要决策方法，在工程技术、经济管理、工农业生产及军事及其它部们都有广泛的应用，并且获得了显著的效果。动态规划可用于解决最优路径问题、资源分配问题、生产计划与库存问题、投资分配问题、装载问题、设备更新与维修问题、排序问题及生产过程的最优控制等。由于它所具有独特的解题思路，在处理某些优化问题时，常常比线性规划或非线性规划方法更有效。 本设计从实际问题展开对动态规划算法最短路问题的实现。 2.实际问题：某工厂需要把一批货物从城市A运到城市E，中间可经过B1 、B2、B3、C1、C2、C3、D1、D2等城市，各城市之间的交通线和距离如下图所示，问应该选择一条什么路线，使得从A到E的距离最短？ 3.分析求解：基本概念及相关符号 (1) 阶段 把所给问题的过程，按时间和空间特征划分成若干个相互联系的阶段，以便按次序去求每个阶段的解，阶段总数一般用字母n表示，用字母k表示阶段变量。 (2) 状态 状态表示每个阶段开始时系统所处的自然状况或客观条件，它描述了研究问题过程状况。描述各阶段状态的变量称为状态变量，常用字母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、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，为了找出最短路线，按计算的顺序逆推回去，可得到最优策略为： ， 最短路线是A→B1→C2→D2→E。 4.代码实现： 利用MyEclipse采用java语言实现对实际问题的代码求解 （1）创建了两个类Node、Status Node是节点类，对应于各城市，包含节点标识（id）、指向（所指向的节 点）以及对应的权值即距离三个属性，方法getW()用于获得两节点之间的距离。 Status是阶段类，对应于各决策阶段，包含阶段标识（id)、节点数、节点三个属性。 （2）主程序：ShortLineDemo.java 创建各节点，生成各阶段状态。 遍历各状态中的各节点： for(int i=s.length-1;i=0;i--){ System.out.print(k=+(i+1)+时，); for(int j=0;js[i].nodeNum;j++){ String str = s[i].node[j].id;System.out.println