运筹学chap6动态规划DynamicProgramming

第六章动态规划

(DynamicProgramming)教学要求：

了解动态规划的基本思想

掌握一维离散动态规划的建模和求解方法应用

会运用动态规划方法解决一些基本应用问题。1可编辑ppt动态规划是运筹学的一个分支，是求解多阶段决策过程最优化问题的数学方法。动态规划在经济管理、工程技术、工农业生产及军事部门中都有着广泛的应用，并且获得了显著的效果。学习动态规划，首先要了解多阶段决策问题。§6.1动态规划原理和模型2可编辑ppt例1：最短路径问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或运费），试求从A点到G点的最短距离（总运输费用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687636853384222133352566433可编辑ppt用穷举法的计算量:从A到G的6个阶段，一共有48条路线，比较47次。4可编辑ppt例2：背包问题

有一个徒步旅行者，其可携带物品重量的限度为a公斤，设有n种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使其背包所起作用（使用价值）最大？物品12…j…n重量（公斤/件）a1

a2

…

aj…

an每件使用价值c1

c2

…cj…

cn类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。5可编辑ppt

生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。机器负荷分配问题：某种机器可以在高低两种不同的负荷下进行生产。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和完成飞行任务（如软着陆）。6可编辑ppt根据过程的特性可以将过程按空间、时间等标志分为若干个互相联系又互相区别的阶段。在每一个阶段都需要做出决策，从而使整个过程达到最好的效果。各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。当各个阶段的决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线，这样的一个前后关联具有链状结构的多阶段过程就称为多阶段决策问题。多阶段决策过程：7可编辑ppt针对多阶段决策过程的最优化问题，美国数学家Bellman等人在20世纪50年代初提出了著名的最优化原理，把多阶段决策问题转化为一系列单阶段最优化问题，从而逐个求解，创立了解决这类过程优化问题的新方法：动态规划。对最佳路径（最佳决策过程）所经过的各个阶段，其中每个阶段始点到全过程终点的路径，必定是该阶段始点到全过程终点的一切可能路径中的最佳路径（最优决策），这就是Bellman提出的著名的最优化原理。简言之，一个最优策略的子策略必然也是最优的。Bellman在1957年出版的《DynamicProgramming》是动态规划领域的第一本著作。8可编辑ppt动态规划的基本概念最短路问题：某运输公司拟将一批货物从A地运往E地，其间的交通系统网络如下图所示。图上节点表示地点，边表示两地之间的道路，边上的数字表示两地间的运输费用，求运输费用最低的运输路线。AB1B2B3C1C2C3D1D2E第2阶段第3阶段第4阶段第1阶段的状态决策：某阶段状态给定之后，从该状态演变到下一阶段某一状态的选择。比如从第一阶段到第二阶段选择什么路线。

策略：各阶段决策确定后，组成的一个有序的决策序列。第2阶段的状态第1阶段一、动态规划的基本概念9可编辑ppt

1、阶段（k）

将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序求解。2、状态sk

能表示决策顺序的离散的量，阶段可以确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。

10可编辑ppt

3、决策uk从某一状态向下一状态过渡时所做的选择。表示决策的变量为决策变量，用uk(sk)表示第k阶段，状态为sk时的决策变量。决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。

4、策略Pk,n(sk)从第k阶段开始到最后第n阶段的决策序列，称k子策略。PA,E(s1)即为全过程策略。11可编辑ppt5、状态转移方程是确定过程由阶段的一个状态到下一阶段另一状态下的演变过程，用公式sk+1=Tk(sk,uk)表示。该公式描述了由第k阶段到第k+1阶段的状态转移规律。12可编辑ppt

6、阶段指标函数vk(sk,uk)

从状态sk出发，选择决策uk所产生的第k阶段指标。过程指标函数Vk,n(sk,uk,uk+1,…,un)：从状态sk出发，选择决策uk,uk+1,…,un所产生的过程指标。动态规划要求过程指标具有可分离性，即Vk,n(sk,uk,uk+1,…,un)=Vk(sk,uk)+Vk+1(sk+1,uk+1,…,un)称指标具有可加性。Vk,n(sk,uk,uk+1,…,un)=Vk(sk,uk)×Vk+1(sk+1,uk+1,…,un)称指标具有可乘性。13可编辑ppt

