运筹学课件-动态规划

第七章动态规划第一节多阶段决策过程优化第二节基本概念和原理第三节模型与求解第四节在管理中应用1/145第七章动态规划是优化多阶段决策过程的一种方法。1957年，美国数学家贝尔曼(R.Bellman)发表了该领域第一本专著《动态规划》(DynamicProgramming)。用于解决最优路径、资源分配、生产与库存、投资、装载、排序等以及过程最优控制等问题。思路独特，对于某些问题，比线性或非线性规划方法有效。2/1453/145Born:26August1920inBrooklyn,NewYorkCityDied:19March1984inLosAngelesRichardErnestBellmancompletedhisdoctoralstudiesinPrincetonandremainedthereasAssistantProfessorofMathematicsaftertheawardofhisdoctoratebutin1948helefttotakeupthepositionofAssociateProfessorofMathematicsatStanfordUniversity.DuringthefollowingsummerheworkedatRAND.动态规划模型的分类：①离散确定型；②离散随机型；③连续确定型；④连续随机型。本章主要介绍离散确定型，思想、原理和方法，为解决其他类型问题打基础。4/145第一节多阶段决策过程最优化有些过程，可按先后分解成若干相互联系的“时段”，每一时段都要做出的决策，构成一个决策序列，这就是多阶段决策问题。

多阶段决策要达到整个过程总体效果最优。某阶段决策影响下阶段决策及总体效果。

每一阶段决策，不仅应谋取本阶段最优，还应考虑对最终目标的影响，从而做出对全局来讲是最优的决策。5/145

动态规划就是随着时间的推移逐段做出决策。

如果研究对象可分离为若干部分，分别考虑，就可视这若干部分为若干时段，用动态规划方法处理之。

现举例如次。6/145例1生产与存贮问题

某厂每月需供应市场一定量产品，余者存入仓库。一般说来，各月适当增加产量可降低生产成本，但存入仓库会增加库存费用。如何安排各月产量，才能既满足市场需求，又减少全年生产与存储费用总和呢？

可逐月考虑，但要顾及全年生产与存储费用总和。7/145例2投资决策问题

某公司有资金Q万元，今后5年要投入A、B、C和D四个项目。各项目投资回收期和收益率不同，问：如何安排各年投资额，才能使第5年末的资金总额最大。

该问题可按5阶段决策问题处理。8/145例3设备更新问题

设备越到后来，维修费越多。但买新设备一次性支出较多。企业要制订一台设备未来8年的更新计划。经预测，第j年的买价为Kj，设Gj为用过j年后的残值，Cj为连续用j-1年后第j年的维修费(j=1，2，…，8)，问：哪一年更新总费用最小？

可视为8阶段决策问题，每年年初要做出决定，是继续用，还是购买新的。9/145第二节动态规划基本概念和原理一、基本概念

用动态规划模型表达和解决实际问题，要用到以下概念：(1)阶段；(2)状态；(3)决策和策略。

下面以实例说明之。10/14511/145例4最短路线问题

要从A向F铺输油管道，问管线如何走，总长度才最短？线上的数字表示距离。(1)阶段

将过程或整体，按时间或空间分解成若干互相联系的时段或部分，以便逐一求解，用k表示阶段(k=1,2,…,5)。从A到F可分5阶段，每一阶段之初都有多个选择。

请注意，并不是所有的问题都能分解。12/14513/145(2)状态

用sk表示各阶段开始状态，称为状态变量。

sk取值全体称为状态集合，用Sk表示。

当某阶段sk给定后，以后过程的发展不受该阶段以前各阶段状态的影响。当前状态是过去历史的一个完整总结，过程的历史只能通过当前状态影响未来的发展，该性质称为无后效性。不具备后效性的变量不能充当状态变量。14/145在例4中，S1={A}，S2={B1，B2}

S3={C1,C2,C3,C4}

S4={D1,D2,D3}

S5={E1,E2}当某段初始状态已选定时，从这个点以后的铺管路线只与该点有关，不受以前的铺管路线影响，所以满足状态的无后效性。15/145

16/145整个决策序列构成策略，用p1,n{u1(s1),u2(s2),…,

un(sn)}表示。可选策略全体称为允许策略集合，记作P1,n，使整体效果最优的策略是最优策略。

