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

运筹学

——第8章动态规划8.1多阶段决策问题8.2最优化原理与动态规划的数学模型8.3离散确定性动态规划模型的求解8.4动态规划求解举例8.1多阶段决策问题动态规划——研究多阶段决策问题的理论和方法。多阶段决策问题——决策过程可分为若干个互相联系的阶段，在每个阶段分别对

应着一组可以选取的决策，当

每个阶段的决策选定后，过程

也就随之确定。AB2B3B1C2C3C1D2D1E25567234515146333345例1：最短路问题例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。例3：

将一个数c(c>0)分成n部分c1,c2,

…cn之和，且ci>0(i=1,

…,n),问如何分割使其乘积为最大。多阶段决策问题和我们前面遇到的决策问题不同，它是和时间有关的。与时间有关的活动过程称为动态过程，其优化方法称为动态规划。与时间无关的活动过程称为静态过程，相应的优化方法称为静态规划。运筹学

——第8章动态规划8.1多阶段决策问题8.2最优化原理与动态规划的数学模型8.3离散确定性动态规划模型的求解8.4动态规划求解举例8.2最优化原理与动态规划的数学模型8.2.1动态规划的求解思路AB2B3B1C2C3C1D2D1E25567234515146333345基本思路：将一个n阶段的决策问题转化为依次求解n个具有递推关系的决策问题，从而简化计算过程。(1)考虑一个阶段的最优选择(1)考虑一个阶段的最优选择(2)联合考虑两个阶段的最优选择(1)考虑一个阶段的最优选择(2)联合考虑两个阶段的最优选择(1)考虑一个阶段的最优选择(2)联合考虑两个阶段的最优选择(1)考虑一个阶段的最优选择(3)联合考虑三个阶段的最优选择(2)联合考虑两个阶段的最优选择(1)考虑一个阶段的最优选择(3)联合考虑三个阶段的最优选择(2)联合考虑两个阶段的最优选择(1)考虑一个阶段的最优选择(3)联合考虑三个阶段的最优选择(4)联合考虑四个阶段，从A到E的最优选择(2)联合考虑两个阶段的最优选择(1)考虑一个阶段的最优选择(3)联合考虑三个阶段的最优选择(4)联合考虑四个阶段，从A到E的最优选择最短路：128.2最优化原理与动态规划的数学模型8.2.1动态规划的求解思路将多阶段决策问题转化为依次求解多个单阶段决策问题的特征：求解的各阶段有递推性。8.2.2动态规划的基本概念

1、阶段（stage）：指问题需要作业决策的步骤，通

常用k表示问题包含的阶段数，

称为阶段变量。

k的编号方法：顺序编号法逆序编号法例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。8.2.2动态规划的基本概念2、状态（state）表示每个阶段开始时所处的自然状况或客观条件，描述了影响决策的因素随决策进程的变化情况。它既是前面阶段所作决策的结果，又是本阶段作出决策的出发点和依据。第k阶段的状态变量常用xk表示。第1阶段状态变量x1是确定的，称初始状态。8.2.2动态规划的基本概念2、状态（state）表示每个阶段开始时所处的自然状况或客观条件.第k阶段的状态变量常用xk表示。例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。运筹学

——第8章动态规划8.1多阶段决策问题8.2最优化原理与动态规划的数学模型8.3离散确定性动态规划模型的求解8.4动态规划求解举例(2)联合考虑两个阶段的最优选择(1)考虑一个阶段的最优选择(3)联合考虑三个阶段的最优选择(4)联合考虑四个阶段，从A到E的最优选择最短路：128.1多阶段决策问题8.2.1动态规划的求解思路将多阶段决策问题转化为依次求解多个单阶段8.1多阶段决策问题8.2.2动态规划的基本概念

