第8章动态规划第1,2节.ppt

1第1节 多阶段决策过程及实例第2节 动态规划的基本概念和基本方程运筹学（第三版）运筹学教材编写 组第8章 动态规划的基本方法清华大学出版社2第8章 动态规划的基本方法 第1节 多阶段决策过程及实例 第2节 动态规划的基本概念和基本方程 第3节 动态规划的最优性原理和最优性定理 第4节 动态规划和静态规划的关系3 动态规划（Dynamic Programming）是运筹学的一个重要分支，它是解决多阶段决策过程最优化的一种方法。美国数学家贝尔曼（R.E.Bellman）等人在50年代初提出了解决多阶段决策问题的“最优性原理”（Principle of Optimality）。1957年贝尔曼出版了专著“动态规划”，该书是动态规划的第一本著作。目前动态规划已经用于解决最优路径问题、资源分配问题、生产调度问题、设备更新问题、复合系统可靠性问题及生产过程最优控制等，并且取得了显著的效果。4 动态规划是用来解决多阶段决策过程最优动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一化的一种数量方法。其特点在于，它可以把一个个n 维决策问题变换为几个一维最优化问题，从维决策问题变换为几个一维最优化问题，从而一个一个地去解决。而一个一个地去解决。需指出：动态规划是求解某类问题的一种需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。用动态规划方法去求解。5第1节 多阶段决策过程及实例 在生产经营活动中，某些问题决策过程可以划分为若干相互联系的阶段，每个阶段需要做出决策，从而使整个过程取得最优。12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策6 各个阶段不是孤立的，而是有机联系的，也就是说，本阶段的决策将影响过程下一阶段的发展，从而影响整个过程效果，所以决策者在进行决策时不能够仅考虑选择的决策方案使本阶段最优，还应该考虑本阶段决策对最终目标产生的影响，从而做出对全局来讲是最优的决策。多阶段决策问题中，各个阶段一般是按照时间来划分的，随着时间的发展而产生各个阶段的决策，从而形成决策序列，这就是动态的含义。7 在一些与时间无关的静态问题中（如非线性规划等），可以人为地赋予时间的概念，使其成为一个多阶段决策问题，再用动态规划方法处理。当每个阶段的决策确定以后，全部过程的决策就是这些阶段决策所组成的一个决策序列，所以多阶段决策问题也称为序贯决策问题。8例例1 最短路线问题 给定一个线路网络，两点之间连线上的数字表示两点之间的距离（或费用），试求一条由A到G的铺管线路，使总距离为最短（或总费用最小）。C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G5313638766852255223333366344189例2.机器负荷分配问题 某种机器可以在高低两种不同的负荷下进行生产。某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量在高负荷下进行生产时，产品的年产量g和投入生产和投入生产的机器数量的机器数量u1的关系为的关系为g=g(u1)，这时，机器的年完这时，机器的年完好率为好率为a，即如果年初完好机器的数量为，即如果年初完好机器的数量为u，到年终，到年终完好的机器就为完好的机器就为au,0a1。在低负荷下生产时，产品的年产量在低负荷下生产时，产品的年产量h和投入生产的机和投入生产的机器数量器数量u2的关系为的关系为 h=h(u2)，相应的机器年完好率，相应的机器年完好率b,0 b0)xi0 i=1,2,30 i=1,2,34433123122334s1|2|3|4 ss ss ss xcxxx 阶段 223112ss xsxsc 按问题的变量个数划分阶段，把它看作一个按问题的变量个数划分阶段，把它看作一个三阶段决策问题，三阶段决策问题，k=1，2，345 设状态变量为设状态变量为s1，s2，s3，s4并记并记s1=c 取问题中的变量取问题中的变量x1，x2，x3为决策变量为决策变量 状态转移方程为：状态转移方程为：s3=x3s3+x2=s2s2+x1=s1=c 允许决策集合为：允许决策集合为：x3=s30 x2s20 x1s1 各阶段指标函数为：各阶段指标函数为：v1（x1）=x1v2（x2）=x22v3（x3）=x3，各指标函数以乘，各指标函数以乘积方式结合积方式结合 46 最优指标函数fk（sk）表示从第k阶段初始状态sk出发到第3阶段所得到的最大值，则动态规划基本方程为：1)(1,2,3 )()(max)(4411)(sfksfxvsfkkkksDxkkkkk47 状态转移方程状态转移方程为：为：s3=x3 s3+x2=s2 s2+x1=s1=c 指标函数为：指标函数为：v1（x1）=x1 v2（x2）=x22 v3（x3）=x322222222223302232202222032*22(2)f()m ax()()=m ax()=m ax()=4/27 x2/3xsxsxssvxfsxfsxxsxss333333334433*33(1)f()max()()=max(1)xxsxssvxfsxss11111111220121031104*1(3)f()m ax()()=m ax()=m ax(4()/27)=/64 x/4xscxcxcsvxfsxfcxxcxcc2223222222222222223232(032620 xsxsxxsxxsxsxs222222222令 hd h由d x得 舍 去）dh又d xdh而 故 是 极 大 值 点d x48*411111*3321122222*32233333*112111 x f()446432141x x f()s4322716111x x f()s444112xx443scscscsscscscsscscscsc所以最优解为：*233*411 x 24164scsczc4921322123122334ss1|2|3|4 =c ss ss ss xxsxxx 阶段 433s xsc 例4将例3用顺推解法解之（自学）502、资源分配问题(P213)资源分配问题就是将一定数量的一种或若干种资源（原材料、资金、设备等）恰当地分配给若干使用者，而使目标函数为最优。一种资源的分配问题称为一维资源分配问题，两种资源的分配问题称为二维资源分配问题。51 假设有一种资源，数量为a，将其分配给n个使用者，分配给第i个使用者数量xi时，相应的收益为gi（xi），问如何分配使得总收入最大？这就是一维资源分配问题，该问题的数学模型为：nixaxxxxgxgxgzinnn,2,1 0 )()()(max21221152 按变量个数划分阶段，k=1，2，n；设决策变量uk=xk，表示分配给第k个使用者的资源数量；设状态变量为sk，表示分配给第k个至第n个使用者的总资源数量；状态转移方程：sk+1=skxk，其中s1=a；允许决策集合：Dk（sk）=xk|0 xksk 阶段指标函数：vk（sk，uk）=gk（xk）表示分配给第k个使用者数量xk时的收益；最优指标函数fk（sk）表示以数量sk的资源分配给第k个至第n个使用者所得到的最大收益，则动态规划基本方程为：0)(1,)()(max)(11110nnkkkksxkksfnksfxgsfkk由后向前逐段递推，f1（a）即为所求问题的最大收益。53P213例1 某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如表所示。问如何分配，才能使国家盈利最大。54 工厂工厂 赢利赢利设备台数设备台数甲甲(1)乙乙(2)丙丙(3)01234503791213051011111104611121255状态变量状态变量Sk:表示分配给第表示分配给第k到第到第n个工厂设备的台数；个工厂设备的台数；决策变量决策变量xk:表示分配给第表示分配给第k个个工厂设备的台数，工厂设备的台数，k=3,2,1;则则sk1=sk-xk 为分配给第为分配给第k1到第到第n个工厂设备的台数；个工厂设备的台数；Pk(xk)表示为表示为xk 台设备分配到第台设备分配到第k个工厂所得盈利值；个工厂所得盈利值；fk（sk）表示为）表示为sk台设备分配给第台设备分配给第k个工厂至第个工厂至第n个工厂时个工厂时所得到的最大盈利值所得到的最大盈利值指标函数的递推方程为：指标函数的递推方程为：fk(sk)=M a x Pk(xk)+fk+1(sk+1)，k=3,2,1;f4(s4)=0 （边界条件）（边界条件）0 xxk kssk k56 x3s3P3(x3)f3(s3)x*30123450000114126623111134121245121253333333()max()0,1,2,3,4,5xf sP xss其中57 x2S2P2(x2)+f3(s2-x2)f2(s2)x*201234500+00010+4 5+05120+6 5+4 10+010230+115+6 10+4 11+014240+125+1110+6 11+411+0161,250+125+1210+11 11+611+4 11+0 21222222232202()max()()0,1,2,3,4,5xsfsP xf sx其中s=58 x1S1P1(x1)+f2(5-x1)f1(5)x*101234550+213+167+14 9+1012+5 13+0 210,211111112101()(5)max()(5)5xsf sfP xfx其中s=按计算表格的顺序反推算，可得两个最优方案 方案(1)x*1=0,s2=s1-x*1=5 x*2=2,s3=s2-x*2=3 x*3=s3=3 方案(2)x*1=2,s2=s1-x*1=3 x*2=2,s3=s2-x*2=1 x*3=s3=1593、生产和存储问题60P225 例3生产计划问题 某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对该产品的需求量分别为2，3，2，4单位，假设每批产品固定成本为3千元，若不生产为0，每单位产品成本为1千元，每个时期最大生产能力不超过6个单位，每期期末未出售产品，每单位需付存贮费0.5千元，假定第1期初和第4期末库存量均为0，问该厂如何安排生产与库存，可在满足市场需求的前提下总成本最小。61 按时期划分为四个阶段按时期划分为四个阶段，状态变量为期末库存，状态变量为期末库存Vk，决策变量为每期生产量决策变量为每期生产量xk。kkk0 x0()3 1*x1,2,.,6 x6()0.5()()kkkkkkkxxkvvvkxvkkkk当第k期生产成本 c当当第 期末库存量为 时的存储费用 h第 期总成本为ch 状态转移方程为：状态转移方程为：vk-1+xk-dk=vk62每期生产量每期生产量x k：每期生产量不超过生产能力每期生产量不超过生产能力6（用（用m表示）；表示）；又因为又因为 v k-1+x k-d k=v k,所以所以v k-1=v k+d k-x k 0,0,即即 x x k v k+d k;0 0 x x kMinMin v k+d k,6=k 每期期末库存量每期期末库存量v k：不大于今后各期需求量之和不大于今后各期需求量之和不大于不大于m-d k。410min(,6)kjkj kvdd 63指标函数循序递推关系为（指标函数循序递推关系为（顺推法顺推法)：f k(vk)=M i n c k(xk)+0.5vk+f k-1(vk-1)=M i n c k(xk)+0.5 vk+f k-1(vk+dk-xk)其中其中 k=min(vk+dk,6 );k=2,3,4 f 0(v0)=0 （边界条件）（边界条件）k=1,2,3,4.0 xxk