(4)状态转移方程

本阶段状态是上阶段状态和决策的结果。若已知第k段状态sk和uk(sk)，则第k+1段状态sk+1也就确定，可表示为：

sk+1=Tk(sk,uk)(7-1)，称为状态转移方程。

例4中，状态转移方程为：sk+1=uk(sk)17/145(5)指标函数

衡量策略优劣的数值称为指标函数。阶段指标函数指第k段从状态sk出发，决策为uk时的效果，用d(sk,uk)表示。

从1到n叫做原过程，从第k(1≤k≤n)段到第n段的过程称为原过程后部子过程。

V1,n(s1,p1,n)表示初始状态为s1，用策略p1,n时，原过程指标函数值，Vk,n(sk,pk,n)表示k阶段状态为sk，用策略pk,n时，后部子过程指标函数值。18/145

19/145二、动态规划基本思想与原理

求最短路线，可求从A至F的所有可能铺设的长度，然后比较。当段数和各段状态都很多时，穷举法效率低。

动态规划方法，从过程最后一段开始，逆序递推，逐步求出各段、各点到终点F的最短路线，最后求得A到F的最短路线。

第1步，从k=5开始，s5可取E1和E2，到F点的距离分别为4，3。即：f5(E1)=4，

f5(E2)=320/145第2步，k=4，s4可取D1，D2和D3，从D1到F点有两条路线，取最短者：f4(D1)=min

d(D1,E1)+f5(E1)=3+4=7d(D1,E2)+f5(E2)5+3相应决策为u*4(D1)=E1。

f4(D2)=min

d(D2,E1)+f5(E1)=6+4=5d(D2,E2)+f5(E2)2+3u*4(D2)=E2。

f4(D3)=min

d(D3,E1)+f5(E1)=1+4=5

d(D3,E2)+f5(E2)3+3u*4(D3)=E1。

21/145类似地，k=3时，

f3(C1)=12，u*3(C1)=D1。f3(C2)=10，u*3(C2)=D2。f3(C3)=8，u*3(C3)=D2。f3(C4)=9，u*3(C4)=D3。k=2时，有f2(B1)=13，u*2(B1)=C2。f2(B2)=15，u*2(B2)=C3。k=1时，有f1(A)=min

d(A,B1)+f2(B1)=4+13=17

d(A,B2)+f2(B2)5+15u*1(A)=B1。

22/145

再按计算顺序反求最优决策序列，即u*1(A)=B1，u*2(B1)=C2，u*3(C2)=D2，u*4(D2)=E2，u*5(E2)=F。最短路线是A→B1→C2→D2→E2→F。

求解各阶段，都用了如下关系：fk(sk)=min

{dk(sk,uk)+fk+1(sk+1)}

(7.3a)ukk=5,4,3,2,1f6(s6)=0(7.3b)23/145

(7.3a)称为动态规划基本方程，(7.3b)称为终端条件。各结点上方括号内数，是该点到F最短距离。连结各点到F的线是最短路径。

在图上直接计算，叫标号。比穷举法易算，计算量少。段数越多，越复杂，越明显。不仅算得了从A到F的最短路线，还得到了中间任一点到F的最短路线。24/14525/145图7-226/1458838561310810131717若d(E1,F)由4改为8，标号过程如下。但f(E1)应当是7。请思考之。动态规划方法基本思想总结：

(1)为过程划分阶段，恰当选取状态和决策变量，定义最优指标函数，把问题化为若干同类型子问题，然后逐个求解。

(2)从终(始)端条件开始，逆(或顺)过程行进方向，逐段寻优。求解各子问题时，都要用前面子问题已得结果，最后一个子问题的最优解，就是整个问题的最优解。

27/145

28/145

动态规划方法的基础是贝尔曼等人提出的最优化原理：“过程最优策略的性质是：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，以后的所有决策应构成最优策略”。

从图7-2可看出，对于例4，无论从哪一段的哪一状态出发到终点F的最短路线，只与该状态有关，而与其以前状态、路线无关，即与从A点到达这一点的路线无关。

29/145第三节动态规划模型与求解一、动态规划模型的建立

