第02讲 优化决策理论与方法

决策理论与方法(2)——优化决策理论与方法合肥工业大学管理学院2019年8月29日2019年8月29日3时22分决策理论与方法-优化决策理论与方法确定性决策确定性决策：指未来状态是确定的（即只有一种状态）一类决策问题，每一个行动方案对应着一个确定的结果值，此时决策函数仅依赖于决策变量。特点：状态是确定的；决策问题变为优化问题。决策的已知变量：决策变量及其取值范围解决问题的主要理论方法：最优化理论与方法注：最优化理论与方法（数学规划）也可以求解不确定性决策问题、随机性决策问题2019年8月29日3时22分决策理论与方法-优化决策理论与方法确定性决策优化决策方法的问题求解过程辨识目标C，确定优化的标准，如：利润、时间、能量等确定影响决策目标的决策变量x，形成目标函数C=f(x)明确决策变量的取值范围，形成约束函数设计求解算法，寻找决策目标在决策变量所受限制的范围内的极小化或极大化。最优化问题的一般形式为：jxhIixgtsxfjiRxn,0)(,,0)(..)(min2019年8月29日3时22分决策理论与方法-优化决策理论与方法优化问题分类可行点与可行域：满足约束条件的x称为可行点，所有可行点的集合称为可行域，记为S；约束优化与无约束优化：当SRn时，称为约束优化；当S=Rn时，称为无约束优化；多目标优化：若f是多个目标函数构成的一个向量值函数，则称为多目标规划；线性规划与非线性规划：当f,g,h均为线性函数时称为线性规划，否则称为非线性规划。2019年8月29日3时22分决策理论与方法-优化决策理论与方法优化问题分类整数规划：当决策变量的取值均为整数时称为整数规划；若某些变量取值为整数，而另一些变量取值为实数，则成为混合整数规划。动态规划与多层规划：若决策是分成多个阶段完成的，前后阶段之间相互影响，则称为动态规划；若决策是分成多个层次完成的，不同层次之间相互影响，则称为多层规划。2019年8月29日3时22分决策理论与方法-优化决策理论与方法优化决策理论与方法1、线性规划2、非线性规划（约束和非约束）3、多目标规划4、组合优化与整数规划2019年8月29日3时22分决策理论与方法-优化决策理论与方法线性规划—管理实例(食谱问题)假设市场上有n种不同的食物，第j种食物的单价为cj。人体正常活动过程中需要m种基本的营养成分，且每人每天至少需要摄入第i种营养成分bi个单位。已知第j种食物中包含第i种营养成分的量为aij个单位。问在满足人体基本营养需求的前提下什么样的配食方案最经济？设食谱中包含第j种食物的量为xj，则：njxmibaxtscxjinjijjnjjj,,2,10,,2,1..min112019年8月29日3时22分决策理论与方法-优化决策理论与方法线性规划—标准型为右端项。为技术系数，为目标函数，为费用（价格）系数，为决策变量，定：在标准形式中，我们约记可行域其中ibijaxTcjcjxxbAxnxSnxcmbnmAxbAxtsxTc0,.,,,0,..min2019年8月29日3时22分决策理论与方法-优化决策理论与方法线性规划—单纯形算法解空间分析可行域分析：n维空间；第一象限；m个超平面。最优解分析：在端点(或称为极点。极点向量中，至少有n-m个0分量)处取极值。单纯形算法的基本思想从某个极点开始获得一个可行解；判断该可行解是不是目标解。若是，算法结束；否则寻找下一个极点（确定入基变量和出基变量），直至找到目标解。2019年8月29日3时22分决策理论与方法-优化决策理论与方法线性规划—内点算法1972年，V.Klee和G.L.Minty指出Dantzig的单纯形算法的迭代次数为O(2n)，是一个指数时间算法，不是优良算法。那么是否存在求解线性规划问题的多项式时间算法？1984年，N.Karmarkar提出了一种投影尺度算法，其计算效果能够同单纯形法相比较，掀起了线性规划内点算法的热潮。2019年8月29日3时22分决策理论与方法-优化决策理论与方法线性规划—内点算法内点算法的思想已知线性规划问题的可行域是一个多面体，最优点在多面体的某个极点取到。在给定初始可行解后，沿着什么样的路径到达最优解呢？单纯形法是从某个基可行解开始，沿着多面体的边移动最终找到最优解。内点算法的思想是从可行域内的任意一点(任一可行解)出发，穿越可行域的内部达到最优解。N.Karmarkar的投影尺度算法就是一种典型的内点算法。2019年8月29日3时22分决策理论与方法-优化决策理论与方法线性规划—内点算法可行域内点初始基可行解基可行解目标函数目标函数最速下降方向2019年8月29日3时22分决策理论与方法-优化决策理论与方法线性规划—内点算法投影尺度算法如何穿过可行域的内部快速达到最优解呢？Karmarkar发现：(1)如果一个内点位于可行域(多胞形、多面体)的中心，那么目标函数的最速下降方向是比较好的方向；(2)存在一个适当的变换，能够将可行域中给定的内点置于变换后的可行域的中心。基于这两点，Karmarkar构造了一种称为投影尺度算法的内点算法。2019年8月29日3时22分决策理论与方法-优化决策理论与方法线性规划—内点算法X空间内点目标函数目标函数最速下降方向Y1空间中心点投影尺度变换1目标函数最速下降方向Y2空间中心点2019年8月29日3时22分决策理论与方法-优化决策理论与方法线性规划—Matlab函数应用OptimizationToolBoxMinfTxS.t.A·x≤bAeq·x=beqlb≤x≤ub其中：f,x,b,beq,lb和ub均为向量；A和Aeq为矩阵。[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)2019年8月29日3时22分决策理论与方法-优化决策理论与方法线性规划—Matlab函数应用例：maxz=x1+2x2S.t.x1+x2≤402x1+x2≤60x1≥0;x2≥0解：将max变为min，min–z=-x1-2x2则：f=[-1;-2];b=[40;60];lb=zeros(2,1);A=[11;21][x,fval]=linprog(f,A,b,[],[],lb)x=[0;40],fval=-80x1x2x1+x2=402x1+x2=60Z=x1+2x22019年8月29日3时22分决策理论与方法-优化决策理论与方法优化决策理论与方法1、线性规划2、非线性规划（约束和非约束）3、多目标规划4、组合优化与整数规划2019年8月29日3时22分决策理论与方法-优化决策理论与方法无约束非线性规划—标准型Minf(x);xRn其中f：Rn→R是一个非线性连续函数。对于任意点x*Rn,它是函数f的最小点(或局部极小点)吗？例如：minf(x)=ex1(4x12+2x22+4x1x2+2x2+1)2019年8月29日3时22分决策理论与方法-优化决策理论与方法无约束非线性规划—极小值存在条件必要条件。设x*是f(x)的局部极小点，则当f(x)在x*点可微时，梯度f(x*)=0；当f(x)在x*点二阶可微时，Hesse矩阵▽2f(x*)是半正定的，即dRn，有dT2f(x*)d0。充分条件。设f(x)在x*点二阶可微，若梯度f(x*)=0且Hesse矩阵2f(x*)是正定的，则x*是f(x)的一个严格局部极小点。充要条件。设f(x)是可微凸函数，则x*是f(x)的全局最小点，当且仅当梯度f(x*)=0。2019年8月29日3时22分决策理论与方法-优化决策理论与方法无约束非线性规划—复习梯度矩阵nxfxfxfxf21)(22221222222122122122122)(nnnnnxfxxfxxfxxfxfxxfxxfxxfxfxfHesse矩阵Taylor展开),(||||))(()(21)()()()(**2***2****xxxxxxxxfxxxxxfxfxfTT2019年8月29日3时22分决策理论与方法-优化决策理论与方法无约束非线性规划—牛顿法基本思想：在一个点附近，用目标函数f(x)的二阶Taylor多项式近似f(x)，并用该Taylor多项式的最小点近似f(x)的最小点。如果近似误差比较大，那么可在近似最小点附近重新构造f(x)的二阶Taylor多项式(迭代)，据此寻找新的近似最小点，重复以上过程直到求得满足一定精度要求的迭代点。2019年8月29日3时22分决策理论与方法-优化决策理论与方法无约束非线性规划—牛顿法设xk是第k次迭代结果，记gk=g(xk)=f(xk)；Gk=G(xk)=2f(xk)。则f(x)=f(xk+p)≈k(p)=f(xk)+g(xk)Tp+1/2pTG(xk)p由于k(p)的最小点满足g(xk)+G(xk)p=0，得p=x-xk=-G-1(xk)g(xk)因此，可近似得到迭代关系：xk+1=xk-G-1(xk)g(xk)2019年8月29日3时22分决策理论与方法-优化决策理论与方法无约束非线性规划—牛顿法牛顿迭代法步骤初始化：给定一个初始点x0以及参数e0；记k=0。收敛性检验：计算g(xk)，若||g(xk)||≤e，则算法终止；否则计算G(xk)。迭代改进：计算新的迭代点xk+1，即xk+1=xk-G-1(xk)g(xk)。k+1→k。返回收敛性检验。2019年8月29日3时22分决策理论与方法-优化决策理论与方法无约束非线性规划—准牛顿法牛顿法算法的优点是收敛速度快(利用了Hesse矩阵)。但使用Hesse矩阵的不足之处是计算量大，Hesse矩阵可能非正定等，准牛顿法(Quasi-Newtonmethod)是对牛顿法的改进，目前被公认为是比较有效的无约束优化方法。基本思想：在迭代过程中只利用目标函数f(x)和梯度g(x)的信息，构造Hesse矩阵的近似矩阵，由此获得一个搜索方向，生产新的迭代点。具体内容请参考相关书籍。2019年8月29日3时22分决策理论与方法-优化决策理论与方法无约束非线性规划—Matlab函数应用OptimizationToolBoxMinf(x)Matlab提供了两个求解无约束非线性规划的函数[x,fval]=fminunc(fun,x0)[x,fval]=fminsearch(fun,x0)用法相似，算法内部的搜索策略不同。fun为f(x)的函数形式，x0为初始解向量。2019年8月29日3时22分决策理论与方法-优化决策理论与方法无约束非线性规划—Matlab函数应用用法创建一个matlab文件，如myfun.mfunctionf=myfun(x)f=f(x);然后调用fminunc或fminsearch并指定初始搜索点。x0=[x1,x2,…,xn][x,fval]=fminunc(@myfun,x0)或[x,fval]=fminsearch(@myfun,x0)2019年8月29日3时22分决策理论与方法-优化决策理论与方法无约束非线性规划—Matlab函数应用例：minf(x)=ex1(4x12+2x22+4x1x2+2x2+1)解：创建一个matlab文件，如myfun.mfunctionf=myfun(x)f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);调用无约束非线性规划函数x0=[-1,1];%Startingguessoptions=optimset('LargeScale','off');[x,fval]=fminunc(@myfun,x0,options);或者[x,fval]=fminse