第七章--动态规划课件.ppt

1、管管 理理 运运 筹筹 学学运筹学运筹学赵明霞赵明霞山西大学经济与管理学院山西大学经济与管理学院管管 理理 运运 筹筹 学学2023-2-162第七章第七章 动态规划动态规划1.1.多阶段决策过程最优化问题多阶段决策过程最优化问题2.2.基本概念、基本原理基本概念、基本原理3.3.动态规划建模与求解动态规划建模与求解4.4.动态规划的应用动态规划的应用管管 理理 运运 筹筹 学学2023-2-163第一节多阶段决策过程最优化问题举例第一节多阶段决策过程最优化问题举例例例1 最短路径问题最短路径问题 下图表示从起点下图表示从起点A到终点到终点E之间各点的距离。求之间各点的距离。求A到到E的最短路

2、径。的最短路径。BACBDBCDEC4123123123221647248386756110643751管管 理理 运运 筹筹 学学2023-2-164用穷举法的计算量用穷举法的计算量:如果从如果从A A到到E E的站点有的站点有k k个，除个，除A A、E E之外每站有之外每站有3 3个位置则个位置则总共有总共有3 3k-1k-12 2条路径；条路径；计算各路径长度总共要进行计算各路径长度总共要进行 (k+1)3(k+1)3k-1k-12 2次加法以及次加法以及3 3k-k-1 12-12-1次比较。随着次比较。随着 k k 的值增加时，需要进行的加法和比较的的值增加时，需要进行的加法和比较

3、的次数将迅速增加；次数将迅速增加；例如当例如当 k=20k=20时，加法次数为时，加法次数为 4.25508339662274.255083396622710101515 次，次，比较比较 1.37260754729771.372607547297710101414 次。若用次。若用1 1亿次亿次/秒的计算机计算秒的计算机计算需要约需要约508508天。天。管管 理理 运运 筹筹 学学2023-2-165逆序解法逆序解法顺序解法顺序解法第二节基本概念、基本方程与最优化原理第二节基本概念、基本方程与最优化原理管管 理理 运运 筹筹 学学2023-2-166 1、阶段阶段k：表示决策顺序的离散的量

4、，阶段可以按时间或空间划分。：表示决策顺序的离散的量，阶段可以按时间或空间划分。2、状态状态sk：每个阶段开始时所处的自然状态或客观条件。状态可以是：每个阶段开始时所处的自然状态或客观条件。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。数量，也可以是字符，数量状态可以是连续的，也可以是离散的。3、决策决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为态的函数，记为xk(sk)D k(sk)。4、策略策略Pk,n(sk)：从第：从第k阶段开始到最后第阶段开始到最后第n阶段的决策序列，称阶段的决策序列

5、，称k子策略。子策略。P1,n(s1)即为全过程策略。即为全过程策略。5、状态转移方程状态转移方程 sk+1=Tk(sk,xk)：某一状态以及该状态下的决策，与下：某一状态以及该状态下的决策，与下一状态之间的函数关系。一状态之间的函数关系。6、指标函数指标函数rk(sk,uk)：衡量策略优劣的数量指标；：衡量策略优劣的数量指标；最优指标函数最优指标函数fk(sk)，f1(s1)。一、逆序解法一、逆序解法管管 理理 运运 筹筹 学学2023-2-167 对于可加性指标函数，上式可以写为对于可加性指标函数，上式可以写为 上式中上式中“opt”表示表示“max”或或“min”。对于可乘性指标函数，上