基本方程最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即

14可编辑ppt

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

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

以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。

终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态n+1下最优指标，

fn+1(sn+1)=0。15可编辑ppt例3：某公司打算在三个不同的地区设置四个销售点，据市场预测部门估计，在不同的地区设置不同数量的销售点，每月可获得的利润如下表所示。试问在各个地区应该如何设置销售点，才能使每月获得的总利润最大？其值是多少？请用动态规划方法分析求解。地区销售点01234A036810B045811C067912各地区不同销售点数量利润表（单位：百万元）16可编辑ppt解：根据多阶段决策问题的特征，将此问题转化为三个阶段的决策问题。1.阶段k=1，2，3，分别代表A，B，C三地区。2.状态变量Sk：表示第k个地区设置销售点时还可设置的销售点数量。3.决策变量Uk：表示第k个地区的销售点数量。6.最优指标函数f（Sk）。4.状态转移方程：Sk+1=Sk-Uk。5.阶段指标值：利润如表V（Sk，Uk）。17可编辑ppt7.动态递推方程：

f（Sk）=Max

V（Sk，Uk）+f（Sk+1）

k=2，1

f（S3）=Max

V（S3，U3）

18可编辑ppt阶段k=3V（S3，U3）f（S3）U3*U3=0U3=1U3=2U3=3U3=4S3=0000S3=10661S3=206772S3=3067993S3=40679121248.逆序递推求解动态方程：表119可编辑ppt阶段k=2V（S2，U2）+f（S3）f（S2）U2*U2=0U2=1U2=2U2=3U2=4S2=00+000S2=10+64+060S2=20+74+65+0101S2=30+94+75+68+0111，2S2=40+124+95+78+612+0143表220可编辑ppt阶段k=1V（S1，U1）+f（S2）f（S1）U1*U1=0U1=1U1=2U1=3U1=4S1=40+143+116+108+610+0162决策方案：地区A——设置2个销售点；地区B——设置1个销售点；地区C——设置1个销售点。此时公司可以获得最大总利润16（百万元）。表321可编辑ppt例2：从A地到E地要铺设一条煤气管道,其中需经过三级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？

AB2B1B3C1C3D1D2E52141126101043121113965810521C222可编辑ppt

解：整个计算过程分四个阶段，从最后一个阶段开始。

第四阶段（D→E）：D有两条路线到终点E。显然有AB2B1B3C1C3D1D2E52141126101043121113965810521C223可编辑ppt首先考虑经过的两条路线第三阶段（C→D）：C到D有6条路线。(最短路线为)AB2B1B3C1C3D1D2E5214126101043121113965810521C224可编辑pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路线为)考虑经过的两条路线25可编辑pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路线为)考虑经过的两条路线26可编辑pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路线为)第二阶段（B→C）：B到C有9条路线。首先考虑经过的3条路线27可编辑pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路线为)考虑经过的3条路线28可编辑pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路线为)考虑经过的3条路线29可编辑pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路线为)第一阶段（A→B）：A到B有3条路线。（最短距离为19）30可编辑ppt

动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n维决策问题变换为几个一维最优化问题，从而一个一个地去解决。需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。二.动态规划的原理最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。也就是说，一个最优策略的子策略也是最优的。31可编辑ppt

动态规划方法的关键：在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。32可编辑ppt动态规划适用于求解哪一类问题？每个阶段的最优决策过程只与本阶段的初始状态有关，而与以前各阶段的决策（即为了到达本阶段的初始状态而采用哪组决策路线无关）。换言之，本阶段之前的状态与决策，只是通过系统在本阶段所处的初始状态来影响本阶段及以后各个阶段的决策。或者说，系统过程的历史只能通过系统现阶段的状态去影响系统的未来。具有这种性质的状态称为无后效性（即马尔科夫性）状态。动态规划方法只适用于求解具有无后效性状态的多阶段决策问题。33可编辑ppt练习1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最优路线为：A→B1→C2→D1→E2→F2→G

路长＝18求从A到G的最短路径334可编辑pptk=5，出发点E1、E2、E3u5(E1)=F1E1F1GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u5(E2)=F2E2F2Gu5(E3)=F2E3F2Gk=6,F1G,f6(F1)=4F2G,f6(F2)=335可编辑pptk=4，f4(D1)=7