1、阶段：k2、状态：xk8.2.2动态规划的基本概念3、决策（decision）表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，uk(xk)表示第k阶段状态变量为xk时对方案的选择。决策变量的取值会受到状态变量的制约，被限制在某一范围之内。Dk(xk)——k阶段状态变量为xk时决策的允许取值范围8.2.2动态规划的基本概念3、决策（decision）例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。4、策略和子策略8.2.2动态规划的基本概念策略——动态规划问题各阶段决策组成的序列总体。子策略——从某一阶段开始到过程最终的决策序列。4、策略和子策略8.2.2动态规划的基本概念策略子策略5、状态转移方程8.2.2动态规划的基本概念若第k阶段的状态变量值为xk，当决策变量uk(xk)的取值决定后，下一阶段状态变量xk+1的值也就完全确定。即xk+1的值对应于xk和uk的值。记为:或简写为：例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。6、指标函数8.2.2动态规划的基本概念（1）阶段指标函数：对某一阶段的状态和决策产生

的效益值的度量，用表示。（2）过程指标函数：过程所包含的各阶段的状态和

决策所产生的总的效益值，记为：常见的两种过程指标函数形式是：①各阶段指标函数的和：②各阶段指标函数的积：8.2.2动态规划的基本概念（3）最优指标函数：对某一确定状态选取最优策略后得到的指标函数值。对应于从状态出发的最优子策略的效益值记作，则有：例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。阶段指标函数：最优指标函数：例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。阶段指标函数：Vk,5=∑[8uj+5(xj-uj)]=∑(5xj+3uj)fk(xk)＝max{5xj+3uj+fk+1(xk+1)}k=5,4,3,2,10≤uk≤xk最优指标函数：8.2.2动态规划的基本概念状态xkxk+1xk+2状态状态决策uk(xk)决策uk+1(xk+1)阶段指标函数

阶段指标函数T(xk,uk)T(xk+1,uk+1)k+1阶段k阶段动态规划概念模型示意图或过程指标函数Dk(xk)—Dk+1(xk+1)—最优指标函数：8.2.3最优化原理与动态规划的数学模型1、最优化原理：作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的决策必构成最优决策。8.2.3最优化原理与动态规划的数学模型1、最优化原理：作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的决策必构成最优决策。2、动态规划的基本方程与边界条件例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下年产量g和机器数u的关系为g＝8u,机器的年完好率为a=0.7。在低负荷年产量h和机器数v的关系为h＝5v,机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，制定五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下年产量g和机器数u的关系为g＝8u,机器的年完好率为a=0.7。在低负荷年产量h和机器数v的关系为h＝5v,机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，制定五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。（1）阶段：（2）状态变量：（3）决策变量：（4）状态转移律：（5）指标函数：（6）基本方程：（7）边界条件：(1)按年数划分为5个阶段，k=1,2,3,4,5(2)取第k年初完好的机器数xk为状态变量(3)取第k年投入高负荷的机器数uk为决策变量,0≤uk≤xk(4)状态转移方程为xk+1=0.7uk+0.9(xk-uk)=0.9xk-0.2uk(5)指标函数为Vk,5=∑[8uj+5(xj-uj)]=∑(5xj+3uj)(6)基本方程与边界条件为：解:fk(xk)＝max{5xj+3uj+fk+1(xk+1)}k=5,4,3,2,10≤uk≤xkf6(x6)＝0例2：机器负荷分配问题8.2.3最优化原理与动态规划的数学模型例：用动态规划的方法求解下述非线性规划问题：maxz=i·xii=13x1+3x2+2x312x1、x2、x30s.t8.2.3最优化原理与动态规划的数学模型（1）阶段数：k=1,2,····,n（2）状态变量：xk——？（3）决策变量：uk——？，允许决策集合D(xk)（4）状态转移律：xk+1=T(xk，uk)（5）阶段指标函数：vk(xk)——?（6）基本方程：fk(xk)=?（7）边界条件：fn+1(xn+1)=?8.2.3最优化原理与动态规划的数学模型例：用动态规划的方法求解下述非线性规划问题：maxz=i·xii=13x1+3x2+2x312x1、x2、x30s.t解：归结为三阶段动态规划问题，每阶段确定一个变量的数值。x13x22x30s1=12s2=s1-x1s3=s2-3x2s4=s3-2x3状态变量Sk：8.2.3最优化原理与动态规划的数学模型例：用动态规划的方法求解下述非线性规划问题：maxz=i·xii=13x1+3x2+2x312x1、x2、x30s.t（1）阶段变量：（2）状态变量：Sk——（3）决策变量：xk——D(Sk)=（4）状态转移律：

