资源描述：
《线性规划与单纯形法-第3节》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、（第三版）《运筹学》教材编写组编清华大学出版社运筹学第1章线性规划与单纯形法第3节单纯形法钱颂迪制作第1章线性规划与单纯形法第3节单纯形法3.1举例3.2初始基可行解的确定3.3最优性检验与解的判断3.4基变换3.5迭代（旋转运算）单纯形法求解线性规划的思路：一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或最小值为止。这样问
2、题就得到了最优解，先举一例来说明。注：单纯形是指0维中的点，一维中的线段，二维中的三角形，三维中的四面体，n维空间中的有n+1个顶点的多面体。例如在三维空间中的四面体，其顶点分别为(0，0，0)，(1，0，0)，(0，1，0)，(0，0，1)。具有单位截距的单纯形的方程是∑xi≤1，并且xi≥0，i=1,2,…,m。3.1举例例6试以例1来讨论如何用单纯形法求解。例1的标准型为：约束方程(1-12)式的系数矩阵从(1-12)式中可以看到x3,x4,x5的系数列向量P3,P4,P5是线性独立的，这些向量构成一个基
3、对应于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(即没有安排生产产品Ⅰ，Ⅱ)的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品Ⅰ或Ⅱ，就
4、可以使工厂的利润指标增加。所以只要在目标函数(1-14)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换。如何确定换入变量，换出变量一般选择正系数最大的那个非基变量x2为换入变量，将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量，可按以下方法来确定换出变量。现分析(1-13)式，当将x2定为换入变量后，必须从x3,x4,x5中确定一个换出变量，并保证其余的都是非负，即x3,x4,x5≥0。当x1=0,由(1-13)式得到x2取何值时，才能满
5、足非负要求从(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的系数列向量
6、变换为单位列向量。其运算步骤是：③′=③/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.125x
7、4(1-19)再检查(1-19)式，可见到所有非基变量x3,x4的系数都是负数。这说明若要用剩余资源x3,x4，就必须支付附加费用。所以当x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。所以X(3)是最优解。即当产品Ⅰ生产4件，产品Ⅱ生产2件，工厂才能得到最大利润。通过上例，可以了解利用单纯形法求解线性规划问题的思路。现将每步迭代得到的结果与图解法做一对比，其几何意义就很清楚了。原例1的线性规划问题是二维的，即两个变量x1,x2；当加入松弛变量x3,x4,x5后，变换为高维的。这时可以想象，满足所有
8、约束条件的可行域是高维空间的凸多面体(凸集)。这凸多面体上的顶点，就是基可行解。初始基可行解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)。从初
