运筹学-05-单纯形法.ppt

1、第五章单纯形法，1单纯形法的基本思想和原理2单纯形法的表格3最小目标函数值线性规划的单纯形表解法4几种特殊情况，2，1单纯形法的基本思想和原理，单纯形法的基本思想：从可行域中的某个顶点开始，判断该顶点是否是最优解，如果不是，则寻找另一个使其目标函数值更好的顶点。直到找到一个顶点作为其最优解，即使其目标函数值最优的解，或者可以判断线性规划问题没有最优解。通过第二章例1的求解，我们引入了单纯形法：加入松弛变量后，我们可以得到如下标准形式：目标函数：max 50 x1 100 x2约束：x1 x2 s1300，2x1 x2 s2400，X2 S3250。XJ0 (j=1，2)，Sj0 (j=1，2，

2、3)，3，3 a的秩是3，a的秩m小于这个方程组的变量数n。为了找到初始的基本可行解，首先介绍了线性规划的下列基本概念。基础：众所周知，A是一个有约束的系数矩阵，它的秩是m。如果B是A(即逆矩阵)中一个数量级为mm的非奇异子矩阵，那么B就是线性规划问题中的一个基础。基向量：基B中的一列称为基向量。在基B中有m个基向量.非基向量：除了基B之外，A中的一列称为基B的非基向量。基变量：对应于基向量pi的变量xi称为基变量，有m个基变量。1单纯形法的基本思想和原理，4，非基变量：对应于非基向量pj的变量xj称为非基变量，有n个非基变量。根据线性代数的知识，如果我们在约束方程的系数矩阵中找到一个基，并使

3、基的非基变量为零，我们就可以通过求解m元线性方程得到唯一的解。这个解叫做线性规划的基本解。在这个例子中，我们还可以找到一个基数a，这样这个基数的非基数变量x和s2为零。此时，约束方程成为基本变量的约束方程：1，单纯形法的基本思想和原理，5，x2 s1300，x2=400，x2 s3=250。这个线性规划的基本解是通过求解它得到的：x1=0，x2=400，s1=100，s2=0，s3=150，因为在这个基本解中，s30的约束条件显然不是这个线性规划的可行解。基本解决方案可以是可行的，也可以是不可行的。它们之间的主要区别在于所有变量的解是否满足非负条件。我们把满足非负条件的基本解称为基本可行解，把

4、这样的基称为可行基。1。单纯形法的基本思想和原理。一般来说，判断一个基是否是可行基，只有在找到它的基本解之后，当它的基本解的所有变量的解都大于或等于零时，才能得出这个解是基本可行解，这个基是可行基。那么我们能在解决它之前找到一个可行的基础吗？也就是说，我们能否找到一个基础来保证解决后得到的解决方案基本上是可行的？因为在线性规划的标准形式中bj要求等于或大于零，所以如果我们能找到一个基，即恒等式矩阵，或一个由恒等式矩阵的各列向量组成的基(至于每个列向量的序列，它是不相关的)，例如，很明显，得到的基本解必须是基本可行解，并且这个恒等式矩阵或由恒等式矩阵的各列向量组成的基必须是可行基。事实上，这个基

5、本可行解中的每个变量要么等于某个bj，要么等于零。1.单纯形法的基本思想和原理。在这个例子中，我们找到了一个基数，即单位矩阵。当第一次寻找可行基时，找到的基要么是单位矩阵，要么是单位矩阵中各列向量的组合，称为初始可行基，它们对应的基本可行解称为初始基本可行解。如果找不到由单位矩阵或单位矩阵的列向量组成的基作为初始可行基，我们将构造初始可行基，具体方法将在后面详细描述。单纯形法的基本思想和原理，即所谓的最优性检验，是判断所获得的基本可行解是否是最优解。1.一般来说，目标函数包括基本变量和非基本变量。现在，我们要求目标函数只能用非基本变量来表示，非基本变量只能用约束方程中的移位项来表示，然后目标函

6、数中的基本变量可以用非基本变量的表达式来代替，这样目标函数只包含非基本变量，或者目标函数中基本变量的系数都为零。此时，目标函数中所有变量的系数是每个变量的检验数，变量xi的检验数表示为I。显然，所有基本变量的检验数必须为零。在本例中，目标函数是50 x1 100 x2。由于初始可行解中的x1和x2是非基变量，目标函数已经用非基变量表示，所以没有必要替换基变量。这样，我们可以知道1=50，2=100，3=0，4=0，5=0。1，单纯形法的基本思想和原理，9，1，单纯形法的基本思想和原理，2，最优解的判别定理对于寻找最大目标函数的问题，对于一个基本可行解，如果所有的测试数都是0，那么这个基本可行解

