1、第五节第五节 单纯形法的进一步讨论单纯形法的进一步讨论一、大M法二、两阶段法-人工变量法人工变量法人工变量法人工变量法问题：线性规划问题：线性规划问题化为标准形时，问题化为标准形时，若约束条件的系数若约束条件的系数矩阵中不存在单位矩阵中不存在单位矩阵，如何构造矩阵，如何构造初始可行基？初始可行基？人工变量法人工变量法加入加入人工变量人工变量设线性规划问题的标准型为设线性规划问题的标准型为：加入人工变量,构造初始可行基.人工变量法人工变量法系数矩阵为系数矩阵为单位矩阵，单位矩阵，可构成初始可构成初始可行基。可行基。约束条件已改变，目标函数如何调整？人工变量法人工变量法“惩罚”人工变量！（1）大M
2、法（2）两阶段法一、大一、大 M M 法法n n人工变量在目标函数中的系数为-M,其中，M 为任意大的正数。目标函数中添加“罚因子”-M（M是任意大的正数）为人工变量系数，只要人工变量0，则目标函数不可能实现最优。例例:求解线性规划问题求解线性规划问题一、大一、大 M M 法法 一、大一、大 M M 法法解:l加入松弛变量和剩余变量进行标准加入松弛变量和剩余变量进行标准 化化,加入人工变量构造初始可行基加入人工变量构造初始可行基.n n求解结果出现检验数非正n n若基变量中含非零的人工变量，若基变量中含非零的人工变量，则无可行解；则无可行解；n n 否则，有最优解。否则，有最优解。一、大一、大
3、 M M 法法l用单纯形法求解（见下页）。用单纯形法求解（见下页）。目标函数中添加“罚因子”-M为人工变量系数，只要人工变量0，则目标函数不可能实现最优。1 -2 1 -4 1 2 -2 0 1 3-63-6M M-1 3M-1M M-1 3M-1 3 -1 -1 x x1 x x2 x x3 0 x x4 11-M x x6 3 -M x x7 1C j-Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x x4 x x5 11 3/2 1 0 0 1 0 0 1 0 0 -M-M x x6 x x7 表表1（初始单纯形表）（初始单纯形表）一、大一、大 M M 法法
4、（单纯形法求解单纯形法求解）3 -2 0 0 1 0 -2 0 1 1 1 M M-1-1 0 0 3 -1 -1x x1 x x2 x x3 0 x x4 10-M x x6 1 -1 x x3 1C j-Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x x4 x x5 1 0 -1 1 -2 0 1 0 1 1-3 3M M-M-M x x6 x x7 一、大一、大 M M 法法（单纯形法求解）（单纯形法求解）表表2 3 0 0 0 1 0 -2 0 1 1 0 0 3 -1 -1 x x1 x x2 x x3 0 x x4 12-1 x x2 1 -1 x
5、x3 1C j-Z j C j CB XB b 1 -2 0 -1 0 0 0 -1 0 0 x x4 x x5 4 i 2 -5 1 -2 0 1 1-1-M-1M-1-M-M-M-M x x6 x x7 表表3一、大一、大 M M 法法（单纯形法求解）（单纯形法求解）1 0 0 0 1 0 0 0 1 0 0 0 3 -1 -1 x x1 x x2 x x3 3 x x1 4-1 x x2 1 -1 x x3 9 2 C j CB XB b1/3 -2/3 0 -1 2/3 -4/3-1/3 -1/3 0 0 x x4 x x5 2/3 -5/3 1 -2 4/3 -7/3 1/3-1/3
6、-M 2/3-MM 2/3-M-M-M x x6 x x7 表表4一、大一、大 M M 法法（单纯形法求解）（单纯形法求解）最优解为最优解为最优解为最优解为目标函数目标函数目标函数目标函数值值值值 z=2z=2检验数均非正，此检验数均非正，此为最终单纯形表为最终单纯形表M在计算机上处理困难。分阶段处理先求初始基，再求解。二、两阶段法二、两阶段法二、两阶段法二、两阶段法n n第一阶段:构造如下的线性规划问题人工变量的人工变量的系数矩阵为系数矩阵为单位矩阵，单位矩阵，可构成初始可构成初始可行基。可行基。目标函数仅含目标函数仅含目标函数仅含目标函数仅含人工变量，并要求人工变量，并要求人工变量，并要求
7、人工变量，并要求实现最小化。实现最小化。实现最小化。实现最小化。若其最优解的若其最优解的若其最优解的若其最优解的目标函数值不为目标函数值不为目标函数值不为目标函数值不为0 0，也即最优解的基，也即最优解的基，也即最优解的基，也即最优解的基变量中含有非零的变量中含有非零的变量中含有非零的变量中含有非零的人工变量，则原线人工变量，则原线人工变量，则原线人工变量，则原线性规划问题无可行性规划问题无可行性规划问题无可行性规划问题无可行解。解。解。解。用单纯形法求解上述问题用单纯形法求解上述问题,若若=0,进入第二阶段进入第二阶段,否则否则,原问题无可行原问题无可行解。解。n n第二阶段：去掉人工变量，
8、还原目标函第二阶段：去掉人工变量，还原目标函数系数，做出初始单纯形表。数系数，做出初始单纯形表。用单纯形法求解即可。用单纯形法求解即可。二、两阶段法二、两阶段法下面举例说明，仍用大M法的例。例：二、两阶段法二、两阶段法 二、两阶段法二、两阶段法l构造第一阶段问题并求解构造第一阶段问题并求解解：解：用单纯形法求解用单纯形法求解二、两阶段法二、两阶段法（第一阶段、求第一阶段、求min min ）1 -2 1-4 1 2 -2 0 1 -6 1 3 0 0 0 x x1 x x2 x x3 0 x x4 11-1 x x6 3 -1 x x7 1 C i CB XB b 1 0 0 0 -1 1 0
9、 0 0 0 -1 0 0 0 -1 x x4 x x5 x x6 0 11 0 3/2 1 1 0 -1 x x7 i 表表1 -1 -2 1 1 -3 -1 x x7 3 -2 0 0 1 0 -2 0 1 0 1 0 0 0 0 x x1 x x2 x x3 0 x x4 10-1 x x6 1 0 x x3 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 x x4 x x5 x x6二、两阶段法二、两阶段法（第一阶段、求第一阶段、求min min ）表表2 -5 4 -2 -1 -1 -1 x x7 3 0 0 0 1 0 -2 0 1 0
10、 0 0 0 0 0 x x1 x x2 x x3 0 x x4 12 0 x x2 1 0 x x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 -1 0 0 -1 x x4 x x5 x x6二、两阶段法二、两阶段法（第一阶段、求第一阶段、求min min ）表表3：最终单纯形表：最终单纯形表第第二二阶阶段段不含人工不含人工变量且变量且=0=0二、两阶段法二、两阶段法第二阶段第二阶段 将将将将去去去去掉掉掉掉人人人人工工工工变变变变量量量量，还还还还原原原原目目目目标标标标函函函函数数数数系系系系数数数数，做做做做出出出出初初初初始始始始单单单单纯纯纯纯形形
11、形形表表表表。3 0 0 0 1 0 -2 0 1 3 -1 -1 x x1 x x2 x x3 0 x x4 12-1 x x2 1-1 x x3 1 C i CB XB b 1 -2 4 0 -1 -0 0 -0 0 x x4 x x5 1 0 0 0 -1二、两阶段法二、两阶段法 1 0 0 0 1 0 0 0 1 3 -1 -1 x x1 x x2 x x3 3 x x1 4-1 x x2 1-1 x x3 9 C i CB XB b 1/3 -2/3 0 -1 2/3 -4/3 0 0 x x4 x x5 第二阶段第二阶段 0 0 0 -1/3 -1/3最优解为最优解为最优解为最优解
12、为目标函数目标函数目标函数目标函数值值值值 z=2z=2单纯形法计算中的几个问题单纯形法计算中的几个问题l1、目标函数极小化时解的最优性判断、目标函数极小化时解的最优性判断 只需用检验数 作为最优性的标志。l2、无可行解的判断、无可行解的判断 当求解结果出现所有 时，如基变量仍 含有非零的人工变量（两阶段法求解时第一阶 段目标函数值不等于0），则问题无可行解。3 3、退化、退化基可行解中存在基变量基可行解中存在基变量=0=0的解的解退化解退化解 换入变量和换出变量的换入变量和换出变量的BlandBland规则规则选择 中下标最小的非基变量 为换入变量,这里:当按 规则计算存在两个和两个以上最小比值时,选下标最小的基变量为换出变量。单纯形法计算中的几个问题单纯形法计算中的几个问题作业作业习题一P1271、5(1)(6)6(1)(2)7(2)8(2)(4)9(1)(3)10(4)第四节第四节 单纯形法的进一步讨论单纯形法的进一步讨论
