《多目标动态优化》PPT课件.ppt

《《多目标动态优化》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《多目标动态优化》PPT课件.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、系统分析方法系统分析方法秦华鹏秦华鹏北京大学深圳研究生院北京大学深圳研究生院 环境与城市学院环境与城市学院Office:E414 Tel:26035291(O)Email: 2006年年3月月第第6讲讲 多目标、动态优化多目标、动态优化一一 多目标优化多目标优化二二 目标规划目标规划三三 动态优化动态优化一一 多目标优化多目标优化多目标优化模型多目标优化模型多目标优化解的性质多目标优化解的性质多目标优化技术简介多目标优化技术简介1.1 多目标优化模型多目标优化模型决策变量决策变量lX（x1，x2，xn）目标函数目标函数lZF(x1，x2，xn)约束条件约束条件lg1(x1，x2，xn)ll g

2、m(x1，x2，xn)系统优化模型一般形式系统优化模型一般形式单目标优化与多目标优化单目标优化与多目标优化单单目标优化：目标优化：max(min)Z=f(x1，x2，xn)系统期望达到的目标可用一个函数来表达系统期望达到的目标可用一个函数来表达多目标优化：多目标优化：max(min)Z1=f1(x1，x2，xn)max(min)Z 2=f 2(x1，x2，xn)max(min)Z m=f m(x1，x2，xn)系统期望达到的系统期望达到的m个目标应该分别用个目标应该分别用m个函数来表达个函数来表达线性多目标优化线性多目标优化如果多目标优化问题的所有目标和约束条件都可如果多目标优化问题的所有目标

3、和约束条件都可用线性方程来表达，则为线性多目标问题，其目用线性方程来表达，则为线性多目标问题，其目标函数可表达为：标函数可表达为：1.2 多目标优化问题解的性质多目标优化问题解的性质 单目标问题中，各种方案的目标函数值具有可比性，单目标问题中，各种方案的目标函数值具有可比性，可以分出优劣，因此一般存在最优解可以分出优劣，因此一般存在最优解多目标问题中，对某个目标的多目标问题中，对某个目标的“优化优化”可能导致其可能导致其它目标的它目标的“劣化劣化”，因此，一般不存在能够同时，因此，一般不存在能够同时满足各个目标最优化的最优解满足各个目标最优化的最优解多目标优化问题的求解，除了要多目标优化问题的

4、求解，除了要“优化优化”单个目标单个目标本身，还要本身，还要平衡平衡各个目标间的关系，因此，多目标各个目标间的关系，因此，多目标优化问题的解是优化问题的解是经过各目标权衡后相对满意的方案经过各目标权衡后相对满意的方案1.3 多目标规划求解技术简介多目标规划求解技术简介 一般思路为：采取某种方式，一般思路为：采取某种方式，平衡平衡各个目各个目标间的关系，将多目标规划问题转化为标间的关系，将多目标规划问题转化为单单目标规划目标规划问题去处理。问题去处理。平衡平衡的技术有：的技术有：v效用最优化模型效用最优化模型v罚款模型罚款模型v目标规划模型目标规划模型v约束模型约束模型v（1）效用最优化模型）效

5、用最优化模型按一定方式，将一系列的目标函数与效用按一定方式，将一系列的目标函数与效用函数建立相关关系，对各效用函数加权求函数建立相关关系，对各效用函数加权求和，以该和函数作为的单目标规划问题的和，以该和函数作为的单目标规划问题的目标函数目标函数目标函数目标函数fi(X)效用函数效用函数i(X)式中，式中，是与各目标函数相关的效用函数的和函是与各目标函数相关的效用函数的和函数；数；权值权值i来反映原问题中各目标函数在总体目来反映原问题中各目标函数在总体目标中的权重，满足：标中的权重，满足：效用函数效用函数效益型效益型效用函数效用函数成本型成本型效用函数效用函数区间型区间型（2）罚款模型）罚款模型

6、如果对每一个目标函数，决策者都能提出如果对每一个目标函数，决策者都能提出一个一个期望值期望值（或称满意值（或称满意值）f*i，那么，可，那么，可通过比较实际值与期望值通过比较实际值与期望值 f*i 之间的偏差之间的偏差来构造单目标问题。来构造单目标问题。在上式中，在上式中，i 是与第是与第i个目标函数相关的权重个目标函数相关的权重（3）目标规划模型）目标规划模型 目标规划模型与罚款模型类似，它也需要目标规划模型与罚款模型类似，它也需要预先确定各个目标的期望值预先确定各个目标的期望值 f*i（4）约束模型）约束模型 如果规划问题的某一目标可以给出一个可如果规划问题的某一目标可以给出一个可供选择的

