第六章动态规划课件

第六章动态规划§1问题的提出§2基本概念、基本方程与最优化原理§3动态规划的应用1精选课件ppt§1问题的提出一、引例——最短路径问题

下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。BACBDBCDEC4123123123221647248386756110637512精选课件ppt§1问题的提出用穷举法的计算量，非常大。讨论：1、以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di、Ci、Bi、A到E的最短路径问题。

第四阶段：两个始点D1和D2，终点只有一个；

表6-1分析得知：从D1和D2到E的最短路径唯一。阶段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)ED1D210*6106EE3精选课件ppt

第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2的最短路径问题：

表6-2分析得知：如果经过C1，则最短路为C1-D2-E；如果经过C2，则最短路为C2-D2-E；如果经过C3，则最短路为C3-D1-E。

§1问题的提出阶段3本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111D2D2D14精选课件ppt第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3的最短路径问题：

表6-3

分析得知：如果经过B1，则走B1-C2-D2-E；如果经过B2，则走B2-C3-D1-E；如果经过B3，则走B3-C3-D1-E；如果经过B4，则走B4-C3-D1-E。

§1问题的提出阶段2本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C35精选课件ppt

第一阶段：只有1个始点A，终点有B1,B2,B3,B4。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：

表6-4最后，可以得到：从A到E的最短路径为A

B4

C3

D1

E§1问题的提出阶段1本阶段始点(状态)本阶段各终点（决策）到E的最短距离本阶段最优终点(最优决策)B1B2B3B4A4+12=163+13=163+14=172+12=1412C26精选课件ppt

以上计算过程及结果，可用图2表示，可以看到，以上方法不仅得到了从A到E的最短路径，同时，也得到了从图中任一点到E的最短路径。

以上过程，仅用了22次加法，计算效率远高于穷举法。BACBDBCDEC41231231233216472483867516106010612111112131414127512§1问题的提出7精选课件ppt§1问题的提出从引例的求解过程中可以得到以下启示：（1）对一个问题是否用上述方法求解，其关键在与能否将问题转化为相互联系的多个阶段的决策问题。（2）对问题的求解是从全局考虑解决局部（阶段）的问题。（3）各阶段选取的决策依赖于当前的状态，又随即引起状态的转移，整个决策序列就是在变化的状态中产生出来，故有“动态”含义。（4）决策过程是与阶段发展过程逆向而行。8精选课件ppt§1问题的提出二、动态规划的含义及适用范围1.动态规划

动态规划是解决一类多阶段决策问题的优化方法，它是考察问题的一种途径，而不是一种算法。

多阶段决策问题：把一个问题看作是一个前后关联具有链状结构的多阶段过程，也称为序贯决策过程。

2.适用范围

如果一个问题可将其过程划分为若干个相互联系的阶段问题，且它的每一阶段都需要进行决策，则这类问题均可用动态规划方法进行求解。

9精选课件ppt一、基本概念

1.阶段和阶段变量用动态规划方法求解问题时，首先将问题的全过程适当地分成若干个互相联系的阶段，以便能按一定的次序去求解。阶段的划分，一般根据时序和空间的自然特征来划分。如引例可按照空间划分为4个阶段。

阶段变量：描述阶段的变量称为阶段变量。用k表示，引例中，k=1,2,3,4.

2.状态和状态变量sk

状态就是阶段的起始位置。它既是该阶段某支路的起点，又是前一阶段某支路的终点。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。

§2基本概念、基本方程与最优化原理10精选课件ppt§2基本概念、基本方程与最优化原理

状态变量：描述过程状态的变量称为状态变量。它可用一个数、一组数或一向量（多维情形）来描述，常用sk第k阶段的状态变量。通常一个阶段有若干个状态。第k阶段的状态就是该阶段所有始点的集合。3.决策与决策变量决策：在某阶段对可供选择状态的决定（或选择）。决策变量：描述决策的变量。常用xk(sk)表示第k阶段处于状态sk时的决策变量，它是状态变量的函数。4.策略与子策略

策略是一个决策序列的集合。由所有各阶段的决策组成的决策函数序列称为全过程策略，简称策略，记为：P1,n(s1)。

子策略：从第k个阶段开始到最后阶段的决策组成的决策函数序列称为k子过程策略，简称子策略，记为：Pk,n(sk)

最优策略：能够达到总体最优的策略。11精选课件ppt§2基本概念、基本方程与最优化原理5.状态转移方程

它是确定过程由某一阶段的一个状态到下一阶段另一状态的演变过程，用sk+1=Tk(sk,xk)表示。该方程描述了第k阶段到第k+1阶段的状态转移规律。因此又称为状态转移函数。6.阶段指标函数rk(sk,xk)