u4(D1)=E2f4(D2)=6

u4(D2)=E2f4(D3)=8

u4(D3)=E2k=2,f2(B1)=13

u2(B1)=C2f2(B2)=16u2(B2)=C3f3(C1)=13

u3(C1)=D1f3(C2)=10

u3(C2)=D1f3(C3)=9

u3(C3)=D1f3(C4)=12

u3(C4)=D3k=3,=minf1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E236可编辑ppt增加研制费（万元）新产品成功的概率甲乙丙0120.600.800.850.400.700.900.300.600.70例3：有一工厂研制甲、乙、丙三种新产品，估计这三种新研制成功的概率分别为：0.6、0.4、0.3。由于工厂急于推出新产品，决定再加拨2万元研制费，以提高新产品研制成功的概率。据估计，把增加的研制费用于各种新产品研制时，研制成功的概率见下表。现把这批研制费分配给各新产品（不分配、分配给1万元或分配给2万元），使这三种新产品都研制成功的概率最大。应怎样分配。37可编辑ppt解：1.划分阶段根据问题的性质，按照时间、空间、变量划分为若干阶段，这是用多阶段决策过程描述一个实际问题的第一步。一个阶段表示需要做出一次决策的子问题，建立动态规划模型要求每个阶段问题具有同一模式。描述阶段的变量称为阶段变量，常用自然数k表示。

可划分为3个阶段求解，对甲产品增加研制费记为第1阶段，对乙产品增加研制费记为第2阶段，对丙产品增加研制费记为第3阶段，k=1，2，3。38可编辑ppt2.确定状态变量及相应的取值范围

多阶段决策过程的进展，可用各阶段的状态演变来描述。状态必须包含表示系统情况和确定决策所需要的全部信息，使其能反映过程的演变特征。同时还要状态满足无后效性，即若已知过程现在处于某一阶段的某一状态，则该阶段以后过程的演变，不再受以前各阶段状态的影响。确定状态变量之后，根据具体问题的性质，找出状态变量在各阶段的取值范围。

把有可能提供的研制费用作状态变量，记为sk，取值为0，1，2（万元）39可编辑ppt3.确定决策变量决策变量一般由系统最优化的目的所决定。把给第K种新产品的研制费用的数量作为决策变量uk,显然，uk不能超过当时拥有的金额sk

即：uk≤sk40可编辑ppt4.建立状态转移方程根据状态变量和决策变量的含义，写出状态转移方程。根据以上对状态变量和决策变量的规定，有：41可编辑ppt5.确定边界条件过程开始和结束的状态。由于开始时可用的金额为2万元，而最后将全部用完，有S1=2,S4=042可编辑ppt6.确定指标函数，建立动态规划的基本方程选取指标函数，根据指标函数建立最优指标函数递推关系,即基本方程。

定义各阶段研制成功概率pk(sk,uk)的乘积为指标函数，并求指标函数最大化。基本方程为43可编辑ppt第三阶段

s3=0

s3=1

s3=2第二阶段

s2=0

s2=1

s2=2第一阶段只有S1=2s2=s1-u1*=2-0=2s3=s2-u2*=2-1=1最优解0-1-1从最后一个阶段开始，逐阶段向前，直至第一阶段，即可求出全过程最优策略和指标函数的最优值。§6.2一维动态规划求解方法

1、逆推法44可编辑ppt2、顺推法

s3=s4+1=1s2=s3+1=2最优解0-1-1由第一阶段开始，逐阶段向后，直至最后一个阶段，同样可求出最优策略和指标函数的最优值。Sk+1表示第k阶段的状态变量。第一阶段

s2=0

s2=1

s2=2第二阶段

s3=0s3=1

s3=2第三阶段45可编辑ppt有一个徒步旅行者，其可携带物品重量的限度为a公斤，设有n种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使背包其所起作用（使用价值）最大？物品12…j…n重量（公斤/件）a1

a2

…

aj…

an每件使用价值c1

c2

…cj…

