第章 线性规划与单纯形法-第3节.pptVIP

令 1最优解的判别定理 若 为对应于基B的一个基可行解，且对于一切j=m+1,…,n，有σj≤0，则X(0)为最优解。称σj为检验数。 当所有非基变量的σj≤0时，由（1-27）式可知已不存在任一可换入的非基变量， 使目标函数继续增大。所以以σj≤0，为最优解的判别准则。 2.无穷多最优解判别定理 若 为一个基可行解，对于一切j=m+1，…,n，有σj≤0，又存在某个非基变量的检验数σm+k=0，则线性规划问题有无穷多最优解。 证: 只需将非基变量xm+k换入基变量中，找到一个新基可行解X(1)。因σm+k=0，由(1-27)知z=z0，故X(1)也是最优解。由2.2节的定理3可知X(0)，X(1)连线上所有点都是最优解。 3．无界解判别定理 若 为一基可行解， 有一个σm+k＞0，并且对i=1,2,…，m，有 存在。 那么该线性规划问题具有无界解(或称无最优解)。 证: 构造一个新的解 X(1)，它的分量为 因 ，所以对任意的λ＞0都是可行解，把x(1)代入目标函数内得 z=z0+λσm+k 因σm+k＞0，故当λ→+∞，则z→+∞，故该问题目标函数无界。 以上讨论都是针对标准型，即求目标函数极大化时的情况。当求目标函数极小化时，一种情况如前所述，将其化为标准型。 如果不化为标准型，只需在上述1，2点中把σj≤0改为σj≥0，第3点中将 σm+k＞0改写为σm+k＜0即可。 3.4 基变换 若初始基可行解X(0)不是最优解及不能判别无界时，需要找一个新的基可行解。具体做法是从原可行解基中换一个列向量(当然要保证线性独立)，得到一个新的可行基，这称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行对换，就得到一个新的基可行解。 1.换入变量的确定 由(1-27)式看到，当某些σj＞0时，xj增大，则目标函数值还可以增大。这时要将某个非基变量xj换到基变量中去(称为换入变量)。若有两个以上的σj＞0，那么选哪个非基变量作为换入变量呢?为了使目标函数值增加得快，从直观上一般选σj＞0中的大者，即 则对应的xk为换入变量。但也可以任选或按最小足码选。 2.换出变量的确定 设P1，P2，…，Pm是一组线性独立的向量组，它们对应的基可行解是X(0)。将它代入约束方程组(1-21)得到 其他的向量Pm+1,Pm+2,…,Pm+t,…,Pn都可以 用P1，P2，…，Pm线性表示， 若确定非基变量Pm+t为换入变量， 必然可以找到一组不全为0的数(i=1,2,…,m)使得 在(1-29)式两边同乘一个正数θ，然后将它加到(1-28)式上，得到 新的基可行解。 由此得到由X(0)转换到X(1)的各分量的转换公式 这里 是原基可行解X(0)的各分量； 是新基可行解X(1)的各分量； βi,m+t是换入向量Pm+t的对应原来一组基向量的坐标。 现在的问题是，这个新解X(1)的m个非零分量对应的列向量是否性独立?事实上，因X(0)的第l个分量对应于X(1)的相应分量是零，即 成立。又因 将(1-32)式减(1-31)式得到 由于上式中至少有βl,m+t≠0， 所以上式表明P1，P2，…，Pm是线性相关， 这与假设相矛盾。 由此可见，X(1)的m个非零分量对应的列向量Pj(j=1,2,…,m,j≠l)与Pm+t是线性独立的， 即经过基变换得到的解是基可行解。 实际上，从一个基可行解到另一个基可行解的变换，就是进行一次基变换。从几何意义上讲，就是从可行域的一个顶点转向另一个顶点(见1-2图解法) 3.5 迭代(旋转运算)上述讨论的基可行解的转换方法是用向量方程来描述，在实际计算时不太方便，因此采用系数矩阵法。现考虑以下形式的约束方程组 一般线性规划问题的约束方程组中加入松弛变量或人工变量后， 很容易得到上述形式 设x1,x2,…,xm为基变量，对应的系数矩阵是m×m单位阵I，它是可行基。令非基变量xm+1,xm+2,…,xn为零，即可得到一个基可行解。若它不是最优解，则要另找一个使目标函数值增大的基可行解。这时从非基变量中确定xk为换入变量。显然这时θ为 在迭代过程中θ可表示为 其中是经过迭代后对应于的元素值。 按θ规则确定xl为换出变量，xk, xl的系数列向量分别为 为了使xk与xl进行对换，须把Pk变为单位向量，这可以通过(1-33)式系数矩阵的增广矩阵进行初等变换来