运筹学第二单纯形法.ppt

*人工变量法（也称大M法）针对标准形约束条件的系数矩阵中不含单位矩阵的处理方法。例6用单纯形法求解LP问题单纯形的进一步讨论第30页，共73页，星期日，2025年，2月5日*解：先将其化为标准形式再强行加上人工变量，使其出现单位矩阵：第31页，共73页，星期日，2025年，2月5日*但这样处理后：①不易接受。因为是强行引进，称为人工变量。它们与不一样。称为松弛变量和剩余变量，是为了将不等式改写为等式而引进的，而改写前后两个约束是等价的。②人工变量的引入一般来说是前后不等价的。只有当最优解中，人工变量都取值零时（此时人工变量实质上就不存在了）才可认为它们是等价的。处理办法：把人工变量从基变量中赶出来使其变为非基变量。为此，发明者建议把目标函数作如下处理：第32页，共73页，星期日，2025年，2月5日*其中M为任意大的实数，“M”称为“罚因子”。用意：只要人工变量取值大于零，目标函数就不可能实现最优。对此单纯形矩阵作初等行变换，有：第33页，共73页，星期日，2025年，2月5日*×－M×－M×（-1）×（-3）×（4M）×1/6第34页，共73页，星期日，2025年，2月5日*×3/2×（-1/3）×（3）第35页，共73页，星期日，2025年，2月5日*至此，检验行已没有负数，当前解即为最优解。最优值为：去掉人工变量，即得原LP问题的最优解：第36页，共73页，星期日，2025年，2月5日*⑴最优解判别定理：所有检验数≥0；人工变量为0⑵无穷多最优解判别定理：所有检验数≥0；人工变量为0；存在某个非基变量的检验数为0⑶无可行解判别：所有检验数≥0；人工变量≠0(4)无界解判别定理：有一个非基变量的检验数＜0,但该数对应的列中没有正元素；人工变量为0解的判别定理：第37页，共73页，星期日，2025年，2月5日*单纯形法步骤一、构造初始可行基1、引入附加变量，化为标准型2、必要时引入人工变量3、目标函数中，附加变量系数为0，人工变量则为M二、求基本可行解1、用非基变量表示基变量和目标函数式2、求出一个基本可行解及相应Z值三、最优性检验依据:检验数及判别定理四、基变换1、换入基的确定：检验数负值中最小的2、换出基的确定：最小非负比值规则返回步骤二第38页，共73页，星期日，2025年，2月5日*2.2单纯形法的表格形式

书例2.1P18第39页，共73页，星期日，2025年，2月5日*作业P791.3（2），1.7（1）第40页，共73页，星期日，2025年，2月5日*大M法目标是尽快把人工变量从基变量中全部“赶”出去（如果能全部“赶”出去的话）。所用方法除了大M法外，还有下面的两阶段法。两阶段法用大M法处理人工变量时，若用计算机处理，必须对M给出一个较大的具体数据，并视具体情况对M值作适当的调整。为了克服这一麻烦，下面的两阶段法将问题拆成两个LP问题分两个阶段来计算：2.3大M法和两阶段法第41页，共73页，星期日，2025年，2月5日*两阶段法的第一阶段求解一个目标中只包含人工变量的LP问题，即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数（一般取1），在保持原问题约束不变的情况下求这个目标函数极小化的解。显然在第一阶段中，当人工变量取值为0时，目标函数值也为0。这时候的最优解就是原问题的一个基可行解。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，表明原LP问题无可行解。第42页，共73页，星期日，2025年，2月5日*第二阶段：求解原线性规划问题的最优解。以第一阶段的最终单纯形表为基础，去掉人工变量，目标函数换为原问题的目标函数，得到第二阶段的初始表，继续迭代求解。第43页，共73页，星期日，2025年，2月5日*⑴若求得的单纯形矩阵中，所有人工变量都处在非基变量的位置。即及。则从第1阶段去掉人工变量后，即为原问题的初始单纯形矩阵。并进入第2阶段。第一阶段求解第一个线性规划：第44页，共73页，星期日，2025年，2月5日*⑵若第一阶段所求得的单纯形中仍含有（解）非零的人工变量，则说明原问题无可行解。不再进入第2阶段。因此两阶段法的第1阶段求解有两个目的：一为判断原问题有无可行解。二，若有，则得原问题的一个初始可行基，再对原问题进行第2阶段的计算。第4