管理运筹学 课件 田世海 第6、7章 目标规划、动态规划

OperationalResearch

运筹学Chapter6第6章GoalProgramming

目标规划OperationalResearchIntroduction目标规划问题及模型目标规划的图解法目标规划的单纯形法主要内容目标规划灵敏度分析目标规划应用举例目标规划问题及模型1、问题的提出： 目标规划是在线性规划的基础上，为适应经济管理多目标决策的需要而由线性规划逐步发展起来的一个分支。 由于现代化企业内专业分工越来越细，组织机构日益复杂，为了统一协调企业各部门围绕一个整体的目标工作，产生了目标管理这种先进的管理技术。目标规划是实行目标管理的有效工具，它根据企业制定的经营目标以及这些目标的轻重缓急次序，考虑现有资源情况，分析如何达到规定目标或从总体上离规定目标的差距为最小。目标规划问题及模型例1.某企业计划生产甲，乙两种产品，这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。问该企业应如何安排计划，使得计划期内的总利润收入为最大？目标规划问题及模型解：设甲、乙产品的产量分别为x1，x2，建立线性规划模型：其最优解为x1＝4，x2＝2，z＊＝14元目标规划问题及模型但企业的经营目标不仅仅是利润，而且要考虑多个方面，如：力求使利润指标不低于12元；考虑到市场需求，甲、乙两种产品的生产量需保持1:1的比例；C和D为贵重设备，严格禁止超时使用；设备B必要时可以加班，但加班时间要控制；设备A即要求充分利用，又尽可能不加班。要考虑上述多方面的目标，需要借助目标规划的方法。目标规划问题及模型线性规划模型存在的局限性：1）要求问题的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足。2）只能处理单目标的优化问题。实际问题中，目标和约束可以相互转化。3）线性规划中各个约束条件都处于同等重要地位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分。4）线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。目标规划问题及模型目标规划怎样解决上述线性规划模型建模中的局限性？1.设置偏差变量，用来表明实际值同目标值之间的差异偏差变量用下列符号表示：d+——超出目标的偏差，称正偏差变量d-——未达到目标的偏差，称负偏差变量正负偏差变量两者必有一个为0。当实际值超出目标值时：d+>0,d-=0;

当实际值未达到目标值时：d+=0,d->0;

当实际值同目标值恰好一致时：d+=0,d-=0;故恒有d+×d-=0目标规划问题及模型2.统一处理目标和约束

对有严格限制的资源使用建立系统约束，数学形式同线性规划中的约束条件。如C和D设备的使用限制。

对不严格限制的约束，连同原线性规划建模时的目标，均通过目标约束来表达。1）例如要求甲、乙两种产品保持1:1的比例，系统约束表达为：x1=x2。由于这个比例允许有偏差，当x1<x2时，出现负偏差d-，即：x1+d-

=x2或x1－x2+d-

=0当x1>x2时，出现正偏差d+，即：x1-d+

=x2或x1－x2-d+

=0目标规划问题及模型∵正负偏差不可能同时出现，故总有：x1－x2+d--d+

=0

若希望甲的产量不低于乙的产量，即不希望d->0,用目标约束可表为:

若希望甲的产量低于乙的产量，即不希望d＋>0,用目标约束可表为:

若希望甲的产量恰好等于乙的产量，即不希望d＋>0,也不希望d->0用目标约束可表为:目标规划问题及模型3）设备B必要时可加班及加班时间要控制，目标约束表示为：2）力求使利润指标不低于12元，目标约束表示为：4）设备A既要求充分利用，又尽可能不加班，目标约束表示为：目标规划问题及模型3.目标的优先级与权系数

在一个目标规划的模型中，为达到某一目标可牺牲其他一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P1,P2,…表示。对于同一层次优先级的不同目标，按其重要程度可分别乘上不同的权系数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。现假定：

第1优先级P1——企业利润；第2优先级P2——甲乙产品的产量保持1:1的比例第3优先级P3——设备A,B尽量不超负荷工作。其中设备A的重要性比设备B大三倍。目标规划问题及模型上述目标规划模型可以表示为：目标规划问题及模型5.目标规划的目标函数由各目标约束的正、负偏差变量及相应的优先因子和权系数构成。从决策者的要求来分析，总希望得到的结果与规定的指标值之间的偏差量愈小愈好。由此可构造一个使总偏差量为最小化的目标函数，minZ=f（d+，d-）其基本形式有三种：4.满意解

对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。目标规划问题及模型（1）要求恰好达到目标值，即正、负偏差变量都要尽可能地小。构造的目标函数是

minZ=f（d++d-

）

（2）要求不超过目标值，但允许达不到目标值，即只有使正偏差量要尽可能地小（实现最少或为零）

