第6章动态规划

会计学1第6章动态规划

动态规划所谓多阶段决策问题是指这样的决策问题:其过程可分为若干个相互联的阶段，每一阶段都对应着一组可供选择的决策，每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。当每一阶段的决策选定以后，就构成一个决策序列，称为一个策略，它对应着一个确定的效果。多阶段决策问题就是寻找使此效果最好的策略。状态

x1阶段1T1决策u1状态

x2决策u2阶段2T2状态

x3...状态

xk决策uk阶段kTk状态

xk+1...状态

xn决策un阶段nTn状态

xn+1第1页/共55页多阶段决策问题工厂生产过程:由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。设备更新问题:一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费．因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。第2页/共55页多阶段决策问题连续生产过程的控制问题:一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。资源分配问题:资源分配问题属于静态问题。如某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题。第3页/共55页动态规划求解的特点通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。无后效性(又称马尔柯夫性)是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。第4页/共55页A

动态规划问题实例C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643例6-1给定一个线路网络，要从A向F铺设一条输油管，各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短？第5页/共55页A

动态规划C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643第6页/共55页1.阶段与阶段变量为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称为多段决策问题的阶段。描述阶段的变量称为阶段变量，常用k表示。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。

动态规划的基本概念第7页/共55页

动态规划的基本概念2.状态、状态变量与可能状态集描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态。反映状态变化的量叫做状态变量。状态变量包含在给定的阶段上确定全部允许决策所需要的信息。每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记作sk，终止状态记为sk+1。通常定义阶段的状态即指其初始状态。一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示，sk∈Sk，。第8页/共55页A

动态规划问题实例C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6第6阶段状态7第9页/共55页

动态规划的基本概念3.决策当一阶段的状态确定后，可以作出不同的选择从而演变到下一阶段的某个状态，这种选择手段称为决策。在最优控制问题中也称为控制。描述决策的变量，称为决策变量。决策变量的允许取值的范围称为允许决策集合。决策变量是状态变量的函数。用uk(sk)表示第K阶段处于状态sk时的决策变量；Dk(sk)表示sk的允许决策集合。第10页/共55页A

动态规划问题实例C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6第6阶段状态7u2(B2)=C2D2(B2)={C2,C3,C4}第11页/共55页

动态规划的基本概念4.策略一个按顺序排列的决策组成的集合。由过程的第K阶段开始到终止阶段为止的过程称为问题的后部子过程。由每段的决策按顺序排列组成的决策函数序列{uk(sk),…,un(sn)}称为K子过程策略，简称子策略，记为pk,n(sk)。当K=1时，此决策函数序列称为全过程的一个策略，简称策略，记为p1,n(s1)，即:

p1,n(s1)={u1(s1),u2(s2),…,un(sn)}第12页/共55页A

动态规划问题实例C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643状态1状态2状态3状态4状态5状态6状态7p3,6(C2)={u3(C2),u4(D2),u5(E3),u6(F1)}p1,6(A)={u1(A),u2(B1),u3(C2),u4(D2),u5(E3),u6(F1)}第13页/共55页

动态规划的基本概念5.状态转移方程确定过程由一个状态到另一个状态的演变过程。若给定第K阶段的状态变量sk的值，如果该阶段的决策变量uk一经确定，第K+1阶段的状态变量sk+1的值也就完全确定。即sk+1的值随sk和uk的值变化而变化。这种确定的对应关系记为:sk+1=Tk(sk,uk(sk))工厂1工厂2工厂3工厂4投资x1投资x2投资x3投资x4状态s2状态变量sk

:可用于第k,k+1,…n个工厂的投资额。决策变量xk

:第k

阶段对第k

个工厂的投资额。状态转移方程:sk+1

=sk

-xks1=600状态s3状态s4状态s5s2=s1-x1s3=s2-x2s4=s3-x3第14页/共55页

动态规划的基本概念6.指标函数和最优值函数用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用等等。

1)阶段指标函数(阶段效应)用gk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标，则它就是第k段指标函数，简记为gk。第15页/共55页

动态规划的基本概念

(2)过程指标函数(目标函数)用Vk(sk,uk)表示第k子过程的指标函数指标函数，不仅跟当前状态sk有关，还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数，严格说来，应表示为:Vk(sk,

pk(sk))，实际应用中上式可表示为:Vk(sk,

uk)或Vk(sk)。过程指标函数Vk(sk,uk)通常是描述所实现的全过程或k

后部子过程效果优劣的数量指标，它是由各阶段的阶段指标函数gk(sk,uk)累积形成的。第16页/共55页

