运筹学第六章

第6章动态规划第1节多阶段决策过程及实例第2节动态规划的基本概念和方程第3节动态规划的最优性原理和最优性定理第4节动态规划和静态规划的关系第5节动态规划应用举例

第1节多阶段决策过程及实例

动态规划研究的对象是多阶段决策问题。所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。多阶段决策问题的典型例子：

1.生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。

2.机器负荷分配问题：某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为g=g(u1)12n状态决策状态决策状态状态决策

这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终完好的机器就为au,0<a<1。

在低负荷下生产时，产品的年产量h和投入生产的机器数量u2的关系为

h=h(u2)

假定开始生产时完好的机器数量为s1。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。

相应的机器年完好率b,0<b<1。

3.航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。

不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。

4

.线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决，后面将详细介绍。

5.最短路问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A点到G点的最短距离（总费用最小）。6AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876835338422123335526643123456生产存贮决策问题最短路问题机器负荷分配问题典型问题:第2节动态规划的基本概念和基本方程

2.1动态规划的基本概念但要便于把问题的过程能转化为多阶段决策的过程。状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合。1.

阶段、阶段变量把所给问题的过程，恰当地分为若干个相互联系的阶段;描述阶段的变量称为阶段变量，常用k表示；阶段的划分，一般是按时间和空间的自然特征来划分；2.状态、状态变量状态表示每个阶段开始所处的自然状态或客观条件。通常一个阶段有若干个状态。描述过程状态的变量称为状态变量，常用sk表示第k阶段的状态。一个数、一组数、一个向量在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合。常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合，显然有一个数一组数一个向量在最优控制中也称为控制。描述决策的变量，称为决策变量决策变量是状态变量的函数常用uk(sk)表示第k阶段当状态为sk时的决策变量。3.决策、决策变量过程的某一阶段、某个状态,可以做出不同的决定(选择),决定下一阶段的状态，这种决定称为决策。uk(sk)

Dk(sk)系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决策有关。其状态转移方程如下（一般形式）图示如下：状态转移方程是确定过程由一个状态到另一个状态的演变过程。如果第k阶段状态变量sk的值、该阶段的决策变量一经确定，第k+1阶段状态变量sk+1的值也就确定。4.多阶段决策过程可以在各个阶段进行决策，去控制过程发展的多段过程，其发展是通过一系列的状态转移来实现的。12ks1u1s2u2s3skukSk+1能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。*无后效性(马尔可夫性)如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；过程的过去历史只能通过当前的状态去影响它未来的发展；构造动态规划模型时，要充分注意是否满足无后效性的要求；如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。动态规划中能处理的状态转移方程的形式。状态具有无后效性的多阶段决策过程的状态转移方程如下状态变量要满足无后效性的要求；5.策略：按顺序排列的决策组成的集合；

由第k

n(终止状态)为止的过程，称为问题的后部子过程（k子过程）。

当k=1时，此决策函数序列成为全过程的一个策略，简称策略，记为p1,n

(s1)。即

可供选择的策略有一定范围，此范围称为允许策略集合，用p表示。从允许策略集合中找出达到最优效果的策略称为最优策略。

由每段的决策按顺序排列组成的决策函数序列称为k子过程策略，简称子策略，记为pk,n(sk)，即动态规划模型的指标函数，应具有可分离性，并满足递推关系。6.指标函数和最优值函数用来衡量所实现过程优劣的一种数量指标，称为指标函数；它是定义在全过程或所有后部子过程上确定的数量函数(费用、成本、利润、路长等)。用Vk,n

表示。即Vk,n可以表示为sk,uk,Vk+1,n的函数。(1)过程和它的任一子过程的指标是它所包含的各阶段的指标和。即其中vj(sj

,uj)

表示第

j阶段的阶段指标。这时上式可写成(2)过程和它的任意子过程的指标是它所包含的各阶段的指标的乘积。即则可改写成常见的指标函数的形式：表示从第k阶段的状态Sk开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。即最优值函数其中“opt”可根据题意取min或max

