《运筹学胡运权清华版105单纯形法的进一步讨论ppt课件》由会员分享，可在线阅读，更多相关《运筹学胡运权清华版105单纯形法的进一步讨论ppt课件（34页珍藏版）》请在金锄头文库上搜索。
1、第五第五节 单纯形法的形法的进一步一步讨论一、大一、大M M法法二、两阶段法二、两阶段法三、单纯形法计算中的几个问题三、单纯形法计算中的几个问题人工变量法人工变量法人工变量法人工变量法问题：线性规划问题：线性规划问题化为规范型时，问题化为规范型时，假设约束条件的系数假设约束条件的系数矩阵中不存在单位矩阵中不存在单位矩阵，如何构造矩阵，如何构造初始可行基？初始可行基？ 人工变量法人工变量法参与参与人工变量人工变量设线性规划问题的规范型为：设线性规划问题的规范型为： 参与人工变量参与人工变量, ,构造初始可行基构造初始可行基. . 人工变量法人工变量法系数矩系数矩阵为阵为单单位矩位矩阵阵，可构成初
2、始可构成初始可行基。可行基。 约束条件已改动，目的函数如何调整？人工变量法人工变量法“惩罚 人工变量！1大M法2两阶段法一、大一、大 M M 法法l人工人工变量在目的函数中的系数量在目的函数中的系数为 -M, -M, l 其中，其中，M M 为恣意大的正数。恣意大的正数。目的函数中添加“罚因子-MM是恣意大的正数为人工变量系数，只需人工变量0，那么目的函数不能够实现最优。例例6: 求解线性规划问题求解线性规划问题一、大一、大 M M 法法 一、大一、大 M M 法法解解: :l参与松弛变量和剩余变量化规范型参与松弛变量和剩余变量化规范型 一、大一、大 M M 法法l参与人工变量构造初始可行基参
3、与人工变量构造初始可行基. . l求解结果出现检验数非正求解结果出现检验数非正l假设基变量中含非零的人工变量，假设基变量中含非零的人工变量，l 那么无可行解；那么无可行解；l 否那么，有最优解。否那么，有最优解。一、大一、大 M M 法法l用单纯形法求解见下页。用单纯形法求解见下页。目的函数中添加“罚因子-M为人工变量系数，只需人工变量0，那么目的函数不能够实现最优。一、大一、大 M M 法单纯形法法单纯形法求解求解CB XB bC jx1 x2 x3 x4 x5 x6 x7x1 x2 x3 x4 x5 x6 x7 -3 0 1 0 0 -M -M 0 x4 4 -M x6 1 -M x7 9
4、 -2 1 -1 0 -1 1 0 1 1 1 1 1 1 1 1 0 0 00 0 0 0 3 1 0 0 3 1 0 0 0 10 0 1-2M-3 4M 1 0 -M 0 0 413C j - Z j初始表表一初始表表一一、大一、大 M M 法单纯形法法单纯形法求解求解CB XB bC jx1 x2 x3 x4 x5 x6 x7x1 x2 x3 x4 x5 x6 x7 -3 0 1 0 0 -M -M 0 x4 3 0 x2 1 -M x7 6 -2 1 -1 0 -1 1 0 3 0 2 1 3 0 2 1 1 -1 0 1 -1 0 6M-3 0 4M+1 0 3M -4M 011C
5、 j - Z j迭代迭代1表二表二6 0 4 0 3 -3 1出现两个或两个出现两个或两个以上最小比值，以上最小比值，任选一个任选一个一、大一、大 M M 法单纯形法法单纯形法求解求解CB XB bC jx1 x2 x3 x4 x5 x6 x7x1 x2 x3 x4 x5 x6 x7 -3 0 1 0 0 -M -M 0 x4 0 0 x2 3 -3 x1 1 0 0 3 0 3/2 -M-3/2 M+1/2 93/2C j - Z j迭代迭代2表三表三0 0 0 1 - - - 0 1 1/3 0 0 0 1/31 0 2/3 0 - 1/6 一、大一、大 M M 法单纯形法法单纯形法求解求
6、解CB XB bC jx1 x2 x3 x4 x5 x6 x7x1 x2 x3 x4 x5 x6 x7 -3 0 1 0 0 -M -M 0 x4 0 0 x2 5/2 1 x3 3/2 -9/2 0 0 0 -3/4 -M+3/4 M-1/4C j - Z j迭代迭代3表四表四0 0 0 1 - - - - 1 0 0 -1/4 1/4 1/43/2 0 1 0 3/4 -3/4 1/4最最最最优优解解解解为为目的函数目的函数目的函数目的函数值值 z=3/2 z=3/2 z=3/2 z=3/2M在计算机上处置困难。分阶段处置先求初始基，再求解。二、两阶段法二、两阶段法二、两阶段法二、两阶段法
7、l第一第一阶段段: : 构造如下的构造如下的线性性规划划问题人工人工变变量的量的系数矩系数矩阵为阵为单单位矩位矩阵阵，可构成初始可构成初始可行基。可行基。 目的函数仅含人工变量，并要务虚现最小化。 假设其最优解的目的函数值不为0，也即最优解的基变量中含有非零的人工变量，那么原线性规划问题无可行解。 用用单纯形法求解上述形法求解上述问题,假假设=0,进入第二入第二阶段段,否那么否那么,原原问题无可行解。无可行解。第二第二阶段：去掉人工段：去掉人工变量，复原目的函数量，复原目的函数系数，做出初始系数，做出初始单纯形表。形表。 用用单纯形法求解即可。形法求解即可。二、两阶段法二、两阶段法下面举例阐明
8、，仍用大M法的例。例：二、两阶段法二、两阶段法 二、两阶段法二、两阶段法l构造第一阶段问题并求解构造第一阶段问题并求解解：解：用单纯形法求解用单纯形法求解二、两二、两阶段法段法第一第一阶段、求段、求min min CB XB bC jx1 x2 x3 x4 x5 x6 x7x1 x2 x3 x4 x5 x6 x7 0 0 0 0 0 -1 -1 0 x4 4 -1 x6 1 -1 x7 9 -2 1 -1 0 -1 1 0 1 1 1 1 1 1 1 1 0 0 00 0 0 0 3 1 0 0 3 1 0 0 0 10 0 1 -2 4 0 0 -1 0 0 413C j - Z j表一表一
9、二、两二、两阶段法段法第一第一阶段、求段、求min min CB XB bC jx1 x2 x3 x4 x5 x6 x7x1 x2 x3 x4 x5 x6 x7 0 0 0 0 0 -1 -1 0 x4 3 0 x2 1 -1 x7 6 -2 1 -1 0 -1 1 0 3 0 2 1 3 0 2 1 1 -1 0 1 -1 0 6 0 4 0 3 -4 011C j - Z j6 0 4 0 3 -3 1表二表二二、两二、两阶段法段法第一第一阶段、求段、求min min 表三：最终单纯形表表三：最终单纯形表不含人工不含人工变量且变量且=0CB XB bC jx1 x2 x3 x4 x5 x6
10、 x7x1 x2 x3 x4 x5 x6 x7 0 0 0 0 0 -1 -1 0 x4 0 0 x2 3 0 x1 1 0 0 0 0 0 -1 -1 C j - Z j0 0 0 1 - - - 0 1 1/3 0 0 0 1/31 0 2/3 0 - 1/6 第第二二阶段段二、两阶段法二、两阶段法第二第二阶段段 去去去去掉掉掉掉人人人人工工工工变变变变量量量量，复复复复原原原原目目目目的的的的函函函函数数数数系系系系数数数数，做做做做出出出出初初初初始始始始单单单单纯纯纯纯形形形形表表表表。0 0 3 0 3/2CB XB bC jx1 x2 x3 x4 x5x1 x2 x3 x4 x5
11、 0 x4 0 0 x2 3 -3 x1 1C j - Z j0 0 0 1 -0 1 1/3 0 01 0 2/3 0 -3 0 1 0 093/2二、两阶段法二、两阶段法第二第二阶段段CB XB bC jx1 x2 x3 x4 x5x1 x2 x3 x4 x5 -3 0 1 0 0 0 x4 0 0 x2 5/2 1 x3 3/2 -9/2 0 0 0 -3/4C j - Z j0 0 0 1 - 1 0 0 -1/43/2 0 1 0 3/4最最最最优优解解解解为为目的函数目的函数目的函数目的函数值值 z=3/2 z=3/2 z=3/2 z=3/2单纯形法计算中的几个问题单纯形法计算中的
12、几个问题l1、目的函数极小化时解的最优性判别、目的函数极小化时解的最优性判别l 只需用检验数只需用检验数 作为最优性的标作为最优性的标志。志。2、退化、退化 单纯形法形法计算中用算中用规那么确定出基那么确定出基变量量时，有有时存在两个以上一存在两个以上一样的最小比的最小比值，这样在下一在下一次迭代中就有一次迭代中就有一 个或几个基个或几个基变量等于量等于0，这就出就出现退化解。退化解。 基可行解中存在基基可行解中存在基变量量=0的解的解退化解退化解单纯形法计算中的几个问题单纯形法计算中的几个问题例：例6大M法求解中表三、表四所给出的基可行 解就是退化解单纯形法计算中的几个问题单纯形法计算中的几
13、个问题退化缘由：能够有多余的约束，从而使得多个基可行解对应于同一个顶点。退化后果：能够导致的最差情形循环。 防止循环的防止循环的Bland规那么规那么选择选择 中下标最小的非基变量中下标最小的非基变量 为为换入变量换入变量, 即即:当按当按 规那么计算存在两个和两个以上最规那么计算存在两个和两个以上最小比值时小比值时,选下标最小的基变量为换出变选下标最小的基变量为换出变量。量。单纯形法计算中的几个问题单纯形法计算中的几个问题 注注1：假设一个线性规划问题的一切基可行解非退：假设一个线性规划问题的一切基可行解非退化，那么称这个线性规划问题非退化。化，那么称这个线性规划问题非退化。 注注2：前面引
14、见的线性规划问题独一解、无穷多解、：前面引见的线性规划问题独一解、无穷多解、无界解的判别定理仅适用于非退化的线性规划问题。无界解的判别定理仅适用于非退化的线性规划问题。单纯形法计算中的几个问题单纯形法计算中的几个问题单纯形法计算中的几个问题单纯形法计算中的几个问题l3、无可行解的判别、无可行解的判别l 当求解结果出现一切当求解结果出现一切 时，如基变量仍时，如基变量仍l 含有非零的人工变量两阶段法求解时第一阶含有非零的人工变量两阶段法求解时第一阶l 段目的函数值不等于段目的函数值不等于0，那么问题无可行解。，那么问题无可行解。例例7: 求解线性规划问题求解线性规划问题无可行解举例无可行解举例单纯形法计算中的几个问题单纯形法计算中的几个问题023可行域可行域为空，空， 无可行解无可行解图解图解x1x2单纯形法计算中的几个问题单纯形法计算中的几个问题23 cj 2 1 0 0 -MCB XB b x1 x2 x3 x4 x5 0x3211100 -Mx56220-11 cj-zj 2+2M 1+2M 0 -M 02x1211100 -Mx5200-2-11 cj-zj 0 -1 -2-2M -M 023一切 ，但是基变量中有人工变量，无可行解参与人工变量，用大参与人工变量，用大M法求解法求解
