线性规划 第五讲 单纯形法的进一步讲解(大m法).ppt

上页上页下页下页返回返回第五讲第五讲 单纯形法的进一步讨论单纯形法的进一步讨论一、大M法 二、两阶段法--------人工变量法人工变量法上页上页下页下页返回返回人工变量法问题：线性规划 问题化为标准形时， 若约束条件的系数 矩阵中不存在单位 矩阵，如何构造 初始可行基？ 上页上页下页下页返回返回人工变量法加入 人工变量设线性规划问题的标准型为：上页上页下页下页返回返回加入人工变量,构造初始可行基. 人工变量法上页上页下页下页返回返回约束条件已改变， 目标函数如何调整？人工变量法上页上页下页下页返回返回“惩罚”人工变量！（1）大M法上页上页下页下页返回返回一、大 M 法• 人工变量在目标函数中的系数为 -M, 其中，M 为任意大的正数目标函数中添加“罚因子” -M（M是任意大的正数） 为人工变量系数，只要人 工变量>0，则目标函数 不可能实现最优上页上页下页下页返回返回例: 求解线性规划问题一、大 M 法上页上页下页下页返回返回一、大 M 法解:l加入松弛变量和剩余变量进行标准 化, 加入人工变量构造初始可行基. 上页上页下页下页返回返回• 求解结果出现检验数非正 – 若基变量中含非零的人工变量，则无可行解； – 否则，有最优解。

一、大 M 法l用单纯形法求解（见下页）目标函数中添加“罚因子” -M为人工变量系数，只要人 工变量>0，则目标函数 不可能实现最优上页上页下页下页返回返回1 -2 1-4 1 2 -2 0 1 3-6M M -1 3M-13 -1 -1x1 x2 x30 x4 11-M x6 3 -M x7 1σjC jCB XB b1 0 0 -1 0 0 0 -M 0 0 x4 x5 113/2 1 0 0 1 0 0 1 0 0 - M - Mx6 x7 表1（初始单纯形表）一、大 M 法（单纯形法求解）上页上页下页下页返回返回3 -2 00 1 0 -2 0 1 1 M-1 03 -1 -1x1 x2 x30 x4 10-M x6 1 -1 x3 1σjC jCB XB b1 0 0 -1 0 0 0 -M 0 0 x4 x5 1 0 -1 1 -2 0 1 0 1-3M- M - Mx6 x7 一、大 M 法（单纯形法求解）表2上页上页下页下页返回返回3 0 00 1 0 -2 0 1 1 0 03 -1 -1x1 x2 x30 x4 12-1 x2 1 -1 x3 1σjC jCB XB b1 -2 0 -1 0 0 0 -1 0 0 x4 x5 4i 2 -5 1 -2 0 1 1-M -1 -M- M - Mx6 x7 表3一、大 M 法（单纯形法求解）上页上页下页下页返回返回1 0 00 1 0 0 0 1 0 0 03 -1 -1x1 x2 x33 x1 4-1 x2 1 -1 x3 92C jCB XB b1/3 -2/3 0 -1 2/3 -4/3 -1/3 -1/3 0 0 x4 x5 2/3 -5/3 1 -2 4/3 -7/3 1/3-M 2/3-M- M - Mx6 x7 表4一、大 M 法（单纯形法求解）最优解为最优解为目标函数目标函数 值值 z=2z=2检验数均非正，此 为最终单纯形表上页上页下页下页返回返回单纯形法计算中的几个问题l1、目标函数极小化时解的最优性判断只需用检验数 作为最优性的标志。

l2、无可行解的判断当求解结果出现所有 时，如基变量仍含有非零的人工变量（两阶段法求解时第一阶段目标函数值不等于0），则问题无可行解上页上页下页下页返回返回Ä退化 基可行解中存在基变量=0的解——退化解换入变量和换出变量的Bland规则®选择 中下标最小的非基变量 为换入变 量, 这里:®当按 规则计算存在两个和两个以上最小比 值时,选下标最小的基变量为换出变量单纯形法计算中的几个问题上页上页下页下页返回返回最优解判断小结（用非基变量的检验数）所有 基变量中有 非零人工变量某非基变量 检验数为零唯一最优解无穷多最优解无可行解对任一 有 换基继续YY YYNNN无界解N。