多阶段决策过程的数学模型：（具有无后效性）小结:方程:状态转移方程概念:阶段变量k﹑状态变量sk﹑决策变量uk;指标:

动态规划本质上是多阶段决策过程;

效益指标函数形式:

和积无后效性可递推解多阶段决策过程问题，求出

最优策略，即最优决策序列f1(s1)

最优轨线，即执行最优策略时的状态序列

最优目标函数值从k到终点最优策略子策略的最优目标函数值最短路的特性：如果已有从起点到终点的一条最短路，那么从最短路线上中间任何一点出发到终点的路线仍然是最短路。（证明用反证法）2.2动态规划的基本思想和基本方程AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368768353384221233355266431234566

k=5，出发点E1、E2、E3u5(E1)=F1E1F1GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u5(E2)=F2E2F2Gu5(E3)=F2E3F2Gk=6,F1Gf6(F1)=4F2G

,f6(F2)=3k=1,k=4，f4(D1)=7

u4(D1)=E2f4(D2)=6

u4(D2)=E2f4(D3)=8

u4(D3)=E2f3(C1)=13

u3(C1)=D1f3(C2)=10

u3(C2)=D1f3(C3)=9

u3(C3)=D2f3(C4)=12

u3(C4)=D3k=3,k=2,f2(B1)=13

u2(B1)=C2f2(B2)=16u2(B2)=C3d1(A,B1)+f2(B1)d1(A,B2)+f2(B2)=minf1(A)=min5+133+16=18u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u5(E1)=F1E1F1Gu5(E2)=F2E2F2Gu5(E3)=F2E3F2G759

u5(E2)=F2u6(F2)=G最优策略从上面的计算过程可以看出，在求解的各个阶段,我们利用了k阶段与k+1阶段之间的递推关系:fk(sk)=min｛dk(sk,uk(sk))+fk+1(uk(sk))｝ukDk(sk)f7(s7)=0k=6,5,4,3,2,1一般情况,k阶段与k+1阶段的递推关系式（动态规划的基本方程）边界条件为动态规划方法的基本思想：求解时从边界条件开始，逆（或顺）过程行进方向，逐段递推寻优。在每个问题求解时，都要使用它前面已求出的子问题的最优结果，依次进行，最后一个子问题的最优解，就是整个问题的最优解。

将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，正确写出基本的递推关系式和恰当的边界条件（简言之为基本方程）。从而把问题化成一族同类型的子问题；在求整个问题的最优策略时，由于初始状态是已知的，每段的决策是该段状态的函数，故沿最优化策略所经过的各段状态便可确定了最优路线。动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。每段决策的选取都是从全局考虑的,与该段的最优选择答案一般是不同的。375976713109111316

184AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221233355

26631234564逆序解法的基本方程(和的情况)边界条件为式中sk+1=Tk(sk,uk)，其求解过程，根据边界条件，从k=n开始，由后向前逆推，从而逐步可求得各段的最优决策和相应的最优值，最后求得f1(s1)

就是整个问题的最优解。其中fk(sk)表示第k阶段的初始状态为sk，从k阶段到n阶段所得到的最优效益值。逆序解法的基本方程(积的情况)边界条件为12s1u1s2u2s3nsnunSn+1kskukSk+1顺序解法的基本方程(和的形式)边界条件为式中sk=Tkr(sk+1,uk)，其求解过程，根据边界条件，从k=1开始，由前向后顺推，从而逐步可求得各段的最优决策和相应的最优值，最后求得fn(sn+1)时，就得到整个问题的最优解。其中fk(sk+1)表示第k阶段的结束状态为sk＋1时，从1阶段到k阶段所得到的最优效益值。顺序解法的基本方程(积的形式)边界条件为12s1u1s2u2s3nsnunSn+1kskukSk+1小结:ⅱ要具有可分离性，并满足递推关系。即ⅲ函数k（sk，uk，Vk+1,n）对于变量Vk+1，n要严格单调。将问题的过程划分成恰当的阶段；选择状态变量sk,既能描述过程的变化又满足无后效性；确定决策变量uk及每一阶段的允许决策集合Dk(sk)；正确写出状态转移方程；正确写出指标函数Vk,n，它应满足下面三个性质：ⅰ是定义在全过程和所有后部子过程上的数量函数;第3节动态规划的最优性原理和最优性定理