6、。对于可乘性指标函数，上式可以写为式可以写为 以上式子称为以上式子称为动态规划最优指标的递推方程动态规划最优指标的递推方程，是动态规划的基本，是动态规划的基本方程。方程。终端条件终端条件：为了使以上的递推方程有递推的起点，必须要设定最：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态优指标的终端条件，一般最后一个状态n+1下最优指标下最优指标fn+1(sn+1)=0。0)(1,1,)(),()(1111)(nnkkkkksDxkksfnnksfxsrsfoptkkk0)(1,1,)(),()(1111)(nnkkkkksDxkksfnnksfxsrsfoptkk

7、k基本方程基本方程管管 理理 运运 筹筹 学学2023-2-168最优化原理最优化原理作为整个过程的最优策略具有如下性质：作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，策必定构成最优子策略。就是说，最优策略的最优策略的任意子策略都是最优的。任意子策略都是最优的。管管 理理 运运 筹筹 学学2023-2-169二、顺序解法二、顺序解法状态转移方程状态转移方程 sk=Tk(sk+1,xk)最优指标函数最优指标函数 fk(sk+1

8、)，fn(sn+1)基本方程基本方程0)(,2,1)(),()(1011)(1sfnksfxsrsfkkkkksDxkkoptkkk0)(,2,1)(),()(1011)(1sfnksfxsrsfkkkkksDxkkoptkkk管管 理理 运运 筹筹 学学2023-2-1610一、基本步骤一、基本步骤1应将实际问题恰当地分割成应将实际问题恰当地分割成n个子问题个子问题(n个阶段个阶段)。通常是根据时间通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数型时，常取静态规划中变量的个数n

9、，即，即k=n。2正确地定义状态变量正确地定义状态变量sk，使它既能正确地描述过程的状态，又能，使它既能正确地描述过程的状态，又能满足无后效性满足无后效性动态规划中的状态与一般控制系统中和通常所说的状动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，必须具备以下三个态的概念是有所不同的，必须具备以下三个特征特征：(1)(1)要能够正确地描述受控过程的变化特征。要能够正确地描述受控过程的变化特征。(2)(2)要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响。段以后，过程的发展

10、不受前面各段状态的影响。(3)(3)要满足可知性。即所规定的各段状态变量的值，可以直接或间接要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。行累计的量。第三节第三节 动态规划建模与求解动态规划建模与求解管管 理理 运运 筹筹 学学2023-2-16113 3正确地定义决策变量及各阶段的允许决策集合正确地定义决策变量及各阶段的允许决策集合U Uk k(s sk k)，根据经验，一般将问题中待求的量，选作动态规划模型中的根据经验，一般将问题中待求的量，选作动态

11、规划模型中的决策变量。决策变量。4.4.能够能够正确地写出状态转移方程正确地写出状态转移方程，至少要能正确反映状态，至少要能正确反映状态转移规律。转移规律。5 5正确地构造出目标与变量的函数关系正确地构造出目标与变量的函数关系目标函数。目标函数。6 6写出动态规划函数写出动态规划函数基本方程基本方程管管 理理 运运 筹筹 学学2023-2-1612例例1 1：1 1、以上求从、以上求从A A到到E E的最短路径问题，可以转化为四个性质完的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从全相同，但规模较小的子问题，即分别从D Di i 、C Ci i、B Bi i、A A到

12、到E E的最短路径问题。的最短路径问题。第四阶段：两个始点第四阶段：两个始点D D1 1和和D D2 2，终点只有一个；，终点只有一个；分析得知：从分析得知：从D D1 1和和D D2 2到到E E的最短路径唯一。的最短路径唯一。阶段阶段4本阶段始点本阶段始点（状态）（状态）本阶段各终点（决策）本阶段各终点（决策）到到E的最短距离的最短距离本阶段最优终点本阶段最优终点（最优决策（最优决策)E D1 D2 10*6 10 6 E E二、离散变量二、离散变量-分段穷举算法分段穷举算法管管 理理 运运 筹筹 学学2023-2-1613 第三阶段：有三个始点第三阶段：有三个始点C1，C2，C3，终点有

13、，终点有D1，D2，对始点，对始点和终点进行分析和讨论分别求和终点进行分析和讨论分别求C1，C2，C3到到D1，D2 的最短的最短路径问题：路径问题：分析得知：如果经过分析得知：如果经过C1，则最短路为则最短路为C1-D2-E；如果经过如果经过C2，则最短路为则最短路为C2-D2-E；如果经过如果经过C3，则最短路为，则最短路为C3-D1-E。阶段阶段3本阶段始点本阶段始点（状态）（状态）本阶段各终点（决策）本阶段各终点（决策）到到E的最短距离的最短距离本阶段最优终点本阶段最优终点（最优决策（最优决策)D1 D2 C1 C2 C3 8+10=18 7+10=17 1+10=11 6+6=12

