基于MATLAB的动态规划常用算法的实现

研究生、运筹学

第7卷　第4期太原师范学院学报(自然科学版)　2008年12月　JOURNALOFTAIYUANNORMALUNIVERSITY(NaturalScienceEdition)　　Dec.2008Vol.7No.4

基于MATLAB的动态规划常用算法的实现

孙　宝　王希云

(太原科技大学数学系,山西太原030024)

　　〔摘要〕　运用MATLAB编程实现了动态规划的逆序、顺序、双向混合算法,并分别应用于求解几类典型问题,验证了该方法的有效性,同时表明该程序对求解动态规划多类典型问题是通用的,丰富了MATLAB优化工具箱,具有一定的应用价值.

〔关键词〕　动态规划;逆序算法;顺序算法;混合双向算法;MATLAB

〔文章编号〕　1672-2027(2008)04-0026-05　〔中图分类号〕　O221.3　〔文献标识码〕　A

0　引言

动态规划(DynamicProgramming)是求解决策过程最优化的有效数学方法[1].它是根据“最优决策的任何截断仍是最优的”这一原理,通过将多阶段决策过程转化为一系列单阶段问题,逐个求解的优化求解方法.目前常用的方法有逆序、顺序以及双向混合算法.MATLAB是决策系统的优化计算和设计的有力工具,但该工具箱中尚无动态规划计算的程序文档.

本文通过求解几类动态规划典型问题将三种常用算法用Matlab实现,体现了程序的通用性,拓展了MATLAB语言的相关程序,克服了该程序使用的局限性,提供了求解相关动态规划问题的有效工具,丰富了MATLAB优化工具箱.

1　动态规划的基本模型

实际中,要构造一个标准的动态规划模型,通常需要采用以下几个步骤:

1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段.这些阶段必须是有序的或者是可排序的(即无后向性),否则,应用无效.

2)选择状态:将问题发展到各个阶段时所处的各种客观情况用不同的状态表示,称为状态.状态的选择要满足无后效性和可知性,即状态不仅依赖于状态的转移规律,还依赖于允许决策集合和指标函数结构.

3)确定决策变量与状态转移方程:当过程处于某一阶段的某个状态时,可以做出不同的决策,描述决策的变量称为决策变量.在决策过程中,由一个状态到另一个状态的演变过程称为状态转移.

4)写出动态规划的基本方程:动态规划的基本方程一般根据实际问题可分为两种形式,逆序形式和顺序形式.动态规划基本方程的逆序形式为:

fk(xk)=u∈D(x)kkk[2]opt{vk(xk,uk)+fk+1(xk+1)},k=n,n-1,…,2,1

边界条件:fn+1(xn+1)=0或fn(xn)=vn(xn,un)

其中第k阶段的状态为xk,其决策变量uk表示状态处于xk+1的决策,状态转移方程为xk+1=Tk(xk,uk),k阶段的允许决策集合记为Dk(xk),vk(xk,uk)为指标函数.

当求解时,由边界条件从k=n开始,由后向前逆推,逐阶段求出最优决策和过程的最优值,直到最后求出f1(x1)即得到问题的最优解.

类似地,动态规划基本方程的顺序形式为:

14

(),.

研究生、运筹学

　第4期　　　　　　　　　　　孙　宝等:基于MATLAB的动态规划常用算法的实现27

fk(xk+1)=u∈D(xkkoptk+1){vk(xk+1,uk)+fk-1(xk)},k=1,2,…,n-1,n

边界条件:f0(x1)=0

　　不同于以上单向递推算法的双向混合算法的基本方程为:

ffk(xk+1)=max/min[Vk(xk+1,uk)+ffk-1(xk)],k=1,2,…

fbj(yj)=max/min[Vj(yj,uj)+fbj+1(yj+1)],j=n,n-1,…

始端条件:ff0(x1)=0;xk=Tk(xk+1,uk)

终端条件:fbn+1(yn+1)=0;yj+1=TJ(yj,j).

2　几类典型问题的实现

本段将针对几类动态规划典型问题利用三种常用算法及Matlab程序实现其结果.下面以资源分配问题为例来具体说明求解过程.

