您好,欢迎访问三七文档
§1多阶段的决策问题§2最优化原理与动态规划的数学模型§3离散确定性动态规划模型的求解§4离散随机性动态规划模型的求解§5一般数学规划模型的动态规划解法AB1B3C1C2C3D1D2EB2575632451514633334【例1】从A至E需经B、C、D,问如何行走,路程最短?§1多阶段的决策问题【例2】某工厂根据合同要求在未来半年中需提供货物数量如表中所示,表中数字为月底交货数量。该厂的生产能力为每月400件,其仓库的存货能力为3百件。已知每百件货物的生产费用为10千元,在进行生产的月份,工厂要支出固定费用4千元,仓库保管费用为每百件货物每月1千元,假定开始及6月底交货后均无存货,试问每个月应该生产多少件产品,才能既满足交货任务又使总费用最小?月份交货数量(件)123456100200500300200100生产生产生产库存库存库存库存费用费用费用1月2月6月可看成6个阶段的决策:【例3】某公司承担一种新产品试制任务,合同要求三个月内交出一台合格的样品,否则将负担1500元的赔偿费。试制时投产一台成功的概率为1/3,投产一批的准备费用为250元,每台试制费用为100元。若投产一批后全部不合格,可再投产一批试制,但每投产一批需要一个月的周期。问每批应该投产多少台,可使总的费用(包括可能发生的赔偿费用)期望值最小?第1月第2月第3月试制试制试制合格否?合格否?合格否?YYYSTOPSTOPSTOPNN赔偿费N多阶段决策问题的特点:①决策过程可划分为若干个互相联系的阶段;②在每一阶段分别对应着一组可以选取的决策;③当每个阶段决策选定以后,活动过程也随之确定。许多多阶段决策问题表现出明显的时序性,故体现出“动态”的特点,所以是动态规划研究的主要对象。某些静态问题,当采用动态规划的方法求解时,也会使问题的处理变得简单。§2最优化原理与动态规划的数学模型2-1动态规划的解题思路将一个n阶段的决策问题转化为依次求解n个具有递推关系的单阶段的决策问题。动态规划问题的计算中较多采用逆序算法AB1B3C1C2C3D1D2EB2575632451514633334NextSolv1NextSolv2NextSolv3逆序求解1)k=4,由递推方程知f4(x4)=min{v4(s4,x4)+f5(x5)},而f5(x5)=0为边界条件f4(x4=D1)=min{D1E+f5(x5)}=3,x4*(D1)=D1Ef4(x4=D2)=min{D2E+f5(x5)}=4,x4*(D2)=D2E∴2)k=3,f3(x3)=min{v3(s3,x3)+f4(x4)},f3(x3=C1)=minC1D1+f4(D1)C1D2+f4(D2)1+34+4=min=4,x3*(C1)=C1D1f3(x3=C2)=minC2D1+f4(D1)C2D2+f4(D2)6+33+4=min=7,x3*(C2)=C2D2Backf3(x3=C3)=minC3D1+f4(D1)C3D2+f4(D2)3+33+4=min=6,x3*(C3)=C3D13)k=2,f2(x2)=min{v2(s2,x2)+f3(x3)},f2(x2=B1)=minB1C1+f3(C1)B1C2+f3(C2)B1C3+f3(C3)7+45+76+6=min=11,x2*(B1)=B1C1f2(x2=B2)=minB2C1+f3(C1)B2C2+f3(C2)B2C3+f3(C3)=minx2*(B2)=B2C1,或x2*(B2)=B2C33+42+71+6=7,Backf2(x2=B3)=minB3C1+f3(C1)B3C2+f3(C2)B3C3+f3(C3)5+41+75+6=min=8,x2*(B3)=B3C2f1(x1=A)=minAB1+f2(B1)AB2+f2(B2)AB3+f2(B3)2+115+73+8=min=11,x1*(A)=AB34)k=1,f1(x1)=min{v1(s1,x1)+f2(x2)},最优策略:A——B3——C2——D2——E,最短距离:f(A)=11∴Back(1)阶段(stage):指一个问题需要做出决策的步数。k——阶段变量。(2)状态(state):某阶段初始状况。既反映前面各阶段决策的结局,又是本阶段作出决策的出发点和依据。是动态规划中各阶段信息的传递点和结合点。sk——第k阶段状态变量。特征:①反映研究对象的演变特征;②包含到达这个状态前的足够信息,并具有无后效性;或称决策的相互独立性;③状态变量具有可知性,当决策确定后,到达的状态是可以测知的。描述状态所必须使用的变量数,称动态规划的维数。2-2动态规划的基本概念(3)决策(decision):指在某阶段初从给定的状态出发,决策者在面临的若干种不同的方案中所做出的选择。决策变量xk(sk)∈Dk(sk)——允许决策集合,xk(sk)取值范围。要点:①决策变量是对活动过程控制的手段;②决策变量取值可以是连续型的,也可以是离散型的;③允许决策集合相当于可行域。(4)策略(policy)与子策略(subpolicy):各阶段决策组成的序列总体称为策略;从某一阶段开始到过程最终的决策序列称为子策略。n阶段策略可记为{x1(s1),x2(s2),…,xn(sn)},子策略可记为{xk(sk),xk+1(sk+1),…,xn(sn)}。(5)状态转移律:状态参数变化的规律。从第k阶段的某一状态值sk出发,当决策变量xk的取值确定之后,下一阶段的状态值sk+1按某种规律T(sk,xk)确定。第k+1阶段状态是第k阶段状态sk和变量xk的函数sk+1=T(sk,xk),又称状态转移方程。说明:①当sk,xk确定后,sk+1取值唯一确定,则为确定性多阶段决策问题;②当sk,xk确定后,sk+1取值为具有某种概率分布的随机变量,则称为随机性多阶段决策问题。(6)指标函数:决策所产生的效益的度量函数。分如下的几类:①vk(sk,xk)——阶段指标函数。②Vk,n(sk,xk,sk+1,xk+1,…,sn,xn)——过程指标函数。③f(sk)=optVk,n——最优指标函数,只与sk有关。Opt——optimize,可以是max,或者min。说明:为便于计算,指标函数应具有递推性。(7)边界条件:对过程最终状态时的效益值表示。即当k=n+1时,f(sk+1)=?上述基本概念可用下述模型示意图表示:状态sksk+1sk+2状态状态决策xk(sk)决策xk+1(sk+1)指标函数vk(sk,xk)指标函数vk+1(sk+1,xk+!)T(sk,xk)T(sk+1,xk+1)k+1阶段k阶段动态规划概念模型示意图贝尔曼(R.Bellman)原理:作为整个过程的最优策略具有这样性质:无论过去的状态和决策如何,对前面所形成的状态而言,余下的诸决策必构成最优策略。动态规划的基本方程(递推方程):Vk,n=vi(si,xi),i=knfk(sk)=optvk(sk,xk)+fk+1(sk+1)Vk,n=vi(si,xi),i=knfk(sk)=optvk(sk,xk)·fk+1(sk+1)xk(sk)∈Dk(sk)xk(sk)∈Dk(sk)当当2-3最优化原理与动态规划的数学模型动态规划问题的模型表述动态规划模型属于算法类模型,故借助于对其相关概念的定义来表述。内容如下:(1)阶段数:k=1,2,····,n(2)状态变量:sk——?(3)决策变量:xk——?,允许决策集合D(sk)(4)状态转移律:sk+1=T(sk,xk)(5)阶段指标函数:vk(sk)——?(6)基本方程:fk(sk)=?(7)边界条件:fn+1(sn+1)=?•逆序解法:从问题的最后一个阶段开始,逆多阶段决策的实际过程反向寻优2-4逆序解法与顺序解法•顺序解法:从问题的最初阶段开始,同多阶段决策的实际过程顺序寻优动态规划问题的逆序算法:1.建立模型:(1)阶段数:k=1,2,3,4(2)状态变量:sk——第k阶段的位置点。(3)决策变量:xk——第k阶段选择的行走路线,允许决策集合D(sk)——sk位置时可选择的线路集合。(4)状态转移律:sk+1=T(sk,xk)——采取xk决策后,位置变化的规律。(5)阶段指标函数:vk(sk,xk)——选择xk决策后产生的距离。(6)基本方程:fk(sk)=min{vk(sk,xk)+fk+1(sk+1)}(7)边界条件:f5(s5=E)=0确定性随机性离散型连续型状态变量取值特征过程演变特征若阶段数固定,则为定期型;若阶段数不固定,则称为不定期型2-5动态规划模型的分类【例4】某一警卫部队共有9支巡逻队,负责3个要害部门A、B、C的警卫巡逻。对每个部位可分别派出2~4支巡逻队,并且由于派出巡逻队数的不同,各部位在一段时期内可能造成的损失有差别,具体数字如表中所示。问:该警卫部门应往各部位分别派多少支巡逻队,使总的预期损失为最小?部位218382431435224103121ABC各部位预期损失表解:把对每一个部位派出巡逻队数量的决策,看成是一个阶段,可归结成3个阶段的决策问题。§3离散确定性动态规划问题的模型与求解Next1Next2Next3一、建立模型(1)阶段变量:k=1,2,3(2)状态变量:sk——第k阶段可用于分配的巡逻队数量;(3)决策变量:xk——第k阶段派出的巡逻队数量;允许决策集合Dk(sk)={2,3,4},k={1,2,3}(4)状态转移律:sk+1=sk-xk;(5)阶段指标函数:pk(xk)——预期损失函数,如表示;(6)基本方程:fk(sk)=min{pk(xk)+fk+1(sk+1)}(7)边界条件:f4(s4)=0x3f3(s3)x3*(s3)二、逆序算法求解1)k=3,对C部位,s4=s3-x3f3(s3)=min{p3(x3)+f4(s4)},而f4(s4)=0,依题意,2s39-4=5,列表计算如下:234242221234Back2)k=2,对B部位,s3=s2-x2f2(s2)=min{p2(x2)+f3(s3)}=min{p2(x2)+f3(s2-x2)},而9-4s29-2=7,列表计算如下:Backs2x2p2(x2)+f3(s2-x2)234538+2235+24--638+2135+2231+24738+2135+2131+22f2(x2)x2*(s2)5935545343)k=1,对A部位,s2=s1-x1,s1=9f1(s1)=min{p1(x1)+f2(s2)}=min{p1(x1)+f2(s1-x1)},列表计算:s1x1p1(x1)+f2(s1-x1)234918+5314+5510+59f1(x1)x1*(s1)693或4最优策略:A—3支,B—4支,C—2支;最小损失为69;A—4支,B—3支,C—2支;最小损失为69。Back【例5】某企业现有5千万元资金可用于三个项目A、B、C的技术改造建设。项目利润的预期年增长额与投资的规模有关,如表所示。问如何确定投资计划,可使利润的预期年增长额最大?项目A015344256B018354558C02037486001000200030004000项目利润预期年增长额单位:万元解:对每个项目的投资决策可看作是一个阶段,故归结为三阶段的动态规划问题。一、建立动态规划模型(1)阶段变量:k=1,2,3(2)状态变量:sk——第k阶段可用于分配的资金数量;(3)决策变量:xk——第k阶段投资数量;允许决策集合D(sk)={xk|0xksk}(4)状态转移律:sk+1=sk-xk;(5)阶段指标函数:pk(xk)——预期利润年增长额函数,如表示;(6)基本方程:fk(sk)=max{pk(xk)+fk+1(sk+1)}(7)边界条件:f4(s4)=0二、逆序算法求解1)k=3,对C项目,f3(s3)=max{p3(x3)+f4(s4)},而f4(s4)=0,依题意,0s35000,0x3s3,列表计算如下:x3f3(s3)x3*(s3)01000200030004000
本文标题:动态规划
链接地址:https://www.777doc.com/doc-5252898 .html