1.3 72单纯形法.ppt

即： 将求出的θ代入X中，得到新的可行解： 为换出变量 最小比值规则 θ规则 第l个分量 第m+t个分量 由上式可知： 0 i=l或i=m+1…n且i≠m+t 换入变量对应的列向量是否能与原来的基向量的剩余向量构成一个基？ X (1)的m个非零分量对应的列向量是线性独立 证明：X(1)的中的m个非零分量对应的m个列向量 和Pm+t 若它们不是线性独立，则Pm+t可以用Pj线性表示，即存在不全为零的数?j ，使 （1-31） （1-32） （1-32）-（1-31）得： X(0)的第 l个分量对应于X(1)的相应分量为零即 与假设矛盾。 P1 ，P2 … Pm线性相关 和Pm+t线性独立 X(1)的中的m个非零分量对应的m个列向量 新组成的向量组是LP的一个可行基。 即经过基变换得到的解是基可行解。 实际上，从一个基可行解到另一个基可行解的变换，就是进行一次基变换。 从几何意义上讲，就是从可行域的一个顶点转到与之相邻的另一个顶点(见1-2图解法) 上述讨论的基可行解的转换方法是用向量方程来描述，在实际计算时不太方便，因此采用系数矩阵法。现考虑以下形式的约束方程组 一般线性规划问题的约束方程组中加入松弛变量或人工变量后，很容易得到上述形式。 3.5 迭代(旋转运算) 设x1,x2,…,xm为基变量，对应的系数矩阵是m×m单位阵I，它是可行基。 X(0) =（ b1 ， b2 ，…， bm ，0，…，0）T 若它不是最优解，则要另找一个使目标函数值增大的基可行解。 根据规则，要确定换入 和换出变量： 先从非基变量中确定xk为换入变量。 再 从基变量中确定xl 为换出变量，这时θ为： 令非基变量xm+1=xm+2=…=xn=0，即可得到一个基可行解： 按θ规则确定xl为换出变量，xk, xl的系数列向量分别为 在迭代过程中θ可表示为 其中 是经过迭代后对应于的元素值。 （1-33）系数矩阵的增广矩阵为： （1-34） 进行初等变换: 1.为了使主元素alk为1， （1-35） 为主元素，它所在的列为主元列，它所在的行为主元行 矩阵中第l行要除以alk ,得到 2. 新的增广矩阵各元素的变换公式为: 3 新的增广矩阵为: x1、x2 ……xl-1 、 xk 、 xl+1 …… xm 构成新的基变量。 令非基变量 xm+1 = …… ＝ xk -1=xl =xk+1 = ……= xn =0,得： 4 【例７ 】 系数矩阵的增广矩阵为： max z=2x1 + 3x2 + 0x3+0 x4 +0x5 x1 + 2x2 + x3 =8 4x1 +x4 =16 4x2 +x5 =12 x1 ,x2 ≥0 X(0) =（０,0,8,16,12）T X(1) =（ 0,3,2,16,0）T 用单纯形法求解线性规划问题的具体步骤如下： ①找出初始可行基，确定初始基本可行解， 建立初始单纯形表；转②。 ②检验对应于非基变量的检验数σj . 若σj≤0（xj为非基变量）都成立， 则当前单纯形表对应的基本解就是最优解，停止计算； 若σj≤0（xj为非基变量）都成立， 且至少有一个σk=0, 则有多重最优解 ； 非以上情况，则转③。 ③在所有σj0中，若有一个σk对应的xk的系数 aik≤0 (i=1,2,…,m)， 则此问题为无界解（无解），停止计算； 否则转④。 ④根据 max（σj0）=σk 确定xk为换入变量； 根据θ规则 θ＝min{bi/aik｜1≤i≤m, aik0}＝bl/alk 确定相应的换出变量， 并得到中心元素alk。转⑤。 ⑤以alk为枢轴元素进行转轴运算， 得到新的单纯形表。转②. 小结 按照单纯形法的思路求解线性规划问题, 要解决三个技术问题: ⑴给出第一个基本可行解; ⑵检验一个基本可行解是否是最优解; ⑶转换到另一个基本可行解. ⑴把线性规划问题变成标准型后, 观察是否每个约束方程中都有一个有单位向量的变量. 如果是,则取这些变量作为基变量, 得到一个基本可行解; 否则,就给没有这种变量的约束条件添加一个人工变量,同时修改目标函数. ⑶第一,确定换入变量. 在大于0的检验数中 找最大的为σk, 对应变量xk为换入变量.