7、范围，则该目标就可以作为约束供选择的范围，则该目标就可以作为约束条件而被排除出目标组，进入约束条件组条件而被排除出目标组，进入约束条件组中中假如，除了第一个目标外，其余目标都可假如，除了第一个目标外，其余目标都可以提出一个可供选的范围，则：以提出一个可供选的范围，则：max(minZ)=f1(x1,x2,xn)二二 目标规划目标规划目标规划由线性规划发展演变而来目标规划由线性规划发展演变而来处理多目标问题的简单实用的方法处理多目标问题的简单实用的方法目标规划与线性规划问题的对比目标规划与线性规划问题的对比目标规划问题的数学模型目标规划问题的数学模型目标规划求解方法目标规划求解方法案例分析案例分

8、析2.1 目标规划与线性规划问题的对比目标规划与线性规划问题的对比线性规划线性规划v单单目标问题目标问题v目标值目标值待求待求v追求目标的追求目标的最优值最优值（最大或最小）（最大或最小）目标规划目标规划v单单或或多多目标问题目标问题v目标值（理想值、期望值）目标值（理想值、期望值）已知已知v追求追求尽可能接近尽可能接近理想值的解理想值的解满意解满意解例例1某厂生产甲、乙两种产品，已知单件生产所某厂生产甲、乙两种产品，已知单件生产所需工时、可用工时数、及单件收益需工时、可用工时数、及单件收益 甲产品甲产品 乙产品乙产品 可用工时可用工时金工工时金工工时 4 2 400装配工时装配工时 2 4

9、500收益收益/件件 100 80 （1）从）从线性规划线性规划角度考虑角度考虑LP：maxZ=100X1+80X2 2X1+4X2 5004X1+2X2 400X1,X2 0 X*=(50,100)Z*=13000 目标：在现有资源条件下，追求最大收益目标：在现有资源条件下，追求最大收益（2）从）从目标规划目标规划角度考虑角度考虑理想值理想值理想值（期望值）：去年总收益理想值（期望值）：去年总收益9000，期望增长期望增长11.1%，即希望今年总收益达即希望今年总收益达到到10000v理想值已经确定理想值已经确定v允许计算值（决策值）小于或大于理想值允许计算值（决策值）小于或大于理想值v希望

10、计算值与理想值之间的（负）差别尽希望计算值与理想值之间的（负）差别尽可能小可能小（2）从）从目标规划目标规划角度考虑角度考虑正、负偏差正、负偏差计算值与理想值之间三种可能：计算值与理想值之间三种可能：v计算值计算值理想值，超过，理想值，超过，d-=0v计算值计算值=理想值，相等，理想值，相等，d+=d-=0因此：因此：d+*d-=0 d+，d-0 引入正、负偏差变量引入正、负偏差变量d+、d-vd+：计算值计算值超过超过理想值部分理想值部分(正偏差变量正偏差变量)vd-：计算值计算值不足不足理想值部分理想值部分(负偏差变量负偏差变量)100X1+80X2-d+d-=10000（2）从）从目标规

11、划目标规划角度考虑角度考虑绝对约束与目标约束绝对约束与目标约束绝对约束：绝对约束：必须严格满足的条件，不能满必须严格满足的条件，不能满足绝对约束的解即为非可行解足绝对约束的解即为非可行解目标约束：目标约束：目标规划所特有的一种约束，目标规划所特有的一种约束，以目标的以目标的理想值作为约束方程右端常数项理想值作为约束方程右端常数项，不必严格满足，允许发生正负偏差。不必严格满足，允许发生正负偏差。4X1+2X2 4002X1+4X2 500100X1+80X2-d+d-=10000（2）从）从目标规划目标规划角度考虑角度考虑目标函数目标函数因为希望：因为希望：100X1+80X2-d+d-=100

12、00100X1+80X2 10000也就是希望：也就是希望：d-0目标函数为：目标函数为：minZ=d-（2）例）例1的目标规划模型的目标规划模型GP：Min Z=d-100X1+80X2-d+d-=100004X1+2X2 4002X1+4X2 500X1,X2,d-,d+0 d+*d-=0LP：Max Z=100X1+80X2 2X1+4X2 5004X1+2X2 400X1,X2 02.2 目标规划问题的数学模型目标规划问题的数学模型案例介绍案例介绍绝对约束与目标约束绝对约束与目标约束目标函数目标函数目标优先级目标优先级目标权因子目标权因子小节小节例例2某工厂生产某工厂生产I、II两种产