minZ=f（d+）（3）要求超过目标值，即超过量不限。要求超额完成规定目标，要实现负偏差量为零或为最小

minZ=f（d-）目标规划问题及模型

建模的步骤1、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；4、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数。3、给各目标赋予相应的优先因子Pi（i=1.2…L）。2、可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。目标规划问题及模型目标规划数学模型的一般形式目标函数（达成函数）目标约束其中：gk为第k个目标约束的预期目标值，和为pl优先因子对应各目标的权系数。目标规划问题及模型用目标规划求解问题的过程：明确问题，列出目标的优先级和权系数构造目标规划模型求出满意解满意否？分析各项目标完成情况据此制定出决策方案NY目标规划问题及模型例2.某厂生产Ⅰ、Ⅱ两种产品，有关数据如表所示。试求获利最大的生产方案？

在此基础上考虑：

1、产品Ⅱ的产量不低于产品Ⅰ的产量；

2、充分利用设备有效台时，不加班；

3、利润不小于56元。解:分析第二目标P2

：第三目标P3

：第一目标P1:ⅠⅡ拥有量原材料2111设备(台时)1210单件利润810目标规划问题及模型1、产品Ⅱ的产量不低于产品Ⅰ的产量；

2、充分利用设备有效台时，不加班；

3、利润不小于56元。2x1+x2≤11（在绝对约束基础上进行目标规划）

x1-x2+d1--d1+=0

(要求：d1+

尽可能小，最好是0才能满足≤)x1+2x2+d2--d2+=10

（要求：d2-

和d2+

都尽可能小，最好等于0）

8x1+10x2+d3--d3+=56

（要求：d3-

尽可能小，最好是0才能满足≥）

x1,x2,di-,di+≥0ⅠⅡ拥有量原材料2111设备(台时)1210单件利润810Introduction目标规划问题及模型目标规划的图解法目标规划的单纯形法主要内容目标规划灵敏度分析目标规划应用举例目标规划的图解法目标规划的图解法：

适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。图解法解题步骤：1.将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）的直线方程分别标示于坐标平面上。2.确定系统约束的可行域。3.在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向目标规划的图解法4.求满足最高优先等级目标的解5.转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解6.重复5，直到所有优先等级的目标都已审查完毕为止7.确定最优解和满意解。目标规划的图解法例4.用图解法求解下列目标规划问题目标规划的图解法(a)(b)(c)(d)x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+满意解(3,3)046834622目标规划的图解法x1x2(a)(b)d1+d1-(c)d2-d2+(d)d3-d3+GD满意解是线段GD上任意点其中G点X＝(2,4)T,D点X＝(10/3,10/3)T05.51055.6112,410/3,10/35107例5.Introduction目标规划问题及模型目标规划的图解法目标规划的单纯形法主要内容目标规划灵敏度分析目标规划应用举例目标规划的单纯形法一般形式：Cj

c1c2cn+2mCBXBb

x1x2xn+2m

cj1xj1bo1e11e12e1n+2mcj2xj2bo2e21e22e2n+2mcjmxjm

bomem1em2emn+2mσkjP1

σ11σ12σ1n+2mP2

σ21σ22σ2n+2mPK

σm1σm2σmn+2m目标规划的单纯形法一、特点1．目标函数：min2．最优性判断：σj≥0时为最优3．非基变量检验数的特殊性：含有不同等级的优先因子P1,P2,…,Pk;又因P1>>P2>>P3>>…>>Pk

，所以检验数的正负首先取决于P1的系数的正负，若P1

的系数为0，再由P2

的系数的正负决定检验数的正负，然后依次类推。目标规划的单纯形法(1)建立初始单纯形表．在表中将检验数行按优先因子个数分别列成K行。初始的检验数需根据初始可行解计算出来，方法同基本单纯形法。当不含绝对约束时，di-

（i=1,2,…,K）构成了一组基本可行解，这时只需利用相应单位向量把各级目标行中对应di-

（i=1,2,…,K）的量消成0即可得到初始单纯形表。置k＝1；解目标规划问题的单纯形法的计算步骤(2)检查当前第k行中是否存在大于0，且对应的前k-1行的同列检验数为零的检验数。若有取其中最大者对应的变量为换入变量，转(3)。若无这样的检验数，则转(5)；目标规划的单纯形法(4)按单纯形法进行基变换运算，建立新的单纯形表，（注意：要对所有的行进行转轴运算）返回(2)；(5)当k＝K时，计算结束。表中的解即为满意解。否则置k=k+1，返回（2）。(3)按单纯形法中的最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量，转（4）；目标规划的单纯形法例1.用单纯形法求解下列目标规划问题解：将上述目标规划问题化为标准型：目标规划的单纯形法建立初始单纯形表：目标规划的单纯形法θ=min｛－，10/2，56/10，11/1｝=5进基变量x2Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