多阶段决策过程的特点：每个阶段都要进行决策，策略是由n个相继进行的决策构成的决策序列。前一阶段的终止状态又是下一阶段的初始状态，因此，确定阶段最优决策不能只从本阶段的效应来考虑，必须是整个过程通盘考虑，整体规划。即阶段k的最优决策不应该只是本阶段效应的最优，而必须是本阶段及其所有后续阶段的总体最优。理论基础

适应于用动态规划方法求解的是具有无后效性的多阶段决策过程。

动态规划方法的理论基础是基于R.Bellman提出的最优性原理：“一个过程的最优策略具有这样的性质：即无论其初始状态及初始决策如何，对于先前决策所形成的状态而言，余下的诸决策仍构成最优策略。”

最优性原理的含义是：最优策略的任何一部分子策略，也是它相应初始状态的最优策略。每个最优策略只能由最优子策略构成。反映动态规划基本方程的是最优化定理，它是策略最优的充分必要条件，而最优化原理仅仅是策略最优的必要条件，它是最优化定理的推论。最优性定理及证明略。第4节动态规划和静态规划的关系例1用逆推解法求解下面问题:分三个阶段，即k=1，2，3;解：设状态变量（因此可得状态转移方程）：考虑效益函数的形式分阶段状态变量与决策变量有密切关系，状态变量一般为累计量或随递推过程变化的量。确定决策变量：x1,x2,x3通常可取静态规划中的变量为决策变量

指标函数

最优指标函数：fk(sk)

基本方程当阶段k=3时，有当阶段k=2时，有得最优决策最优目标函数有两个解，其中x2=0舍去。因2阶导数在x*2处小于0，故有极大值。当阶段k=1时，有最优决策最优目标函数因此最后可得：s3=s2-x*2=s1-x*1-x*2问如何分配投资数额才能使总效益最大?解：可列出静态规划问题的模型如下分三个阶段，即k=1，2，3。状态变量sk为第k阶段初可分配给第k到第3个项目的资金数决策变量xk为决定投给第k个项目的资金

确定状态变量(因此可得状态转移方程)：例2某公司有资金10万元，若投资于项目(i=1,2,3)的投资额为xi时，其效益分别为状态转移方程

指标函数

最优指标函数：fk(sk)

基本方程最优目标函数f3(s3)=2s32

当阶段k=3时，有f3(s3)=max｛2x32｝0≤

x3≤s3最优决策为x3*=s3当阶段k=2时，有2阶导数大于0，存在极小点。最大值点只能在[0，s2]端点上取得，即当当当时，时，时，此时此时当阶段k=1时，有2阶导数>0，故比较[0,10]的端点因为∴最优投资方案是全部资金投于第3个项目，可得最大收益200万元。S2>9/2当当时时矛盾，舍去。（最优决策）S2<9/2

当阶段k=n时逆推解法小结：

设已知初始状态s1，最优值函数fk(sk)表示从k阶段到n阶段所得到的最大效益。以求最大化为例来说明。即其中s表示状态，x表示决策（控制）。可得最优决策xn=xn(sn)和最优值fn(sn)。若D(sn)只有一个决策,则可写成xn=xn(sn)。具体方法如下：

当阶段k=n-1时其中状态转移方程得到最优决策xn-1=xn-1(sn-1)和最优值fn-1(sn-1)。