14、5+6=11 6+6=12 12 11 11 D2 D2 D1管管 理理 运运 筹筹 学学2023-2-1614第二阶段：有第二阶段：有4个始点个始点B1,B2,B3,B4，终点有，终点有C1,C2,C3。对始点。对始点和终点进行分析和讨论分别求和终点进行分析和讨论分别求B1,B2,B3,B4到到C1,C2,C3 的最短的最短路径问题：路径问题：分析得知：如果经过分析得知：如果经过B1，则走，则走B1-C2-D2-E；如果经过如果经过B2，则走，则走B2-C3-D1-E；如果经过如果经过B3，则走，则走B3-C3-D1-E；如果经过如果经过B4，则走，则走B4-C3-D1-E。阶段阶段2本阶段

15、始点本阶段始点（状态）（状态）本阶段各终点（决策）本阶段各终点（决策）到到E的最的最短距离短距离本阶段最优终本阶段最优终点（最优决策点（最优决策)C1 C2 C3 B1 B2 B3 B4 2+12=14 4+12=16 4+12=16 7+12=19 1+11=12 7+11=18 8+11=19 5+11=16 6+11=17 2+11=13 3+11=14 1+11=12 12 13 14 12 C2 C3 C3 C3管管 理理 运运 筹筹 学学2023-2-1615第一阶段：只有第一阶段：只有1个始点个始点A，终点有，终点有B1,B2,B3,B4。对始点和终。对始点和终点进行分析和讨论分

16、别求点进行分析和讨论分别求A到到B1,B2,B3,B4的最短路径问题：的最短路径问题：最后，可以得到：从最后，可以得到：从A到到E的最短路径为的最短路径为A B4 C3 D1 E 阶段阶段1本阶段始本阶段始点点(状态状态)本阶段各终点（决策）本阶段各终点（决策）到到E的最的最短距离短距离本阶段最优终本阶段最优终点点(最优决策最优决策)B1 B2 B3 B4 A4+12=16 3+13=163+14=172+12=14 14 B4管管 理理 运运 筹筹 学学2023-2-1616 以上计算过程及结果，可用图以上计算过程及结果，可用图2表示，可以看到，以上方表示，可以看到，以上方法不仅得到了从法不

17、仅得到了从A到到D的最短路径，同时，也得到了从图中的最短路径，同时，也得到了从图中任一点到任一点到E的最短路径。的最短路径。以上过程，仅用了以上过程，仅用了22次加法，计算效率远高于穷举法。次加法，计算效率远高于穷举法。BACBDBCDEC412312312332164724838675161060106121111121314144B127512管管 理理 运运 筹筹 学学2023-2-1617教材例教材例2三、连续变量三、连续变量管管 理理 运运 筹筹 学学2023-2-1618最短路径问题（例最短路径问题（例1 1）资源分配问题（投资问题）资源分配问题（投资问题）背包问题背包问题生产经营

18、问题生产经营问题系统可靠性问题系统可靠性问题设备更新问题设备更新问题机器负荷分配问题机器负荷分配问题货郎担问题货郎担问题第四节第四节 动态规划的应用动态规划的应用管管 理理 运运 筹筹 学学2023-2-1619 例例3.某公司拟将某种设备某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表所示，问这厂。各工厂获得此设备后，预测可创造的利润如表所示，问这5台设备应如何分配给这台设备应如何分配给这3个工厂，使得所创造的总利润为最大？个工厂，使得所创造的总利润为最大？工工 厂厂盈盈 利利设备台数设备台数 甲甲 厂厂 乙乙

19、厂厂 丙丙 厂厂 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 12资源分配问题资源分配问题管管 理理 运运 筹筹 学学2023-2-1620解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设厂。设 sk=分配给第分配给第k个厂至第个厂至第3个厂的设备台数（个厂的设备台数（k=1、2、3）。）。xk=分配给第分配给第k个厂设备台数。个厂设备台数。已知已知s1=5,并有并有 从从sk 与与xk 的定义，可知的定义，可知以下以下我们从第三阶段开始计算。我们从第

