《教案动态规划改.ppt》由会员分享，可在线阅读，更多相关《教案动态规划改.ppt（96页珍藏版）》请在三一办公上搜索。
1、动态规划（Dynamic Programming）,动态规划是解决复杂系统优化问题的一种方法。是解决动态系统多阶段决策过程的基本方法之一。,教学大纲:,理解动态规划基本概念、最优化原理和基本方程，通过资源分配和生产与存储等问题,学习应用动态规划解决多阶段决策问题。重点:掌握动态规划模型结构、逆序法算法原理、资源分配、设备更新、生产于存贮等问题。难点为动态规划中状态变量等的确定。,第一节 动态规划的研究对象和引例,引例1 最短路问题,多阶段决策问题的典型例子：1.生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存
2、和需求决定生产计划。,2.机器负荷分配问题：某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为g=g(u1),这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终完好的机器就为au,0a1。,在低负荷下生产时，产品的年产量h和投入生产的机器数量u2的关系为 h=h(u2),假定开始生产时完好的机器数量为s1。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。,相应的机器年完好率b,0 b1。,3.航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变
3、化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。,不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。,4.线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决，后面将详细介绍。,最短路问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A点到G点的最短距离（总费用最小）。,典型 问题:,但要便于把问题的过程能转化为多阶段决策 的过程。,状态变量的取值有一定的允许集合或范围，此
4、集合称为状态允许集合。,第二节 动态规划的基本概念和定义,1.阶段、阶段变量,把所给问题的过程，适当地分为若干个相互联系的阶段;,描述阶段的变量称为阶段变量，常用k表示；,阶段的划分，一般是按时间和空间的自然特征来划分；,2.状态、状态变量,每个阶段开始所处的自然状态或客观条件。,通常一个阶段有若干个状态。,描述过程状态的变量称为状态变量，常用sk表示第k阶段的状态。,一个数、一组数、一个向量,在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合。常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合，显然有,决定下一阶段的状态，这种决定称为决策。,在最优控制中也称为控制。,
5、描述决策的变量，称为决策变量。,决策变量是状态变量的函数。,常用uk(sk)表示第k阶段当状态为 sk时的决策变量。,3.决策、决策变量,过程的某一阶段、某个状态,可以做出不同的决定(选择),uk(sk)Dk(sk),系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决策有关。其状态转移方程如下（一般形式）,图示如下：,状态转移方程是确定过程由一个状态到另一个状态的演变过程。如果第k阶段状态变量sk的值、该阶段的决策变量一经确定，第k+1阶段状态变量sk+1的值也就确定。,4.多阶段决策过程,可以在各个阶段进行决策，去控制过程发展的多段过程；,其发展是通过一
6、系列的状态转移来实现的；,能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。,如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。,动态规划中能处理的状态转移方程的形式。,状态具有无后效性的多阶段决策过程的状态转移方程如下,无后效性(马尔可夫性),如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；,过程的过去历史只能通过当前的状态去影响它未来的发展；,构造动态规划模型时，要充分注意是否满足无后效性的要求；,状态变量要满足无后效性的要求；,由每段的决策按顺序排列组成的决策函数序列称为k子过程策略，,当k
7、=1时，此决策函数序列成为全过程的一个策略，简称策略，记为p1,n(s1).即,可供选择的策略有一定范围，此范围称为允许策略集合，用p表示。从允许策略集合中找出达到最优效果的策略称为最优策略。,5.策略:,按顺序排列的决策组成的集合；,简称子策略，记为pk,n(sk)，即,它是定义在全过程或所有后部子过程上确定的数量函数。,动态规划模型的指标函数，应具有可分离性，并满足递推关系。,常见的指标函数的形式是：,费用、成本、利润、路长等。,用Vk,n 表示之。,6.指标函数和最优值函数,用来衡量所实现过程优劣的一种数量指标，称为指标函数；,即Vk,n可以表示为sk,uk,Vk+1,n的函数。,常见的
8、指标函数的形式是：,过程和它的任一子过程的指标是它所包含的各阶段的指标和。即,无后效性的结果。,其中vj(sj)表示第 j 阶段的阶段指标。这时上式可写成,过程和它的任意子过程的指标是它所包含的各阶段的指标的 乘 积。即,则可改写成,多阶段决策过程的数学模型：（具有无后效性的多阶段决策过程）,采取最优策略所得到的指标函数值。,最优值函数：,即,可递推,多阶段决策过程的数学模型：（具有无后效性）,小结:,指标函数形式:,和、,积,无后效性,可递推,解多阶段决策过程问题，求出,f1(s1),从k到终点最优策略子策略的最优目标函数值,第三节：动态规划的基本思想和基本方程,9,最短路的特性：如果已有从
9、起点到终点的一条最短路，那么从最短路线上中间任何一点出发到终点的路线仍然是最短路。（证明用反证法）,k=5，出发点E1、E2、E3,k=2,f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3,7 5 9,u5(E2)=F2,u6(F2)=G,最优策略,用动态规划（逆序法求解的）基本特性：,一般情况,k阶段与k+1阶段的递推关系式（动态规划基本方程）,练习：写出乘积形式指标函数的动态规划基本方程。,顺序解法：实际上没有顺序法！,小结:,要具有可分离性，并满足递推关系。即,函数k（sk，uk，Vk+1,n）对于变量Vk+1，n要严格单调。,是定义在全过程和所有后部子过程
10、上的数量函数;,第四节：动态规划的理论基础和 具体迭代方 法,多阶段决策过程的特点：每个阶段都要进行决策，策略是由n个相继进行的决策构成的决策序列。前一阶段的终止状态又是下一阶段的初始状态，因此，确定阶段最优决策不能只从阶段的效应来考虑，必须是整个过程通盘考虑，整体规划。即阶段k的最优决策不应该只是本阶段效应的最优，而必须是本阶段及其所有后续阶段的总体最优。,动态规划方法的理论基础是基于R.Bellman提出的最优性原理：“一个过程的最优策略具有这样的性质：即无论其初始状态及初始决策如何，对于先前决策所形成的状态而言，余下的诸决策仍构成最优策略。”,1.理论基础,适应于用动态规划方法求解的是具
11、有无后效性的多阶段决策过程。,最优性原理的含义是：最优策略的任何一部分子策略，也是它相应初始状态的最优策略。每个最优策略只能由最优子策略构成。,动态规划的最优性定理：设阶段数为n的多阶段决策过程，其阶段编号为k=0,1,.,n-1。允许策略,是最优策略的充要条件是对任意一个k,0kn-1和s0S0，有,它是由给定的初始状态s0和子策略p0,k-1所确定的k段状态。当V是效益函数时，opt取max;当V是损失函数时，opt取min.,证明：必要性（）,充分性（）设p0,n-1=(p0,k-1,pk,n-1)为任一策略，sk为由（s0，p0,k-1）所确定的k阶段的起始状态，则有（以最大化为例）,
12、推论：若允许策略p*0,n-1是最优策略，则对任意的k,0kn-1,它的子策略p*k,n-1对于以 s*k=Tk-1(s*k-1,u*k-1)为起点的k到n-1子过程来说，必是最优策略。（注意：k段状态s*k,是由s0和p*0,k+1所确定的）,2.具体迭代方法：作为练习，请同学们根据例题，自己写出。,第五节 动态规划与静态规划之间的关系及其相关总结,动态规划解法,逆序法,顺序法,动态规划 动态规划区别 关系 静态规划 静态规划,线性规划静态规划 非线性规划,5.1 逆序（递推）法,设已知初始状态s1，最优值函数fk(sk)表示从k阶段到n阶段所得到的最大效益。以求最大化为例来说明。,当阶段k
13、=n时,可得最优决策xn=xn(sn)和最优值fn(sn)。,若D(sn)只有一个决策,则可写成 xn=xn(sn)。,具体方法如下：,当阶段k=n-1时,其中状态转移方程,得到最优决策xn-1=xn-1(sn-1)和最优值fn-1(sn-1)。,当阶段k=k时,其中状态转移方程,得最优决策xk=xk(sk)和最优值fk(sk)。如此类推，直到第一阶段。,当阶段k=1时,其中状态转移方程,得最优决策x1=x1(s1)和最优值f1(s1)。,由于初始状态s1已知,故x1=x1(s1)和f1(s1)是确定的,根据状态转移方程按照上述递推过程相反顺序推算下去，就可逐步确定出每阶段的决策及效益。,例1
14、 用动态规划的逆序法求解下面问题:,状态变量一般为累计量或随递推过程变化的量。,此问题中可设（因此可得状态转移方程）：,则有,解：,当阶段k=3时，有,当阶段k=2时，有,有两个解，其中x2=0舍去。因2阶导数在x*2处小于0，故有极大值。,当阶段k=1时，有,因此最后可得：,s3=s2-x*2=s1-x*1-x*2,与前面应用微分法一样,问如何分配投资数额才能使总效益最大?,解：可列出静态规划问题的模型如下,分阶段：分三个阶段，即k=1，2，3。确定决策变量：通常可以取静态规划中的变量为决策 变量。确定状态变量：状态变量与决策变量有密切关系，状态变量一般为累计量或随递推过程变化的量。,例2
15、某公司有资金10万元，若投资于项目(i=1,2,3)的投资额为xi时，其效益分别为,考虑效益函数的形式,状态转移方程,指标函数,最优指标函数fk(sk),基本方程,最优目标函数 f3(s3)=2s32,每一阶段可使用的资金数为状态变量sk,此问题中可设（因此可得状态转移方程）：,当阶段k=2时，有,是凹函数，最大值点只能在0，s2端点上取得，即,当阶段k=1时，有,2阶导数大于0,是凹函数，故比较0,10的端点,最优投资方案是全部资金投于第3个项目，可得最大收益200万元。,S29/2,当,当,时,时,矛盾，舍去。,（最优决策）,S29/2,2阶导数0,5.2 顺序解法 自学内容,5.3 动态
16、规划的优缺点,优点:.最优解是全局最优解。.能得到一系列（包括子过程）的最优解。.不需要对系统状态转移方程、阶段效应函数等的解析性质作任何假设。,缺点：.没有统一的标准模型和标准的算法可供使用。.应用的局限性，要求满足“无后效性”。.“维数灾难”问题。,资源分配问题生产与存贮问题设备更新问题,第九章 动 态规划应用举例,第一节 资源分配问题,1.1 多元投资分配问题 设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i 种产品，其收益为gi(xi)问应如何分配，才能使生产n种产品的总收入最大？,将数量一定的一种或若干种资源，恰当地分配给若干个使用者，使效益函数为最优。,决策集
17、合：Dk(sk)=uk|0uk=xksk,uk:分配给生产第k种产品的原料数量，即uk=xk；,sk:分配给用于生产第k种至第n种产品的原料数量；,状态转移方程：sk+1=sk-uk=sk-xk,最优值函数fk(sk):数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收益，动态规划的递推关系为：,某公司拟将5台某种设备分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为公司提供的盈利如表。问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大。,例1,解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为1，2，3。,逆推法,k=3时，0s35，x3s3,可分配的机器数量,分配
18、的机器数量,x3*(1)=1,x3*(0)=0,4,当阶段k=2时，s3=s2-x2，0s25，0 x2s2，有,结果列于下表：,f3(1-0)=f3(1),=4,f3(5-3)=f3(2),当阶段k=1时，s2=s1-x1，s1=5，0 x1s1，有,x1*(5)=0,2,结果可写成表格的形式,max,逆推到第一张表,x3*=3,x2*=2,按计算表格的顺序逆推，可知最优分配方案有两个：甲工厂分配0台，乙工厂分配2台,丙工厂分配3台。,甲工厂分配2台，乙工厂分配2台，丙工厂分配1台。以上两个分配方案所得到的总盈利均为21万元,问题：如果原设备台数是4台，求最优分配方案？如果原设备台数是3台，
19、求最优分配方案？,1.2 资源连续分配问题:一般问题的提法是,如此进行n年，如何确定投入A的资源量u1、un，使总收入最大？,此问题的静态规划问题模型为：,动态规划的逆推关系方程为：,最后求得得f1(s1)即为所求问题的最大收入。,例2 机器负荷分配问题,解：设阶段数k表示年度。,试问每年如何安排机器在高低两种负荷下的生产，可使5年内生产的产品总产量最高。,低负荷下生产的机器台数是sk-uk。,第k年度产量为,u5*=s5,f5(s5)=8 s5,u4*=s4,f4(s4)=13.6s4,u3*=s3,f3(s3)=17.55s3,u2*=0,f2(s2)=20.8s2,u1*=0,f1(s1
20、)=23.7s1,最高产量为23700。,因此最优策略为:u1*=0,u1*=0,u3*=s3,u4*=s4 u5*=s5,作业：如规定在第五年结束时完好机器数为500台，该如何安排生产？,得到,所谓生产与库存问题就是一个生产部门，如何在已知生产成本、库存费用和各阶段市场需求条件下，决定各阶段产量，使计划内的费用总和为最小的问题。很多问题可以化成此类问题来解决。,设某公司对某种产品要制定一项n个阶段的生产计划。已知它的初始库存量为零，每阶段生产该产品的数量有上限的限制；每阶段社会对该产品的需求量是已知的，公司保证供应；在n阶段末的终结库存量为零。问该公司如何制定每个阶段的生产计划，从而使总成本
21、最小？,设dk为第k阶段对产品的需求量；,Xk为第k阶段该产品的生产量；,Vk为第k阶段开始时的产品的库存量；,第二节生产与存贮问题,Ck(xk)表示第k阶段生产产品xk时的成本费用，包括生产准备成本k和产品成本axk,hk(vk,Xk)表示在第k阶段结束时,库存费用,第k阶段的成本费用为Ck(xk)+hk(vk,Xk),设某一生产部门，生产周期分为n个阶段，已知最初库存量为s1，阶段市场的需求为dk，生产的固定成本为K，单位产品的消耗费用为L，单位产品的阶段库存费用为h，仓库容量为M，阶段生产能力为B。问如何安排各阶段产量，使计划周期内的费用总和最小。,状态变量Sk选为阶段k的初始库存量，S
22、1已知，Sn+1=0。阶段k的库存量即不能超过库存容量M，也不能超过阶段k至阶段n的需求总量，即,决策变量uk选为阶段k的产量。阶段产量必须不超过生产能力和第k阶段到第n阶段的总需求减去第k阶段初的库存量，同时要大于该阶段的需求和库存量之差，即,状态转移方程为,阶段效益为阶段生产费用和库存费用之和，即,阶段k的生产费用,k阶段末的库存费用,动态规划基本方程,例 已知n=3，K=8，L=2，h=2，S1=1，M=4，S4=0（计划周期末期的库存量为0），B=6，d1=3，d2=4，d3=3，求解生产与库存问题。解：利用上述的递推方程得,S4=S3+u3-d3=0,若,若,则,则,结果见下表：,时
23、,是唯一确定的，因此,最优决策为,最优路线为 1，0，0，0最优目标函数值为42。,S2=s1+u1-3=0,S3=S2+u2-d2=0+4-4=0,某工厂生产某种产品的月生产能力为10件，已知今后4个月的产品成本及需求量如表3所示。如果本月产量超过需求量时，可以存储起来以后各月使用，一件产品的月存储费为20元，试安排月生产计划并做到：（1）保证满足每月的需求量，并规定计划期初和期末库存量为0；（2）在生产能力允许范围内，安排每月生产量计划使产品总成本（即生产费用加存储费）最低。用动态规划方法求解。,例2,个人、单位等随时均有设备更新问题。彩电、设备随着使用年限的增加而设备陈旧，处理价格愈低，
24、因此需要维修和更新的费用增加。处于各种阶段的设备总是面临保留还是更新问题。保留还是更新，应该从整个计划期间的总回收额来考虑，而不能从局部的某个阶段的回收额来考虑，是一个多阶段的决策问题。,设备更新问题提法如下（以一台机器为例）：n为计划设备使用年数。Ik(t)为第k年（阶段）机器役龄为t年的一台机器运行（再使用一年）所得的收入。Ok(t)为第k年机器役龄为t年的一台机器运行（再使用一年）时所需运行的费用（或维修费用）。Ck(t)为第k年机器役龄为t年的一台机器更新时所需更新的净费用（处理一台役龄为t的旧设备，买进一台新设备的更新净费用）。,第三节设备更新问题,建立动态规划模型如下：阶段k（k=
25、1，2，n）表示计划年限数。状态变量sk：第k年初，设备已使用过的年数，即役龄。决策变量xk：是第k年初更新（Replacement），还是保留使用（Keep）旧设备，分别用K，R表示。状态转移方程为：,阶段效益为：,为折扣因子，表示一年以后的收入是上一年的单位。要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年内总效益最大？,最优指标函数gk(sk)：表示第k年初，使用一台已用了sk年的设备，到第n年末的最大收益，动态规划的基本方程为,实际上,例：设某台新设备的年效益及年均维修费用、更新净费用如下表，试确定今后五年内的更新策略，使总效益最大。（设=1）,解：n=5,状态变量s5可取1，2，3，4，5,状态变量s4可取1，2，3，4,此时s3可取1，2，3,由于状态s2只能取1，2 所以有,由于状态s1只能取0，所以有,最优策略,某工厂共有5个单位能源供给3个车间，由于车间的设备条件不同，使用能源所能获得的收益情况也不同，具体数据如表3所示。为使工厂获得最大收益，每个车间各应分配多少单位的能源？,收益表,练习,有一卡车载重15吨，现有3种货物可运送，3种货物重量及收入如表所示。问如何装载（各种货物数量不限）使收入最大？用动态规划方法求解,练习,
