第七章动态规划(管理运筹学,李军)

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

2、为阶段指标函数，用gn表示。显然gn是状态变量sn和决策变量dn的函数，即gn= rn(sn, dn)，如图6-1(b)所示。2022-7-3多阶段决策过程多阶段决策过程 决策 输入 阶段 输出 转移律 图6-1(a) dn sn(in) n sn(out) gn= rn(sn, dn) 图6-1(b)2022-7-3多阶段决策过程多阶段决策过程 d1 d2 dNs1 s2 s3 sN sN+1 1 2 N g1 g2 gN 图 6-2 N 阶段决策系统示意图2022-7-3Bellman最优性原理最优性原理 作为整个过程的最优策略具有这样的性作为整个过程的最优策略具有这样的性质：质： 即无论

3、过去的状态和决策如何，对前即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决面的决策所形成的状态而言，余下的诸决策必须构成最优子策略。简而言之，一个策必须构成最优子策略。简而言之，一个最优策略的任一子策略都是最优子策略。最优策略的任一子策略都是最优子策略。2022-7-3动态规划的数学描述动态规划的数学描述1.阶段2.状态3.决策 4.状态转移律5.策略与子策略6.阶段指标函数7.过程指标函数8.最优指标函数2022-7-3阶段阶段在多阶段决策过程中，决策点将整个过程划分为若干部分，其中的每一部分即为一个阶段。描述阶段的变量称为阶段变量，常用 k 来表示。阶段的划分一般是根据

4、时间和空间的自然特征来进行的，一个N 个阶段的多阶段决策问题其阶段变量 k =1，2，N。2022-7-3状态状态状态表示每个阶段开始所处的自然状况或客观条状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。状态反映前件，它描述了研究问题过程的状况。状态反映前面各阶段决策的结局，又是本阶段决策的出发点面各阶段决策的结局，又是本阶段决策的出发点和依据。状态是各阶段信息的传递点和结合点，和依据。状态是各阶段信息的传递点和结合点，各阶段的状态通常用状态变量各阶段的状态通常用状态变量Sk来描述。作为来描述。作为状状态应具有这样的性质：在某阶段的状态给定后，态应具有这样的性质：在某

5、阶段的状态给定后，该阶段以后过程的发展不受此阶段以前各阶段状该阶段以后过程的发展不受此阶段以前各阶段状态的影响。换句话说，过程的历史只能通过当前态的影响。换句话说，过程的历史只能通过当前的状态来影响未来，当前的状态是过程以往历史的状态来影响未来，当前的状态是过程以往历史的一个总结。这个性质称为无后效性或健忘性。的一个总结。这个性质称为无后效性或健忘性。2022-7-3决策决策 决策是指决策者在若干可行方案中所决策是指决策者在若干可行方案中所作出的选择。决策变量作出的选择。决策变量dk(Sk)表示第表示第k 阶段、阶段、状态为状态为Sk时的决策。决策变量的取值会受时的决策。决策变量的取值会受到一

6、定的限制，用到一定的限制，用Dk(Sk)表示第表示第k 阶段、状阶段、状态为态为Sk 时决策变量允许的取值范围，称为时决策变量允许的取值范围，称为允许决策集合，因而有允许决策集合，因而有dk(Sk) Dk(Sk) 。2022-7-3状态转移律状态转移律 状态转移律是确定由一个状态到另一个状态演变过程的关系式，这种演变的对应关系记为Sk+1=Tk (Sk, dk)。2022-7-3策略与子策略各阶段决策所组成的决策序列称为一各阶段决策所组成的决策序列称为一个策略，具有个策略，具有N个阶段的动态规划问个阶段的动态规划问题的策略可表示为题的策略可表示为d1(S1), d2(S2), , dN(SN)

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

8、k,N 可表示为rk 和Rk+1,N二者的函数。最常见的过程指标函数与阶段指标函数的关系有如下两种： 1.过程指标函数是阶段指标函数的和，此时Rk,N =rk +Rk+1,N 2.过程指标函数是阶段指标函数的积，此时Rk,N =rk Rk+1,N2022-7-3最优指标函数最优指标函数从第 k 个阶段开始到第 N 个阶段为止，采取最优策略或最优子策略所得到的指标函数称为最优指标函数，用 fk (Sk)表示，即： fk (Sk) = opt (dk) rk rk+1 rN = opt(dk) rk fk+1 (Sk+1)当 k=N 时 fk+1 (Sk+1)= fN+1 (SN+1)，fN+1

9、(SN+1)被称为边界条件，它的取值要根据具体问题来定，一般为 ”0” 或 “1”.2022-7-3 A B C D B1 12 9 C1 15 6 A 4 B2 20 D 8 16 10 C2 16 B3 9例例12022-7-3例例1的构模的构模阶段阶段：k=1, 2, 3状态状态：选各阶段所处的位置为状态变量，因此有S1= A。决策决策：所选择的路线； D1(S1)= B1, B2, B3 状态转移状态转移：目前状态一定，选择的线路一定，下一个状态一定。阶段指标函数：阶段指标函数：该阶段行进的路程过程指标函数：过程指标函数：阶段指标函数的和最优指标函数：最优指标函数：fk(Sk)=min