13、品，生产单位产品所需两种产品，生产单位产品所需要的原材料及占用设备台时、每天拥有的设备台要的原材料及占用设备台时、每天拥有的设备台时、原材料最大供应量、单件产品可获利润。时、原材料最大供应量、单件产品可获利润。I III II 资源拥有量资源拥有量原材料原材料(公斤公斤)2 1 11设备设备(小时小时)1 2 10利润利润(千元千元/件件)8 10 工厂在安排生产计划的考虑工厂在安排生产计划的考虑原材料情况：计划使用原材料不能超过拥有量；原材料情况：计划使用原材料不能超过拥有量；市场情况：产品市场情况：产品销售量有下降趋势，期望产销售量有下降趋势，期望产品品的产量不超过产品的产量不超过产品的产

14、量。的产量。期望充分利用设备，但不希望加班。期望充分利用设备，但不希望加班。期望达到利润计划指标期望达到利润计划指标56千元。千元。2X1+X2 11X1-X2 0X1+2X2=108X1+10X2 56（1）绝对约束与目标约束）绝对约束与目标约束2X1+X2 11X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56X1,X2,di-,di+0 di-.di+=0d1-:X1产量不足产量不足X2 部分部分d1+:X1产量超过产量超过X2 部分部分d2-:设备使用不足设备使用不足10 部部分分d2+:设备使用超过设备使用超过10 部分部分d3-:利润不

15、足利润不足56 部分部分d3+:利润超过利润超过56 部分部分设设X1，X2为产品为产品，产品，产品产量。产量。（2）目标函数市场情况：产品市场情况：产品销售量有下降趋势，期望产销售量有下降趋势，期望产品品的产量不超过产品的产量不超过产品的产量。的产量。期望充分利用设备，但尽可能不加班。期望充分利用设备，但尽可能不加班。期望达到利润计划指标期望达到利润计划指标56千元。千元。X1-X2 0X1+2X2=108X1+10X2 56X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56minZ1=d1+minZ2=d2-+d2+minZ3=d3-（3）优先

16、级）优先级在目标规划中，多个目标之间往往有主次、在目标规划中，多个目标之间往往有主次、缓急之区别缓急之区别v凡要求首先达到的目标，赋予优先级凡要求首先达到的目标，赋予优先级 p1v凡要求第二位达到的目标，赋予优先级凡要求第二位达到的目标，赋予优先级 p2v优化规则优化规则v只有完成了高级别的优化后，再考虑低级别的优只有完成了高级别的优化后，再考虑低级别的优化化v再进行低级别的优化时，不能破坏高级别以达到再进行低级别的优化时，不能破坏高级别以达到的优化值的优化值（4）权因子）权因子在同一优先级中有几个不同的偏差变量要求在同一优先级中有几个不同的偏差变量要求极小，而这几个偏差变量之间重要性又有区极

17、小，而这几个偏差变量之间重要性又有区别别可用可用“权因子权因子”来区分同一优先级中来区分同一优先级中不同偏差变量重要性不同，如不同偏差变量重要性不同，如 p p2 2（2 2d d2 2-+d+d2 2+）表示表示d d2 2-的重要程度为的重要程度为d d2 2+的两倍，的两倍，表明表明 “充分利用设备充分利用设备”的愿望的愿望“不希望加班不希望加班”的的愿望愿望权因子的数值一般需要分析者与决策者商讨权因子的数值一般需要分析者与决策者商讨确定确定例例2的多目标规划模型的多目标规划模型minZ=P1d1+P2(2d2-+d2+)+P3(d3-)2X1+X2 11X1-X2+d1-d1+=0X1

18、+2X2+d2-d2+=108X1+10X2+d3-d3+=56X1,X2,di-,di+0 小结小结1）约束条件）约束条件v硬约束硬约束(绝对约束绝对约束)v软约束软约束(目标约束目标约束)，引入，引入d-,d+2）目标优先级与权因子）目标优先级与权因子vP1 P2 PLv同一级中可以有若干个目标：同一级中可以有若干个目标：P21,P22,P23 v其重要程度用权重系数其重要程度用权重系数W21,W22,W23 表示表示目标规划的基本思想是，给定若干目标以及实现目标规划的基本思想是，给定若干目标以及实现这些目标的优先顺序，在有限的资源条件下，使这些目标的优先顺序，在有限的资源条件下，使总的偏

