最优化方法课件：2-3 单纯形法

1、13 单纯形法 单纯形法的一般原理 表格单纯形法 借助人工变量求初始的基本可行解2 单纯形法的一般步骤如下： 1947年，Dantzig提出的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。 （1）寻找一个初始的基本可行解。 （2）检查现行的基本可行解是否最优，如果为最优， 则停止迭代，已找到最优解，否则转一步。 （3）移至目标函数值有所改善的另一个基本可行解， 然后转回到步骤（2）。 3一、引例用单纯形方法求解下列线性规划： min z=6x14x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20解：化为标准型 min z=6x14x2+0 x3+0 x4 2x

2、1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 04基本解如下表 基 基本解 可行否 目标值对应图中的点B1=（P1，P2） X1=（20，20，0，0）T 200 BB2=（P1，P3） X2=（30，0，40，0）T 180 CB3=（P1，P4） X3=（50，0，0，80）T DB4=（P2，P3） X4=（0，60，80，0）T EB5=（P2，P4） X5=（0，100/3，0，160/3）T 400/3 AB6=（P3，P4） X6=（0，0，100，120）T 0 OABCDEOx1x22x1+3x2 =1004x1 + 2x2

3、 =120 min z=6x14x2 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 05（1）找初始可行基：B1=（P3，P4）现成的初始可行基；此时， XB=（x3，x4）T，XN=（x1，x2）T用XN表示Z和XB有： min z=6x14x2 x3 =1002x13x2 +x4 =1204x12x2令 XN=(0,0)T有 XB=(100,120)T则有： X（1）=（0，0，100，120）T为对应于基B1的基可行解。问： X（1）是否最优呢？否 称非基变量在目标函数中的系数为检验数。min z=6x14x2 2x1 + 3x2

4、+ x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0因为： x1和x2在目标函数中的系数为负，当x1，z ；x2，z 。6（2）寻找可行基B2，使其对应的基可行解X（2）能使目标函数值增加。选： x10则有： X（2）=（x1，0，x3，x4）Tmin z=6x14x2 x3 =1002x13x2 +x4 =1204x12x2要使为X（2）基可行解，x3，x4中必有一个为零，而另一个大等于零。只要取 x1=min100/2，120/4=30就有 x3=40，x4=0这样 X（2）=（30，0，40，0）T因为 P1，P3线性无关，因此，B2=（P1，P3）为一个

5、基而 X（2）为对应于B2的基可行解此时 XB=（x1，x3）T，XN=（x2，x4）T用XN表示Z和XB有： min z=180 x2（3/2）x4 x1 = 30（1/2）x2（1/4）x4 x3 = 40 2 x2 +（1/2）x4问： X（2）是否最优呢？否因为： x2在目标函数中的系数为正，当x2，z 。7（3）寻找可行基B3，使其对应的基可行解X（3）能使目标函数值增加。选： x20则有： X（3）=（x1，x2，x3，0）T min z=180 x2（3/2）x4 x1 = 30（1/2）x2（1/4）x4 x3 = 40 2 x2 +（1/2）x4要使为X（3）基可行解，x1，

6、x3中必有一个为零，而另一个大等于零。只要取 x2=min30/（1/2），40/2=20就有 x1=20，x3=0这样 X（3）=（20，20，0，0）T因为 P1，P2线性无关，因此，B3=（P1，P2）为一个基而 X（3）为对应于B3的基可行解此时 XB=（x1，x2）T，XN=（x3，x4）T用XN表示Z和XB有： min z=200+ （1/2）x3+（5/4）x4 x1 =20 +（1/4）x3 （3/8）x4 x2 =20 （1/2）x3 +（1/4）x4问： X（3）是否最优呢？是，8从引例可以总结出求解过程：（1）确定初始基及其基可行解；（2）判断是否为最优解，是停止，否则转

7、下一步；（3）转换可行基，并求出相应的基可行解，使目标函数值有所改进，转（2）。9 确定初始的基本可行解 确定初始的基本可行解等价于确定初始的可行基. 在线性规划标准型中设法得到一个m阶单位矩阵I作为初始可行基。 若在化标准形式前，m个约束方程都是“”的形式，那么在化标准形时只需在一个约束不等式左端都加上一个松弛变量xn+i (i=12m)。10判断现行的基本可行解是否最优 设有标准形式的线性规划问题：min z=C T X；AX=b，X0；假定 A中存在一可行基B, 且B为单位阵x1 + a1,m+1xm+1 + + a1nxn=b1 x2 + a2,m+1xm+1 + + a2nxn=b2

