最优化理论小结

1、精选优质文档-倾情为你奉上学号： 姓名：施林红 最优化理论方法小结转眼间研一的第一学期就要结束了，经过三个月的学习，我对最优化理论与方法这门课也有了一定的认识与了解。下面是我对这门课的小结。1.线性规划线性规划的规范形式如下 （1） 称以下形式为标准形式 （2）其中z为目标函数，（j=1,2,，n）为决策变量, 为价值系数，（j=1,2,，m）为右端项，为约束系数。从线性规划的标准形式可知，其具有四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。1.1单纯形算法单纯形算法的基本思想是有选择的取基本可行解，即从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目

2、标函数值不比原目标函数值差。下面是以我自己的理解对单纯形算法的步骤所做的归纳：1） 列出初始单纯形表2） 算出检验数。3） 确定旋入、旋出变量。先确定旋入变量，旋入变量是取检验数最大所在的那一列对应的决策变量；旋出变量是将单纯形表中b所在的那一列的各项值除以旋入变量所在列的对应值（必须大于0）即得到，取最小的值，其对应的决策变量作为旋出变量。4） 对组成的矩阵作初等行变换，知道选入变量之前所在的的列变为旋出变量之前所在的列对应的值即可。5） 如此反复迭代，直到检验数全为非正则停止。6） 从表中得到最优解和最优目标值。1.2对偶单纯形算法对偶单纯性算法的基本思想是从原规划的一个基本解出发，此基本

3、解不一定可行，但它对应着一个对偶可行解（检验数均非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负分量，如果有小于零的分量则进行迭代，求另一基本解，此基本解对应着另一个基本可行解（检验数非正）。如果得到的基本解的分量均非负，则该基本解为最优解。下面是以我自己的理解对单纯形算法的步骤所做的归纳：1）建立初始对偶单纯形表，此表要求检验数行各元素一定非正，原规划的基本可行解可以有小于零的分量。2）若基本解的所有分量皆非负，则得到原规划的最优解，停止计算。若基本解有小于零的的分量，且所在行的各系数，则原规划没有可行解；若所在行的各系数存在，则确定最小的为出基变量，并

4、计算确定为进基变量。3）如此反复迭代，直至基本解非负，检验数全为非正则停止。1.3灵敏度分析 线性规划模型中的参数常常是估计量，所以在对问题求解之后，需要对这些估计量进行分析，以决定是否需要对所求解进行调整。周围环境的变化也会使参数发生变化，这些参数的变化很可能影响以求得的最优值，因此在解决实际问题时，一般要研究最优解对数据变化反应的程度，以使决策者全面的考虑问题，这就是灵敏度分析所要研究的一部分内容。灵敏度分析考虑价值系数，资源系数，约束条件系数，增加新变量，增加约束条件等的变化对其的影响。价值系数的变化有两种情况，一是非基变量系数的变化，二是基变量系数的变化。非基变量系数的变化。当非基变量

5、系数变化时，只影响与有关的一个检验数的变化，对其它的没有影响，变化后的检验数，变化后的某一价值系数为-，-为的变化上限。当变化超过此上限时，最优解将发生变化，应求出新检验数的值，取为进基变量，继续迭代求新的解。基变量系数变化时，它的变化使n-m非基变量的检验数都发生变化。为使最优解保持不变应满足，当超过此范围时，应求出n-m个检验数，选择其中大于零的检验数对应的变量为进基变量，继续迭代，求新的最优解。右端一常数的变化会影响解的可行性，但不会引起检验数符号变化，由知，会引起最优解数值的变化。最优解的变化可以分为以下两种：一是，即最优基B不变（影子价格不变，也就是对偶问题的最优解不变）；二是中出现

6、负分量，这将使最优基变化，若最优基不变（影子价格不变），这只需要将变化后的代入的表达式重新计算即可，若中出现负分量，则只需通过迭代求解新的最优基和最优解。为使最优基不变应该满足，当超过此范围时，将使最优解中某个分量小于零，是最优基发生变化。此时可利用对偶单纯形法继续迭代求新的最优解。当约束条件中当只有一个系数变化，并且其为非基变量的系数时，的变化只影响一个检验数，为使最优解保持不变，改变量应满足 其中为对偶最优解的y的第i个分量。增加一个新变量，其相应的目标函数系数为，检验数为，若0，则最优解不变，否则在单纯形表中加入列，继续进行单纯形法迭代。当增加一个约束条件时，现将最优解代入该约束式，若满

7、足该约束条件，则最优解不变。否则将约束条件考虑进去，增加一个新行和一个新列(引入松弛变量或人工变量)，并通过初等变换使新表中含有各单位向量，此时相应的新基变量的值必小于0，利用对偶单纯形算法继续迭代求解。2.无约束最优化方法无约束最优化问题，是指问题中的情况，为了简便，记无约束最优化问题为，其中，。2.1最速下降法最速下降法是求解无约束问题的古老而又基本的方法，在下降算法的模型中，方向取负梯度方向，采用精确的一位搜索，即得到最速下降法。最速下降法的基本思想是从当前点出发，取函数f (x)在点处下降最快的方向作为我们的搜索方向。设，在可微，那么，是问题的最优解，是在在点的最速下降方向。最速下降法的流程图如下：图2-1最速下降法流程图其特点是全局最优,线性收敛,易产生扭摆现象而造成早停.当x(k) 距最优点较远时,速度快,而接近最优点时,速度下降.适用于精度要求不高或用于对复杂函数寻找一个好的初始点。2.2牛顿法由于最速下降法在最初几步迭代中函数值下降很快，但愈接近极值点下降的愈慢。因此，应寻找使目标函数下降更快的方法。牛顿法就是一种收敛很快的方法，其基本思路是利用二次函数近似目标函数，把这个二次函数的极小点作为新的迭代点。牛顿法的流程图如下：图2-2牛顿法流程图牛顿法的特点是二阶收敛，局部收敛。当X(k)充分接近x时，局部函数可用于正定二次函数很好地近似，故收敛很快。使用