3.194单纯形法(人工变量法）3.19.ppt

①目标求极大值 ②变量非负 ③右端项非负 ④全部等式约束 一、单纯形法的基本原理 （一）基本变量： 如果变量xj在某一方程中系数为1，而在其它一切方程中的系数为零，则称xj为该方程中的基本变量。否则为非基本变量。 （二）基本解： 在典型方程中，设非基本变量为零，求解基本变量得到的解，称为基本解 。 （三）基本可行解： 基本变量为非负的一组基本解称为基本可行解 。 规范形式—典型方程组(p-59) 最优性的检验与解的判别(p-59) 则: 检验数 对线性规划问题的实际意义是： 表示当变量xj 增加1个单位时，目标函数的增加量；其经济意义表示相对利润．当 0时，说明非基本变量增加1个单位，目标函数可以增加，即现在的函数值不是最优，还能增加．这时要将某个非基本变量换到基本变量中去（称为进基变量）．为了使目标函数值增长最快，所以应选择检验数最大的一项所对应的非基本变量进基, 得到最优解或 证明最优解不存在 单纯形法原理： 第一步：引入非负的松弛变量，将LP化为标准形式 第二步：寻求初始可行基，确定基变量 第三步：写出初始基本可行解和相应的目标函数值 1、分析用非基变量表示目标函数的表达式 通常把非基变量前面的系数叫做“检验数”（非基变量前面的系数均为正数时，任何一个非基变量进基都能使Z值增加） 2、选哪一个非基变量进基 任何一个正检验数对应的非基变量？ 最大正检验数对应的非基变量 ？ 排在最前面的正检验数对应的非基变量？ 3、确定出基变量（最小比值原则） 4、基变换，写出新的用非基变量表示基变量的表达式 5、写出新的用非基变量表示目标函数的表达式 检验数仍有正的，返回（1）进行讨论，当用非基变量表示目标函数的表达式中，检验数全部非正时，当前基本可行解就是最优解。 例8 某制药厂生产甲、乙两种药品，它们均须在A、B、C三种设备上加工，每种设备的使用时间，每吨药品的加工时间以及所获利润见下表，甲、乙药品各生产多少吨，可使该厂所获利润最大？ 单纯形法的基本步骤: 1．建立初始单纯形表 ----确定初始基本可行解 确定基变量、非基变量以及初始基本可行解和目标函数的值。 单纯形法的基本步骤: 1．建立初始单纯形表 ----确定初始基本可行解 确定基变量、非基变量以及初始基本可行解和目标函数的值。 单纯形法求解中的特殊情况 1．最终产生最优值的单纯形表中，某一非基本变量的检验数＝0，意味着作任何增大，目标函数的最优值不变．此时线性规划问题的最优解并不唯一，有多重最优解． （见下面例题） 单纯形表迭代 在选择进基变量和出基变量时作以下规定： ① 在选择进基变量时，在所有 ?j 0的非基变量中选取下标最小的进基； ② 当有多个变量同时可作为出基变量时，选择下标最大的那个变量出基。这样就可以避免出现循环,当然，这样可能使收敛速度降低。 三、大M法 先将约束条件标准化，再引入非负的人工变量，以人工变量作为初始基变量，其对应的系数列向量构成单位矩阵，称为“人造基” 三、大M法 一般情况的处理：主要是讨论初始基本可行解不明显时，常用的方法。 考虑一般问题： 引入人工变量 xn+i ≥ 0，i = 1 ,…, m； a11 x1+ a12 x2+ … + a1n xn+ xn+1 = b1 a21 x1+ a22 x2+ … + a2n xn + xn+2 = b2 … am1 x1+ am2 x2+ … + amn xn + xn+m = bm x1, x2 ，...， xn , xn+1, …, xn+m ≥ 0 引入人工变量 xn+i ≥ 0 （i = 1 , … , m）及充分大正数 M 。得到： 1．建立初始单纯形表---确定初始基本可行解 a11 x1+ a12 x2+ … + a1n xn+ xn+1 = b1 a21 x1+ a22 x2+ … + a2n xn + xn+2 = b2 … am1 x1+ am2 x2+ … + amn xn + xn+m = bm x1