19、离目标值的偏差最小总的偏离目标值的偏差最小小结小结期望期望目标函数目标函数fi(X)=gi 恰好达到目标恰好达到目标minZ=f(d-+d+)fi(X)=gi 超过目标超过目标minZ=f(d-)fi(X)gi 不超过目标不超过目标minZ=f(d+)3）目标函数（准则函数）目标函数（准则函数）对目标约束：对目标约束：fi(X)+di-di+=gi小结小结目标函数的实质：目标函数的实质：求一组决策变量的满意值，求一组决策变量的满意值，使决策结果与给定目标总偏差最小。使决策结果与给定目标总偏差最小。目标函数的特点：目标函数的特点：v目标函数中只有偏差变量目标函数中只有偏差变量v目标函数总是求偏差

20、变量最小目标函数总是求偏差变量最小目标函数值的含义目标函数值的含义：vZ=0：各级目标均已达到：各级目标均已达到vZ0：部分目标未达到部分目标未达到一般模型一般模型2.3 目标规划的求解方法目标规划的求解方法序贯式算法序贯式算法 一种分解的算法，根据优先级的先后次一种分解的算法，根据优先级的先后次序，将原多目标问题分解为一系列传统的序，将原多目标问题分解为一系列传统的单目标线性规划问题，然后依次求解。单目标线性规划问题，然后依次求解。（1）序贯式算法的思路）序贯式算法的思路令令i=1，建立仅含建立仅含p1级目标的线性规划单目标级目标的线性规划单目标模型：模型：min Z 1 (D-，D+)；利

21、用单纯形法求解利用单纯形法求解 pi 级单目标规划，得到级单目标规划，得到min Z i(D-，D+)=Z*i令令i=i+1，建立仅含建立仅含 pi 级目标的线性规划单目标级目标的线性规划单目标模型：模型：min Z i=Z i(D-，D+)；同时考虑所有比同时考虑所有比 pi 高级别目标相应的约束条件高级别目标相应的约束条件；还要增加约束条件：还要增加约束条件：Z s(D-，D+)=Z*s s=1,2,i-1转第转第2步，直到考虑完所有级别目标步，直到考虑完所有级别目标第第1步：构造步：构造P1级目标构成的单目标线性级目标构成的单目标线性minZ=P1d1+P2(2d2-+d2+)+P3(d

22、3-)2X1+X2 11X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56X1,X2,di-,di+0 minZ1=d1+2X1+X2 11X1-X2+d1-d1+=0在P1级只包含d1+，因此只取含有d1+的约束条件；绝对约束绝对约束第第2步步 求解求解 P1级单目标规划级单目标规划minZ1=d1+2X1+X2 11X1-X2+d1-d1+=0计算结果：Min Z 1(D-，D+)=d1+=0 第3步：构造P2级目标构成的单目标线性上一级目标所应满足的约束条件上一级目标所应满足的约束条件本级目标所应满足本级目标所应满足的约束条件的约束条件为保证

23、优化时为保证优化时P2，不破坏，不破坏P1的的最优值而增加的约束条件最优值而增加的约束条件minZ=P1d1+P2(2d2-+d2+)+P3(d3-)2X1+X2 11X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56X1,X2,di-,di+0 minZ2=2d2-+d2+2X1+X2 11X1-X2+d1-d1+=0X1+2X2+d2-d2+=10d1+=0minZ2=2d2-+d2+2X1+X2 11X1-X2+d1-d1+=0X1+2X2+d2-d2+=10d1+=0第4步：求解 P2级单目标规划minZ2=2d2-+d2+2X1+X2 1

24、1X1-X2+d1-d1+=0X1+2X2+d2-d2+=10d1+=0计算结果：Min Z 2(D-，D+)=2d2-+d2+=0 第5步：构造P3级目标构成的单目标线性minZ3=d3-2X1+X2 11X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56d1+=02d2-+d2+=0较低级目标所应满足的约束条件较低级目标所应满足的约束条件本级目标所应满足本级目标所应满足的约束条件的约束条件为保证优化时为保证优化时P2，不破坏，不破坏P1的的最优值而增加的约束条件最优值而增加的约束条件minZ=P1d1+P2(2d2-+d2+)+P3(d3-)2