当阶段k=k时其中状态转移方程得最优决策xk=xk(sk)和最优值fk(sk)。如此类推，直到第一阶段。当阶段k=1时其中状态转移方程得最优决策x1=x1(s1)和最优值f1(s1)。由于初始状态s1已知,故x1=x1(s1)和f1(s1)是确定的,根据状态转移方程按照上述递推过程相反顺序推算下去，就可逐步确定出每阶段的决策及效益。例3用顺推解法求解下面问题:设s4=c,fk(sk+1)表示第k阶段的结束状态为

sk+1，从1阶段到k阶段的最大值。分三个阶段，即k=1，2，3;解：设状态变量（因此可得状态转移方程）：确定决策变量：x1,x2,x3

指标函数

最优指标函数：fk(sk+1)

基本方程当阶段k=1时，有当阶段k=2时，有得最优决策最优目标函数当阶段k=3时，有最优决策最优目标函数因此最后可得：例4用动态规划方法解下面问题解：设状态变量为s0、s1、s2、s3按问题中变量的个数分为三个阶段，即k=1，2，3

确定决策变量：x1,x2,x3

fk(sk)表示第k阶段的结束状态为sk，从1阶段到k阶段的最大值。确定状态变量(因此可得状态转移方程)：状态转移方程最优目标函数f1(s1)=(4/9)s12

当阶段k=1时，有f1(s1)=max｛4x12｝X1＝s1/3最优决策为x1*=s1/3当阶段k=2时，有因该点不在允许决策集合内，最大值点只能在[0，s2/2]端点上取得，即所以h2(s2,x2)的最大值点在x2=0处，故得到f2(s2)=(4/9)s22及相应的最优解x2*=0。当阶段k=3时，有由于s3不知道，故须再对s3求一次极值，即

当阶段k=1时顺推解法小结：

设已知初始状态sn+1，最优值函数fk(s)表示第k阶段末的结束状态为s，从1阶段到k阶段所得到的最大效益。以求最大化为例来说明。即其中s表示状态，x表示决策（控制）。可得最优决策x1=x1(s2)和最优值f1(s2)。若D1(s1)只有一个决策,则可写成x1=x1(s2)。具体方法如下：

当阶段k=2时其中状态转移方程得到最优决策x2=x2(s3)和最优值f2(s3)。

当阶段k=k时其中状态转移方程得最优决策xk=xk(sk+1)和最优值fk(sk+1)。如此类推，直到第n阶段。

当阶段k=n时其中状态转移方程得最优决策xn=xn(sn+1)和最优值fn(sn+1)。由于终止状态sn+1已知,故xn=xn(sn+1)和fn(sn+1)是确定的,根据状态转移方程按照上述递推过程相反顺序推算下去，就可逐步确定出每阶段的决策及效益。动态规划的优缺点：优点:.

最优解是全局最优解。

.能得到一系列（包括子过程）的最优解。

.不需要对系统状态转移方程、阶段效应函数等的解析性质作任何假设。缺点：

.没有统一的标准模型和标准的算法可供使用。

.应用具有局限性，要求满足“无后效性”。

.存在“维数灾难”问题，变量的个数增加，计算的难度成倍增加。第5节动态规划应用举例

5.1节一维资源分配问题设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi(xi)问应如何分配，才能使生产n种产品的总收入最大？将数量一定的一种或若干种资源，恰当地分配给若干个使用者，使效益函数为最优。maxz=g1(x1)+g2(x2)+‥‥+gn(xn)x1+x2+…+xn=axi≥0i=1,2,…,ns.t.决策集合：Dk(sk)={uk|0uk=xksk}uk:分配给生产第k种产品的原料数量，即uk=xk；sk:分配给用于生产第k种至第n种产品的原料数量；状态转移方程：sk+1=sk-uk=sk-xk最优值函数fk(sk):数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收益，动态规划的递推关系为：某工业部门根据国家计划的安排，拟将某种高效率的设备5台分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为公司提供的盈利如表。

