第8章动态规划第1,2节PPT课件

1、1 动态规划（Dynamic Programming）是运筹学的一个重要分支，它是解决多阶段决策过程最优化的一种方法。美国数学家贝尔曼（R. E. Bellman）等人在50年代初提出了解决多阶段决策问题的“最优性原理”（Principle of Optimality）。1957年贝尔曼出版了专著“动态规划”，该书是动态规划的第一本著作。目前动态规划已经用于解决最优路径问题、资源分配问题、生产调度问题、设备更新问题、复合系统可靠性问题及生产过程最优控制等，并且取得了显著的效果。第1页/共78页2 动态规划是用来解决多阶段决策过程最优动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在

2、于，它可以把一化的一种数量方法。其特点在于，它可以把一个个n 维决策问题变换为几个一维最优化问题，维决策问题变换为几个一维最优化问题，从而一个一个地去解决。从而一个一个地去解决。 需指出：动态规划是求解某类问题的一种需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。用动态规划方法去求解。第2页/共78页3第1节 多阶段决策过程及实例 在生产经营活动中

3、，某些问题决策过程可以划分为若干相互联系的阶段，每个阶段需要做出决策，从而使整个过程取得最优。12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策第3页/共78页4 各个阶段不是孤立的，而是有机联系的，也就是说，本阶段的决策将影响过程下一阶段的发展，从而影响整个过程效果，所以决策者在进行决策时不能够仅考虑选择的决策方案使本阶段最优，还应该考虑本阶段决策对最终目标产生的影响，从而做出对全局来讲是最优的决策。 多阶段决策问题中，各个阶段一般是按照时间来划分的，随着时间的发展而产生各个阶段的决策，从而形成决策序列，这就是动态的含义。第4页/共78页5 在一些与时间无关的静态问题中（如非线性

4、规划等），可以人为地赋予时间的概念，使其成为一个多阶段决策问题，再用动态规划方法处理。 当每个阶段的决策确定以后，全部过程的决策就是这些阶段决策所组成的一个决策序列，所以多阶段决策问题也称为序贯决策问题。 第5页/共78页6例1 最短路线问题 给定一个线路网络，两点之间连线上的数字表示两点之间的距离（或费用），试求一条由A到G的铺管线路，使总距离为最短（或总费用最小）。C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G531363876685225522333336634418第6页/共78页7例2. 机器负荷分配问题 某种机器可以在高低两种不同的负荷下进行生产。 在高负荷下进行生产

5、时，产品的年产量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,3第41页/共78页4233123122334s1 | 2 | 3 | 4 ss ss ss xcxxx 阶段 223112ss xsxsc 按问题的变量个数划分阶段，把它看作一个三按问题的变量个数划分阶段，把它看作一个三阶段决策问题，阶段决策问题，k=1，2，3第42页/共78页4