25、X1+X2 11X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56X1,X2,di-,di+0 第6步：求解 P3级单目标规划minZ3=d3-2X1+X2 11X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56d1+=02d2-+d2+=0计算结果：Min Z 3(D-，D+)=0 例例2结论结论Variable Valued3-x1x2d1-d1+d2-d2+d3+Min Z 1(D-，D+)=d1+=0，第第1优先级：优先级：期望产品期望产品的产量不超过产品的产量不超过产品的产量的产量，得到满足！

26、得到满足！Min Z 2(D-，D+)=2d2-+d2+=0，第第2优优先级：期望充分利用设备，但尽可能不加先级：期望充分利用设备，但尽可能不加班，得到满足！班，得到满足！Min Z3(D-，D+)=d3-=0，第第3优先级：优先级：期望达到利润计划指标期望达到利润计划指标56千元千元,得到得到满足满足vminZ=P1d1+P2(2d2-+d2+)+P3(d3-)=0三三 动态规划动态规划动态规划引论动态规划引论动态规划的基本原理动态规划的基本原理动态规划的基本方程动态规划的基本方程举例举例3.1 动态规划引论动态规划引论从案例说起从案例说起多阶段决策问题与动态规划多阶段决策问题与动态规划最短

27、路径问题最短路径问题从从A地到地到D地要铺设一条煤气管道地要铺设一条煤气管道,其中需其中需经过两级中间站，两点之间的连线上的数字经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，表示距离，如图所示。问应该选择什么路线，使总距离最短？使总距离最短？AB1B2C1C2C3D24333321114机器负荷问题机器负荷问题某种机器可以在高低两种不同的负荷下进行生产：某种机器可以在高低两种不同的负荷下进行生产：在高负荷下生产时在高负荷下生产时，机器的年完好率为，机器的年完好率为70%70%，且，且，产品的年产量产品的年产量=8*=8*投入生产的机器数量投入生产的机器数量在低负

28、荷下生产时在低负荷下生产时，机器的年完好率为，机器的年完好率为90%90%，且，且，产品的年产量产品的年产量=5*=5*投入生产的机器数量投入生产的机器数量假定开始生产时完好的机器数量为假定开始生产时完好的机器数量为10001000要求制定一个五年计划要求制定一个五年计划,在在每年开始时决定机器在每年开始时决定机器在两种不同负荷下生产的数量两种不同负荷下生产的数量，使五年内产品的总，使五年内产品的总产量最高。产量最高。多阶段决策问题与动态规划多阶段决策问题与动态规划以上两个问题都可以划分为多个决策阶段。以上两个问题都可以划分为多个决策阶段。多阶段决策问题：多阶段决策问题：系统运行过程中可划分为

29、若干相继系统运行过程中可划分为若干相继的的“阶段阶段”，每个阶段都要进行决策，并使整个过程，每个阶段都要进行决策，并使整个过程达到最优的一类问题。达到最优的一类问题。阶段：阶段：阶段按时间、空间或其它特征划分，且各阶段阶段按时间、空间或其它特征划分，且各阶段相互联系，某阶段的结束是下一阶段起始相互联系，某阶段的结束是下一阶段起始问题的特征问题的特征：某阶段的最优策略，而对下一阶段未必：某阶段的最优策略，而对下一阶段未必最有利。为使整个过程效果最优，必须将每阶段作为最有利。为使整个过程效果最优，必须将每阶段作为整个决策链的一环，从整体考虑。整个决策链的一环，从整体考虑。动态规划：动态规划：用来多

30、阶段决策过程优化的一种数量方法。用来多阶段决策过程优化的一种数量方法。12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策3.2 动态规划的基本原理动态规划的基本原理上世纪上世纪50年代，美国数学家贝尔曼提出解年代，美国数学家贝尔曼提出解决多阶段决策问题的决多阶段决策问题的“最优性原理最优性原理”假设采取了最优策略，得到某个系统运动假设采取了最优策略，得到某个系统运动的最优轨线，该最优轨线将的最优轨线，该最优轨线将s（起点）和（起点）和t（终点）连接。若在最优轨线上取一点（终点）连接。若在最优轨线上取一点k，则子轨线，则子轨线k-s也是最优的。也是最优的。最优策略的一部分也是最优的最