20、三阶段开始计算。222223),(xsxsTs33xs 111112),(xsxsTs管管 理理 运运 筹筹 学学2023-2-1621 第三阶段第三阶段:显然将显然将s3(s3=0,1,2,3,4,5)台设备都分配给第台设备都分配给第3工厂时，工厂时，也就是也就是s3=x3时，第时，第3阶段的指标值（即第阶段的指标值（即第3厂的盈利）厂的盈利）为最大，即为最大，即 由于第由于第3阶段是最后的阶段，故有阶段是最后的阶段，故有 其中其中x3可取值为可取值为0,1,2,3,4,5。其数值计算见表。其数值计算见表106。).,(),(max)(333333333ssrxsrsfx),(),(max3

21、333333ssrxsrx管管 理理 运运 筹筹 学学2023-2-1622012345000014 4126623111134121245121253x3s),(333xsr)(33sf3*x管管 理理 运运 筹筹 学学2023-2-1623 其中其中x*3表示取表示取3子过程上最优指标值子过程上最优指标值f3(s3)时的时的x3决策，决策，例如在表中可知当例如在表中可知当s3=4时，有时，有r3(4,4)=12,有有f3(4)=12此时此时x*3=4，即当，即当s3=4 时，此时取时，此时取x3=4（把（把4台设备分配给第台设备分配给第3厂）是最优决策，此时阶段指标值厂）是最优决策，此时阶

22、段指标值（盈利）为（盈利）为12，最优，最优3子过程最优指标值也为子过程最优指标值也为12。管管 理理 运运 筹筹 学学2023-2-1624第二阶段：第二阶段：当把当把s2=0,1,2,3,4,5台设备分配给第台设备分配给第2工厂和第工厂和第3工厂时，则对每个工厂时，则对每个s2值，有一种最优分配方案，值，有一种最优分配方案，使最大盈利即最优使最大盈利即最优2子过程最优指标函数值为子过程最优指标函数值为)(),(max)(33222222sfxsrsfx因为因为s3=s2-x2上式也可写成上式也可写成)(),(max)(223222222xsfxsrsfx管管 理理 运运 筹筹 学学2023

23、-2-16250123450 00104 51206 54 1023011 56 110 1424012 114110 161,25012 512 1161141102122x2s)(),(223222xsfxsr)(22sf2*x00050104101156101110管管 理理 运运 筹筹 学学2023-2-1626第一阶段：第一阶段：把把 台设备分配给第台设备分配给第1，第，第2，第，第3厂时，最大盈利为厂时，最大盈利为其中可取值其中可取值0,1,2,3,4,5。数值计算见表。数值计算见表 )5(11ss),5(),5(max)5(111111xfxrfx1x0123455 316 9+

24、10 12+5 13+0 21 0,21x1s)5(),5(1211xfxr210147)(1xf1*x管管 理理 运运 筹筹 学学2023-2-1627然后按计算表格的顺序推算，可知最优分配方案有两个：然后按计算表格的顺序推算，可知最优分配方案有两个：1.由于由于x*1=0，根据，根据s2=s1-x*1=5，查表，查表107可知可知x*2=2，再，再由由s3=s2-x*2=3，求得，求得x*3=s3=3。即分配给甲厂。即分配给甲厂0台，乙厂台，乙厂2台，台，丙厂丙厂3台。台。2.由于由于x*1=2，根据，根据s2=s1-x*1=3，查表，查表107可可知知x*2=2，再由再由s3=s2-x*

25、2=1,求得求得x*3=s3=1，即分配给甲厂，即分配给甲厂2台，台，乙厂乙厂2台，丙厂台，丙厂1台。台。这两种分配方案都能得到最高的总盈利这两种分配方案都能得到最高的总盈利21万元。万元。管管 理理 运运 筹筹 学学2023-2-1628 设有设有n种物品，每一种物品数量无限。第种物品，每一种物品数量无限。第i种物品每件重种物品每件重量为量为wi公斤，每件价值公斤，每件价值ci元。现有一只可装载重量为元。现有一只可装载重量为W公斤公斤的背包，求各种物品应各取多少件放入背包，使背包中物的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。品的价值最高。这个问题可以用整数规划模型来描述

26、。设这个问题可以用整数规划模型来描述。设xi为第为第i种物品种物品装入背包的件数（装入背包的件数（i=1,2,n），背包中物品的总价值为），背包中物品的总价值为z，则则 max z=c1x1+c2x2+cnxn s.t.w1x1+w2x2+wnxnW x1,x2,xn 0 且为整数。且为整数。背包问题背包问题管管 理理 运运 筹筹 学学2023-2-1629 下面用动态规划逆序解法求解它。设下面用动态规划逆序解法求解它。设阶段变量阶段变量k：第：第k次装载第次装载第k种物品（种物品（k=1,2,n）状态变量状态变量sk：第：第k次装载时背包还可以装载的重量；次装载时背包还可以装载的重量；决策变

27、量决策变量xk：第：第k次装载第次装载第k种物品的件数；种物品的件数；状态转移方程：状态转移方程：sk+1=sk wkxk；阶段指标：阶段指标：rk=ckxk；最优过程指标函数最优过程指标函数fk(sk)：第：第k到到n阶段容许装入物品的最大使用价值；阶段容许装入物品的最大使用价值；递推方程：递推方程：fk(sk)=max ckxk+fk+1(sk+1)=max ckxk+fk+1(sk wkxk)；x Dk(sk)终端条件：终端条件：fn+1(sn+1)=0。管管 理理 运运 筹筹 学学2023-2-1630例例4.某咨询公司有某咨询公司有10个工作日可以去处理四种类型的咨询项目，个工作日可

28、以去处理四种类型的咨询项目，每种类型的咨询项目中待处理的客户数量、处理每个客户所需工每种类型的咨询项目中待处理的客户数量、处理每个客户所需工作日数以及所获得的利润如表所示。显然该公司在作日数以及所获得的利润如表所示。显然该公司在10天内不能处天内不能处理完所有的客户，它可以自己挑选一些客户，其余的请其他咨询理完所有的客户，它可以自己挑选一些客户，其余的请其他咨询公司去做，应如何选择客户使得在这公司去做，应如何选择客户使得在这10个工作日中获利最大？个工作日中获利最大？咨询项目类型咨询项目类型待处理客户数待处理客户数处理每个客户所处理每个客户所需工作日数需工作日数处理每个客处理每个客户所获利润户

29、所获利润123443221347281120管管 理理 运运 筹筹 学学2023-2-1631解：用动态规划来求解此题。解：用动态规划来求解此题。我们把此问题分成四个阶段：我们把此问题分成四个阶段：第一阶段我们决策将处理多少个第一种咨询项目类型中的客户，第一阶段我们决策将处理多少个第一种咨询项目类型中的客户，第二阶段决策将处理多少个第二种咨询项目类型中的客户，第二阶段决策将处理多少个第二种咨询项目类型中的客户，第三阶段、第四阶段我们也将作出类似的决策。我们设第三阶段、第四阶段我们也将作出类似的决策。我们设sk分配给第分配给第k种咨询项目到第四种咨询项目的所有客户的总工作日种咨询项目到第四种咨询

30、项目的所有客户的总工作日（第（第k阶段的状态变量）。阶段的状态变量）。xk=在第在第k种咨询项目中处理客户的数量（第种咨询项目中处理客户的数量（第k阶段的决策变量）。阶段的决策变量）。已知已知s110并有并有管管 理理 运运 筹筹 学学2023-2-1632从第四阶段开始计算：从第四阶段开始计算：显然将显然将s4个工作日个工作日s4=(0,1,2,10)尽可能分配给第四类咨询项尽可能分配给第四类咨询项目，即目，即x4=s4/7时，第四阶段的指标值为最大，其中时，第四阶段的指标值为最大，其中s4/7表示取表示取不大于不大于s4/7的最大整数，符号的最大整数，符号 为取整符号，故有为取整符号，故有

31、由于第四阶段是最后的阶段，故有由于第四阶段是最后的阶段，故有,3),(222223xsxsTs.4),(333334xsxsTs).7/,(),(max4444444ssrxsrx),7/,(),(max)(4444*44444ssrxsrsfx,),(111112xsxsTs管管 理理 运运 筹筹 学学2023-2-1633因为因为s4至多为至多为10，其数值计算见表，其数值计算见表010001002003004005006007020180201902011002014x4s),(444xsr)(44sf4*x000000020202020管管 理理 运运 筹筹 学学2023-2-1634

32、第三阶段：第三阶段：当把当把s3=(0,1,2,10)个工作日分配给第四类和第三类咨询项目个工作日分配给第四类和第三类咨询项目时，则对每个时，则对每个s3值，都有一种最优分配方案，使其最大盈利即最值，都有一种最优分配方案，使其最大盈利即最优优3子过程最优指标函数值为子过程最优指标函数值为 因为因为因为因为s3 至多为至多为10，所以所以x3的取值可为的取值可为0,1,2。其数值计算见表。其数值计算见表1011。.)(),(max)(33222222sfxsrsfx2233xss.)4(),(max)(334333333xsfxsrsfx管管 理理 运运 筹筹 学学2023-2-1635 0 1

33、 2000 1 00 200 300 40011 1 50011 1 60011 1 7 11+0 20 0 8020 11+0 22 2 9020 11+0 22 2 10020 11+0 22 23x3s)4(),(334333xsfxsr)(33sf3*x00000020001101101102202202200管管 理理 运运 筹筹 学学2023-2-1636 第二阶段：第二阶段：同样以每个同样以每个s2值都有一种最优分配方案，使其最大盈利即值都有一种最优分配方案，使其最大盈利即最优最优2子过程最优指标函数值为：子过程最优指标函数值为：因为，故有因为，故有因为因为s2至多为至多为10，

34、所以，所以x2的取值为的取值为0,1,2,3。.)3(),(max)(223222222xsfxsrsfx2233xss.)3(),(max)(223222222xsfxsrsfx管管 理理 运运 筹筹 学学2023-2-1637管管 理理 运运 筹筹 学学2023-2-1638 第一阶段：第一阶段：我们已知，又因为我们已知，又因为 ，同样有，同样有 因为因为 ,故可取值为故可取值为0,1,2,10。101s.)(),(max)(112111111xsfxsrsfx112xss.)10(),10(max)10(121111xfxrfx101s1x管管 理理 运运 筹筹 学学2023-2-163

35、9可知可知f1(10)=28，x*1=0从而得从而得s2=s1-x*110010s2=10的这一行可知的这一行可知x*2=1，由，由s3=s2-3x*17s3=7的这一行可知的这一行可知x*3=0，最后由，最后由s4=s3-x*3 7s4=7 这一行得这一行得x*4=1综上所述得最优解为：综上所述得最优解为：x*1=0,x*2=1，x*3=0，x*4=1,最大盈利为最大盈利为28。现在我们不妨假设该咨询公司的工作计划有所改变，只有现在我们不妨假设该咨询公司的工作计划有所改变，只有8个工作日个工作日来来处理这四类咨询项目，那么该咨询公司如何选择客户使得获利最大呢？我处理这四类咨询项目，那么该咨询

36、公司如何选择客户使得获利最大呢？我们们不必从头开始重做这个问题不必从头开始重做这个问题，而只要在第一阶段上把，而只要在第一阶段上把s1改成改成8，重新计，重新计算就可得到结果，这是动态规划的一个算就可得到结果，这是动态规划的一个好处好处。管管 理理 运运 筹筹 学学2023-2-1640得到两组最优解如下：得到两组最优解如下：它们的最优解（即最大盈利）都为它们的最优解（即最大盈利）都为22。一旦咨询的工作日一旦咨询的工作日不是减少而是增加不是减少而是增加，那么我们不仅要重新计，那么我们不仅要重新计算第一阶段，而且要在第二、第三、第四阶段的计算表上补上增加算第一阶段，而且要在第二、第三、第四阶段

37、的计算表上补上增加的工作日的新的信息，也可得到新的结果。的工作日的新的信息，也可得到新的结果。1001)4*3*2*1*xxxx管管 理理 运运 筹筹 学学2023-2-1641 例例5 5.某公司为主要电力公司生产大型变压器，由于电力某公司为主要电力公司生产大型变压器，由于电力采取预订方式购买，所以该公司可以预测未来几个月的需求采取预订方式购买，所以该公司可以预测未来几个月的需求量。为确保需求，该公司为新的一年前四个月制定一项生产量。为确保需求，该公司为新的一年前四个月制定一项生产计划，这四个月的需求如表所示。计划，这四个月的需求如表所示。生产成本随着生产数量而变化。调试费为生产成本随着生产