001－11－100000P21012001－1000

P3

5681000001－100

x3

11210000001σjP1

000100000P2

－1－20002000P3

－8－100000010换出变量d2-目标规划的单纯形法Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

053/201－11/2-1/20000x251/21001/2-1/2000

P3

63000-551－100

x3

63/2000-1/21/2001σjP1

000100000P2

000011000P3

－30005-5010θ=min｛10/3,10,6/3,12/3｝=2,进基变量x1换出变量d3-目标规划的单纯形法Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

02001－13-3-1/21/200x2401004/3-4/3-1/61/600x121000-5/35/31/3-1/300x3

300002-2-1/21/21σjP1

000100000P2

000011000P3

000000100最优解为x1＝2，x2＝4。但非基变量d3+的检验数为零，故此题有无穷多最优解。目标规划的单纯形法Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

02001－13-3-1/21/200x2401004/3-4/3-1/61/600x121000-5/35/31/3-1/300x3

300002-2-1/21/21σjP1

000100000P2

000011000P3

000000100θ=min｛4,24,－,6｝=4进基变量d3+换出变量d1-目标规划的单纯形法Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

04002-26-6-1100x210/301-1/31/31/3-1/30000x110/3102/3-2/31/3-1/30000x3

100-1－1-11001σjP1

000100000P2

000011000P3

000000100最优解为x1＝10/3，x2＝10/3。目标规划的单纯形法例2.用单纯形法求解下列目标规划问题目标规划的单纯形法Cj00P100P302.5P20P2CBXBbx1x2P1250030121－1000000014021001－100000601000001－1000100010000001－1σjP1

－30－1201000000P2

00000002.501P3

0000010000θ=min｛2500/30,140/2,60/1,

-｝=60,进基变量x1换出变量d3-目标规划的单纯形法Cj

00P100P302.5P20P2CBXBbx1x2P17000121－100－30300002001001－1－22000x1601000001－1000100010000001－1σjP1

0－12010030－3000P2

00000002.501P3

0000010000θ=min｛700/30,20/2,－,－｝=10进基变量d3+换出变量d2-目标规划的单纯形法Cj

00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000x17011/2001/2-1/200000100010000001-1σjP1

030115-150000P2

0-5/400-5/45/45/2001P3

0000010000θ=min｛400/15,－,－,－｝=10进基变量d2+换出变量d1-目标规划的单纯形法Cj

00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000x1250/312/51/30-1/300000000100010000001－1σjP1

0010000000P2

0-1-1/121/12002/5001P3

01/5-1/151/15100000θ=min｛－,350/6,1250/6,100/1｝=75进基变量x2换出变量d3+目标规划的单纯形法Cj

00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000x2175/3011/12-1/1200-5/25/2000x160100000-11000125/300-1/121/12005/2-5/21－1σjP1

0010000000P2

00000005/201P3

00-1/121/12101/2-1/200P3优先等级目标没有实现，但已无法改进，得到满意解

x1

＝60，x2

＝175/3，

d2+＝115/3，d4-＝125/3目标规划的单纯形法例3.已知一个生产计划的线性规划模型如下，其中目标函数为总利润，x1,x2

为产品A、B产量。现有下列目标：1.要求总利润必须超过2500元；2.考虑产品受市场影响，为避免积压，A、B的生产量不超过60件和100件；3.由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用图解法求解。目标规划的单纯形法解：以产品A,B的单件利润比2.5:1为权系数，模型如下：目标规划的单纯形法0x2

0⑴x11401201008060402020406080100⑵⑶⑷ABCDC(60,58.3)T为所求的满意解。(60,58.3)目标规划的单纯形法例4.已知条件如表所示工序型号每周最大加工能力ABⅠ（小时/台）Ⅱ（小时/台）436215070利润（元/台）300450如果工厂经营目标的期望值和优先等级如下：p1:每周总利润不得低于10000元；p2:因合同要求，A型机每周至少生产10台，B型机每周至少生产15台；p3:希望工序Ⅰ的每周生产时间正好为150小时，工序Ⅱ的生产时间最好用足，甚至可适当加班。目标规划的单纯形法这个问题的目标规划模型为：目标规划的单纯形法小结线性规划LP目标规划GP目标函数min,max系数可正负min,偏差变量系数≥0变量xi,xsxa

xixsxad约束条件绝对约束目标约束、绝对约束解最优最满意运筹学

——第7章动态规划7.1多阶段决策问题7.2最优化原理与动态规划的数学模型7.3离散确定性动态规划模型的求解8.4动态规划求解举例8.1多阶段决策问题动态规划——研究多阶段决策问题的理论和方法。多阶段决策问题——决策过程可分为若干个互相联系的阶段，在每个阶段分别对