建立基本方程，关键是划分阶段，将问题分解成具有递推关系的若干子问题，而查明递推关系的关键又在于选择状态变量，明确各阶段状态转移关系sk+1=Tk(sk,uk)。

资源分配问题是动态规划典型应用之一。下面以此类问题为例介绍动态规划建模条件及解法。30/145例5现有10万元资金，在第i个项目投入xi时，收益为g1(x1)=4x1；g2(x2)=9x2；

g3(x3)=2x23，问如何分配资金，总收益才最多?Maxz=4x1+9x2+2x23s.t.x1+x2+x3=10，x1,x2,x3≥0按动态规划求解。先在项目1投资，然后在项目2…，每次只考虑一个项目。下面选择状态变量，找出各后部子过程之间递推关系。31/145

可把原NLP问题中变量xk定为决策变量uk，即设

uk=xk(k=1，2，3)

状态和决策变量关系密切，状态变量一般为累计量或随着递推变化。

可把每阶段可用资金定为状态变量sk，初始状态s1=10。32/145u1为项目1可用资金，第1阶段(k=1)，有s1=10，

u1=x1，

第2阶段(k=2)，s2为余下可投入其余两个项目的资金，即s2=s1-u1，u2=x2，一般地，第k阶段，有sk=sk-1-uk-1，uk=xk，于是，阶段k，

k=1，2，3状态变量sk：第k阶段可投入第k到第3个项目的资金。决策变量xk：投入第k个项目的资金。33/145

34/145

一般地，建立动态规划模型的要点为：

1.分析题意，识别问题各阶段，按时空顺序适当划分满足递推关系的若干阶段或部分。

2.正确的状态变量应有两个特征：

(1)能直接或间接确定各阶段取值；

(2)能反映过程演变且无无后效性。即由第k阶段状态sk出发的后部子过程，可视为以sk为初始状态的独立过程。35/145

这一点并非每个问题都容易满足。3.写出状态转移方程

sk+1=Tk(sk,uk)或转移规则。4.明确指标函数Vk,n，最优指标函数fk(sk)以及阶段指标vk(sk,uk)的含义，列出最优指标函数的递推关系及终端条件(即基本方程)。

此外，需经验与熟练地运用最优化原理。36/14537/145k012453二、逆序与顺序解法

逆序（顺序）解法寻优方向与过程行进方向相反（相同）。

例4的顺序解法计算步骤如下：k=0，

f0(s0)=f0(A)=0，这是初始条件。k=1，f1(s1)f1(B1)=4，u1(B1)=Af1(B2)=5，u1(B2)=A38/145k=2，f2(s2)f2(C1)=d(B1,C1)+f1(B1)=2+4=6u2(C1)=B1f2(C2)=mind(B1,C2)+f1(B1)=min2+4=6d(B2,C2)+f1(B2)8+5u2(C2)=B1，f2(C3)=mind(B1,C3)+f1(B1)=min6+4=10d(B2,C3)+f1(B2)7+5

u2(C3)=B1，39/145f2(C4)=d(B2,C4)+f1(B2)=7+5=12u2(C4)=B2k=3，f3(s3)

f3(D1)=11，u3(D1)=C1或C2f3(D2)=12，u3(D2)=C2f3(D3)=14，u3(D3)=C3k=4，f4(s4)

f4(E1)=14，u4(E1)=D1f4(E2)=14，u4(E2)=D2k=5，f5(s5)

f5(F)=17，u5(F)=E240/14541/145414141112146710124517042/14514141112146710124517按定义知f5(F)=17为所求最短路长，而路径则为A→B1→C2→D2→E2→F，与逆序解法相同。计算过程如图7-3。图中节点上方括号内的数是该点到A点的最短距离，黑粗线是该点到A点的路径。上述解法写成如下递推方程：fk(sk)=min{vk(sk,uk)+fk-1(sk-1)}，

(7.5a)

k=1,2,3,4,5f0(s0)=0

(7.5b)这里，sk=Tk(sk+1,uk)43/145

一般地说，当给定初始状态时可用逆序解法，当给定终止状态时可用顺序解法。

若给定了一个初始状态与一个终止状态，两种方法均可用，如例4。

但若虽已给定初始状态，终点状态有多个，需比较到达不同终点的各路径及最优指标函数值，以选取总效益最佳的终点状态时，用顺序解法较简便。