（5）阶段指标函数：（6）基本方程：（7）边界条件：8.2.3最优化原理与动态规划的数学模型例：用动态规划的方法求解下述非线性规划问题：maxz=i·xii=13x1+3x2+2x312x1、x2、x30s.t（1）阶段变量：k=1,2,3（2）状态变量：Sk——第k阶段可用于分配的右端项数量；（3）决策变量：xk——第k阶段选取的变量数值；D(Sk)={0

x1

S1,0x2

S2/3,0x3

S3/2}；（4）状态转移律：S2=S1－x1

；S3=S2－3x2；S4=S3－2x3；（5）阶段指标函数：vk(xk)=k·xk；（6）基本方程：fk(Sk)=max{vk(xk)·fk+1(Sk+1)}（7）边界条件：f4(S4)=1构造和求解动态规划模型需要注意的：状态xkxk+1xk+2状态状态决策uk(xk)决策uk+1(xk+1)阶段指标函数

阶段指标函数T(xk,uk)T(xk+1,uk+1)k+1阶段k阶段（1）状态变量的确定是建模的关键。（2）决策变量是控制过程的手段，取舍可能连续或离散。（3）状态转移律中，Xk+1的取值可能是确定的或随机的。（4）指标函数必须有递推性。1、逆序解法：从问题的最后一个阶段开始，逆多阶段的

决策过程反向寻优。用逆序解法求最短路问题2、顺序解法：从问题的最初阶段开始，同多阶段的实际

过程顺序寻优。8.2.4逆序解法与顺序解法运筹学

——第8章动态规划8.1多阶段决策问题8.2最优化原理与动态规划的数学模型8.3离散确定性动态规划模型的求解8.4动态规划求解举例8.2.2动态规划的基本概念状态xkxk+1xk+2状态状态决策uk(xk)决策uk+1(xk+1)阶段指标函数

阶段指标函数T(xk,uk)T(xk+1,uk+1)k+1阶段k阶段动态规划概念模型示意图或过程指标函数Dk(xk)—Dk+1(xk+1)—最优指标函数：（1）阶段数（2）状态变量（3）决策变量

（4）状态转移律（5）阶段指标函数（6）基本方程（7）边界条件最短路问题（1）阶段数：k=1,2,3,4,5,6（2）状态变量：xk——第k阶段的位置点。（3）决策变量：uk——第k阶段选择的行走路线，

允许决策集合D(xk)——xk位置时可选择的线路集合。（4）状态转移律：xk+1=T(xk,uk)——采取uk决策后，位置变化的规律。（5）阶段指标函数：vk(xk,uk)——选择uk决策后产生的距离。（6）基本方程：fk(xk)=min{vk(xk，uk)+fk+1(xk+1)}（7）边界条件：f7(x7)=0最短路问题基本方程:fk(xk)＝Min{Dk(uk)+fk+1(xk+1)},k＝6,5,4,3,2,1

uk∈Dk(xk)

f7(x7)＝0(1)当k=6时x6u6D6(u6)+f7(x7)f6(x6)最短路问题基本方程:fk(xk)＝Min{Dk(uk)+fk+1(xk+1)},k＝6,5,4,3,2,1

uk∈Dk(xk)

