管理运筹学07动态规划.ppt

《管理运筹学07动态规划.ppt》由会员分享，可在线阅读，更多相关《管理运筹学07动态规划.ppt（57页珍藏版）》请在三一办公上搜索。

1、2023/11/4,1.多阶段决策过程2.Bellman最优性原理3.动态规划的数学描述4.例6.15.确定性动态规划问题6.随机性动态规划问题,第七章 动态规划,2023/11/4,多阶段决策过程,多阶段决策问题是指这样一类问题，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，从而使整个过程达到最佳的活动效果。任何一个阶段(Stage，决策点)都是由输入(Input)、决策(Decision)、转移律(Transformation)和输出(output)构成的，如图6-1(a)所示。由于每一阶段都对应一个决策，所以每一阶段都应存在一个衡量决策效益大小的指标函数，这一指标函数称

2、为阶段指标函数，用gn表示。显然gn是状态变量sn和决策变量dn的函数，即gn=rn(sn,dn)，如图6-1(b)所示。,2023/11/4,多阶段决策过程,2023/11/4,多阶段决策过程,2023/11/4,Bellman最优性原理,作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优子策略。简而言之，一个最优策略的任一子策略都是最优子策略。,2023/11/4,动态规划的数学描述,1.阶段2.状态3.决策 4.状态转移律5.策略与子策略6.阶段指标函数7.过程指标函数8.最优指标函数,2023/11/4,阶段,在多阶

3、段决策过程中，决策点将整个过程划分为若干部分，其中的每一部分即为一个阶段。描述阶段的变量称为阶段变量，常用 k 来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，一个N 个阶段的多阶段决策问题其阶段变量 k=1，2，N。,2023/11/4,状态,状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。状态反映前面各阶段决策的结局，又是本阶段决策的出发点和依据。状态是各阶段信息的传递点和结合点，各阶段的状态通常用状态变量Sk来描述。作为状态应具有这样的性质：在某阶段的状态给定后，该阶段以后过程的发展不受此阶段以前各阶段状态的影响。换句话说，过程的历史只能通过当前的状态

4、来影响未来，当前的状态是过程以往历史的一个总结。这个性质称为无后效性或健忘性。,2023/11/4,决策,决策是指决策者在若干可行方案中所作出的选择。决策变量dk(Sk)表示第k 阶段、状态为Sk时的决策。决策变量的取值会受到一定的限制，用Dk(Sk)表示第k 阶段、状态为Sk 时决策变量允许的取值范围，称为允许决策集合，因而有dk(Sk)Dk(Sk)。,2023/11/4,状态转移律,状态转移律是确定由一个状态到另一个状态演变过程的关系式，这种演变的对应关系记为Sk+1=Tk(Sk,dk)。,2023/11/4,策略与子策略,各阶段决策所组成的决策序列称为一个策略，具有N个阶段的动态规划问题

5、的策略可表示为d1(S1),d2(S2),dN(SN)。从某一阶段开始到过程终点为止的决策序列，称为子过程策略或子策略。从第k个阶段起的子策略可表示为dk(Sk),dk+1(Sk+1),dN(SN)。,2023/11/4,阶段指标函数,阶段指标函数是对应某一阶段决策的效率度量，用gk=rk(Sk,dk)来加以表示。,2023/11/4,过程指标函数,过程指标函数是用来衡量所实现过程优劣的数量指标，它是定义在全过程（策略）或后续子过程（子策略）上的数量函数。过程指标函数常用Rk,N 来表示，构成动态规划的过程指标函数应具有可分性并满足递推关系，即Rk,N 可表示为rk 和Rk+1,N二者的函数。

6、最常见的过程指标函数与阶段指标函数的关系有如下两种：1.过程指标函数是阶段指标函数的和，此时Rk,N=rk+Rk+1,N 2.过程指标函数是阶段指标函数的积，此时Rk,N=rk Rk+1,N,2023/11/4,最优指标函数,2023/11/4,A B C D B1 12 9 C1 15 6 A 4 B2 20 D 8 16 10 C2 16 B3 9,例1,2023/11/4,例1的构模,阶段：k=1,2,3状态：选各阶段所处的位置为状态变量，因此有S1=A。决策：所选择的路线；D1(S1)=B1,B2,B3 状态转移：目前状态一定，选择的线路一定，下一个状态一定。阶段指标函数：该阶段行进的