7、就是最优解。让我们用通俗的方式来解释最优解判别定理。让非基本变量表示的目标函数具有以下形式。由于所有xj值都大于或等于零，当所有XJ值都小于或等于零时，可以知道它是小于或等于零的数字。为了最大化Z的值，它显然只有零。我们将这些xj作为非基本变量(即，让这些xj的值为零)，并且所获得的基本可行解使得目标函数值z0最大。* *要找到目标函数的最小值，只需将0改为0，10，1单纯形法的基本思想和原理。第三，基本变换已经通过测试，我们知道这个初始基本可行解不是最优解。下面描述如何通过基变换找到一个新的可行基。具体方法是将可行基中的一个列向量改为一个新的可行基，使新的基本可行解的目标函数值更好。为了改变

8、基数，有必要确定换入变量和换出变量。1.从最优解判别式定理确定基本变量，当一个j0，非基本变量xj变为基本变量时不取零值可以增加目标函数值，所以我们要选择基数大于0的非基本变量来改变为基本变量(称为基本变量)。如果有两个以上的j0，为了增加目标函数，一般选择J最大的非基变量作为输入基变量。在本例中，2=100是测试数中最大的正数，因此x2被选为输入基变量。11，1单纯形法的基本思想和原理，2。基础变量的确定在确定x2为基础变量后，我们应该在最初的三个基础变量s1、s2和s3中确定一个基础变量，即哪个基础变量成为非基础变量？如果s3作为基础变量，新的基础变量是x2、s1和s2。因为非基变量x1=

9、s3=0，我们也可以从下面的公式中找到基本解：x2 s1=300，x2 s2=400，x2=250: x1=0，x2=250，s1=50，s2=150。因为这个解满足非负条件并且基本上是可行的，所以s3可以确定为基变量。在找到基本解之前，我们能确定基本变量吗？在找到初始基本可行解并确定基本变量后，让我们看看什么样的基本变量可以确定为基本变量。或者说基本变量应该具备什么条件？12，1单纯形法，我们将确定基本变量的方法总结如下：将每个约束方程中确定的基本变量的正系数除以约束方程中常项的值，并确定约束方程中原始基本变量的最小比值作为基本变量。这样，在下一次迭代的矩阵变换中，可以确保新获得的bj值都大

10、于或等于零。在这个例子中，约束方程在第二步中已知x2是基础变量。我们将每个约束方程中x2的正系数除以相应的常数，得到单纯形法的基本思想和原理，其中取值最小，所以我们可以知道带系数向量的基变量s3是基变量，所以我们可以知道x2、s1和s2是基变量，x1和s3是非基变量。让非基本变量为零，得到x2 s1=300，x2 s2=400，x2=250。新的基本可行解是x1=0，x2=250，s1=50，s2=150。此时，目标函数值为50 x1 100 x2=500 100250=25000。显然，这比当初始基本可行解x1=0，x2=0，S1=300和S3=250时，目标函数值为0要好得多。接下来，我们

11、将测试它的最优性。如果不是最优解，我们将继续改变基础，直到我们找到最优解，或者我们可以判断线性规划中没有最优解。单纯形法的表格形式。在解释单纯形法的表格形式之前，试验数的表达式是从一般的数学模型中导出的。以m阶恒等式矩阵为可行基的线性规划模型如下(假设其系数矩阵的前m列为恒等式矩阵):以下用于表示基本变量，以下用于表示非基本变量。表格形式的15，2单纯形法，通过移动第I约束方程，基变量xi可以表示为非基变量，并且上述表达式可以被带入目标函数，因此有表格形式的16，2单纯形法，其假设X1、X2和XM是基变量，即第I约束方程的基变量恰好是xi，并且在迭代之后，基将改变并且zj将被计算。如果行I中的