31、优策略的一部分也是最优的最优性原理的应用最优性原理的应用从从A地到地到D地要铺设一条煤气管道地要铺设一条煤气管道,其中需其中需经过两级中间站，两点之间的连线上的数字经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，表示距离，如图所示。问应该选择什么路线，使总距离最短？使总距离最短？AB1B2C1C2C3D24333321114 解：整个计算过程分三个阶段，从最后一个阶段开始。解：整个计算过程分三个阶段，从最后一个阶段开始。第一阶段（第一阶段（C D）：）：C 有三条路线到终点有三条路线到终点DAB1B2C1C2C3D24333321114DC1C2C3显然有显然有

32、f1(C1)=1 ；f1(C2)=3 ；f1(C3)=4第第k阶段从阶段从Sk 到终点最短距离到终点最短距离第二阶段（第二阶段（B1 C）：）：B1 到到C有三条路线。有三条路线。d(B1,C1)+f1(C1)3+1 f2(B1)=min d(B1,C2)+f1(C2)=min 3+3 d(B1,C3)+f1(C3)1+4 4 =min 6 =4 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B1C1 D)d(B2,C1)+f1(C1)2+1 f2(B2)=min d(B2,C2)+f1(C2)=min 3+3 d(B2,C3)+f1(C3)1+4

33、 3 =min 6 =3 5第二阶段（第二阶段（B2 C）：）：B2到到C有三条路线。有三条路线。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B2C1 D)第三阶段（第三阶段（A B）：）：A 到到B 有二条路线。有二条路线。f3(A)1=d(A,B1)f2(B1)246 f3(A)2=d(A,B2)f2(B2)437 f3(A)=min =min6,7=6d(A,B1)f2(B1)d(A,B2)f2(B2)AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为AB1C1 D)基本概念基本概念动态规划基本方程动态

34、规划基本方程动态规划的步骤动态规划的步骤基本概念基本概念阶段阶段状态与状态变量状态与状态变量决策决策策略策略状态转移方程状态转移方程指标函数和最优值函数指标函数和最优值函数（1）阶段阶段阶段（阶段（stage）把所研究的决策问题，按先后）把所研究的决策问题，按先后顺序划分为若干相互联系的决策步骤，以便顺序划分为若干相互联系的决策步骤，以便按一定的次序进行求解。按一定的次序进行求解。描述阶段的变量称描述阶段的变量称阶段变量阶段变量，常用，常用k表示。表示。AB1B2C1C2C3D24333321114DC1C2C3（2）状态与状态变量状态与状态变量状态（状态（statestate）用用sk表示阶

35、段表示阶段k的起始状态（或输入的起始状态（或输入状态）；用状态）；用sk+1表示阶段表示阶段k的结束状态（或输出状态）的结束状态（或输出状态）状态变量的取值有一定的允许集合或范围，此集合状态变量的取值有一定的允许集合或范围，此集合称为称为状态允许集合状态允许集合例如：最短路径问题中，第例如：最短路径问题中，第2阶段有二个输入状态，阶段有二个输入状态，三个输出状态。三个输出状态。AB1B2C1C2C3D24333321114DC1C2C3（3）决策与决策变量决策与决策变量决策（决策（decisiondecision）用用x xk k表示从第表示从第k阶段状态阶段状态sk到到第第k+1阶段的状态阶

36、段的状态sk+1所采取的策略，它使活动过程所采取的策略，它使活动过程从状态从状态sk转变为转变为sk+1。决策变量的取值往往在某一范围之内，此范围称为决策变量的取值往往在某一范围之内，此范围称为允许决策集合允许决策集合，可用，可用DK(sK)表示表示。AB1B2C1C2C3D24333321114C1C2C3决策：决策：x x2(B1)=B1C1允许决策集合：允许决策集合：D2(B1)=B1C1，B1C2，B1C3（4）策略策略策略：策略：是一个按顺序排列的决策组成的集合。在实是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为际问题中，可供选择的策略有一定的范围，

37、称为允允许策略集合许策略集合。从允许策略集合中找出达到最优效果。从允许策略集合中找出达到最优效果的策略称为的策略称为最优策略最优策略。12ks1x1s2x2s3skxksk+1AB1B2C1C2C3D24333321114C1C2C3策略：策略：AB1C1 D（5）状态转移方程状态转移方程状态转移方程：状态转移方程：是确定过程由一个状态到另是确定过程由一个状态到另一个状态的方程，描述了状态转移规律。一个状态的方程，描述了状态转移规律。12ks1x1s2x2s3skxksk+1AB1B2C1C2C3D24333321114C1C2C3u2(B1)=B1C1s3=T2(B1,u2)=C1讨论：状态

