单纯形法、大M法

1、27.01.2021,单纯形法的计算步骤,例1.10 用单纯形法求下列线性规划的最优解,1）将问题化为标准型，加入松驰变量x3、x4则标准型为,27.01.2021,单纯形法的计算步骤,2）求出线性规划的初始基可行解，列出初始单纯形表,检验数,0,0,3,27.01.2021,单纯形法的计算步骤,3）进行最优性检验,如果表中所有检验数 ，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步,4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表,确定换入基的变量。选择 ，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即： ，其对应的xk作

2、为换入变量。 确定换出变量。根据下式计算并选择 ，选最小的对应基变量作为换出变量,27.01.2021,单纯形法的计算步骤,用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。 5）重复3）、4）步直到计算结束为止,27.01.2021,单纯形法的计算步骤,换入列,bi /ai2，ai20,40,10,换出行,将3化为1,5/3,1,18,0,1/3,0,1/3,10,1,1/3,30,30,0,5/3,0,4/3,乘以3/5后得到,1,0,3/5,1/5,18,0,1,1/5,2/5,4,0,0,1,1,最优解,最优值,

3、27.01.2021,单纯形法的计算步骤,例1.11 用单纯形法求解,解：将数学模型化为标准形式,不难看出x4、x5可作为初始基变量，列单纯形表计算,27.01.2021,单纯形法的计算步骤,20,x2,2,1/3,1,5,0,1,20,75,3,0,17,1,3,1/3,0,9,0,2,25,60,x1,1,1,0,17/3,1/3,1,25,0,1,28/9,1/9,2/3,35/3,0,0,98/9,1/9,7/3,最优解,最优值,27.01.2021,单纯形法的进一步讨论人工变量法,一、人工变量法： 前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并

4、不含有单位矩阵，为了得到一组基向量和初始基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大m法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法,1、大m 法 通过引进人工变量，构造一个辅助的线性规划问题，然后由辅助的线性规划问题找出原问题的第一个初始可行基，在此基础上，利用单纯形方法求出原问题的最优解,27.01.2021,单纯形法的进一步讨论人工变量法,例1.10 用大m法解下列线性规划,解：首先将数学模型化为标准形式,系数矩阵中不存在单位矩阵，无法建立初始单纯形表,27.01.2021,单纯形法的进一步讨论人

5、工变量法,故人为添加两个单位向量，得到人工变量单纯形法数学模型,其中：m是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表,27.01.2021,单纯形法的进一步讨论人工变量法,27.01.2021,2、两阶段法 在原来问题引入人工变量后分两个阶段求解线性规划问题的方法。其中，第一阶段在原来问题中引入人工变量，设法构造一个单位阵的初始可行基，另外在目标函数中令非人工变量的系数全部为0，人工变量的系数为1，构造一个新的辅助目标函数。在此基础上，建立辅助线性规划问题。然后运用单纯形方法求解，直到辅助目标函数值为0时

6、为止。第二阶段重新回到原来的问题，以第一阶段得到的可行基为初始可行基，运用单纯形方法以求出原来问题的解,27.01.2021,3)两阶段法的计算步骤 （1）不考虑原问题是否存在基可行解， 引进人工变量，构造辅助线性规划问题。 （2）用单纯形方法求解辅助问题，若辅助问题的目标函数值w 0，则原问题无可行解，停止计算。 （3）若辅助问题目标函数的值w =0，则将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数换原问题的目标函数系数，作为第二阶段的初始表。 4）解的判断同单纯形法,27.01.2021,例4.2用两阶段法求解线性规划问题 min=-3x1+x2+x3 s.t. x1-2x2

7、+x3 11 -4x1+x2+2x3 3 -2x1 +x3 =1 x1,x2,x3, 0 解：先在约束条件中加入人工变量，写出辅助规划问题。min w=x6+x7 s.t. x1-2x2+x3+x4 =11 -4x1+x2+2x3 -x5+x6 =3 -2x1 +x3 +x7 =1 xi0,i=1,2, ,7,27.01.2021,用单纯形法进行第一阶段的计算如下表,27.01.2021,人工变量x6=x7 0，第一阶段目标函数w=0，则 (0，1，1，12，0)t是原线性规划问题的基可行解，转第二阶段的计算,27.01.2021,由表可得最优解为： x1=4， x2=1，x3=9； 目标函数

8、值 z=-2,27.01.2021,单纯形法的进一步讨论人工变量法,解的判别： 1）唯一最优解判别：最优表中所有非基变量的检验数非零,且基变量中无非零的人工变量，则线规划具有唯一最优解。 2）多重最优解判别：最优表中存在非基变量的检验数为零,且基变量中无非零的人工变量，则线则性规划具有多重最优解（或无穷多最优解）。 3）无界解判别：某个k0且aik（i=1，2,m）则线性规划具有无界解。 4）无可行解的判断：当用大m单纯形法计算得到最优解并且存在人工变量0时，则表明原线性规划无可行解。 5）退化解的判别：存在某个基变量为零的基本可行解,27.01.2021,二、退化、循环及其处理方法,1、退化 单纯形法计算中用规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。 2、退化迭代的特点 （1）退化解的基变量中至少有一个取值为0。 （2）退化迭代中基在不断变化但解始终不变。 （3）退化迭代不会引起目标函数值的改进。 3、防止循环迭代的方法 （1）摄动法 （2）字典顺序法 （3）最小下标法,27.01.2