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

对只具有两个决策变量的目标规划的数学模型，我们可以用图解法来分析求解。通过图解示例，可以看到目标规划中优先因子，正、负偏差变量及权系数等的几何意义。图解法的基本步骤1.令各偏差变量为0，作出所有的约束直线2.作图表示偏差变量增加对约束直线的影响3.确定满足第一优先级目标集的最优解空间（不考虑其他优先级）4.转到第k+1优先级，求出其相应的最优解空间5.令k=k+1反复执行步骤（4），直到所有的优先级均求解完毕。上周内容回顾对只具有两个决策变量的目标规划的数学模型，我们可1【例题】某电视机厂装配黑白和彩色两种电视机，每装配一台电视需占用装配线1小时，装配线每周计划开动40小时，预计市场每周彩色电视机的销量是24台，每台可获利为80元，黑白电视机的销量为30台，每台可获利40元。该厂确定的目标为：第一优先级：充分利用装配线每周计划开动40小时；第二优先级：允许装配线加班；但加班时间每周尽量不超过10小时；第三优先级：装配电视机的数量尽量满足市场需要。因彩色电视机的利润高，取其权系数为2。试建立该问题的目标规划模型，并求解黑白电视机和彩色电视机的产量。【例题】某电视机厂装配黑白和彩色两种电视机，每装配一台电视需2设x1,x2分别表示黑白和彩色电视机的产量，该问题的目标规划模型为：用图解法求解，见下图。设x1,x2分别表示黑白和彩色电视机的产量，该3x1x205040302010

10203040501.令各偏差变量为0，作出所有的约束直线x1x205010204GHFEDCBAx1x205040302010

1020304050d4+d3-d2+d2-d1+d1-d4-d3+2.作图表示偏差变量增加对约束直线的影响GHFEDCBAx1x20501025P1,P2的目标实现后，x1,x2的取值范围为ABCD3.确定满足第一优先级目标集的最优解空间（不考虑其他优先级）4.转到第k+1优先级，求出其相应的最优解空间GHFEDCBAx1x205040302010

1020304050d4+d3-d2+d2-d1+d1-d4-d3+P1,P2的目标实现后，x1,x2的取值范围为ABCD3.6P３目标要求，d3-权系数大于d4-,取d3-=0，

x1,x2的取值范围为ABEF在ABEF中，只有

E点d4-取极小值。取E点为满意解(24,26)5.令k=k+1反复执行步骤（4），直到所有的优先级均求解完毕。GHFEDCBAx1x205040302010

1020304050d4+d3-d2+d2-d1+d1-d4-d3+P３目标要求，d3-权系数大于d4-,取d3-=0，x17第10章动态规划10.1多阶段决策问题10.2多阶段决策的有关概念10.3动态规划的基本思想和基本方程10.4动态规划模型的建立与求解10.5动态规划应用举例

第10章动态规划10.1多阶段决策问题8

动态规划所研究的对象是多阶段决策问题。所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。10.1多阶段决策问题动态规划所研究的对象是多阶段决策问题。19在实际生产经营活动中，存在着一类将过程划分为若干个相互联系的阶段，而每个阶段都需要做出决策，并且一个阶段的决策确定后，常影响下一阶段的决策，即多阶段决策问题。在这类多阶段决策问题中，整个问题的各个阶段所确定的决策构成一个决策序列，通称为策略。对应于一个策略，就有确定活动效果，且可用数量指标来衡量。因此多阶段决策问题就需要在允许选择的那些策略中选择最优策略，使在预定的标准下达到最好的效果。动态规划是一种解决问题的思路，而不是一种算法。这一点与线性规划不同，线性规划是一种算法。在实际生产经营活动中，存在着一类将过程划分为10

【例10-1】生产与存储问题某工厂每季度需供应市场600，700，500和1200件产品，未销售完的产品存入仓库，存储费为每件每季度1元，生产费用为件数的平方成正比，比例系数为0.005。现要制定生产计划，在满足市场需求的条件下，使一年的生产与存储费用最少。按季度的顺序分为4个阶段，k=1,2,3,4设第k季生产的产品为uk件，

第k季初的库存量为sk，

第k季的销售量为qk

，则sk+1=sk+uk-qk假设年初和年底无存货，即