38、的无后效性讨论：状态的无后效性一般而言，系统某阶段的状态转移不但与系统当一般而言，系统某阶段的状态转移不但与系统当前状态和决策有关，而且还与系统的历史状态和前状态和决策有关，而且还与系统的历史状态和决策有关决策有关特殊的，系统状态的转移都只仅与前一时刻的状特殊的，系统状态的转移都只仅与前一时刻的状态有关、而与过去的状态无关，称这样的状态具态有关、而与过去的状态无关，称这样的状态具有有“无后效性无后效性”动态规划解决动态规划解决“具有无后效性具有无后效性”的多阶段决的多阶段决策问题策问题（6）指标函数和最优值函数指标函数和最优值函数指标函数指标函数又称目标函数，它又称目标函数，它用来表示系统所用

39、来表示系统所要实现的目标，是衡量策略优劣的尺度。要实现的目标，是衡量策略优劣的尺度。指标函数的含义可能是距离、利润、成本、指标函数的含义可能是距离、利润、成本、产量或资源消耗等产量或资源消耗等衡量从衡量从k阶段阶段n阶段阶段决策过程总体效果的决策过程总体效果的确确定数量函数：定数量函数：Vk,n衡量衡量第第k阶段阶段决策效果的决策效果的指标：指标：dk(sk,xk)指标函数指标函数Vk,n最优值最优值最优值函数：最优值函数：fk(sk)最短路径问题中的指标函数最短路径问题中的指标函数Vk,n第第k阶段从阶段从Sk 到终点的距离到终点的距离dk(sk,xk)从从Sk 到到xk决策所指节点的距决策

