《优化决策理论与方法》由会员分享，可在线阅读，更多相关《优化决策理论与方法（88页珍藏版）》请在金锄头文库上搜索。
1、决策理论与方法决策理论与方法(2) 优化决策理论与方法优化决策理论与方法确定性决策确定性决策vv确定性决策确定性决策确定性决策确定性决策：指未来状态是确定的（即只有一种状：指未来状态是确定的（即只有一种状：指未来状态是确定的（即只有一种状：指未来状态是确定的（即只有一种状态）一类决策问题，每一个行动方案对应着一个确态）一类决策问题，每一个行动方案对应着一个确态）一类决策问题，每一个行动方案对应着一个确态）一类决策问题，每一个行动方案对应着一个确定的结果值，此时决策函数仅依赖于决策变量。定的结果值，此时决策函数仅依赖于决策变量。定的结果值，此时决策函数仅依赖于决策变量。定的结果值，此时决策函数仅
2、依赖于决策变量。vv特点特点特点特点：状态是确定的；决策问题变为优化问题。：状态是确定的；决策问题变为优化问题。：状态是确定的；决策问题变为优化问题。：状态是确定的；决策问题变为优化问题。vv决策的已知变量决策的已知变量决策的已知变量决策的已知变量：决策变量及其取值范围决策变量及其取值范围决策变量及其取值范围决策变量及其取值范围vv解决问题的主要理论方法解决问题的主要理论方法解决问题的主要理论方法解决问题的主要理论方法：最优化理论与方法：最优化理论与方法：最优化理论与方法：最优化理论与方法vv注：注：注：注：最优化理论与方法（数学规划）也可以求解不最优化理论与方法（数学规划）也可以求解不最优化
3、理论与方法（数学规划）也可以求解不最优化理论与方法（数学规划）也可以求解不确定性决策问题、随机性决策问题确定性决策问题、随机性决策问题确定性决策问题、随机性决策问题确定性决策问题、随机性决策问题-优化决策理论与方法确定性决策确定性决策vv优化决策方法的问题求解过程优化决策方法的问题求解过程优化决策方法的问题求解过程优化决策方法的问题求解过程辨识目标辨识目标辨识目标辨识目标C C，确定优化的标准，如：利润、时间、能量等，确定优化的标准，如：利润、时间、能量等，确定优化的标准，如：利润、时间、能量等，确定优化的标准，如：利润、时间、能量等确定影响决策目标的决策变量确定影响决策目标的决策变量确定影响
4、决策目标的决策变量确定影响决策目标的决策变量x x，形成目标函数，形成目标函数，形成目标函数，形成目标函数C=C=f f( (x x) )明确决策变量的取值范围，形成约束函数明确决策变量的取值范围，形成约束函数明确决策变量的取值范围，形成约束函数明确决策变量的取值范围，形成约束函数设计求解算法，寻找决策目标在决策变量所受限制的范设计求解算法，寻找决策目标在决策变量所受限制的范设计求解算法，寻找决策目标在决策变量所受限制的范设计求解算法，寻找决策目标在决策变量所受限制的范围内的极小化或极大化。围内的极小化或极大化。围内的极小化或极大化。围内的极小化或极大化。最优化问题的一般形式为：最优化问题的一
5、般形式为：最优化问题的一般形式为：最优化问题的一般形式为：-优化决策理论与方法优化问题分类优化问题分类vv可行点可行点可行点可行点与与与与可行域可行域可行域可行域：满足约束条件的：满足约束条件的：满足约束条件的：满足约束条件的x x称为可行点，所称为可行点，所称为可行点，所称为可行点，所有可行点的集合称为可行域，记为有可行点的集合称为可行域，记为有可行点的集合称为可行域，记为有可行点的集合称为可行域，记为S S；vv约束优化约束优化约束优化约束优化与与与与无约束优化无约束优化无约束优化无约束优化：当：当：当：当S S R Rn n时，称为约束优时，称为约束优时，称为约束优时，称为约束优化；当化
6、；当化；当化；当S=RS=Rn n时，称为无约束优化；时，称为无约束优化；时，称为无约束优化；时，称为无约束优化；vv多目标优化多目标优化多目标优化多目标优化：若：若：若：若f f是多个目标函数构成的一个向量值是多个目标函数构成的一个向量值是多个目标函数构成的一个向量值是多个目标函数构成的一个向量值函数，则称为多目标规划；函数，则称为多目标规划；函数，则称为多目标规划；函数，则称为多目标规划；vv线性规划线性规划线性规划线性规划与与与与非线性规划非线性规划非线性规划非线性规划：当：当：当：当f f, ,g g, ,h h均为线性函数时称均为线性函数时称均为线性函数时称均为线性函数时称为线性规划
7、，否则称为非线性规划。为线性规划，否则称为非线性规划。为线性规划，否则称为非线性规划。为线性规划，否则称为非线性规划。-优化决策理论与方法优化问题分类优化问题分类vv整数规划整数规划整数规划整数规划：当决策变量的取值均为整数时称为整数：当决策变量的取值均为整数时称为整数：当决策变量的取值均为整数时称为整数：当决策变量的取值均为整数时称为整数规划；若某些变量取值为整数，而另一些变量取值规划；若某些变量取值为整数，而另一些变量取值规划；若某些变量取值为整数，而另一些变量取值规划；若某些变量取值为整数，而另一些变量取值为实数，则成为混合整数规划。为实数，则成为混合整数规划。为实数，则成为混合整数规划
8、。为实数，则成为混合整数规划。vv动态规划动态规划动态规划动态规划与与与与多层规划多层规划多层规划多层规划：若决策是分成多个阶段完成：若决策是分成多个阶段完成：若决策是分成多个阶段完成：若决策是分成多个阶段完成的，前后阶段之间相互影响，则称为动态规划；若的，前后阶段之间相互影响，则称为动态规划；若的，前后阶段之间相互影响，则称为动态规划；若的，前后阶段之间相互影响，则称为动态规划；若决策是分成多个层次完成的，不同层次之间相互影决策是分成多个层次完成的，不同层次之间相互影决策是分成多个层次完成的，不同层次之间相互影决策是分成多个层次完成的，不同层次之间相互影响，则称为多层规划。响，则称为多层规划
9、。响，则称为多层规划。响，则称为多层规划。-优化决策理论与方法优化决策理论与方法优化决策理论与方法1 1、线性规划、线性规划、线性规划、线性规划2 2、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）3 3、多目标规划、多目标规划、多目标规划、多目标规划4 4、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划-优化决策理论与方法线性规划线性规划管理实例管理实例vv( (食谱问题食谱问题食谱问题食谱问题) )假设市场上有假设市场上有假设市场上有假设市场上有n n种不同的食物，第种不同的食物，第种不同的食物
10、，第种不同的食物，第j j种食物的单价种食物的单价种食物的单价种食物的单价为为为为c cj j。人体正常活动过程中需要。人体正常活动过程中需要。人体正常活动过程中需要。人体正常活动过程中需要mm种基本的营养成分，且每种基本的营养成分，且每种基本的营养成分，且每种基本的营养成分，且每人每天至少需要摄入第人每天至少需要摄入第人每天至少需要摄入第人每天至少需要摄入第i i种营养成分种营养成分种营养成分种营养成分b bi i个单位。已知第个单位。已知第个单位。已知第个单位。已知第j j种食物种食物种食物种食物中包含第中包含第中包含第中包含第i i种营养成分的量为种营养成分的量为种营养成分的量为种营养成
11、分的量为a aij ij个单位。问在满足人体基本营个单位。问在满足人体基本营个单位。问在满足人体基本营个单位。问在满足人体基本营养需求的前提下什么样的配食方案最经济？养需求的前提下什么样的配食方案最经济？养需求的前提下什么样的配食方案最经济？养需求的前提下什么样的配食方案最经济？vv设食谱中包含第设食谱中包含第设食谱中包含第设食谱中包含第j j种食物的量为种食物的量为种食物的量为种食物的量为x xj j，则：，则：，则：，则：-优化决策理论与方法线性规划线性规划标准型标准型-优化决策理论与方法线性规划线性规划单纯形算法单纯形算法vv解空间分析解空间分析解空间分析解空间分析可行域分析可行域分析可
12、行域分析可行域分析：n n维空间；第一象限；维空间；第一象限；维空间；第一象限；维空间；第一象限；mm个超平面。个超平面。个超平面。个超平面。最优解分析最优解分析最优解分析最优解分析：在端点：在端点：在端点：在端点( (或称为极点。极点向量中，至少有或称为极点。极点向量中，至少有或称为极点。极点向量中，至少有或称为极点。极点向量中，至少有n n- -mm个个个个0 0分量分量分量分量) )处取极值。处取极值。处取极值。处取极值。vv单纯形算法的基本思想单纯形算法的基本思想单纯形算法的基本思想单纯形算法的基本思想从某个极点开始获得一个可行解；从某个极点开始获得一个可行解；从某个极点开始获得一个可
13、行解；从某个极点开始获得一个可行解；判断该可行解是不是目标解。若是，算法结束；否则寻判断该可行解是不是目标解。若是，算法结束；否则寻判断该可行解是不是目标解。若是，算法结束；否则寻判断该可行解是不是目标解。若是，算法结束；否则寻找下一个极点（确定找下一个极点（确定找下一个极点（确定找下一个极点（确定入基变量入基变量入基变量入基变量和和和和出基变量出基变量出基变量出基变量），直至找到），直至找到），直至找到），直至找到目标解。目标解。目标解。目标解。-优化决策理论与方法线性规划线性规划内点算法内点算法vv19721972年，年，年，年，V. KleeV. Klee和和和和G. L. MintyG
14、. L. Minty指出指出指出指出DantzigDantzig的单纯的单纯的单纯的单纯形算法的迭代次数为形算法的迭代次数为形算法的迭代次数为形算法的迭代次数为O(2O(2n n) )，是一个指数时间算法，是一个指数时间算法，是一个指数时间算法，是一个指数时间算法，不是优良算法。那么是否存在求解线性规划问题的不是优良算法。那么是否存在求解线性规划问题的不是优良算法。那么是否存在求解线性规划问题的不是优良算法。那么是否存在求解线性规划问题的多项式时间算法？多项式时间算法？多项式时间算法？多项式时间算法？vv19841984年，年，年，年，N. KarmarkarN. Karmarkar提出了一种
15、提出了一种提出了一种提出了一种投影尺度算法投影尺度算法投影尺度算法投影尺度算法，其计算效果能够同单纯形法相比较，掀起了线性规其计算效果能够同单纯形法相比较，掀起了线性规其计算效果能够同单纯形法相比较，掀起了线性规其计算效果能够同单纯形法相比较，掀起了线性规划划划划内点算法内点算法内点算法内点算法的热潮。的热潮。的热潮。的热潮。-优化决策理论与方法线性规划线性规划内点算法内点算法vv内点算法的思想内点算法的思想内点算法的思想内点算法的思想已知线性规划问题的可行域是一个多面体，最优点在多已知线性规划问题的可行域是一个多面体，最优点在多已知线性规划问题的可行域是一个多面体，最优点在多已知线性规划问题
16、的可行域是一个多面体，最优点在多面体的某个极点取到。在给定初始可行解后，沿着什么面体的某个极点取到。在给定初始可行解后，沿着什么面体的某个极点取到。在给定初始可行解后，沿着什么面体的某个极点取到。在给定初始可行解后，沿着什么样的路径到达最优解呢？样的路径到达最优解呢？样的路径到达最优解呢？样的路径到达最优解呢？单纯形法是从某个基可行解开始，沿着多面体的边移动单纯形法是从某个基可行解开始，沿着多面体的边移动单纯形法是从某个基可行解开始，沿着多面体的边移动单纯形法是从某个基可行解开始，沿着多面体的边移动最终找到最优解。最终找到最优解。最终找到最优解。最终找到最优解。内点算法的思想是从可行域内的任意
17、一点内点算法的思想是从可行域内的任意一点内点算法的思想是从可行域内的任意一点内点算法的思想是从可行域内的任意一点( (任一可行解任一可行解任一可行解任一可行解) )出出出出发，穿越可行域的内部达到最优解。发，穿越可行域的内部达到最优解。发，穿越可行域的内部达到最优解。发，穿越可行域的内部达到最优解。 N. Karmarkar N. Karmarkar的的的的投投投投影尺度算法影尺度算法影尺度算法影尺度算法就是一种典型的内点算法。就是一种典型的内点算法。就是一种典型的内点算法。就是一种典型的内点算法。-优化决策理论与方法线性规划线性规划内点算法内点算法可行域可行域内点内点初始基可行解初始基可行解
18、基可行解基可行解目标函数目标函数目标函数最速下降方向目标函数最速下降方向-优化决策理论与方法线性规划线性规划内点算法内点算法vv投影尺度算法投影尺度算法投影尺度算法投影尺度算法如何穿过可行域的内部快速达到最优解呢？如何穿过可行域的内部快速达到最优解呢？如何穿过可行域的内部快速达到最优解呢？如何穿过可行域的内部快速达到最优解呢？KarmarkarKarmarkar发现：发现：发现：发现： (1) (1)如果一个内点位于可行域如果一个内点位于可行域如果一个内点位于可行域如果一个内点位于可行域( (多胞形、多面体多胞形、多面体多胞形、多面体多胞形、多面体) )的的的的中心，那么目标函数的最速下降方向
19、是比较好的方向；中心，那么目标函数的最速下降方向是比较好的方向；中心，那么目标函数的最速下降方向是比较好的方向；中心，那么目标函数的最速下降方向是比较好的方向；(2)(2)存在一个适当的变换，能够将可行域中给定的内点置存在一个适当的变换，能够将可行域中给定的内点置存在一个适当的变换，能够将可行域中给定的内点置存在一个适当的变换，能够将可行域中给定的内点置于变换后的可行域的中心。基于这两点，于变换后的可行域的中心。基于这两点，于变换后的可行域的中心。基于这两点，于变换后的可行域的中心。基于这两点，KarmarkarKarmarkar构构构构造了一种称为造了一种称为造了一种称为造了一种称为投影尺度
20、算法投影尺度算法投影尺度算法投影尺度算法的内点算法。的内点算法。的内点算法。的内点算法。-优化决策理论与方法线性规划线性规划内点算法内点算法X空间空间内点内点目标函数目标函数目标函数最目标函数最速下降方向速下降方向Y1空间空间中心点中心点投影尺度变换投影尺度变换1目标函数最目标函数最速下降方向速下降方向Y2空间空间中心点中心点投影尺度变换投影尺度变换2-优化决策理论与方法线性规划线性规划Matlab函数应用函数应用vvOptimization ToolBoxOptimization ToolBoxMin Min f fT Tx xS.t. S.t. AxbAxbAeqAeqx x=beq=be
21、qlblbx xubub其中：其中：其中：其中：f f, , x x, , b b, beq, lb, beq, lb和和和和ubub均为向量；均为向量；均为向量；均为向量；A A和和和和AeqAeq为矩阵。为矩阵。为矩阵。为矩阵。 x x, , f fval = val = linproglinprog( (f f,A,A,b b,Aeq,beq,lb,ub),Aeq,beq,lb,ub)-优化决策理论与方法线性规划线性规划Matlab函数应用函数应用vv例：例：例：例：max z=x1+2x2max z=x1+2x2S.t. S.t. x1+x2x1+x240402x1+x2602x1+x
22、260x1x10; x200; x20解解解解：将：将：将：将maxmax变为变为变为变为minmin，min z=-x1-2x2min z=-x1-2x2则：则：则：则：f f=-1;-2; =-1;-2; b b=40;60; lb=zeros(2,1); A=1 1;2 1=40;60; lb=zeros(2,1); A=1 1;2 1 x x, , f fval = val = linproglinprog( (f f,A,A,b b,lb),lb) x x=0;40, =0;40, f fval= -80val= -80x1x2x1+x2=402x1+x2=60Z=x1+2x2-优化
23、决策理论与方法优化决策理论与方法优化决策理论与方法1 1、线性规划、线性规划、线性规划、线性规划2 2、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）3 3、多目标规划、多目标规划、多目标规划、多目标规划4 4、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划-优化决策理论与方法无约束非线性规划无约束非线性规划标准型标准型vvMin Min f f( (x x); ); x x R Rn nvv其中其中其中其中f f：R Rn nRR是一个非线性连续函数。对于任意点是一个非线性连续函数。对于任意点是一
24、个非线性连续函数。对于任意点是一个非线性连续函数。对于任意点x x* * R Rn n, , 它是函数它是函数它是函数它是函数f f的最小点的最小点的最小点的最小点( (或局部极小点或局部极小点或局部极小点或局部极小点) )吗？吗？吗？吗？vv例如：例如：例如：例如：min min f f( (x x)=e)=ex x1 1(4(4x x1 12 2+2+2x x2 22 2+4+4x x1 1x x2 2+2+2x x2 2+1)+1)-优化决策理论与方法无约束非线性规划无约束非线性规划极小值存在条件极小值存在条件vv必要条件必要条件必要条件必要条件。设。设。设。设x x* *是是是是f f
25、( (x x) )的局部极小点，则的局部极小点，则的局部极小点，则的局部极小点，则当当当当f f( (x x) )在在在在x x* *点可微时，梯度点可微时，梯度点可微时，梯度点可微时，梯度 f f( (x x* *)=0)=0；当当当当f f( (x x) )在在在在x x* *点二阶可微时，点二阶可微时，点二阶可微时，点二阶可微时，HesseHesse矩阵矩阵矩阵矩阵2 2f f( (x x* *) )是半正定是半正定是半正定是半正定 的，的，的，的，即即即即d d R Rn n，有，有，有，有d dT T 2 2f f( (x x* *) )d d 0 0。vv充分条件充分条件充分条件充
26、分条件。设设设设f f( (x x) )在在在在x x* *点二阶可微，若梯度点二阶可微，若梯度点二阶可微，若梯度点二阶可微，若梯度 f f( (x x* *)=0)=0且且且且HesseHesse矩阵矩阵矩阵矩阵 2 2f f( (x x* *) )是正定是正定是正定是正定 的，则的，则的，则的，则x x* *是是是是f f( (x x) )的一个严的一个严的一个严的一个严格局部极小点。格局部极小点。格局部极小点。格局部极小点。vv充要条件充要条件充要条件充要条件。设。设。设。设f f( (x x) )是可微凸函数，则是可微凸函数，则是可微凸函数，则是可微凸函数，则x x* *是是是是f f
27、( (x x) )的全局的全局的全局的全局最小点，当且仅当梯度最小点，当且仅当梯度最小点，当且仅当梯度最小点，当且仅当梯度 f f( (x x* *)=0)=0。-优化决策理论与方法无约束非线性规划无约束非线性规划复习复习vv梯度矩阵梯度矩阵梯度矩阵梯度矩阵vvHesseHesse矩阵矩阵矩阵矩阵vvTaylorTaylor展开展开展开展开-优化决策理论与方法无约束非线性规划无约束非线性规划牛顿法牛顿法vv基本思想基本思想基本思想基本思想：在一个点附近，用目标函数：在一个点附近，用目标函数：在一个点附近，用目标函数：在一个点附近，用目标函数f f( (x x) )的二阶的二阶的二阶的二阶Tay
28、lorTaylor多项式近似多项式近似多项式近似多项式近似f f( (x x) )，并用该，并用该，并用该，并用该TaylorTaylor多项式的最小多项式的最小多项式的最小多项式的最小点近似点近似点近似点近似f f( (x x) )的最小点。如果近似误差比较大，那么可的最小点。如果近似误差比较大，那么可的最小点。如果近似误差比较大，那么可的最小点。如果近似误差比较大，那么可在近似最小点附近重新构造在近似最小点附近重新构造在近似最小点附近重新构造在近似最小点附近重新构造f f( (x x) )的二阶的二阶的二阶的二阶TaylorTaylor多项式多项式多项式多项式( (迭代迭代迭代迭代) )，
29、据此寻找新的近似最小点，重复以上过程，据此寻找新的近似最小点，重复以上过程，据此寻找新的近似最小点，重复以上过程，据此寻找新的近似最小点，重复以上过程直到求得满足一定精度要求的迭代点。直到求得满足一定精度要求的迭代点。直到求得满足一定精度要求的迭代点。直到求得满足一定精度要求的迭代点。-优化决策理论与方法无约束非线性规划无约束非线性规划牛顿法牛顿法vv设设设设x xk k是第是第是第是第k k次迭代结果，记次迭代结果，记次迭代结果，记次迭代结果，记g gk k= =g g( (x xk k)=)= f f( (x xk k) )；GGk k=G(=G(x xk k)=)= 2 2f f( (x
30、 xk k) )。则。则。则。则f f( (x x)=)=f f( (x xk k+ +p p) k k( (p p)=)=f f( (x xk k)+)+g g( (x xk k) )T Tp p+1/2+1/2p pT TG(G(x xk k) )p pvv由于由于由于由于 k k( (p p) )的最小点满足的最小点满足的最小点满足的最小点满足g g( (x xk k)+G()+G(x xk k) )p p=0=0，得，得，得，得p p= =x x- -x xk k=-G=-G-1-1( (x xk k) )g g( (x xk k) )vv因此，可近似得到迭代关系：因此，可近似得到迭代
31、关系：因此，可近似得到迭代关系：因此，可近似得到迭代关系：x xk k+1+1= =x xk k-G-G-1-1( (x xk k) )g g( (x xk k) )-优化决策理论与方法无约束非线性规划无约束非线性规划牛顿法牛顿法vv牛顿迭代法步骤牛顿迭代法步骤牛顿迭代法步骤牛顿迭代法步骤初始化初始化初始化初始化：给定一个初始点：给定一个初始点：给定一个初始点：给定一个初始点x x0 0以及参数以及参数以及参数以及参数e0e0；记；记；记；记k k=0=0。收敛性检验收敛性检验收敛性检验收敛性检验：计算：计算：计算：计算g g( (x xk k) )，若，若，若，若| |g g( (x xk
32、k)|e)|e，则算法终止；否则，则算法终止；否则，则算法终止；否则，则算法终止；否则计算计算计算计算G(G(x xk k) )。迭代改进迭代改进迭代改进迭代改进：计算新的迭代点：计算新的迭代点：计算新的迭代点：计算新的迭代点x xk k+1+1，即，即，即，即x xk k+1+1= =x xk k-G-G-1-1( (x xk k) )g g( (x xk k) )。k+1kk+1k。返回收敛性检验。返回收敛性检验。返回收敛性检验。返回收敛性检验。-优化决策理论与方法无约束非线性规划无约束非线性规划准牛顿法准牛顿法vv牛顿法算法的优点是收敛速度快牛顿法算法的优点是收敛速度快牛顿法算法的优点是
33、收敛速度快牛顿法算法的优点是收敛速度快( (利用了利用了利用了利用了HesseHesse矩阵矩阵矩阵矩阵) )。但使用。但使用。但使用。但使用HesseHesse矩阵的不足之处是计算量大，矩阵的不足之处是计算量大，矩阵的不足之处是计算量大，矩阵的不足之处是计算量大，HesseHesse矩阵可能非正定等，准牛顿法矩阵可能非正定等，准牛顿法矩阵可能非正定等，准牛顿法矩阵可能非正定等，准牛顿法(Quasi-(Quasi-Newton method)Newton method)是对牛顿法的改进，目前被公认是对牛顿法的改进，目前被公认是对牛顿法的改进，目前被公认是对牛顿法的改进，目前被公认为是比较有效的
34、无约束优化方法。为是比较有效的无约束优化方法。为是比较有效的无约束优化方法。为是比较有效的无约束优化方法。vv基本思想基本思想基本思想基本思想：在迭代过程中只利用目标函数：在迭代过程中只利用目标函数：在迭代过程中只利用目标函数：在迭代过程中只利用目标函数f(x)f(x)和梯度和梯度和梯度和梯度g(x)g(x)的信息，构造的信息，构造的信息，构造的信息，构造HesseHesse矩阵的近似矩阵，由此获矩阵的近似矩阵，由此获矩阵的近似矩阵，由此获矩阵的近似矩阵，由此获得一个搜索方向，生产新的迭代点。具体内容请参得一个搜索方向，生产新的迭代点。具体内容请参得一个搜索方向，生产新的迭代点。具体内容请参得
35、一个搜索方向，生产新的迭代点。具体内容请参考相关书籍。考相关书籍。考相关书籍。考相关书籍。-优化决策理论与方法无约束非线性规划无约束非线性规划Matlab函数应用函数应用vvOptimization ToolBoxOptimization ToolBoxMin Min f f( (x x) )vvMatlabMatlab提供了两个求解无约束非线性规划的函数提供了两个求解无约束非线性规划的函数提供了两个求解无约束非线性规划的函数提供了两个求解无约束非线性规划的函数x,fval = x,fval = fminuncfminunc(fun,x0)(fun,x0)x,fval = x,fval = f
36、minsearchfminsearch(fun,x0)(fun,x0)vv用法相似，算法内部的搜索策略不同。用法相似，算法内部的搜索策略不同。用法相似，算法内部的搜索策略不同。用法相似，算法内部的搜索策略不同。funfun为为为为f(x)f(x)的的的的函数形式，函数形式，函数形式，函数形式，x0x0为初始解向量。为初始解向量。为初始解向量。为初始解向量。-优化决策理论与方法无约束非线性规划无约束非线性规划Matlab函数应用函数应用vv用法用法用法用法创建一个创建一个创建一个创建一个matlabmatlab文件，如文件，如文件，如文件，如myfun.mmyfun.mfunction f =
37、myfun(x)function f = myfun(x)f = f(x);f = f(x);然后调用然后调用然后调用然后调用fminuncfminunc或或或或fminsearchfminsearch并指定初始搜索点。并指定初始搜索点。并指定初始搜索点。并指定初始搜索点。 x0=x1,x2,xn x0=x1,x2,xn x,fval = x,fval = fminuncfminunc(myfun,x0) (myfun,x0) 或或或或 x,fval = x,fval = fminsearchfminsearch(myfun,x0)(myfun,x0)-优化决策理论与方法无约束非线性规划无约束
38、非线性规划Matlab函数应用函数应用vv例例例例：min min f f( (x x)=e)=ex x1 1(4(4x x1 12 2+2+2x x2 22 2+4+4x x1 1x x2 2+2+2x x2 2+1)+1)vv解解解解：创建一个创建一个创建一个创建一个matlabmatlab文件，如文件，如文件，如文件，如myfun.mmyfun.mfunction f = myfun(x)function f = myfun(x)f =ef =exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);xp(x(1)*(4*x(1)2+2*x(2)2+
39、4*x(1)*x(2)+2*x(2)+1);调用无约束非线性规划函数调用无约束非线性规划函数调用无约束非线性规划函数调用无约束非线性规划函数 x0 = -1,1; % Starting guess x0 = -1,1; % Starting guess options = optimset(LargeScale,off); options = optimset(LargeScale,off); x,fval = x,fval = fminunc fminunc(myfun,x0,options);(myfun,x0,options);或者或者或者或者x,fval =x,fval = fmins
40、earchfminsearch(myfun,x0,options);(myfun,x0,options);-优化决策理论与方法无约束非线性规划无约束非线性规划Matlab函数应用函数应用vv fminunc fminunc结果：结果：结果：结果：x = 0.5000 -1.0000x = 0.5000 -1.0000fval = 1.0983e-015fval = 1.0983e-015iterations: 8iterations: 8algorithm: medium-scale: Quasi-Newton line algorithm: medium-scale: Quasi-Newto
41、n line searchsearchvv fminsearchfminsearch结果：结果：结果：结果：x =0.5000 -1.0000x =0.5000 -1.0000fval =5.1425e-010fval =5.1425e-010iterations: 46iterations: 46algorithm: Nelder-Mead simplex direct searchalgorithm: Nelder-Mead simplex direct search-优化决策理论与方法约束非线性规划约束非线性规划标准型标准型vv其中其中其中其中f f( (x x) )是目标函数，是目标函
42、数，是目标函数，是目标函数，g gi i( (x x) )和和和和h hj j( (x x) )为约束函数为约束函数为约束函数为约束函数( (约束约束约束约束条件条件条件条件) )。S=S=x x| |g gi i( (x x) ) 0 0 h hj j( (x x)=0)=0 为可行域。为可行域。为可行域。为可行域。vv有约束非线性规划问题有约束非线性规划问题有约束非线性规划问题有约束非线性规划问题(COP)(COP)是指是指是指是指f f( (x x), ),g gi i( (x x), ),h hj j( (x x) )至少至少至少至少有一个是非线性的，且有一个是非线性的，且有一个是非线
43、性的，且有一个是非线性的，且I I或或或或 至少有一个为非空。至少有一个为非空。至少有一个为非空。至少有一个为非空。-优化决策理论与方法约束非线性规划约束非线性规划几个概念几个概念vv积极积极积极积极(active)(active)约束约束约束约束：设：设：设：设x x0 0是是是是COPCOP问题的一个可行解，问题的一个可行解，问题的一个可行解，问题的一个可行解，则它必须满足所有约束条件。对于则它必须满足所有约束条件。对于则它必须满足所有约束条件。对于则它必须满足所有约束条件。对于g gi i( (x x0 0) ) 0 0，或者，或者，或者，或者等号成立，或者大于号成立。称等号成立的约束为
44、等号成立，或者大于号成立。称等号成立的约束为等号成立，或者大于号成立。称等号成立的约束为等号成立，或者大于号成立。称等号成立的约束为积极约束积极约束积极约束积极约束( (有效约束有效约束有效约束有效约束) )，此时，此时，此时，此时，x x0 0处于该约束条件形成处于该约束条件形成处于该约束条件形成处于该约束条件形成的可行域边界上；称大于号成立的约束为非积极的可行域边界上；称大于号成立的约束为非积极的可行域边界上；称大于号成立的约束为非积极的可行域边界上；称大于号成立的约束为非积极(inactive)(inactive)约束约束约束约束( (无效约束无效约束无效约束无效约束) )，此时，此时，
45、此时，此时，x x0 0不在该约束条件不在该约束条件不在该约束条件不在该约束条件形成的可行域边界上。显然所有形成的可行域边界上。显然所有形成的可行域边界上。显然所有形成的可行域边界上。显然所有h hj j(x(x0 0) )约束均是积极约束均是积极约束均是积极约束均是积极约束。记约束。记约束。记约束。记J=J=j j| |g gj j( (x x0 0)=0)=0 h hj j( (x x0 0)=0)=0，称为积极约束指，称为积极约束指，称为积极约束指，称为积极约束指标集。标集。标集。标集。-优化决策理论与方法约束非线性规划约束非线性规划几个概念几个概念vv可行方向可行方向可行方向可行方向。
46、设。设。设。设x x0 0为为为为COPCOP问题的任一可行解，对某一方向问题的任一可行解，对某一方向问题的任一可行解，对某一方向问题的任一可行解，对某一方向d d来来来来说，若说，若说，若说，若0 000使得对于任意使得对于任意使得对于任意使得对于任意0,0, 0 0 ，均有，均有，均有，均有x x0 0+ + d d S S，称，称，称，称d d为为为为x x0 0的一个可行方向。显然若的一个可行方向。显然若的一个可行方向。显然若的一个可行方向。显然若d d满足满足满足满足d dT T g gi i( (x x) ) 0 0，d dT T h hj j( (x x)=0)=0，则则则则d
47、d一定是可行方向。（可用一阶一定是可行方向。（可用一阶一定是可行方向。（可用一阶一定是可行方向。（可用一阶TaylorTaylor公式分析）。公式分析）。公式分析）。公式分析）。vv下降方向下降方向下降方向下降方向。设设设设x x0 0 S S，对某一方向，对某一方向，对某一方向，对某一方向d d来说，若来说，若来说，若来说，若0 000使得对于任使得对于任使得对于任使得对于任意意意意0,0, 0 0 ，均有，均有，均有，均有f f( (x x0 0+ + d d)f f( (x x0 0) )，则称，则称，则称，则称d d为为为为x x0 0点的一个下降方点的一个下降方点的一个下降方点的一个
48、下降方向。由向。由向。由向。由f f( (x x0 0+ + d d)=)=f f( (x x0 0)+)+ ( ( f f( (x x0 0) )T Td d+o(+o( ) )可知：若可知：若可知：若可知：若d d满足满足满足满足d dT T f f( (x x0 0)0)0，有，有，有，有f f( (x x0 0+ + d d)0)0，则，则，则，则x x* *为为为为COPCOP问题的一个问题的一个问题的一个问题的一个严格局部极小点。严格局部极小点。严格局部极小点。严格局部极小点。( (凸规划问题凸规划问题凸规划问题凸规划问题) )设设设设f f( (x x) )为凸函数，为凸函数，为
49、凸函数，为凸函数，g gi i( (x x) )为凹函数，为凹函数，为凹函数，为凹函数，h hj j( (x x) )为线性为线性为线性为线性函数。对于函数。对于函数。对于函数。对于x x* * S S，若，若，若，若函数函数函数函数f f( (x x), ), g gi i( (x x) )在在在在x x* *处可微，且处可微，且处可微，且处可微，且KKTKKT条件成立，则条件成立，则条件成立，则条件成立，则x x* *为为为为COPCOP问题的全局最小点。问题的全局最小点。问题的全局最小点。问题的全局最小点。-优化决策理论与方法约束非线性规划约束非线性规划极小值存在条件极小值存在条件vv二
50、阶必要条件二阶必要条件二阶必要条件二阶必要条件设设设设x x* *是是是是COPCOP问题的局部极小点且满足问题的局部极小点且满足问题的局部极小点且满足问题的局部极小点且满足KKTKKT条件。若函数条件。若函数条件。若函数条件。若函数f f( (x x), ), g gi i( (x x), ), h hj j( (x x) )在在在在x x* *处二阶可微，则必有：处二阶可微，则必有：处二阶可微，则必有：处二阶可微，则必有：d dT T xxxx2 2L(L(x x* *, , * *, , * *) )d d 0 0 其中，其中，其中，其中，L(L(x x, , , , )=)=f f(
51、(x x)- )-g g( (x x) )T T - -h h( (x x) )T T , , g g( (x x), ),h h( (x x) )分别为由分别为由分别为由分别为由g gi i( (x x) )和和和和h hj j( (x x) )构成的向量值函数，构成的向量值函数，构成的向量值函数，构成的向量值函数， , , 分别为对应于分别为对应于分别为对应于分别为对应于g g( (x x) )和和和和h h( (x x) )的拉格朗日乘子向量。的拉格朗日乘子向量。的拉格朗日乘子向量。的拉格朗日乘子向量。vv二阶充分条件二阶充分条件二阶充分条件二阶充分条件设设设设x x* *是是是是COP
52、COP问题的问题的问题的问题的KKTKKT点。点。点。点。 * *, , * *分别为对应于分别为对应于分别为对应于分别为对应于g g( (x x) )和和和和h h( (x x) )的拉格朗日乘子向量，且的拉格朗日乘子向量，且的拉格朗日乘子向量，且的拉格朗日乘子向量，且函数函数函数函数f f( (x x), ), g gi i( (x x), ), h hj j( (x x) )在在在在x x* *处二处二处二处二阶可微，若阶可微，若阶可微，若阶可微，若d dT T xxxx2 2L(L(x x* *, , * *, , * *) )d d0,0,则则则则x x* *为为为为COPCOP问题
53、的一个问题的一个问题的一个问题的一个严格局部极小点。严格局部极小点。严格局部极小点。严格局部极小点。-优化决策理论与方法约束非线性规划约束非线性规划极小值存在条件极小值存在条件vv例：例：例：例：min f(x)=xmin f(x)=x1 12 2+x+x2 22 2 S.t. x S.t. x1 1+x+x2 2 4 4 x x1 1,x,x2 2 0 0vv解：解：解：解：g g1 1(x)=x(x)=x1 1+x+x2 2-4-4 0;g0;g2 2(x)=x(x)=x1 1 0;g0;g3 3(x)=x(x)=x2 2 0 0 f(x)=2xf(x)=2x1 1,2x,2x2 2 T
54、T, , g g1 1(x)=1,1(x)=1,1T T, , g g2 2(x)=1,0(x)=1,0T T, , g g3 3(x)=0,1(x)=0,1T T, ,得得得得到：到：到：到：2x2x1 1= = 1 1+ + 2 22x2x2 2= = 1 1+ + 3 3又又又又(x(x1 1+x+x2 2-4)-4) 1 1=0=0；x x1 1 2 2=0=0；x x2 2 3 3=0=0； i i 0 0vv若若若若 1 1=0=0，则，则，则，则x x1 1=x=x2 2=0=0，与题意不符；，与题意不符；，与题意不符；，与题意不符；vv若若若若 1 100，则，则，则，则x1+
55、x2-4=0x1+x2-4=0，x10, x20x10, x20。因此有。因此有。因此有。因此有 2 2= = 3 3=0=0，所以，所以，所以，所以x1=x2=x1=x2= 1 1/2/2，得，得，得，得x1=x2=2x1=x2=2，x*=2,2x*=2,2T T为该问题的唯一为该问题的唯一为该问题的唯一为该问题的唯一KKTKKT点。点。点。点。vv根据凸规划充分条件知根据凸规划充分条件知根据凸规划充分条件知根据凸规划充分条件知x*x*为全局最小点。为全局最小点。为全局最小点。为全局最小点。-优化决策理论与方法约束非线性规划约束非线性规划可行方向法可行方向法vv上面例题介绍了通过求解上面例题
56、介绍了通过求解上面例题介绍了通过求解上面例题介绍了通过求解KKTKKT方程获得问题解的方方程获得问题解的方方程获得问题解的方方程获得问题解的方法，但法，但法，但法，但KKTKKT方程并不总是很好求解。下面介绍几种方程并不总是很好求解。下面介绍几种方程并不总是很好求解。下面介绍几种方程并不总是很好求解。下面介绍几种约束优化的求解方法：可行方向法、序列无约束化约束优化的求解方法：可行方向法、序列无约束化约束优化的求解方法：可行方向法、序列无约束化约束优化的求解方法：可行方向法、序列无约束化法和法和法和法和SQPSQP法。法。法。法。vv可行方向法的应用条件可行方向法的应用条件可行方向法的应用条件可
57、行方向法的应用条件：要求所有约束均为线性约：要求所有约束均为线性约：要求所有约束均为线性约：要求所有约束均为线性约束（称为线性约束的优化问题，束（称为线性约束的优化问题，束（称为线性约束的优化问题，束（称为线性约束的优化问题，LCOLCO）。）。）。）。vv可行方向法的基本思想可行方向法的基本思想可行方向法的基本思想可行方向法的基本思想：当某个可行方向同时也是：当某个可行方向同时也是：当某个可行方向同时也是：当某个可行方向同时也是目标函数的下降方向时，沿此方向移动一定会在满目标函数的下降方向时，沿此方向移动一定会在满目标函数的下降方向时，沿此方向移动一定会在满目标函数的下降方向时，沿此方向移动
58、一定会在满足可行性的情况下改进迭代点的目标函数值。足可行性的情况下改进迭代点的目标函数值。足可行性的情况下改进迭代点的目标函数值。足可行性的情况下改进迭代点的目标函数值。-优化决策理论与方法约束非线性规划约束非线性规划可行方向法可行方向法x1x2-优化决策理论与方法约束非线性规划约束非线性规划可行方向法可行方向法vvLCOLCO问题：问题：问题：问题： Min Min f f( (x x) ) S.t. S.t. a ai iT Tx x b bi i, , i i I I a aj jT Tx x= =b bj j, , j jvv设设设设x x0 0是是是是LCOLCO的一个可行解，若的一
59、个可行解，若的一个可行解，若的一个可行解，若d d是可行域在是可行域在是可行域在是可行域在x x0 0点的点的点的点的可可可可行方向行方向行方向行方向，则，则，则，则d d满足满足满足满足A AI( I(x x0)0)d d 0(I(0(I(x x0 0)=)=i i| |a ai iT Tx x0 0= =b bi i, ,i i I)I)，A A d d=0=0。vv设设设设x x0 0是是是是LCOLCO的一个可行解，若的一个可行解，若的一个可行解，若的一个可行解，若d d是可行域在是可行域在是可行域在是可行域在x x0 0点的点的点的点的下下下下降方向降方向降方向降方向，则，则，则，则
60、d d满足满足满足满足d dT T f f( (x x0 0)0)00，定义二次罚函数，定义二次罚函数，定义二次罚函数，定义二次罚函数Min Q(Min Q(x x, , )=)=x x1 1+ +x x2 2+(2+(2 ) )-1-1( (x x1 1- -x x2 22 2) )2 2QQx1x1=1+(=1+(x x1 1- -x x2 22 2)/ )/ =0=0QQx2x2=1-2=1-2x x2 2( (x x1 1- -x x2 22 2)/ )/ =0=0解得：解得：解得：解得：x x * *=(1/4-=(1/4- ,-1/2),-1/2)T T, Q, Q* *=-1/4
61、-=-1/4- /2/2当当当当 00时得，时得，时得，时得，x x* *=(1/4,-1/2)=(1/4,-1/2)T T, , f f* *=-1/4=-1/4-优化决策理论与方法约束非线性规划约束非线性规划序列无约束化法序列无约束化法vv对数障碍函数法对数障碍函数法对数障碍函数法对数障碍函数法：障碍函数：障碍函数：障碍函数：障碍函数：其中其中其中其中 称为障碍参数，且当称为障碍参数，且当称为障碍参数，且当称为障碍参数，且当 00时，时，时，时，P(P(x x, , ) )的极小值趋于的极小值趋于的极小值趋于的极小值趋于f(x)f(x)的极小值。的极小值。的极小值。的极小值。该方法的适用性
62、：该方法的适用性：该方法的适用性：该方法的适用性：COPCOP问题仅包含不等式约束函数，且问题仅包含不等式约束函数，且问题仅包含不等式约束函数，且问题仅包含不等式约束函数，且可行域存在内点。即可行域存在内点。即可行域存在内点。即可行域存在内点。即S S0 0=x x| |g g( (x x)0)0 -优化决策理论与方法约束非线性规划约束非线性规划序列无约束化法序列无约束化法vv例例例例：minminf f= =x x/2|/2|x x 1 1 vv解：构造对数障碍函数解：构造对数障碍函数解：构造对数障碍函数解：构造对数障碍函数P(P(x x, , )=)=x x/2-/2- ln(ln(x x
63、-1)-1)PPx x=1/2-=1/2- /( /(x x-1)=0-1)=0，得，得，得，得x x * *=1+2=1+2 ，P*=1/2+P*=1/2+ - - ln2ln2 当当当当 00时得时得时得时得x x* *=1=1，f f*=1/2*=1/2-优化决策理论与方法二次规划二次规划标准型标准型vv若有约束非线性规划的目标函数是决策变量若有约束非线性规划的目标函数是决策变量若有约束非线性规划的目标函数是决策变量若有约束非线性规划的目标函数是决策变量x x的二次的二次的二次的二次函数且所有约束均为线性约束，称此类非线性规划函数且所有约束均为线性约束，称此类非线性规划函数且所有约束均为
64、线性约束，称此类非线性规划函数且所有约束均为线性约束，称此类非线性规划问题为二次规划问题为二次规划问题为二次规划问题为二次规划(Quadratic Programming, QP)(Quadratic Programming, QP)问题。问题。问题。问题。其标准型为：其标准型为：其标准型为：其标准型为：-优化决策理论与方法二次规划二次规划标准型标准型vv其中其中其中其中Q=QQ=QT T R Rn n n n（n n阶对称方阵）；以阶对称方阵）；以阶对称方阵）；以阶对称方阵）；以a ai iT T(i (i I) I)为行为行为行为行向量的矩阵记为向量的矩阵记为向量的矩阵记为向量的矩阵记为A
65、 AI I R RIIn n；以；以；以；以a aj jT T( (j j) )为行向量的为行向量的为行向量的为行向量的矩阵记为矩阵记为矩阵记为矩阵记为A A R R n n；对应的向量记为；对应的向量记为；对应的向量记为；对应的向量记为b bI I, , b b 。若目标函。若目标函。若目标函。若目标函数的数的数的数的HesseHesse矩阵矩阵矩阵矩阵QQ是半正定是半正定是半正定是半正定( (或正定或正定或正定或正定) )的，则的，则的，则的，则QPQP问题为问题为问题为问题为( (严格严格严格严格) )凸二次规划凸二次规划凸二次规划凸二次规划(CQP)(CQP)。我们仅讨论凸二次规划问。
66、我们仅讨论凸二次规划问。我们仅讨论凸二次规划问。我们仅讨论凸二次规划问题，因为非凸二次规划的题，因为非凸二次规划的题，因为非凸二次规划的题，因为非凸二次规划的QQ存在负特征根，求解很存在负特征根，求解很存在负特征根，求解很存在负特征根，求解很困难。困难。困难。困难。-优化决策理论与方法二次规划二次规划极小点存在条件极小点存在条件vv充要条件充要条件充要条件充要条件可行点可行点可行点可行点x x* *是是是是QPQP问题的局部极小点当且仅当问题的局部极小点当且仅当问题的局部极小点当且仅当问题的局部极小点当且仅当x x* *为一个为一个为一个为一个KKTKKT点且对于任意非零可行方向点且对于任意非
67、零可行方向点且对于任意非零可行方向点且对于任意非零可行方向d d，有，有，有，有d dT TQQd d 0 0。对于凸二次规划，对于凸二次规划，对于凸二次规划，对于凸二次规划，x x* *为全局极小点当且仅当为全局极小点当且仅当为全局极小点当且仅当为全局极小点当且仅当x x* *为局部极小为局部极小为局部极小为局部极小点，当且仅当点，当且仅当点，当且仅当点，当且仅当x x* *为为为为KKTKKT点。点。点。点。二次规划的二次规划的二次规划的二次规划的KKTKKT定理形式为：定理形式为：定理形式为：定理形式为：QQx x* *+c=A+c=AI IT T * *+A+A T T * *(A(A
68、I Ix x* *- -b bI I) ) * *=0=0vv二次规划的求解本质上就是求解上述二次规划的求解本质上就是求解上述二次规划的求解本质上就是求解上述二次规划的求解本质上就是求解上述KKTKKT方程。方程。方程。方程。-优化决策理论与方法约束非线性规划约束非线性规划SQP法法vv对于非线性约束优化对于非线性约束优化对于非线性约束优化对于非线性约束优化(COP)(COP)问题，问题，问题，问题，vv若若若若x x* *是是是是COPCOP问题的一个局部最优解，则它对应一个问题的一个局部最优解，则它对应一个问题的一个局部最优解，则它对应一个问题的一个局部最优解，则它对应一个纯等式约束优化问
69、题纯等式约束优化问题纯等式约束优化问题纯等式约束优化问题-优化决策理论与方法约束非线性规划约束非线性规划SQP法法vv因此如果事先知道积极约束指标集，那么带有不等因此如果事先知道积极约束指标集，那么带有不等因此如果事先知道积极约束指标集，那么带有不等因此如果事先知道积极约束指标集，那么带有不等式约束优化问题就可以转化为纯等式约束优化问题，式约束优化问题就可以转化为纯等式约束优化问题，式约束优化问题就可以转化为纯等式约束优化问题，式约束优化问题就可以转化为纯等式约束优化问题，并可用准牛顿法求解，这就是逐次二次规划并可用准牛顿法求解，这就是逐次二次规划并可用准牛顿法求解，这就是逐次二次规划并可用准
70、牛顿法求解，这就是逐次二次规划(Sequential Quadratic Programming(Sequential Quadratic Programming，SQP)SQP)法。法。法。法。vv基本思想基本思想基本思想基本思想：在迭代点处构造一个二次规划子问题，：在迭代点处构造一个二次规划子问题，：在迭代点处构造一个二次规划子问题，：在迭代点处构造一个二次规划子问题，近似原来的约束优化问题；然后通过求解该二次规近似原来的约束优化问题；然后通过求解该二次规近似原来的约束优化问题；然后通过求解该二次规近似原来的约束优化问题；然后通过求解该二次规划子问题获得约束优化问题的一个改进迭代点；不划子
71、问题获得约束优化问题的一个改进迭代点；不划子问题获得约束优化问题的一个改进迭代点；不划子问题获得约束优化问题的一个改进迭代点；不断重复此过程，直到求出满足一定要求的迭代点。断重复此过程，直到求出满足一定要求的迭代点。断重复此过程，直到求出满足一定要求的迭代点。断重复此过程，直到求出满足一定要求的迭代点。-优化决策理论与方法约束非线性规划约束非线性规划SQP法法vv对于等式约束优化问题对于等式约束优化问题对于等式约束优化问题对于等式约束优化问题Min Min f f( (x x) )S.t. S.t. h h( (x x)=0)=0vv拉格朗日函数记为拉格朗日函数记为拉格朗日函数记为拉格朗日函数
72、记为L(x,L(x, )=)=f f( (x x)- )- T Th h( (x x) )vv则则则则 L(x,L(x, )=()=( f f( (x x)- )- h h( (x x) ) , -, -h h( (x x) )T T=0=0，显然问题的最优解，显然问题的最优解，显然问题的最优解，显然问题的最优解(x*,(x*, *)*)满足此式。满足此式。满足此式。满足此式。vv设设设设(x(xk k, , k k) )是第是第是第是第k k次迭代结果，根据牛顿法，有：次迭代结果，根据牛顿法，有：次迭代结果，根据牛顿法，有：次迭代结果，根据牛顿法，有：-优化决策理论与方法约束非线性规划约束非
73、线性规划SQP法法vv上述迭代过程等价于如下的二次规划的迭代。设给定迭代点上述迭代过程等价于如下的二次规划的迭代。设给定迭代点上述迭代过程等价于如下的二次规划的迭代。设给定迭代点上述迭代过程等价于如下的二次规划的迭代。设给定迭代点(x(xk k, , k k) )，则，则，则，则-优化决策理论与方法约束非线性规划约束非线性规划Matlab函数应用函数应用vvOptimization ToolBoxOptimization ToolBoxMin Min f f( (x x) )s.t. c(x)s.t. c(x) 0 0 ceq(x)=0 ceq(x)=0 A A x x b b Aeq Aeq
74、 x=beqx=beq lb lb x x ububvvx,fval = x,fval = fmincon fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)vvfunfun定义目标函数定义目标函数定义目标函数定义目标函数,x0,x0定义初始可行解，定义初始可行解，定义初始可行解，定义初始可行解，nonlconnonlcon定义定义定义定义c(x)c(x)和和和和ceq(x)ceq(x)。-优化决策理论与方法约束非线性规划约束非线性规划Matlab函数应用函数应用vv用法用法用法用法创建一个创建
75、一个创建一个创建一个matlabmatlab文件，如文件，如文件，如文件，如myfun.mmyfun.mfunction f = myfun(x)function f = myfun(x)f = f(x);f = f(x);创建另一个创建另一个创建另一个创建另一个matlabmatlab文件，如文件，如文件，如文件，如confun.mconfun.mfunction c, ceq = confun(x)function c, ceq = confun(x)c = c(x); c = c(x); ceq = ceq(x);ceq = ceq(x);调用调用调用调用fminconfmincon并指
76、定初始搜索点以及其他向量、矩阵。并指定初始搜索点以及其他向量、矩阵。并指定初始搜索点以及其他向量、矩阵。并指定初始搜索点以及其他向量、矩阵。x0=x1,x2,xn;A;b;Aeq;beq;lb;ub;x0=x1,x2,xn;A;b;Aeq;beq;lb;ub;x,fval=x,fval=fminconfmincon(myfun,x0,A,b,Aeq,beq,lb,ub,confun)(myfun,x0,A,b,Aeq,beq,lb,ub,confun)-优化决策理论与方法约束非线性规划约束非线性规划Matlab函数应用函数应用vv例例例例：min min f f( (x x)=e)=ex x1
77、 1(4(4x x1 12 2+2+2x x2 22 2+4+4x x1 1x x2 2+2+2x x2 2+1)+1) S.t. S.t. x x1 1x x2 2- -x x1 1- -x x2 2 -1.5-1.5 x x1 1x x2 2 -10-10vv解解解解：创建一个创建一个创建一个创建一个matlabmatlab文件，如文件，如文件，如文件，如myfun.mmyfun.mfunction f = myfun(x)function f = myfun(x)f =ef =exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);xp(x(1)*
78、(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);创建另一个创建另一个创建另一个创建另一个matlabmatlab文件，如文件，如文件，如文件，如confun.mconfun.mfunction c, ceq = confun(x)function c, ceq = confun(x)c = 1.5 + x(1)*x(2) - x(1) - x(2); -x(1)*x(2) - 10;c = 1.5 + x(1)*x(2) - x(1) - x(2); -x(1)*x(2) - 10;ceq = ;ceq = ;-优化决策理论与方法约束非线性规划约束非线性规划Mat
79、lab函数应用函数应用调用有约束非线性规划函数调用有约束非线性规划函数调用有约束非线性规划函数调用有约束非线性规划函数x0 = -1,1; % Starting guessx0 = -1,1; % Starting guessoptions = optimset(LargeScale,off);options = optimset(LargeScale,off);x,fval=fmincon(objfun,x0,confun,options)x,fval=fmincon(objfun,x0,confun,options)运行结果运行结果运行结果运行结果：x =-9.5474 1.0474x =
80、-9.5474 1.0474fval =0.0236fval =0.0236iterations: 8iterations: 8algorithm: medium-scale: SQP, Quasi-Newton, line-algorithm: medium-scale: SQP, Quasi-Newton, line-searchsearch-优化决策理论与方法二次规划二次规划Matlab函数应用函数应用vvOptimization ToolBoxOptimization ToolBoxMin 0.5Min 0.5x xT THHx x+ +f fT Tx xs.t. As.t. A x
81、x b b Aeq Aeq x=beqx=beq lb lb x x ububvvx,fval = x,fval = quadprogquadprog(H,f,A,b,Aeq,beq,lb,ub,x0)(H,f,A,b,Aeq,beq,lb,ub,x0)vvx0x0定义初始可行解定义初始可行解定义初始可行解定义初始可行解( (可选可选可选可选) )-优化决策理论与方法二次规划二次规划Matlab函数应用函数应用vv用法用法用法用法首先要将目标函数转换成二次规划标准型，从而得到首先要将目标函数转换成二次规划标准型，从而得到首先要将目标函数转换成二次规划标准型，从而得到首先要将目标函数转换成二次规
82、划标准型，从而得到HH和和和和f f两个矩阵。两个矩阵。两个矩阵。两个矩阵。调用调用调用调用quadprogquadprog并根据需要指定初始搜索点以及其他向量、并根据需要指定初始搜索点以及其他向量、并根据需要指定初始搜索点以及其他向量、并根据需要指定初始搜索点以及其他向量、矩阵。矩阵。矩阵。矩阵。x0=x1,x2,xn;A;b;Aeq;beq;lb;ub;x0=x1,x2,xn;A;b;Aeq;beq;lb;ub;x,fval=x,fval=quadprogquadprog(H,f,A,b,Aeq,beq,lb,ub,x0)(H,f,A,b,Aeq,beq,lb,ub,x0)-优化决策理论与
83、方法二次规划二次规划Matlab函数应用函数应用vv例例例例：min min f f( (x x)=1/2)=1/2x x1 12 2+ +x x2 22 2- -x x1 1x x2 2-2-2x x1 1-6-6x x2 2) ) S.t. S.t. x x1 1+ +x x2 2 2 2 - -x x1 1+2+2x x2 2 2 2 2 2x x1 1+ +x x2 2 3 3 x x1 1, , x x2 2 0 0vv解解解解：改写改写改写改写f f( (x x)=1/2()=1/2(x x1 12 2+2+2x x2 22 2- -x x1 1x x2 2- -x x1 1x x
84、2 2) )-2-2x x1 1-6-6x x2 2得：得：得：得：H=1 -1;-1 2, H=1 -1;-1 2, f f=-2;-6, x=-2;-6, x=x x1 1; ;x x2 2 ; ;表示其它矩阵或向量表示其它矩阵或向量表示其它矩阵或向量表示其它矩阵或向量A=1 1;-1 2;2 1; A=1 1;-1 2;2 1; b b=2;2;3; lb=0;0;Aeq=;beq=;ub=2;2;3; lb=0;0;Aeq=;beq=;ub=。不指派初始解。不指派初始解。不指派初始解。不指派初始解。-优化决策理论与方法二次规划二次规划Matlab函数应用函数应用调用二次规划函数调用二次
85、规划函数调用二次规划函数调用二次规划函数x,fval=x,fval=quadprogquadprog(H,f,A,b,lb)(H,f,A,b,lb)运行结果运行结果运行结果运行结果：x =0.6667;1.3333x =0.6667;1.3333fval =-8.2222fval =-8.2222iterations: 3iterations: 3algorithm: medium-scale: active-set(algorithm: medium-scale: active-set(积极约束集方法积极约束集方法积极约束集方法积极约束集方法) )-优化决策理论与方法优化决策理论与方法优化决
86、策理论与方法1 1、线性规划、线性规划、线性规划、线性规划2 2、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）3 3、多目标规划、多目标规划、多目标规划、多目标规划4 4、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划-优化决策理论与方法多目标规划多目标规划管理实例管理实例vv( (物资调度物资调度物资调度物资调度) )假设物资调度部门计划将某种物资从若干个存储假设物资调度部门计划将某种物资从若干个存储假设物资调度部门计划将某种物资从若干个存储假设物资调度部门计划将某种物资从若干个存储仓库调运到若
87、干个销售网点销售。考虑到物资的时效性和销仓库调运到若干个销售网点销售。考虑到物资的时效性和销仓库调运到若干个销售网点销售。考虑到物资的时效性和销仓库调运到若干个销售网点销售。考虑到物资的时效性和销售效益，调度部门希望物资在运输过程中尽可能快地到达目售效益，调度部门希望物资在运输过程中尽可能快地到达目售效益，调度部门希望物资在运输过程中尽可能快地到达目售效益，调度部门希望物资在运输过程中尽可能快地到达目的地；同时，考虑到运输成本，调度部门还希望物资的总运的地；同时，考虑到运输成本，调度部门还希望物资的总运的地；同时，考虑到运输成本，调度部门还希望物资的总运的地；同时，考虑到运输成本，调度部门还希
88、望物资的总运输费用最小。试建立描述物资调运过程的数学模型。输费用最小。试建立描述物资调运过程的数学模型。输费用最小。试建立描述物资调运过程的数学模型。输费用最小。试建立描述物资调运过程的数学模型。vv解解解解：设共有：设共有：设共有：设共有mm个仓库，第个仓库，第个仓库，第个仓库，第i i个仓库的物资库存量为个仓库的物资库存量为个仓库的物资库存量为个仓库的物资库存量为a ai i吨；有吨；有吨；有吨；有n n个个个个销售网点，第销售网点，第销售网点，第销售网点，第j j个销售网点的销售量为个销售网点的销售量为个销售网点的销售量为个销售网点的销售量为b bj j吨。第吨。第吨。第吨。第i i个仓
89、库到第个仓库到第个仓库到第个仓库到第j j个销售网点的距离为个销售网点的距离为个销售网点的距离为个销售网点的距离为d dij ij，单位物资的运费为，单位物资的运费为，单位物资的运费为，单位物资的运费为c cij ij。设从第。设从第。设从第。设从第i i个仓个仓个仓个仓库运到第库运到第库运到第库运到第j j个销售网点的物资量为个销售网点的物资量为个销售网点的物资量为个销售网点的物资量为x xij ij。-优化决策理论与方法多目标规划多目标规划管理实例管理实例vv决策目标：决策目标：决策目标：决策目标：运输速度最快，可用吨公里数（运输速度最快，可用吨公里数（运输速度最快，可用吨公里数（运输速度
90、最快，可用吨公里数（可观测变量可观测变量可观测变量可观测变量）最小描述。）最小描述。）最小描述。）最小描述。总吨公里数为总吨公里数为总吨公里数为总吨公里数为 i i j jd dij ijx xij ij；运输费用最小。总运输费用为运输费用最小。总运输费用为运输费用最小。总运输费用为运输费用最小。总运输费用为 i i j jc cij ijx xij ij；vv约束条件约束条件约束条件约束条件每个仓库的运出量不超过仓库的库存量：每个仓库的运出量不超过仓库的库存量：每个仓库的运出量不超过仓库的库存量：每个仓库的运出量不超过仓库的库存量： j jx xij ij a ai i；运到每个销售网点的量
91、与其销售能力相匹配：运到每个销售网点的量与其销售能力相匹配：运到每个销售网点的量与其销售能力相匹配：运到每个销售网点的量与其销售能力相匹配： i ix xij ij= =b bj j；每个仓库的运出量非负：每个仓库的运出量非负：每个仓库的运出量非负：每个仓库的运出量非负：x xij ij 0 0。-优化决策理论与方法多目标规划多目标规划管理实例管理实例vv最后得到模型：最后得到模型：最后得到模型：最后得到模型：vv模型包含模型包含模型包含模型包含2 2个目标；个目标；个目标；个目标；vvmnmn个决策变量；个决策变量；个决策变量；个决策变量；vvmn+m+nmn+m+n个约束。个约束。个约束。
92、个约束。-优化决策理论与方法多目标规划多目标规划标准型标准型vv多目标规划多目标规划多目标规划多目标规划(multi-Objective Programming,MOP)(multi-Objective Programming,MOP)就就就就是指在决策变量满足给定约束的条件下研究多个可是指在决策变量满足给定约束的条件下研究多个可是指在决策变量满足给定约束的条件下研究多个可是指在决策变量满足给定约束的条件下研究多个可数值化的目标函数同时极小化数值化的目标函数同时极小化数值化的目标函数同时极小化数值化的目标函数同时极小化( (或极大化或极大化或极大化或极大化) )的问题。的问题。的问题。的问题。
93、其一般形式如下：其一般形式如下：其一般形式如下：其一般形式如下：Min Min f f( (x x)=()=(f f1 1( (x x), ),f f2 2( (x x),),f fp p( (x x) )T T，S.t. S.t. g gi i( (x x) ) 0;0;i i I I h hj j( (x x)=0;)=0;j j。-优化决策理论与方法多目标规划多目标规划Pareto最优解最优解vv设设设设x x* *是可行域是可行域是可行域是可行域S S上的一个点，对于上的一个点，对于上的一个点，对于上的一个点，对于 x x S S，均有：，均有：，均有：，均有：f fi i( (x x
94、*)*) f fi i( (x x)( )(i i=1,=1,p p) )，称，称，称，称x x* *为为为为MOPMOP问题的绝对最优问题的绝对最优问题的绝对最优问题的绝对最优解；若不存在解；若不存在解；若不存在解；若不存在x x S S，使得，使得，使得，使得f fi i( (x x) ) f fi i( (x*x*)( )(或或或或f fi i( (x x) ) f fi i( (x*x*) ) ( (i i=1,=1,p p) )，则称，则称，则称，则称x x* *为为为为MOPMOP问题的有效解问题的有效解问题的有效解问题的有效解( (或弱有效或弱有效或弱有效或弱有效解解解解) )。
95、有效解通常也称为。有效解通常也称为。有效解通常也称为。有效解通常也称为ParetoPareto最优解。最优解。最优解。最优解。Sx1x2f(S)f(S)f2f2f1f1绝对最优解绝对最优解有效解有效解弱有效解弱有效解-优化决策理论与方法多目标规划多目标规划Pareto最优解存在条件最优解存在条件vv( (必要条件必要条件必要条件必要条件) )假设向量值函数假设向量值函数假设向量值函数假设向量值函数f f=f f1 1( (x x),),f fp p( (x x) )T T, , g g=g g1 1( (x x),),g g|I|I|( (x x) )T T, , h h=h h1 1( (x
96、 x),),h h| | | |( (x x) )T T在在在在x x* * S S处可处可处可处可微，若微，若微，若微，若x x* *是是是是MOPMOP问题的有效解或弱有效解，则存在问题的有效解或弱有效解，则存在问题的有效解或弱有效解，则存在问题的有效解或弱有效解，则存在向量向量向量向量R R+ +p p，R R+ +|I|I|，R R+ +| | | |，使得，使得，使得，使得( ( , , , , )0)0，且且且且 f f( (x x*)*) = = g g( (x x*)*) + + h h( (x x*)*) T Tg g( (x x*)=0*)=0。-优化决策理论与方法多目标规
97、划多目标规划求解方法求解方法vv直接求解多目标规划问题的有效解集是直接求解多目标规划问题的有效解集是直接求解多目标规划问题的有效解集是直接求解多目标规划问题的有效解集是NP-NP-难问题。难问题。难问题。难问题。下面介绍多目标规划问题的间接解法，基本思路都下面介绍多目标规划问题的间接解法，基本思路都下面介绍多目标规划问题的间接解法，基本思路都下面介绍多目标规划问题的间接解法，基本思路都是将多目标规划问题转化为一个或多个单目标优化是将多目标规划问题转化为一个或多个单目标优化是将多目标规划问题转化为一个或多个单目标优化是将多目标规划问题转化为一个或多个单目标优化问题。问题。问题。问题。vv基于一个
98、单目标问题的方法基于一个单目标问题的方法基于一个单目标问题的方法基于一个单目标问题的方法：将原来的多目标规划：将原来的多目标规划：将原来的多目标规划：将原来的多目标规划问题转化成一个单目标优化问题，然后利用非线性问题转化成一个单目标优化问题，然后利用非线性问题转化成一个单目标优化问题，然后利用非线性问题转化成一个单目标优化问题，然后利用非线性优化算法求解该单目标问题，所得解作为优化算法求解该单目标问题，所得解作为优化算法求解该单目标问题，所得解作为优化算法求解该单目标问题，所得解作为MOPMOP问题问题问题问题的最优解。的最优解。的最优解。的最优解。关键问题在于关键问题在于关键问题在于关键问题
99、在于：保证所构造的单目标问：保证所构造的单目标问：保证所构造的单目标问：保证所构造的单目标问题的最优解是题的最优解是题的最优解是题的最优解是MOPMOP问题的有效解或弱有效解。问题的有效解或弱有效解。问题的有效解或弱有效解。问题的有效解或弱有效解。-优化决策理论与方法多目标规划多目标规划求解方法求解方法vv线性加权和法线性加权和法线性加权和法线性加权和法：Min Min T Tf f( (x x)=)= k k k kf fk k( (x x) )，S.t. S.t. g gi i( (x x) ) 0;0;i i I I h hj j( (x x)=0;)=0;j j权重设置权重设置权重设置
100、权重设置要求要求要求要求： k k k k=1, =1, k k 0(0(k k=1,2,=1,2,p p) )。vv主要目标法：主要目标法：主要目标法：主要目标法：Min Min f f( (x x)=)=f f1 1( (x x) )，( (不妨设不妨设不妨设不妨设f f1 1( (x x) )为主要目标为主要目标为主要目标为主要目标) )S.t. S.t. g gi i( (x x) ) 0;0;i i I I h hj j( (x x)=0;)=0;j j f fk k( (x x) ) u uk k, , k k=2,=2,p pu uk k为专家经验值。为专家经验值。为专家经验值。
101、为专家经验值。-优化决策理论与方法多目标规划多目标规划求解方法求解方法vv极小化极大法极小化极大法极小化极大法极小化极大法：在目标函数：在目标函数：在目标函数：在目标函数f(x)f(x)的的的的p p个分量中，极小个分量中，极小个分量中，极小个分量中，极小化化化化f(x)f(x)的最大分量，即的最大分量，即的最大分量，即的最大分量，即minminx x S Smaxmax1 1 j j p pf fj j( (x x) )vv理想点法理想点法理想点法理想点法：分别求出：分别求出：分别求出：分别求出f f( (x x) )中每个分量中每个分量中每个分量中每个分量f fj j( (x x) )的极
102、小点的极小点的极小点的极小点f fj j0 0，得到理想点，得到理想点，得到理想点，得到理想点f f0 0=(=(f f1 10 0,f fp p0 0) )T T；然后求解单目标优化；然后求解单目标优化；然后求解单目标优化；然后求解单目标优化问题：问题：问题：问题：minminx x S S| |f f( (x x)- )-f f0 0| | 。 为范数的阶，可取为范数的阶，可取为范数的阶，可取为范数的阶，可取1 1，2 2， 。-优化决策理论与方法多目标规划多目标规划求解方法求解方法vv基于多个单目标问题的方法基于多个单目标问题的方法基于多个单目标问题的方法基于多个单目标问题的方法：将原来
103、的多目标规划：将原来的多目标规划：将原来的多目标规划：将原来的多目标规划问题转化成具有一定次序的多个单目标优化问题，问题转化成具有一定次序的多个单目标优化问题，问题转化成具有一定次序的多个单目标优化问题，问题转化成具有一定次序的多个单目标优化问题，然后依次求解这些单目标优化问题，并把最后一个然后依次求解这些单目标优化问题，并把最后一个然后依次求解这些单目标优化问题，并把最后一个然后依次求解这些单目标优化问题，并把最后一个单目标优化问题的解作为单目标优化问题的解作为单目标优化问题的解作为单目标优化问题的解作为MOPMOP问题的最优解。问题的最优解。问题的最优解。问题的最优解。关键关键关键关键问题
104、在于问题在于问题在于问题在于：保证最后一个单目标优化问题的最优解：保证最后一个单目标优化问题的最优解：保证最后一个单目标优化问题的最优解：保证最后一个单目标优化问题的最优解是是是是MOPMOP问题的有效解或弱有效解。问题的有效解或弱有效解。问题的有效解或弱有效解。问题的有效解或弱有效解。vv分层排序法分层排序法分层排序法分层排序法：将目标函数按重要度依次排序，然后：将目标函数按重要度依次排序，然后：将目标函数按重要度依次排序，然后：将目标函数按重要度依次排序，然后在前一个目标函数的最优解集中寻找下一个目标的在前一个目标函数的最优解集中寻找下一个目标的在前一个目标函数的最优解集中寻找下一个目标的
105、在前一个目标函数的最优解集中寻找下一个目标的最优解集，并把最后一个目标的最优解作为最优解集，并把最后一个目标的最优解作为最优解集，并把最后一个目标的最优解作为最优解集，并把最后一个目标的最优解作为MOPMOP问问问问题的最优解。题的最优解。题的最优解。题的最优解。-优化决策理论与方法多目标规划多目标规划求解方法求解方法1. 1.min min f f1 1( (x x) )，x x S S（不妨设（不妨设（不妨设（不妨设f f1 1( (x x) )为第一层目标），为第一层目标），为第一层目标），为第一层目标），得到最优解集得到最优解集得到最优解集得到最优解集S S1 1; ;2. 2.第第第
106、第j j层：层：层：层：min min f fj j( (x x), ),x x S Sj j-1-1，j j=2,=2,p p3. 3.最后将最后将最后将最后将S Sp p中的点作为多目标问题的最优解。中的点作为多目标问题的最优解。中的点作为多目标问题的最优解。中的点作为多目标问题的最优解。-优化决策理论与方法多目标规划多目标规划Matlab函数应用函数应用vvOptimization ToolBoxOptimization ToolBoxMin max Min max f fi i( (x x) )s.t. c(x)s.t. c(x) 0 0 ceq(x)=0 ceq(x)=0 A A x
107、 x b b Aeq Aeq x=beqx=beq lb lb x x ububvvx,fval = x,fval = fminimaxfminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)vvFunFun定义目标函数；定义目标函数；定义目标函数；定义目标函数；x0x0定义初始可行解；定义初始可行解；定义初始可行解；定义初始可行解；nonlconnonlcon定义定义定义定义c(x)c(x)和和和和ceq(x)ceq(x)。-优化决策理论与方法多目标规划多目标规划Matlab函数应用函数应用vv用
108、法用法用法用法创建一个创建一个创建一个创建一个matlabmatlab文件，如文件，如文件，如文件，如myfun.mmyfun.mfunction f = myfun(x)function f = myfun(x)f(1) = ff(1) = f1 1(x);f(2)=f(x);f(2)=f2 2(x);f(p)=f(x);f(p)=fp p(x)(x)创建另一个创建另一个创建另一个创建另一个matlabmatlab文件，如文件，如文件，如文件，如confun.mconfun.mfunction c, ceq = confun(x)function c, ceq = confun(x)c =
109、c(x); c = c(x); ceq = ceq(x);ceq = ceq(x);调用调用调用调用fminimaxfminimax并指定初始搜索点以及其他向量、矩阵。并指定初始搜索点以及其他向量、矩阵。并指定初始搜索点以及其他向量、矩阵。并指定初始搜索点以及其他向量、矩阵。x0=x1,x2,xn;A;b;Aeq;beq;lb;ub;x0=x1,x2,xn;A;b;Aeq;beq;lb;ub;x,fval=x,fval=fminimaxfminimax(myfun,x0,A,b,Aeq,beq,lb,ub,confun)(myfun,x0,A,b,Aeq,beq,lb,ub,confun)-优
110、化决策理论与方法多目标规划多目标规划Matlab函数应用函数应用vvOptimization ToolBoxOptimization ToolBoxMinMinx,x, s.t. F(x)-weights.t. F(x)-weight goalgoal c(x) c(x) 0 0 ceq(x)=0 ceq(x)=0 A A x x b b Aeq Aeq x=beqx=beq lb lb x x ububvvx,fvalx,fval= =fgoalattainfgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)(fun,x0,goa
111、l,weight,A,b,Aeq,beq,lb,ub,nonlcon)vvFunFun定义目标函数；定义目标函数；定义目标函数；定义目标函数；goalgoal为理想点；为理想点；为理想点；为理想点；x0x0定义初始可行解；定义初始可行解；定义初始可行解；定义初始可行解；nonlconnonlcon定义定义定义定义c(x)c(x)和和和和ceq(x)ceq(x)。weightweight为各目标的权重向量。为各目标的权重向量。为各目标的权重向量。为各目标的权重向量。-优化决策理论与方法多目标规划多目标规划Matlab函数应用函数应用vv用法用法用法用法创建一个创建一个创建一个创建一个matlab
112、matlab文件，如文件，如文件，如文件，如myfun.mmyfun.mfunction f = myfun(x)function f = myfun(x)f(1) = ff(1) = f1 1(x);f(2)=f(x);f(2)=f2 2(x);f(p)=f(x);f(p)=fp p(x)(x)创建另一个创建另一个创建另一个创建另一个matlabmatlab文件，如文件，如文件，如文件，如confun.mconfun.mfunction c, ceq = confun(x)function c, ceq = confun(x)c = c(x); c = c(x); ceq = ceq(x);
113、ceq = ceq(x);调用调用调用调用fgoalattainfgoalattain并设定理想点、权重向量，指定初始搜并设定理想点、权重向量，指定初始搜并设定理想点、权重向量，指定初始搜并设定理想点、权重向量，指定初始搜索点以及其他向量、矩阵。索点以及其他向量、矩阵。索点以及其他向量、矩阵。索点以及其他向量、矩阵。x0=x1,x2,xn;A;b;Aeq;beq;lb;ub;goal;weightx0=x1,x2,xn;A;b;Aeq;beq;lb;ub;goal;weightx,fval=x,fval=fgoalattainfgoalattain(myfun,x0,goal,weight,A
114、,b,Aeq,beq,(myfun,x0,goal,weight,A,b,Aeq,beq,lb,ub,confun)lb,ub,confun)-优化决策理论与方法多目标规划多目标规划Matlab函数应用函数应用vv例：例：例：例：min f1,f2,f3,f4,f5min f1,f2,f3,f4,f5f(1)= 2*x(1)2+x(2)2-48*x(1)-40*x(2)+304; f(1)= 2*x(1)2+x(2)2-48*x(1)-40*x(2)+304; f(2)= -x(1)2 - 3*x(2)2;f(2)= -x(1)2 - 3*x(2)2;f(3)= x(1) + 3*x(2) -
115、18;f(3)= x(1) + 3*x(2) -18;f(4)= -x(1)- x(2);f(4)= -x(1)- x(2);f(5)= x(1) + x(2) - 8;f(5)= x(1) + x(2) - 8;无约束。无约束。无约束。无约束。-优化决策理论与方法多目标规划多目标规划Matlab函数应用函数应用vv解解解解(1)(1)：用：用：用：用fminimaxfminimax求解。求解。求解。求解。定义定义定义定义myfun.mmyfun.m指定初始搜索点：指定初始搜索点：指定初始搜索点：指定初始搜索点：x0=0.1; 0.1x0=0.1; 0.1调用调用调用调用x,fval=x,fv
116、al=fminimaxfminimax(myfun,x0)(myfun,x0)结果：结果：结果：结果：x = 4.0000 4.0000x = 4.0000 4.0000fval = 0.0000 -64.0000 -2.0000 -8.0000 -0.0000fval = 0.0000 -64.0000 -2.0000 -8.0000 -0.0000iterations: 7iterations: 7algorithm: minimax SQP, Quasi-Newton, line_searchalgorithm: minimax SQP, Quasi-Newton, line_searc
117、h-优化决策理论与方法多目标规划多目标规划Matlab函数应用函数应用vv解解解解(2)(2)：用：用：用：用fgoalattainfgoalattain求解。求解。求解。求解。定义定义定义定义myfun.mmyfun.m指定初始搜索点：指定初始搜索点：指定初始搜索点：指定初始搜索点：x0=0.1; 0.1x0=0.1; 0.1指定理想点：指定理想点：指定理想点：指定理想点：goal=1 -60 -5 -10 -1goal=1 -60 -5 -10 -1指定权重：指定权重：指定权重：指定权重：weight=abs(goal)weight=abs(goal)调用调用调用调用x,fval=x,fv
118、al=fgoalattainfgoalattain(myfun,x0,goal,weight)(myfun,x0,goal,weight)结果：结果：结果：结果：x =3.9798 3.9596x =3.9798 3.9596fval =1.9395 -62.8754 -2.1412 -7.9395 -0.0605fval =1.9395 -62.8754 -2.1412 -7.9395 -0.0605iterations: 7iterations: 7algorithm: goal attainment SQP, Quasi-Newton, algorithm: goal attainmen
119、t SQP, Quasi-Newton, line_searchline_search-优化决策理论与方法优化决策理论与方法优化决策理论与方法1 1、线性规划、线性规划、线性规划、线性规划2 2、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）、非线性规划（约束和非约束）3 3、多目标规划、多目标规划、多目标规划、多目标规划4 4、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划、组合优化与整数规划-优化决策理论与方法组合优化组合优化基本概念基本概念vv组合优化问题组合优化问题组合优化问题组合优化问题是指从一个有限的可行解集中寻找使某个性能是指从一个
120、有限的可行解集中寻找使某个性能是指从一个有限的可行解集中寻找使某个性能是指从一个有限的可行解集中寻找使某个性能函数取极值的最优解。函数取极值的最优解。函数取极值的最优解。函数取极值的最优解。vv给定一个有限集给定一个有限集给定一个有限集给定一个有限集N=1,2,nN=1,2,n和权函数和权函数和权函数和权函数c:NRc:NR。记。记。记。记N N的某些的某些的某些的某些子集的集合为子集的集合为子集的集合为子集的集合为F F，则组合优化问题就是从，则组合优化问题就是从，则组合优化问题就是从，则组合优化问题就是从F F中找到一个具有最中找到一个具有最中找到一个具有最中找到一个具有最小权重的子集。小
121、权重的子集。小权重的子集。小权重的子集。vv已经证明：求解组合优化问题的最优解是已经证明：求解组合优化问题的最优解是已经证明：求解组合优化问题的最优解是已经证明：求解组合优化问题的最优解是NP-NP-难的。设计各难的。设计各难的。设计各难的。设计各类类类类贪婪算法贪婪算法贪婪算法贪婪算法是求解组合优化问题常用的思路。是求解组合优化问题常用的思路。是求解组合优化问题常用的思路。是求解组合优化问题常用的思路。-优化决策理论与方法组合优化组合优化基本概念基本概念vv常见的组合优化问题：常见的组合优化问题：常见的组合优化问题：常见的组合优化问题：最短路问题最短路问题最短路问题最短路问题：给定一定的路长
122、分布，确定从某个地点到：给定一定的路长分布，确定从某个地点到：给定一定的路长分布，确定从某个地点到：给定一定的路长分布，确定从某个地点到另一个地点使路长最短的路径。另一个地点使路长最短的路径。另一个地点使路长最短的路径。另一个地点使路长最短的路径。(TSP(TSP问题问题问题问题) )最大流问题最大流问题最大流问题最大流问题：在一个有容量限制的网络中，如何使得从：在一个有容量限制的网络中，如何使得从：在一个有容量限制的网络中，如何使得从：在一个有容量限制的网络中，如何使得从一个顶点到另一个顶点的流量达到最大？一个顶点到另一个顶点的流量达到最大？一个顶点到另一个顶点的流量达到最大？一个顶点到另一
123、个顶点的流量达到最大？装箱问题装箱问题装箱问题装箱问题：如何将一定规格的物品装到箱子中，使得占：如何将一定规格的物品装到箱子中，使得占：如何将一定规格的物品装到箱子中，使得占：如何将一定规格的物品装到箱子中，使得占用箱子的个数最少？用箱子的个数最少？用箱子的个数最少？用箱子的个数最少？背包问题背包问题背包问题背包问题：如何挑选一些价值不同、尺寸有别的物品放：如何挑选一些价值不同、尺寸有别的物品放：如何挑选一些价值不同、尺寸有别的物品放：如何挑选一些价值不同、尺寸有别的物品放到一个有限大的背包中，使得背包内的物品价值总量最到一个有限大的背包中，使得背包内的物品价值总量最到一个有限大的背包中，使得
124、背包内的物品价值总量最到一个有限大的背包中，使得背包内的物品价值总量最大？大？大？大？-优化决策理论与方法组合优化组合优化最短路问题最短路问题vv给定一个网络给定一个网络给定一个网络给定一个网络N=(V, E, N=(V, E, w w) )，其中，其中，其中，其中w w为权函数，最短路问题是为权函数，最短路问题是为权函数，最短路问题是为权函数，最短路问题是指对于两个不同的顶点指对于两个不同的顶点指对于两个不同的顶点指对于两个不同的顶点s,ts,t V V，寻找一条从，寻找一条从，寻找一条从，寻找一条从s s到到到到t t的路，使得的路，使得的路，使得的路，使得路上所有弧的权和最小路上所有弧的
125、权和最小路上所有弧的权和最小路上所有弧的权和最小( (权可看作弧长权可看作弧长权可看作弧长权可看作弧长) )。vv关联矩阵：关联矩阵：关联矩阵：关联矩阵：A=(A=(a aij ij) )|V|E|V|E|。a aij ij=1(=1(v vi i为为为为e ej j的起点的起点的起点的起点) )；a aij ij=-1(=-1(v vi i为为为为e ej j的的的的终点终点终点终点) )；a aij ij=0(=0(其他情形其他情形其他情形其他情形) )。引入。引入。引入。引入0-10-1整型变量整型变量整型变量整型变量x xj j( (e ej j E)E)，记，记，记，记x x=(=(
126、x x1 1, ,x x2 2,.,.,x x|E|E|) )T T。则最短路径问题可表示成如下的。则最短路径问题可表示成如下的。则最短路径问题可表示成如下的。则最短路径问题可表示成如下的0-10-1整数规整数规整数规整数规划问题：划问题：划问题：划问题：min min w wT Tx xs.t. s.t. a as sT Tx x=1=1 a at tT Tx x=-1=-1 a ai iT Tx x=0, =0, i i s s, ,t t x x 0 0-优化决策理论与方法组合优化组合优化最短路问题最短路问题vv例例例例：考虑如图所示的网络，定义权函数：考虑如图所示的网络，定义权函数：考
127、虑如图所示的网络，定义权函数：考虑如图所示的网络，定义权函数w=(1,2,2,3,1)w=(1,2,2,3,1)T T。试确。试确。试确。试确定从定从定从定从s s到到到到t t点的最短路径。点的最短路径。点的最短路径。点的最短路径。vv解解解解：a as s=(1 1 0 0 0)=(1 1 0 0 0)T T；a at t=(0 0 0 -1 -1)T;=(0 0 0 -1 -1)T;a aa a=(-1 0 1 1 0)=(-1 0 1 1 0)T T; ; a ab b=(0 -1 =(0 -1 -1 0 1)-1 0 1)T T，得到以下规划方程：，得到以下规划方程：，得到以下规划方
128、程：，得到以下规划方程：min xmin x1 1+2x+2x2 2+2x+2x3 3+3x+3x4 4+x+x5 5s.t. xs.t. x1 1+x+x2 2=1=1 -x -x4 4-x-x5 5=-1=-1 -x -x1 1+x+x3 3+x+x4 4=0=0 -x -x2 2-x-x3 3+x+x5 5=0=0 x x1 1,x ,x2 2,x ,x3 3,x ,x4 4,x ,x5 5 0 0调用函数调用函数调用函数调用函数linproglinprog(w,Aeq,beq,lb)(w,Aeq,beq,lb)得得得得x=0 1 0 0 1x=0 1 0 0 1T T表明从表明从表明从
129、表明从s s出发经过第出发经过第出发经过第出发经过第2 2、5 5条边到达条边到达条边到达条边到达t t点最短。点最短。点最短。点最短。stabe1e2e3e5e4-优化决策理论与方法整数规划整数规划标准型标准型vv整数规划是一类特殊的组合优化问题。线性整数规划是一类特殊的组合优化问题。线性整数规划是一类特殊的组合优化问题。线性整数规划是一类特殊的组合优化问题。线性( (混合混合混合混合) )整数规划问题整数规划问题整数规划问题整数规划问题是指在等式或不等式的线性约束下，是指在等式或不等式的线性约束下，是指在等式或不等式的线性约束下，是指在等式或不等式的线性约束下，极大化极大化极大化极大化(
130、(或极小化或极小化或极小化或极小化) )某个线性函数，其中要求某些变某个线性函数，其中要求某些变某个线性函数，其中要求某些变某个线性函数，其中要求某些变量必须取整数。量必须取整数。量必须取整数。量必须取整数。vv线性混合整数规划线性混合整数规划线性混合整数规划线性混合整数规划(MILP)(MILP)：max cmax cT Tx x+ +h hT Ty y|A|Ax x+G+Gy y b b, , x x Z Z+ +n n, , y y R R+ +p p x x, ,y y为决策变量向量，其中为决策变量向量，其中为决策变量向量，其中为决策变量向量，其中x x包含包含包含包含n n个整数变量
131、，个整数变量，个整数变量，个整数变量，y y包含包含包含包含p p个个个个实数变量；实数变量；实数变量；实数变量；c c为为为为n n维向量；维向量；维向量；维向量；h h为为为为p p维向量；维向量；维向量；维向量；A A为为为为mnmn阶矩阵，阶矩阵，阶矩阵，阶矩阵，GG为为为为mpmp阶矩阵。阶矩阵。阶矩阵。阶矩阵。-优化决策理论与方法整数规划整数规划标准型标准型vv整数规划的可行域整数规划的可行域整数规划的可行域整数规划的可行域：S=(x,y)|AS=(x,y)|Ax x+G+Gy y b b, , x x Z Z+ +n n, , y y R R+ +p p vv例：例：例：例：P=
132、P=x x Z Z1 1RR1 1|- |-x x1 1+ +x x2 2 1/2, 31/2, 3x x1 1+4+4x x2 2 3, 3, x x2 2 0 0 x1x2-优化决策理论与方法整数规划整数规划解的特点解的特点vv从整数规划的可行域分析可知，整数规划的解与其从整数规划的可行域分析可知，整数规划的解与其从整数规划的可行域分析可知，整数规划的解与其从整数规划的可行域分析可知，整数规划的解与其松弛问题松弛问题松弛问题松弛问题( (整数规划问题的所有变量取值不受整数限整数规划问题的所有变量取值不受整数限整数规划问题的所有变量取值不受整数限整数规划问题的所有变量取值不受整数限制时的线性
133、规划问题制时的线性规划问题制时的线性规划问题制时的线性规划问题) )既有密切的联系，又有本质的既有密切的联系，又有本质的既有密切的联系，又有本质的既有密切的联系，又有本质的区别。区别。区别。区别。vv整数规划问题的可行解一定是松弛问题的可行解，整数规划问题的可行解一定是松弛问题的可行解，整数规划问题的可行解一定是松弛问题的可行解，整数规划问题的可行解一定是松弛问题的可行解，但反之不一定。所以整数规划问题的最优解不会优但反之不一定。所以整数规划问题的最优解不会优但反之不一定。所以整数规划问题的最优解不会优但反之不一定。所以整数规划问题的最优解不会优于其松弛问题的最优解。于其松弛问题的最优解。于其
134、松弛问题的最优解。于其松弛问题的最优解。vv求解方法：求解方法：求解方法：求解方法：GomoryGomory割平面法、分支定界法、分解割平面法、分支定界法、分解割平面法、分支定界法、分解割平面法、分支定界法、分解算法。算法。算法。算法。-优化决策理论与方法整数规划整数规划Matlab函数应用函数应用vvOptimization ToolBoxOptimization ToolBoxMin Min f f x xs.t. As.t. A x x b b Aeq Aeq x=beqx=beq x x：0-10-1vvx,fval =x,fval =bintprogbintprog(f, A, b, Aeq, beq, x0)(f, A, b, Aeq, beq, x0)vvx0x0定义初始可行解定义初始可行解定义初始可行解定义初始可行解( (可选可选可选可选) )；bintprogbintprog仅适合求解仅适合求解仅适合求解仅适合求解0-10-1整数规划问题。整数规划问题。整数规划问题。整数规划问题。-优化决策理论与方法