cn一、背包问题§6.3动态规划在经济和管理中的应用46可编辑ppt设xj为第j种物品的装件数（非负整数）则问题的数学模型如下：用动态规划方法求解，令fk(y)为总重量不超过y公斤，包中只装有前k种物品时的最大使用价值。其中y≥0，k＝1,2,…,n。所以问题就是求fn(a)47可编辑ppt其递推关系式为：当k=1时，有：48可编辑ppt例3：求下面背包问题的最优解物品(xi)

x1

x2

x3重量（ai）325使用价值8512解：a＝5，问题是求f3(5)49可编辑ppt物品(xi)

x1

x2

x3重量（ai）325使用价值851250可编辑ppt物品(xi)

x1

x2

x3重量（ai）325使用价值851251可编辑ppt物品(xi)

x1

x2

x3重量（ai）325使用价值851252可编辑ppt53可编辑ppt所以，最优解为X＝（1.1.0），最优值为Z=13。总结：解动态规划的一般方法:从终点逐段向始点方向寻找最小(大)的方法。54可编辑ppt现有数量为a（万元）的资金，计划分配给n个工厂，用于扩大再生产。假设：xi为分配给第i个工厂的资金数量（万元）；gi(xi)为第i个工厂得到资金后提供的利润值（万元）。问题：如何确定各工厂的资金数，使得总的利润为最大。据此，有下式：二.投资分配问题55可编辑ppt

令：fk(x)表示以数量为x的资金分配给前k个工厂，所得到的最大利润值。用动态规划求解，就是求

fn(a)的问题。

当k=1时，f1(x)=g1(x)（因为只给一个工厂）

当1＜k≤n时，其递推关系如下：设：y为分给第k个工厂的资金（其中0≤y≤x），此时还剩x－y（万元）的资金需要分配给前k－1个工厂，如果采取最优策略，则得到的最大利润为fk－1(x－y)，因此总的利润为：

gk(y)＋fk－1(x－y)56可编辑ppt如果a是以万元为资金分配单位，则式中的y只取非负整数0，1，2，…，x。上式可变为：所以，根据动态规划的最优化原理，有下式：57可编辑ppt例4：设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。投资利润0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依据题意，是要求f4(60)。58可编辑ppt按顺序解法计算。第一阶段：求f1(x)。显然有f1(x)＝g1(x)，得到下表

投资利润0102030405060f1(x)＝

g1(x)0205065808585最优策略0102030405060第二阶段：求f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。59可编辑ppt最优策略为（40，20），此时最大利润为120万元。同理可求得其它f2(x)的值。60可编辑ppt最优策略为（30，20），此时最大利润为105万元。61可编辑ppt最优策略为（20，20），此时最大利润为90万元。最优策略为（20，10），此时最大利润为70万元。62可编辑ppt最优策略为（10，0）或（0，10），此时最大利润为20万元。

f2(0)＝0。最优策略为（0，0），最大利润为0万元。得到下表最优策略为（20，0），此时最大利润为50万元。63可编辑ppt

投资利润0102030405060f2(x)020507090105120最优策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)第三阶段：求f3(x)。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。64可编辑ppt最优策略为（20，10，30），最大利润为155万元。同理可求得其它f3(x)的值。得到下表65可编辑ppt

投资利润0102030405060f3(x)0256085110135155最优策略(0,0,0)(0,0,10)(0,0,20)(0,0,30)(20,0,20)(20,0,30)(20,10,30)第四阶段：求f4(60)。即问题的最优策略。66可编辑ppt最优策略为（20，0，30，10），最大利润为160万元。67可编辑ppt排序问题指n种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。1.n×1排序问题

即n种零件经过1种设备进行加工，如何安排？14682023交货日期（d）45173加工时间（t）零件代号例：三、排序问题68可编辑ppt（1）平均通过设备的时间最小按零件加工时间非负次序排列顺序，其时间最小。（即将加工时间由小到大排列即可）零件加工顺序工序时间13457实际通过时间1481320交货时间82314620平均通过时间延迟时间=13–6=769可编辑ppt（2）按时交货排列顺序零件加工顺序工序时间13457实际通过时间56101720交货时间82314620平均通过时间延迟时间=070可编辑ppt（3）既满足交货时间，又使平均通过时间最小零件加工顺序工序时间13457实际通过时间1691320交货时间82314620延迟时间=0平均通过时间71可编辑ppt

2.n×2排序问题