38、数量而变化。调试费为4 4，除了调度费用，除了调度费用外，每月生产的头两台各花费为外，每月生产的头两台各花费为2 2，后两台花费为，后两台花费为1 1。最大生。最大生产能力每月为产能力每月为4 4台。台。生产与存贮问题生产与存贮问题管管 理理 运运 筹筹 学学2023-2-1642每台变压器在仓库中由这个月存到下个月的储存费为每台变压器在仓库中由这个月存到下个月的储存费为1 1，仓库的最大储存能力为仓库的最大储存能力为3 3台，另外，知道在台，另外，知道在1 1月月1 1日时仓库里日时仓库里存有一台变压器，要求在存有一台变压器，要求在4 4月月3030日仓库的库存量为零。试问日仓库的库存量为零

39、。试问该公司应如何制定生产计划，使得四个月的生产成本和储该公司应如何制定生产计划，使得四个月的生产成本和储存总费用最少？存总费用最少？管管 理理 运运 筹筹 学学2023-2-1643解：我们按月份来划分阶段，第解：我们按月份来划分阶段，第i个月为第个月为第i阶段阶段：（：（i=1,2,3,4).设设 为第为第k阶段期初库存量；阶段期初库存量；k=1,2,3,4 为第为第k阶段生产量；阶段生产量；k=1,2,3,4为第为第k阶段需求量；阶段需求量；k=1,2,3,4，这已在表，这已在表10-15中告诉我们。中告诉我们。因为下个月的库存量等于上个月的库存量加上上个月的产量减去上个因为下个月的库存