7、路程过程指标函数：阶段指标函数的和最优指标函数：fk(Sk)=minrk+fk+1(Sk+1)其中，边界条件fk+1(Sk+1)=0。,2023/11/4,例1的求解,K=3时：f3(C1)=min15=15,C1 Df3(C2)=min16=16,C2 DK=2时：f2(B1)=min12+15,9+16=25,B1 C2 f2(B2)=min20+15,16+16=32,B2 C2f2(B3)=min10+15,9+16=25,B3 C1或B3 C2 K=1时：f1(A)=min6+25,4+32,8+25=31,A B1 C2 D,2023/11/4,确定性动态规划问题,给出Sk 和dk

8、的取值后，状态Sk+1的取值唯一确定的动态规划问题称为确定性动态规划问题。确定性动态规划有广泛的应用领域，这些领域可概括为：1.最短路问题：见117页例7-1 2.资源分配问题 3.存贮控制问题 4.非线性规划问题,2023/11/4,资源分配问题,例7-2:第119页某公司拟将500万元的资本投入所属的甲、乙、丙三个工厂，各工厂获得投资后年利润将有相应的增长，一定投资下的利润增长额如下表所示，试确定最优的投资分配方案，使公司年利润增长额最大。投资(百万元)1 2 3 4 5 甲 0.3 0.7 0.9 1.2 1.3 乙 0.5 1.0 1.1 1.1 1.1 丙 0.4 0.6 1.1 1

9、.2 1.2,2023/11/4,例7-2的求解,按工厂分为三个阶段：甲 乙 丙 k：1 2 3 设Sk为第k个工厂至第3个工厂可利用的投资额，xk为第k个工厂获得的投资额，则Sk+1=Sk-xk。因而有最优指标函数：fk(Sk)=maxrk(xk)+fk+1(Sk-xk)f4(S4)=0,2023/11/4,例7-2的求解,k=3：f3(S3)=maxr3(x3)+f4(S4)=maxr3(x3)S3 0 1 2 3 4 5*x3 0 1 2 3 4 4,5f3(S3)0 0.4 0.6 1.1 1.2 1.2 k=2：f2(S2)=maxr2(x2)+f3(S2-x2),2023/11/4

10、,例7-2的求解,x2 r2(x2)+f3(S2-x2)S2 0 1 2 3 4 5 f2(S2)*x2 0 0+0 0 0 1 0+.4.5+0 0.5 1 2 0+.6.5+.4 1+0 1.0 2 3 0+1.1.5+.6 1+.4 1.4 2 4 0+1.2.5+1.1 1+.6 1.1+.4 1.1=0 1.6 1,2 5 0+1.2.5+1.2 1+1.1 1.1+.6 1.1+.4 1.1+0 2.1 2,2023/11/4,例7-2的求解,k=1：f1(S1)=maxr1(x1)+f2(S1-x1)x1 r1(x1)+f2(S1-x1)S1 0 1 2 3 4 5 f1(S1)

11、*x1 5 0+2.1.3+1.6.7+1.4.9+1.0 1.2+0.5 1.3+0 2.1 0,2 然后按计算表格的顺序反推算，可得如下两个最优分配方案：1.x1=0 S2=S1-x1=5-0=5 x2=2S3=3x3=3 2.x1=2，x2=2，x3=1,2023/11/4,第121页例7-3,机器负荷分配问题：某种机器可在高、低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为g=8u1，其中u1为投入高负荷生产的机器数量，年完好率为a=0.7；在低负荷下生产的产量函数为h=5y，其中y为投入低负荷生产的机器数量，年完好率为b=0.9。假定开始生产时完好的机器数量为S1=100

12、0台，试问每年应如何安排机器在高、低负荷下生产，才能使机器在五年里生产的产品总量最多。,2023/11/4,例7-3的求解,构造动态规划模型：设阶段序数k表示年度，状态变量Sk 为第k年初拥有的完好机器数量，同时也是第k-1年度末时的完好机器数量。决策变量uk为第k年度中分配到高负荷下生产的机器数量，于是Sk-uk为第k年度中分配到低负荷下生产的机器数量。状态转移方程：Sk+1=auk+b(Sk-uk)=0.7uk+0.9(Sk-uk)允许决策集合：Dk(Sk)=0ukSk 设vk(Sk,uk)为第k年度的产量，则vk=8uk+5(Sk-uk)过程指标函数：V1,5=vk(Sk,uk)边界条件

13、：f5(S6)=0最优递推函数：fk(Sk)=max 8uk+5(Sk-uk)+fk+1 0.7uk+0.9(Sk-uk),2023/11/4,例7-3的求解,K=5:f5(S5)=max 8u5+5(S5-u5)+f6 0.7u5+0.9(S5-u5)=max 8u5+5(S5-u5)=max 3u5+5S5f5(S5)是关于u5的单调增函数*u5=S5 f5(S5)=8S5 K=4:f4(S4)=max 8u4+5(S4-u4)+f5 0.7u4+0.9(S4-u4)=max 8u4+5(S4-u4)+80.7u4+0.9(S4-u4)=max 1.4u4+12.2S4f4(S4)是关于u