即n种零件经过2种设备进行加工，如何安排？例：49523B53786A零件设备ABT72可编辑ppt经变换为49523B53786A零件设备加工顺序图如下：ABT3756895432+2+2-5

加工周期T=3+7+5+6+8+2=3173可编辑ppt

3.n×3排序问题

即n种零件经过3种设备进行加工，如何安排？例：3468564683579310CBAABCT74可编辑pptABCT变换4+36+45+86+56+48+65+37+53+910+3B+CA+B75可编辑ppt排序4+36+45+86+56+48+65+37+53+910+3B+CA+B复原3468564683579310CBA76可编辑ppt计算T=6+10+8+7+6+4+3=44计算依据：77可编辑ppt练习：11851079827746CBAT=4578可编辑ppt练习：求投资分配问题得最优策略，其中a＝50万元，其余资料如表所示。投资利润01020304050g1(x)02140528085g2(x)015365073100g3(x)0256065687079可编辑ppt例：某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如何设置销售点可使每月总利润最大。地区销售点01234123000161210251714302116322217x1=2，x2=1，x3=1，f3(4)=4780可编辑ppt练习1：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过6吨，问如何安排运输，使总利润最大？种类123重量（吨/公斤）234单件利润（元）80130180最优方案：X1

=（0.2.0）X2=（1.0.1）Z=26081可编辑ppt练习2：求下列问题的最优解

X=(2.1.0)

最优值为

Z=1382可编辑ppt背包问题

一位旅行者携带背包旅游，已知他的背包所能承受的重量为w千克，现有n种物品可供他选择装入包中，第i种物品的单件重量为wi千克，其价值是携带数量的函数。问旅行者应如何选择携带物品的件数，使总价值最大？

划分阶段

将可装入物品按排序，每段装一种物品，共划分为n个阶段，k=1,2,……,n.

状态变量

表示在第k阶段开始时，背包中允许装入前k种物品的总重量，记为sk

决策变量

装入第k种物品的件数xk

建立状态转移方程

sk+1=sk-wkxk

允许决策集合

确定指标函数

确定边界条件

背包所能承受的重量为w千克83可编辑ppt生产计划问题

已知企业产品的生产费用、存储费用和市场的需求量，在其生产能力和存储能力许可的前提下，怎样制定各个时期的生产计划，既能完成交货任务，又使总支出最小。某中转仓库要按月在月初供应一定数量的某种部件给总装车间，由于生产条件的变化，生产车间在各月份中生产每单位这种部件所需耗费的工时不同，各月份的生产量于当月的月底前，全部要存入仓库以备后用。已知总装车间的各个月份的需求量以及在加工车间生产该部件每单位数量所需工时，仓库容量和开始库存量，要求最终库存量为0，要制定一个半年的逐月生产计划，既满足需要和仓库容量的限制，又使生产这种部件的总耗费工时数最少。

84可编辑ppt生产计划问题划分阶段

按月份划分阶段，每个月为一个阶段，k=1,2,……,n.

状态变量

第k阶段开始时（即本阶段需求送出之前，上阶段产品送入之后）部件库存量，记为sk

决策变量

第k阶段内的部件生产量，记为uk

建立状态转移方程

sk+1=sk+uk-dk

最优指标函数

fk(sk)表示在第k阶段开始的库存量为sk时，从第k阶段到最后一阶段生产部件的最小累计工时数。

基本方程

确定边界条件

so=开始库存量，sn=085可编辑ppt货物存储问题考虑下面三个月的库存问题，在每月初，公司必须决定在本月内，应生产多少产品。在一个月内生产x单位的产品，所需成本为c(x)，其中c(0)=0，当x>0时，c(x)=3+2x。每月最多生产4个单位，每月的需求是随机的，或为1或为2单位。如果生产的数量大于需求，就出现库存。每个月末检查库存，1个单位的库存费用是1元。因为库存能力有限，每月末的库存量不能超过3单位。但同时要求必须及时满足需求。在第3个月末要把现有的库存以每单位2元的价格售出。在第1月的月初，公司有1单位的库存。如何制定生产策略使三个月内的期望费用最小。

划分阶段

将三个月分为三个阶段，每个月为一个阶段

状态变量

sk表示第k个月初的库存数

决