运筹学-05-单纯形法

管 理 运 筹 学第五章 单 纯 形 法 1 单纯形法的基本思路和原理 2 单纯形法的表格形式 3 求目标函数值最小的线性规划的问题的单纯形表解法 4 几种特殊情况1管 理 运 筹 学1 单纯形法的基本思路和原理单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是 ,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。通过第二章例 1的求解来介绍单纯形法 :在加上松弛 变 量之后我 们 可得到 标 准型如下： 目 标 函数： max 50x1+100x2约 束条件： x1+x2+s1300 ， 2x1+x2+s2400 ， x2+s3250.xj0 （ j=1， 2） ,sj0 （ j=1， 2,3）2管 理 运 筹 学它的系数矩阵 ,其中 pj为系数矩阵 A第 j列的向量。 A的秩为 3,A的秩 m小于此方程组的变量的个数 n， 为了找到一个初始基本可行解，先介绍以下几个线性规划的基本概念。 基 ： 已知 A是约束条件的 mn 系数矩阵，其秩为 m。若 B是 A中 mm 阶非奇异子矩阵（即可逆矩阵），则称 B是线性规划问题中的一个基。基向量 ：基 B中的一列即称为一个基向量。基 B中共有 m个基向量。 非基向量 ：在 A中除了基 B之外的一列则称之为基 B的非基向量。 基变量： 与基向量 pi相应的变量 xi叫基变量，基变量有 m个。1 单纯形法的基本思路和原理3管 理 运 筹 学非基变量： 与非基向量 pj相应的变量 xj叫非基变量，非基变量有 n m个。由 线 性代数的知 识 知道，如果我 们 在 约 束方程 组 系数矩 阵 中找到一个基，令 这 个基的非基 变 量 为 零，再求解 这 个 m元 线 性方程 组 就可得到唯一的解了， 这 个解我 们 称之 为线 性 规 划的基本解。在此例中我 们 不妨找到了 为 A的一个基，令 这 个基的非基 变 量 x ， s2为 零。 这时约 束方程就 变为 基 变 量的 约 束方程 ： 1 单纯形法的基本思路和原理4管 理 运 筹 学x2+s1300 ， x2=400， x2+s3=250.求解得到此线性规划的一个基本解： x1=0， x2=400， s1= 100， s2=0， s3= 150由于在这个基本解中 s1= 100， s3= 150， 不满足该线性规划 s10 ，s30 的约束条件，显然不是此线性规划的可行解，一个基本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行解，并把这样的基叫做可行基。1 单纯形法的基本思路和原理5管 理 运 筹 学一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型中要求 bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如，那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个 bj或等于零。 1 单纯形法的基本思路和原理6管 理 运 筹 学在本例题中我们就找到了一个基是单位矩阵。在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可行基，具体做法在以后详细讲述。 1 单纯形法的基本思路和原理7管 理 运 筹 学二、 最优性检验所谓最优性检验就是判断已求得的基本可行解是否是最优解。 1. 最优性检验的依据 检验数 j一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可以用非基变量来表示基变量，然后用非基变量的表示式代替目标函数中基变量，这样目标函数中只含有非基变量了，或者说目标函数中基变量的系数都为零了。此时目标函数中所有变量的系数即为各变量的检验数，把变量 xi的检验数记为 i。 显然所有基变量的检验数必为零。在本例题中目标函数为 50x1+100x2。 由于初始可行解中 x1， x2为非基变量，所以此目标函数已经用非基变量表示了，不需要再代换出基变量了。这样我们可知 1=50， 2=100， 3=0， 4=0， 5=0。1 单纯形法的基本思路和原理8管 理 运 筹 学1 单纯形法的基本思路和原理 2.最优解判别定理对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验数 0，则这个基本可行解是最优解。下面我们用通俗的说法来解释最优解判别定理。设用非基变量表示的目标函数为如下形式由于所有的 xj的取值范围为大于等于零，当所有的 都小于等于零时，可知 是一个小于等于零的数，要使 z的值最大，显然 只有为零。我们把这些 xj取为非基变量 (即令这些 xj的值为零 )，所求得的基本可行解就使目标函数值最大为 z0。*对于求目标函数最小值的情况，只需把 0改 为 09管 理 运 筹 学1 单纯形法的基本思路和原理三、 基变换通过检验，我们知道这个初始基本可行解不是最优解。下面介绍如何进行基变换找到一个新的可行基，具体的做法是从可行基中换一个列向量，得到一个新的可行基，使得求解得到的新的基本可行解，其目标函数值更优。为了换基就要确定换入变量与换出变量。1. 入基变量的确定 从最优解判别定理知道，当某个 j 0时，非基变量 xj变为基变量不取零值可以使目标函数值增大，故我们要选基检验数大于 0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的 j 0， 则为了使目标函数增加得更大些，一般选其中的 j最大者的非基变量为入基变量，在本例题中 2=100是检验数中最大的正数，故选 x2为入基变量。 10管 理 运 筹 学1 单纯形法的基本思路和原理2. 出基变量的确定 在确定了 x2为入基变量之后，我们要在原来的 3个基变量 s1， s2， s3中确定一个出 基变量，也就是确定哪一个基变量变成非基变量呢？ 如果 把 s3作为出基变量，则新的基变量为 x2， s1， s2， 因为非基变量 x1=s3=0， 我们也可以从下式： x2 +s1=300，x2+s2=400， x2=250，求出基本解： x1=0， x2=250， s1=50， s2=150， s3=0。 因为此解满足非负条件，是基本可行解，故 s3可以确定为出基变量。 能否在求出基本解以前来确定出基变量呢？ 以下就来看在找出了初始基本可行解和确定了入基变量之后，怎么样的基变量可以确定为出基变量呢？或者说出基变量要具有什么条件呢？ 11管 理 运 筹 学1 单纯形法的基本思路和原理我们把确定出基变量的方法概括如下：把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的 bj值都大于等于零。在本例题中约束方程为在第二步中已经知道 x2为入基变量，我们把各约束方程中 x2的为正的系数除对应的常量，得12管 理 运 筹 学1 单纯形法的基本思路和原理其中 的值最小，所以可以知道在原基变量中系数向量为 的基变量 s3为出基变量，这样可知 x2， s1， s2为基变量， x1， s3为非基变量。 令非基变量为零，得x2+s1=300,x2+s2=400,x2=250.求解得到新的基本可行解 x1=0,x2=250,s1=50,s2=150.这时目标函数值为50x1+100x2=500+100250=25000。显 然比初始基本可行解 x1=0,x2=0,s1=300,s3=250时 的目 标 函数 值为 0要好得多。下面我 们 再 进 行 检验 其最 优 性，如果不是最 优 解 还 要 继续进 行基 变换 ，直至找到最 优 解，或者能 够 判断出 线 性 规 划无最 优 解 为 止。 13管 理 运 筹 学2 单纯形法的表格形式在讲解单纯形法的表格形式之前，先从一般数学模型里推导出检验数 的表达式。可行基为 m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前 m列是单位矩阵）：以下用 表示基变量，用 表示非基变量。14管 理 运 筹 学2 单纯形法的表格形式把第 i个约束方程移项，就可以用非基变量来表示基变量 xi，把以上的表达式带入目标函数，就有其中：15管 理 运 筹 学2 单纯形法的表格形式上面假设 x1,x2, xm是基变量，即第 i行约束方程的基变量正好是 xi，而经过迭代后，基将发生变化，计算 zj的式子也会发生变化。如果迭代后的第 i行约束方程中的基变量为 xBi，与 xBi相应的目标函数系数为 cBi， 系数列向量为 则其中， (cB)是由第 1列第 m行各约束方程中的基变量相应的目标函数依次组成的有序行向量。单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵，而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来求解第二章的例 1。max 50x1+100x2+0s1+0s2+0s3.x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250， x1, x2, s1, s2, s30. 把上面的数据填入如下的单纯形表格16管 理 运 筹 学2 单纯形法的表格形式 按照线性规划模型在表中填入相对应的值，如上表所示； 在上表中有一个 m*m的单位矩阵，对应的基变量为 s1,s2,s3； 在 zj行中填入第 j列与 cB列中对应的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0， 所在 zi行中的第 2位数填入 0； 在 行中填入 cj-zj所得的值，如 ； z表示把初始基本可行解代入目标函数求得的目标函数值，即 b列 *cB列； 初始基本可行解为 s1=300,s2=400,s3=250,x1=0,x2=0; 由于 250/1最小，因此确定 s3为出基变量； 由于 ，因此确定 x2为入基变量。出基变量所在行，入基变量所在列的交汇处为主元，这里是 a32=1， 在表中画圈以示区别。迭代次数基 变量 cBx1 x2 s3 s4 s5 b 比 值Bi/ai2 50 100 0 0 00s1s2s30001 1 1 0 02 1 0 1 00 1 0 0 1300400250300/1400/1250/1zj 0 0 0 0 050 100 0 0 0z=017管 理 运 筹 学2 单纯形法的表格形式 以下进行第一次迭代，其变量为 x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得 x2的系数向量 p2变换成单位向量，由于主元在 p2的第 3 分量上，所以这个单位向量是 也就是主元素变成 1。这样我们又得到的第 1次迭代的单纯表如下所示。 在上表中第 3个基变量 s1已被 x2代替，故基变量列中的第 3个基变量应变为 x2。 由于第 0次迭代表中的主元 a32已经为 1，因此第 3行不变。为了使第 1行的 a12为 0，只需把第 3行 *(-1)加到第 1行即可。同样可以求得第 2行。 求得第 1次迭代的基本可行解为 s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.迭代次数基 变量 cBx1 x2 s3 s4 s5 b 比 值bi/aij 50 100 0 0 01s1s2x2001001 0 1 0 -12 0 0 1 -10 1 0 01150/2zj 0 100 0 0 10050 0 0 0 -1002500018管 理 运 筹 学2 单纯形法的表格形式 从上表可以看出，第一次迭代的 ，因此不是最优解。设 x1为入基变量，从此值可知 b1/a11=50为最小正数，因此， s1为出基变量，a11为主元，继续迭代如下表所示。 从上表中可知第二次迭代得到的基本可行解为 x1=50,x2=250,s1=0,s2=50, s3=0,这时 z=27500。 由于检验数都 0，因此所求得的基本可行解为最优解， z=27500为最优目标函数值。 实际上，我们可以连续地使用一个单纯形表，不必一次迭代重画一个表头。迭代次数基 变量 cBx1 x2 s3 s4 s5 b 比 值bi/aij 50 100 0 0 02x1s2x25001001 0 1 0 -10 0 -2 1 10 1 0 0 15050250zj 50 100 50 0 500 0 -50 0 -502750019管 理 运 筹 学3 求目标函数值最小的线性规划的问题的单纯形表解法一、大 M法 以第二章的例 2来讲解如何用单纯形表的方法求解目标函数值最小的线性规划问题。 目标函数： 约束条件： 加入松弛变量和剩余变量变为标准型，得到新的约束条件如下 ：20管 理 运 筹 学3 求目标函数值最小的线性规划的问题的单纯形表解法至于目标函数，在标准型中并不一定要求求最大值或最小值，但是为了使单纯形表解法有一个统一的解法，我们把所有求目标函数最小值的问题化成求目标函数最大值的问题。具体做法只要把目标函数 乘以（ 1）。 要注意到人工变量是与松弛、剩余变量不同的。松弛变量、剩余变量它们可以取零值，也可以取正值，而人工变量只能取零值。一旦人工变量取正值，那么有人工变量的约束方程和原始的约束方程就不等价了，这样所求得的解就不是原线性规划的解了。为了竭尽全力地要求人工变量为零，我们规定人工变量在目标函数中的系数为 M， 这里 M为任意大的数。这样只要人工变量 M 0，所求的目标函数最大值就是一个任意小的数。这样为了使目标函数实现最大就必须把人工变量从基变量中换出。如果一直到最后，人工变量仍不能从基变量中换出， 也就是说人工变量仍不为零，则该问题无可行解。21管 理 运 筹 学3 求目标函数值最小的线性规划的问题的单纯形表解法此例的数学模型如下所示： 目标函数： max z= 2x1 3x2 Ma1 Ma2.约束条件： x1+x2 s1+a1=350， x1 s2+a2=125， 2x1+x2+s3=600， x1， x2， s1， s2， s3， a1， a20.像这样，为了构造初始可行基得到初始可行解，把人工变量 “ 强行 ”地加到原来的约束方程中去，又为了尽力地把人工变量从基变量中替换出来就令人工变量在求最大值的目标函数里的系数为 M， 这个方法叫做 大 M法， M叫做 罚因子 。 22管 理 运 筹 学3 求目标函数值最小的线性规划的问题的单纯形表解法下面我们就用 大 M法来求解此题 :迭代次数基 变量cB x1 x2 s1 s2 s3 a1 a2 b 比 值-2 -3 0 0 0 -M -M0 a1a2a3-M-M01 1 -1 0 0 1 01 0 0 -1 0 0 12 1 0 0 1 0 0350125600350/1125/1600/2zj -2M -M M M 0 -M -M-2+2M -3+M -M -M 0 0 0-475M1 a1x2s3-M-200 1 -1 0 0 1 -11 0 0 -1 0 0 10 1 0 2 1 0 -2225125350225-350/2zj -2 -M M -M+2 0 -M -M-20 -3+M -M M-2 0 0 2-2M-225M-2502 a1x1s2-M-200 1/2 -1 0 -1/2 1 01 1/2 0 0 1/2 0 00 1/2 0 1 1/2 0 1/2300/1/2175/1/2zj -2 -1/2M-1 M 0 1/2M-1 -M 00 1/2M-2 -M 0 - 1/2M+1 0 -M-50M-60023管 理 运 筹 学3 求目标函数值最小的线性规划的问题的单纯形表解法从上表中可知检验数都小于零。已求得最优解为： x1=250,x2=100,s1=0, s2=125,s3=0,a1=0,a2=0， 其最优值为f=-z=-(-800)=800。迭代次数基 变量 cBx1 x2 s1 s2 s3 a1 a2 b 比 值 -2 -3 0 0 0 -M -M3x2x1s2-3-200 1 -2 0 -1 2 01 0 1 0 1 -1 00 0 1 1 1 -1 -1100250125zj -2 -3 4 0 1 -4 00 0 -4 0 -1 -M+4 -M -80024管 理 运 筹 学3 求目标函数值最小的线性规划的问题的单纯形表解法二、两阶段法两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划划分两阶段求解，仍以上面的例题为例，阐述两阶段法的求解过程。第一阶段：要判断原线性规划是否有基可行解，方法是先求解下列线性规划问题：目标函数：约束条件：25管 理 运 筹 学3 求目标函数值最小的线性规划的问题的单纯形表解法注意： 此线性规划的约束条件与原线性规划一样，而目标函数是求人工变量的相反数之和的最大值。如果此值大于零，则不存在使所有人工变量都为零的可行解，停止计算。如果此值为零，即说明存在一个可行解，使得所有的人工变量都为零。第二阶段：将第一阶段的最终单纯形表中的人工变量取消，将目标函数换成原问题的目标函数，把此可行解作为初始可行解进行计算。26管 理 运 筹 学3 求目标函数值最小的线性规划的问题的单纯形表解法迭代次数基 变量cB x1 x2 s1 s2 s3 a1 a2 b 比 值-2 -3 0 0 0 -1 -10 a1a2s3-1-101 1 -1 0 0 1 01 0 0 -1 0 0 12 1 0 0 1 0 0350125600350/1125/1600/2zj -2 -1 1 1 0 -1 -1-2 1 -1 -1 0 0 0-4701 a1x1s3-1000 1 -1 1 0 1 -11 0 0 -1 0 0 10 1 0 2 1 0 -2225125350zj 0 -1 1 -1 0 -1 10 1 -1 1 0 0 22252 x2x1s30000 1 -1 1 0 1 01 0 0 -1 0 0 10 0 1 1 1 -1 -1225125125zj 0 0 0 0 0 0 00 0 0 0 0 -1 -1027