当前位置：文档库 › 动态规划--运筹学课程设计

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

湖南农业大学

综合设计报告

综合设计五

动态规划算法

学生姓名：曾俊扬

学号：200840204219

年级专业：2008级信息与计算科学2班

指导老师：王明春老师

学院：理学院

评阅成绩：

评阅意见：

成绩评定教师签名：时间：

湖南·长沙

提交日期：2011年6月

动态规划之最短线路问题

1设计目的、要求

熟悉动态规划的相关概念，掌握使用动态规划的基本方法求解生活实际问题。本设计主要研究最短路问题，利用JAVA 实现最短路算法。

2设计原理

在求解的各个阶段，利用了k 阶段与k+1阶段之间的递推关系：

{}11()55444()min (,())()4,3,2,1

()0(()(,))

k k k k k k k k k k u D s f s d s u s f s k f s f s d s E ++∈?=+=??==??或

3采用软件、设备

微型电子计算机、MyEclipse 6.5

4设计内容

1.动态规划基本认识：

动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼(R ．Bellman)等人在本世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支——动态规划。他的名著《动态规划》于1957年出版，该书是动态规划的第一本著作。

动态规划是现代企业管理中的一种重要决策方法，在工程技术、经济管理、工农业生产及军事及其它部们都有广泛的应用，并且获得了显著的效果。动态规划可用于解决最优路径问题、资源分配问题、生产计划与库存问题、投资分配问题、装载问题、设备更新与维修问题、排序问题及生产过程的最优控制等。由于它所具有独特的解题思路，在处理某些优化问题时，常常比线性规划或非线性规划方法更有效。

本设计从实际问题展开对动态规划算法最短路问题的实现。

2.实际问题：某工厂需要把一批货物从城市A 运到城市E ，中间可经过B 1 、

B 2、B 3、

C 1、C 2、C 3、

D 1、D 2等城市，各城市之间的交通线和距离如下图所示，问应该选择一条什么路线，使得从A 到

E 的距离最短？

3.分析求解：基本概念及相关符号

(1) 阶段

把所给问题的过程，按时间和空间特征划分成若干个相互联系的阶段，以便按次序去求每个阶段的解，阶段总数一般用字母n 表示，用字母k 表示阶段变量。 (2) 状态

状态表示每个阶段开始时系统所处的自然状况或客观条件，它描述了研究问题过程状况。描述各阶段状态的变量称为状态变量，常用字母s k 表示第k 阶段的状态变量，状态变量的取值范围称为状态集，用S k 表示。 (3) 决策

当系统在某阶段处于某种状态，可以采取的行动（或决定、选择），从而确定下一阶段系统将到达的状态，称这种行动为决策。描述决策的变量，称为决策变量。常用字母u k (s k )表示第k 阶段系统处于状态s k 时的决策变量。决策变量的取值范围称为决策集，用D k (s k )表示。

下面利用动态规划的逆推归纳法，将问题从最后一个城市E 逐步推算到第一个城市A ，在此()k k f s 表示第k 阶段从城市s k 到城市E 最短路。

1）当 k = 4 时，由于第四阶段只有两个城市 D 1、D 2

显然，*41141()(,)4,()f D d D E u D E ===，*

42242()(,)3,()f D d D E u D E ===。

2）当 k = 3 时，s 3取值C 1、C 2、C 3 ,从C 1出发到E 有两条路，一条是经过

D 1到

E ，另一条是经过D 2到E ，显然：

1141*31311

1242(,)()34()min min 7,

()(,)()53d C D f D f C u C D d C D f D ++????

====????++????

即从1C 到E 的最短距离是7，相应的决策为*311()u C D =，最短路线是

11C D E →→。

同理 2141*323222242(,)()64()5,

()(,)()23d C D f D f C u C D d C D f D ++????

====?

???++??

3141*333313242(,)()14()5,

()(,)()33d C D f D f C u C D d C D f D ++????

====????++??

3）当 k = 2 时，s 2的取值为B 1、B 2、B 3，从B 1出发到E 有三条路，分别是