f7(x7)＝0(1)当k=6时x6u6D6(u6)+f7(x7)f6(x6)F1F1G4+0=4*4F2F2G3+0=3*3最短路问题(1)当k=6时x6u6D6(u6)+f7(x7)f6(x6)F1F1G4+0=4*4F2F2G3+0=3*3x5u5D(u5)+f6(x6)f5(x5)(2)当k=5时:最短路问题(1)当k=6时x6u6D6(u6)+f7(x7)f6(x6)F1F1G4+0=4*4F2F2G3+0=3*3x5u5D(u5)+f6(x6)f5(x5)E1E1F1E1F23+4=7*5+3=87E2E2F1E2F25+4=92+3=5*5E3E3F1E3F26+4=106+3=9*9(2)当k=5时:最短路问题x5u5D(u5)+f6(x6)f5(x5)E1E1F1E1F23+4=7*5+3=87E2E2F1E2F25+4=92+3=5*5E3E3F1E3F26+4=106+3=9*9(2)当k=5时:x4u4D(u4)+f5(x5)f4(x4)(3)当k=4时:最短路问题x5u5D(u5)+f6(x6)f5(x5)E1E1F1E1F23+4=7*5+3=87E2E2F1E2F25+4=92+3=5*5E3E3F1E3F26+4=106+3=9*9(2)当k=5时:x4u4D(u4)+f5(x5)f4(x4)D1D1E1D1E22+7=92+5=7*7D2D2E2D2E31+5=6*2+9=116D3D3E2D3E33+5=8*3+9=128(3)当k=4时:最短路问题x4u4D(u4)+f5(x5)f4(x4)D1D1E1D1E22+7=92+5=7*7D2D2E2D2E31+5=6*2+9=116D3D3E2D3E33+5=8*3+9=128(3)当k=4时:x3u3D(u3)+f4(x4)f3(x3)(4)当k=3时:最短路问题x4u4D(u4)+f5(x5)f4(x4)D1D1E1D1E22+7=92+5=7*7D2D2E2D2E31+5=6*2+9=116D3D3E2D3E33+5=8*3+9=128(3)当k=4时:x3u3D(u3)+f4(x4)f3(x3)C1C1D1C1D26+7=13*8+6=1413C2C2D1C2D23+7=10*5+6=1110C3C3D2C3D33+6=9*3+8=119C4C4D2C4D38+6=144+8=12*12(4)当k=3时:最短路问题x3u3D(u3)+f4(x4)f3(x3)C1C1D1C1D26+7=13*8+6=1413C2C2D1C2D23+7=10*5+6=1110C3C3D2C3D33+6=9*3+8=119C4C4D2C4D38+6=144+8=12*12(4)当k=3时:x2u2D(u2)+f3(x3)f2(x2)(5)当k=2时:最短路问题x3u3D(u3)+f4(x4)f3(x3)C1C1D1C1D26+7=13*8+6=1413C2C2D1C2D23+7=10*5+6=1110C3C3D2C3D33+6=9*3+8=119C4C4D2C4D38+6=144+8=12*12(4)当k=3时:x2u2D(u2)+f3(x3)f2(x2)

B1B1C1B1C2B1C31+13=143+10=13*6+9=15

13B2B2C2B2C3B2C48+9=177+9=16*6+12=18

16(5)当k=2时:最短路问题x2u2D(u2)+f3(x3)f2(x2)

B1B1C1B1C2B1C31+13=143+10=13*6+9=15

13B2B2C2B2C3B2C48+9=177+9=16*6+12=18

16(5)当k=2时:x1u1D(u1)+f2(x2)f1(x1)(6)当k=1时:最短路问题x2u2D(u2)+f3(x3)f2(x2)

B1B1C1B1C2B1C31+13=143+10=13*6+9=15

13B2B2C2B2C3B2C48+9=177+9=16*6+12=18

16(5)当k=2时:x1u1D(u1)+f2(x2)f1(x1)AAB1AB25+13=18*3+16=1918(6)当k=1时:最短路问题x6u6D6(u6)+f7(x7)f6(x6)F1F1G4+0=4*4F2F2G3+0=3*3x5u5D(u5)+f6(x6)f5(x5)E1E1F1E1F23+4=7*5+3=87E2E2F1E2F25+4=92+3=5*5E3E3F1E3F26+4=106+3=9*9x4u4D(u4)+f5(x5)f4(x4)D1D1E1D1E22+7=92+5=7*7D2D2E2D2E31+5=6*2+9=116D3D3E2D3E33+5=8*3+9=128x3u3D(u3)+f4(x4)f3(x3)C1C1D1C1D26+7=13*8+6=1413C2C2D1C2D23+7=10*5+6=1110C3C3D2C3D33+6=9*3+8=119C4C4D2C4D38+6=144+8=12*12x2u2D(u2)+f3(x3)f2(x2)

