运筹学课件1-6大M两阶段.ppt

《运筹学课件1-6大M两阶段.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、单纯形表复习小结求解思想－－顶点的逐步转移，条件是使目标函数值不断得到改善。表格单纯形法求解步骤第一步：将LP化为标准型，并加以整理。引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。确定初始可行基，写出初始基本可行解第二步：最优性检验计算检验数，检查：所有检验数是否≤0？是——结束，写出最优解和目标函数最优值；还有正检验数——检查相应系数列≤0？是——结束，该LP的解无界！不属于上述两种情况，转入下一步—基变换。确定是停止迭代还是转入基变换？选择（最大）正检验数对应的系数列为主元列，主元列对

2、应的非基变量为换入变量；最小比值对应的行为主元行，主元行对应的基变量为换出变量。第三步：基变换确定进基变量和出基变量。利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，从而得到一张新的单纯形表，返回第二步。第四步换基迭代（旋转运算、枢运算)完成一次迭代，得到新的基本可行解和相应的目标函数值该迭代过程直至下列情况之一发生时停止检验数行全部变为非正值；（得到最优解）或主元列≤0（最优解无界）停止迭代的标志（停机准则）标准型的单纯型算法(1)变换主行(2)变换主列除主元保留为1，其余都置0(3)变换非主行、主列元素aij(包括bi)四角算法公

3、式：标准型的单纯型算法5、迭代过程(4)变换CB，XB(5)计算目标函数、机会成本zj和检验数cjzj6、返回步骤2单纯形法的进一步讨论一、大M法二、两阶段法----人工变量法人工变量法问题：线性规划问题化为标准形时，若约束条件的系数矩阵中不存在单位矩阵，如何构造初始可行基？人工变量法加入人工变量设线性规划问题的标准型为：加入人工变量,构造初始可行基.人工变量法系数矩阵为单位矩阵，可构成初始可行基。约束条件已改变，目标函数如何调整？人工变量法“惩罚”人工变量！（1）大M法（2）两阶段法思路因为人工变量是为了构造初始基本可行解，人为加入原约束方程

4、中的虚拟变量，只有当它们同时等于零，加入人工变量的等式约束才与原约束条件相等。也就是说，若经过基变换，基变量中不再含有非零人工变量，这表示原问题有解；若经过基变换，最终单纯形表中还存在非零人工变量，这表示原问题无可行解。一、大M法人工变量在目标函数中的系数为-M,其中，M为任意大的正数。目标函数中添加“罚因子”M（M是任意大的正数）为人工变量系数，只要人工变量>0，则目标函数不可能实现最优。例:求解线性规划问题一、大M法一、大M法解:加入松弛变量和剩余变量进行标准化,加入人工变量构造初始可行基.求解结果出现检验数非正若基变量中含非零的人工变量，则

5、无可行解；否则，有最优解。一、大M法用单纯形法求解（见下页）。目标函数中添加“罚因子”M为人工变量系数，只要人工变量>0，则目标函数不可能实现最优。1-21-412-2013-6MM-13M-13-1-1x1x2x30x411-Mx63-Mx71Cj-ZjCjCBXBb100-1000-M00x4x5113/2100100100-M-Mx6x7表1（初始单纯形表）一、大M法（单纯形法求解）3-20010-2011M-103-1-1x1x2x30x410-Mx61-1x31Cj-ZjCjCBXBb100-1000-M00x4x510-11-2010

6、1-3M-M-Mx6x7一、大M法（单纯形法求解）表2300010-2011003-1-1x1x2x30x412-1x21-1x31Cj-ZjCjCBXBb1-20-1000-100x4x54i2-51-2011-M-1-M-M-Mx6x7表3一、大M法（单纯形法求解）1000100010003-1-1x1x2x33x14-1x21-1x392CjCBXBb1/3-2/30-12/3-4/3-1/3-1/300x4x52/3-5/31-24/3-7/31/3-M2/3-M-M-Mx6x7表4一、大M法（单纯形法求解）最优解为目标函数值z=2检验数

7、均非正，此为最终单纯形表①最优表中，基变量不包含人工变量，则最优解就是原线性规划的最优解，不影响目标函数的取值；②最优表中，基变量中仍含有人工变量，表明原线性规划的约束条件被破坏，线性规划没有可行解，也就没有最优解！结果M在计算机上处理困难。分阶段处理——先求初始基，再求解。二、两阶段法二、两阶段法第一阶段:构造如下的线性规划问题人工变量的系数矩阵为单位矩阵，可构成初始可行基。目标函数仅含人工变量，并要求实现最小化。若其最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，则原线性规划问题无可行解。用单纯形法求解上述问题,若ω=0,进

8、入第二阶段,否则,原问题无可行解。第二阶段：去掉人工变量，还原目标函数系数，做出初始单纯形表。用单纯形法求解即可。二、两阶段法下面举例说