14、4的单调增函数*u4=S4 f4(S4)=13.6S4,2023/11/4,例7-3的求解,依此类推可求得：*u3=S3 f3(S3)=17.5S3*u2=0 f2(S2)=20.8S2*u1=0 f1(S1)=23.7S1=23700(件)计算结果表明，前两年应把全部完好设备均投入低负荷生产；而后三年应把全部完好设备均投入高负荷生产。这样所得的产量最高，其最高产量为23700件。各年年初的状态为：S1=1000(台)，S2=900，S3=810，S4=567 S5=397，S6=278上述讨论终端状态S6 是自由的，如果在终端也附加一个约束条件，如在五年结束时完好的机器数不低于500台(上面

15、只有278台)，问应如何安排生产？,2023/11/4,存贮控制问题,例7-4:第124页 某鞋店销售一种雪地防潮鞋，以往的销售经历表明，此种鞋的销售季节是从10月1日至3月31日。下一个销售季节各月的需求量预测值为：月 份 10 11 12 1 2 3需求(双)40 20 30 40 30 20 该鞋店直接从生产商进货，基础进货价为每双4美元。进货批量有10、20、30、40和50双五种规模，对应不同的进货批量享受一定的价格折扣，具体数值如下：批 量 10 20 30 40 50 折扣(%)4 5 10 20 25,2023/11/4,例7-4的求解,假设需求是按一定速度均匀发生的，订货不需

16、要时间，但订货只能在月初办理，每次订货的费用为10美元。月存贮费用是按每月底鞋的存量计算的，每双0.2美元。由于订货不需要时间，所以销售季节以外的月份无存货。试确定最佳的进货方案，以使总的销售费用最小。阶段：k=1,2,3,4,5,6状态：Sk 代表第k月初鞋的存量决策变量：dk 代表第k月鞋的采购量状态转移律：Sk+1=Sk+dk-Dk，S1=S7=0费用函数：rk(Sk,dk)=(dk)+0.2(Sk+dk-Dk)，其中(dk)为订货费用，订货费用由两部分构成，一部分是固定的采购费10美元，另一部分是货款，dk=0时(dk)=0。最优指标函数：fk(Sk)=min(dk)+0.2(Sk+d

17、k-Dk)+fk+1(Sk+1),2023/11/4,例7-4的求解,K=6(三月):S6 0 10 20*d6 20 10 0f6(S6)=(*d6)86 48 0K=5(二月):d5 0 10 20 30 40 50*d5 f5(S5)S5 0 204 188 164 50 164 10 172 168 142 40 142 20 134 136 122 30 122 30 86 98 90 0 86 40 50 52 0 50 50 4 0 4,2023/11/4,例7-4的求解,K=4(一月):d4 0 10 20 30 40 50*d4 f4(S4)S4 0 302 304 40 3

18、02 10 282 282 286 30,40 282 20 250 262 264 252 20 250 30 212 230 244 230 218 10 212 40 164 192 212 210 196 170 0 164 50 144 174 178 176 152 0 144 60 126 140 144 132 0 126,2023/11/4,例7-4的求解,K=3(十二月):d3 0 10 20 30 40 50*d3 f3(S3)S3 0 420 422 414 50 414 10 388 402 392 384 50 384 20 350 370 372 362 332

19、50 332 30 302 332 340 342 310 314 0 302 40 284 302 310 290 292 298 0 284,2023/11/4,例7-4的求解,K=2(十一月):d2 0 10 20 30 40 50*d2 f2(S2)S2 0 500 504 474 468 50 468 10 462 472 454 446 452 40 446 K=1(十月):d1 0 10 20 30 40 50*d1 f1(S1)S1 0 606 608 40 606,2023/11/4,例7-4的求解,利用状态转移律，按上述计算的逆顺序推算，可得如下最优策略：十月份40双 十一

20、月份50双 十二月份0双 一月份40双 二月份50双 三月份0双最小的销售费用为606美元。,2023/11/4,非线性规划问题,2023/11/4,例7-5的求解,阶段：按问题的变量个数划分阶段k=1，2，3状态：S1=c，S2，S3 决策变量：x1，x2，x3状态转移律：Sk+1=Sk-xk允许决策集合：0 xk Sk 最优指标函数：fk(Sk)=maxrk(xk)fk+1(Sk+1)边界条件：fk+1(Sk+1)=1,2023/11/4,例7-5的求解,2023/11/4,例7-5的求解,2023/11/4,随机性动态规划问题,给出Sk 和dk的取值后，状态Sk+1的取值不是唯一确定的，