B1B1C1B1C2B1C31+13=143+10=13*6+9=15

13B2B2C2B2C3B2C48+9=177+9=16*6+12=18

16x1u1D(u1)+f2(x2)f1(x1)AAB1AB25+13=18*3+16=1918完整计算过程：即：A到G的最短路长为18，路径为：A→B1→C2→D1→E2→F2→G最短路问题(1)将所研究问题的过程划分为n个恰当的阶段，k＝1,2,…,n；(2)正确地选择状态变量xk，并确定初始状态x1的值；(3)确定决策变量uk以及各阶段的允许决策集Dk(xk)；(4)给出状态转移方程；(5)给出满足要求的过程指标函数Vk,n及相应的最优值函数；(6)写出递推方程和边界条件，建立基本方程；(7)按照基本方程递推求解。小结：动态规划法的步骤：注：前六步是建立动态规划模型的步骤。习题1：用动态求解最短路问题习题1：用动态求解最短路问题（1）阶段数：k=1,2,3,4（2）状态变量：xk——第k阶段的位置点。（3）决策变量：uk——第k阶段选择的行走路线，

允许决策集合D(xk)——xk位置时可选择的线路集合。（4）状态转移律：xk+1=T(xk,uk)——采取uk决策后，位置变化的规律。（5）阶段指标函数：vk(xk,uk)——选择uk决策后产生的距离。（6）基本方程：fk(xk)=min{vk(xk，uk)+fk+1(xk+1)}（7）边界条件：f5(x5)=0习题1：用动态求解最短路问题XkukDk(uk)+fk+1(xk+1)fk(xk)8.2.5动态规划模型的分类确定性随机性连续离散状态变量取值特征过程演变特征确定性随机性连续离散离散确定性动态规划模型连续确定性动态规划模型离散随机性动态规划模型连续随机性动态规划模型状态变量取值特征过程演变特征8.2.5动态规划模型的分类运筹学

——第8章动态规划8.1多阶段决策问题8.2最优化原理与动态规划的数学模型8.3离散确定性动态规划模型的求解8.4动态规划求解举例8.3 离散确定性动态规划模型的求解例4：某一警卫部队共有12支巡逻队，负责4个要害部门A、B、C、D的警卫巡逻。对每个部位可分别派出2-4支巡逻队，并且由于派出巡逻队数的不同，各部位在一段时期内可能造成的预期损失如表中所示。问：如何分派，可使总的预期损失为最小？队数预期损失部位2 183824343 143522314 10312125ABCD8.3 离散确定性动态规划模型的求解解：把对每个部位派出巡逻队数量的决策看成一个阶段，归结成4

阶段决策问题。（1）阶段变量：k=1,2,3,4（2）状态变量：xk（3）决策变量：uk允许决策集合D(xk)（4）状态转移律：xk+1（5）阶段指标函数：vk(uk)（6）基本方程（7）边界条件1、建立模型8.3 离散确定性动态规划模型的求解解：把对每个部位派出巡逻队数量的决策看成一个阶段，归结成4

阶段决策问题。（1）阶段变量：k=1,2,3,4（2）状态变量：xk——第k阶段可用于分配的巡逻队数量；（3）决策变量：uk——第k阶段派出的巡逻队数量；允许决策集合D(xk)={2,3,4}（4）状态转移律：xk+1=xk-uk

；（5）阶段指标函数：vk(uk)——预期损失函数，如表所示；（6）基本方程：fk(xk)=min{vk(uk)+fk+1(xk+1)}（7）边界条件：f5(x5)=01、建立模型8.3 离散确定性动态规划模型的求解（1）k=4，对D部位：由xk+1=xk-uk

；

fk(xk)=min{vk(uk)+fk+1(xk+1)}2、求解8.3 离散确定性动态规划模型的求解（1）k=4，对D部位：f4(x4)=min{v4(u4)+f5(x5)}，

f5(x5)=0，依题意，2

x412－6=6，列表计算如下：x4u4v4(u4)+f5(x5)f4(x4) u4*

