单纯形法单纯形引入

1、单纯形法的引入例1：LP：MAX: 300X1 +400X2 +500X3 ST: 1X1 +2X2 +3X3 =170 2X1 +1X2 +4X3 =01）化成标准型：MAX: 300X1 +400X2 +500X3 +0X4 +0X5ST: 1X1 +2X2 +3X3 + X4 =170 2X1 +1X2 +4X3 +X5 =160X1,X2,X3,X4,X5 =02）矩阵表示：MAX CXST AX=bX=0或 MAX CX | AX=b, X=03）猜想：两个约束，如果只保留两个变量在约束中，其它变量设为0，会如何？若保留 X1,X2MAX: 300X1 +400X2 +500X3 S

2、T: 1X1 +2X2 =170 -3X3 -1X42X1 +1X2 =160 -4X3 -1X5求解方程组，得出： X150 -5/3X3 +1/3X4 -2/3X5 X260 -2/3X3 -2/3X4 +1/3X5这里X1,X2被称为基变量, X3,X4,X5为非基变量。令非基变量X3,X4,X5=0,得到： X150 X260此时，得到一个基本解（基解）（50，60，0，0，0）基变量非负，此基本解为基本可行解。（如果解出基变量为负，这个基本解为非可行解）4）疑问：此基本可行解是最优解吗？分析目标函数：Z=300X1 +400X2 +500X3=300*50+400*60=39000，

3、是最优值吗？若将目标函数里的X1,X2用X3，X4，X5表示，如上面棕色字体表示的公式，代入目标函数，得：Z= 39000(800/3)X3(500/3)X4 (200/3)X5分析：X3,X4,X5的系数都是负数，考虑他们非负的约束，如果他们任何一个要变动，只能大于零，会使目标函数减少（变差）。所以，现在得到的解是最优解。最优值为39000。目标函数只用非基变量表示后，变量的系数称为检验数。求最大化的线性规划，如果基变量已经非负，所有检验数非正，可以判定达到了最优解。5）思考：这个解可能是碰巧得到的！如果不是最优解，怎么办？再找！寻找范围：顶点穷举法不可取选取使得目标函数改进最快的路线，看下

4、面的例题。例2：单纯形法解一般线性规划问题的系统方法例：用单纯形法求解MAX Z=2X1+3X2ST: 1X1 +2X2 =8 4X1 =16 4X2 =01）化成标准型：MAX Z=2X1+3X2+0X3+0X4+0X5ST: 1X1 +2X2 +X3 = 8 4X1 +X4 = 16 4X2 +X5 = 12X1,X2,X3,X4,X5 =0基变量个数等于系数矩阵的zhi（约束条件个数）2）用X3、X5表示X1,X2,X4。X3、X5为非基变量原约束条件方程变为：1X1 +2X2 = 8 - X34X1 +X4 = 16 4X2 = 12 - X5解得：X1 = 2 - X3 + 1/2X

5、5X2 = 3 - 1/4X5X4 = 8 + 4X3 - 2X5令非基变量X3、X5等于零,得：X1=2, X2=3, X4=8,目标函数值等于13。得到一个可行解（2，3，0，8，0），是不是最优解？用非基变量X3、X5表示基变量X1,X2，X4，代入目标函数：MAX Z=2（2-X3+1/2X5）+3（3-1/4X5）=13-2X3+1/4X5此时，非基变量X5前面的系数大于零，不是最优解，13也不是最优值。X5为换入变量（入基变量），由非基变量变为基变量。哪个换出呢？当有多个检验数为正时，选择检验数最大的入基3）确定换出变量，在下面三个式子中：（X3仍为非基变量）X1=2-X3+1/2

6、X5X2=3-1/4X5X4=8+4X3-2X5？令X3=0，得到：X1=2 +1/2X5X2=3-1/4X5X4=8-2X5要使X1,X2,X4=0,(或者：X1,X2,X4要成为非基变量，必须满足X1 or X2 or X4=0)。对于第一条等式， X5=0的任意值都符合条件。对于第二条等式，当X5=0；对于第三条等式，当X5=0。只有当0=X5=0。MIN(12,4)=4,确定X4为出基变量？单纯型法中算法为把各约束方程中X5为负的系数除相应的常量，取最小值。4）用X3,X4表示X1、X2、X5X1=4- 1/4X4X2=2- 1/2X3+ 1/8 X4X5=4+ 2X3- 1/2X4令

7、非基变量X3、X4等于零,得：X1=4,X2=2,X5=4,目标函数值= 2X1+3X2=14。得到一个可行解（4，2，0，0，4），是不是最优解？代入目标函数Z=2X1+3X2+0X3+0X4+0X5 =2（4- 1/4X4）+3（2- 1/2X3+ 1/8 X4）+0X3+0X4+0X5=14- 1/8X4- 3/2X3此时，非基变量X3、X4前面的系数都小于零，是最优解，X1=4, X2=2, Z=14.总结上述过程，可以推导出：用Xi(i=1,2,m)表示基变量，用Xj(j=m+1,m+2,n)表示非基变量。根据线性规划的一般形式，可以推导出：（经过迭代后，z=目标函数值+非基变量*系

