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

将模型填入单纯形表1.45中。 表1.45 经过若干次迭代后，基变量变为 ，则在表1.45中基一列的 ，应改为 ，为计算出 的取值， 一列中，约束条件的B应变为I，则当非基变量 , 变为零时，在解的一列中直接可得 的取值，故可在表1.45中的约束条件行两边同左乘 ，得表1.46。 表1.46 这里不妨假设 是存在的，因为如果B不可逆，说明约束条件中含多余约束方程，可去掉多余的约束，保证B的可逆性。 为判断当前的基本可行解是否最优，必须将表1.46中的基变量 从目标函数行中消去，可通过以下运算来实现，即将约束条件行左乘 后，加到目标函数行得表1.47。 表1.47 这样就得到了：当 为基变量时，解 为 ，目标函数值为 ，非基变量 的检验数分别为 和 。 当 和 都满足最优性 条件时，已得最优解，否则，当前的基本 解还不是最优的，还可进一步迭代，考虑 新的 (基变量)。 通过以上对单纯形表格矩阵形式的分析， 可以看出，当单纯形表格迭代到某一步 时，表格中的所有数据均由基变量 决 定，即我们取 在约束条件中的系数矩阵 为B，求出它的逆阵 ，再取 在目标函 数中的系数 ，则利用表1.47可将整个单 纯形表计算出来。只是在计算时，我们要 注意以下两点： 1.可能有一个或几个变量同时出现在 与 中，也就是说有一个或几个变量它既 是迭代若干次后的基变量，也是初始基变 量，虽然它们每个变量在单纯形表中占一 列，但我们在讨论 时要把它考虑进去， 在讨论 时也要把它考虑进去，即一列 扮演了两个角色。 2．由于单纯形表中，各变量的位置一般按 等事先确定，而未必会正好按 基变量 ，非基变量 等排列，好在 线性规划约束条件、目标函数中，交换变 量的先后位置是不要紧的，我们可以通过 交换变量的位置来实现 的排 列，或更常用的是，就用原有的次序，按 列来进行计算，选取有关的数据。 下面利用1.2节中例题1.8的第二次迭代单纯形表来说明。例1.8的标准形式如下： 约束条件： 填入单纯形表1.48中 初始基变量是 ，当某次迭代中， 以 作为基变量，注意到 既 是初始基变量在 中，又是迭代后的基 变量在 中，且在 表中也没紧连 在一起，在约束条件中，取 ，所对 应的三列，组成矩阵B： ,计算出 由目标函数行，得 有了这些数据，就可计算出以 为基的单纯性表中的其他数据如下： (1)解所在的列： 基变量取值为： 目标函数值 (2) 所在的列： 既不是初始基变量， 也不是当前单纯形表中的基变量，故 属 。 在约束条件中的系数： 在目标函数行的检验数： (3)初始基变量 由 组成，它们在 约束条件中的系数即为 ，已经求得，它 们的目标函数行的系数应为： (4)迭代后基变量 在目标函数行的 系数应为零，在约束条件中的系数为单位 矩阵。 把以上计算结果填入单纯形表格，可得表 1.49。 表1.49 这和例1.8中第二次迭代的表格完全相同。 在叙述定理2之前先讲一个引理1 引理1 可行解 是基本 可行解的充分必要条件是它的非零分量所 对应的列向量线性无关。 证明： 为简单起见，设X的非零分量为前k个变 量 。当X是基本可行解 时， 都是基变量，所对应的列 向量 当然是线性无关的，这 就是必要性。 下面证充分性。 如果向量组 线性无关， 显然 当 时，它们构成一个基，因而 便是相应的基本可行解。 若 时，由于 中存在着m个列向量的基向量组，根据线性代数中的代换定理，总可以从其余的列中取出m-k个列向量，比如 来使得 构成一个极大线性无关向量组，这样就确定了一个基B。它所唯一确定的基本可行解， 正是前面的可行解X。 定理2 在可行域Q中的点X是极点的充分必要条件是：X是 的一个基本可行解。 证 先证必要性。如果Q中的X是