10、rk + fk+1(Sk+1)其中，边界条件fk+1(Sk+1)=0。2022-7-3例例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 D2022-7-3确定性动态规划问题确定性动态规划问题给出Sk 和dk的取值后，状态Sk+

11、1的取值唯一确定的动态规划问题称为确定性动态规划问题。确定性动态规划有广泛的应用领域，这些领域可概括为： 1.最短路问题：见117页例7-1 2.资源分配问题 3.存贮控制问题 4.非线性规划问题2022-7-3资源分配资源分配问题问题例例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

12、 1.2 1.2 2022-7-3例例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 2022-7-3例例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(S

13、2 - x2) 2022-7-3例例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 2022-7-3例例7-2的求解的求解k =1：f1(S1)=maxr1(x1)+f2(S1-x1) x1 r1(x1)+f

14、2(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 2022-7-3第第121页例页例7-3机器负荷分配问题机器负荷分配问题：某种机器可在高、低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为g=8u1，其中u1为投入高负荷生产的机器数量，年完好率为a=0.7；在低负荷下生产的产量函数为h=5y，其中y

15、为投入低负荷生产的机器数量，年完好率为b=0.9。假定开始生产时完好的机器数量为S1=1000台，试问每年应如何安排机器在高、低负荷下生产，才能使机器在五年里生产的产品总量最多。2022-7-3例例7-3的求解的求解构造动态规划模型构造动态规划模型：设阶段阶段序数k表示年度，状态状态变量Sk 为第k年初拥有的完好机器数量，同时也是第k-1年度末时的完好机器数量。决策决策变量uk为第k年度中分配到高负荷下生产的机器数量，于是Sk - uk为第k年度中分配到低负荷下生产的机器数量。状态转移方程状态转移方程： Sk +1=auk+b(Sk - uk )=0.7uk+0.9(Sk - uk )允许决策

16、集合允许决策集合： 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 )2022-7-3例例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+ 5S5

17、f5 (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.6S42022-7-3例例7-3的求解的求解依此类推可求得：*u3=S3 f3 (S3 ) = 17.5S3*u2= 0 f2 (S2 ) = 20.8S2*u1= 0 f1 (S1 ) = 23.7S

18、1 =23700(件)计算结果表明，前两年应把全部完好设备均投入低负荷生产；而后三年应把全部完好设备均投入高负荷生产。这样所得的产量最高，其最高产量为23700件。各年年初的状态为： S1 = 1000(台)， S2 = 900， S3 = 810， S4 = 567 S5 = 397， S6 = 278上述讨论终端状态S6 是自由的，如果在终端也附加一个约束条件，如在五年结束时完好的机器数不低于500台(上面只有278台)，问应如何安排生产？2022-7-3存贮控制问题存贮控制问题例例7-4:第124页 某鞋店销售一种雪地防潮鞋，以往的销售经历表明，此种鞋的销售季节是从10月1日至3月31日

19、。下一个销售季节各月的需求量预测值为：月 份 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 2022-7-3例例7-4的求解的求解 假设需求是按一定速度均匀发生的，订货不需要时间，但订货只能在月初办理，每次订货的费用为10美元。月存贮费用是按每月底鞋的存量计算的，每双0.2美元。由于订货不需要时间，所以销售季节以外的月份无存货。试确定最佳的进

20、货方案，以使总的销售费用最小。阶段阶段：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)20

21、22-7-3例例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 42022-7-3例例7-4的求解的求解K=4(一月): d4 0 10 20 30 40 50 * d4 f4 (S4 )S4 0 302 304 40 30

22、2 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 1262022-7-3例例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

23、 332 50 332 30 302 332 340 342 310 314 0 302 40 284 302 310 290 292 298 0 284 2022-7-3例例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 2022-7-3例例7-4的求解的求解利用状态转移律，按上述计算的逆顺序推算，可

24、得如下最优策略：十月份40双 十一月份50双 十二月份0双 一月份40双 二月份50双 三月份0双最小的销售费用为606美元。2022-7-3非线性规划问题非线性规划问题 2022-7-3例例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) =12022-7-3例例7-5的求解的求解:3kmax