12、迭代约束方程中的基本变量是xBi，则对应于xBi的目标函数系数是cBi，并且系数列向量是，其中(cB)是由对应于列1的行M中的每个约束方程中的基本变量的目标函数组成的有序行向量。单纯形法的表格形式是计算基本可行解，检验其最优性，并用表格方法迭代某一步。表格形式有点像增广矩阵，它的计算方法也一般采用矩阵行的初等变换。以下单纯形表用于求解第2章中的示例1。Max50x1100x20s10s20s3。x1x2s1=300，2x1 x2 s2=400，x2 s3=250，x1，x2，s1，s2，s30。将上述数据以17，2单纯形法的形式填入以下单纯形表，并根据线性规划模型填入表中相应的值，如上表所示；

13、在上表中，有一个m*m的恒等式矩阵，对应的基本变量是S1、S2和S3；用Jth列和cB列的对应元素相乘相加得到的值填充zj行，如z2=0*1 0*1 0*1=0，zi行的第二位数字用0填充；在该行中填写从cj-zj获得的值，如：z表示将初始基本可行解代入目标函数得到的目标函数值，即B *列；初始基本可行解为s1=300，s2=400，s3=250，x1=0，x2=0。由于250/1是最小的，s3被确定为基础变量。因此，x2被确定为基础变量。基本变量所在的行和基本变量所在的列的交集是主要元素，其中a32=1。在表格中圈出不同之处。18，2表格形式的单纯形法，下面是第一次迭代，其变量是x2，s1，

14、s2，通过矩阵行的初等变换，得到一个新的基本可行解。具体方法是通过行的初等变换将x2的系数向量p2变换成单位向量。因为主元素在p2的第三个分量上，这个单位向量就是主元素变成1。这样，我们得到了第一次迭代的简单表格，如下所示。在上表中，第三个基本变量s1已被x2替换，因此基本变量列中第三个基本变量的应变为x2。因为第0次迭代中的主成分a32已经是1，所以第三行保持不变。要使第一行中的a12为0，只需在第一行中添加第三行*(1)。第二行也可以找到。第一次迭代的基本可行解是S1=50，S2=150，X2=250，X1=0，S3=0，Z=25000。19、2。从上表可以看出，第一次迭代不是最优解。假设

15、x1是基础变量。从这个值来看，b1/a11=50是最小的正数。因此，s1是基础变量，a11是主成分。继续迭代，如下表所示。从上表可以看出，从第二次迭代获得的基本可行解是x1=50，x2=250，s1=0，s2=50，s3=0，然后z=27500。因为测试数都是0，所以得到的基本可行解是最优解，z=27500是最优目标函数值。事实上，我们可以连续使用单工表，而不必在一次迭代中重新绘制表头。20，3求解目标函数值最小的线性规划问题的单纯形表法。1.大M法用第二章的例子2说明了如何用单纯形表法求解目标函数值最小的线性规划问题。目标函数：约束条件：增加松弛变量，将剩余变量改变为标准形式，得到新的约束条

16、件如下：21，3单纯形表法求解具有最小目标函数值的线性规划问题，对于目标函数，不一定要求在标准形式中寻找最大值或最小值，但为了使单纯形表法有一个统一的解，我们把寻找最小目标函数的所有问题转化为最大目标函数。具体方法是简单地将目标函数乘以(1)。应该注意的是，人工变量不同于松弛和剩余变量。松弛变量和剩余变量可以取零值或正值，而人工变量只能取零值。一旦人工变量取正值，带有人工变量的约束方程就不等价于原始约束方程，所以得到的解不是原始线性规划解。为了尽一切努力要求人工变量为零，我们规定目标函数中人工变量的系数为m，其中m是一个任意大的数。这样，只要人为变量M0，目标函数的最大值就是一个任意小的数。因

17、此，为了最大化目标函数，有必要从基础变量中替换人工变量。如果人工变量不能从基础变量交换到最后，也就是说，人工变量仍然不是零，那么问题就没有可行的解决方案。22，3求解具有最小目标函数值的线性规划问题的单纯形表法，本例的数学模型如下所示：目标函数：max z=2x13x2Ma1Ma2。约束：x1 x2s1 a1=350，x1s2 a2=125，2x1 x2 s3=600，x1，x2，s1，s2，s3，a1，s3。为了构造初始可行基并得到初始可行解，人工变量被强制加入到原始约束方程中，为了尽可能地从基变量中替换人工变量，人工变量在寻求最大值的目标函数中的系数为m，称为大m法，m称为罚因子。23，3求出目标函数值最小的线性规划问题的