40、量等于上个月的库存量加上上个月的产量减去上个月的需求量，我们就得到了如下状态转移方程：月的需求量，我们就得到了如下状态转移方程：因为，故有因为，故有因为，故有因为，故有kxkd,1112dxss11s,1121dxss,2223dxss,3334dxss,4445dxss05s,4440dxsks管管 理理 运运 筹筹 学学2023-2-1644由于必须要满足需求，则有由于必须要满足需求，则有通过移项得到通过移项得到 另一方面，第另一方面，第k阶段的生产量必不大于同期的生产能力（阶段的生产量必不大于同期的生产能力（4台），也台），也不大于第不大于第k阶段至第四阶段的需求之和与第阶段至第四阶段的

41、需求之和与第k阶段期初库存量之差，否阶段期初库存量之差，否则第则第k阶段的生产量就要超过从第阶段的生产量就要超过从第k阶段至第四阶段的总需求，故有阶段至第四阶段的总需求，故有以下我们从第四阶段开始计算：以下我们从第四阶段开始计算：从以上的状态转移方程可知从以上的状态转移方程可知这样就有这样就有),4,3,2,1(,kdxskkkkkksdxkx44,)(minkikiksdx,0444dxs,34444ssdx)3,(),(min)(444444444ssrxsrsfx管管 理理 运运 筹筹 学学2023-2-1645 这里的阶段指标可以分成两部分，即生产成本与这里的阶段指标可以分成两部分，即

42、生产成本与储存费，即为储存费，即为 由于第四阶段末要求库存为零，即有，由于第四阶段末要求库存为零，即有，这样可得这样可得 对于每个的可行值，的值列于表对于每个的可行值，的值列于表),(nnnxsr),()(),(nnnnnnnnxshxcxsr001),(444xsh)3()3,()3()3,()(444444444444scsshscssrsf4s)(44sf管管 理理 运运 筹筹 学学2023-2-1646表中当时，可知第四阶段要生产表中当时，可知第四阶段要生产台，从表可知总成本为台，从表可知总成本为9，同样可以算出当，同样可以算出当 为为1,2,3时的情况，结果已列时的情况，结果已列于表

43、中。于表中。第三阶段：第三阶段：此时有：此时有：因为以及所以有因为以及所以有例如，当第三阶段初库存量时，生产量为例如，当第三阶段初库存量时，生产量为2时，时，则所以生产成本为则所以生产成本为8，第三阶段末库存，第三阶段末库存为为2时，储存费为，而时，储存费为，而04s3344sx4s)(1)(),()(),(3333333333333dxsxcxshxcxsr,3334dxss,13d)()1(1)(min)(443333)4,4min(133333sfxsxcsfsxs)1()1(1)(min3343333)4,4min(1333xsfxsxcsxs13s3x2121333dxs221),2

