最优化理论小结

1、学号：20131221447姓名：施林红最优化理论方法小结转眼间研一的第一学期就要结束了，经过三个月的学习，我对最优化理论与方法这 门课也有了一定的认识与了解。下面是我对这门课的小结。线性规划线性规划的规范形式如下max z = c x + c x HF c x1 12 2n ns.t. a x + a x + a x b11 112 21n n 1a x + a x + a x b21 122 22n n 2（）:a x + a x + a x 0称以下形式为标准形式max z = c x + c x + c x1 12 2n nst. a x + a x + a x = b11 112 2

2、1n n 1a x + a x + a x = b21 122 22n n 2（2）:a x + a x + a x = bm1 1m 2 2mn n mx ,x ,x 0其中z为目标函数，x （j=1,2,，n）为决策变量，c为价值系数，b.（j=,2,，jjIm）为右端项，a为约束系数。从线性规划的标准形式可知，其具有四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。1.1单纯形算法单纯形算法的基本思想是有选择的取基本可行解，即从可行域的一个极点出发，沿着可 行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。下面是以我自己的理解对单纯形算法的步骤所做的归

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

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

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

6、二是基变量系数的变化。非基 变量系数的变化。当非基变量系数匕变化匕时，只影响与匕有关的一个检验数b k的变化， 对其它的bj没有影响，变化后的检验数 b k =b.+匕，变化后的某一价值系数为 c o& rnJ%a J ci mn aU 0，即最优 基B不变（影子价格不变，也就是对偶问题的最优解不变）；二是B-1b中出现负分量，这 将使最优基变化，若最优基不变（影子价格不变），这只需要将变化后的七代入B-1b的表 达式重新计算即可，若B-1b中出现负分量，则只需通过迭代求解新的最优基和最优解。为 使最优基不变Ab应该满足|p 0|Ab m.n -bL|p b 1 （y* 0）11y* 七 ,i

7、Aa 二 （y*0）其中y*为对偶最优解的y的第i个分量。增加一个新变量x ，其相应的目标函数系数为c ，检验数为b ，若b 0，则+1+1+1+1最优解不变，否则在单纯形表中加入x歹U，继续进行单纯形法迭代。+1当增加一个约束条件时，现将最优解代入该约束式，若满足该约束条件，则最优解不变。 否则将约束条件考虑进去，增加一个新行和一个新歹（引入松弛变量或人工变量），并通过初 等变换使新表中含有各单位向量，此时相应的新基变量的值必小于0，利用对偶单纯形算法继续迭代求解。无约束最优化方法无约束最优化问题，是指(fs )问题中S = Rn的情况，为了简便，记无约束最优化问题 为(f)min f G)

8、，其中，f : Rn 一 R。2.1最速下降法最速下降法是求解无约束问题的古老而又基本的方法，在下降算法的模型中，方向取负 梯度方向d(k) =Nf (x(k)，采用精确的一位搜索，即得到最速下降法。最速下降法的基本思想是从当前点七出发，取函数f (x)在点七处下降最快的方向作 为我们的搜索方向。设f : RnT R，在x可微，Vf (X)丰0，那么，d = w(X)是问题 |W(X )|mmf 3,日)的最优解，d是f在在x点的最速下降方向。(p) st. Id 1最速下降法的流程图如下：图2-1最速下降法流程图其特点是全局最优，线性收敛,易产生扭摆现象而造成早停.当x(k)距最优点较远时,速度快，而 接近最优点时，速度下降.适用于精度要求不高或用于对复杂函数寻找一个好的初始点。2.2牛顿法由于最速下降法在最初几步迭代中函数值下降很快，但愈接近极值点下降的愈慢。因此， 应寻找使目标函数下降更快的方法。牛顿法就是一种收敛很快的方法，其基本思路是利用二 次函数近似目标函数，把这个二次函数的极小点作为新的迭代点。牛顿法的流程图如下：图2-2牛顿法流程图牛顿法的特点是二阶收敛，局部收敛。当X(k)充分接近x时，局部函数可用于正