8、数）； ； 其中，Ci是基变量前面的系数，Cj是非基变量前面的系数。Z=2X1+3X2+0X3+0X4+0X5=2（4- 1/4X4）+3（2- 1/2X3+ 1/8 X4）=14- 1/8X4- 3/2X3(X4前面系数的计算方法：=0-（2*1/4 + 3*(-1/8)）=-1/8)例3用单纯形法求解 HYPERLINK 单纯形法求解2-基本迭代.doc （见单纯形法求解2 课件）MAX 50X1+100X2+0S1+0S2+0S3STX1 +X2+S1 =3002X1+X2 +S2 =400X2 +S3 =250(0) 确定单位矩阵对应的变量为初始基变量，即S1、S2、S3为基变量，X1

9、、X2为非基变量。用X1，X2表示S1、S2、S3，整理得：S1=300- X1- X2S2=400-2X1-X2S3=250 -X2令非基变量X1、X2等于0，得到：S1=300，S2=400，S3 =250。这组可行解为（0,0,300,400,250）。目标函数Z=50X1+100X2，代入可行解，得Z=0。由于目标函数X2系数100大于50，表明生产X2比生产X1，使得目标函数增长快。因此，选择X2为入基变量。S1、S2、S3中哪个为出基变量呢？考虑：X1还是非基变量，令X1=0，S1=300- X2S2=400- X2S3 =250 -X2X2只有小于等于250，才能保证S1、S2、

10、S3都大于等于0。因此，S3为出基变量。此时，S1、S2、X2为基变量，X1，S3为非基变量。(1) 用X1，S3表示 S1、S2、X2，整理得：S1=50 - X1 + S3S2=150 - 2X1 + S3X2 =250 - S3令非基变量X1 、S3等于0，得到：S1=50，S2=150，X2 =250。这组可行解为（0,250,50,150, 0）。目标函数:Z=50X1+100(250-S3)+0(50-X1+S3)+0(150-2X1+S3) +0S3=(50-0*1-0*2)X1+25000- 100S3=25000。此时，非基变量X1的系数50大于0，表明增加X1的产量，还可以

11、使得目标函数值增大。因此，可以确定X1为入基变量。S1、S2、X2中哪个为出基变量呢？考虑：S3还是非基变量，令S3=0，S1=50 - X1 S2=150 - 2X1 X2 =250 X1只有小于等于50，才能保证S1、S2、X2都大于等于0。因此，S1为出基变量。此时， X1、S2、X2为基变量，S1，S3为非基变量。(2) 用S1，S3表示 X1、S2、X2，整理得：X1=50 - S1 + S3S2=50 + 2S1-S3X2 =250 - S3令非基变量S1、S3等于0，得到：X1=50，S2=50，X2 =250。这组可行解为（50,250, 0, 50, 0）。目标函数Max Z

12、=50(50 - S1 + S3) +100(250-S3)= 27500- 50S1-50S3此时，非基变量S1 、S3的系数都小于0，说明已经得到最优解，Z=27500。例4 目标函数最小化与人工变量问题 HYPERLINK 单纯形法求解3-大M法.doc （见课件3）MIN F=2X1+3X2STX1+X2=350X1 =1252X1+X2=0化成标准型：(设F=-Z)MAX Z=-2X1-3X2+0S1+0S2+0S3STX1+X2-S1 =350X1 -S2 =1252X1+X2 +S3=600X1, X2, S1, S2, S3, =0此时，约束条件的系数矩阵是：在矩阵中找不到3阶

13、单位矩阵注意：负的单位向量与单位向量是不同的，用负的单位向量作基向量求得的基本解一般不满足非负条件，不是可行解。例如：上式中将S1, S2, S3作为基变量，X1, X2为非基变量，得：S1 =-350 +X1+X2S2 = -125+ X1 S3 =600-2X1-X2令非基变量X1, X2为零，得一组解为(0,0,-350,-125,600)，不是可行解。在第一、二约束条件中加入人工变量 A1,A2，模型成如下形式：MAX -2X1-3X2+0S1+0S2+0S3-MA1-MA2STX1+X2-S1 +A1 =350X1 -S2 +A2=1252X1+X2 +S3 =600X1, X2,

14、S1, S2, S3, A1, A2=0约束条件的系数矩阵变为： 注意：人工变量与松弛变量等不同，只能取零值，一旦人工变量取正值，那么有人工变量的约束方程和原始的约束方程就不等价了。为了尽力要求人工变量为0，规定人工变量在目标函数中的系数为-M，M为任意大的数。这样只要人工变量0，所求得目标函数最大值就是一个任意小的数，因此，目标函数会尽量趋近A=0。总结：1、最优性检验的依据检验数j用非基变量表示目标函数中的基变量，此时目标函数中所有变量的系数就是各变量的检验数。基变量的检验数必然为0。2、最优解判别定理对于求最大目标函数的问题中，对于某个基本可行解，如果所有的检验数j=0，则这个基本可行解

15、是最优解。（只要存在大于0的检验数，就需要继续迭代。）对于求目标函数最小的情况，只需将j=0。3、判断准则：（1）是唯一最优解？是无穷多最优解？ HYPERLINK 单纯形表法4无穷多最优解.doc （见课件4）判断准则：对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解。（2）是无界解？在某次迭代的单纯形表中，如果存在着一个大于零的检验数，并且该列的系数向量的每个元素都小于或等于零，则此线性规划问题为无界解。（3）是无解？线性规划的最优解里有大于零的人工变量，则此线性规划问题为无解。例6无界解问题 HYPERLINK 单纯形表法5无界解.doc （见课件5）max x+ys.t. x-y 1 -3x+2y