应着一组可以选取的决策，当

每个阶段的决策选定后，过程

也就随之确定。AB2B3B1C2C3C1D2D1E25567234515146333345例1：最短路问题例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。例3：

将一个数c(c>0)分成n部分c1,c2,

…cn之和，且ci>0(i=1,

…,n),问如何分割使其乘积为最大。多阶段决策问题和我们前面遇到的决策问题不同，它是和时间有关的。与时间有关的活动过程称为动态过程，其优化方法称为动态规划。与时间无关的活动过程称为静态过程，相应的优化方法称为静态规划。运筹学

——第8章动态规划8.1多阶段决策问题8.2最优化原理与动态规划的数学模型8.3离散确定性动态规划模型的求解8.4动态规划求解举例8.2最优化原理与动态规划的数学模型8.2.1动态规划的求解思路AB2B3B1C2C3C1D2D1E25567234515146333345基本思路：将一个n阶段的决策问题转化为依次求解n个具有递推关系的决策问题，从而简化计算过程。(1)考虑一个阶段的最优选择(1)考虑一个阶段的最优选择(2)联合考虑两个阶段的最优选择(1)考虑一个阶段的最优选择(2)联合考虑两个阶段的最优选择(1)考虑一个阶段的最优选择(2)联合考虑两个阶段的最优选择(1)考虑一个阶段的最优选择(3)联合考虑三个阶段的最优选择(2)联合考虑两个阶段的最优选择(1)考虑一个阶段的最优选择(3)联合考虑三个阶段的最优选择(2)联合考虑两个阶段的最优选择(1)考虑一个阶段的最优选择(3)联合考虑三个阶段的最优选择(4)联合考虑四个阶段，从A到E的最优选择(2)联合考虑两个阶段的最优选择(1)考虑一个阶段的最优选择(3)联合考虑三个阶段的最优选择(4)联合考虑四个阶段，从A到E的最优选择最短路：128.2最优化原理与动态规划的数学模型8.2.1动态规划的求解思路将多阶段决策问题转化为依次求解多个单阶段决策问题的特征：求解的各阶段有递推性。8.2.2动态规划的基本概念

1、阶段（stage）：指问题需要作业决策的步骤，通

常用k表示问题包含的阶段数，

称为阶段变量。

k的编号方法：顺序编号法逆序编号法例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。8.2.2动态规划的基本概念2、状态（state）表示每个阶段开始时所处的自然状况或客观条件，描述了影响决策的因素随决策进程的变化情况。它既是前面阶段所作决策的结果，又是本阶段作出决策的出发点和依据。第k阶段的状态变量常用xk表示。第1阶段状态变量x1是确定的，称初始状态。8.2.2动态规划的基本概念2、状态（state）表示每个阶段开始时所处的自然状况或客观条件.第k阶段的状态变量常用xk表示。例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。运筹学

——第8章动态规划8.1多阶段决策问题8.2最优化原理与动态规划的数学模型8.3离散确定性动态规划模型的求解8.4动态规划求解举例(2)联合考虑两个阶段的最优选择(1)考虑一个阶段的最优选择(3)联合考虑三个阶段的最优选择(4)联合考虑四个阶段，从A到E的最优选择最短路：128.1多阶段决策问题8.2.1动态规划的求解思路将多阶段决策问题转化为依次求解多个单阶段8.1多阶段决策问题8.2.2动态规划的基本概念

1、阶段：k2、状态：xk8.2.2动态规划的基本概念3、决策（decision）表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，uk(xk)表示第k阶段状态变量为xk时对方案的选择。决策变量的取值会受到状态变量的制约，被限制在某一范围之内。Dk(xk)——k阶段状态变量为xk时决策的允许取值范围8.2.2动态规划的基本概念3、决策（decision）例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。4、策略和子策略8.2.2动态规划的基本概念策略——动态规划问题各阶段决策组成的序列总体。子策略——从某一阶段开始到过程最终的决策序列。4、策略和子策略8.2.2动态规划的基本概念策略子策略5、状态转移方程8.2.2动态规划的基本概念若第k阶段的状态变量值为xk，当决策变量uk(xk)的取值决定后，下一阶段状态变量xk+1的值也就完全确定。即xk+1的值对应于xk和uk的值。记为:或简写为：例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。6、指标函数8.2.2动态规划的基本概念（1）阶段指标函数：对某一阶段的状态和决策产生

的效益值的度量，用表示。（2）过程指标函数：过程所包含的各阶段的状态和