8、 xm + am,m+1xm+1 + + amnxn=bm得到对应于基B的基可行解X=（b1，b2，bm，0，0）T1112 假如已求得一个基本可行解相应的目标函数值13要判定是否已经达到最小值，只需将 代入目标函数，即： 其中 称为非基变量N的检验向量，它的各个分量称为检验数。若N的每一个检验数均大于等于0，即N0，那么现在的基本可行解就是最优解。14定理1：最优解判别定理 对于线性规划问题若某个基本可行解所对应的检验向量，则这个基本可行解就是最优解。定理2：无穷多最优解判别定理 若是一个基本可行解，所对应的检验向量，其中存在一个检验数m+k=0，则线性规划问题有无穷多最优解。15 如果现行

9、的基本可行解不是最优解，即在检验向量 中存在负的检验数，则需在原基本可行解的基础上寻找一个新的基本可行解，并使目标函数值有所改善。 基本可行解的改进 具体做法是：先从检验数为负的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值），再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。由此可得一个新的基本可行解，由 可知，这样的变换一定能使目标函数值有所减少。16换入变量的确定 最大减少原则 假设检验向量 ， 选取最小负检验数所对应的非基变量为换入变量，即若 则选取对应的 为换入变量， 由于且为最小，可使目标函数值 最大限度的减少。17如

10、果确定为换入变量，方程其中为中与对应的系数列向量。现在需在 中确定一个基变量为换出变量。 换出变量的确定 最小比值原则 当由零慢慢增加到某个值时， 的非负性可能被打破。为保持解的可行性，可以按最小比值原则确定换出变量： 若则选取对应的基变量 为换出变量。 18 定理3：无最优解（无界）判别定理 若 是一个基本可行解，有一个检验数 ，但是 ，则该线性规划问题无最优解。证：令 ，则得新的可行解将上式代入因为 , 故当+时，Z。19 可将这些计算设计成一个简单的表格，即单纯形表来完成：C CBTCNT CB XB b X1 X2 Xm X m+1 Xm+2 Xn C1C2.Cm X1X2.Xm b1

11、b2.bm I N 12.m 0 CN T- CB TN 表格单纯形法20BNbCBTCNTIB-1NB-1b0CNT -CBT B-1N21例1：用单纯形法求解 min z=6x14x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20解：化为标准型 min z=6x14x2+0 x3+0 x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0找初始可行基：B1=（P3，P4）现成的初始可行基；22列初始单纯形表从表中有：X（1）=（0，0，100，120）T为对应于基B1的基可行解，显然不是最优解；根据minj|j0=

12、120/4，对应的x4为换出变量；Cj6 4 0 0b CBXBx1 x2 x3 x4 0 0 x3x4 2 3 1 04 2 0 1100120100/2120/4(min)z-6 -4 0 0023以4为主元素进行迭代，得新的单纯形表：从表中有：X（2）=（30，0，40，0）T为对应于基B2的基可行解，显然不是最优解；根据maxj|j0=2，确定x2为换入变量； 按规则确定换出变量，即：=bi/aik|aik0=40/2，对应的x3为换出变量； Cj 6400b CBXB x1 x2x3x4 0 x3021-1/24040/2(min) 6x111/201/43030/(1/2)Z0-1

13、03/218024以2为主元素进行迭代，得新的单纯形表： Cj 6400b CBXB x1x2x3x4 4 x2011/2-1/420 6x110-1/43/820 Z001/25/4 - 200表中j 0，j=1，4，因此得最优解： X*=（20，20，0，0）T，Z*=200 25例2、用单纯形方法求解线性规划问题解：26 0 1 0 1 03x2-2 0 0 1 2 -12x30-0 1 0 1 03x2-24/11 0 1 0 04x303/10 1 0 1 03x40_1 0 1 0 04x30 0 0 0 0 1 1 0 0 -2 12x1-1 -1 0 0 2 02/11 0 0