40、所指节点的距离离fk(sk)第第k阶段从阶段从Sk 到终点最短距离到终点最短距离 d(B2,C1)+f1(C1)3 f2(B2)=min d(B2,C2)+f1(C2)=min 6 =3 d(B2,C3)+f1(C3)5AB1B2C1C2C3D24333321114C1C2C3递推方程式递推方程式这样，就将原来的这样，就将原来的n阶段决策问题化为一阶段决策问题化为一系列单变量优化问题系列单变量优化问题f fk k(s(sk k)opt opt dk(sk,xk)+f+fk+1k+1(s(sk+1k+1)opt opt dk(sk,xk)+f+fk+1k+1(T(s(T(sk k,x,xk k)

41、0 xkDk3.2.2 动态规划基本方程动态规划基本方程递推方程式与状态转移方程式合称为动态递推方程式与状态转移方程式合称为动态规划基本方程规划基本方程递推方程式：递推方程式：f fk k(s(sk k)opt opt dk(sk,xk)+f+fk+1k+1(s(sk+1k+1)0 xkDk 状态转移方程式：状态转移方程式：s sk+1k+1=T(=T(s sk k,x,xk k)3.2.3 动态规划的步骤动态规划的步骤(1)将所研究问题的过程划分为将所研究问题的过程划分为n个恰当的阶段个恰当的阶段(2)正确地选择状态变量正确地选择状态变量Sk，并确定初始状态并确定初始状态S1的值的值(3)确

42、定决策变量确定决策变量xk以及各阶段的允许决策集以及各阶段的允许决策集Dk(Sk)(4)给出状态转移方程；给出状态转移方程；(5)给出满足要求的指标函数给出满足要求的指标函数Vk,n及相应的最优值函及相应的最优值函(6)写出递推方程，建立基本方程；写出递推方程，建立基本方程；(7)按照基本方程递推求解按照基本方程递推求解 举例举例：机器负荷问题：机器负荷问题某种机器可以在高低两种不同的负荷下进行生产：某种机器可以在高低两种不同的负荷下进行生产：在高负荷下进行生产时，机器的年完好率为在高负荷下进行生产时，机器的年完好率为70%70%，且，产品的年产量且，产品的年产量=8*=8*投入生产的机器数量

43、投入生产的机器数量这时在低负荷下生产时，机器的年完好率为这时在低负荷下生产时，机器的年完好率为90%90%，且，产品的年产量且，产品的年产量=5*=5*投入生产的机器数量投入生产的机器数量假定开始生产时完好的机器数量为假定开始生产时完好的机器数量为10001000要求制定一个五年计划要求制定一个五年计划,在每年开始时决定机器在在每年开始时决定机器在两种不同负荷下生产的数量，使五年内产品的总两种不同负荷下生产的数量，使五年内产品的总产量最高。产量最高。机器负荷问题机器负荷问题x1x2x5125s1s2s3s5s6V1V2V5(1)按年数划分为按年数划分为5个阶段，个阶段，k=1,2,3,4,5(

44、2)取第取第k年初完好的机器数年初完好的机器数sk为状态变量为状态变量,s1=1000(3)取第取第k年投入高负荷的机器数年投入高负荷的机器数xk为决策变量为决策变量,0 xksk(4)状态转移方程为状态转移方程为 sk+1k+0.9(sk-xkkk(5)指标函数为指标函数为Vk,5=8xj+5(sj-xj)=(5sj+3xj)解解:125s1s2s3s5s6V1V2V5基本方程基本方程(6)(6)基本方程为基本方程为 f fk k(s(sk k)max max 5sk+3xk+f+fk+1k+1(s(sk+1k+1)k=5,4,3,2,1)k=5,4,3,2,1 0 xksk f f6 6(

45、s(s6 6)0 0 根据状态转移方程：根据状态转移方程：Sk+1Skk f fk k(s(sk k)max max 5sk+3xk+f+fk+1k+1(Skk)因此基本方程因此基本方程f fk k最终可转化为最终可转化为Sk和和Xk的表达式。的表达式。当当k=5时时基本方程为基本方程为f fk k(s(sk k)max max 5sj+3xj+f+fk+1k+1(s(sk+1k+1)0 xkskf f6 6(s(s6 6)0 0当当k=5时，时，0 x5s5 f5(s5)max5s5+3x5+f6(s6)max5s5+3x5 8s5 此时此时x5*=s5Sk+1=0.9Sk-0.2Xk 当当

46、k=4时时基本方程为基本方程为f fk k(s(sk k)max max 5sj+3xj+f+fk+1k+1(s(sk+1k+1)k=5,4,3,2,1)k=5,4,3,2,1 0 xkskf f5 5(s(s5 5)8s5当当k=4时，时，0 x4s4 f4(s4)max5s4+3x4+f5(s5)max5s4+3x4+8s5 max5s4+3x444)max44 4 此时此时x4*=s4当当k=3时时基本方程为基本方程为f fk k(s(sk k)max max 5sj+3xj+f+fk+1k+1(s(sk+1k+1)k=5,4,3,2,1)k=5,4,3,2,1 0 xkskf f4 4

47、(s(s4 4)4当当k=3时，时，0 x3s3 f3(s3)max5s3+3x3+f4(s4)max5s3+3x3+4 max5s3+3x333)max33 3 此时此时x3*=s3当当k=2时时基本方程为基本方程为f fk k(s(sk k)max max 5sj+3xj+f+fk+1k+1(s(sk+1k+1)k=5,4,3,2,1)k=5,4,3,2,1 0 xkskf f3 3(s(s3 3)3当当k=2时，时，0 x2s2 f2(s2)max5s2+3x2+f3(s3)max5s2+3x2+3 max5s2+3x222)max22 2 此时此时x2*=0当当k=1时时基本方程为基本

48、方程为f fk k(s(sk k)max max 5sj+3xj+f+fk+1k+1(s(sk+1k+1)k=5,4,3,2,1)k=5,4,3,2,1 0 xkskf f2 2(s(s2 2)2当当k=1时，时，0 x1s1 f5(s5)max5s5+3x5+f6(s6)max5s5+3x5 8s5 此时此时x5*=s5 f1(s1)max5s1+3x+f2(s2)max5s1+3x1+2 max5s1+3x111)max1 1 1 此时此时x1*=0结果结果f1(1000)=23700s1=1000,x1*=0，s2=900,x2*=0s3=810,x3*=810s5=397,x5*=39

49、7s4=576,x4*=576小结小结动态规划的最优策略具有这样的性质：动态规划的最优策略具有这样的性质：一个最优策一个最优策略的子策略也是最优的略的子策略也是最优的；动态规划解决动态规划解决“具有无后效性具有无后效性”的多阶段决策问题；的多阶段决策问题；动态规划通过建立递推方程，动态规划通过建立递推方程，将原来的将原来的n阶段决策阶段决策问题化为一系列单变量优化问题问题化为一系列单变量优化问题动态规划是考察问题的一种途径，而不是一种算法；动态规划是考察问题的一种途径，而不是一种算法；动态规划模型没有统一的模式，建模时必须根据具动态规划模型没有统一的模式，建模时必须根据具体问题具体分析体问题具体分析