决策所产生的总的效益值，记为：常见的两种过程指标函数形式是：①各阶段指标函数的和：②各阶段指标函数的积：8.2.2动态规划的基本概念（3）最优指标函数：对某一确定状态选取最优策略后得到的指标函数值。对应于从状态出发的最优子策略的效益值记作，则有：例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。阶段指标函数：最优指标函数：例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。阶段指标函数：Vk,5=∑[8uj+5(xj-uj)]=∑(5xj+3uj)fk(xk)＝max{5xj+3uj+fk+1(xk+1)}k=5,4,3,2,10≤uk≤xk最优指标函数：8.2.2动态规划的基本概念状态xkxk+1xk+2状态状态决策uk(xk)决策uk+1(xk+1)阶段指标函数

阶段指标函数T(xk,uk)T(xk+1,uk+1)k+1阶段k阶段动态规划概念模型示意图或过程指标函数Dk(xk)—Dk+1(xk+1)—最优指标函数：8.2.3最优化原理与动态规划的数学模型1、最优化原理：作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的决策必构成最优决策。8.2.3最优化原理与动态规划的数学模型1、最优化原理：作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的决策必构成最优决策。2、动态规划的基本方程与边界条件例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下年产量g和机器数u的关系为g＝8u,机器的年完好率为a=0.7。在低负荷年产量h和机器数v的关系为h＝5v,机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，制定五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。例2：机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下年产量g和机器数u的关系为g＝8u,机器的年完好率为a=0.7。在低负荷年产量h和机器数v的关系为h＝5v,机器的年完好率为b=0.9。假定开始生产时完好的机器数量为x1，制定五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。（1）阶段：（2）状态变量：（3）决策变量：（4）状态转移律：（5）指标函数：（6）基本方程：（7）边界条件：(1)按年数划分为5个阶段，k=1,2,3,4,5(2)取第k年初完好的机器数xk为状态变量(3)取第k年投入高负荷的机器数uk为决策变量,0≤uk≤xk(4)状态转移方程为xk+1=0.7uk+0.9(xk-uk)=0.9xk-0.2uk(5)指标函数为Vk,5=∑[8uj+5(xj-uj)]=∑(5xj+3uj)(6)基本方程与边界条件为：解:fk(xk)＝max{5xj+3uj+fk+1(xk+1)}k=5,4,3,2,10≤uk≤xkf6(x6)＝0例2：机器负荷分配问题8.2.3最优化原理与动态规划的数学模型例：用动态规划的方法求解下述非线性规划问题：maxz=i·xii=13x1+3x2+2x312x1、x2、x30s.t8.2.3最优化原理与动态规划的数学模型（1）阶段数：k=1,2,····,n（2）状态变量：xk——？（3）决策变量：uk——？，允许决策集合D(xk)（4）状态转移律：xk+1=T(xk，uk)（5）阶段指标函数：vk(xk)——?（6）基本方程：fk(xk)=?（7）边界条件：fn+1(xn+1)=?8.2.3最优化原理与动态规划的数学模型例：用动态规划的方法求解下述非线性规划问题：maxz=i·xii=13x1+3x2+2x312x1、x2、x30s.t解：归结为三阶段动态规划问题，每阶段确定一个变量的数值。x13x22x30s1=12s2=s1-x1s3=s2-3x2s4=s3-2x3状态变量Sk：8.2.3最优化原理与动态规划的数学模型例：用动态规划的方法求解下述非线性规划问题：maxz=i·xii=13x1+3x2+2x312x1、x2、x30s.t（1）阶段变量：（2）状态变量：Sk——（3）决策变量：xk——D(Sk)=（4）状态转移律：

（5）阶段指标函数：（6）基本方程：（7）边界条件：8.2.3最优化原理与动态规划的数学模型例：用动态规划的方法求解下述非线性规划问题：maxz=i·xii=13x1+3x2+2x312x1、x2、x30s.t（1）阶段变量：k=1,2,3（2）状态变量：Sk——第k阶段可用于分配的右端项数量；（3）决策变量：xk——第k阶段选取的变量数值；D(Sk)={0

x1

S1,0x2

S2/3,0x3

S3/2}；（4）状态转移律：S2=S1－x1

；S3=S2－3x2；S4=S3－2x3；（5）阶段指标函数：vk(xk)=k·xk；（6）基本方程：fk(Sk)=max{vk(xk)·fk+1(Sk+1)}（7）边界条件：f4(S4)=1构造和求解动态规划模型需要注意的：状态xkxk+1xk+2状态状态决策uk(xk)决策uk+1(xk+1)阶段指标函数

阶段指标函数T(xk,uk)T(xk+1,uk+1)k+1阶段k阶段（1）状态变量的确定是建模的关键。（2）决策变量是控制过程的手段，取舍可能连续或离散。（3）状态转移律中，Xk+1的取值可能是确定的或随机的。（4）指标函数必须有递推性。1、逆序解法：从问题的最后一个阶段开始，逆多阶段的

