单纯形法大M法求解线性规划问题.ppt

* C -3 -2 -1 0 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 x8 θ 0 -M -M x4 x7 x8 6 4 3 1 1 1 1 0 0 0 0 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1 6/1 - 3/1 Z’ -7M -6-4M -15-M -3+M -2+M -1-2M 0 -M -M 0 0 0 -M -2 x4 x7 x2 3 4 3 1 0 2 1 0 1 0 -1 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1 3/1 4/1 - Z’ Z’ -3+M 0 -3-M 0 -M -2 0 2-M -3 -M -2 x1 x7 x2 3 1 3 1 0 2 1 0 1 0 -1 0 0 -3 -1 -1 -1 1 1 0 1 -1 0 0 -1 0 1 0 0 3-3M 3-M -M 1-M 0 -1 在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人工变量x7=1为基变量，所以原线性规划不存在可行解。 * 无最优解 无最优解与无可行解时两个不同的概念。 无可行解是指原规划不存在可行解，从几何的角度解释是指 线性规划问题的可行域为空集； 无最优解则是指线性规划问题存在可行解，但是可行解的目 标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为有限最优解，或无界解。 判别方法：无最优解判别定理 　　在求解极大化的线性规划问题过程中，若某单纯形表的检验 行存在某个大于零的检验数，但是该检验数所对应的非基变量 的系数列向量的全部系数都为负数或零，则该线性规划问题 无最优解， 可以 可以 * 例7、试用单纯形法求解下列线性规划问题： 解：引入松弛变量x3,x4化为标准型 C 2 2 0 0 θ C XB B x1 x2 x3 x4 0 X3 1 -1 1 1 0 0 X4 2 -1/2 1 0 1 Z 0 2 2 0 0 因 但 所以原问题 无最优解 * 退化解 　　当线性规划问题的基本可行解中有一个或多个基变量取零值时，称此基本可行解为退化解。 产生的原因：在单纯形法计算中用最小比值原则确定换出变量时，有时存在两个或两个以上相同的最小比值θ，那么在下次迭代中就会出现一个甚至多个基变量等于零。 遇到的问题：当某个基变量为零，且下次迭代以该基变量作为换出变量时，目标函数并不能因此得到任何改变（由旋转变换性质可知，任何一个换入变量只能仍取零值，其它基变量的取值保持不变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完全相同。从几何角度来解释，这两个退化的基本可行解对应线性规划可行域的同一个顶点， 解决的办法：最小比值原则计算时存在两个及其以上相同的最小比值时，选取下标最大的基变量为换出变量，按此方法进行迭代一定能避免循环现象的产生（摄动法原理）。 * 例8、求解下述线性规划问题： 解：引入松弛变量 　　　　化标准型 * 0 0 0 -24 2 -80 3 0 Z -5 -6 0 -42 0 -8 0 5 Z 1 0 0 0 1 0 0 1 x3 2 1 2 0 6 0 -24 1 1 x1 3 3 2 1 30 0 -8 0 3 x5 0 0 -3 0 -