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

（ 第三版） 运筹学 教材编写组 编清华大学出版社运筹学 第 1章 线性规划与单纯形法第 3节 单纯形法钱颂迪 制作第 1章 线性规划与单纯形法第 3节 单纯形法3.1 举例3.2 初始基可行解的确定3.3 最优性检验与解的判断3.4 基变换3.5 迭代（旋转运算）单纯形法求解线性规划的思路： 一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或最小值为止。这样问题就得到了最优解，先举一例来说明。注： 单纯形是指 0维中的点，一维中的线段，二维中的三角形，三维中的四面体， n维空间中的有 n+1个顶点的多面体。例如在三维空间中的四面体，其顶点分别为 (0， 0， 0)， (1， 0， 0)， (0， 1， 0)， (0， 0， 1)。具有单位截距的单纯形的方程是 xi1 ，并且 xi0 ，i=1,2,m。3.1 举例例 6 试以例 1来讨论如何用单纯形法求解。例 1的标准型为：约束方程 (1-12)式的系数矩阵 从 (1-12)式中可以看到 x3,x4,x5的系数列向量P3 ,P4,P5是线性独立的，这些向量构成一个基对应于 B的变量 x3,x4,x5为 基变量 . 从 (1-12)式中可以得到（ 1-13）将 (1-13)式代入目标函数 (1-11) 得到 当令非基变量 x1=x2=0，便得到 z=0。这时得到一个基可行解 X(0) X(0)=(0,0,8,16,12)T 这个基可行解表示：工厂没有安排生产产品 、 ；资源都没有被利用，所以工厂的利润指标 z=0。 从分析目标函数的表达式 (1-14)可以看到 非基变量 x1,x2(即没有安排生产产品 ， )的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品 或 ，就可以使工厂的利润指标增加。所以只要在目标函数 (1-14)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换。 如何确定换入变量，换出变量 一般选择正系数最大的那个非基变量 x2为换入变量，将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量，可按以下方法来确定换出变量。 现分析 (1-13)式，当将 x2定为换入变量后，必须从 x3,x4,x5中确定一个换出变量，并保证其余的都是非负，即 x3,x4,x50。当 x1=0,由 (1-13)式得到x2取何值时，才能满足非负要求 从 (1-15)式中可以看出，只有选择 x2=min(8/2,-,12/4)=3时， 才能使 (1-15)式成立。 因当 x2=3时，基变量 x5=0，这就决定用 x2去替换 x5。 以上数学描述说明了每生产一件产品 ，需要用掉各种资源数为 (2， 0， 4)。由这些资源中的薄弱环节，就确定了产品 的产量。 这里就是由原材料 B的数量确定了产品 的产量 x2=12/4=3件。为求得以 x3,x4,x2为基变量的一个基可行解和进一步分析问题，需将 (1-13)中 x2的位置与 x5的位置对换。得到用高斯消去法 将 (1-16)式中 x2的系数列向量变换为单位列向量。其运算步骤是： = /4； = -2 ; = , 并将结果仍按原顺序排列有 ： 再将 (1-17)式代入目标函数 (1-11)式得到 从目标函数的表达式 (1-18)中可以看到，非基变量 x1的系数是正的，说明目标函数值还可以增大， X(1)还 不是最优解。 于是再用上述方法，确定换入、换出变量，继续迭代，再得到另一个基可行解 X(2) X(2)=(2,3,0,8,0)T 再经过一次迭代，再得到一个基可行解 X(3) X(3)=(4,2,0,0,4)T 而这时得到目标函数的表达式是： z=14-1.5x3-0.125x4 (1-19) 再检查 (1-19)式，可见到所有非基变量 x3,x4的系数都是负数。这说明若要用剩余资源 x3,x4，就必须支付附加费用。 所以当 x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。所以 X(3)是最优解。即当产品 生产 4件，产品 生产 2件，工厂才能得到最大利润。 通过上例，可以了解利用单纯形法求解线性规划问题的思路。现将每步迭代得到的结果与图解法做一对比，其几何意义就很清楚了。 原例 1的线性规划问题是二维的， 即两个变量 x1,x2；当加入松弛变量 x3,x4,x5后， 变换为高维的。 这时可以想象，满足所有约束条件的可行域是高维空间的凸多面体 (凸集 )。这凸多面体上的顶点，就是基可行解。初始基可行解 X(0)=(0,0,8,16,12)T就相当于图 1-2中的原点 (0， 0)，X(1)=(0,3,2,16,0)T相当于图 1-2中的 Q4点 (0， 3)； X(2)=(2， 3， 0， 8， 0)T相当于 图 1-2中的 Q3点 (2， 3)， 最优解 X(3)=(4， 2， 0， 0， 4)T 相当于图 1-2中的 Q2点 (4， 2)。 从初始基可行解 X(0)开始迭代，依次得到 X(1)， X(2)，X(3)。这相当于图 1-2中的目标函数平移时， 从 0点开始，首先碰到 Q4，然后碰到 Q3，最后达到 Q2。下面讨论一般线性规划问题的求解。一般线性规划问题的求解 3.2 初始基可行解的确定 为 了确定初始基可行解，要首先找出初始可行基，其方法如下。 (1)直接观察 (2)加松弛变量 (3)加非负的人工变量(1)直接观察若线性规划问题从 Pj(j=1,2,n)中一般能直接观察到存在一个初始可行基(2)加松弛变量 对所有约束条件是 “ ”形式的不等式，可以利用化为标准型的方法，在每个约束条件的左端加上一个松弛变量。 经过整理，重新对 xj及aij(i=1,2,m;j=1,2,n)进行编号，则可得下列方程组x1,x2,xm 为松弛变量于是含有 mm单位矩阵，以 B 作为可行基。 将 (1-22)式每个等式移项得令 xm+1=xm+2=xn=0，由 (1-23)式可得xi=bi (i=1,2,m)得到一个初始基可行解 又因 bi0( 在 1-3节中已做过规定 )，所以得到一个初始基可行解 X=(x1,x2,xm,0， ， 0)T n-m个=(b1,b2,bm,0， ， 0)T n-m个(3