决策过程反向寻优。用逆序解法求最短路问题2、顺序解法：从问题的最初阶段开始，同多阶段的实际

过程顺序寻优。8.2.4逆序解法与顺序解法运筹学

——第8章动态规划8.1多阶段决策问题8.2最优化原理与动态规划的数学模型8.3离散确定性动态规划模型的求解8.4动态规划求解举例8.2.2动态规划的基本概念状态xkxk+1xk+2状态状态决策uk(xk)决策uk+1(xk+1)阶段指标函数

阶段指标函数T(xk,uk)T(xk+1,uk+1)k+1阶段k阶段动态规划概念模型示意图或过程指标函数Dk(xk)—Dk+1(xk+1)—最优指标函数：（1）阶段数（2）状态变量（3）决策变量

（4）状态转移律（5）阶段指标函数（6）基本方程（7）边界条件最短路问题（1）阶段数：k=1,2,3,4,5,6（2）状态变量：xk——第k阶段的位置点。（3）决策变量：uk——第k阶段选择的行走路线，

允许决策集合D(xk)——xk位置时可选择的线路集合。（4）状态转移律：xk+1=T(xk,uk)——采取uk决策后，位置变化的规律。（5）阶段指标函数：vk(xk,uk)——选择uk决策后产生的距离。（6）基本方程：fk(xk)=min{vk(xk，uk)+fk+1(xk+1)}（7）边界条件：f7(x7)=0最短路问题基本方程:fk(xk)＝Min{Dk(uk)+fk+1(xk+1)},k＝6,5,4,3,2,1

uk∈Dk(xk)

f7(x7)＝0(1)当k=6时x6u6D6(u6)+f7(x7)f6(x6)最短路问题基本方程:fk(xk)＝Min{Dk(uk)+fk+1(xk+1)},k＝6,5,4,3,2,1

uk∈Dk(xk)

f7(x7)＝0(1)当k=6时x6u6D6(u6)+f7(x7)f6(x6)F1F1G4+0=4*4F2F2G3+0=3*3最短路问题(1)当k=6时x6u6D6(u6)+f7(x7)f6(x6)F1F1G4+0=4*4F2F2G3+0=3*3x5u5D(u5)+f6(x6)f5(x5)(2)当k=5时:最短路问题(1)当k=6时x6u6D6(u6)+f7(x7)f6(x6)F1F1G4+0=4*4F2F2G3+0=3*3x5u5D(u5)+f6(x6)f5(x5)E1E1F1E1F23+4=7*5+3=87E2E2F1E2F25+4=92+3=5*5E3E3F1E3F26+4=106+3=9*9(2)当k=5时:最短路问题x5u5D(u5)+f6(x6)f5(x5)E1E1F1E1F23+4=7*5+3=87E2E2F1E2F25+4=92+3=5*5E3E3F1E3F26+4=106+3=9*9(2)当k=5时:x4u4D(u4)+f5(x5)f4(x4)(3)当k=4时:最短路问题x5u5D(u5)+f6(x6)f5(x5)E1E1F1E1F23+4=7*5+3=87E2E2F1E2F25+4=92+3=5*5E3E3F1E3F26+4=106+3=9*9(2)当k=5时:x4u4D(u4)+f5(x5)f4(x4)D1D1E1D1E22+7=92+5=7*7D2D2E2D2E31+5=6*2+9=116D3D3E2D3E33+5=8*3+9=128(3)当k=4时:最短路问题x4u4D(u4)+f5(x5)f4(x4)D1D1E1D1E22+7=92+5=7*7D2D2E2D2E31+5=6*2+9=116D3D3E2D3E33+5=8*3+9=128(3)当k=4时:x3u3D(u3)+f4(x4)f3(x3)(4)当k=3时:最短路问题x4u4D(u4)+f5(x5)f4(x4)D1D1E1D1E22+7=92+5=7*7D2D2E2D2E31+5=6*2+9=116D3D3E2D3E33+5=8*3+9=128(3)当k=4时:x3u3D(u3)+f4(x4)f3(x3)C1C1D1C1D26+7=13*8+6=1413C2C2D1C2D23+7=10*5+6=1110C3C3D2C3D33+6=9*3+8=119C4C4D2C4D38+6=144+8=12*12(4)当k=3时:最短路问题x3u3D(u3)+f4(x4)f3(x3)C1C1D1C1D26+7=13*8+6=1413C2C2D1C2D23+7=10*5+6=1110C3C3D2C3D33+6=9*3+8=119C4C4D2C4D38+6=144+8=12*12(4)当k=3时:x2u2D(u2)+f3(x3)f2(x2)(5)当k=2时:最短路问题x3u3D(u3)+f4(x4)f3(x3)C1C1D1C1D26+7=13*8+6=1413C2C2D1C2D23+7=10*5+6=1110C3C3D2C3D33+6=9*3+8=119C4C4D2C4D38+6=144+8=12*12(4)当k=3时:x2u2D(u2)+f3(x3)f2(x2)