总之，应针对问题的特点，灵活选用。44/145

上述两种方法，建模时要注意以下区别：

1.状态转移方式不同

如图7-4所示，逆序解法第k段的输入状态sk和决策uk确定了sk+1，状态转移方程为：sk+1=Tk(sk,uk)(7.6)式(7.6)称为状态sk到sk+1的顺序转移方程。45/14546/145

顺序解法第k段sk由sk+1和uk决定，见图7-5，状态转移方程为：

sk=Tk(sk+1,uk)(7.7)式(7.7)称逆序状态转移方程。

逆序解法中阶段指标vk(sk,uk)在顺序解法中应表为vk(sk+1,uk)。

2.指标函数的定义不同

逆序解法，最优指标函数fk(sk)表示第k段从状态sk出发到终点后部子过程最优效益值，

f1(s1)是整体最优函数值。47/145

48/145

49/145

50/145

51/145三、基本方程分段求解时几种常用算法

动态规划基本方程分段求解，须根据具体问题特点，灵活求解。大体有以下方法。

1.离散变量的分段穷举算法

状态与决策变量若只取离散值，则可用分段穷举法。例4就是。求最优指标函数值时，应正确确定各段状态变量取值和允许决策集合范围。52/1452．连续变量的解法

状态与决策变量若连续，可用解析法、线性和非线性规划法或其他数值计算方法等。

例5，状态与决策变量均连续，每阶段求优时不能用穷举法。(1)逆序解法

例5状态变量sk为第k段初可分配给第k到第3个项目的资金；决策变量xk为投入第k个项目的资金；状态转移方程为sk+1=sk-xk，53/145

最优指标函数fk(sk)表示第k阶段，状态为sk时，从第k到第3个项目的最大收益，

f1(s1)即为所求总收益。递推方程为：

fk(sk)=

max{gk(xk)+fk+1(sk+1)}

k=3,2,1

0≤xk

≤skf4(s4)=0k=3f3(s3)=max

{2x23}=

2s230≤x3

≤s3k=2f2(s2)=

max{9x2+f3(s3)}

0≤x2

≤s2

=

max{9x2+2(s2-x2)2}0≤x2≤s254/145令h2=9x2+2(s2-x2)2，由dh2/dx2=9-4(s2-x2)=0，得x2=s2-9/4，而d2h2/dx22=4>0，所以x2=s2-9/4是极小点。极大值只能在x2=0或x2=s2处取得。f2(s2)|x2=s2

=

9s2f2(s2)|x2=0=

2s22当f2(s2)|x2=s2

=f2(s2)|x2=0时，s2=9/2当s2>9/2时，f2(s2)|x2=s2

<

f2(s2)|x2=0，x*2=0当s2<9/2时，f2(s2)|x2=s2

>

f2(s2)|x2=0，x*2=s255/145k=1f1(s1)=

max{4x1+f2(s2)}

0≤x1≤s1当f2(s2)=9s2时，

f1(10)=

max

{4x1+9s1-9x1}

0≤x1≤10=max{9s1-5x1}=9s1，

x*1=0

0≤x1≤10但此时，s2=s1-x1=10-0=10>9/2，与s2<9/2矛盾，舍去。56/145当f2(s2)=2s22时，

f1(10)=max{4x1+2(s1-x1)2}0≤x1≤10令h1=4x1+2(s1-x1)2由dh1/dx1=4-4(s1-x1)=0，得x1=s1-1，d2h1/dx21=1>0，故x1=s1-1是极小点。极大值只能在x1=0或x1=s1=10处取得。f1(s1)|x1=0=2s21=200，

f1(s1)|x1=10=

40所以，

x*1=0，s2=s1-x*1=s1=10，因s2>9/2，所以x*2=0；s3=s2-x*2=s2=10，所以，

x*3=s3=10全部资金投于第3个项目，收益为200万元。57/145(2)顺序解法

令状态变量sk为可投入第1到第k个项目的金额，则状态转移方程为：

s3=10，s2=s3-x3，s1=s2-x2，s0=s1-x1即sk=sk+1-xk+1，

令最优指标函数fk(sk)表示投入第1到第k个项目的总额为sk时的总收益最大值。基本方程为：fk(sk)=