(x4)2、求解8.3 离散确定性动态规划模型的求解（1）k=4，对D部位：f4(x4)=min{v4(u4)+f5(x5)}，

f5(x5)=0，依题意，2

x412－6=6，列表计算如下：x4u4v4(u4)+f5(x5)2 3 42 34 — — 3 34 31 — 4 34 31 255 34 31 256 34 31 25f4(x4) u4*

(x4)34 231 325 425 425 42、求解8.3 离散确定性动态规划模型的求解（2）k=3，对C部位由xk+1=xk-uk

；fk(xk)=min{vk(uk)+fk+1(xk+1)}8.3 离散确定性动态规划模型的求解2）k=3，对C部位，x4=x3－u3 f3(x3)=min{v3(u3)+f4(x4)} 而4

x38，列表计算如下：x3u3v3(u3)+f4(x4)f3(x3) u3*

(x3)8.3 离散确定性动态规划模型的求解2）k=3，对C部位，x4=x3－u3 f3(x3)=min{v3(u3)+f4(x4)} 而4

x38，列表计算如下：x3u3v3(u3)+f4(x4)2 3 44 24+34 — — 5 24+31 22+34 — 6 24+25 22+31 21+347 24+25 22+25 21+318 24+25 22+25 21+25f3(x3) u3*

(x3)58 255 249 247 346 48.3 离散确定性动态规划模型的求解（3）k=2，对B部位

由xk+1=xk-uk

；fk(xk)=min{vk(uk)+fk+1(xk+1)}8.3 离散确定性动态规划模型的求解3）k=2，对B部位，x3=x2－u2

