对只具有两个决策变量的目标规划的数学模型解析课件

对只具有两个决策变量的目标规划的数学模型，对只具有两个决策变量的目标规划的数学模型，我们可以用图解法来分析求解。通过图解示例，可以我们可以用图解法来分析求解。通过图解示例，可以看到目标规划中优先因子，正、负偏差变量及权系数看到目标规划中优先因子，正、负偏差变量及权系数等的几何意义。等的几何意义。图解法的基本步骤图解法的基本步骤1.令各偏差变量为令各偏差变量为0，作出所有的约束直线，作出所有的约束直线2.作图表示偏差变量增加对约束直线的影响作图表示偏差变量增加对约束直线的影响3.确定满足第一优先级目标集的最优解空间（不考确定满足第一优先级目标集的最优解空间（不考虑其他优先级）虑其他优先级）4.转到第转到第k+1优先级，求出其相应的最优解空间优先级，求出其相应的最优解空间5.令令k=k+1反复执行步骤（反复执行步骤（4），直到所有的优先级），直到所有的优先级均求解完毕。均求解完毕。上周内容回顾上周内容回顾【例题例题】某电视机厂装配黑白和彩色两种电视机，每装某电视机厂装配黑白和彩色两种电视机，每装配一台电视需占用装配线配一台电视需占用装配线1小时，装配线每周计划开动小时，装配线每周计划开动40小时，预计市场每周彩色电视机的销量是小时，预计市场每周彩色电视机的销量是24台，每台台，每台可获利为可获利为80元，黑白电视机的销量为元，黑白电视机的销量为30台，每台可获利台，每台可获利40元。该厂确定的目标为：元。该厂确定的目标为：第一优先级：充分利用装配线每周计划开动第一优先级：充分利用装配线每周计划开动40小时；小时；第二优先级：允许装配线加班；但加班时间每周尽量第二优先级：允许装配线加班；但加班时间每周尽量不超过不超过10小时；小时；第三优先级：装配电视机的数量尽量满足市场需要。第三优先级：装配电视机的数量尽量满足市场需要。因彩色电视机的利润高，取其权系数为因彩色电视机的利润高，取其权系数为2。试建立该问题的目标规划模型，并求解黑白电视试建立该问题的目标规划模型，并求解黑白电视机和彩色电视机的产量。机和彩色电视机的产量。设设x1,x2分别表示黑白和彩色电视机的产量，该问分别表示黑白和彩色电视机的产量，该问题的目标规划模型为：题的目标规划模型为：11223341211122213324412min240502430,0,1,2,3,4iiZpdpdpddxxddxxddxddxddxx ddi用图解法求解，见下图。用图解法求解，见下图。x1x2050 40 30 20 10 10 20 30 40 501.令各偏差变量为令各偏差变量为0，作出所有的约束直线作出所有的约束直线121112221332444050.2430 xxddxxddstxddxdd GHFEDCBAx1x2050 40 30 20 10 10 20 30 40 50d4+d3-d2+d2-d1+d1-d4-d3+2.作图表示偏差变量增作图表示偏差变量增加对约束直线的影响加对约束直线的影响P1,P2的目标实的目标实现后，现后，x1,x2的取的取值范围为值范围为ABCD 11223342pdpdpdd3.确定满足第一优先级确定满足第一优先级目标集的最优解空间目标集的最优解空间（不考虑其他优先级）（不考虑其他优先级）4.转到第转到第k+1优先级，求优先级，求出其相应的最优解空间出其相应的最优解空间GHFEDCBAx1x2050 40 30 20 10 10 20 30 40 50d4+d3-d2+d2-d1+d1-d4-d3+P目标要求，目标要求，d3-权系数权系数大于大于d4-,取取d3-=0，x1,x2的取值范围为的取值范围为ABEF在在ABEF中，只有中，只有 E 点点d4-取极小值。取极小值。取取E点为满意解点为满意解(24,26)11223342pdpdpdd5.令令k=k+1反复执行步骤（反复执行步骤（4），），直到所有的优先级均求解完毕。直到所有的优先级均求解完毕。GHFEDCBAx1x2050 40 30 20 10 10 20 30 40 50d4+d3-d2+d2-d1+d1-d4-d3+第第1010章章 动态规划动态规划10.1 10.1 多阶段决策问题多阶段决策问题10.2 10.2 多阶段决策的有关概念多阶段决策的有关概念10.3 10.3 动态规划的基本思想和基本方程动态规划的基本思想和基本方程10.4 10.4 动态规划模型的建立与求解动态规划模型的建立与求解10.5 10.5 动态规划应用举例动态规划应用举例 动态规划所研究的对象是多阶段决策问题。动态规划所研究的对象是多阶段决策问题。所谓所谓多阶段决策问题是多阶段决策问题是指一类活动过程，它可以指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。下一阶段的初始状态。每个阶段的决策确定以后，就得到一个决策序列，每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。段的效益的总和达到最优。10.1 多阶段决策问题多阶段决策问题 在实际生产经营活动中，存在着一类将过程划分在实际生产经营活动中，存在着一类将过程划分为若干个相互联系的为若干个相互联系的阶段阶段，而每个阶段都需要做出，而每个阶段都需要做出决决策策，并且一个阶段的决策确定后，常影响下一阶段的，并且一个阶段的决策确定后，常影响下一阶段的决策，即决策，即多阶段决策问题多阶段决策问题。在这类多阶段决策问题中，整个问题的各个阶段在这类多阶段决策问题中，整个问题的各个阶段所确定的所确定的决策决策构成一个决策序列，通称为构成一个决策序列，通称为策略策略。对应。对应于一个策略，就有确定活动效果，且可用数量指标来于一个策略，就有确定活动效果，且可用数量指标来衡量。因此多阶段决策问题就需要在允许选择的那些衡量。因此多阶段决策问题就需要在允许选择的那些策略中选择最优策略，使在预定的标准下达到最好的策略中选择最优策略，使在预定的标准下达到最好的效果。效果。动态规划是一种解决问题的思路，而不是一种算法。动态规划是一种解决问题的思路，而不是一种算法。这一点与线性规划不同，线性规划是一种算法。这一点与线性规划不同，线性规划是一种算法。【例例10-110-1】生产与存储问题生产与存储问题 某工厂每季度需供应市场某工厂每季度需供应市场600600，700700，500500和和12001200件产品，未销售完的产品存入仓库，存储费为件产品，未销售完的产品存入仓库，存储费为每件每季度每件每季度1 1元，生产费用为件数的平方成正比，元，生产费用为件数的平方成正比，比例系数为比例系数为0.0050.005。现要制定生产计划，在满足市。现要制定生产计划，在满足市场需求的条件下，使一年的生产与存储费用最少。场需求的条件下，使一年的生产与存储费用最少。按季度的顺序分为按季度的顺序分为4个阶段，个阶段，k=1,2,3,4 设设第第k季季生产的产品为生产的产品为uk件件，第第k季初的库存量季初的库存量为为sk，第第k季的季的销售量为销售量为 qk，则则sk+1=sk+uk-qk 假设年初和年底无存货，即假设年初和年底无存货，即 s1=s5=0全过程目标管理全过程目标管理函数为函数为：4211(0.005)kkkfus 该问题是求最优的生产决策序列，即全年中每该问题是求最优的生产决策序列，即全年中每季度的最优生产量季度的最优生产量u u1 1*,u,u2 2*,u,u3 3*,u,u4 4*，在满足市场需，在满足市场需求的条件下，使得一年的总费用最少。则该问题的求的条件下，使得一年的总费用最少。则该问题的数学模型为：数学模型为：4211115min(0.005)0,0kkkkkkkfusssuqss 【例【例10-2】最短路线问题。设有一辆汽车由最短路线问题。设有一辆汽车由A城到城到B城，中间可经过城，中间可经过v1到到v8城市，各城市的交通路线及城市，各城市的交通路线及距离如图所示，问应选择哪一条路线，可使总距离最距离如图所示，问应选择哪一条路线，可使总距离最短。短。Av285685547 866924337131234v39v6Bv8v7v5v4v1这一问题看成是四个阶段的决策问题，由这一问题看成是四个阶段的决策问题，由A到到(v1,v2,v3)中的点是第一阶段；由中的点是第一阶段；由(v1,v2,v3)中的点到中的点到(v4,v5,v6)中的中的点是第二阶段；由点是第二阶段；由(v4,v5,v6)中的点到中的点到(v7,v8)中的点是中的点是第二阶段；由第二阶段；由(v7,v8)中的一点到中的一点到B是第四阶段。是第四阶段。要求在各个阶段选取一个恰当的决策，由这些决策要求在各个阶段选取一个恰当的决策，由这些决策组成的决策序列所决定的一条路线，其总路程最短。组成的决策序列所决定的一条路线，其总路程最短。Av285685547 866924337131234v39v6Bv8v7v5v4v110.2 10.2 多阶段决策的有关概念多阶段决策的有关概念 1.阶段阶段 把所给问题的过程恰当地分为若干个相互联系的把所给问题的过程恰当地分为若干个相互联系的阶段，以便按一定顺序去求解。阶段，以便按一定顺序去求解。描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量，用，用k表示。表示。阶段的划分，一般是按时间和空间的自然特征来阶段的划分，一般是按时间和空间的自然特征来划分划分。【例例10-1】生产与存储问题按自然时间分为生产与存储问题按自然时间分为4个阶个阶段（季度）段（季度）K=1，2，3，4。【例例10-2】最短路问题按空间的自然特征分为最短路问题按空间的自然特征分为4个个阶段。阶段。年、年、月、月、路段路段2.状态状态 状态表示每个阶段开始时所处的自然状态或客观状态表示每个阶段开始时所处的自然状态或客观条件，描述了问题过程的状况，又称为不可控因素。条件，描述了问题过程的状况，又称为不可控因素。描述过程状态的变量称为描述过程状态的变量称为状态变量状态变量。用。用sk表示表示第第k阶段所处的状态。阶段所处的状态。状态变量的取值有一定的允许集合或范围，此状态变量的取值有一定的允许集合或范围，此集合称为集合称为状态允许集合状态允许集合。【例例10-1】中状态是每个阶段开始时的库存量，它中状态是每个阶段开始时的库存量，它既是前一阶段决策的结果，又是后一阶段决策的开始。既是前一阶段决策的结果，又是后一阶段决策的开始。通常一个阶段有若干个状态。构成状态集合。通常一个阶段有若干个状态。构成状态集合。【例例10-1】中中s1=0，s5=0表示状态变量表示状态变量s1，s5的值的值为为0，而，而s2，s3，s4的取值可能有多种情况。的取值可能有多种情况。s1=A，s2=(v1,v2,v3)，s3=(v4,v5,v6)，s4=(v7,v8)状态应具有无后效性状态应具有无后效性 如果某阶段状态给定后，则在这个阶段以后过程如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；的发展不受这个阶段以前各段状态的影响；过程的过去历史只能通过当前的状态去影响它未来过程的过去历史只能通过当前的状态去影响它未来的发展；的发展；构造动态规划模型时，要充分注意是否满足无构造动态规划模型时，要充分注意是否满足无后效性的要求；后效性的要求；如果状态变量不能满足无后效性的要求，如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。应适当地改变状态的定义或规定方法。Av285685547 866924337131234v39v6Bv8v7v5v4v1【例【例10-2】中中 在实际问题中决策变量的取值往往在某一范围在实际问题中决策变量的取值往往在某一范围之内，此范围称为之内，此范围称为允许决策集合允许决策集合。常用。常用Dk(sk)表示第表示第k阶段从状态阶段从状态sk出发的允许决策集合。出发的允许决策集合。决策变量是状态变量的函数。决策变量是状态变量的函数。常用常用uk(sk)表示第表示第k阶段当状态为阶段当状态为 sk时的决策变量。时的决策变量。3.决策决策 过程的某一阶段、过程的某一阶段、某个状态某个状态,可以做出不同的可以做出不同的决决定定(选择选择),决定下一阶段的状态，这种决定称为决定下一阶段的状态，这种决定称为决策决策。描述决策的变量，称为描述决策的变量，称为决策变量决策变量。【例例10-1】中，从第一阶段的状态中，从第一阶段的状态s1=0出发，其允许出发，其允许决策集合为决策集合为Dk(sk)=600，601，3000【例【例10-2】中，从第二阶段的状态中，从第二阶段的状态s2=v1出发，其允许出发，其允许决策集合为决策集合为Dk(sk)=v4,v5,v6。可供选择的策略有一定范围，此范围称为可供选择的策略有一定范围，此范围称为允许策允许策略集合略集合，用，用p表示。从允许策略集合中找出达到最优表示。从允许策略集合中找出达到最优效果的策略称为效果的策略称为最优策略最优策略。当当k=1时，此决策函数序列成为全过程的一个时，此决策函数序列成为全过程的一个策略，简称策略，简称策略策略，记为，记为p1,n(s1).即即)(,),(),()(22111,1nnnsusususp 4.策略策略按顺序排列的决策组成的集合；按顺序排列的决策组成的集合；由第由第k n(终止状态终止状态)为止的过程，称为原过程为止的过程，称为原过程的的后部子过程后部子过程（k子过程）。子过程）。)(,),(),()(11,nnkkkkknksusususp由每段的决策按顺序排列组成的决策函数序列称由每段的决策按顺序排列组成的决策函数序列称为为k子过程策略，简称子过程策略，简称子策略子策略，记为，记为pk,n(sk)，即即5.状态转移方程状态转移方程 状态转移方程是确定过程由一个状态到另一个状态转移方程是确定过程由一个状态到另一个状态的演变过程。本阶段的状态是上一阶段状态和状态的演变过程。本阶段的状态是上一阶段状态和上一阶段决策的结果，对于本阶段来讲，状态是已上一阶段决策的结果，对于本阶段来讲，状态是已知的。知的。211132221(,)(,)(,)kkkksLsusLsusLsu 如果给出第如果给出第k阶段状态变阶段状态变量量sk的值、该阶段的决策变的值、该阶段的决策变量量uk一经确定，第一经确定，第k+1阶段状阶段状态变量态变量sk+1的值也就确定，其的值也就确定，其关系为：关系为：12ks1u1s2u2s3skukSk+1 能用动态规划方法求解的多阶段决策过程是一能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即类特殊的多阶段决策过程，即具有无后效性具有无后效性的多阶的多阶段决策过程。段决策过程。图示如下：图示如下：【例例10-1】中，状态转移方程为中，状态转移方程为sk+1=sk+uk qk其中其中k=1,2,3,4【例例10-2】中，状态转移方程为中，状态转移方程为sk+1=uk(sk)6.指标函数和最优值函数指标函数和最优值函数 用来衡量所实现过程优劣的一种数量指标，称为用来衡量所实现过程优劣的一种数量指标，称为指标函数；它分阶段指标函数和过程指标函数。指标函数；它分阶段指标函数和过程指标函数。阶段指标函数：仅是某一阶段到下一阶段的效益，阶段指标函数：仅是某一阶段到下一阶段的效益，用用dk(sk,uk)表示，指在第表示，指在第k阶段由状态阶段由状态sk采取决策采取决策uk(sk)时的效益。时的效益。Av285685547 866924337131234v39v6Bv8v7v5v4v1【例例10-2】中，中，d3(v4,v7)是指由是指由v4出发，下一阶段出发，下一阶段的决策是的决策是v7的两点的两点间的距离。即间的距离。即d3(v4,v7)=3。过程指标函数：它是定义在全过程和所有后部子过过程指标函数：它是定义在全过程和所有后部子过程上的数量函数，表示第程上的数量函数，表示第k阶段状态为阶段状态为sk、采用策略、采用策略pk,n(sk)时后部时后部k子过程的效益值。子过程的效益值。动态规划模型的指标函数，应具有可分离性，并动态规划模型的指标函数，应具有可分离性，并满足满足递推递推关系。关系。nknkkkknknksususVV,2,1111,),(费用、成本、利润、路长等费用、成本、利润、路长等。用。用Vk,n 表示之。表示之。即即V Vk k,n n可以表示为可以表示为s sk k,u,uk k,V,Vk+1,nk+1,n的函数的函数V Vk,nk,n=f(s=f(sk k,u,uk k,V,Vk+1k+1,n n)的函数。的函数。常见的指标函数的形式是：常见的指标函数的形式是：过程和它的任一子过程的指标是它所包含的各阶过程和它的任一子过程的指标是它所包含的各阶段的指标和。即段的指标和。即usdsusVjjnkjjnkkn,k,1无后效性无后效性的结果。的结果。其中其中dj(s sj )表示第表示第 j 阶段的阶段的阶段指标阶段指标。这时上式。这时上式可写成可写成),(),(),(111,11,susVusvsusVnkknkkkknkknk 过程和它的任一子过程的指标是它所包含的各阶段的过程和它的任一子过程的指标是它所包含的各阶段的指标的乘积。即指标的乘积。即),(),(usdsusVjjjnkjnkkn,k1),(),(),(111,11,susVusvsusVnkknkkkknkknk则可改写成则可改写成),(,),(111,1111,nkknkkkknkkkknksusVussususV 第第k阶段阶段 第第n阶段阶段 状态状态sk 终止状态终止状态采取最优策略所得采取最优策略所得到的指标函数值。到的指标函数值。最优值函数最优值函数：最优指标函数是指从第：最优指标函数是指从第k阶段状态采用阶段状态采用最优策略到过程终止时的最佳效益值，即指标函数最优策略到过程终止时的最佳效益值，即指标函数的最优值的最优值,记为记为fk(sk)可递推可递推即即 ,1,()(,)knkk nkknkuufoptsVs us Av285685547 866924337131234v39v6Bv8v7v5v4v1【例例10-2】中，中，f3*(v4)是指从是指从v4到到B的最短距离。的最短距离。347473434848,34()minmin753,dv vfvfvdv vfv 整个问题即为整个问题即为 f1*(A)是指从是指从A到到B的最短距离。的最短距离。具有可具有可分离性分离性,*2*1nuuu,*2*1nsss解多阶段决策过程问题，求出解多阶段决策过程问题，求出 最优策略最优策略，即最优，即最优决策序列决策序列 susvoptsfnkknkkkuunk1,f1(s1)最优轨线最优轨线，即执行最优策略时的即执行最优策略时的状态序列状态序列 最优目标函数值最优目标函数值),(*1*1*,1*,1nnnnususVV从从k到终点最优策略到终点最优策略子策略的最优目标函数值子策略的最优目标函数值步步走近路，距离为：步步走近路，距离为：5+7+3+4=19。问题：是否一定最优？问题：是否一定最优？Av285685547 866924337131234v39v6Bv8v7v5v4v110.3 10.3 动态规划的基本思想和基本方程动态规划的基本思想和基本方程【例例10-2】步步走步步走近路近路最优化定理最优化定理 作为整个过程的最优策略具有如下性质：不管在作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对此最优策略上的某个状态以前的状态和决策如何，对该状态而言，以后所有的决策必定构成最优子策略。该状态而言，以后所有的决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。就是说，最优策略的任意子策略都是最优的。对最短路问题而言对最短路问题而言,从最短路上任一点到终点的从最短路上任一点到终点的部分道路（最短路上的子路）也一定是从该点到终点部分道路（最短路上的子路）也一定是从该点到终点的最短路。的最短路。动态规划的基本思想：逐段分析，逐点考虑并动态规划的基本思想：逐段分析，逐点考虑并优化后，逐步扩大范围，直到找到最优解。优化后，逐步扩大范围，直到找到最优解。如果一个问题的最短路在某阶段通过如果一个问题的最短路在某阶段通过Qs，则由点则由点Qs出发到达终点的这条路线，对于从出发到达终点的这条路线，对于从Qs出发到达终点出发到达终点的所有可能选择的不同路线来说，必定是最短路线。的所有可能选择的不同路线来说，必定是最短路线。QsAB要找到最短路，只要从最后一段开始，用逐步逆推的要找到最短路，只要从最后一段开始，用逐步逆推的方法，求出各点到终点的最短路线，最后求得由起点方法，求出各点到终点的最短路线，最后求得由起点到终点的最短路线。到终点的最短路线。【例【例10-3】按照动态规划的基本思想求解【例按照动态规划的基本思想求解【例10-2】中最短路问题中最短路问题。Av285685547 866924337131234v39v6Bv8v7v5v4v1具体计算前，先引进几个符号：具体计算前，先引进几个符号：K阶段变量阶段变量sk状态变量，表示第状态变量，表示第k阶段所处的位置阶段所处的位置uk决策变量，表示当状态为决策变量，表示当状态为sk时，可选择的时，可选择的下一状态下一状态(这里有这里有uk=Sk+l)dk(sk,uk)从从sk到到sk+1uk的距离的距离fk*(sk)由由sk到终点的最短距离。到终点的最短距离。求解此问题的过程，是从最后一个阶段开始计求解此问题的过程，是从最后一个阶段开始计算，逐步倒退直到第一阶段为止，即用逐步逆推的算，逐步倒退直到第一阶段为止，即用逐步逆推的方法，该问题就是求方法，该问题就是求f1*(s1)。Av285685547 866924337131234v39v6Bv8v7v5v4v1（1）在第四阶段：）在第四阶段：当当k=4时时，只要再走一步即到终，只要再走一步即到终点点B地地。目前的。目前的状态状态集集 s4=v7,v8，可选择的下一状态，可选择的下一状态u4是是B。v7 B f f4 4*(v(v7 7)=4)=4v v8 8 B f f4 4*(v(v8 8)=3)=3从从v7和和v8到到B的的最短路径唯一最短路径唯一从从v7和和v8到到B的最短路径为：的最短路径为：347473434848,34()minmin753,dv vfvfvdv vfv （2）在第三阶段：）在第三阶段：k=3,s3=v4,v5,v6说明说明v4到到B的最短距离为的最短距离为7，其最短路线为，其最短路线为 v4v7B,u3(v4)=v7Av285685547 866924337131234v39v6Bv8v7v5v4v1u3(v4)=v7v4 v7 B 367473636848,14()minmin533,dvvfvfvdvvfv 357473535848,64()minmin523,dv vfvfvdv vfv u3(v5)=v8v5 v8 Bu3(v6)=v7v6 v7 BAv285685547 866924337131234v39v6Bv8v7v5v4v1Av285685547 866924337131234v39v6Bv8v7v5v4v1（3）在第二阶段：）在第二阶段：k=2,s2=v1,v2,v3说明从说明从v1到到B的最短的最短距离为距离为9，其最短路，其最短路线为线为v1v5v8B，相应决策为相应决策为u2(v1)=v5 21434212153521636,()min,min 67,45,559dv vfvfvdv vfvdv vfv 说明从说明从v2到到B的最短的最短距离为距离为11，其最短，其最短路线为路线为v2v6v7B，相相应决策为应决策为u2(v2)=v6 22434222253522636,()min,min 87,75,6511dv vfvfvdv vfvdv vfv Av285685547 866924337131234v39v6Bv8v7v5v4v1说明从说明从v3到到B的最短的最短距离为距离为13，其最短，其最短路线为路线为v3v5v8B，相相应决策为应决策为u2(v3)=v8 23434232353523636,()min,min 77,85,9513dv vfvfvdv vfvdv vfv Av285685547 866924337131234v39v6Bv8v7v5v4v1从从A到到B的最短距离为的最短距离为17，其最短路线为，其最短路线为Av1v5v8B，相应决策为相应决策为u1(A)=v1 1121112221323,()min,min 89,911,51317dA vfvfAdA vfvdA vfv （4）在第一阶段：）在第一阶段：k=1,s1=AAv285685547 866924337131234v39v6Bv8v7v5v4v1步步走近路，步步走近路，不一定是最优不一定是最优对一个实际问题，建立动态规划模型的步骤对一个实际问题，建立动态规划模型的步骤:,),(111,11,nkknkkkknkknksusVussksV 是定义在全过程和所有后部子过程上的数量函数是定义在全过程和所有后部子过程上的数量函数;要具有可分离性，并满足递推关系。即要具有可分离性，并满足递推关系。即 函数函数 k k（s sk k，u uk k，V Vk+1,nk+1,n）对于变量对于变量V Vk+1k+1，n n要严格单调。要严格单调。1.1.将问题的过程划分成恰当的阶段；将问题的过程划分成恰当的阶段；2.2.选择状态变量选择状态变量s sk k,既能描述过程的变化又满足无既能描述过程的变化又满足无后效性；后效性；3.3.确定决策变量确定决策变量u uk k及每一阶段的允许决策集合及每一阶段的允许决策集合D Dk k(s sk k)；4.4.正确写出状态转移方程；正确写出状态转移方程；5.5.正确写出指标函数正确写出指标函数V Vk,nk,n，它应满足下面三个性质：它应满足下面三个性质：由上述性质，针对实际问题，构造动态规划基本由上述性质，针对实际问题，构造动态规划基本方程步骤：方程步骤：确定阶段指标函数确定阶段指标函数vk(sk,uk);确定状态转移方程确定状态转移方程sk+1=Tk(sk,uk)确定动态规划基本方程。确定动态规划基本方程。动态规划基本方程的一般形式为：动态规划基本方程的一般形式为：边界条件为边界条件为111nnsf或或运算运算+或或是是sk的的函数函数 1,kkkkkkkkkkkkuDsfsvsusfusopt 110nnfs