运筹学-第1章-3-单纯形法

1、运筹学,计算机与通信工程学院,2,授课主要内容,目录： 第一章线性规划 第二章运输问题 第三章动态规划 第四章 图与网络分析,3,1.3 单纯形法,单纯形法的基本思想： 从可行域的一个基可行解（顶点）出发，判断是否为最优解，如果不是最优解就转移到另一个较好的基可行解（相邻），如果目标函数达到最优，则已经得到最优解，否则继续转移到其他较好的基可行解（顶点）。 由于基可行解的数目有限，所以在有限次迭代内，可以找到最优解。,4,单纯形法迭代原理,迭代基础：如果LP存在最优解，则一定有一个基可行最优解，且对应LP可行域的顶点。（可行，基解，最优）,1.确定初始基可行解,基解，可行解,（1）直接观察法,

2、5,max z = x1 + 3x2 + 2x3 + x4 s.t. x1 + 2x2 + 3x3 = 3 3x2 + x3 + x4 = 4 x1,x2,x3,x4 0,选 XB = (x1 x4)T 令x2 = x3 = 0 则 初始基可行解：X = (3 0 0 4)T,（2）人工变量法（大M法）,6,若给定问题标准化后，系数矩阵中不存在m个线性无关的单位列向量，则在某些约束的左端加一个非负变量xn+i（人工变量），使得变化后的系数矩阵中恰有m个线性无关的单位列向量，并且在目标函数中减去这些人工变量与一个足够大的正数M的乘积，对于变化后的问题，取m个单位列向量构成的单位子矩阵为初始基，则

3、该基对应的可行解一定是基可行解。,（2）人工变量法（大M法）,7,原问题的任意基可行解都是变化后问题的基可行解 若变化后的问题最优解中不含有非零的人工变量，则该解就是原问题的最优解 若变化后的问题中含有非零的人工变量则元问题无可行解,例：max z = x1 + 2x2 + 3x3 x1 + 3x2 + 2x3 = 3 s.t. 2x1 + x2 + x3 = 4 x1,x2,x3 0,8,2.最优性检验和解的判别,非基变量检验数,9,由检验数可以判断解的最优性情况 （1）因为所有Xj0，当所有j0,且所有aik0(Pj0), i=1,2,m，则该问题无界（无界解）； （4）因为所有Xj0，当

4、存在j0时，则该基可行解不是最优解，需要寻找另一个基可行解；,10,3.基变换,变换目的：使目标函数Z值得到改善，接近最优解，一次基变换，是从该顶点到相邻顶点，即一次基变换仅变换一个基变量。,换入变量的确定（入基变量） k0,aik 至少一个大于0，若k=Maxj| j0,则xk为换入变量。 换出变量的确定（出基变量）,则xl为换出变量。 系数变换（初等行变换）,11,以alk为主元进行初等行变换,12,1.4 单纯形法计算步骤,求初始基可行解 最优性检验 基变换,13,单纯形法原理单纯形法总结,STEP 0 找到一个初始的基础可行解，确定基变量和非基变量。转STEP 1。 STEP 1 将目

5、标函数和基变量分别用非基变量表示。转STEP 2。 STEP 2 如果目标函数中所有非基变量的检验数全部为非正数，则已经获得最优解，如果全为负数，则为唯一最优解，运算终止。 ；如果有为0的非基变量检验数，则有无穷多最优解。运算终止。如果有某非基变量检验数为正，且工艺系数全非正，则无界，运算终止。 否则，选取检验数为正数最大的非基变量进基。转STEP 3。 STEP 3 选择最小比值对应的基变量离基，进行系数初等行变换，得新的基可行解，转STEP 1。,14,一.求初始基可行解,1.当约束条件为“”时，直接在约束不等式左边加上非负的松弛变量，使约束方程的系数矩阵很容易找到一个单位矩阵，求出一个初