max{gk(xk)+fk-1(sk-1)}k=1,2,3

0≤xk≤skf0(s0)=0表示未投资时的最大收益。58/145k=1f1(s1)=

max

{g1(x1)+f0(s0)}0≤x1≤s1=

max{4x1}=

4s1，

x*1=s1

0≤x1≤s1k=2f2(s2)=

max{9x2+f1(s1)}

0≤x2≤s2

=

max{9x2+4(s2-x2)}0≤x2≤s2

=max{5x2+4s2}=9s2，

x*2=s2

0≤x2≤s259/145k=3f3(s3)=

max

{2x23+f2(s2)}0≤x3≤s3=

max{2x23+9(s3-x3)}

0≤x3≤s3令h(s3,x3)=2x23+9(s3-x3)dh(s3,x3)/dx3=4x3-9=0，x3=9/4d2h(s3,x3)/dx23=4>0，x3=9/4为极小点，极大值应当在x3=0或x3=10处取得。f3(s3)|x3=0=

9s3，f3(s3)|x3=10=200，

x*3=10，s2=s3-x*3=10-10=0，

s2=s3-x*3=s3-s3=0，

s1=s2-x*1=s2-s2=0，60/145最优投资方案与逆序解法结果相同，只投资于项目3，最大收益为200万元

对本例而言，顺序解法比逆序解法简单。61/145

62/145状态转移方程为：

sk+1=sk-xksk与xk是连续变量。当各gk(xk)较复杂时，较难求出fk(sk)。常把连续变量离散化，求数值解。具体做法如下：(1)令sk=0，Δ，2Δ，…，mΔ=a，

Δ大小可依据要求的精度定。(2)规定状态变量sk及决策变量xk只取离散值，递推方程就变为：fk(sk)=

max{gk(pΔ)+fk+1(sk-pΔ)}

p=0,1,…,qfn+1(sn+1)=0其中，qΔ=sk,xk=pΔ。63/145(3)按逆序解法，逐步递推求fn(sn)，fn-1(sn-1)…，

f1(s1)，最后求出最优资金分配方案。现举例说明连续的状态和决策变量如何分段取值。Maxz=4x1+9x2+2x23s.t.x1+x2+x3=10，x1,x2,x3≥0解令Δ=2，则状态空间Sk={0,2,4,6,8,10}，决策集合为0≤xk≤sk，64/145递推方程为：fk(sk)=

max{gk(xk)+fk+1(sk-xk)}

0≤xk≤sk

f4(s4)=0k=3，f3(s3)=

max{2x23}，计算结果见表7-1。

0≤x3≤s3表7-165/145s30246810f3(s3)083272128200x*30246810k=2，f2(s2)=

max{9x2+f3(s2-x2)}

0≤x2≤s2表7-266/145s20246x20020240246g2+f3081832263672504454f2(s2)0183672x*20240s30246810f3(s3)083272128200x*30246810s2810x2024680246810g2+f312890686272146108868090f2(s2)128200x*200s30246810f3(s3)083272128200x*30246810s2810x2024680246810g2+f312890686272146108868090f2(s2)128200x*200k=1，f1(s1)=

max{4x1+f2(s1-x1)}

0≤x1≤10表7-367/145s20246x20020240246g2+f3081832263672504454f2(s2)0183672x*20240s110x10246810g1+f220013688605040f1(s1)200x*10最优决策为：x*1=0，

x*2=0，

x*3=10，最大收益为f1(s1)=200，与例5结论相同。

该法会丢失最优解，一般只是近似解。68/145

69/145设状态变量为：sk=(Xk,Yk)，Xk：用于生产第k至n种产品的第1种资源量；Yk：用于生产第k至n种产品的第2种资源量；设决策变量为：uk=(xk,yk)，xk：用于生产第k种产品的第1种资源量；yk：用于生产第k种产品的第2种资源量；状态转移方程为：Xk+1=Xk-xkYk+1=

Yk-

yk70/145允许决策集合为：Dk(Xk,Yk)={(xk,yk)|0≤xk≤Xk，0≤yk≤Yk}最优指标函数fk(Xk,Yk)表示分配于第k种产品至第n种产品的两种资源分别为Xk和Yk时的最大收益。基本递推方程为：fk(Xk,Yk)=

