新版运筹学动态规划课件

第六章动态规划

DynamicProgramming，DP美国数学家贝尔曼（Richard.Bellman,(1920～1984))创始时间上个世纪50年代创始人

动态规划是运筹学的一个主要分支,同时也是现代企业管理中的一种重要决策方法,它是解决多阶段决策过程的最优化的一种方法。2022/10/281第六章动态规划

DynamicProgramming动态规划模型分类离散确定型离散随机型连续确定型连续随机型动态规划解决问题的思路独特,在处理某些优化问题时,有时比线性规划或者非线性规划更有效.需要丰富的想象力去建立模型，并能用创造性的技巧去求解。其中离散确定性是最基本的,本章主要介绍这种类型的问题,介绍动态规划的基本思想、原理和方法.2022/10/282动态规划离散确定型离散随机型连续确定型连续随机型本章主要内容多阶段决策过程及其问题举例

最短路问题

动态规划的基本概念和基本方程

动态规划应用举例资源分配问题背包问题生产库存问题………2022/10/283本章主要内容多阶段决策过程及其问题举例2022/10/226.1多阶段决策过程及其问题举例动态规划研究的问题-----多阶段决策问题（顺序决策问题）研究的问题可以在时间或空间上划分为若干个相互联系阶段，称为”时段”。在每一个时段都需要做出决策,每时段的决策将影响到下一时段的决策,因此决策者每段决策时,不仅要考虑本阶段目标最优,还应考虑最终目标的最优,最终达到整个决策活动的总体目标最优.12状态状态状态n…状态决策决策决策状态2022/10/2846.1多阶段决策过程及其问题举例动态规划研究的问题----动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。然而，它也可以处理与时间无关的静态问题，只要在问题中人为地引入“时段”因素，就可以将其转化为一个多阶段决策问题。2022/10/285动态规划方法与“时间”关系很密切，随着时间2511214106104131112396581052C1C3D1AB1B3B2D2EC2例1最短路径问题求从A到E的最短路径。显然，这种运输网络问题是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。2022/10/2862511214106104131112396581052C1

第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从A到E的路程共有3×3×2×1＝18条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线。显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算．

第二种方法贪心算法，即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是

AB3C3D1E.距离为：1+11+8+5=252022/10/287第一种方法称做全枚举法或穷举法。它的基本思想是

2511214106104131112396581052C1C3D1AB1B3B2D2EC2第1阶段第4阶段第3阶段第2阶段状态第三种方法是动态规划方法。2022/10/2882511214106104131112396581052C

基本思想：如果起点A经过B1,C1,D1而到终点E，则由C1出发经D1到E点这条子路线，是从C1到E的最短路线。所以，寻找最短路线，应该从最后一段开始找，然后往前递推.设sk：第k阶段初的状态（所处的结点）;xk(sk)：在sk状态时第k阶段所作的决策,决定下一个状态的位置；d(sk,xk)：第k阶段，采取策略xk

所发生的距离;fk(sk)：在第k阶段，由sk状态开始到终点E的最短距离.2022/10/289基本思想：如果起点A经过B1,C1,D1而到终点E，则由C2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02022/10/28102511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=02022/10/28112511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52022/10/28122511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52022/10/28132511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82022/10/28142511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72022/10/28152511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=82022/10/28162511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=202022/10/28172511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=20f2(B2)=142022/10/28182511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=202022/10/28192511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=20状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E从A到E的最短路径为19，路线为A→B2→C1→D1→E2022/10/28202511214106104131112396581052C1多阶段决策过程及实例-标号法B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G531368766835342138223335526643437597681310912131618该点到G点的最短距离第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段从G到A的解法称为逆序解法。注：因为从A到G的最短路与从G到A的最短路是一样的，因此也可以从A出发来找。从A到G的解法称为顺序解法。2022/10/2821多阶段决策过程及实例-标号法B1AC3F2F1E3E2E1D综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。2022/10/2822综上所述可见，全枚举法虽可找出最优方案，但不是个6.2动态规划的基本概念和基本方程

