管理运筹学07动态规划课件

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

输入阶段输出转移律图6-1(a)

dn

sn(in)

n

sn(out)

gn=rn(sn,dn)

图6-1(b)2023/2/6Bellman最优性原理作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优子策略。简而言之，一个最优策略的任一子策略都是最优子策略。2023/2/6动态规划的数学描述1.阶段2.状态3.决策4.状态转移律5.策略与子策略6.阶段指标函数7.过程指标函数8.最优指标函数2023/2/6阶段在多阶段决策过程中，决策点将整个过程划分为若干部分，其中的每一部分即为一个阶段。描述阶段的变量称为阶段变量，常用k来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，一个N

个阶段的多阶段决策问题其阶段变量k=1，2，，N。2023/2/6决策决策是指决策者在若干可行方案中所作出的选择。决策变量dk(Sk)表示第k阶段、状态为Sk时的决策。决策变量的取值会受到一定的限制，用Dk(Sk)表示第k阶段、状态为Sk时决策变量允许的取值范围，称为允许决策集合，因而有dk(Sk)

Dk(Sk)。2023/2/6状态转移律

状态转移律是确定由一个状态到另一个状态演变过程的关系式，这种演变的对应关系记为Sk+1=Tk(Sk,dk)。2023/2/6策略与子策略各阶段决策所组成的决策序列称为一个策略，具有N个阶段的动态规划问题的策略可表示为{d1(S1),d2(S2),…,dN(SN)}。从某一阶段开始到过程终点为止的决策序列，称为子过程策略或子策略。从第k个阶段起的子策略可表示为{dk(Sk),dk+1(Sk+1),…,dN(SN)}。2023/2/6过程指标函数过程指标函数是用来衡量所实现过程优劣的数量指标，它是定义在全过程（策略）或后续子过程（子策略）上的数量函数。过程指标函数常用Rk,,N

来表示，构成动态规划的过程指标函数应具有可分性并满足递推关系，即Rk,,N

可表示为rk和Rk+1,N二者的函数。最常见的过程指标函数与阶段指标函数的关系有如下两种：1.过程指标函数是阶段指标函数的和，此时Rk,,N

=rk+Rk+1,N

2.过程指标函数是阶段指标函数的积，此时Rk,,N

=rkRk+1,N2023/2/6最优指标函数2023/2/6

ABCDB112

9C1156

A4B220D

81610C216

B39例12023/2/6例1的求解K=3时：f3(C1)=min{15}=15,C1Df3(C2)=min{16}=16,C2DK=2时：f2(B1)=min{12+15,9+16}=25,B1C2

f2(B2)=min{20+15,16+16}=32,B2C2f2(B3)=min{10+15,9+16}=25,B3C1或B3C2

K=1时：f1(A)=min{6+25,4+32,8+25}=31,AB1C2D2023/2/6确定性动态规划问题给出Sk和dk的取值后，状态Sk+1的取值唯一确定的动态规划问题称为确定性动态规划问题。确定性动态规划有广泛的应用领域，这些领域可概括为：1.最短路问题：见117页例7-12.资源分配问题3.存贮控制问题4.非线性规划问题2023/2/6资源分配问题[例7-2]:第119页某公司拟将500万元的资本投入所属的甲、乙、丙三个工厂，各工厂获得投资后年利润将有相应的增长，一定投资下的利润增长额如下表所示，试确定最优的投资分配方案，使公司年利润增长额最大。投资(百万元)12345甲0.30.70.91.21.3乙0.51.01.11.11.1丙0.40.61.11.21.22023/2/6例7-2的求解k=3：f3(S3)=max{r3(x3)+f4(S4)}=max{r3(x3)}S3012345

*x3

012344,5f3(S3)00.40.61.11.21.2k=2：f2(S2)=max{r2(x2)+f3(S2-x2)}2023/2/6例7-2的求解

x2r2(x2)+f3(S2-x2)

S2

012345f2(S2)*x2

00+00010+.4.5+00.5120+.6.5+.41+01.0230+1.1.5+.61+.41.4240+1.2.5+1.11+.61.1+.41.1=01.61,250+1.2.5+1.21+1.11.1+.61.1+.41.1+02.12

2023/2/6例7-2的求解k=1：f1(S1)=max{r1(x1)+f2(S1-x1)}x1r1(x1)+f2(S1-x1)S1

012345f1(S1)*x1

50+2.1.3+1.6

.7+1.4

.9+1.0

1.2+0.5

1.3+0

2.10,2

然后按计算表格的顺序反推算，可得如下两个最优分配方案：1.x1=0S2=S1-x1=5-0=5x2=2S3=3x3=3