max{gk(xk,yk)+fk+1(Xk+1-xk,Yk-yk)}

0≤xk≤Xk

0≤yk≤Ykk=n,n-1,…,2,1fn+1(Xn+1,

Yn+1)=071/145

72/145

73/145第四节动态规划在管理中的应用

本节介绍一些例子。一、背包问题

登山背包有n种物品要装，但最多装a公斤，第i种单件重ai公斤，价值ci(xi)(表明本物品对登山重要性)是件数xi的函数

(i=1,2,…,n)，问如何选装各种物品件数，使总价值最大?74/145

75/145允许决策集合为：Dk(sk)={xk|0≤xk≤[sk/ak],xk为整数}最优指标函数fk(sk)表示背包允许装入物品总重量不超过sk公斤，按最优策略装前k种物品时的最大价值。顺序递推方程为：fk(sk)=max{ck(xk)+fk-1(sk-ak-1xk-1)}

xk=0,1,…,[sk/ak]k=1,2,…,nf0(s0)=0，表示未装入物品时最大价值。76/145用顺序解法逐步算出f1(s1)，

f2(s2)，…，

fn(sn)及相应的决策x1(s1)，x2(s2)，

…，

xn(sn)，最后得到的fn(a)即为所求最大价值。最优策略反向推出。

当xi仅表示装入(取1)和不装(取0)第i种物品，则本模型就是0-1背包问题。77/145例7货运量10t的卡车，可装3种货物，每种单位重量及价值如下表。如何装载总价值最大?

设第i种货物装载的件数为xi(i=1,2,3)，则问题可表为：

Max

z=4x1+5x2+6x3

s.t.3x1+4x2+5x3≤10

xi

为非负整数

(i=1,2,3)78/145货物编号123单件重t345单位价值456是离散决策变量，可列表求解当k=1时，f1(s1)=

max{4x1+f0(s0)}或

0≤3x1≤s1取整数

f1(s1)=max

{4x1+f0(s0)}=4[s1/3]

0≤x1≤[s1/3]取整数79/145s1012345678910f1(s1)0004448881212x*100011122233当k=2时，f2(s2)=

max{5x2+

f1(s2-4x2)}

0≤x2≤s2/4整数80/145s2012345x200000101c2+f1000455f2(s2)000455x*2000011s1012345678910f1(s1)0004448881212x*100011122233s2678910x20101012012012c2+f1859891012910121310f2(s2)89101213x*201201s2012345x200000101c2+f1000455f2(s2)000455x*2000011s2678910x20101012012012c2+f1859891012910121310f2(s2)89101213x*201201k=3，f3(s3)=

max{6x3+f2(s3-5x3)}

x3=0,1,2=

max{f2(10),6+f2(5),12+f2(0)

}=

max{13,11,12}=13，

x*3=0逆推，可得全部策略为：x*3=0，x*2=1，

x*1=2。当约束条件两个以上时，就是多维背包问题，解法与本例相似，但状态变量是多维的。81/145二、生产经营问题例8生产与存储问题某厂生产并销售某种产品，今后四个月需求量预测如表7-7。每月生产j单位产品的费用为：C(j)=0j=0

=3+j

(千元)j=1,2,3,4,5,682/145i(月)1234gi2324月库存费为E(j)=0.5j(千元)，最大库容为3单位，最大月产量6单位，期初和期末库存量都是零。试订四个月计划，既满足需求，总费用又最小。设第i+1月库存是第i月可售量与需求量之差；而第i月可售量是月初库存量与产量之和。(1)阶段：每月为一阶段，k=1,2,3,4。(2)状态变量：sk为第k月初库存量。(3)决策变量：

uk为第k月产量。(4)状态转移方程：

sk+1=sk+uk-gk83/145(5)最优指标函数：fk(sk)表示第k月初库存为sk时，按最佳策略生产，从该月到第4月末最低生产与存贮费用。考虑k=4，因4月末库存应为零，该月需求4，故该月产量应为u4=4-s4，因最大库容为3，所以s4只能取0,1,2,3。f4(s4)=min{C(u4)+E(s4)}，f4(s4)与u4(s4)如表7-8。表7-884/145s40123f4(s4)76.565.5u4(s4)4321k=3，

