逆序解法与顺序解法课件

1

为从初始阶段出发到第k阶段状态sk

止采取最优子策略或最优策略所获得的最优指标函数值。为系统在第k阶段状态sk

时采取决策的阶段指标。状态变量sk

则描述该阶段结束时的系统状况。状态转移方程：

从本质上讲，顺序解法和逆序解法原理（除去其方向因素外）是相同的，在具体的求解过程中，都是将原问题转化为一系列单个问题的求解。但是，两种方法各有优势，前向法求解下面例8.3时，有明显的优势。一般地，当初始状态给定时，用逆推法比较方便；当终止状态给定时，用顺推法比较方便。后向法求出了各点到目标地的最短路线；而前向法求出了起点到各目的地的最短路线。这里，2

【例8.3】图8.3所示为一水利网络，为水库，分别为不同的供水目的地，试找出给各供水目的地供水的最短路线。例8.323113212432421C1C3D1AB1B3B2D2C2图8.33线性规划和非线性规划所研究的问题，通常都是与时间无关的，故又可以称为静态规划；静态规划与动态规划在很多情况下（原则上）是可以相互转换的。动态规划可以看作是求d1,d2,…,dn

使得指标函数v1n(d1,d2,…,dn

)达到最优的极值问题，状态转移方程，起始条件以及允许状态集，允许决策集等是约束条件，原则上它可以用线性规划或非线性规划方法求解；反过来，一些静态规划只要适当引入阶段变量、状态、决策变量等要素就可以用动态规划方法来求解。

8.3

动态规划应用举例动态规划和静态规划4

所谓资源分配问题，就是将数量一定的一种或若干种资源(如资金、原材料、机器设备、劳动力等)恰当的分配给若干个使用者，从而使得总的经济效益最大。一种资源分配问题可叙述如下：设有数量为a

的某种资源，用于生产n

种产品，若以数量为xi

的资源投入第i种产品的生产，其收益相应的为gi

(xi)，问如何分配这种资源，才能使得生产n种产品的总收入最大？

8.3.1

资源分配问题5(2)状态变量：

(1)阶段变量：表示分配用于生产第种产品至第,这里把资源分配给一个或者几个使用者的过程作为一个阶段。种产品的原料数量；其静态规划的数学模型的形式一般为：转化成动态规划模型为：6注：利用动态规划进行逐段计算，最后求得即为所求问题的最大总收入。

(3)决策变量：(6)递推关系式：表示分配给生产第种产品的原料数，允许决策集：；(4)状态转移方程：(5)阶段指标：；；7p205例4巡逻队问题阶段变量k：把9只巡逻队往三个部位派遣依次分成三个阶段（k=1,2,3

）决策变量xk：表示第k阶段派出巡逻队数状态变量sk：表示第k阶段派出巡逻队后，剩余的巡逻队数状态转移方程：sk-1=

sk

+

xk阶段指标

pk(xk)

：表示第k阶段派出巡逻队xk时，该阶段的预期损失值解（顺序解法）8p205例4巡逻队问题（续）递推关系式：当k=1时，(s0=9)

x1

s1p1(

x1)f1(s1)x1*2345101046141437181829当k=2时

x2

s2p2(

x2)+f1(s1)f2(s2)x2*2342-35+1031+14453或4338+1035+1431+18482438+1435+18-522当k=3时

x3

s3p3(

x3)+f2(s2)f23(s3)x3*234024+4522+4821+52692结果10p205例4巡逻队问题阶段变量k：把9只巡逻队往三个部位派遣依次分成三个阶段（k=1,2,3

）决策变量xk：表示第k阶段派出巡逻队数状态变量sk：表示第k阶段初可派遣的巡逻队数状态转移方程：sk+1=

sk

-

xk阶段指标

pk(xk)

：表示第k阶段派出巡逻队xk时，该阶段的预期损失值解（逆序解法）11p205例4巡逻队问题（续）递推关系式：当k=3时，(s4=0)

x3

s3p3(

x3)f3(s3)x3*23422424232222342121412当k=2时

x2

s2p2(

x2)+f3(s3)f2(s2)x2*234538+2235+24593638+2135+2231+24554735+2131+22534当k=1时

x1

s1p1(

x1)+f2(s2)f1(s1)x1*234918+5314+5510+59693或4结果13回溯得，x1*=3，x2*=4，x3*=2或x1*=4，x2*=3，x3*=2总的预期损失为6914

【例】

某公司拥有三家连锁商店，拟将新招聘的5名员工分配给甲、乙、丙三个商店，各商店得到新员工后，每年盈利情况如表8-2所示。问分配给各商店各多少员工，才能使得公司的总盈利最大？(单位：千元)表8-2分配新员工后，甲、乙、丙三个商店每年盈利情况(单位：千元)

