当前位置:首页 >> 城乡/园林规划 >>

运筹学实验_动态规划

实验二用 MATLAB 解决动态规划问题
问题:有一部货车每天沿着公路给四个售货店卸下 6 箱货物, 如果各零售店 出售该货物所得利润如下表所示,试求在各零售店卸下几箱货物,能使获得总利 润最大?其值为多少?

零售店 箱数 0 1 2 3 4 5 6 1 0 4 6 7 7 7 7 2 0 2 4 6 8 9 10 3 0 3 5 7 8 8 8 4 0 4 5 6 6 6 6

解: 1)将问题按售货店分为四个阶段 2)设 sk 表示为分配给第 k 个售货店到第 n 个工厂的货物数, xk 设为决策变量,表示为分配给第 k 个售货店的货物数, 状态转移方程为 sk+1=sk-xk。 Pk(xk)表示为 xk 箱货物分到第 k 个售货店所得的盈利值。 fk(sk)表示为 sk 箱货物分配给第 k 个售货店到第 n 个售货店的最大盈利值。 3)递推关系式: fk(sk)=max[ Pk(xk)+ fk+1(sk-xk) ] 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,6x4*表示使得 f4(s4)为最大值时的最优决策。 x4 s4 P4(x4)

0 0

1 4

2

3

4

5

6

f4(s4)

x4*

0 1 2 3 4 5

5 6 6 6

0 4 5 6 6 6

0 1 2 3 4 5

6

6

6

6

第三阶段: 设将 s3 箱货物(s3=0,1,2,3,4,5,6)分配给 3 售货店和 4 售货店时,对每一个 s3 值, 都有一种最优分配方案,使得最大盈利值为:f3(s3)=max[ P3(x3)+ f4(s3-x3) ] ,x3 =0,1,2,3,4,5,6 x3 s3 P3(x3)+f4(s3-x3)

0 0+0 0+4 0+5 0+6 0+6 0+6 0+6

1 3+0 3+4 3+5 3+6 3+6 3+6

2

3

4

5

6

f3(s3)

x3*

0 1 2 3 4 5 6

5+0 5+4 5+5 5+6 5+6

7+0 7+4 7+5 7+6

8+0 8+4 8+5

8+0 8+4

8+0

0 4 7 9 11 12 13

0 0 1 2 3 3/4 3/4

第二阶段: 设将 s2 箱货物(s2=0,1,2,3,4,5,6)分配给 2 售货店、3 售货店和 4 售货店时,则最 大盈利值为:f2(s2)=max[ P2(x2)+ f3(s2-x2) ] 其中,x2=0,1,2,3,4,5,6 x2 s2 P2(x2)+f3(s2-x2)

0 0+0 0+4 0+7 0+9 0+11 0+12 0+13

1 2+0 2+4 2+7 2+9 2+11 2+12

2

3

4

5

6

f2(s2)

x2*

0 1 2 3 4 5 6

4+0 4+4 4+7 4+9 4+11

6+0 6+4 6+7 6+9

8+0 8+4 8+7

9+0 9+4

0 4 7 9 11 13 10+0 15

0 0 0 0/1 0/1/2 1/2/3 2/3/4

第一阶段: 设将 s2 箱货物(s1=0,1,2,3,4,5,6)分配给 1 售货店、2 售货店、3 售货店和 4 售货 店时,则最大盈利值为:f1(s1)=max[ P1(x1)+ f2(s1-x1) ] 其中,x1=0,1,2,3,4,5,6 x1 s1 P1(x1)+f2(s1-x1)

0 0+0 0+4 0+7 0+9 0+11 0+13 0+15

1 4+0 4+4 4+7 4+9 4+11 4+13

2

3

4

5

6

f1(s1)

x1*

0 1 2 3 4 5 6

6+0 6+4 6+7 6+9 6+11

7+0 7+4 7+7 7+9

7+0 7+4 7+7

7+0 7+4

7+0

0 4 8 11 13 15 17

0 0/1 1 1 1/2 1/2 1/2

按计算表格的顺序反推,可知最优分配方案有 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。 4) x1*=2,x2*=0,x3*=3,x4*=1。 5) x1*=2,x2*=1,x3*=2,x4*=1。 6) x1*=2,x2*=2,x3*=1,x4*=1。 以上 6 种最优方案的总利润均为 17。 使用 Matlab 解决上面的问题: 在 matlab 命令窗口输入下面的程序:

图 1 程序及其运行结果-1

图 2 程序及其运行结果-2

图 3 程序及其运行结果-3