(一)基本概念和基本方程(1)阶段：k=1,……，n(2)状态变量sk：第k阶段的状态.状态变量取值的集合成为状态集合，用Sk表示。状态集合可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定．(3)决策变量uk(sk)：第k阶段的决定，Dk(sk)为决策变量的取值范围.状态转移方程sk＋1＝T(sk,uk)：描述第k阶段与第k+1阶段的状态变量的关系2022/10/28236.2动态规划的基本概念和基本方程(一)基本概念和基本2022/10/2824(5)指标v(sk,uk)

：第k阶段状态sk情况下采取决策uk得到的结果（距离、得益、成本等）指标函数是指各阶段指标的累计。即V(sk,uk,…,sn,un,sn+1)=vk(sk,uk)*vk+1(sk+1,uk+1)…*vn(sn,un)它表示从第k阶段的状态sk开始到第n阶段的终止状态的指标累计。式中*表示某种运算符，一般为加法运算或者乘积运算。(6)最优指标函数fk(sk)：它表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采取最优策略得到的指标函数值

阶段函数2022/10/2224(5)指标v(sk,uk)：第24逆推公式fk(sk)＝OPT{d(sk,uk)+fk+1(sk+1)}k=n,…1fn+1(sn+1)＝0或fk(sk)＝OPT{d(sk,uk)+fk+1(sk+1)}k=n-1,…1fn(sn)＝OPT{d(sn,un)}多阶段决策问题中，常见的目标函数形式之一是取各阶段效益之和的形式.有些问题，如系统可靠性问题，其目标函数是取各阶段效益的连乘积形式.总之，具体问题的目标函数表达形式需要视具体问题而定。Max或者min2022/10/2825逆推公式fk(sk)＝OPT{d(sk,uk)+fk+12511214106104131112396581052C1C3D1AB1B3B2D2EC2第1阶段第4阶段第3阶段第2阶段对例1(1)阶段：k＝1，2，…，4(2)状态变量：sk－第k阶段初所处的位置,状态集合Sk

如S2:={B1,B2,B3}.2511214106104131112396581052C126(3)决策变量uk：在第k段sk状态时决定选取的下一段的某点.(4)状态转移方程：sk＋1＝uk(

sk)(5)阶段效益：

d(sk,uk)为第k段，采取决策uk到下一状态的距离.(6)最优指标函数：fk(sk)：第k段，在sk状态时到终点E的最短距离.逆推公式：fk(sk)＝min{d(sk,uk)+fk+1(sk+1)}k=4,…1f5(s5)＝02022/10/2827(3)决策变量uk：在第k段sk状态时决定选取的下一段（二）贝尔曼最优化原理：

一个最优策略具有这样的性质，即不论初始状态与初始策略如何，对于先前决策所造成的状态而言，余下所有决策必构成最优决策。也即：一个最优策略的子策略也是最优的。AⅠ

BMII’II2022/10/2828（二）贝尔曼最优化原理：AⅠBMII’II2022/1（三）解法步骤反向条件优化正向求最优解fk(sk)＝OPT{d(sk,uk)+fk+1(sk+1)}k=n,…1fn+1(sn+1)＝0fk(sk)＝OPT{d(sk,uk)*fk+1(sk+1)}k=n,…1fn+1(sn+1)＝12022/10/2829（三）解法步骤fk(sk)＝OPT{d(sk,uk)+f6.3应用举例例2资源分配问题-1例3资源分配问题-2例4背包问题例5生产库存问题例6可靠性问题例7机器负荷分配问题等等2022/10/28306.3应用举例例2资源分配问题-12022/10/2例2资源分配问题-1某公司准备将5台设备分配给所属的三个子工厂，各工厂获得设备后的可盈利情况如表所示。问：如何分配这五台设备，才能使公司获得的收益最大？

工厂盈利（万元）设备数工厂1工厂2工厂300001354271063101111412111251411122022/10/2831例2资源分配问题-1某公司准备将5台设备分配给所属的三分析(1)阶段：k=1,2,3.(3)决策变量uk：对第k个企业的分配数.(2)状态变量sk：对第k至3个企业可分配的设备数或：第k阶段初可分配的设备数.(4)状态转移方程：sk＋1＝sk–uk.(5)最优指标函数fk(sk)：第k至3个企业采取最优分配策略可产生的最大收益.设分配给第k个工厂的机器数为uk工厂1工厂2工厂32022/10/2832分析(1)阶段：k=1,2,3.(3)决策变量ukfk(sk)＝max{gk(

uk)+fk+1(sk-uk)}k=3,2,1f4(s4)＝0其中，gk

(uk)是阶段函数逆推公式：sk+12022/10/2833fk(sk)＝max{gk(uk)+fk+1(sk-uk=3,S3={0,1,2,3,4,5},f3(s3)＝max{g3(u3)+0}g3(u3)+0maxu3s3012345f3(s3)u3000010441204662304611113404611121245046111212124,52022/10/2834k=3,S3={0,1,2,3,4,5},f3k=2,S2={0,1,2,3,4,5},f2(s2)＝max{g2(u2)+f3(s3)}g2(u2)+f3(s3)max最优决策u2s2012345f2(s2)u20000(0,0)10+45+051(1,0)20+65+410+0102(2,0)30+115+610+411+0142(2,1)40+125+1110+611+411+0161,2(1,3)

(2,2)50+125+1210+1111+611+411+0212(2,3)S3=S2-u32022/10/2835k=2,S2={0,1,2,3,4,5},f2g1(u1)+f2(s2)max最优决策u1s1012345f1(s1)u150+213+167+1410+1012+514+0210,2(0,2,3)(2,2,1)k=1,S1={5},f1(s1)＝max{g1(u1)+f2(s2)}得到两种方案：u1*＝0，u2*＝2，u3*＝3:工厂1分配0台，工厂2分配2台，工厂3分配3台;u1*＝2，u2*＝2，u3*＝1:工厂1分配2台，工厂2分配2台，工厂3分配1台。总盈利均为21万元。同理得到另一组最优解2022/10/2836g1(u1)+f2(s2)max最优决策u10一般分配问题某种资源，总量为a，分配于n种生产。若分配ui

用于第i种生产，收益为gi(ui)。问：应如何分配才能使总收入最大？容易建立其数学模型：maxZ=g1(u1)+g2(u2)+…+gn(un)u1+u2+…+un=aui≥0

2022/10/2837一般分配问题某种资源，总量为a，分配于n种生产。若分配uifk(sk)＝max{g(skuk)+fk+1(sk+1)}k=n-1,…,2,1fn+1(sn+1)＝00≤uk≤sk逆推公式：sk:

第k阶段初可分配的资源数。

uk:对第k个企业的分配资源数.状态转移方程:sk+1=

sk-uk2022/10/2838fk(sk)＝max{g(skuk)+fk+1(sk+例3

资源分配问题-2

某工厂要进行A,B,C三种新产品的试制，为提高三种产品研制成功的概率，决定调拨经费2百万，并要求资金集中使用，也即以百万为单位进行分配，其增加研发费与新产品不成功概率的关系如表所示。问如何分配资金，可使三种产品都研制不成功的概率最小。产品不成功概率费用（百万）ABC00.40.60.810.20.40.520.150.20.3例3资源分配问题-2某工厂要进行A,B,C三种新39分析(1)阶段：k=1，2，3(3)决策变量uk：对第k阶段分配金额(2)状态变量sk：第k阶段初的可用金额(4)状态转移方程：sk＋1＝sk-uk产品A产品B产品C分析(1)阶段：k=1，2，3(3)决策变量uk40fk(sk)＝min{gk

(

uk)*fk+1(sk+1)}k=3,2,1f4(s4)＝1逆推公式：其中，gk

(uk)是阶段指标函数(5)最优指标函数fk(sk)：第k至3阶段采取最优分配策略，得到不成功概率最小fk(sk)＝min{gk(uk)*fk+1(sk+41

u3s3g3(u3)minu3=0u3=1u3=2f3(s3)u*3(s3)00.8——0.8010.80.5—0.5120.80.50.30.32k=3,S3={0,1,2},f3(s3)＝min{g3(u3)*1}u3g3(u3)minu3=0u342

u2s2g2(u2)*f2(s2)minu2=0u2=1u2=2f2(s2)u*2(s2)00.6*0.8——0.48010.6*0.50.4*0.8—0.3020.6*0.30.4*0.50.2*0.80.162k=2,S2={0,1,2},f2(s2)＝min{g2(u2)*f2(s2)}u2g2(u2)*f2(s2)m43g1(u1)*f2(s2)mins1u1012f1(s1)u*1(s1)20.4*0.16=0.0640.2*0.3=0.060.15*0.48=0.0720.061k=1,S1={2},f1(s1)＝max{g1(u1)*f2(s2)}得到方案：u1*＝1，u2*＝0，u3*＝1:产品A分配1百万，产品B分配0，产品C分配1百万f*=0.06g1(u1)*f2(s2)mins1u1012f144

例4

背包问题某卡车载重能力为10吨，现要装三种产品，已知每件产品的重量和利润如表：

又规定产品3至多装2件。问如何安排运输可使总利润最大？产品种类k重量Pk(吨/件)利润(价值)rk(元/件)A4150B3120C2802022/10/2845例4背包问题产品种类重量利润(价值)A4150B31设u1,u2,u3分别为1、2、3货物的装载件数，得到数学模型：设u1,u2,u3分别为1、2、3货物的装载件数，得到数学模46阶段k=1,2,3，状态变量sk—第k阶段初的可装载能力，决策变量uk—第k阶段的装载件数，状态转移方程:（tk为k产品的单件重量）递推公式:f4(s4)=0,k=3,2,1动态规划方法求解产品A产品B产品C阶段k=1,2,3，动态规划方法求解产品A产品B产品C47物品A物品B物品Ck=1k=2k=3k=4s1=10s2s3s4阶段k状态变量：装载前背包的容量决策变量：装载的件数u1u2u3决策允许集合：装载件数的范围0≤u1≤[s1/t1]u1为整数状态转移方程：背包容量和装载件数的关系阶段指标：vk(sk,uk)=rkuk

在背包中第k种物品的价值最优指标：fk(sk)=max{rkuk+fk+1(sk+1)}终端条件：f4(s4)=0s2＝s1-t1x1s3=s2-t2x2s4=s3-t3x30≤u2≤[s2/t2]u2为整数0≤u3≤{[s3/t3],2}u3为整数物品A物品B物品Ck=1k=2k=3k=4s1=10s2s348k=3

u3s3r3u3=80u3minu3=0u3=1u3=2f3(s3)u*3(s3)0~10——002~3080—8014~100801601602C的单件重量为2,限制最多装2件k=3u3r3u3=80u3minu3=0u3=49u2s2（公斤）r2u2+f3(s3)=120u2+f3(s2-3u2)f2(s2)u*2最优决策u2=0u2=1u2=2u2=30,10+000(0,0)20+80800(0,1)30+80120+01201(1,0)40+160120+01600(0,0)50+160120+802001(1,1)60+160120+80240+02402(2,0)70+160120+160240+02801(1,2)80+160120+160240+803202(2,1)90+160120+160240+80360+03603(3,0)100+160120+160240+160360+04002(2,2)k=2,装载物品B，f2(s2)B的单件重量为3u2r2u2+f3(s3)=120u2+f3(s2-3u2)50u1s1(公斤)r1u1+f2(s2)=150u1+f2(s1-4u1)f1(u1)u*1最优决策u1=0u1=1u1=2100+400150+240300+804000(0,2,2)k=1，装载物品A，f1(u1)最优解为：物品A装0件，物品B装2件，物品C装2件。最大价值为400元。A的单件重量为4u1r1u1+f2(s2)=150u1+f2(s1-4u51例5生产库存问题某厂在年末估计，下年4个季度市场对该厂某产品的需求量均为dk=3(k=1,2,3,4)，该厂每季度生产此产品的能力为bk=5(k=1,2,3,4,)。每季度生产这种产品的固定成本为F=13（不生产时为0），每一产品的单位变动成本为C=2。本季度产品如不能售出，则需发生库存费用g=1/件，仓库能贮存产品的最大数量Ek=4。年初年末库存为0，

试问如何安排4个季度的生产，以保证在满足市场需求的前提下，使生产和库存总费用最小?2022/10/2852例5生产库存问题2022/10/2252假设：第k季度可以销售的产品是本季度初的库存及本季度的产量(1)阶段：k=1,2,3,4n=4.(2)状态变量sk：第k季度初的库存量.(3)决策变量uk：第k

个季度的产量.(4)转移方程：

sk＋1＝sk

+uk-dk.(5)最优指标函数fk(sk)：第k季度至第4个季度采取最优策略时的最小总费用.2022/10/2853假设：第k季度可以销售的产品是本季度初的库存及本季度的产量fk(sk)＝min{wk(uk,sk)+fk+1(sk+1)}

k=4,3,2,1f5(s5)＝0逆推公式：2022/10/2854fk(sk)＝min{wk(uk,sk)+fk+1(sk+1新版运筹学动态规划课件55k=4u4s4s2=w4+0min0123f4(s4)u*4(s4)0———191931——17—1722—15——15130———00k=4s2=w4+0min0123f4(s4)u*4(56k=3

u3s3w3+f4(s3+u3-3)min012345f3(s3)u*3(s3)0———19+1922+1725+153831——17+1920+1723+1526+02652—15+1918+1721+1524+0—24430+1916+1719+1522+0——19041+1717+1520+0———180k=3u3w3+f4(s3+u3-3)mi57K=2

u2s2w2+f3(s2+u2-3)min12345f2(s2)u*2(s2)0——19+3822+2625+244841—17+3820+2623+2426+17435215+3818+2621+2424+1927+18434K=2u2w2+f3(s2+u2-3)mi58k=1u1s1w1+f2(s1+u1-3)min345f1(s1)u*1(s1)019+4822+4525+43673or4k=1u1w1+f2(s1+u1-3)min34559例5可靠性问题某机器工作系统由n个部件组成，这些部件正常工作关系为串联，每个部件都装有主要元件的备用件，并可自动投入工作。显然备用件越多，可靠性越大，但系统的成本、重量、体积会变大。若已知备用件总费用为C，总重量为W.ck

为第k个部件装配一个备用件的费用问：在这两个限制条件下，应如何选用部件的备用件个数，使得正常工作的可靠性最大？wk为第

k个部件装配一个备用件的重量Pk

第k个部件的故障概率2022/10/2860例5可靠性问题某机器工作系统由n个部件组成，这些部件MaxV=dk(sk,

uk)nk=1nk=1ckuk≤Cnk=1wkuk≤W

uk≥0且为整数

设uk为第k个部件装配备用件个数dk(sk,

uk)为第k个部件装配uk个备用件时，机器正常工作的概率MaxV=dk(sk,uk)nk=1nk=61动态规划模型：(1)阶段：k=1,2,…,n(2)决策变量：uk：第k个部件上装备用件个数(3)状态变量：sk：第k-n个部件允许的总费用tk：第k-n个部件允许的总重量(4)状态转移：

sk+1=sk-ckuktk+1=tk-wkuk

动态规划模型：(1)阶段：k=1,2,…,n(2)决策变62(5)fk(sk，tk)：第k-n个部件，采取最优策略时机器正常工作的概率。逆推公式：fk(sk，tk)=max{dk(sk,uk)*fk+1(sk+1，tk+1)}

fn+1(sn+1，tn+1)=1k=n,…,1(5)fk(sk，tk)：第k-n个部件，采取最优策63某复合系统由A,B,C三个部分串联而成，已知：①A、B、C相互独立；②各部分的单件故障率分别为：P1=0.4，P2=0.2，P3=0.5；③每个部分的单件价格为：A部分单价c1=1万元；

B部分单价c2=2万元；C部分单价c3=3万元；④可投资购置部件金额为10万元。求A、B、C三部分各应购置多少部件才能使系统的总可靠率最大？某复合系统由A,B,C三个部分串联而成，已知：64令A、B、C分别为阶段1、2、3。sk——第k阶段及以后可用来购买部件总额uk——第k环节配备的件数状态转移方程：sk+1=sk－ckuk

第k环节本身的可靠率为：令：fk(sk)表示k阶段尚有资金sk时，可能获得k段及以后各段组成系统的最高可靠率。递推方程为：fk(sk)=max[dk(sk，uk)×fk+1(sk－ckuk)]，f4(s4)=1令A、B、C分别为阶段1、2、3。65采用后向动态规划法，从第3阶段算起。

u3s3u3＝1u3＝2f3(s3)=max{d3(s3,u3)}u*3345670.50.50.50.50.5－－－1-0.251-0.250.50.50.50.750.7511122采用后向动态规划法，从第3阶段算起。u3u66阶段2，此时考虑当把钱用于购置B和C部件时，各应购置多少个部件为最优。显然，此时B、C应至少各配制1个部件，故s2≥c2+c3=2+3=5；同时，A部件亦至少配备1个部件，故s2≤10－1=9。

u2s2u2＝1u2＝2u2＝3f2(s2)u*2567890.8×0.50.8×0.50.8×0.50.8×0.750.8×0.75－－0.96×0.50.96×0.50.96×0.5－－－－0.992×0.50.40.40.480.60.611211阶段2，此时考虑当把钱用于购置B和C部件时，各应购置多少个部67阶段1，A部件处，s1=10万元。

u1s1u1＝1u1＝2u1＝3u1＝4u1＝5f1(s1)u*1100.6×0.60.84×0.60.936×0.480.9744×0.40.99×0.40.5042阶段1，A部件处，s1=10万元。u1u1＝1u168例6机器负荷分配问题

某厂有120台同一规格完好的机器.

每台机床全年在高负荷下工作可创利9万元，但机器的报废率高,每年将有1/2的机器报废.在低负荷下工作可创利6万元，每年将有1/4的机器报废.

试拟定连续3年的分配计划，使得总利润最大。2022/10/2869例6机器负荷分配问题某厂有120台同一规格完好的动态规划模型:分三个阶段，k＝1、2、3。定义：sk——第k阶段完好的机器数量。uk——第k阶段用于高负荷工作的机器数量。状态转移方程：阶段函数为：

令：fk(sk)表示k阶段尚有机器数量为sk时，可能获得总收益，则递推方程为：2022/10/2870动态规划模型:2022/10/2270采用后向动态规划法，从第3阶段算起。

采用后向动态规划法，从第3阶段算起。71例7

不确定采购问题某厂5周内需采购一批原料，价格波动见右表试求：在哪周，以什么价格购进，期望价格最低？单价P5000.36000.37000.4例7不确定采购问题某厂5周内需采购一批原料，价格波动见72分析(1)分5个阶段

(2)状态变量sk：第k周的实际价格Sk={500，600，700}(3)决策变量uk：1第k周采购0第k周等待SkE：第k周等待，以后再采购的期望价格分析(1)分5个阶段(2)状态变量sk：第k73(4)最优指标函数fk(

Sk)，第k到5周采用最优采购策略时的最低期望价格。基本方程：fk(

sk)=min{

sk，SkE}k=4,3,2,1f5(

s5)=

s5k=5

f5(

s5)=

s5

x5=1

s5500600700f5(

s5)500600700u5111(4)最优指标函数fk(Sk)，第k到5周采用最优采购74k=4

f4(

s4)=min{

s4，S4E}S4E=0.3f5(500)+0.3f5(600)+0.4f5(700)=610f4(s4)=min{

s4，610}=500,当s4=500600,当s4=600610,当s4=700u4=0

u4=1k=3

S3E=

0.3f4(500)+0.3f4(600)+0.4f4(700)=0.3×500+0.3×600+0.4×610=574k=4f4(s4)=min{s4，S475

f3(

s3)=min{

s3，S3E}=min{

s3，574}

500,当s3=500u3=1574,当s3=600,700u3=0=k=2

f2(

s2)=min{

s2，551.8}500,当s2=500u2=1551.8,当s2=600,700u2=0=f3(s3)=min{s3，S3E}500,当s376k=1

f1(

s1)=min{

s1，536.26}500,当s1=500u1=1536.26,当s1=600,700u1=0=5006007001VXX2VXX3VXX4VVX5VvVk=1f1(s1)=min{s1，53677∴最优策略：1,2,3周500，采购4周，500,600,采购5周，什么价格均买按此策略，价格期望值为：0.3f1(500)+0.3f1(600)+0.4f1(700)=0.3×500+0.3×536.26+0.4×536.26=525.32≈525∴最优策略：1,2,3周500，采购按此策略，价格期望78总结特点解决多阶段决策问题，依次在每一阶段上决策。逐阶段优化一个解，直至结束才产生一个完整的最优解。DP是一种方法，并不是算法，因此对不同问题要设计不同解算过程。2022/10/2879总结特点2022/10/2279优点应用广泛、灵活。可以解决有些非线性和整数规划，对含有随机因素的问题与确定型的线性优化问题解起来几乎一样容易。求解方便。缺点决策者不能简单地将他的问题应用已有的商品化的DP软件包解决。2022/10/2880优点2022/10/2280研究范围：线性规划，非线性规划，整数规划，网络分析，控制工程分类离散确定型，连续确定型，离散随机型，连续随机型离散连续确定随机决策变量状态变量2022/10/2881离散连续确定随机决策变量状态变量2022/10/2281第六章动态规划

DynamicProgramming，DP美国数学家贝尔曼（Richard.Bellman,(1920～1984))创始时间上个世纪50年代创始人

动态规划是运筹学的一个主要分支,同时也是现代企业管理中的一种重要决策方法,它是解决多阶段决策过程的最优化的一种方法。2022/10/2882第六章动态规划

DynamicProgramming动态规划模型分类离散确定型离散随机型连续确定型连续随机型动态规划解决问题的思路独特,在处理某些优化问题时,有时比线性规划或者非线性规划更有效.需要丰富的想象力去建立模型，并能用创造性的技巧去求解。其中离散确定性是最基本的,本章主要介绍这种类型的问题,介绍动态规划的基本思想、原理和方法.2022/10/2883动态规划离散确定型离散随机型连续确定型连续随机型本章主要内容多阶段决策过程及其问题举例

最短路问题

动态规划的基本概念和基本方程

动态规划应用举例资源分配问题背包问题生产库存问题………2022/10/2884本章主要内容多阶段决策过程及其问题举例2022/10/226.1多阶段决策过程及其问题举例动态规划研究的问题-----多阶段决策问题（顺序决策问题）研究的问题可以在时间或空间上划分为若干个相互联系阶段，称为”时段”。在每一个时段都需要做出决策,每时段的决策将影响到下一时段的决策,因此决策者每段决策时,不仅要考虑本阶段目标最优,还应考虑最终目标的最优,最终达到整个决策活动的总体目标最优.12状态状态状态n…状态决策决策决策状态2022/10/28856.1多阶段决策过程及其问题举例动态规划研究的问题----动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。然而，它也可以处理与时间无关的静态问题，只要在问题中人为地引入“时段”因素，就可以将其转化为一个多阶段决策问题。2022/10/2886动态规划方法与“时间”关系很密切，随着时间2511214106104131112396581052C1C3D1AB1B3B2D2EC2例1最短路径问题求从A到E的最短路径。显然，这种运输网络问题是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。2022/10/28872511214106104131112396581052C1

第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从A到E的路程共有3×3×2×1＝18条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线。显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算．

第二种方法贪心算法，即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是

AB3C3D1E.距离为：1+11+8+5=252022/10/2888第一种方法称做全枚举法或穷举法。它的基本思想是

2511214106104131112396581052C1C3D1AB1B3B2D2EC2第1阶段第4阶段第3阶段第2阶段状态第三种方法是动态规划方法。2022/10/28892511214106104131112396581052C

基本思想：如果起点A经过B1,C1,D1而到终点E，则由C1出发经D1到E点这条子路线，是从C1到E的最短路线。所以，寻找最短路线，应该从最后一段开始找，然后往前递推.设sk：第k阶段初的状态（所处的结点）;xk(sk)：在sk状态时第k阶段所作的决策,决定下一个状态的位置；d(sk,xk)：第k阶段，采取策略xk

所发生的距离;fk(sk)：在第k阶段，由sk状态开始到终点E的最短距离.2022/10/2890基本思想：如果起点A经过B1,C1,D1而到终点E，则由C2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02022/10/28912511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=02022/10/28922511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52022/10/28932511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52022/10/28942511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82022/10/28952511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72022/10/28962511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=82022/10/28972511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=202022/10/28982511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=20f2(B2)=142022/10/28992511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=202022/10/281002511214106104131112396581052C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=20状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E从A到E的最短路径为19，路线为A→B2→C1→D1→E2022/10/281012511214106104131112396581052C1多阶段决策过程及实例-标号法B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G531368766835342138223335526643437597681310912131618该点到G点的最短距离第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段从G到A的解法称为逆序解法。注：因为从A到G的最短路与从G到A的最短路是一样的，因此也可以从A出发来找。从A到G的解法称为顺序解法。2022/10/28102多阶段决策过程及实例-标号法B1AC3F2F1E3E2E1D综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。2022/10/28103综上所述可见，全枚举法虽可找出最优方案，但不是个6.2动态规划的基本概念和基本方程

(一)基本概念和基本方程(1)阶段：k=1,……，n(2)状态变量sk：第k阶段的状态.状态变量取值的集合成为状态集合，用Sk表示。状态集合可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定．(3)决策变量uk(sk)：第k阶段的决定，Dk(sk)为决策变量的取值范围.状态转移方程sk＋1＝T(sk,uk)：描述第k阶段与第k+1阶段的状态变量的关系2022/10/281046.2动态规划的基本概念和基本方程(一)基本概念和基本2022/10/28105(5)指标v(sk,uk)

：第k阶段状态sk情况下采取决策uk得到的结果（距离、得益、成本等）指标函数是指各阶段指标的累计。即V(sk,uk,…,sn,un,sn+1)=vk(sk,uk)*vk+1(sk+1,uk+1)…*vn(sn,un)它表示从第k阶段的状态sk开始到第n阶段的终止状态的指标累计。式中*表示某种运算符，一般为加法运算或者乘积运算。(6)最优指标函数fk(sk)：它表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采取最优策略得到的指标函数值

阶段函数2022/10/2224(5)指标v(sk,uk)：第105逆推公式fk(sk)＝OPT{d(sk,uk)+fk+1(sk+1)}k=n,…1fn+1(sn+1)＝0或fk(sk)＝OPT{d(sk,uk)+fk+1(sk+1)}k=n-1,…1fn(sn)＝OPT{d(sn,un)}多阶段决策问题中，常见的目标函数形式之一是取各阶段效益之和的形式.有些问题，如系统可靠性问题，其目标函数是取各阶段效益的连乘积形式.总之，具体问题的目标函数表达形式需要视具体问题而定。Max或者min2022/10/28106逆推公式fk(sk)＝OPT{d(sk,uk)+fk+12511214106104131112396581052C1C3D1AB1B3B2D2EC2第1阶段第4阶段第3阶段第2阶段对例1(1)阶段：k＝1，2，…，4(2)状态变量：sk－第k阶段初所处的位置,状态集合Sk

如S2:={B1,B2,B3}.2511214106104131112396581052C1107(3)决策变量uk：在第k段sk状态时决定选取的下一段的某点.(4)状态转移方程：sk＋1＝uk(

sk)(5)阶段效益：

d(sk,uk)为第k段，采取决策uk到下一状态的距离.(6)最优指标函数：fk(sk)：第k段，在sk状态时到终点E的最短距离.逆推公式：fk(sk)＝min{d(sk,uk)+fk+1(sk+1)}k=4,…1f5(s5)＝02022/10/28108(3)决策变量uk：在第k段sk状态时决定选取的下一段（二）贝尔曼最优化原理：

一个最优策略具有这样的性质，即不论初始状态与初始策略如何，对于先前决策所造成的状态而言，余下所有决策必构成最优决策。也即：一个最优策略的子策略也是最优的。AⅠ

BMII’II2022/10/28109（二）贝尔曼最优化原理：AⅠBMII’II2022/1（三）解法步骤反向条件优化正向求最优解fk(sk)＝OPT{d(sk,uk)+fk+1(sk+1)}k=n,…1fn+1(sn+1)＝0fk(sk)＝OPT{d(sk,uk)*fk+1(sk+1)}k=n,…1fn+1(sn+1)＝12022/10/28110（三）解法步骤fk(sk)＝OPT{d(sk,uk)+f6.3应用举例例2资源分配问题-1例3资源分配问题-2例4背包问题例5生产库存问题例6可靠性问题例7机器负荷分配问题等等2022/10/281116.3应用举例例2资源分配问题-12022/10/2例2资源分配问题-1某公司准备将5台设备分配给所属的三个子工厂，各工厂获得设备后的可盈利情况如表所示。问：如何分配这五台设备，才能使公司获得的收益最大？

工厂盈利（万元）设备数工厂1工厂2工厂300001354271063101111412111251411122022/10/28112例2资源分配问题-1某公司准备将5台设备分配给所属的三分析(1)阶段：k=1,2,3.(3)决策变量uk：对第k个企业的分配数.(2)状态变量sk：对第k至3个企业可分配的设备数或：第k阶段初可分配的设备数.(4)状态转移方程：