第3章：动态规划.ppt
第三章：动态规划第三章：动态规划3.1 3.1 基本概念基本概念一、动态决策问题一、动态决策问题 决策过程具有阶段性和时序性决策过程具有阶段性和时序性(与时间有关与时间有关)的决策问题。即决策过程可划分为明显的阶段。的决策问题。即决策过程可划分为明显的阶段。二、什么叫动态规划二、什么叫动态规划(D.P.Dynamic Program)(D.P.Dynamic Program)多阶段决策问题最优化的一种方法。多阶段决策问题最优化的一种方法。广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。三、动态规划三、动态规划(D.P.)(D.P.)的起源的起源 19511951年年,(,(美美)数学家数学家R.BellmanR.Bellman等提出等提出最优化原理，从而建立动态规划，最优化原理，从而建立动态规划，名著名著动态规划动态规划于于19571957年出版。年出版。四、动态决策问题分类四、动态决策问题分类1 1、按数据给出的形式分为：、按数据给出的形式分为：离散型动态决策问题。离散型动态决策问题。连续型动态决策问题。连续型动态决策问题。2 2、按决策过程演变的性质分为：、按决策过程演变的性质分为：确定型动态决策问题。确定型动态决策问题。随机型动态决策问题随机型动态决策问题。1 五、动态决策问题的基本要素五、动态决策问题的基本要素AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141 1、阶段阶段(stage)n(stage)n：作出决策的若干轮次。作出决策的若干轮次。n=1n=1、2 2、3 3、4 4、5 5。2 2、状态状态(state)Sstate)Sn n：每一阶段的出发位置。构成状态集，记为每一阶段的出发位置。构成状态集，记为S Sn n S S1 1=A=A，S S2 2=B=B1 1,B,B2 2,B,B3 3，S S3 3=C=C1 1,C,C2 2,C,C3 3，S S4 4=D=D1 1,D,D2 2,D,D3 3，S S5 5=E=E1 1,E,E2 2。阶段的起点阶段的起点。3 3、决策决策(decision)Xdecision)Xn n：从：从一个阶段某状态演变到下一个阶段某状态的选择。一个阶段某状态演变到下一个阶段某状态的选择。构成决策集，记为构成决策集，记为D Dn n(S(Sn n)。阶段的终点。阶段的终点。D D1 1(S(S1 1)=X)=X1 1(A)=B(A)=B1 1,B,B2 2,B,B3 3=S=S2 2，D D2 2(S(S2 2)=X)=X2 2(B(B1 1),X),X2 2(B(B2 2),X),X2 2(B(B3 3)=C)=C1 1,C,C2 2;C;C1 1,C,C2 2,C,C3 3;C;C2 2,C,C3 3=C=C1 1,C,C2 2,C,C3 3=S=S3 3，D D3 3(S(S3 3)=X)=X3 3(C(C1 1),X),X3 3(C(C2 2),X),X3 3(C(C3 3)=D)=D1 1,D,D2 2;D;D1 1,D,D2 2,D,D3 3;D;D1 1,D,D2 2,D,D3 3=D=D1 1,D,D2 2,D,D3 3=S=S4 4，D D4 4(S(S4 4)=X)=X4 4(D(D1 1),X),X4 4(D(D2 2),X),X4 4(D(D3 3)=E)=E1 1,E,E2 2;E;E1 1,E,E2 2;E;E1 1,E,E2 2=E=E1 1,E,E2 2=S=S5 5，D D5 5(S(S5 5)=X)=X5 5(E(E1 1),X),X5 5(E(E2 2)=F;F=F)=F;F=F。2AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975144 4、策略策略(policy)(policy)：全过程中各个阶段的决策全过程中各个阶段的决策X Xn n组成的有序总体组成的有序总体 X Xn n。如如 A A B B2 2 C C1 1 D D1 1 E E2 2 F F 上例从上例从 A A F F 共有共有3838种走法，即有种走法，即有3838条路线，条路线，3838个策略。个策略。5 5、子策略子策略(sub-policy)(sub-policy)：剩下的剩下的n n个阶段构成个阶段构成n n子过程，相应的决策系列叫子过程，相应的决策系列叫n n子策略。子策略。如如 C C1 1 D D1 1 E E2 2 F F6 6、状态转移方程：前一阶段的终点状态转移方程：前一阶段的终点(决策决策)是后前一阶段的起点是后前一阶段的起点(状态状态)。X Xn n =S=Sn+1n+17 7、指标函数：各个阶段的数量指标，记为指标函数：各个阶段的数量指标，记为r rn n(s(sn n,x,xn n)。如上例中，用如上例中，用d dn n(s(sn n,x,xn n)表示距离。表示距离。d d2 2(B(B3 3,C,C2 2)=1,d)=1,d3 3(C(C2 2,D,D3 3)=6)=6 等。等。8 8、目标函数：策略的数量指标值，记为、目标函数：策略的数量指标值，记为 Z=optrZ=optr1 1(s(s1 1,x,x1 1)*)*r rn n(s(sn n,x,xn n)。其中：其中：optopt为为maxmax或或minmin，*为运算符号。为运算符号。如上例中，如上例中，Z=mindZ=mind1 1(s(s1 1,x,x1 1)+)+d dn n(s(sn n,x,xn n)=mind)=mind1 1+d+d2 2+d dn n 3 3.2 3.2 最优化原理最优化原理 一、一、R.BellmanR.Bellman最优化原理：最优化原理：作为整个过程的最优策略，无任过去的状态和决策如何，对前面的决策形成状态而言，作为整个过程的最优策略，无任过去的状态和决策如何，对前面的决策形成状态而言，余下的诸决策必构成最优策略。余下的诸决策必构成最优策略。即：若即：若M M是从是从A A到到B B最优路线上的任一点，则从最优路线上的任一点，则从M M到到B B的路线也是最优路线。的路线也是最优路线。A MB 二、指标递推方程：二、指标递推方程：f fn n*(S Sn n)=)=optopt r rn n(s(sn n,x,xn n)*)*f fn+1 n+1*(s(sn+1n+1)x xn nDDn n(S(Sn n)如上例：如上例：f fn n*(S Sn n)=)=minmin d dn n(s(sn n,x,xn n)+)+f fn+1n+1*(S(Sn+1n+1)，n n=4=4、3 3、2 2、1 1 x xn nDDn n(S(Sn n)f f5 5*(S(S5 5)=)=minmin r r5 5(s(s5 5,x,x5 5)x x5 5DD5 5(S(S5 5)三、求解过程：三、求解过程：用反向嵌套递推法：从最后一个阶段开始，依次对各子过程寻优，直至获得全过程的最优，用反向嵌套递推法：从最后一个阶段开始，依次对各子过程寻优，直至获得全过程的最优，形成最优策略，获得最优策略指标值。形成最优策略，获得最优策略指标值。4 3.3 DP3.3 DP建模及求解建模及求解 一、建模条件：一、建模条件：决策过程本身具有时顺序性或可以转化为具有时序性的决策问题，决策过程本身具有时顺序性或可以转化为具有时序性的决策问题，均可建立动态规划数学模型求解。均可建立动态规划数学模型求解。AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514 二、典型动态决策问题建模及其求解二、典型动态决策问题建模及其求解 1 1、最短路线问题、最短路线问题 例例1 1：求下列图中：求下列图中A A到到F F的的最短路线及最短路线值。最短路线及最短路线值。5AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141 1、阶段阶段(stage)n(stage)n：n=1n=1、2 2、3 3、4 4、5 5。2 2、状态状态(state)Sstate)Sn n：S S1 1=A=A，S S2 2=B=B1 1,B,B2 2,B,B3 3，S S3 3=C=C1 1,C,C2 2,C,C3 3，S S4 4=D=D1 1,D,D2 2,D,D3 3，S S5 5=E=E1 1,E,E2 2。3 3、决策决策(decision)Xdecision)Xn n：决策集决策集D Dn n(S(Sn n)。D D1 1(S(S1 1)=X)=X1 1(A)=B(A)=B1 1,B,B2 2,B,B3 3=S=S2 2，D D2 2(S(S2 2)=X)=X2 2(B(B1 1),X),X2 2(B(B2 2),X),X2 2(B(B3 3)=C)=C1 1,C,C2 2;C;C1 1,C,C2 2,C,C3 3;C;C2 2,C,C3 3=C=C1 1,C,C2 2,C,C3 3=S=S3 3，D D3 3(S(S3 3)=X)=X3 3(C(C1 1),X),X3 3(C(C2 2),X),X3 3(C(C3 3)=D)=D1 1,D,D2 2;D;D1 1,D,D2 2,D,D3 3;D;D1 1,D,D2 2,D,D3 3=D=D1 1,D,D2 2,D,D3 3=S=S4 4，D D4 4(S(S4 4)=X)=X4 4(D(D1 1),X),X4 4(D(D2 2),X),X4 4(D(D3 3)=E)=E1 1,E,E2 2;E;E1 1,E,E2 2;E;E1 1,E,E2 2=E=E1 1,E,E2 2=S=S5 5，D D5 5(S(S5 5)=X)=X5 5(E(E1 1),X),X5 5(E(E2 2)=F;F=F)=F;F=F。4 4、状态转移方程：状态转移方程：X Xn n =S=Sn+1n+15 5、指标函数指标函数(距离距离)：d dn n(s(sn n,x,xn n)。d d2 2(B(B3 3,C,C2 2)=1,)=1,d d3 3(C(C2 2,D,D3 3)=6)=6 等。等。6 6、指标递推方程指标递推方程：f fn n*(S Sn n)=)=minmin r rn n(s(sn n,x,xn n)+)+f fn+1n+1*(S(Sn+1n+1)，n n=4=4、3 3、2 2、1 1 x xn nDDn n(S(Sn n)f f5 5*(S(S5 5)=)=minmin r r5 5(s(s5 5,x,x5 5)x x5 5DD5 5(S(S5 5)6AB1B2B3C1C2C3D1D2D3E1E2F3549543517158464422269751411F22F4+1=52+2=44 E26+1=79+2=117E17+1=85+2=77E27AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141+4=55+7=12 /5D18+4=124+7=116+7=1311D24+4=84+7=112+7=98D19+5=145+11=16 /14C14+5=93+11=145+8=139C1 /1+11=127+8=15 12C28AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975143+14=175+9=144+12=16 14B2最短路线值为：f1*(s1)=14最短路线求解如下：911F22F4+1=52+2=44 E26+1=79+2=117E17+1=85+2=77E21+4=55+7=12 /5D18+4=124+7=116+7=1311D24+4=84+7=112+7=98D19+5=145+11=16 /14C14+5=93+11=145+8=139C1 /1+11=127+8=15 12C23+14=175+9=144+12=16 14B210AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514即：A B2 C1 D1 E2 F 112 2、资源分配问题、资源分配问题 某种资源总量为某种资源总量为a a，用于生产用于生产n n种产品，若分配数量种产品，若分配数量X Xi i用于生产第用于生产第i i种产品，收益为种产品，收益为g gi i(X(Xi i)。问：如何分配才使总收益最大问：如何分配才使总收益最大?例例1.1.某有色金属公司拟拔出某有色金属公司拟拔出5050万元对所属三家冶炼厂进行技术改造。若以十万元为最小分割单位，万元对所属三家冶炼厂进行技术改造。若以十万元为最小分割单位，各厂收益与投资的关系如下表示：各厂收益与投资的关系如下表示：公司经理从定量决策的需要出发，要求公司经理从定量决策的需要出发，要求系统分析组求出：对三个工厂如何分配系统分析组求出：对三个工厂如何分配这这5050万元，才能使总收益达到最大万元，才能使总收益达到最大?121 1、阶段阶段n n：1 2 31 2 3 (工厂工厂)2 2、状态状态S Sn n：S S1 1 ，S S2 2=S=S1 1-X X1 1 ，S S3 3=S=S2 2-X X2 2，(可供分配的资源量可供分配的资源量)=5)=5，=0,1,=0,1,5,5，=0,1,=0,1,5,5，3 3、决策变量决策变量X Xn n：X X1 1 ，X X2 2 ,X,X3 3=S=S3 3 (分配的资源量分配的资源量)=0,1,)=0,1,5,5，=0,1,=0,1,5,5，=0,1,=0,1,5 ,5 4 4、状态转移方程：状态转移方程：S Sn+1n+1=S Sn n -X Xn n 5 5、指标函数指标函数(收益收益)g gn n(x(xn n)：g g1 1(x(x1 1)=g)=g2 2(x(x2 2)=g)=g3 3(x(x3 3)=)=0,4.5,7,9,10.5,120,4.5,7,9,10.5,12，0,2,4.5,7.5,11,150,2,4.5,7.5,11,15，0,5,7,8,10,130,5,7,8,10,136 6、指标递推方程指标递推方程：f fn n*(S Sn n)=)=maxmax g gn n(x(xn n)+)+f fn+1n+1*(S(Sn+1n+1)，n n=2=2、1 1 0 0 x xn nS Sn n f f3 3*(S(S3 3)=)=maxmax g g3 3(x(x3 3)，0 0 x x3 3S S3 3工厂1工厂2工厂313S2=S1-x1=5-1=4S3=S2-x2=4-3=1最优策略为：P*=x1*，x2*，x3*=1，3，1 Z*=17 万元S3=S2-x2S2=S1-x1143 3、背包问题、背包问题 例例.设有设有3 3种物品，每种数量无限，其重量和价值如下表。现有一只可装载重量为种物品，每种数量无限，其重量和价值如下表。现有一只可装载重量为W=5W=5公斤的背包，公斤的背包，试问试问:各种物品应各取多少件放入背包，才能使背包中的物品价值最高？各种物品应各取多少件放入背包，才能使背包中的物品价值最高？这个问题可以整数规划数学模型来描述：这个问题可以整数规划数学模型来描述：设第设第i i种物品取种物品取x xi i件放入背包，背包中物品总价值记为件放入背包，背包中物品总价值记为Z Z，则有数学模型：则有数学模型：Max Z=65xMax Z=65x1 1+80 x+80 x2 2+30 x+30 x3 3 s.t.2x s.t.2x1 1+3x+3x2 2+x+x3 355 x xj j00，j=1,2,3j=1,2,3；且为整数且为整数下面用动态规划求解：下面用动态规划求解：15、阶段阶段n n：1 2 31 2 3(物品物品)、状态状态SnSn：S S1 1=5=5，S S2 2=S=S1 1W W1 1X X1 1，S S3 3=S=S2 2W W2 2X X2 2 (背包可装入的重量背包可装入的重量)=1,3,5 =0,1,2,3,5)=1,3,5 =0,1,2,3,5、决策决策XnXn：0X X1 1S S1 1/W/W1 1 0X X2 2S S2 2/W/W2 2 0X X3 3 S S3 3/W/W3 3(装入的物品件数装入的物品件数)X)X1 1=0,1,2 X=0,1,2 X2 2=0,1 X=0,1 X3 3=0,1,2,3,5=0,1,2,3,5、状态转移方程：状态转移方程：S Sn+1n+1=S Sn nWnXnWnXn 、阶段阶段指标函数指标函数(价值价值)：r r1 1(x(x1 1)=65x)=65x1 1,r,r2 2(x(x2 2)=80 x)=80 x2 2,r,r3 3(x(x3 3)=30 x)=30 x3 3 、递推方程：递推方程：物品物品A A物品物品B B物品物品C C下面利用表格进行计算，下面利用表格进行计算，从最后一个阶段开始：从最后一个阶段开始：16n=3n=3时：时：此时此时 X X3 3SS3 3/W W3 3=S S3 3，为整数为整数X3S3f3(S3)=r3(X3)f3*(S3)X3*012350000103030120306060230306090903503060901501505n=2n=2时：时：此时此时 X X2 2SS2 2/W W2 2=S S2 2/3 3，为整数，为整数，S S3 3=S=S2 2 W W2 2 X X2 2 X2S2f2(S2)=r2(X2)+f3*(S3)f2*(S2)X2*0110+30=3030030+90=9080+0=8090050+150=15080+60=1401500n=1n=1时：时：此时此时 X X1 1SS1 1/W W1 1=S S1 1/2 2，为整数，为整数，S S2 2=S=S1 1 W W1 1 X X1 1 X1S1f1(S1)=r1(X1)+f2*(S2)f1*(S1)X1*01250+150=15065+90=155130+30=1601602S S2 2=S=S1 1W W1 1X X1 1*=5=52 22=12=1S S3 3=S=S2 2W W2 2X X2 2*=1=130=1 30=1 最优策略为：最优策略为：X X*=x=x1 1*，x x2 2*，x x3 3*=2*=2，0 0，11，Z Z*=f=f1 1*(S S1 1)=160)=160即应取第一种物品即应取第一种物品2 2件，第二种物品件，第二种物品0 0件，第三种物品件，第三种物品1 1件放入背包，件放入背包，才能使背包中的所有物品总价值最高为才能使背包中的所有物品总价值最高为160160元。元。174 4、生产问题、生产问题 例例.某厂生产一种产品，该产品在未来三个月中的需要量分别为某厂生产一种产品，该产品在未来三个月中的需要量分别为3 3，4 4，3 3万件，若生产准备费为万件，若生产准备费为 3 3万元万元/次，每件成本为次，每件成本为1 1元，每件每月存储费为元，每件每月存储费为0.70.7元，假定元，假定1 1月初和月初和4 4月初存货为月初存货为0 0，且每月，且每月 产量不限。试求：该厂未来三个月内的最优生产计划？产量不限。试求：该厂未来三个月内的最优生产计划？1月3月4月2月需求量：需求量：D D1 1=3 D=3 D2 2=4 D=4 D3 3=3=3、阶段阶段(月月)n)n：1 2 3 41 2 3 4、状态状态SnSn：S S1 1=0=0，S S2 2=S=S1 1+X+X1 1D D1 1，S S3 3=S=S2 2+X+X2 2D D2 2 S S4 4=S=S3 3+X+X3 3D D3 3=0=0 (月初库存月初库存)=0,1,2,3,4,5,6,7,=0,1,2,3)=0,1,2,3,4,5,6,7,=0,1,2,3、决策决策XnXn：X X1 1=X X2 2=X X3 3=(生产量生产量)3,4,5,6,7,8,9,10;0,1,2,3,4,5,6,7;0,1,2,3)3,4,5,6,7,8,9,10;0,1,2,3,4,5,6,7;0,1,2,3、状态转移方程：状态转移方程：S Sn+1n+1=S Sn n+X Xn nD D n n 、阶段阶段指标函数指标函数(成本成本)：成本：成本=生产费用存储费用生产费用存储费用 rn(Xn)=31Xn，Xn00，Xn00.7Sn、递推方程：递推方程：18n=3n=3时：时：此时此时 S S3 3+X+X3 3D D3 3=0=0，即即 X X3 3=3=3S S3 3 n=2n=2时：时：因为因为00S S3 333，而，而S S3 3=S=S2 2+X+X2 2D D2 2 ，即即 0 0 S S2 2+X+X2 24 34 3 ，所以所以 4-4-S S2 2X X2 277S S2 2X3S3f3(S3)=r3(X3)f3*(S3)X3*012306+0=66315+0.7=5.75.7224+1.4=5.45.4130+2.1=2.12.10X2S2f2(S2)=r2(X2)+f3*(S3)f2*(S2)X*20123456707+68+5.79+5.410+2.112.1716.7+67.7+5.78.7+5.49.7+2.111.8626.4+67.4+5.78.4+5.49.4+2.111.6536.1+67.1+5.78.1+5.49.1+2.111.2442.8+66.8+5.77.8+5.48.8+2.18.8053.5+5.77.5+5.48.5+2.19.2064.2+5.48.2+2.19.6074.9+2.17019 n=1n=1时：因为时：因为00S S2 277，而，而S S2 2=S=S1 1+X+X1 1D D1 1 ，即即 0 0 S S1 1+X+X1 13 73 7 ，所以所以 3 3S S1 1X X1 11010S S1 1由此可知：由此可知：S S1 1=0=0，此时此时X X1 1*=3=3；S S2 2=S=S1 1+X+X1 1*3=03=03 33=03=0，此时此时X X2 2*=7=7；S S3 3=S=S2 2+X+X2 2*4=04=07 74=34=3，此时此时X X3 3*=0=0。最优策略为：最优策略为：X X*=x=x1 1*，x x2 2*，x x3 3*=3*=3，7 7，00 Z Z*=f=f1 1*(S(S1 1)=18.1)=18.1即第一个月生产即第一个月生产3 3万件，第二个月生产万件，第二个月生产7 7万件，第三个月生产万件，第三个月生产0 0万件，可使总成本最低为万件，可使总成本最低为18.118.1万元。万元。X1S1f1(S1)=r1(X1)+f2*(S2)f1*(S1)X1*34567891009+11.210+8.811+9.212+9.613+718.136+12.17+11.88+11.620