f2(x2)=min{v2(u2)+f3(x3

）， 而8

x210，列表计算如下：x2u2v2(u2)+f3(x3)f2(x2) u2*

(x2)8.3 离散确定性动态规划模型的求解3）k=2，对B部位，x3=x2－u2

f2(x2)=min{v2(u2)+f3(x3

）， 而max{12-4，6}=8

x212－2=10，列表计算如下：x2u2v2(u2)+f3(x3)2 3 48 38+49 35+55 31+589 38+47 35+49 31+5510 38+46 35+47 31+49f2(x2) u2*

(x2)87 284 380 48.3 离散确定性动态规划模型的求解（4）k=1，对A部位由xk+1=xk-uk

；fk(xk)=min{vk(uk)+fk+1(xk+1)}8.3 离散确定性动态规划模型的求解4）k=1，对A部位，x2=x1－u1，x1=12

f1(x1)=min{v1(u1)+f2(x2)}，列表计算：x1u1v1(u1)+f2(x2)f1(x1) u1*

(x1)8.3 离散确定性动态规划模型的求解4）k=1，对A部位，x2=x1－u1，x1=12

f1(x1)=min{v1(u1)+f2(x2)}，列表计算：x1u1v1(u1)+f2(x2)2 3 412 18+80 14+84 10+87f1(x1) u1*

(x1)97 48.3 离散确定性动态规划模型的求解x1u1v1(u1)+f2(x2)2 3 412 18+80 14+84 10+87f1(x1) u1*

(x1)97 4最优策略：A—4，B—2，C—2，D—4；最小损失为97。xk+1=xk－uk

完整计算过程：练习-投资计划问题某企业现有5000万元资金可用于三个项目A、B、C的建设。项目利润的预期年增长额与投资的规模有关，如表示。用动态规划方法确定投资计划，使利润的预期年增长额最大。项目投资额A 0 15 34 42 56B 0 18 35 45 58C 0 20 37 48 600 1000 2000 3000 4000项目利润预期年增长额 单位：万元P171-8.2运筹学

——第8章动态规划8.1多阶段决策问题8.2最优化原理与动态规划的数学模型8.3离散确定性动态规划模型的求解8.4动态规划求解举例

项目投资额ABC28910415202863035358384043公司有资金8万元，投资A，B，C三个项目，单位投资为2万元，每个项目的投资效益率与投入该项目的资金有关，三个项目A，B，C的投资效益（万元）和投入资金（万元）的关系见下表：试用动态规划决策以下问题：公司如何分配8万元资金用于以上三个项目，才能使公司总收益最大？投资计划问题解：把确定每个项目投资额的决策看成一个阶段，归

结成3阶段决策问题。（1）阶段变量：k=？（2）状态变量：xk——？（3）决策变量：uk——？允许决策集合D(xk)=？（4）状态转移律：（5）阶段指标函数：vk(uk)——（6）基本方程：（7）边界条件：1、建立模型投资计划问题解：把确定每个项目投资额的决策看成一个阶段，归

结成3阶段决策问题。（1）阶段变量：k=1,2,3（2）状态变量：xk——第k阶段可用于投资的金额；（3）决策变量：uk——第k阶段的投资额；允许决策集合D(xk)={uk|0≤uk≤

xk}={0,2,4,6,8}（4）状态转移律：xk+1=xk-uk

；（5）阶段指标函数：vk(uk)——预期损失函数，如表所示；（6）基本方程：fk(xk)=max{vk(uk)+fk+1(xk+1)}（7）边界条件：f4(x4)=01、建立模型投资计划问题（1）k=3，对C项目：f3(x3)=max{v3(u3)+f4(x4)}，

f4(x4)=0，依题意，D3(x3)={0,2,4,6,8}，0≤x3≤8，列表计算如下：2、求解投资计划问题x3u3v3(u3)+f4(x4)f3(x3) u3*

(x3)（1）k=3，对C项目：f3(x3)=max{v3(u3)+f4(x4)}，

f4(x4)=0，依题意，D3(x3)={0,2,4,6,8}，0≤x3≤8，列表计算如下：2、求解投资计划问题x3u3v3(u3)+f4(x4)02468f3(x3) u3*

(x3)024680————010———01028——0102835—01028354301028354302468（2）k=2，对B项目：f2(x2)=max{v2(u2)+f3(x3)}，D2(x2)={0,2,4,6,8}，0≤x2≤8，x3=x2-u2

，列表计算如下：x2u2v2(u2)+f3(x3)f2(x2) u2*

(x2)（2）k=2，对B项目：f2(x2)=max{v2(u2)+f3(x3)}，D2(x2)={0,2,4,6,8}，0≤x2≤8，x3=x2-u2

，列表计算如下：x2u2v2(u2)+f3(x3)02468f2(x2) u2*

(x2)024680————0+109+0———0+289+1020+0——0+359+2820+1035+0—0+439+3520+2835+104001028374800024（3）k=1，对A项目：f1(x1)=max{v1(u1)+f2(x2)}，D1(x1)={0,2,4,6,8}，x1=8，x2=x1-u1

，列表计算如下：x1u1v1(u1)+f2(x2)f1(x1) u1*

(x1)（3）k=1，对A项目：f1(x1)=max{v1(u1)+f2(x2)}，D1(x1)={0,2,4,6,8}，x1=8，x2=x1-u1

，列表计算如下：x1u1v1(u1)+f2(x2)02468f1(x1) u1*

(x1)80+488+3715+2830+1038+0480u1*=0,u2*=4,u3*=4最大投资收益为48。例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。8.4动态规划举例(1)阶段：(2)状态变量(3)决策变量(4)状态转移方程(5)指标函数(6)基本方程解:例2：机器负荷分配问题(1)阶段：按年数划分为5个，k=1,2,3,4,5(2)状态变量：第k年初完好的机器数xk(3)决策变量：第k年投入高负荷的机器数uk,0≤uk≤xk(4)状态转移方程：

xk+1=0.7uk+0.9(xk-uk)=0.9xk-0.2uk(5)指标函数：Vk,5=∑[8uj+5(xj-uj)]=∑(5xj+3uj)(6)基本方程：解:fk(xk)＝max{5xj+3uj+fk+1(xk+1)}k=5,4,3,2,1

0≤uk≤xkf6(x6)＝0例2：机器负荷分配问题(1)当k=5时xk+1=0.9xk-0.2uk(1)当k=5时f5(x5)＝max{5x5+3u5+f6(x6)}=max{5x5+3u5}=8x5