B1B1C1B1C2B1C31+13=143+10=13*6+9=15

13B2B2C2B2C3B2C48+9=177+9=16*6+12=18

16(5)当k=2时:最短路问题x2u2D(u2)+f3(x3)f2(x2)

B1B1C1B1C2B1C31+13=143+10=13*6+9=15

13B2B2C2B2C3B2C48+9=177+9=16*6+12=18

16(5)当k=2时:x1u1D(u1)+f2(x2)f1(x1)(6)当k=1时:最短路问题x2u2D(u2)+f3(x3)f2(x2)

B1B1C1B1C2B1C31+13=143+10=13*6+9=15

13B2B2C2B2C3B2C48+9=177+9=16*6+12=18

16(5)当k=2时:x1u1D(u1)+f2(x2)f1(x1)AAB1AB25+13=18*3+16=1918(6)当k=1时:最短路问题x6u6D6(u6)+f7(x7)f6(x6)F1F1G4+0=4*4F2F2G3+0=3*3x5u5D(u5)+f6(x6)f5(x5)E1E1F1E1F23+4=7*5+3=87E2E2F1E2F25+4=92+3=5*5E3E3F1E3F26+4=106+3=9*9x4u4D(u4)+f5(x5)f4(x4)D1D1E1D1E22+7=92+5=7*7D2D2E2D2E31+5=6*2+9=116D3D3E2D3E33+5=8*3+9=128x3u3D(u3)+f4(x4)f3(x3)C1C1D1C1D26+7=13*8+6=1413C2C2D1C2D23+7=10*5+6=1110C3C3D2C3D33+6=9*3+8=119C4C4D2C4D38+6=144+8=12*12x2u2D(u2)+f3(x3)f2(x2)

B1B1C1B1C2B1C31+13=143+10=13*6+9=15

13B2B2C2B2C3B2C48+9=177+9=16*6+12=18

16x1u1D(u1)+f2(x2)f1(x1)AAB1AB25+13=18*3+16=1918完整计算过程：即：A到G的最短路长为18，路径为：A→B1→C2→D1→E2→F2→G最短路问题(1)将所研究问题的过程划分为n个恰当的阶段，k＝1,2,…,n；(2)正确地选择状态变量xk，并确定初始状态x1的值；(3)确定决策变量uk以及各阶段的允许决策集Dk(xk)；(4)给出状态转移方程；(5)给出满足要求的过程指标函数Vk,n及相应的最优值函数；(6)写出递推方程和边界条件，建立基本方程；(7)按照基本方程递推求解。小结：动态规划法的步骤：注：前六步是建立动态规划模型的步骤。习题1：用动态求解最短路问题习题1：用动态求解最短路问题（1）阶段数：k=1,2,3,4（2）状态变量：xk——第k阶段的位置点。（3）决策变量：uk——第k阶段选择的行走路线，

允许决策集合D(xk)——xk位置时可选择的线路集合。（4）状态转移律：xk+1=T(xk,uk)——采取uk决策后，位置变化的规律。（5）阶段指标函数：vk(xk,uk)——选择uk决策后产生的距离。（6）基本方程：fk(xk)=min{vk(xk，uk)+fk+1(xk+1)}（7）边界条件：f5(x5)=0习题1：用动态求解最短路问题XkukDk(uk)+fk+1(xk+1)fk(xk)8.2.5动态规划模型的分类确定性随机性连续离散状态变量取值特征过程演变特征确定性随机性连续离散离散确定性动态规划模型连续确定性动态规划模型离散随机性动态规划模型连续随机性动态规划模型状态变量取值特征过程演变特征8.2.5动态规划模型的分类运筹学

——第8章动态规划8.1多阶段决策问题8.2最优化原理与动态规划的数学模型8.3离散确定性动态规划模型的求解8.4动态规划求解举例8.3 离散确定性动态规划模型的求解例4：某一警卫部队共有12支巡逻队，负责4个要害部门A、B、C、D的警卫巡逻。对每个部位可分别派出2-4支巡逻队，并且由于派出巡逻队数的不同，各部位在一段时期内可能造成的预期损失如表中所示。问：如何分派，可使总的预期损失为最小？队数预期损失部位2 183824343 143522314 10312125ABCD8.3 离散确定性动态规划模型的求解解：把对每个部位派出巡逻队数量的决策看成一个阶段，归结成4