s1=s5=0【例10-1】生产与存储问题按季度的顺序分为4个阶段11全过程目标管理函数为：该问题是求最优的生产决策序列，即全年中每季度的最优生产量u1*,u2*,u3*,u4*，在满足市场需求的条件下，使得一年的总费用最少。则该问题的数学模型为：全过程目标管理函数为：该问题是求最优的生产决策序12【例10-2】最短路线问题。设有一辆汽车由A城到B城，中间可经过v1到v8城市，各城市的交通路线及距离如图所示，问应选择哪一条路线，可使总距离最短。Av285685547866924337131234v39v6Bv8v7v5v4v1【例10-2】最短路线问题。设有一辆汽车由A城到13这一问题看成是四个阶段的决策问题，由A到(v1,v2,v3)中的点是第一阶段；由(v1,v2,v3)中的点到(v4,v5,v6)中的点是第二阶段；由(v4,v5,v6)中的点到(v7,v8)中的点是第二阶段；由(v7,v8)中的一点到B是第四阶段。要求在各个阶段选取一个恰当的决策，由这些决策组成的决策序列所决定的一条路线，其总路程最短。Av285685547866924337131234v39v6Bv8v7v5v4v1这一问题看成是四个阶段的决策问题，由A到(v1,v2,v3)1410.2多阶段决策的有关概念1.阶段把所给问题的过程恰当地分为若干个相互联系的阶段，以便按一定顺序去求解。描述阶段的变量称为阶段变量，用k表示。阶段的划分，一般是按时间和空间的自然特征来划分。【例10-1】生产与存储问题按自然时间分为4个阶段（季度）K=1，2，3，4。【例10-2】最短路问题按空间的自然特征分为4个阶段。年、月、路段10.2多阶段决策的有关概念1.阶段152.状态状态表示每个阶段开始时所处的自然状态或客观条件，描述了问题过程的状况，又称为不可控因素。描述过程状态的变量称为状态变量。用sk表示第k阶段所处的状态。状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合。【例10-1】中状态是每个阶段开始时的库存量，它既是前一阶段决策的结果，又是后一阶段决策的开始。通常一个阶段有若干个状态。构成状态集合。【例10-1】中s1=0，s5=0表示状态变量s1，s5的值为0，而s2，s3，s4的取值可能有多种情况。2.状态状态表示每个阶段开始时所处的自然16s1=A，s2=(v1,v2,v3)，s3=(v4,v5,v6)，s4=(v7,v8)状态应具有无后效性如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；过程的过去历史只能通过当前的状态去影响它未来的发展；构造动态规划模型时，要充分注意是否满足无后效性的要求；如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。Av285685547866924337131234v39v6Bv8v7v5v4v1【例10-2】中s1=A，s2=(v1,v2,v3)，s3=(v4,v5,v17在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合。常用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}。在实际问题中决策变量的取值往往在某一范围之内18

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

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

(s1).即

4.策略按顺序排列的决策组成的集合；

由第k

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

由每段的决策按顺序排列组成的决策函数序列称为k子过程策略，简称子策略，记为pk,n(sk)，即可供选择的策略有一定范围，此范围称为允许策略195.状态转移方程状态转移方程是确定过程由一个状态到另一个状态的演变过程。本阶段的状态是上一阶段状态和上一阶段决策的结果，对于本阶段来讲，状态是已知的。如果给出第k阶段状态变量sk的值、该阶段的决策变量uk一经确定，第k+1阶段状态变量sk+1的值也就确定，其关系为：5.状态转移方程状态转移方程是确定过程2012ks1u1s2u2s3skukSk+1能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。图示如下：【例10-1】中，状态转移方程为sk+1=sk+uk–qk其中k=1,2,3,4【例10-2】中，状态转移方程为sk+1=uk(sk)12ks1u1s2u2s3skukSk+121

6.指标函数和最优值函数用来衡量所实现过程优劣的一种数量指标，称为指标函数；它分阶段指标函数和过程指标函数。阶段指标函数：仅是某一阶段到下一阶段的效益，用dk(sk,uk)表示，指在第k阶段由状态sk采取决策uk(sk)时的效益。Av285685547866924337131234v39v6Bv8v7v5v4v1【例10-2】中，d3(v4,v7)是指由v4出发，下一阶段的决策是v7的两点间的距离。即d3(v4,v7)

=3。6.指标函数和最优值函数用来衡量22过程指标函数：它是定义在全过程和所有后部子过程上的数量函数，表示第k阶段状态为sk、采用策略pk,n(sk)时后部k子过程的效益值。动态规划模型的指标函数，应具有可分离性，并满足递推关系。