m=1; A=[0 4 6 7 7 7 7]; B=[0 2 4 6 8 9 10]; C=[0 3 5 7 8 8 8]; D=[0 4 5 6 6 6 6]; for a=1:7 for b=1:7 for c=1:7 for e=1:7 if a+b+c+e==10 d(m)=A(a)+B(b)+C(c)+D(e); E(m,1)=a; E(m,2)=b; E(m,3)=c; E(m,4)=e;

m=m+1; else continue; end end end end end MAXNum=d(1); for l=1:size(d,2) if d(l)>MAXNum MAXNum=d(l); p=l; else continue; end end for l=1:size(d,2) if d(l)==MAXNum E(l,:)-1 else continue; end end MAXNum 按回车后可以得到以下的结果: ans = 1 1 3 1 ans = 1 2 2 1 ans = 1 3 1 1 ans = 2 0 3 1 ans = 2 1 2 1 ans = 2 2 1 1 MAXNum = 17 由运行结果可知最优方案有 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。

4) x1*=2,x2*=0,x3*=3,x4*=1。 5) x1*=2,x2*=1,x3*=2,x4*=1。 6) x1*=2,x2*=2,x3*=1,x4*=1。 最大总利润为 17。 这与之前的计算结果一致。


相关文章:
运筹学实验_动态规划.doc
运筹学实验_动态规划 - 实验二用 MATLAB 解决动态规划问题 问题:有一部
运筹学(二)动态规划(1-2014)_图文.ppt
运筹学(二)动态规划(1-2014) - 运筹学(二) 动态规划 动态规划 ? 动态规划运筹学的一个分支,它是 解决多阶段决策问题的一种数学方法。大 约产生...
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划 (Dynamic programming) 背包问
运筹学 动态规划_图文.ppt
运筹学 动态规划 - 动态规划是分析某一类问题的一种途径。它 不像LP那样有一个
运筹学第10章 动态规划.ppt
运筹学第10章 动态规划_数学_自然科学_专业资料。运筹学是管理类专业的一门重要
运筹学动态规划PPT_图文.ppt
运筹学动态规划PPT - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 投资分配问题 背包问题 动态规划是用来解决多阶段决策过程最优 化的...
运筹学动态规划04_图文.ppt
运筹学动态规划04 - (Dynamic programming) 1 概述 ? 1951年Bellman提出,1957《动态规划动态规划是解决多阶段决策问题的一种数学方法。 动态规...
运筹学 动态规划应用.ppt
运筹学 动态规划应用_数学_自然科学_专业资料。第七章 动态规划动态规划问题的基本概念和基本原理 动态规划模型的建立与求解 应用举例 应用举例 1。背包问题 2。...
运筹学7动态规划.ppt
运筹学7动态规划_数学_自然科学_专业资料。运筹学7动态规划 第七 章动态规划 主要内容: §7.1 多阶段决策过程的最优化 §7.2 动态规划的基本概念和基本原理 ...
运筹学上机实验---.._图文.ppt
运筹学上机实验---.. - 《运筹学实验 ?第一讲 ?第二讲 ?第三讲 ?第四讲 ?第五讲 实验软件介绍 动态规划 图与网络分析 排队论 存贮论 1 第一讲 ...
运筹学(动态规划1)_图文.ppt
运筹学(动态规划1) - 1.多阶段决策过程的最优化 一、多阶段决策问题 (Mu
运筹学5(动态规划)_图文.ppt
运筹学5(动态规划) - 第七章 动态规划 7.1 动态规划问题和基本概念 7.2 动态规划的基本原理 7.3 动态规划的应用 引言 动态规划与多阶段决策: 多阶段决策是...
运筹学动态规划习题_图文.ppt
运筹学动态规划习题 - 习题三 一、某工厂购进100台机器,准备生产A、B 两种
运筹学 动态规划应用---背包问题_图文.ppt
运筹学 动态规划应用---背包问题 - 动态规应用-- 背包问题 则 Max z
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 资源分配问题 生产计划问题 背包问题 复合系统工作可靠性问题 动态规划是用...
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划(Dynamic Programming) 动态规划是美国数学家Bellman创立的。Bellman50年代执教于普林 斯顿和斯坦福大学,后进入兰德(Rand)研究所...
运筹学课件动态规划_图文.ppt
运筹学课件动态规划 - 第十章 动态规划(DP) Dynamic Program
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划 第1页 1.动态规划的产生 动态规划运筹学的一个重要分支,它是解决多阶 段决策过程最优化的一种数学方法。 动态规划产生于20世纪50...
运筹学实验报告.doc
运筹学实验报告 - 西华大学能源与环境学院学生上机实验报告 西华大学上机实验报告 课程名称:运筹学 指导教师: 实验名称:图论、动态规划求解 年级/专业:09 水利 1 ...
运筹学实验指导书14-15-1.doc
-2- 《运筹学实验指导书 实验二 1 实验目的和任务 图论、动态规划求解 目