问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大。例1解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为1，2，3。=g3﹙0﹚=0=maxk=3时，0s35，0x3s3f3(s3)=max﹝g3﹙x3﹚﹞0≤x3≤s3f4(s4)=0g3(0)g3(1)

=4x3*(1)=1S3=0,f3(0)=max｛g3﹙x3﹚+f4(s4)｝

0≤x3≤s3x3*(0)=0x3=0,1S3=1,f3(1)=max｛g3﹙x3﹚+f4(s4)｝0≤x3≤s3当阶段k=2时，s3=s2-x2，

0s25，0x2s2，有结果列于下表：f3(1-0)=f3(1)=4

f3(5-3)=f3(2)=max=21g1(0)+f2(5)g1(1)+f2(4)g1(2)+f2(3)g1(3)+f2(2)g1(4)+f2(1)g1(5)+f2(0)

=max｛g1﹙x1﹚+f2(s1-x1)｝x1=0,1,2,3,4,5当阶段k=1时，s2=s1-x1，

s1=5，0x1s1，有S1=5,f1(S1)=max｛g1﹙x1﹚+f2(s2)｝0≤x1≤s1x1*(5)=0,20+213+167+149+1012+513+0=

max结果可写成表格的形式S2*=s1*-x1*=5-0=5S3*=s2*-x2*=5-2=3max逆推到第一张表S3*=s2*-x2*=5-2=3x3*=3x2*=2按计算表格的顺序逆推，可知最优分配方案有两个：甲工厂分配0台，乙工厂分配2台,丙工厂分配3台。甲工厂分配2台，乙工厂分配2台，丙工厂分配1台。以上两个分配方案所得到的总盈利均为21万元1.2资源连续分配问题:一般问题的提法是

A种生产数量u1投入收益g(u1)

年终资源回收率a如此进行n年，如何确定投入A的资源量u1、…、un，使总收入最大？

B种生产数量s1-u1收益h(s1-u1)

年终资源回收率b资源数量s1第一年资源数量s2=au1+b(s1-u1)第二年

A种生产数量u2投入;收益g(u2);年终回收率a

B种生产数量s2-u2;收益h(s2-u2);年终回收率b到n年此问题的静态规划问题模型为：动态规划的逆推关系方程为：最后求得得f1(s1)即为所求问题的最大收入。

高负荷:产量函数g=8u1,u1是投入生产的机器

数量，年完好率为a=0.7，低负荷:产量函数h=5y，y是投入生产的机器数量，年完好率为b=0.9。假定开始生产时完好机器的数量为1000台。

机器

例2机器负荷分配问题解：设阶段数k表示年度。试问每年如何安排机器在高低两种负荷下的生产，可使5年内生产的产品总产量最高。状态变量sk为第k年度初拥有的完好机器台数；

决策变量uk为第k年度中分配高负荷下生产的机器台数。低负荷下生产的机器台数是sk-uk。

状态转移方程第k年度产量为

递推方程为指标函数允许决策集合

0uksk当k=5时,f5(s5)=max﹛8u5+5﹙s5-u5﹚

+f6(s6)﹜0≤u5≤s5=max﹛3u5+5s5﹜0≤u5≤s5u5*=s5,f5(s5)=8s5当k=4时,

f4(s4)=max﹛8u4+5(s4–u4)