44、()()(4333444fdxsfsf管管 理理 运运 筹筹 学学2023-2-1647可知，这样可知，可知，这样可知，填入表中的栏内，其他结果如表：填入表中的栏内，其他结果如表：第二阶段：第二阶段：因为所以有因为所以有6)2(4f,16628)2()2,1(43 fr2,133xs,422232dxssd管管 理理 运运 筹筹 学学2023-2-1648 计算结果如表所示。计算结果如表所示。表表)(),(min)(33222)4,8min(422222sfxsrsfsxs)(),()(min3322222)4,8min(4222sfxshxcsxs)()(1)(min222322222)4,

45、8min(4222dxsfdxsxcsxs)4()4(1)(min2232222)4,8min(4222xsfxsxcsxs管管 理理 运运 筹筹 学学2023-2-1649第一阶段：第一阶段：因为故有因为故有计算结果见表。计算结果见表。,1,2211111sdxssd)(),(min)1()(22111411111sfxsrfsfx)21()21(1)(min12111411xfxxcx管管 理理 运运 筹筹 学学2023-2-1650利用递推关系可以得到两组最优解：利用递推关系可以得到两组最优解：这时有最低总成本这时有最低总成本29。0441)4321xxxx3042)4321xxxx管管

46、 理理 运运 筹筹 学学2023-2-1651教材例教材例8管管 理理 运运 筹筹 学学2023-2-1652 例例6.某科研项目组由三个小组用不同的手段分别研究，它们失败的某科研项目组由三个小组用不同的手段分别研究，它们失败的概率各为概率各为0.40，0.60，0.80。为了减少三个小组都失败的可能性，现决。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表：败概率如下表：问如何分派科学家才能使三个小组都失败的概率（即科研项目最终问如何分派科学家才能使三个小组都失败的概率