从状态sk出发，选择决策xk所产生的第k阶段指标。7.最优指标函数fk(sk)表示从第k阶段的状态sk开始采用最优子策略，到第n阶段的终止时所得到的最优指标函数值。

12精选课件ppt二、基本方程最优指标的递推方程（动态规划的基本方程）：

对于可加性指标函数，上式可以写为

上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以写为

终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1)=0。§2基本概念、基本方程与最优化原理13精选课件ppt三、最优化原理

作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。§2基本概念、基本方程与最优化原理14精选课件ppt§2基本概念、基本方程与最优化原理四、动态规划求解过程

（1）将问题的过程划分成恰当的阶段；（2）正确选择状态变量sk，使它能够恰当地描述过程的演变；（3）确定决策变量xk；（4）正确写出状态转移方程sk+1=Tk(sk,xk)；（5）写出最优指标的递推方程：

fn+1(sn+1)=0终点条件15精选课件ppt一、资源分配问题

例2.某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表10-5所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？

表8-5盈利工厂设备台数甲厂乙厂丙厂000013542710639111141211125131112§3动态规划的应用16精选课件ppt解：（1）划分阶段：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。

（2）确定状态变量：设sk=分配给第k个厂至第3个厂的设备台数（k=1、2、3）。

（3）确定决策变量：设xk=分配给第k个设备台数。

（4）写出状态转移方程。已知s1=5,并有§3动态规划的应用17精选课件ppt第三阶段:

表6－6

01234500－－－－－001－4－－－－412－－6－－－623－－－11－－1134－－－－12－1245－－－－－12125§3动态规划的应用18精选课件ppt第二阶段：

表6－7

0123450－－－－－0010＋4

－－－－5120＋65＋4－－－10230＋115＋611＋0－－14240＋1211＋411＋0－161,250＋125＋1211＋611＋411＋0212§3动态规划的应用19精选课件ppt

第一阶段：把台设备分配给第1，第2，第3厂时，最大盈利为其中可取值0,1,2,3,4,5.数值计算见表8－8

表6-8然后按计算表格的顺序推算，可知最优分配方案有两个：1.由于，根据，查表6－7可知，再由，求得。即分配给甲厂0台，乙厂2台，丙厂3台。2.由于，根据，查表6－7可

0123455

3＋169+1012+513+0210,2§3动态规划的应用20精选课件ppt知，再由,求得，即分配给甲厂2台，乙厂2台，丙厂1台。这两种分配方案都能得到最高的总盈利21万元。

§3动态规划的应用21精选课件ppt二、背包问题

设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设xi为第i种物品装入背包的件数（i=1,2,…,n），背包中物品的总价值为z，则Maxz=c1x1+c2x2+…+cnxns.t.w1x1+w2x2+…+wnxn≤Wx1,x2,…,xn

0

且为整数。§3动态规划的应用22精选课件ppt下面用动态规划逆序解法求解它。设（1）阶段变量k：第k次装载第k种物品（k=1,2,…,n）（2）状态变量sk：第k次装载时背包还可以装载的重量；（3）决策变量uk=xk：第k次装载第k种物品的件数；（4）状态转移方程：sk+1=sk

wkxk；（5）最优过程指标函数fk(sk)：第k到n阶段容许装入物品的最大使用价值；阶段指标：rk=ckxk；递推方程：

fk(sk)=max{ckxk+fk+1(sk+1)}=max{ckxk+fk+1(sk

wkxk)}；x

Dk(sk)终端条件：

fn+1(sn+1)=0。§3动态规划的应用23精选课件ppt

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

咨询项目类型待处理客户数处理每个客户所需工作日数处理每个客户所获利润123443221347281120§3动态规划的应用24精选课件ppt

解：用动态规划来求解此题。

（1）把此问题分成四个阶段，第一阶段我们决策将处理多少个第一种咨询项目类型中的客户，第二阶段决策将处理多少个第二种咨询项目类型中的客户，第三阶段、第四阶段我们也将作出类似的决策。

（2）设状态变量

＝分配给第k种咨询项目到第四种咨询项目的所有客户的总工作日（第k阶段的状态变量）。

（3）设决策变量

=在第k种咨询项目中处理客户的数量（第k阶3段的决策变量）。

（4）写出状态转移方程已知＝10，并有

§3动态规划的应用25精选课件ppt

并从与的定义可知

从第四阶段开始计算：显然将个工作日尽可能分配给第四类咨询项目，即时，第四阶段的指标值为最大，其中，表示取不大于的最大整数，符号为取整符号，故有由于第四阶段是最后的阶段，故有§3动态规划的应用26精选课件ppt

因为至多为10，其数值计算见表6－10。

表6－10

