最优化理论小结

学号：20131221447姓名：施林红最优化理论方法小结转眼间研一的第一学期就要结束了，经过三个月的学习，我对《最优化理论与方法》这门课也有了一定的认识与了解。下面是我对这门课的小结。1.线性规划线性规划的规范形式如下0,,..max,21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz（1）称以下形式为标准形式0,,..max,21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz（2）其中z为目标函数，jx（j=1,2,……，n）为决策变量,jc为价值系数，ib（j=1,2,……，m）为右端项，ija为约束系数。从线性规划的标准形式可知，其具有四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。1.1单纯形算法单纯形算法的基本思想是有选择的取基本可行解，即从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。下面是以我自己的理解对单纯形算法的步骤所做的归纳：1）列出初始单纯形表2）算出检验数j。3）确定旋入、旋出变量。先确定旋入变量，旋入变量是取检验数最大所在的那一列对应的决策变量；旋出变量是将单纯形表中b所在的那一列的各项值除以旋入变量所在列的对应值（必须大于0）即得到，取最小的值，其对应的决策变量作为旋出变量。4）对),,,(21nxxxb组成的矩阵作初等行变换，知道选入变量之前所在的的列变为旋出变量之前所在的列对应的值即可。5）如此反复迭代，直到检验数全为非正则停止。6）从表中得到最优解x和最优目标值z。1.2对偶单纯形算法对偶单纯性算法的基本思想是从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数均非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负分量，如果有小于零的分量则进行迭代，求另一基本解，此基本解对应着另一个基本可行解（检验数非正）。如果得到的基本解的分量均非负，则该基本解为最优解。下面是以我自己的理解对单纯形算法的步骤所做的归纳：1）建立初始对偶单纯形表，此表要求检验数行各元素一定非正，原规划的基本可行解可以有小于零的分量。2）若基本解的所有分量皆非负，则得到原规划的最优解，停止计算。若基本解有小于零的的分量ib，且ib所在行的各系数ija0，则原规划没有可行解；若ib所在行的各系数存在ija0，则确定最小的rx为出基变量，并计算rkkrjrjjaaa0min确定kx为进基变量。3）如此反复迭代，直至基本解非负，检验数全为非正则停止。1.3灵敏度分析线性规划模型中的参数常常是估计量，所以在对问题求解之后，需要对这些估计量进行分析，以决定是否需要对所求解进行调整。周围环境的变化也会使参数发生变化，这些参数的变化很可能影响以求得的最优值，因此在解决实际问题时，一般要研究最优解对数据变化反应的程度，以使决策者全面的考虑问题，这就是灵敏度分析所要研究的一部分内容。灵敏度分析考虑价值系数，资源系数，约束条件系数，增加新变量，增加约束条件等的变化对其的影响。价值系数的变化有两种情况，一是非基变量系数的变化，二是基变量系数的变化。非基变量系数的变化。当非基变量系数kc变化kc时，只影响与kc有关的一个检验数k的变化，对其它的j没有影响，变化后的检验数kkkc，变化后的某一价值系数为kckc-k，kc-k为kc的变化上限。当kc变化超过此上限时，最优解将发生变化，应求出新检验数k的值，取kx为进基变量，继续迭代求新的解。基变量系数lc变化lc时，它的变化使n-m非基变量的检验数都发生变化。为使最优解保持不变lc应满足0''min0''maxljljjlljljjaacaa，当lc超过此范围时，应求出n-m个检验数j，选择其中大于零的检验数对应的变量为进基变量，继续迭代，求新的最优解。右端一常数rb的变化会影响解的可行性，但不会引起检验数符号变化，由bBxB1知，会引起最优解数值的变化。最优解的变化可以分为以下两种：一是01bB，即最优基B不变（影子价格不变，也就是对偶问题的最优解不变）；二是bB1中出现负分量，这将使最优基变化，若最优基不变（影子价格不变），这只需要将变化后的rb代入bB1的表达式重新计算即可，若bB1中出现负分量，则只需通过迭代求解新的最优基和最优解。为使最优基不变rb应该满足0'min0'maxiririririribbb，当rb超过此范围时，将使最优解中某个分量小于零，是最优基发生变化。此时可利用对偶单纯形法继续迭代求新的最优解。当约束条件中当只有一个系数ija变化，并且其为非基变量jx的系数时，ija的变化只影响一个检验数j，为使最优解保持不变，改变量ija应满足)0(**iijijyya)0(**iijijyya其中*iy为对偶最优解的y的第i个分量。增加一个新变量1nx，其相应的目标函数系数为1nc，检验数为1n，若1n0，则最优解不变，否则在单纯形表中加入1nx列，继续进行单纯形法迭代。当增加一个约束条件时，现将最优解代入该约束式，若满足该约束条件，则最优解不变。否则将约束条件考虑进去，增加一个新行和一个新列(引入松弛变量或人工变量)，并通过初等变换使新表中含有各单位向量，此时相应的新基变量的值必小于0，利用对偶单纯形算法继续迭代求解。2.无约束最优化方法无约束最优化问题，是指fs问题中nRS的情况，为了简便，记无约束最优化问题为xffmin，其中，RRfn:。2.1最速下降法最速下降法是求解无约束问题的古老而又基本的方法，在下降算法的模型中，方向取负梯度方向)()()(kkxfd，采用精确的一位搜索，即得到最速下降法。最速下降法的基本思想是从当前点kx出发，取函数f(x)在点kx处下降最快的方向作为我们的搜索方向。设RRfn:，在x可微，0)(xf，那么，)()(xfxfd是问题1..);('min)(dtsdxfp的最优解，d是f在在x点的最速下降方向。最速下降法的流程图如下：)()(kxfStop,)(kxyesK=1,)1(x初始点,0)()()(kkxfdNok=k+1)()()1()()(0..)(minkkkkkkdxxtsdxf得图2-1最速下降法流程图其特点是全局最优,线性收敛,易产生扭摆现象而造成早停.当x(k)距最优点较远时,速度快,而接近最优点时,速度下降.适用于精度要求不高或用于对复杂函数寻找一个好的初始点。2.2牛顿法由于最速下降法在最初几步迭代中函数值下降很快，但愈接近极值点下降的愈慢。因此，应寻找使目标函数下降更快的方法。牛顿法就是一种收敛很快的方法，其基本思路是利用二次函数近似目标函数，把这个二次函数的极小点作为新的迭代点。牛顿法的流程图如下：K=1,)1(x初始点,0)()()1()()(2,))(()(kkkkkksxxsxffsxf得?)(ksStop,optlxk.)1(为yesK=k+1no图2-2牛顿法流程图牛顿法的特点是二阶收敛，局部收敛。当X(k)充分接近x时，局部函数可用于正定二次函数很好地近似，故收敛很快。使用于目标函数在一阶/二阶偏导数，且维数不宜太高。2.3共轭梯度法K=k+1)()()1()()(0..)(minkkkkkkdxxtsdxf得,)1(x初始点,01)()1()1(kxfd)()(kxfStop,optxkyesK=n?)()1()1()(kkkkdxfd1,)()1()1()1()1(kxfdxxnnoyesno图2-3共轭梯度法流程图其特点在于全局收敛（下降算法）；线性收敛；每步迭代只需存储若干向量（适用于大规模问题）；有二次终结性（对于正定二次函数，至多n次迭代可达opt.）