+f5(0.7u4+0.9(s4–u4))﹜0≤u4≤s4=max﹛13.6u4+12.2(s4-u4﹜0≤u4≤s4=max﹛1.4u4+12.2s4﹜0≤u4≤s4u4*=

s4,f4(s4)=13.6s4依次类推可得，u3*=s3f3(s3)=17.5s3

u2*=0

f2(s2)=20.8s2

u1*=0

f1(s1)=23.7s1最高产量为f1(s1)

=23700(台)。因此最优策略为:

u1*=0,u2*=0,u3*=s3,u4*=s4u5*=s5,u5*=s5,f5(s5)=8s5u4*=

s4,f4(s4)=13.6s45.2生产存贮问题一个生产部门，如何在已知生产成本、库存费用和各阶段市场需求条件下，决定各阶段产量，使计划内的费用总和为最小的问题。例8.某工厂要对一种产品制订今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产品的需求量如下表所示。假定该厂生产每批产品的固定成本3千元，若不生产就为0；每单位产品成本为1千元；每个时期生产能力所允许的最大生产批量为不超过6个单位；每个时期未售出的产品，每单位需付存贮费0.5千元。还假定在第一个时期的初始库存量为0，第四个时期末的库存量也为0。问该厂应如何安排各个时期的生产与库存，才能在满足市场需求条件下，使总成本最小。解：设dk为第k阶段的需求量，xk为第k阶段的生产量，vk为第k时期末库存量。有vk=vk-1+xk-dk把生产的四个时期作为四个阶段，k=1,2,3,4。由题意知，第k阶段的生产成本为第k时期末库存量为vk时的存储费用为hk(vk)=0.5vk第k时期内的总成本为ck(xk)+hk(vk)动态规划的顺序递推关系式为当k=1时，由f1(v1)=min{c1(x1)+h1(v1)}

对v1在0与之间的值分别进行计算即v1=0,1,2,3,4，于是由x1=min{v1+2,6}知，x1可取值为2,3,4,5,6。分别计算如下：

f1(0)=min{3+x1+0.5×0}=5 所以x1=2x1=min(v1+2,6)x1=2

f1(1)=min{3+x1+0.5×1}=6.5所以x1=3

f1(2)=min{3+x1+0.5×2}=8 所以x1=4

f1(3)=min{3+x1+0.5×3}=9.5 所以x1=5

f1(4)=min{3+x1+0.5×4}=11 所以x1=6k=2，f2(v2)=min{c2(x2)+h2(v2)+f1(v2+3-x2)}0≤x2≤min{v2+3,6}x1=3x1=4x1=5x1=6v2可在0与之间取值。即v2可取值0,1,2,3。x2可在0与min{v2+3,6}之间取值。分别计算如下：由有x2=0。由有x2=0。用同样的方法计算f2(2)=min{c2(x2)+h2(2)+f1(5－x2)}=14,有x2=5 0≤x2≤5 f2(3)=min{c2(x2)+h2(3)+f1(6－x2)}=15.5，有x2=6 0≤x2≤6k=3，f3(v3)=min{c3(x3)+h3(v3)+f2(v3+2－x3)}，v3可在0与min{4,6－2}=4之间取值。x3可在0与min{v3+2,6}之间取值。分别计算如下：有x3=0。用同样的方法计算

f3(2)=min{c3(x3)+h3(2)+f2(4－x3)}=17.5，有x3=4 0≤x3≤4

f3(3)=min{c3(x3)+h3(3)+f2(5－x3)}=19，有x3=5 0≤x3≤5

f3(4)=min{c3(x3)+h3(4)+f2(6－x3)}=20.5，有x3=6 0≤x3≤6有x3=0或3。k=4，因要求第4时期末的库存量为0，即v4=0，故有

f4(0)=min{c4(x4)+h4(0)+f3(4－x4)}

0≤x4≤4

x4=0。按计算顺序反推算，可找出每个时期的最优生产决策为: x1=5，x2=0，x3=6，x4=0其相应的最小总成本为20.5千元。例10某车间需要按月在月底都要供应一定数量的部件总装车间，由于生产条件的变化，该车间在各月中生产每单位这种部件所耗费的工时不同，各月份的生产量于当月的月底前，全部要存入仓库以备后用。已知总装车间的各个月份的需求量以及在加工车间生产该部件每单位数所需工时数如表6-7所示。设库存容量H=9，开始时库存量为2，期终库存量为