s3与库容量、生产能力和需求量有关，在此，由库容量决定：

s3={0,1,2,3}。为满足需求，u3至少为g3-s3=2-s3，若库存s3大于2，则u3应取0。为保证期末库存为0，u3不能超过g3+g4-s3=6-s3，另外，u3不能超过库容量3，即不能超过g3+3-s3=5-s3，也不能超过生产能力6，总之，有max{0,2-s3}≤u3≤min{6,5-s3,6-s3}的整数f3(s3)=min{C(u3)+E(s3)+f4(s3+u3-g3)}85/145对s3=0,1,2,3求出f3(s3)，当s3=0时，f3(0)=min{(3+u3)+0.5×0+f4(u3-2)}，2≤u3≤5

u3=2:5+7=min

u3=3:6+6.5=12，u*3(0)=2,

u3=4:7+6u3=5:8+5.5这就是说，若第3月初库存为零，则3、4二月最低费用为12（千元），第3月最优产量为2单位。见表7-9。86/145s40123f4(s4)76.565.5u4(s4)4321当s3=1时，f3(1)=min{(3+u3)+0.5×1+f4(u3-1)}，1≤u3≤4

u3=1:4+0.5+7=min

u3=2:5+0.5+6.5=11.5，u*3(1)=1,

u3=3:6+0.5+6u3=4:7+0.5+5.5这就是说，若第3月初库存为1，则3、4二月最低费用为11.5（千元），第3月最优产量为1单位。87/145s40123f4(s4)76.565.5u4(s4)4321当s3=2时，f3(2)=min{C(u3)+0.5×2+f4(u3)}，0≤u3≤3

u3=0:0+1+7=min

u3=1:4+1+6.5=8，u*3(2)=0,

u3=2:5+1+6u3=3:6+1+5.5这就是说，若第3月初库存为2，则3、4二月最低费用为8（千元），第3月最优产量为0单位。88/145s40123f4(s4)76.565.5u4(s4)4321当s3=3时，f3(2)=min{C(u3)+0.5×3+f4(u3+1)}，0≤u3≤2

u3=0:0+1.5+6.5=min

u3=1:4+1.5+6=8，u*3(3)=0,

u3=2:5+1.5+5.5

这就是说，若第3月初库存为3，则3、4二月最低费用为8（千元），第3月最优产量为0单位。89/145s40123f4(s4)76.565.5u4(s4)432190/145s301u3(s3)23451234C+E+f41212.51313.511.51212.513f3(s3)1211.5u*3(s3)21s323u3(s3)0123012C+E+f4811.51212.5811.512f3(s3)88u*3(s3)00表7-9s4=s3+u3-g3=s3+u3-2k=2f2(s2)=min{C(u2)+E(s2)+f3(s2+u2-g2)}s2=0,1,2,3决策变量u2为：max{0,g2-s2}≤u2≤min{6,g2+3-s2,g2+g3+g4-s2}的整数，即max{0,3-s2}≤u2≤min{6,6-s2,9-s2}的整数本段计算结果见表7-10。91/14592/145s201u2(s2)34562345C+E+f31818.5161717.51815.516.5f2(s2)1615.5u*2(s2)54s323u3(s3)12340123C+E+f41717.5151613.51714.515.5f3(s3)1513.5u*3(s3)30表7-10s3=s2+u2-g2=s2+u2-3k=1f1(s1)=min{C(u1)+E(s1)+f2(s1+u1-g1)}s1=0决策变量u1受本月需求量、库存容量和生产能力限制，应为2≤u1≤5的整数，f1(0)=min{C(u1)+f2(u1-2)}2≤u1≤5的整数本段计算结果见表7-11。93/145表7-11f1(s1)从表7-11可知，最低总费用为f1(0)=21(千元)，第1月最佳产量为2单位，而需求为2单位，所以，第2月初库存为0，再由表7-10查s2=0列，可得，第2月最佳产量为5单位，同理查得，第3月最佳产量为0单位，第4月最佳产量为4单位。94/145s10u1(s1)2345C+f22121.52221.5f1(s1)21u*1(s1)2s2=s1+u1-g1=s1+u1-2

95/145例9采购与销售问题