6、3 设状态变量为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 ，各指标函数以乘积方式结合 第43页/共78页44 最优指标函数fk（sk）表示从第k阶段初始状态sk出发到第3阶段所得到的最大值，则动态规划基本方程为： 1)(1 , , 2 , 3 )()(max)(4411)(sfksfxvsfkkkksDxkkkkk第44页/共78页45状态转移方程为：状态

7、转移方程为：s3=x3s3+x2=s2s2+x1=s1=c指标函数为：指标函数为：v1（x1）=x1v2（x2）=x22v3（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/ 4x

8、scxcxcsvxfsxfcxxcxcc2223222222222222223232(032620 xsxsxxsxxsxsxs222222222令 hd h由d x得 舍 去 ）dh又d xdh而 故 是 极 大 值 点d x第45页/共78页46*411111*3321122222*32233333*112111 x f ( )446432141x x f ()s4322716111x x f ( )s444112xx443scscscsscscscsscscscsc所以最优解为： *233*411 x 24164scsczc第46页/共78页4721322123122334ss1 | 2

9、 | 3 | 4 = c ss ss ss xxsxxx 阶段 433s xsc 例4将例3用顺推解法解之（自学）第47页/共78页482、资源分配问题(P213) 资源分配问题就是将一定数量的一种或若干种资源（原材料、资金、设备等）恰当地分配给若干使用者，而使目标函数为最优。 一种资源的分配问题称为一维资源分配问题，两种资源的分配问题称为二维资源分配问题。 第48页/共78页49 假设有一种资源，数量为a，将其分配给n个使用者，分配给第i个使用者数量xi时，相应的收益为gi（xi），问如何分配使得总收入最大？这就是一维资源分配问题，该问题的数学模型为：nixaxxxxgxgxgzinnn,

10、2 , 1 0 )()()( max212211第49页/共78页50 按变量个数划分阶段，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)(11110nnkkkksxkksfnk

11、sfxgsfkk由后向前逐段递推，f1（a）即为所求问题的最大收益。 第50页/共78页51P213例1 某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如表所示。问如何分配，才能使国家盈利最大。第51页/共78页52 工厂 赢利设备台数甲(1) 乙(2) 丙(3)012345037912130510111111046111212第52页/共78页53状态变量Sk:表示分配给第k到第n个工厂设备的台数；决策变量xk:表示分配给第k个工厂设备的台数， k=3,2,1;则sk1=sk-xk 为分配给第k1到第n个

12、工厂设备的台数；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 k第53页/共78页54 x3s3P3(x3)f3(s3) x*30123450000114126623111134121245121253333333( )max()0,1,2,3,4,5xf sP xss其中第54页/共78页55 x2S2P2(x2)+f3(s2-x2)f2(s2

13、) 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 =第55页/共78页56 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 =按计算表格的顺序反

14、推算，可得两个最优方案方案(1) x*1=0, s2=s1-x*1=5x*2=2, s3=s2-x*2=3x*3=s3=3方案(2) x*1=2, s2=s1-x*1=3x*2=2, s3=s2-x*2=1x*3=s3=1第56页/共78页573、生产和存储问题第57页/共78页58P225 例3生产计划问题 某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对该产品的需求量分别为2，3，2，4单位，假设每批产品固定成本为3千元，若不生产为0，每单位产品成本为1千元，每个时期最大生产能力不超过6个单位，每期期末未出售产品，每单位需付存贮费0.5千元，假定第1期初和第4期

15、末库存量均为0，问该厂如何安排生产与库存，可在满足市场需求的前提下总成本最小。 第58页/共78页59 按时期划分为四个阶段，状态变量为期末库存Vk，决策变量为每期生产量xk。kkk0 x0()3 1* x1,2,.,6 x6()0.5()()kkkkkkkxxkvvvkxvkkkk当第k期生产成本 c当当第 期末库存量为 时的存储费用 h第 期总成本为ch状态转移方程为：状态转移方程为： vk-1+ xk- dk= vk第59页/共78页60每期生产量x k ：每期生产量不超过生产能力6（用m表示）；又因为 v k-1 +x k -d k = v k, 所以v k-1 = v k+ d k-

16、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 第60页/共78页61指标函数循序递推关系为（顺推法) ： 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

17、 k 0 xxk k 第61页/共78页62f 1(v1 )= M i n c 1(x1)+0.5 v1 + f 0(v0)x x1 = min(v1+ d1, 6 )41120min(,6)min(9,62)4jjvdd1111120(0)min(30.5*0)5,2xvfxx时，1111131(1)min(30.5*1)6.5,3xvfxx时，1111142(2)min(30.5*2)8,4xvfxx时，1111153(3)min(30.5*3)9.5,5xvfxx时，1111164(4)min(30.5*6)11,6xvfxx时，第62页/共78页63222222221220222242

18、23()min ()()(3)min(,6)min(3,6) 0vmin(,6)min(6,3)3xjjf vc xh vf vxvdvdd 其中：2222212032212212221221(0)min()(0)(3)c (0)(0)(3)09.5c (1)(0)(2)48 =minmin9.5,0c (2)(0)(1)56.565c (3)(0)(0)xfc xhfxhfhfxhfhf所以2222212204(1)min()(1)(4)=11.5,0 xfc xhfxx所以2222212205(2)min()(2)(5)=14,5xfc xhfxx所以2222212206(3)min()(

19、3)(6)=15.5,6xfc xhfxx所以第63页/共78页643333333323303333343()min ()()(2)min(,6)min(2,6) 0vmin(,6)min(4,4)4xf vc xh vf vxvdvdd其中：3333333333(0)14,0(1)16,03(2)17.5,4(3)19,5(4)20.5,6fxfxfxfxfx所以所以或所以所以所以第64页/共78页654444443404434343443430(0)min ( )(0)(4)c (0)(4)0 20.5c (1)(3)4 19 =min c (2)(2)min 5 17.520.5,06

20、16c (3)(1)7 14c (4)(0)xvfc xhfxfffxff所以第65页/共78页66k-1kkkv = v + d -x 阶段需求量di库存量vi生产量xi440032462300123500按计算顺序反向推算得最优解第66页/共78页674、排序问题 本书所论及的问题是： 假定有N个零件，都要先经机器A，再经机器B进行加工。各零件在机器A、B上的加工时间固定，但可互不相同。问这些零件应以怎样的次序进入加工，可使从第 1 个零件进入加工开始到最后一个零件加工完毕为止这一段时间最短？这个问题已经得到了完满的解决。 我们这里只介绍结论，而不涉及获得结论的推理过程。第67页/共78页

21、68P 240排序规则（Johnson 1954) （2）找出矩阵M中的最小元素（如有多个，任取一个）；若它在上行，则相应工件应排在最前加工；如在下行则相应工件应排在最后加工。 （3） 将排定位置的工件从M中划去，其余下的工件重复按（2）进行，其次序在原已排定次序的工件之间，取最前或最后。如此反复，直到所有工件加工次序都排定为止。基本思路：尽是减少在机床B上的等待加工时间。因此在机床B上加工时间长的工件先加工，在B上加工时间短的后加工。（1）先作工件加工时间的工时矩阵 a1, a2, ,an b1, b2, ,bn1 , 2,.,n工件时间矩阵=M第68页/共78页69P240例9 设有5个工件需在机床A、B上加工，加工顺序是先A后B，每个工件所需加工时间如表所示。部如何安排加工顺序，使机床连续加工完成所有工作的加工时间最少？并求出总加工时间。AB136272347453574第69页/共78页7013542工件号码 1 2 3 4 53 7 4 5 7 M=6 2 7 3 4最优加工顺序第70页/共78页71A52477742B28事件 完成时间 3 7 14 19 26工件号码 1 3 4 3 5 M=6 3 事件B开始时间 3 9 16 20 26事件 完成时间 9 16 20 23 28总加工时间为小时第71页/共78页725