第4章 单纯形法

第四章 单 纯 形 法 1 单纯形法的基本思路和原理 2 单纯形法的表格形式 3 求目标函数值最小的线性规划的问题的单纯形表解法 4 几种特殊情况11 单纯形法的基本思路和原理单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是 ,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。2通过第二章例 1的求解来介绍单纯形法 :在加上松弛 变 量之后我 们 可得到 标 准型如下： 目 标 函数： max 50x1+100x2约 束条件： x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250.xj0 （ j=1， 2） ,sj0 （ j=1， 2,3）3它的系数矩阵 ,其中 pj为系数矩阵 A第 j列的向量。 A的秩为 3,A的秩 m小于此方程组的变量的个数 n， 为了找到一个初始基本可行解，先介绍以下几个线性规划的基本概念。 可行解 ：满足所有约束条件的解 最优解 ：是目标函数达到最大（小）的可行解 非可行解 ：至少一个约束条件不被满足的解 可行域 ：所有可行解的集合（包括边界） 顶点可行解 （ CPF）：位于可行域顶点的解基 ：已知 A是约束条件的 mn 系数矩阵，其秩为 m。若 B是 A中 mm 阶非奇异子矩阵（即可逆矩阵），即子矩阵 B的行列式不为零，是矩阵 A中的一个 满秩子矩阵 ，则称 B是线性规划问题中的一个 基 。1 单纯形法的基本思路和原理对于线性方程组：当 R（ A） = R（ A）=r=n时，方程组有唯一解；当 R（ A） = R（ A） =r3，因此选择增加 x2。即选择检验数中最大的正数，故选 x2为入基变量（ x2不再为 0，故由非基变量变成了基变量。） 入基变量确定原则： 尽快地能找到最优解。221 单纯形法的基本思路和原理（ 2） 出基变量的确定（确定在何处停下） 在确定了 x2为入基变量之后，我们要在原来的 3个基变量 s1， s2， s3中确定一个出 基变量，也就是确定哪一个基变量变成非基变量呢？ x2增加， Z会随之增加 ，因此， 在可行域的范围内我们希望移动的足够远以尽可能地增大 x2的值。 在保持非基变量 x1=0的前提下，增加 x2会改变其他变量的值 ,但 要保证求出的是可行解 ，即满足约束方程组的 非负解。非基变量（包括入基变量）是非负的，但是我们需要考察在基变量非负约束下 x2最多能增加多少。即要保证 x3、 x4、 x5都非负。x1 +x3 =42x2 +x4 =123x1+2x2 +x5=18x3=4x4=12-2x2x5=18-2x223管 理 运 筹 学 x3=40 对 x2增加没有上限限制 x4=12-2x20 x212/2=6 x5=18-2x20 x218/2=9 因此， x2只能增加至 6，此 时 x4减少 为 0。若增加x2的 值 超 过 6，会使 x4变为负 数，得到的 为 非基本可行解。 这 个 计 算称 为 最小比 值试 算或 法 则 。 如果某一个 约 束方程中入基 变 量的系数 为 0或者 为负值 ，我 们 不予考 虑 ； 对 于入基 变 量的系数 严 格为 正的 约 束方程，察看 右端 项 与入基 变 量系数的比 值 。方程中 拥 有比 值 最小的基 变 量会随着入基变 量 值 的增加首先减小到 0。 这 个基 变 量 变为 0意味着在一个基本可行解中它 变 成了非基 变 量。 这个 变 量被称 为 出基 变 量。 出基 变 量的确定原 则 ， 保 证 解非 负 。24管 理 运 筹 学 4、求新的基本可行解。 新的非基变量： x1=0， x4=0。 代入求解基变量的值， 可以直接代入求解，也可以先对方程组进行行初等变换 ，使得每一个基变量从原来所在的方程以外的其他方程中消去，而在该方程中系数为 1，然后进行求解。后一种方法在单纯形表中采用。具体变换方法： 把左边 x4的系数变为右边 x2的系数。 Z-3x1-5x2 =0x1 +x3 =42x2 +x4 =123x1+2x2 +x5=18Z-3x1 +5/2x4 =30x1 +x3 =4x2 +1/2x4 =123x1 -x4 +x5=18非常直观地得到基本可行解和目标函数值 25管 理 运 筹 学 5、最优性检验。 从上面也可以很容易得到用非基变量来表示目标函数的形式。 Z=30 + 3x1 - 5/2x4 从 0开始增加任意一个非基变量（同时调整基变量的值以继续满足约束）都会导致移向两个相邻的基本可行解的其中一个。因为 x1有正系数，增加 x1会导致相邻可行解优于当前基本可行解，因此当前解就不是最优。 下面请大家自己动手进行第二次迭代和最优性检验等运算。26管 理 运 筹 学特殊情况 入基变量的相持：如上例中 z=3x1+3x2 也就是有两个或以上的非基变量的检验数相同，可以任意选择一个入基。最终都会求得最优解，不存在一种便捷方法能预先指出哪个选择会更快得到最优解。 出基变量的相持：入基变量增加时，会使多个基变量同时为 0。即方程右端项与入基变量系数比值相等（正数）。值为 0的基变量称为退化的变量。（后面会详细讲） 无出基变量：当入基变量可以无限增加，而不会造成当前任何一个基变量为负值。即约束条件无法阻止目标函数值得无限增加。说明 Z无界 。272 单纯形法的表格形式在讲解单纯形法的表格形式之前，先从一般数学模型里推导出检验数 的表达式。可行基为 m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前 m列是单位矩阵）：以下用 表示基变量，用 表示非基变量。282 单纯形法的表格形式把第 i个约束方程移项，就可以用非基变量来表示基变量 xi，把以上的表达式带入目标函数，就有其中：292 单纯形法的表格形式上面假设 x1,x2, xm是基变量，即第 i行约束方程的基变量正好是 xi，而经过迭代后，基将发生变化，计算 zj的式子也会发生变化。如果迭代后的第 i行约束方程中的基变量为 xBi，与 xBi相应的目标函数系数为 cBi， 系数列向量为 则其中， (cB)是由第 1列第 m行各约束方程中的基变量相应的目标函数依次组成的有序行向量。单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵，而其计算的方法