经过C 1、C 2、C 3到E ，则有：

1131*2112322121333(,)()67()(,)()459,

()55(,)()d B C f C f B d B C f C u B C d B C f C ++????????

=+=+==????????

++???

同理 2131*2222322232333(,)()87()(,)()7511,

()65(,)()d B C f C f B d B C f C u B C d B C f C ++????

????

=+=+==????????

++????

3131*233232233333(,)()77()(,)()8512,

()75(3,)()d B C f C f B d B C f C u B C d B C f C ++????

????

=+=+==????????

++???

4）当k = 1时，s 1的只有一个取值为A. 从A 出发到E 有三条路，分别经

过B 1、B 2、B 3到E ，则有：

121*122211323(,)()89()min (,)()min 91117,

()612(,)()d A B f B f A d A B f B u A B d A B f B ++????????

=+=+==????????

++???

于是得到从A 到E 的最短距离17，为了找出最短路线，按计算的顺序逆

推回去，可得到最优策略为：

****1,41121232242(){(),(),(),()}p A u A B u B C u C D u D E =====，最短路线是A →B 1→C 2→D 2→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;j

String str = s[i].node[j].id;System.out.println(s[i].node[j].id+"到终

点"+node[node.length-1].id+"的最短距离为:"+f(s,i,s[i].node[j]));

System.out.println("最短路线

为:"+str+shortline(s,i,s[i].node[j]));}

}

5原始程序、数据

在主程序中使用节点类Node创建所有节点并用阶段类Status创建所有阶段：

节点创建：

Node[] node = new Node[10];

node[9] = new Node("E",new Node[]{},new int[]{});

node[8] = new Node("D2",new Node[]{node[9]},new int[]{3});

......

node[1] = new Node("B1",new Node[]{node[4],node[5],node[6]},new int[]{6,4,5});

node[0] = new Node("A",new Node[]{node[1],node[2],node[3]},new int[]{8,9,6});

阶段生成：

Status[] s = new Status[4];

s[0] = new Status(1,1,new Node[]{node[0]});

.....

s[3] = new Status(4,2,new Node[]{node[7],node[8]});

点到终点的最短距离：

private static int f(Status[] s,int a,Node node) {

int[] ary = new int[node.nextnode.length];

if(s[a].id==s.length){ary[0] = node.getW(node.nextnode[0]);

}else{for(int i=0;i

ary[i]=node.getW(node.nextnode[i])+f(s,a+1,node.nextnode[i]);}

ary[0] = min(ary);}

return ary[0];}

最短路线输出：

private static String shortline(Status[] s,int a,Node node) {

i nt[] ary = new int[node.nextnode.length];

if(s[a].id==s.leng th){return "→"+node.nextnode[0].id;

}else{int k = 0;for(int i=0;i

ary[i]=node.getW(node.nextnode[i])+f(s,a+1,node.nextnode[i]);

if(ary[i]

return "→"+node.nextnode[k].id + shortline(s,a+1,node.nextnode[k]);}

}

6结果分析

程序运行截图：

得到如下结果：

最短路线顺序为：123A B C D E →→→→。最短距离为17。

参考文献

[1] 何坚勇.运筹学基础[M].北京:清华大学出版社，2000：12-15

[2] 胡运权.运筹学教程[M].北京:清华大学出版社, 2004：54-59

[3] 韩伯棠.管理运筹学[M].北京:高等教育出版社，2000：25-30

[4] 吴祈宗.运筹学[M].北京:机械工程出版社，2000：11-15

[5] 钱颂迪.运筹学[M].北京:清华大学出版社，2001：36-39

[6] 李荣均.运筹学（MBA工商管理教材）[M].北京.华南理工大学出版社，2002：44-48

附录

（主要是源程序）

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

if(this.nextnode[i].id==n.id){

return this.w[i];

}

return 0;

}

package work;

public class Status {

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 java.util.Scanner;

public class ShortLineDemo {

public static void main(String[] args) {

Node[] node = new Node[10];

node[9] = new Node("E",new Node[]{},new int[]{});

node[8] = new Node("D2",new Node[]{node[9]},new int[]{3});

node[7] = new Node("D1",new Node[]{node[9]},new int[]{4});

node[6] = new Node("C3",new Node[]{node[7],node[8]},new int[]{1,3});

node[5] = new Node("C2",new Node[]{node[7],node[8]},new int[]{6,2});

node[4] = new Node("C1",new Node[]{node[7],node[8]},new int[]{3,5});

node[3] = new Node("B3",new Node[]{node[4],node[5],node[6]},new int[]{7,8,7});

node[2] = new Node("B2",new Node[]{node[4],node[5],node[6]},new int[]{8,7,6});

node[1] = new Node("B1",new Node[]{node[4],node[5],node[6]},new int[]{6,4,5});

node[0] = new Node("A",new Node[]{node[1],node[2],node[3]},new int[]{8,9,6});

Status[] s = new Status[4];

s[0] = new Status(1,1,new Node[]{node[0]});

s[1] = new Status(2,3,new Node[]{node[1],node[2],node[3]});

s[2] = new Status(3,3,new Node[]{node[4],node[5],node[6]});

s[3] = new Status(4,2,new Node[]{node[7],node[8]});

for(int i=s.length-1;i>=0;i--){

System.out.print("k="+(i+1)+"时，");

for(int j=0;j

String str = s[i].node[j].id;

System.out.println(s[i].node[j].id+"到终点"+node[node.length-1].id+"的最短距离为:"

+f(s,i,s[i].node[j]));

System.out.println("最短路线为:"+str+shortline(s,i,s[i].node[j]));

}

System.out.println();

}

private static String shortline(Status[] s,int a,Node node) {

int[] ary = new int[node.nextnode.length];

if(s[a].id==s.length){

return "→"+node.nextnode[0].id;

}else{

int k = 0;

for(int i=0;i

ary[i] = node.getW(node.nextnode[i])+f(s,a+1,node.nextnode[i]);

if(ary[i]

k = i;

ary[0] = ary[i];

}

return "→"+node.nextnode[k].id + shortline(s,a+1,node.nextnode[k]);

}

private static int f(Status[] s,int a,Node node) {

int[] ary = new int[node.nextnode.length];

if(s[a].id==s.length){

ary[0] = node.getW(node.nextnode[0]);

}else{

for(int i=0;i

ary[i] = node.getW(node.nextnode[i])+f(s,a+1,node.nextnode[i]);

}

ary[0] = min(ary);

}

return ary[0];

}

private static int min(int[] f) {

Arrays.sort(f);

return f[0];

}

运筹学整数规划例题

练习4.9 连续投资问题某公司现有资金10万元,拟在今后五年考虑用于下列项目的投资: 项目A:从第一年到第四年每年年初需要投资,并于次年收回本利115%,但要求第一年投资最低金额为4万元,第二.三.四年不限. 项目B:第三年初需要投资,到第五年末能收回本利128%,但规定最低投资金额为3万元,最高金额为5万元. 项目C:第二年初需要投资,到第五年末能收回本利140%,但规定其投资金额或为2万元,或为4万元,或为6万元,或为8万元. 项目D:五年每年年初都可购买公债,于当年末归还,并获利6%,此项目投资金额不限. 试问该公司应图和确定这些项目的每年投资金额,使到第五年末拥有最大的资金收益. (1) x 为项目各年月初投入向量。 (2) ij x 为 i 种项目j 年的月初的投入。 (3) 向量c 中的元素 ij c 为i 年末j 种项目收回本例的百分比。 (4) 矩阵A 中元素 ij a 为约束条件中每个变量ij x 的系数。 (5) Z 为第5年末能拥有的资金本利最大总额。因此目标函数为 4325max 1.15 1.28 1.40 1.06A B C D Z x x x x =+++ 束条件应是每年年初的投资额应等于该投资者年初所拥有的资金. 第1年年初该投资者拥有10万元资金,故有 11100000A D x x +=. 第2年年初该投资者手中拥有资金只有()116%D x +,故有 22211.06A C D D x x x x ++=. 第3年年初该投资者拥有资金为从D 项目收回的本金: 21.06D x ,及从项目A 中第1年投资收回的本金: 11.15A x ,故有 333121.15 1.06A B D A D x x x x x ++=+ 同理第4年、第5年有约束为 44231.15 1.06A D A D x x x x +=+, 5341.15 1.06D A D x x x =+

运筹学实验_动态规划

实验二用MATLAB解决动态规划问题问题:有一部货车每天沿着公路给四个售货店卸下6箱货物,如果各零售店出售该货物所得利润如下表所示,试求在各零售店卸下几箱货物,能使获得总利润最解: 1)将问题按售货店分为四个阶段 2)设s k表示为分配给第k个售货店到第n个工厂的货物数, x k设为决策变量,表示为分配给第k个售货店的货物数, 状态转移方程为s k＋1＝s k－x k。 P k(x k)表示为x k箱货物分到第k个售货店所得的盈利值。 f k(s k)表示为s k箱货物分配给第k个售货店到第n个售货店的最大盈利值。 3)递推关系式: f k(s k)＝max[ P k(x k)+ f k+1(s k－x k) ] k=4,3,2,1 边界条件:f5(s5)＝0 4)从最后一个阶段开始向前逆推计算。第四阶段: 设将s4箱货物(s4＝0,1,2,3,4,5,6)全部分配给4售货店时,最大盈利值为: f4(s4)＝max[P4(x4)] 其中x4＝s4＝0,1,2,3,4,5,6 x4*表示使得f4(s4)为最大值时的最优决策。第三阶段:

设将s3箱货物(s3＝0,1,2,3,4,5,6)分配给3售货店与4售货店时,对每一个s3值,都有一种最优分配方案,使得最大盈利值为:f3(s3)＝max[ P3(x3)+ f4(s3－x3) ] ,x3＝第二阶段: 设将s2箱货物(s2＝0,1,2,3,4,5,6)分配给2售货店、3售货店与4售货店时,则最大盈利值为:f2(s2)＝max[ P2(x2)+ f3(s2－x2) ] 第一阶段: 设将s2箱货物(s1＝0,1,2,3,4,5,6)分配给1售货店、2售货店、3售货店与4售货店时,则最大盈利值为:f1(s1)＝max[ P1(x1)+ f2(s1－x1) ] 按计算表格的顺序反推,可知最优分配方案有6个: 1） x1*＝1,x2*＝1,x3*=3,x4*=1。 2） x1*＝1,x2*＝2,x3*=2,x4*=1。 3） x1*＝1,x2*＝3,x3*=1,x4*=1。

《管理运筹学期末复习题》

运筹学期末复习题一、判断题： 1、任何线性规划一定有最优解。（） 2、若线性规划有最优解，则一定有基本最优解。（） 3、线性规划可行域无界，则具有无界解。（） 4、基本解对应的基是可行基。（） 5、在基本可行解中非基变量一定为零。（） 6、变量取0或1的规划是整数规划。（） 7、运输问题中应用位势法求得的检验数不唯一。（） 8、产地数为3，销地数为4的平衡运输中，变量组{X11，X13，X22，X33，X34}可作为一组基变量.（） 9、不平衡运输问题不一定有最优解。（） 10、m+n-1个变量构成基变量组的充要条件是它们不包含闭回路。（） 11、含有孤立点的变量组不包含有闭回路。（） 12、不包含任何闭回路的变量组必有孤立点。（） 13、产地个数为m销地个数为n的平衡运输问题的系数距阵为A，则有r(A)≤m+n-1（） 14、用一个常数k加到运价矩阵C的某列的所有元素上,则最优解不变。（） 15、匈牙利法是求解最小值分配问题的一种方法。（） 16、连通图G的部分树是取图G的点和G的所有边组成的树。（） 17、求最小树可用破圈法.（） 18、Dijkstra算法要求边的长度非负。（） 19、Floyd算法要求边的长度非负。（） 20、在最短路问题中，发点到收点的最短路长是唯一的。（） 21、连通图一定有支撑树。（） 22、网络计划中的总工期等于各工序时间之和。

（） 23、网络计划中，总时差为0的工序称为关键工序。（） 24、在网络图中，关键路线一定存在。（） 25、紧前工序是前道工序。（） 26、后续工序是紧后工序。（） 27、虚工序是虚设的,不需要时间,费用和资源,并不表示任何关系的工序。（） 28、动态规划是求解多阶段决策问题的一种思路，同时是一种算法。（） 29、求最短路径的结果是唯一的。（） 30、在不确定型决策中，最小机会损失准则比等可能性则保守性更强。（） 31、决策树比决策矩阵更适于描述序列决策过程。（） 32、在股票市场中，有的股东赚钱，有的股东赔钱，则赚钱的总金额与赔钱的总金额相等，因此称这一现象为零和现象。（） 33、若矩阵对策A的某一行元素均大于0，则对应值大于0。（） 34、矩阵对策中，如果最优解要求一个局中人采取纯策略，则另一局中人也必须采取纯策略。（） 35、多阶段决策问题的最优解是唯一的。（） 36、网络图中相邻的两个结点之间可以有两条弧。（）

128503-管理运筹学-习题-06-动态规划

习题 6-1. 考虑下面的网络图，箭头上的数字代表相连两个节点之间的距离。（1）用动态规划找出从节点1到节点10的最短路。（2）从节点4到节点10的最短路呢？ 6-2. 从北京到上海的包机的剩余装载能力为2000kg ，某一运输公司现有4种货物需要从北京运输到上海。每种货物的单位、单位重量和单位运输费用如下表所示。（1）用动态规划找出包机应该运输的每种货物的单位数。（2）假设包机同意装载另一批货物，剩余装载能力降为1800kg ，计算结果会怎样变化？ 6-3. 假定有一个3阶段的过程，每一阶段的产量是需要做出决策的函数。使用数学符号，问题表述如下： Max ()()()332211d r d r d r ++ s.t. 1000321≤++d d d 每个阶段的决策变量和相应的返回值如下所示：

6-4. 某制造公司为一家汽车工厂提供发动机的部件，以下是3个月的生产计划的数据。量是10单位，并且生产批量是10的倍数（例如，10,20或者30单位）。 6-5. 某物流公司雇佣了8名新员工，现决定如何把他们分配到4项作业上。公司给出了以下每项作业分配不同的作业人员的估计利润表。 (1) 用动态规划决定每项作业应该分配的新员工数目。 (2) 如果公司只雇佣了6名新员工，应该把这些员工分配给哪些作业？ 6-6. 一个锯木厂采购了一批20ft 长的原木，想要把这些原木切成更短的原木，然后把切后的小原木卖给制造公司。制造公司已经订购了一批4种尺寸的原木：l 1=3ft ，l 2=7ft ，l 3=11ft ，l 4=16ft 。锯木厂现在有2000个长度为20ft 的原木的库存，并希望有选择地裁截原木以最大化利润。假定锯木厂的订单是无限的，唯一的问题就是确定把现有原木裁成的类型以最大化利润。原木的利润如下表所示：任何裁截类型的长度限制如下： 201173321≤++d d d 其中，i d 是长度为i l 的类型的裁截数目，4,3,2,1=i . （1）为这个问题建立动态规划模型，并使用模型解决问题。你需要设立哪些变量？状态变量有哪些？（2）简要介绍如果总的长度l 被截成l 1，l 2，……l N 这样N 中长度的话，如果扩展现有模型以找到最优解？ 6-7. 一家港口公司建立了良好的管理训练计划，希望每一个员工完成一个4阶段的作业。但是在训练计划的每个阶段，员工都会被分配一系列艰难的作业。以下是训练计划的每个阶段员工可能被分派的作业和任务估计完成时间。次级阶段的作业取决于其先前的作业。例如，在阶段1接受作业A 的员工在阶段2只能接受作业F 或者作业G ——即每一项作业都存在优先关系。

运筹学--第七章动态规划

１８９习题七7.1计算如图所示的从A 到E 的最短路线及其长度（单位：km ）：（1）用逆推解法；2用标号法。 7.2 用动态规划方法求解下列问题（1） max z ＝x 12x 2 x 33 x 1＋x 2＋x 3 ≤6 x j ≥0 （j ＝1,2,3）（2）min z ＝ 3x 12＋4x 22 ＋x 32 x 1x 2 x 3 ≥ 9 x j ≥0 （j ＝1,2,3） 7.3 利用动态规划方法证明平均值不等式： n n n x x x n x x x 12121)()( ≥+++ 设x i ≥0，i ＝1，2，…，n 。 7.4 考虑一个有m 个产地和n 个销地的运输问题。设a i （i ＝1，2，…，m ）为产地i 可发运的物资数，b j （j ＝1，2，…，n ）为销地j 所需要的物资数。又从产地i 到销地j 发运x ij 单位物资所需的费用为h ij （x ij ），试将此问题建立动态规划的模型。 7.5 某公司在今后三年的每一年的开头将资金投入A 或B 项工程，年末的回收及其概率如下表所示。每年至多做一项投资，每次只能投入1000万元。求出三年后所拥有的期望金额达到最大的投资方案。投资回收概率 A 0 0.4 2000 0.6 B 1000 0.9 2000 0.1 7.6 某公司有三个工厂，它们都可以考虑改造扩建。每个工厂都有若干种方案可供选择，各种方案的投资及所能取得的收益如下表所示(单位：千万元)。现公司有资金5千万元，问应如何分配投资使公司的总收益最大?

7.7 某厂准备连续3个月生产A种产品，每月初开始生产。A的生产成本费用为x2，其中x是A产品当月的生产数量。仓库存货成本费是每月每单位为1元。估计3个月的需求量分别为d1＝100，d2＝110，d3＝120。现设开始时第一个月月初存货s0＝0，第三个月的月末存货s3＝0。试问：每月的生产数量应是多少才使总的生产和存货费用为最小。 7.8 设有一辆载重卡车，现有4种货物均可用此车运输。已知这4种货物的重量、容积及价值关系如下表所示。货物代号重量（吨）容积（立方米）价值（千元） 1 2 2 3 2 3 2 4 3 4 2 5 4 5 3 6 若该卡车的最大载重为15吨，最大允许装载容积为10立方米，在许可的条件下，每车装载每一种货物的件数不限。问应如何搭配这四种货物，才能使每车装载货物的价值最大。 7.9 某警卫部门有12支巡逻队负责4个仓库的巡逻。按规定对每个仓库可分别派2－4支队伍巡逻。由于所派队伍数量上的差别，各仓库一年内预期发生事故的次数如下表所示。试应用动态规划的方法确定派往各仓库的巡逻队数，使预期事故的总次数为最少。巡逻队数预期事故次数仓库 1 2 3 4 2 18 38 14 34 3 16 36 12 31 4 12 30 11 25 7.10 （生产计划问题）根据合同，某厂明年每个季度末应向销售公司提供产品，有关信息见下表。若产品过多，季末有积压，则一个季度每积压一吨产品需支付存贮费0.2万元。现需找出明年的最优生产方案，使该厂能在完成合同的情况下使全年的生产费用最低。季度j生产能力a j（吨）生产成本d j（万元/吨）需求量b j（吨） 1 30 15.6 20 2 40 14.0 25 3 25 15.3 30 4 10 14.8 15 （1）请建立此问题的线性规划模型。（提示：设第j季度工厂生产产品x j吨，第j季度初存贮的产品为y j吨，显然y1＝0）（2）请建立此问题的动态规划模型。（均不用求解）１９０

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

最新管理运筹学模拟试题及答案

运筹学整数规划例题

运筹学实验_动态规划

《管理运筹学期末复习题》

128503-管理运筹学-习题-06-动态规划

运筹学--第七章 动态规划

运筹学--第七章动态规划