动态规划的基本概念

适于用动态规划求解的问题的过程指标函数(即目标函数)，必须具有关于阶段指标的可分离形式．对于k部子过程的指标函数可以表示为:

Vk,n=Vk,n(sk,uk,sk+1,uk+1,…

,sn,un)=gk(sk,uk)⊙gk+1(sk+1,uk+1)⊙…⊙gn(sn,un)多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即:

å==nkiiuisigkV),(有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如:

Õ==nkiiiikusgV),(第17页/共55页

动态规划的基本概念指标函数的最优值称为最优值函数，记为fk(sk)。它表示从第K阶段的状态开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。),,,()(1,},,{+=nkknkuukksusVoptsfnkLL

相应的子策略称为sk状态下的最优子策略，记为pk*(sk)；而构成该子策赂的各段决策称为该过程上的最优决策，记为:uk*(sk),uk+1*(sk+1),…,un*(sn)。

特别当k=1且s1取值唯一时，f1(s1)就是问题的最优值，而p1*就是最优策略。但若取值不唯一,则问题的最优值记为f0有:)()}({11111011*Î*===ssfsfoptfSs第18页/共55页

动态规划的基本概念7.多阶段决策问题的数学模型综上所述，适于应用动态规划方法求解的一类多阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式:ïïîïïíì=ÎÎ===+nkUuSsusTsstusususVVoptfkkkkkkkknnuun,,2,1),(),,,,,,(12211~1LL第19页/共55页A

最短路径问题C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643例6-2:用动态规划求解最短路径。第20页/共55页将问题分成五个阶段，第k阶段到达的具体地点用状态变量sk表示，例如:s2=B2表示第二阶段到达位置B2。这里状态变量取字符值而不是数值。将决策定义为到达下一站所选择的路径，例如目前的状态是s2=B2，这时决策允许集合包含三个决策，它们是D2(s2)=D2(B2)={B2→C2，B2

→C3，B2→C4}。最优指标函数fk(xk)表示从目前状态到E的最短路径。终端条件为:f7(s7)=f7(G)=0其含义是从G到G的最短路径为0。递推方程为: )}(),({)(11)(++Î+=kkkkksDukksfusVMinsfkkk

最短路径问题第21页/共55页贝尔曼最优化原理作为一个全过程的最优策略具有这样的性质:对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为:p1*(s1)={u1*(s1),u2*(s2),…,un*(sn)}则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略p1*中，即为:pk*(sk)={uk*(sk),uk+1*(sk+1),…,un*(sn)}第22页/共55页贝尔曼最优化原理基于贝尔曼最优化原理，提出了一种逆序递推法；该法的关键在于给出一种递推关系。一般把这种递推关系称为动态规划的函数基本方程。对于求最小的加法的计算公式为:ïïîïïíì-=+==++Î++1,2,,1,)},())(,({min)(0)(11)(11LnnksfsusgsfsfkkkkkksUukknnkkk第23页/共55页贝尔曼最优化原理(1)当过程指标函数为“和”的形式时，相应的函数基本方程为:ïïîïïíì-=+==++Î++1,2,,1,)},())(,({)(0)(1111LnnksfsusgoptsfsfkkkkkkUukknnkk(2)当过程指标函数为“和”的形式时，相应的函数基本方程为:ïïîïïíì-=·==++Î++12111111,,,n,nk)}s(f))s(u,s(g{opt)s(f)s(fkkkkkkUukknnkkL第24页/共55页动态规划方法的基本步骤用函数基本方程逆推求解是常用的方法:首先要有效地建立动态规划模型,然后再递推求解,最后得出结论。正确地建立一个动态规划模型,是解决问题的关键。正确的动态规划模型,应该满足下列条件:1.应将实际问题恰当地分割成n个子问题(n个阶段)通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n。第25页/共55页动态规划方法的基本步骤2.正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性。要能够正确地描述受控过程的变化特征。要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。在解静态规划模型时，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量sk的维数．约束条件所表示的内容，就是状态变量sk所代表的内容。第26页/共55页动态规划方法的基本步骤3.正确地定义决策变量及各阶段的允许决策集合Uk(sk)一般将问题中待求的量，选作动态规划模型中的决策变量，或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常常取前者的变量xj为后者的决策变量uk。4.正确地写出状态转移方程要能正确反映状态转移规律。如果给定第k阶段状态变量sk的值，则该段的决策变量uk一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有:

sk+1=Tk(sk,uk)第27页/共55页动态规划方法的基本步骤5.正确地写出目标函数。要满足可分性，即对于所有k后部子过程，其目标函数仅取决于状态sk及其以后的决策:uk,uk+1,…,un。即它是定义在全过程和所有后部子过程上的数量函数。要满足递推关系。即:Vk,n(sk,uk,sk+1,uk+1,…

,sn+1)=ψk[sk,uk,

Vk+1(sk+1,…

,sn+1)]函数严格单调。即:

ψk[sk,uk,Vk+1(sk+1,…

,sn+1)]对变元Rk+1来说要严格单调。第28页/共55页动态规划方法的基本步骤动态规划的四大要素状态变量及其可能集合sk∈Sk决策变量及其允许集合uk∈Uk

状态转移方程sk+1=Tk(sk,uk)阶段效应Vk(sk,uk)动态规划基本方程ïïîïïíì-=+==++Î++1,2,,1,)},())(,({)(0)(1111LnnksfsusgoptsfsfkkkkkkUukknnkk第29页/共55页逆推解法设已知初始状态为s1,并假定最优值函数fk(sk)表示第k阶段的初始状态为sk，从k阶段到n阶段所得到的最大效益。从第n阶段开始，则有:),(max)()(nnnsDxnnxsvsfnnnÎ=解该问题，得到最优解xn=xn(sn)和最优值fn(sn)。在第n阶段，有)](),([max)(111)(1111nnnnnsDxnnsfxsvsfnnn*=---Î----在第k阶段，有)](),([max)(11)(1++Î*=kkkkksDxkksfxsvsfkkk如此类推，直到第一阶段有)](),([max)(22111)(11111sfxsvsfsDx*=Î由于初始状态s1已知,故x1=x1(s1)和f1

(s1)是确定的，从而s2=T1(s1,x1)也就可以确定，于是x2=x2(s2)和f2(s2)也可确定。按照上述递推过程相反的顺序推算，就可逐步确定每阶段的决策和效益。第30页/共55页逆推解法例6-3:用逆推法求解下面问题。0,,max3213213221³=++=xxxcxxxxxxz按照变量个数划分阶段，该问题是一个三阶段决策问题。状态变量为s1,s2,s3,且s1=c决策变量即为问题中的变量x1,x2,x3各阶段指标函数按乘积方式最优值函数fk(sk)表示从第k阶段初始状态sk

到第3阶段所得最大值。设s1=c，

s2+x1=s1,s3+x2=s2,s3=x3则有x3=s3，0≤x2≤s2，0≤x1≤s1第31页/共55页顺推解法设已知终止状态为sn+1,并假定最优值函数fk(sk)表示第k阶段末的结束状态为sk，从1阶段到k

n阶段所得到的最大效益。从第1阶段开始，则有:),(max)()(111sDx11xsvsf111Î=解该问题，得到最优解x1=x1

(s2)和最优值f1(s2)。在第n阶段，有)](),([max)()(1nn-1nnnsDxnnsfxsvsfnnn*=Î+由于终止状态sn+1已知,故xn=xn(sn+1)和最优值fn

(sn+1)是确定的，按照上述递推过程相反的顺序推算，就可逐步确定每阶段的决策和效益。得到最优解xn=xn(sn+1)和最优值fn

(sn+1)。第32页/共55页例6-4:用顺推法求解下面问题。0,,max3213213221³=++=xxxcxxxxxxz最优值函数fk(sk+1)表示从第k阶段末的结束状态sk+1，从第1阶段到k阶段所得最大值。设

s2=x1,s3+x2=s3,s3+x3=s4=c则有x1=s2，0≤x2≤s3，0≤x3≤s4顺推解法第33页/共55页资源分配问题(离散型)例6-5:设有6万元资金用于4个工厂的扩建，已知每个工厂的利润增长额同投资额的大小有关，见下表。问应如何确定对这四个工厂的投资额，使总利润增长额最大？投资额(j)工厂(i)0100200300400500600

10204260758590

20254557657073

30183961789095

40284765748085表1利润增长额gi(xj)单位:百元第34页/共55页资源分配问题(离散型)解:把对四个工厂的投资依次看成4个阶段的决策过程，确定对第k个工厂的投资额看成第k个阶段的决策，k=1,2,3,4。工厂1工厂2工厂3工厂4投资x1投资x2投资x3投资x4状态s2状态变量sk

:可用于第k,k+1,…n个工厂的投资额。决策变量xk

:第k

阶段对第k

个工厂的投资额。允许决策集Dk:{100,200,

…,sk}状态转移方程:sk+1

=sk

-xk，

s1=600阶段指标函数gk

:第k阶段投资xk元时所产生的利润。最优指标函数fk

(sk):第k阶段状态为sk且采取最佳投资策略，从第k

个工厂以及以后的最大总利润。s1=600状态s3状态s4状态s5s2=s1-x1s3=s2-x2s4=s3-x3îíì=+=++££0)()()({max)(55110sfsfsgsfkkkksxkkkk第35页/共55页资源分配问题(离散型)投资额(j)工厂(i)010020030040050060030284765748085k=4时，第4个工厂投资时，还有资金s4，若投资于第4个工厂的资金为x4，则最大利润为:)}({max)}()({max)(44055440444444xgsfxgsfsxsx££££=+=x4

g4(x4)s4f4(s4)x4*01002003004005006000000028100281000284720047200028476530065300028476574400744000284765748050080500028476574808560085600第36页/共55页资源分配问题(离散型)投资额(j)工厂(i)010020030040050060030183961789095k=3时，第3个工厂投资时，还有资金s3，若投资于第3个工厂的资金为x3，则最大利润为:x3

g3+f4s3f3(s3)x3*01002003004005006000+00000+2818+01002800+4718+2839+02004700+6518+4739+2861+0300652000+7418+6539+4761+2878+0400893000+8018+7439+6561+4778+2890+05001083000+8518+8039+7461+6578+4790+2895+0600126300)}()({max)}()({max)(33433044330334433xsfxgsfxgsfsxsx-+=+=££££第37页/共55页资源分配问题(离散型)投资额(j)工厂(i)01002003004005006002f3(s3)0254557657073028476789108126k=2时，第2个工厂投资时，还有资金s2，若投资于第2个工厂的资金为x2，则最大利润为:x2

g2+f3s2f2(s2)x2*01002003004005006000+00000+2825+01002800+4725+2845+0200531000+6725+4745+2857+0300732000+8925+6745+4757+2865+040092100,2000+10825+8945+6757+4765+2870+05001141000+12625+10845+8957+6765+4770+2873+0600134200)}()({max)}()({max)(22322033220222222xsfxgsfxgsfsxsx-+=+=££££第38页/共55页资源分配问题(离散型)投资额(j)工厂(i)01002003004005006001f2(s2)0204260758590028537392114134k=1时，s1=600，若投资于第1个工厂的资金为x1，则最大利润为:x1

g1+f2s1f3(s3)x1*01002003004005006000+13420+11442+9260+7375+5385+2890+06001340,100,200)}()({max)}()({max)600()(1121160002211600011111xsfxgsfxgfsfxx-+=+==££££此时对应最大值134的有三个值，所对应的最优策略分别为x1*=0,100,200，再由状态转移方程可得到其它最优策略:x1*=0,x2*=200,x3*=300,x4*=100,x1*=100,x2*=100,x3*=300,x4*=100x1*=200,x2*=100,x3*=200,x4*=100,x1*=200,x2*=200,x3*=0,x4*=200第39页/共55页背包问题设有n种物品，每一种物品数量无限。第i种物品每件重量为wi，每件价值ci。现有一只可装载重量为W的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设第i种物品取xi件(i=1,2,…,n，xi为非负整数)，背包中物品的价值为z，则则Max

z=c1x1+c2x2+…+cnxn

w1x1+w2x2+…+wnxn≤W

x1,x2,…,xn为正整数第40页/共55页阶段k:第k次装载第k种物品(k=1,2,…,n)状态变量sk:第k次装载时背包还可以装载的重量决策变量xk:第k次装载第k种物品的件数决策允许集合: Dk(sk)={xk|0≤xk≤

sk/wk，xk为整数}；状态转移方程:sk+1=sk-wkxk阶段指标:vk=ckxk递推方程fk(sk)=max{ckxk+fk+1(sk+1)}=max{ckxk+fk+1(sk-wkxk)}终端条件:fn+1(sn+1)=0背包问题第41页/共55页例6-6:已知c1=65,c2=80,c3=30,w1=2,w2=3,w3=1,W=5,f4(x4)=0背包问题k=3时:k=2时:k=2时:)}30{max)}({max)(3/04433/033333333xsfxcsfwsxwsx££££=+=)}3(80{max)}({max)(2232/03322/022222222xsfxsfxcsfwsxwsx-+=+=££££)}2(65{max)}({max)(1121/02211/011111111xsfxsfxcsfwsxwsx-+=+=££££应取第一种物品2件,第三种物品1件,最高价值为160元,背包没有余量。由f1(x1)得列表可以看出，如果背包得容量为W=4，W=3，W=2和W=1时，相应的最优解立即可以得到。第42页/共55页设有某种资源总数量为s1,可投入用于生产A、B产品。第一年若以数量u1投入生产A，剩下的s1-u1就投入生产B，则可得到收入为g(u1)+h(s1-u1),其中g(u1)和h(u1)为已知函数，且g(0)+h(0)=0,这种资源在投入A、B产品生产后，年终还可回收再投入生产。设年回收率分别为0<a<1和0<b<1，则在第一年生产后，回收的资源量合计为s2=au1+bh(s1-u1)。第二年再将资源数量s2中的u2和s2-u2分别投入A、B产品生产，则又可得到收入为g(u2)+h(s2-u2)。如此进行n年，试问应当如何决定每年投入A生产的资源量u1,u2,…,un,才能使总的收入最大？资源分配问题(连续型)第43页/共55页MaxZ=g(u1)+h(s1-u1)+g(u2)+h(s2-u2)+…+g(un)+h(sn-un)s2=au1+bh(s1-u1)s3=au2+bh(s2-u2)……sn+1=aun+bh(sn-un)0≤ui≤si+1，i=1，2，…，n状态变量sk:第k阶段可投入A、B两种生产的资源量决策变量uk:第k阶段可投入A生产的资源量，则sk-uk投入B生产的资源量状态转移方程:sk+1=auk+b(sk-uk)资源分配问题(连续型)ïîïíì-+=-++-+=££+££)}()({max)()]}([)()({max)(010nnnsunnkkkkkkksukkushugsfusbaufushugsfnnkk第44页/共55页例6-7:某公司有500辆运输卡车，在超负荷运输(即每天满载行驶500km以上)情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3；在低负荷下运输(即每天行驶300km以下)情况下，年利润为16万元/辆。年损坏率为0.1。现要制定一个5年计划，问每年年初应如何分配在两种不同的负荷下完好车辆运输的卡车数量，使5年内的总利润最大？状态变量sk:第k年初完好卡车数量，其中s1=500决策变量xk:第k年初分配给超负荷运输的卡车数量，则分配给低负荷的卡车数为sk-uk状态转移方程:sk+1=(1-0.3)xk

+(1-0.1)(sk-xk)=0.9sk

-0.2xk阶段指标函数gk(xk):表示第k年度利润,即

gk(xk)=25xk+16(sk-xk)=16sk+9xk设备负荷分配问题第45页/共55页最优指标函数fk(sk):第k年度初完好车辆数为sk时，采用最优策略到第5年末所产生的最大利润。

设备负荷分配问题{}îíì==+=++££0)(1,2,3,4,5)()(max)(66110sfksfxgsfkkkksxkkkk第一年初:500辆车全部用于低负荷运输。第二年初:还有450辆完好的车，也全部用于低负荷运输。第三年初:还有405辆完好的车，全部用于超负荷运输。第四年初:还有238.5辆完好的车，全部用于超负荷运输。第五年初:还有198.45辆完好的车，全部用于超负荷运输。到第五年末，即第六年初，还剩余138.15辆完好的车。实现最大利润约3.74亿元。第46页/共55页课堂思考:某公司有1000辆运输卡车，在超负荷运输(即每天满载行驶500km以上)情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3；在低负荷下运输(即每天行驶300km以下)情况下，年利润为16万元/辆。年损坏率为0.1。现要制定一个5年计划，问每年年初应如何分配在两种不同的负荷下完好车辆运输的卡车数量，使在第5年年末剩余的完好卡车数量为500台，并且使在5年内的总利润最大？设备负荷分配问题第47页/共55页例6-8:某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产品的数量如下表所示。该厂生产每批产品的固定成本为3千元，若不生产为0；每单位产品成本为1千元；每个时期生产能力所允许的最大生产批量为不超过6个单位；每个时期末未售出的产品，每单位需支付存储费用0.5千元。假定在第一个时期的库存为0，第四个时期库存量为0。该厂应如何安排各个时期的生产与库存，才能在满足市场需要的条件下，成本最小？时期1234需求量2324生产计划问题第48页/共55页状态变量sk

:第k阶段结束时的产品库存量。决策变量xk

:xk为第k阶段该产品的生产量。状态转移方程:设dk为第k阶段对产品的需求量，则

sk

=sk-1

+xk-dkck(xk)表示第k阶段生产产品xk时的成本费用。h