第三篇 线性规划单纯形算法-1.ppt

第三章 单纯形法;（每迭代一次要计算一次 ） ; 5 如有σj为负值，选取σj绝对值最大的一列为枢轴列，使这一列对应的变量为进基变量。 6 应用最小比值规则,决定枢轴行,使这一行的基变量出基。最小比值原则就是指,若进基变量为xr 。r列的系数为;定义2：称 为基B的单纯形乘子，记为：; 解：第一步，将（LP）问题化为（SLP）问题。 第二步，作下面形式的单纯形表（开始只能写出左上部表格）; 第三步; 第六步，对选定的入基变量 xj ，考虑 取 ，对应的变量 x2 作为出基变量;反复进行上述步骤，直到各检验数均非负值，即可得到基本最优解，上面得到原问题最优解为：; 1. 如果所有判别数 （j=1~n）由最优判别定理1知B是最优基，则求出了最优基本解，步骤终止。; ; 使用人工变量的单纯形法中有两种解法可以尽快地把人工变量???小到零---大M法和两阶段单纯形法。 （—）大M单纯形法：大M单纯形法要求将目标函数中的人工变量被指定一个很大的目标函数系数（人工变量与松弛剩余变量不同之处） ;例2 .用人工变量大M法解下列线性规则； max z=(3 X1+ 2 X2) s.t. 2x1+x2≤2 3x1+4x2≥12 x1≥0， x2≥0 ; 2x1+x2+x3=2 3x1+4x2-x4+x5=12 xi≥0 i=1~5;;这时的检验数已全部非负.得最优解x1=x3=x4=0 x2=2 x5=4 最优值Z=4-4M 此时的最优基中包含了人工变量.因此是不可行的.从而原问题无解.这类情况有时称为伪最优解（Pseudo Optimal Solution) （二） 两阶段单纯形法 仍以上面的例子来说明.在加入人工变量x6和x7以后.还可以将线性规划问题分成两个阶段求解 第一阶段的目的是为原问题求初始基可行解。第二阶段再在此基可行解基础上对原目标函数进行优化。 在第一阶段中先不考虑原来的目标函数.而是另外建立一数个人工目标函.因在例1中.第一阶段的目的是要使x6和x7为零.所以本例中目标函数及约束问题列为；; 用单纯形法来解这个新的线形规划问题（也可以先化为极大化问题再解）（用MIN时注意判别数改变符号！）;用单纯形法求解。得出第一阶段表格如下：（注意是极小化问题，判别数都不大于0时即为最优表！）;（LP）中退化的基本可行解是指基可行解中有取零值的基变量的情形。 我们以前的计算都是假设在非退化的情形下进行的，并证明了单纯形法收敛性。但实际上，往往会出现退化的基可行解，这时单纯法会出现循环。 先看一个有退化基的例子，来说明一个基可能重复出现，从而出现循环迭代。;二 避免循环的ε摄动法 如果（SLP）有一个退化的基本可行解，即B0b≥0中有0分量。于是就不满足单纯形法迭代收敛定理的条件，不能保证有限次迭代内解决此问题。 上面的Beale 例即说明了此种情况。 摄动法的基本思想就是： 将向量b作一微小的变动，变为b（ε）。使得 B0-1b（ε）0。从而对于摄动问题B0对应了非退化的基本可行解。如果能进一步证明：在ε的某一取值范围内摄动问题是一个非退化的（LP），那么它满足单纯形法迭代收敛条件，经过有限次迭代就能解决此问题。如果摄动问题有最优解，再把b（ε）→b，就得到原问题的最优解。 下面来具体构造摄动问题。; 若B是摄动问题的可行基，则基变量取值非负。 故知基变量取值为正值。 即若B是摄动问题的可行基，则B一定是摄动问题的非退化可行基。 定理7：当ε0足够小， （1）若 是摄动问题的基可行解，令ε=0，则 是原问题的一个基可行解。 （2）若x*（ε）是摄动问题的基本最优解。则x*（0）也是原问题的基本最优解。 证明：（1）设X0（ε）是摄动问题的一个基可行解，对应基B。并设 的分量为 (i=1～m),由（*）式知X0（ε）的基变量取值为：