2.1　建立动态规划模型

1)把问题的演变过程划分为恰当的阶段.

将A,B,C,D四个要害划分为4个阶段k=4.

2)选择状态变量,使之既能描述过程的演变又满足无后效性.令状态量xk为第k个要害处应派往的巡逻队数.

3)选择决策变量uk及相应的允许决策集合

Dk(xk)={uk 2≤uk≤4}(k=1,2,3,4).

　　4)写出状态转移方程

状态转移方程:xk+1=xk-uk.

5)写出指标函数

4

指标函数为:Vk,4=

出的巡逻队数为uk.

6)写出基本方程∑p(u)kki=k用pk(uk)表示k阶段派

先考虑给D部位派巡逻队,k=4

基本方程为:f4(x4)=min{p4(x4)+f5(x5)},

f5(x5)=0

2.2　算法主程序框图(逆序算法为例,见图1)

在这里仅以动态规划逆序算法进行讨论,顺序算法类

似.对于各个阶段的子问题的求解方法基本都是相同的,

在当前阶段的所有子问题求得最优决策以后,通过状态转

移方程可以确定出下一阶段的状态和允许状态集合,从而

可以在决策集合上来寻求这个新阶段的最优决策.从第n

个阶段出发,直到第一个阶段为止,即可得到全过程的最

优决策.

2.3　逆序、顺序、双向混合算法的实现结果[3]

2.3.1　基于MATLAB的动态规划逆序算法的实现

复杂系统可靠性问题描述:

某电子设备由5种元件1,2,3,4,5组成,其可靠性分

别为0.9,0.8,0.5,0.7,0.6.为保证电子设备系统的可靠

性,同种元件可并联多个.现允许设备使用元件的总数为

15,.图1　逆序算法程序1Te

研究生、运筹学

28太原师范学院学报(自然科学版)　　　　　　　　　　　　　　　第7卷　

表1　复杂系统可靠性问题

Table1　Theproblemofcomplexsystemreliability

基于MATLAB的动态规划逆序算法对复杂系统可靠性问题的实现

目标函数

状态转移方程

决策函数

指标函数

5种元件分别并联的个数

系统总可靠性最优结果functiony=ObjFun(v,f)functiony=TransFun(k,x,u)functionu=DeciseFun(k,x)functionv=SubObjFun(k,x,u)2,2,4,3,40.8447

　　资源分配问题描述:

某警卫部门共有12支巡逻队,负责4个要害部位A,B,C,D的警卫巡逻。对每个部位派出2～4支巡逻队,并且派出的巡逻队数量不同,各部位预期在一段时期内可能造成损失有差别,具体数字如下.问该警卫部门应往各部位分别派多少巡逻队,才能使总的预期损失最小.

部位　　　A　　　B　　　C　　　D

队数

2

3

4181410383531242221343125

表2　资源分配问题

Table2　Theproblemofresourceallocation

基于MATLAB的动态规划逆序算法对资源分配问题的实现

目标函数

状态转移方程

决策函数

指标函数

各部位分别派往的队数

预期的最小损失functiony=ObjFun(v,f)functiony=TransFun(k,x,u)functionu=DeciseFun(k,x)functionv=SubObjFun(k,x,u)4,2,2,497

2.3.2　基于MATLAB的动态规划顺序算法的实现

任务均衡问题描述:

现有4种不同的车床1,2,3,4,同时加工500件相同的零件.各车床加工一个零件的时间分别为0.5h,0.1h,0.2h,0.05h.问如何给4个车床分配加工零件数目,使完工时间最短?

表3　任务均衡问题

Table3　Theproblemoftaskbalance

基于MATLAB的动态规划顺序算法对任务均衡问题的实现

目标函数functiony=ObjFun(v,f)

状态转移方程functiony=TransFun(k,x,u)

决策函数functionu=DeciseFun(k,x)

指标函数functionv=SubObjFun(k,x,u)

4种车床同时加工的数目27,135,67,271

最短完工时间h13.55

　　资源分配问题描述:

某警卫部门共有12支巡逻队,负责4个要 …… 此处隐藏：4987字，全部文档内容请下载后查看。喜欢就下载吧 ……