010－001－002－003－004－005－006－0070201802019020110011§3动态规划的应用27精选课件ppt

第三阶段：当把个工作日分配给第四类和第三类咨询项目时，则对每个值，都有一种最优分配方案，使其最大盈利即最优3子过程最优指标函数值为

因为因为至多为10，所以的取值可为0,1,2。其数值计算见表6－11。§3动态规划的应用28精选课件ppt

表6－11

0120－－001－－002－－003－－0040＋0－11150＋0－11160＋0－111711+0－20080＋2011+022290＋2011+0222100＋2011+0222§3动态规划的应用29精选课件ppt

第二阶段：同样以每个值都有一种最优分配方案，使其最大盈利即最优2子过程最优指标函数值为：因为，故有因为至多为10，所以的取值为0,1,2,3。其数值计算见表6－12。§3动态规划的应用30精选课件ppt§3动态规划的应用表6-1231精选课件ppt

第一阶段：我们已知，又因为，同样有

因为,故可取值为0,1,2,…,10。其数值计算见表6－13。表6－13§3动态规划的应用32精选课件ppt从表6－13可知，从而得＝10－0＝10，在表6－12的的这一行可知，由，查表6－11的的这一行可知，最后由，查表6-10的的这一行得，综上所述得最优解为：此时最大盈利为28。现在我们不妨假设该咨询公司的工作计划有所改变，只有8个工作日来处理这四类咨询项目，那么该咨询公司如何选择客户使得获利最大呢？我们不必从头开始重做这个问题，而只要在第一阶段上把改成8，重新计算就可得到结果，如表6－14所示，这是动态规划的一个好处。

§3动态规划的应用33精选课件ppt

表6－14

如上一样可从表6－14,6－12,6－11,6－10得到两组最优解如下：

它们的最优解（即最大盈利）都为22。一旦咨询的工作日不是减少而是增加，那么我们不仅要重新计算第一阶段，而且要在第二、第三、第四阶段的计算表上补上增加的工作日的新的信息，也可得到新的结果。§3动态规划的应用34精选课件ppt

实际上，背包问题我们也可以用整数规划来求解，如果背包携带物品重量的限制为W公斤，这N种物品中第i种物品的重量为，价值为，第i种物品的总数量的，我们可以设表示携带第i种物品的数量，则其数学模型为：S.T.且为整数。

我们不妨用此模型去求解例3，也一定得出同样的结果。§3动态规划的应用35精选课件ppt三、生产与存贮问题例4.某公司为主要电力公司生产大型变压器，由于电力采取预订方式购买，所以该公司可以预测未来几个月的需求量。为确保需求，该公司为新的一年前四个月制定一项生产计划，这四个月的需求如表6－15所示。生产成本随着生产数量而变化。调试费为4，除了调度费用外，每月生产的头两台各花费为2，后两台花费为1。最大生产能力每月为4台，生产成本如表6－16所示。

表6－15

§3动态规划的应用36精选课件ppt

表6－16

每台变压器在仓库中由这个月存到下个月的储存费为1，仓库的最大储存能力为3台，另外，知道在1月1日时仓库里存有一台变压器，要求在4月30日仓库的库存量为零。试问该公司应如何制定生产计划，使得四个月的生产成本和储存总费用最少？解：（1）我们按月份来划分阶段，第i个月为第i阶段：（i=1,2,3,4).（2）设为第k阶段期初库存量；k=1,2,3,4

§3动态规划的应用37精选课件ppt

（3）为第k阶段生产量；k=1,2,3,4为第k阶段需求量；k=1,2,3,4，这已在表10-15中告诉我们。（4）写出状态转移方程

因为下个月的库存量等于上个月的库存量加上上个月的产量减去上个月的需求量，我们就得到了如下状态转移方程：因为，故有

因为，故有

§3动态规划的应用38精选课件ppt

由于必须要满足需求，则有

通过移项得到

另一方面，第k阶段的生产量必不大于同期的生产能力（4台），也不大于第k阶段至第四阶段的需求之和与第k阶段期初库存量之差，否则第k阶段的生产量就要超过从第k阶段至第四阶段的总需求，故有

以下我们从第四阶段开始计算：从以上的状态转移方程可知这样就有

§3动态规划的应用39精选课件ppt

这里的阶段指标可以分成两部分，即生产成本与储存费，即为由于第四阶段末要求库存为零，即有，这样可得对于每个的可行值，的值列于表6－17。

表6－17§3动态规划的应用40精选课件ppt

表中当时，可知第四阶段要生产台，从表6－16可知总成本为9，同样可以算出当为1,2,3时的情况，结果已列于表6－17中。第三阶段：此时有：因为

以及

所以有例如，当第三阶段初库存量时，生产量为2时，则