费用、成本、利润、路长等。用Vk,n

表示之。即Vk,n可以表示为sk,uk,Vk+1,n的函数Vk,n=f(sk,uk,Vk+1,n)的函数。过程指标函数：它是定义在全过程和所有后部子过程上的数量函数23常见的指标函数的形式是：过程和它的任一子过程的指标是它所包含的各阶段的指标和。即无后效性的结果。其中dj(sj

)

表示第

j阶段的阶段指标。这时上式可写成过程和它的任一子过程的指标是它所包含的各阶段的指标的乘积。即则可改写成常见的指标函数的形式是：过程和它的任一子过程的指标是它所包含24

第k阶段第n阶段状态sk

终止状态采取最优策略所得到的指标函数值。最优值函数：最优指标函数是指从第k阶段状态采用最优策略到过程终止时的最佳效益值，即指标函数的最优值,记为fk(sk)可递推即采取最优策略所得到的指标函数值。最优值函数：25

Av285685547866924337131234v39v6Bv8v7v5v4v1【例10-2】中，f3*(v4)是指从v4到B的最短距离。整个问题即为f1*(A)是指从A到B的最短距离。具有可分离性Av28568554786692433713123426解多阶段决策过程问题，求出

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

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

最优目标函数值从k到终点最优策略子策略的最优目标函数值解多阶段决策过程问题，求出最优策略，即最优决策序列27步步走近路，距离为：5+7+3+4=19。问题：是否一定最优？Av285685547866924337131234v39v6Bv8v7v5v4v110.3动态规划的基本思想和基本方程【例10-2】步步走近路步步走近路，距离为：5+7+3+4=19。Av285685528最优化定理作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态而言，以后所有的决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。

对最短路问题而言,从最短路上任一点到终点的部分道路（最短路上的子路）也一定是从该点到终点的最短路。

动态规划的基本思想：逐段分析，逐点考虑并优化后，逐步扩大范围，直到找到最优解。最优化定理动态规划的基本思想29如果一个问题的最短路在某阶段通过Qs，则由点Qs出发到达终点的这条路线，对于从Qs出发到达终点的所有可能选择的不同路线来说，必定是最短路线。QsAB要找到最短路，只要从最后一段开始，用逐步逆推的方法，求出各点到终点的最短路线，最后求得由起点到终点的最短路线。如果一个问题的最短路在某阶段通过Qs，则由点30【例10-3】按照动态规划的基本思想求解【例10-2】中最短路问题。Av285685547866924337131234v39v6Bv8v7v5v4v1【例10-3】按照动态规划的基本思想求解【例10-2】中最短31具体计算前，先引进几个符号：K——阶段变量sk——状态变量，表示第k阶段所处的位置uk——决策变量，表示当状态为sk时，可选择的下一状态(这里有uk=Sk+l)dk(sk,uk)

——从sk到sk+1＝uk的距离fk*

(sk)——由sk到终点的最短距离。求解此问题的过程，是从最后一个阶段开始计算，逐步倒退直到第一阶段为止，即用逐步逆推的方法，该问题就是求f1*

(s1)。具体计算前，先引进几个符号：32Av285685547866924337131234v39v6Bv8v7v5v4v1（1）在第四阶段：

当k=4时，只要再走一步即到终点B地。目前的状态集s4={v7,v8}，可选择的下一状态u4是B。v7Bf4*(v7)=4v8B

f4*(v8)=3从v7和v8到B的最短路径唯一从v7和v8到B的最短路径为：Av285685547866924337131234v39v33（2）在第三阶段：k=3,s3={v4,v5,v6}说明v4到B的最短距离为7，其最短路线为v4→v7→B,u3(v4)=v7Av285685547866924337131234v39v6Bv8v7v5v4v1u3(v4)=v7v4v7B（2）在第三阶段：k=3,s3={v4,v5,v6}说明v434u3(v5)=v8v5v8Bu3(v6)=v7v6v7BAv285685547866924337131234v39v6Bv8v7v5v4v1u3(v5)=v8u3(v6)=v7Av285685547835Av285685547866924337131234v39v6Bv8v7v5v4v1（3）在第二阶段：k=2,s2={v1,v2,v3}说明从v1到B的最短距离为9，其最短路线为v1→v5→v8→B，相应决策为u2(v1)=v5Av285685547866924337131234v39v36说明从v2到B的最短距离为11，其最短路线为v2→v6→v7→B，相应决策为u2(v2)=v6Av2