21、而是具有某种概率分布的随机变量(此概率分布由状态和决策唯一确定)，这类动态规划问题称为随机性动态规划问题。下面就通过三个例题来介绍一下随机性动态规划问题的应用。1.例1 2.例2 3.例3,2023/11/4,例1,某公司承担一种新产品试制任务，合同要求三个月内交出一台合格的样品，否则将负担1500元的经济赔偿。据估计，试制时投产一台得到合格样品的概率是1/3，投产一批的准备结束费用为250元，每台试制费用为100元。若投产一批全都不合格，可再投产一批，但每投一批的试制周期为一个月。要求确定每批投入的批量，使总的试制费用（包括可能的赔偿损失）期望值最小。阶段：k=1，2，3状态：Sk=1 表示

22、第k个月初尚未得到合格样品 Sk=0 表示第k个月初已经得到了合格样品决策变量：dk 表示第k个月初投产试制的台数,2023/11/4,例1的求解,2023/11/4,例1的求解,2023/11/4,例1的求解,2023/11/4,例1的求解,2023/11/4,例2,某厂生产上需要在近五周内采购一批原料，估计在未来五周内价格会有一定的波动，各种价格及其出现的概率如下表所示，试确定在哪一周以什么价格购入原料，才能使采购价格的期望值最小。价格：500 600 700 概率：0.3 0.3 0.4,2023/11/4,例2的求解,阶段：k=1,2,3,4,5表示各周状态：yk 代表第k周的实际价格

23、决策变量：xk=1代表第k周决定采购 xk=0代表第k周决定等待ykE：第k周决定等待，对应最优子策略采购价格的期望值最优指标函数：fk(yk)=min yk,ykEykE=E fk+1(yk+1)=0.3 fk+1(500)+0.3 fk+1(600)+0.4 fk+1(700)fk(yk)=yk 时 xk=1，代表以价格yk采购；fk(yk)=ykE 时 xk=0，代表等待。,2023/11/4,例2的求解,k=5：对于最后一周，如果所需的原料尚未买入，则无论市场价格如何都必须采购，因此有：f5(500)=500，f5(600)=600，f5(700)=700k=4：y4E=0.3 f5(

24、500)+0.3 f5(600)+0.4 f5(700)=610 f4(y4)=min y4,y4E=500，y4=500(采购)=600，y4=600(采购)=610，y4=700(等待)同理可求得:,2023/11/4,例2的求解,k=3：y3E=0.3 f4(500)+0.3 f4(600)+0.4 f4(700)=574 f3(y3)=min y3,y3E=500，y4=500(采购)=574，y4=600(等待)=574，y4=700(等待)k=2：y2E=0.3 f3(500)+0.3 f3(600)+0.4 f3(700)=551.8 f2(y2)=min y2,y2E=500，

25、y4=500(采购)=551.8，y4=600(等待)=551.8，y4=700(等待)k=1：y1E=0.3 f2(500)+0.3 f2(600)+0.4 f2(700)=536.3 f1(y1)=min y1,y1E=500，y4=500(采购)=536.3，y4=600(等待)=536.3，y4=700(等待),2023/11/4,例3,某矿山机械中有一易损部件，已知该部件损坏的概率与其所使用的周数有关。如该部件已使用了m周，则在下一周生产中损坏的概率为pm。有两种部件更新方法：一是不管是否损坏，使用若干周后就更新；二是在生产中损坏时才更新。前者的更新费用为cr，后者的更新费用为cf(

26、cr cf)。已知：p0=0.05，p1=0.2，p3=0.7，p4=1 cr=1000，cf=2000 问：在长期生产的情况下，应采取什么样的更新方法，才能使总的部件更新费用最小？,2023/11/4,例3的求解,解：这是一个不定期的动态规划问题，用fn(m)表示该部件已使用了m周还要继续使用n周的最小期望费用。对更新后已使用了m周的部件，若不管是否损坏都决定更新，则期望费用为：fn(0)+cr；若只要不损坏就继续使用，可能出现两种情况，即部件在下一周内损坏或不损坏，则期望费用为：(1-pm)fn-1(m+1)+pmcf+fn(0)由此：fn(m)=minfn(0)+cr；(1-pm)fn-1(m+1)+pmcf+fn(0)其中：,2023/11/4,例3的求解,2023/11/4,例3的求解,2023/11/4,例3的求解,2023/11/4,例3的求解,2023/11/4,例3的求解,2023/11/4,例3的求解,2023/11/4,例3的求解,由上述计算可知，在长期生产的情况下，当一个部件已经使用三周时，不管它是否损坏都应进行更新，这样可使总费用的期望值最小。,