第2章 线性规划（第2节） 运筹学课件.ppt

表2.33 基 右边 1 0 0 2 0 42 0 2/7 1 1/7 0 3 0 45/7 0 -2/7 1 15 得到最优解 和 。 但是从最优表格表1.33中看非基变量 在目标方程中有一个零的系数，这表明存在着可选择的解。 这个解是基本的，因为 可以做基变量。 计算如下： · 在表2.33中，调入 和调出 ， 得表2.34。 表2.34 基 右边 1 0 0 2 0 42 0 0 1 7/45 -2/45 7/3 0 1 0 -2/45 7/45 7/3 得到新的最优解是 和 以上得到两个可选择的最优基本解(0,3)和(7/3，7/3)。 它们的目标函数值 是相同的。 我们可以用这两个最优基本解的任何加权平均数产生无穷多个最优的非基本解。 这只要设 ，而令 和 即 和 就可以了。 当 时，就得到两个最优基本解， 而在 时， 所得到的就是一族最优的非基本解， 它们就是图2.7中BC线段上的各个点。 一般地，一个线性规划问题如果有P个可选择的最优基本解 那么包括基本的和非基本的所有可选择解族是 这里 并且 。 4．不存在可行解 这种情况是在一个线性规划问题中没有一个点能满足所有约束条件时发生。 在图形上，没有可行解意味着可行域是空的。 下面举个例子说明怎样应用单纯形法来看出这种情况。 例2.11 约束条件： 解：增加松弛变量和人工变量后，填入单纯形表格如表2.35所示。 表2.35 基 解 1 -3 -2 0 0 M 0 0 2 1 0 1 0 2 0 3 4 -1 0 1 12 在表2.35中将目标方程只按非基变量表示后，得到初始表格如表2.36。 表2.36 基 解 1 -3-3M -2-4M M 0 0 -12M 0 2 1 0 1 0 2 0 3 4 -1 0 1 12 在表2.36中，调入 和调出 ， 得表2.37。 表2.37 基 解 1 1+5M 0 M 2+4M 0 4-4M 0 2 1 0 1 0 2 0 -5 0 -1 -4 1 4 根据最优性条件，这个解是最优的，但在最优解中包括了一个正的人工变量R，这表明问题没有可行解。 因为一个正的R表示原来问题的第二个约束条件没有被满足，所得到的解实际上是表示另外一个问题。 这个例子的图像如图2.8所示。 从图2.8可以看出，这个问题没有可行域。 一个线性规划问题是否有可行解也可以用两阶段法中的第1阶段来检验。 例2.7 约束条件： 解：填入单纯形表格后，得到初始表格如表2.23所示。 表2.23 基 右边 1 -3 -9 0 0 0 0 1 4 1 0 8 0 1 2 0 1 4 表中是 松弛变量。 第一次迭代：调入 和调出 ，得表2.24。 表2.24 基 右边 1 -3/4 0 9/4 0 18 0 1/4 1 1/4 0 2 0 1/2 0 -1/2 1 0 第二次迭代： 调入 和调出 ，得表2.25。 表2.25 基 右边 1 0 0 3/2 3/3 18 0 0 1 1/2 -1/2 2 0 1 0 -1 2 0 得到最优解 ，和 这是一个退化的最优解。 这个例子的解用图像表示如图2.4所示。 在本例中，本来只要两个约束条件就可以 确定一个极点，而现在 和 这三个约束条件所对应的直线都经过最优解点(0，2)。 实际上 这个约束条件是多余的。 2．无界的解 这种情况发生在可行域是无界的时候，以致使目标函数值可以无限地增加。 但是一个无界的可行域并不一定总是产生无限的目标函数值，下面对这两种情况各举一个例子来说明。 例2.8 约束条件： 解：增加松弛变量后，初始表格如表2.26所示。 表2.26 基