阶段决策问题。（1）阶段变量：k=1,2,3,4（2）状态变量：xk（3）决策变量：uk允许决策集合D(xk)（4）状态转移律：xk+1（5）阶段指标函数：vk(uk)（6）基本方程（7）边界条件1、建立模型8.3 离散确定性动态规划模型的求解解：把对每个部位派出巡逻队数量的决策看成一个阶段，归结成4

阶段决策问题。（1）阶段变量：k=1,2,3,4（2）状态变量：xk——第k阶段可用于分配的巡逻队数量；（3）决策变量：uk——第k阶段派出的巡逻队数量；允许决策集合D(xk)={2,3,4}（4）状态转移律：xk+1=xk-uk

；（5）阶段指标函数：vk(uk)——预期损失函数，如表所示；（6）基本方程：fk(xk)=min{vk(uk)+fk+1(xk+1)}（7）边界条件：f5(x5)=01、建立模型8.3 离散确定性动态规划模型的求解（1）k=4，对D部位：由xk+1=xk-uk

；

fk(xk)=min{vk(uk)+fk+1(xk+1)}2、求解8.3 离散确定性动态规划模型的求解（1）k=4，对D部位：f4(x4)=min{v4(u4)+f5(x5)}，

f5(x5)=0，依题意，2

x412－6=6，列表计算如下：x4u4v4(u4)+f5(x5)f4(x4) u4*

(x4)2、求解8.3 离散确定性动态规划模型的求解（1）k=4，对D部位：f4(x4)=min{v4(u4)+f5(x5)}，

f5(x5)=0，依题意，2

x412－6=6，列表计算如下：x4u4v4(u4)+f5(x5)2 3 42 34 — — 3 34 31 — 4 34 31 255 34 31 256 34 31 25f4(x4) u4*

(x4)34 231 325 425 425 42、求解8.3 离散确定性动态规划模型的求解（2）k=3，对C部位由xk+1=xk-uk

；fk(xk)=min{vk(uk)+fk+1(xk+1)}8.3 离散确定性动态规划模型的求解2）k=3，对C部位，x4=x3－u3 f3(x3)=min{v3(u3)+f4(x4)} 而4

x38，列表计算如下：x3u3v3(u3)+f4(x4)f3(x3) u3*

(x3)8.3 离散确定性动态规划模型的求解2）k=3，对C部位，x4=x3－u3 f3(x3)=min{v3(u3)+f4(x4)} 而4

x38，列表计算如下：x3u3v3(u3)+f4(x4)2 3 44 24+34 — — 5 24+31 22+34 — 6 24+25 22+31 21+347 24+25 22+25 21+318 24+25 22+25 21+25f3(x3) u3*

(x3)58 255 249 247 346 48.3 离散确定性动态规划模型的求解（3）k=2，对B部位

由xk+1=xk-uk

；fk(xk)=min{vk(uk)+fk+1(xk+1)}8.3 离散确定性动态规划模型的求解3）k=2，对B部位，x3=x2－u2

f2(x2)=min{v2(u2)+f3(x3

）， 而8

x210，列表计算如下：x2u2v2(u2)+f3(x3)f2(x2) u2*

(x2)8.3 离散确定性动态规划模型的求解3）k=2，对B部位，x3=x2－u2

f2(x2)=min{v2(u2)+f3(x3

）， 而max{12-4，6}=8

x212－2=10，列表计算如下：x2u2v2(u2)+f3(x3)2 3 48 38+49 35+55 31+589 38+47 35+49 31+5510 38+46 35+47 31+49f2(x2) u2*

(x2)87 284 380 48.3 离散确定性动态规划模型的求解（4）k=1，对A部位由xk+1=xk-uk

；fk(xk)=min{vk(uk)+fk+1(xk+1)}8.3 离散确定性动态规划模型的求解4）k=1，对A部位，x2=x1－u1，x1=12

f1(x1)=min{v1(u1)+f2(x2)}，列表计算：x1u1v1(u1)+f2(x2)f1(x1) u1*

(x1)8.3 离散确定性动态规划模型的求解4）k=1，对A部位，x2=x1－u1，x1=12

f1(x1)=min{v1(u1)+f2(x2)}，列表计算：x1u1v1(u1)+f2(x2)2 3 412 18+80 14+84 10+87f1(x1) u1*

(x1)97 48.3 离散确定性动态规划模型的求解x1u1v1(u1)+f2(x2)2 3 412 18+80 14+84 10+87f1(x1) u1*

(x1)97 4最优策略：A—4，B—2，C—2，D—4；最小损失为97。xk+1=xk－uk

完整计算过程：练习-投资计划问题某企业现有5000万元资金可用于三个项目A、B、C的建设。项目利润的预期年增长额与投资的规模有