47、（即科研项目最终失败的概率）最小？失败的概率）最小？高级科学家高级科学家小组小组12300.400.600.8010.200.400.5020.150.200.30系统可靠性问题系统可靠性问题管管 理理 运运 筹筹 学学2023-2-1653 解：用逆序算法。设解：用逆序算法。设 阶段：每个研究小组为一个阶段，且阶段：每个研究小组为一个阶段，且阶段阶段123小组小组123管管 理理 运运 筹筹 学学2023-2-1654计算计算当当n=3时，时，当当n=2时，时，s3 f3*(s3)x3*008001050120302 x2s2f2(s2,x2)=P2(x2)f3*(s2-x2)f2*(s2)

48、x2*012004804801030032030020180200160162管管 理理 运运 筹筹 学学2023-2-1655 当当n=1时，时，最优解为最优解为 x1*=1，x2*=0，x3*=1；科研项目最终失败的概率为；科研项目最终失败的概率为0.060。x1s1f1(s1,x1)=P1(x1)f2*(s1-x1)f2*(s2)x2*01220064 0060 0072 0060 1管管 理理 运运 筹筹 学学2023-2-1656教材例教材例9设备更新问题设备更新问题管管 理理 运运 筹筹 学学2023-2-1657顺序解法顺序解法管管 理理 运运 筹筹 学学2023-2-1658习习 题题7.27.27.37.37.47.47.87.87.147.14