012345甲03791213乙0510111111丙046111212工人数盈利数商店类似练习如p215-8.115在实际中，如销售后分配问题、机器设备分配问题、货物分配问题、投资分配问题等等，均属于这类资源分配问题。这种只将资源合理分配，而不考虑回收的问题，又称之为资源平行分配问题。还有一种要考虑资源回收利用的问题，这里决策变量为连续值，故又可以称之为资源连续分配问题，这类分配问题的一般叙述如下:

设有数量为s1的某种资源，可投入A

和B

两种生产。第一年若以数量

x1

投入生产A

后，剩下的量s1-x1

就投入生产B，则可以得到收入g(x1)+h(s1-x1)，其中g(x)和h(x)

为已知函数，且g(0)=h(0)=0。这种资源在投入到A、B

生产后，年终年终还可以回收再投入生产。设年回收率分别为0<a<1

和0<b<1，则在第一年生产后，回收的资源量合计为

s2=

ax1+b(s1-x1)

资源连续分配问题16第二年再将资源数量s2中的x2和s2-x2分别投入到A、B

进行生产，则第二年又可以得到收入为g(x2)+h(s2-x2)，如此继续进行n年。试问：应该如何决定每年投入生产A的资源量x1,x2,…,xn，才能使得总的收入最大？此问题的静态规划模型为：转化为动态规划模型:，按年份将整个过程分为个阶段；(1)阶段变量：17表示第阶段用于生产的资源量，表示用于生产的资源量，(3)决策变量：允许决策集为：(2)状态变量sk：表示在第k阶段可投入生产的资源量；(4)状态转移方程：

(5)阶段指标：；(6)递推关系式：18p208例5（资源连续分配问题）已知递推关系式：当k=3时19当k=2时当k=1时20回溯当时，有

s2=90，所以从而

s3=60，故三年最大总收益为2200

万元。218.3.2

背包问题(Knapsack)

一般的提法：以旅行者携带背包去登山为例。已知他所能承受的背包重量的极限为W(千克)，现有n种物品可供他选择装入背包。第i

种物品的单位重量为

wi

(千克)，其价值（可以是表明本物品对登山者的重要性指标）是携带数量xi的函数g(

xi)（i=1,2,…,n）.问旅行者应如何选择携带物品的件数，以使总价值最大？其数学模型为：为整数22p213例8（背包问题）下用动态规划逆序解法建模求解：阶段k

:

将可装入货物按1，2，3的顺序排序，每段装入一种货物，共划分3个阶段，即k=1,2,3.状态变量sk

：在第k段开始时，还可装载的货物重量。决策变量xk

：装入第k种货物的件数。状态转移方程：

sk+1=sk-wkxk

阶段指标函数

：vkxk递推关系式：23当k=3时

x3

s330x3f3(s3)x3*012345000010303012030606023030609090340306090120120450306090120150150524当k=2时

x2

s280x2+

f3(s2-3x2)f2(s2)x2*0100+00010+3030020+6060030+9080+090040+12080+30120050+15080+60150025当k=1时

x1

s165x2+

f2(s1-2x1)f1(s1)x1*01250+15065+90130+301602回溯可得：装载货物的最大总价值为160。最优装载方案是

x1*=2，x2*=0，x3*=1268.3.3

用动态规划解非线性规划解:这是一个资源分配问题。设分配次序为x1,x2,

x3，阶段正向编号，逆向递推，由约束条件可得边界条件s1=27。第三阶段：（给x3分配）由边界条件和状态转移方程有：s4=s3x3≥0，即x3*=s3，因此有，第二阶段：（给x2分配）27由状态转移方程有：s3=s2x2，代入上式得，第一阶段：（给x1分配）由状态转移方程有：s2=s1x1=27x1

，代入上式得，解得解得，x1*=9，f1(s1)=9

回溯得，x1*=x2*=x3*=9

28

设有个城市，分别用来表示，城市之间的距离为。一个推销商从城市1出发到其他每个城市去一次且只去一次，最后回到城市1，问怎样选择行走路线，才能使得行走总路程最短？其动态规划模型如下：将从城市1到城市的中间城市集合用表示第阶段到达城市之表示，城，规定推销员是从城市1开始的，设推销员走到(2)状态变量：按经过城市的个数来分段，(1)阶段变量：个阶段，将整个过程分为问题一般描述如下：；8.3.4

旅行推销商问题(了解)29前中途所经过的城市的集，则有，其中，因此，可选取作为描述过程的状态变量；表示推销商在状态下前往的下一个城表示从城市到城市的距离；表示从城市1经过个城市到达城