某商店未来4个月，准备用一个仓库专销某种商品，最多贮存1000单位。假定每月只能卖存货。定货下月初才能到。未来四个月买卖价格预测如表7-12。1月初库存500单位。若不计库存费，该店应如何制订1至4月购销计划，使预期获利最大。

表7-1296/145月份购价(ck)售价(pk)110122983111341517解

按月划分4阶段，k=1,2,3,4状态变量sk：第k月初库存量。决策变量xk：第k月卖出量。

yk：第k月订购量。状态转移方程：

sk+1=sk+yk-xk

最优指标函数fk(sk)：第k月初库存量为sk时，从第k月到4月末所获最大利润。逆序递推方程：

fk(sk)=max{pkxk-ckyk+fk+1(sk+1)}k=

4,3,2,10≤xk≤sk

0≤yk≤1000-(sk-xk)f5(s5)=097/145k=4f4(s4)=max{17x4-15y4}0≤x4≤s4

0≤y4≤1000-(s4-x4)显然，应有x*4=s4，y*4=0，f4(s4)=17s4,k=3f3(s3)=max{13x3-11y3+17(s3+y3-x3)}0≤x3≤s30≤y3≤1000-(s3-x3)

=max{-4x3+6y3+17s3}0≤x3≤s30≤y3≤1000-(s3-x3)98/145该阶段需解一个线性规划问题Maxz=-4x3+6y3+17s3s.t

x3≤s3

y3-x3≤1000-

s3x3,y3≥0x*3=s3,y*3=1000时有最大值f3(s3)=6000+13s3k=2时，f2(s2)=max{8x2-9y2+6000+13(s2+y2-x2)}0≤x2≤s20≤y2≤1=max{6000+13s2-5x2+4y2}

0≤x2≤s20≤y2≤1000-(s2-x2)99/145解线性规划问题Maxz=6000+13s2-5x2+4y2s.t

x2≤s2

y2-x2≤1000-s2x2,y2≥0x*2=0,y*2=1000-s2f2(s2)=6000+13s2+4000-4s2=10000+9s2100/145k=1时，f1(500)=max{12x1-10y1+10000+9(s1+y1-x1)}0≤x1≤5000≤y1≤500+s1=max{3x1-y1+14500}

0≤x1≤5000≤y1≤500+s1解线性规划问题Maxz=3x1-y1+14500s.t

x1≤500

y1-x1≤1000-s1=500x1,y1≥0x*1=500,y*1=0，f1(500)=14500+3×500=16000101/145最优策略见表7-13。最大利润为16000。表7-13102/145月份当期存货(sk)售出量(xk)购入量(yk)15005000200100031000100010004100010000三、设备更新问题

设备用多少年更新最合算？

新设备，负荷大，产量多，维修少。但到后来，产出减少，维修费增加。更新可增加产量，但费用多。

此类问题一般提法：已知效益r(t)，维修费u(t)及更新费c(t)，n年内各年初都要考虑，是仍用旧设备还是换新的，使n年总效益最大。103/145设rk(t)：第k年已用过t年(役龄)，再用1年的效益。uk(t)：第k年役龄为t年，再用一年的维修费。ck(t)：第k年卖掉役龄t年设备，购入新设备的净更新费用。α为折扣因子(0≤α≤1)，表示一年后单位收入价值相当于现年的α单位。104/145动态规划模型阶段k(k=1,2,…,n)表示该设备计划年限。状态变量sk：第k年初，设备役龄。决策变量xk：第k年初更新，还是继续用。分别用R与K表示。状态转移方程：sk+1=sk

+1当xk=K

1当xk=R阶段指标vk(sk,xk)=rk(sk)-uk(sk)当xk=K

rk(0)-uk(0)-

ck(sk)

当xk=R105/145

106/145例10某台新设备年效益、年均维修费、净更新费用如表7-14。试制订5年内更新策略，使总收益最多。（设α=1）表7-14107/145012345效益rk(t)54.543.7533.5维修费uk(t)0.511.522.53更新费ck(t)0.51.52.22.533.5解k=5f5(s5)=maxr5(s5)-u5(s5)当xk=K

r5(0)-u5(0)-c5(s5)当xk=Rs5当可取1,2,3,4f5(1)=maxr5(1)-