管理运筹学07动态规划.ppt
2023/11/4,1.多阶段决策过程2.Bellman最优性原理3.动态规划的数学描述4.例6.15.确定性动态规划问题6.随机性动态规划问题,第七章 动态规划,2023/11/4,多阶段决策过程,多阶段决策问题是指这样一类问题，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，从而使整个过程达到最佳的活动效果。任何一个阶段(Stage，决策点)都是由输入(Input)、决策(Decision)、转移律(Transformation)和输出(output)构成的，如图6-1(a)所示。由于每一阶段都对应一个决策，所以每一阶段都应存在一个衡量决策效益大小的指标函数，这一指标函数称为阶段指标函数，用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,阶段,在多阶段决策过程中，决策点将整个过程划分为若干部分，其中的每一部分即为一个阶段。描述阶段的变量称为阶段变量，常用 k 来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，一个N 个阶段的多阶段决策问题其阶段变量 k=1，2，N。,2023/11/4,状态,状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。状态反映前面各阶段决策的结局，又是本阶段决策的出发点和依据。状态是各阶段信息的传递点和结合点，各阶段的状态通常用状态变量Sk来描述。作为状态应具有这样的性质：在某阶段的状态给定后，该阶段以后过程的发展不受此阶段以前各阶段状态的影响。换句话说，过程的历史只能通过当前的状态来影响未来，当前的状态是过程以往历史的一个总结。这个性质称为无后效性或健忘性。,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个阶段的动态规划问题的策略可表示为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二者的函数。最常见的过程指标函数与阶段指标函数的关系有如下两种：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 状态转移：目前状态一定，选择的线路一定，下一个状态一定。阶段指标函数：该阶段行进的路程过程指标函数：阶段指标函数的和最优指标函数：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的取值后，状态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.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,例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)*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=1000台，试问每年应如何安排机器在高、低负荷下生产，才能使机器在五年里生产的产品总量最多。,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)边界条件：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)是关于u4的单调增函数*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台(上面只有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的求解,假设需求是按一定速度均匀发生的，订货不需要时间，但订货只能在月初办理，每次订货的费用为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+dk-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 302 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 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双 十一月份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的取值不是唯一确定的，而是具有某种概率分布的随机变量(此概率分布由状态和决策唯一确定)，这类动态规划问题称为随机性动态规划问题。下面就通过三个例题来介绍一下随机性动态规划问题的应用。1.例1 2.例2 3.例3,2023/11/4,例1,某公司承担一种新产品试制任务，合同要求三个月内交出一台合格的样品，否则将负担1500元的经济赔偿。据估计，试制时投产一台得到合格样品的概率是1/3，投产一批的准备结束费用为250元，每台试制费用为100元。若投产一批全都不合格，可再投产一批，但每投一批的试制周期为一个月。要求确定每批投入的批量，使总的试制费用（包括可能的赔偿损失）期望值最小。阶段：k=1，2，3状态：Sk=1 表示第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周的实际价格决策变量：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(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，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(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的求解,由上述计算可知，在长期生产的情况下，当一个部件已经使用三周时，不管它是否损坏都应进行更新，这样可使总费用的期望值最小。,