2.x1=2，x2=2，x3=12023/2/6例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/2/6例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}f5(S5)是关于u5的单调增函数*u5=S5f5(S5)=8S5

K=4:f4(S4)=max{8u4+5(S4-u4)+f5[0.7u4+0.9(S4-u4)]}=max{8u4+5(S4-u4)+8[0.7u4+0.9(S4-u4)]}=max{1.4u4+12.2S4}f4(S4)是关于u4的单调增函数*u4=S4f4(S4)=13.6S42023/2/6例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/2/6例7-4的求解K=6(三月):

S601020*d620100f6(S6)=(*d6)86480K=5(二月):

d5

01020304050*

d5

f5(S5)S50204188164501641017216814240142201341361223012230869890086405052050504042023/2/6例7-4的求解K=4(一月):

d4

01020304050*

d4

f4(S4)S40302304403021028228228630,40282202502622642522025030212230244230218102124016419221221019617001645014417417817615201446012614014413201262023/2/6例7-4的求解K=3(十二月):

d3

01020304050*

d3

f3(S3)S304204224145041410388402392384503842035037037236233250332303023323403423103140302402843023102902922980284

2023/2/6例7-4的求解K=2(十一月):

d2

01020304050*

d2

f2(S2)S20500504474468504681046247245444645240446K=1(十月):

d1

01020304050*

d1

f1(S1)S1060660840606

2023/2/6例7-4的求解利用状态转移律，按上述计算的逆顺序推算，可得如下最优策略：十月份40双十一月份50双十二月份0双一月份40双二月份50双三月份0双最小的销售费用为606美元。2023/2/6非线性规划问题

2023/2/6例7-5的求解阶段：按问题的变量个数划分阶段k=1，2，3状态：S1=c，S2，S3决策变量：x1，x2，x3状态转移律：Sk+1=Sk-xk允许决策集合：0xkSk

最优指标函数：fk(Sk)=max{rk(xk)

fk+1(Sk+1)}边界条件：fk+1(Sk+1)=12023/2/6例7-5的求解2023/2/6例7-5的求解2023/2/6随机性动态规划问题给出Sk和dk的取值后，状态Sk+1的取值不是唯一确定的，而是具有某种概率分布的随机变量(此概率分布由状态和决策唯一确定)，这类动态规划问题称为随机性动态规划问题。下面就通过三个例题来介绍一下随机性动态规划问题的应用。1.例12.例23.例32023/2/6例1

某公司承担一种新产品试制任务，合同要求三个月内交出一台合格的样品，否则将负担1500元的经济赔偿。据估计，试制时投产一台得到合格样品的概率是1/3，投产一批的准备结束费用为250元，每台试制费用为100元。若投产一批全都不合格，可再投产一批，但每投一批的试制周期为一个月。要求确定每批投入的批量，使总的试制费用（包括可能的赔偿损失）期望值最小。阶段：k=1，2，3状态：Sk=1表示第k个月初尚未得到合格样品

Sk=0表示第k个月初已经得到了合格样品决策变量：dk表示第k个月初投产试制的台数2023/2/6例1的求解2023/2/6例1的求解2023/2/6例1的求解2023/2/6例1的求解2023/2/6例2某厂生产上需要在近五周内采购一批原料，估计在未来五周内价格会有一定的波动，各种价格及其出现的概率如下表所示，试确定在哪一周以什么价格购入原料，才能使采购价格的期望值最小。价格：500600700概率：0.30.30.42023/2/6例2的求解阶段：k=1,2,3,4,5表示各周状态：yk代表第k周的实际价格决策变量：xk=1代表第k周决定采购

xk=0代表第k周决定等待ykE：第k周决定等待，对应最优子策略采购价格的期望值最优指标函数：fk(yk)=min{yk,ykE}ykE=E[fk+1(yk+1)]=0.3fk+1(500)+0.3fk+1(600)+0.4fk+1(700)fk(yk)=yk时xk=1，代表以价格yk采购；fk(yk)=ykE时xk=0，代表等待。2023/2/6例2的求解k=5：

对于最后一周，如果所需的原料尚未买入，则无论市场价格如何都必须采购，因此有：

f5(500)=500，f5(600)=600，f5(700)=700k=4：y4E=0.3f5(500)+0.3f5(600)+0.4f5(700)=610f4(y4)=min{y4,y4E}=500，y4=500(采购)

=600，y4=600(采购)=610，y4=700(等待)同理可求得:2023/2/6例2的求解k=3：y3E=0.3f4(500)+0.3f4(600)+0.4f4(700)=574f3(y3)=min{y3,y3E}=500，y4=500(采购)

=574，y4=600(等待)=574，y4=700(等待)k=2：y2E=0.3f3(500)+0.3f3(600)+0.4f3(700)=55