14、 -2 12x50 -1 -2 0 0 08/21 2 0 0 18x50 x1 x2 x3 x4 x5bXBCB -1 - 2 0 0 0C最优解最优值2/23/1-27 因为非基变量x4的检验数4=0，由无穷多最优解判别定理，本例的线性规划问题存在无穷多最优解。事实上若以x4为换入变量，以x3为换出变量，再进行一次迭代，可得一下单纯形表：最优解 最优值最优解的一般表示式C -1 -2 0 0 0CBXBb x1 x2 x3 x4 x50-2-1x4x2x1124 0 0 1/2 1 -1/2 0 1 -1/2 0 1/2 1 0 1 0 0 0 0 0 0 128无最优解 无最优解与无可行

15、解时两个不同的概念。 无可行解是指原规划不存在可行解，从几何的角度解释是指线性规划问题的可行域为空集； 无最优解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优值，即目标函数在可行域内可以趋于无穷小（或者无穷大）。无最优解也称为无有限最优解，或无界解。 29因但所以原问题无最优解解：引入松弛变量x3,x4化为标准型C -2 -2 0 0 CXB b x1 x2 x3 x4 0X3 1-11100X4 2-1/2101-2-200例3、试用单纯形法求解下列线性规划问题：31对于极大化的线性规划问题的处理：检验是否最优的准则有所不同，即： 若某个基本可行解的所有非基变量对应的检验数 （

16、而不是），则基本可行解为最优解否则采用最大增加原则（而非最大减少原则）确定换入变量，即： 若则选取对应的非基变量xm+k为换入变量确定了换入变量以后，换出变量仍采用最小比值原则来确定。 32借助人工变量求初始的基本可行解 假定我们下面研究的线性规划都是非退化的，将线性规划问题化为标准型,如果约束方程组中包含有一个单位矩阵I，那么已经得到了一个初始可行基。 否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。 33 首先将原问题化为标准型添加人工变量 例4: 线性规划问题:34加入

17、人工变量后的约束方程组与原约束方程组是不等价的。加上人工变量以后，线性规划的基本可行解不一定是原线性规划的问题的基本可行解。 只有当基本可行解中所有人工变量都为取零值的非基变量时，该基本可行解对原线性规划才有意义。因为此时只需去掉基本可行解中的人工变量部分，剩余部分即为原线性规划的一个基本可行解而这正是我们引入人工变量的主要目的。35初始基本可行解 对原线性规划没有意义的,但是我们可以从X(0)出发进行迭代，迭代结果有两种：1.一旦所有的人工变量都从基变量迭代出来，变成只能取零值的非基变量，那么我们实际上已经求得了原线性规划问题的一个初始的基本可行解。此时可以把所有人工变量剔除，开始正式进入求

18、原线性规划最优解的过程。2. 如果最优单纯形表的基变量中仍含有人工变量，那么该线性规划就不存在可行解。36 大M法 以后的计算与单纯形表解法相同，只需认定是一个很大的正数即可。 1.假如在单纯形最优表的基变量中不包含人工变量，则最优解中剔除人工变量即为原问题的最优基本可行解。 2.否则说明原问题无可行解。为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的系数。3738解： 首先将原问题化为标准型添加人工变量，并在目标函数中分别赋予 例5、用大M法求解下面的线性规划问题:39- 0 1 -1/2 -1/2

19、 0 1/2 1/23/2X2-2 1 0 -1/2 1/2 0 1/2 -1/21/2X11- -1 1 0 -1 0 0 11X2-21/2 2 0 -1 1 0 1 -11X6M1/1 -1 1 0 -1 0 0 11X7M2/1 1 1 -1 0 0 1 02X6M 0 0 -1/2 -3/2 0 +M 3/2+M 0 0 1/2 1/2 1 -1/2 -1/23/2X50 -1-2M 0 M -2-M 0 0 2+2M2/1 1 0 0 1 1 0 -12X50 1 -2-2M M M 0 0 03/1 0 1 0 0 1 0 03X50 X1 x2 x3 x4 x5 x6 x7bX