25、)()(max)(3443333xSfxrSf33Sx:2kmax)()(max)(322332222SxSfxrSf)(max)(222222xSxSf令)()(22222xSxxh， 由02dxdh可 得2322Sx， 根 据02)(22322222SSxdxhd可 知2322Sx为 极 大 值 点 ， 所 以 ：2322Sx，3227422)(SSf2022-7-3例例7-5的求解的求解:1k)()(max)(221111SfxrSf)(maxmax)(311274132274111xSxSxSf同 上 可 知4164111)(SSf，1411Sx由 于cS1， 按 计 算 的 反 顺

26、序 推 算 可 得 各 阶 段的 最 优 决 策 和 最 优 值 ， 即 ：cx411，46411)(ccf；cx212，316122)(cSfcx413，cSf4133)(2022-7-3随机性动态规划问题随机性动态规划问题 给出Sk 和dk的取值后，状态Sk+1的取值不是唯一确定的，而是具有某种概率分布的随机变量(此概率分布由状态和决策唯一确定)，这类动态规划问题称为随机性动态规划问题。下面就通过三个例题来介绍一下随机性动态规划问题的应用。 1.例1 2.例2 3.例32022-7-3例1 某公司承担一种新产品试制任务，合同要求三个月内交出一台合格的样品，否则将负担1500元的经济赔偿。据

27、估计，试制时投产一台得到合格样品的概率是1/3，投产一批的准备结束费用为250元，每台试制费用为100元。若投产一批全都不合格，可再投产一批，但每投一批的试制周期为一个月。要求确定每批投入的批量，使总的试制费用（包括可能的赔偿损失）期望值最小。阶段阶段：k=1，2，3状态状态：Sk=1 表示第k个月初尚未得到合格样品 Sk=0 表示第k个月初已经得到了合格样品决策变量决策变量： dk 表示第k个月初投产试制的台数2022-7-3例1的求解2022-7-3例1的求解3k：)1 ()()(min) 1 (, 0)0(43233333fdCffd) 1 (4f的意义是第四个月初仍未得到合格样品情况下

28、的后期费用，所以1500) 1 (4f。 1500)()(33233ddC d3 S3 0 1 2 3 4 5)(33Sf3d 0 0 0 0 1 1500 1350 1117 994 946 948 946 42022-7-3例1的求解 946)()(23222ddC d2 S2 0 1 2 3 4)(22Sf2d 0 0 0 0 1 946 981 870 830 837 830 32k：)1 ()()(min)1 (, 0)0(33222222fdCffd2022-7-3例1的求解1k：)1 ()()(min)1 (2321111fdCfd 830)()(13211ddC d1 S1 0

29、 1 2 3 4) 1 (1f1d 1 830 903 819 796 814 796 3 1d=3, 2d=3, 3d=4,2022-7-3例2 某厂生产上需要在近五周内采购一批原料，估计在未来五周内价格会有一定的波动，各种价格及其出现的概率如下表所示，试确定在哪一周以什么价格购入原料，才能使采购价格的期望值最小。 价格： 500 600 700 概率： 0.3 0.3 0.42022-7-3例2的求解阶段阶段：k = 1, 2, 3, 4, 5表示各周状态状态： yk 代表第k周的实际价格决策变量决策变量：xk =1代表第k周决定采购 xk =0代表第k周决定等待ykE ：第k周决定等待，

30、对应最优子策略采购价格的期望值最优指标函数最优指标函数： 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，代表等待。2022-7-3例2的求解k = 5： 对于最后一周，如果所需的原料尚未买入，则无论市场价格如何都必须采购，因此有： f5(500) = 500， f5(600) = 600， f5(700) = 700k = 4：y4E = 0.3 f5(500)

31、 + 0.3 f5(600) + 0.4 f5(700) = 610 f4 (y4 )=min y4, y4E = 500， y4 = 500(采购) = 600， y4 = 600 (采购) = 610， y4 = 700 (等待)同理可求得:2022-7-3例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)

32、+ 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 (等待)2022-7-3例3 某矿山机械中有一易损部件，已知该部件损坏的

33、概率与其所使用的周数有关。如该部件已使用了m周，则在下一周生产中损坏的概率为pm 。有两种部件更新方法：一是不管是否损坏，使用若干周后就更新；二是在生产中损坏时才更新。前者的更新费用为cr，后者的更新费用为cf (cr cf)。 已知：p0 =0.05，p1 =0.2，p3 =0.7， p4 =1 cr =1000，cf=2000 问：在长期生产的情况下，应采取什么样的更新方法，才能使总的部件更新费用最小？2022-7-3例3的求解解：解：这是一个不定期的动态规划问题，用fn (m )表示该部件已使用了m周还要继续使用n周的最小期望费用。 对更新后已使用了m周的部件，若不管是否损坏都决定更新，

34、则期望费用为：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) 其中：2022-7-3例3的求解fppfffccpcpcpf001302001)0(fppnncff0011) 1 ()0(：0)(0mf按上述递推关系式有如下计算结果：2022-7-3例3的求解:1n3 .1052000)0(05. 0105. 01100fppcf)0(2000 2 . 0)2(8 . 0 ;1000)0(min) 1 (1011ffff 1 .4211 .421; 3 .1105min)0(2000 4 . 0)3(6 . 0 ;1000)0(min)2(1011ffff 2 .8422 .842; 3 .1105min)0(2000 7 . 0)4(3 . 0