6、始基可行解。 2.当约束条件为“时，直接在约束不等式左边减去非负的剩余变量，此情况下很难找到一个单位矩阵，为求出初始基可行解，为此需要引入人工变量，以方便构成初始基可行解的一个基。 为了不改变问题的性质，对引入人工变量Xi”的线性规划问题，需要在目标函数中减去MXi”,M为足够大的正数，称罚因子，促使Xi”最终必为0。 3.当约束条件为”=“时，同样需要引入人工变量，以方便构成初始基可行解的一个基。目标函数需要减去罚因子。,15,二.最优性检验,（1）若所有j0,且所有aik0(Pj0), i=1,2,m，则该问题无界，计算终止。 （4）当存在j0时，且有aik0,继续第三步（基变换）；,16

7、,三.基变换,用单纯形法按上述步骤求解时，可采用表格形式，这样更直观，易于避免错误，该表格称为单纯形表。,17,例,j,2,1,0,0,0, ,-,4,5, ,x1入，x4出,j,0,1/3,0,-1/3,0, ,x2入，x5出,3,12,3/2, ,j,0,0,0,-1/4,-1/2,所以：X*=(x1,x2,x3)T=(7/2,3/2,15/2)T Z*=17/2,18,例:1.4(1),j,10,5,0,0, ,3,8/5, ,x1入,x4出,j,0,1,0,-2, ,x2入,x3出,3/2,4,j,0,0,-5/14,-25/14,所以：X*=(x1,x2)T=(1,3/2)T Z*=

8、35/2, ,对应0,对应A,对应B,19,1.5 单纯形法的进一步讨论,一、人工变量法（大M法） 约束条件： “” 减一个剩余变量后，再加一个人工变量； “” 加一个人工变量； 目标函数： 人工变量的系数为“M”，即罚因子； 若线性规划问题有最优解则人工变量必为0。,20,MaxZ=-3x1+x3 x1+ x2+ x34 -2x1+ x2- x31 3x2+x3=9 xi 0,j=1,2,3,增加人工变量后，线性规划问题中就存在一个B为单位矩阵， 后面可以根据我们前面所讲的单纯形法来进行求解。,MaxZ=-3x1+x3-Mx6-Mx7 x1+ x2+ x3+x4 =4 -2x1+ x2-x3

9、 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7,标准化及变形,21,二、两阶段法 第一阶段求初始基可行解。给原问题加入人工变量，并构建一个仅含人工变量的目标函数（对人工变量和的相反数求最大），约束条件和原问题的一样。 当第一阶段中目标函数的最优值0，既人工变量0，则转入第二阶段；若第一阶段中目标函数的最优值不等于0，既人工变量不等于0，则判断原问题为无解。 第二阶段求原问题最优解。将第一阶段计算所得的单纯形表划去人工变量所在的列，并将目标函数换为原问题的目标函数，作为第二阶段的初始单纯形表，以第一阶段的最优解作为初始基可行解，进行进一步的求解。,22,求解辅助问题，得到辅

10、助问题的最优解,引进人工变量x6，x7，构造辅助问题，辅助问题的目标函数为所有人工变量之和的极小化,MaxW=0?,原问题没有可行解。,把辅助问题的最优解作为原问题的初始基可行解,用单纯形法求解原问题，得到原问题的最优解,否,是,两阶段法的算法流程图,MaxZ=-3x1+x3 x1+ x2+ x34 -2x1+ x2- x31 3x2+x3=9 xi 0,j=1,2,3,MaxW=-x6-x7 x1+ x2+ x3+x4 =4 -2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xi 0,j=1,7,23,目标函数极小化最优性； 退化解的判别； 无可行解的判别； 无界的判别；

11、 无穷多最优解的判别； 唯一最优解的判别.,三、单纯形法计算中的几个问题,当所有非基变量的j0时为最优解；,最优解中基变量有取值为0的值时；,最优解中人工变量为非0的基变量时；,存在某个k0，且所有的aik0时；,得最优解时，有检验数为0的非基变量；,得最优解时，所有非基变量检验数为负；,24,j,40,45,0,25,100/3,40, 3 ,x2入，x3出,j,0,0,0,-5,因为j全0,且1=0,则有无穷多最优解。 所以：X*=(0,80/3,20,0,0),Z*=1700,例:,0,-10,25,j,1,1,0,0,-,50, ,x1入，x4出,j,0,2,0,-1,因为2=2,且ai2全小于0所以：无界,例:,26