20、BCB 1 -2 0 0 0 M MC40 0 1 0 0 1 0 03X2-2 1 0 0 1 1 0 -12X40 1 1 -1 0 0 1 02X2-2 2 0 -1 1 0 1 -11X40- 0 1 -1/2 -1/2 0 1/2 1/23/2X2-21/2/1/2 1 0 -1/2 1/2 0 1/2 -1/21/2X11 1 0 0 0 2 M M -1 0 1 0 1 -1 01X30 3 0 -2 0 0 2M M -1 0 1 0 1 -1 01X50 0 0 -1/2 -3/2 0 +M 3/2+M3/2 /1/2 0 0 1/2 1/2 1 -1/2 -1/23/2X5

21、0 X1 x2 x3 x4 x5 x6 x7bXBCB 1 -2 0 0 0 M MC最优解 最优值41无可行解 通过大法求初始的基本可行解。但是如果在大法的最优单纯形表的基变量中仍含有人工变量，那么该线性规划就不存在可行解。 人工变量的值不能取零，说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程。此时线性规划问题的可行域为空集。42解：故引入人工变量，并利用大M法求解例6、求解下列线性规划问题43C 3 2 1 0 0 0 M M CB XB b x1 x2 x3 x4 x5 x6 x7 x8 0MM x4x7x8 643 1 1 1 1 0 0 0 01 0 -1 0 -1 0

22、 1 00 1 -1 0 0 -1 0 1 6/1-3/1 3-M 2-M 1+2M 0 M M 0 0 0M2 x4x7x2 343 1 0 2 1 0 1 0 -11 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 3/14/1- 3-M 0 3+M 0 M 2 0 -2+M 3M2 x1x7x2 313 1 0 2 1 0 1 0 -10 0 -3 -1 -1 -1 1 10 1 -1 0 0 -1 0 1 0 0 -3+3M -3+M M -1+M 0 1 在以上最优单纯形表中，所有非基变量检验数都大于零，但在该表中人工变量x7=1为基变量，所以原线性规划不存在可行解

23、。44两阶段法 两阶段法引入人工变量的目的和原则与大M法相同，所不同的是处理人工变量的方法。两阶段法的步骤： 1. 求解一个辅助线性规划。目标函数取所有人工变量之和，并取极小化； 2. 如果辅助线性规划存在一个基本可行解，使目标函数的最小值等于零，则所有人工变量都已经“离基”。表明原问题已经得了一个初始的基本可行解，可转入第二阶段继续计算； 否则说明原问题没有可行解，可停止计算。 45解：首先将问题化为标准型添加人工变量x6,x7,并建立辅助线性规划如下：例7、用两阶段法求解线性规划问题。46 0 1 -1/2 -1/2 0 1/2 1/23/2X20 1 0 -1/2 1/2 0 1/2 -

24、1/21/2X10- -1 1 0 -1 0 0 11X201/2 2 0 -1 1 0 1 -11X611/1 -1 1 0 -1 0 0 11X712/1 1 1 -1 0 0 1 02X61 0 0 0 0 0 1 1 0 0 1/2 1/2 1 -1/2 -1/23/2X50 -2 0 1 -1 0 0 22/1 1 0 0 1 1 0 -12X50 0 -2 1 1 0 0 03/1 0 1 0 0 1 0 03X50 x1 x2 x3 x4 x5 x6 x7bXBCB 0 0 0 0 0 1 1C辅助规划所有检验数：原问题已得一个初始基本可行解，47由上表可知，通过若干次旋转变换，

25、原问题的约束方程组已变换成包含一个单位矩阵的约束方程组该约束方程组可作为第二阶段初始约束方程组，将目标函数则还原成原问题的目标函数，可继续利用单纯形表求解。48 1 0 0 0 2 1 0 0 1 1 0 1 0 0 1 -1 0 1 0 1231X4X2X30-20 3 0 -2 0 0 2 0 -1 1 0 1 1 -1 0 0 -1 0 1 0 1121X4X2X50-200 0 -1/2 -3/2 01/2/1/2-3/2/1/2 1 0 -1/2 1/2 0 0 1 -1/2 -1/2 0 0 0 1/2 1/2 11/23/23/2X1X2X51-20 x1 x2 x3 x4 x5 bXBCB1 -2 0 0 0C可得最优解 ，目标函数值maxZ=-6，与用大M法的结果完全相同。49无可行解 通过两阶段法求初始的基本可行解。但是如果两阶段法的辅助线性规划的目标函数的极小值大于零，那么该线