最优化方法 第二章第二讲 单纯形法.ppt

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

2、x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0,4,基本解如下表 基 基本解 可行否 目标值对应图中的点 B1=（P1，P2） X1=（20，20，0，0）T 200 B B2=（P1，P3） X2=（30，0，40，0）T 180 C B3=（P1，P4） X3=（50，0，0，80）T D B4=（P2，P3） X4=（0，60，80，0）T E B5=（P2，P4） X5=（0，100/3，0，160/3）T 400/3 A B6=（P3，P4） X6=（0，0，100，120）T 0 O,min z=6x14x2 2x1

3、+ 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0,5,（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 + x3 =100 4x1

4、 + 2x2 +x4 =120 x1、x2，x3，x4 0,6,（2）寻找可行基B2，使其对应的基可行解X（2）能使目标函数值增加。 选： x10 则有： X（2）=（x1，0，x3，x4）T,min 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）为一个基 而 X（2）为对应于B2的基可行解 此时 XB=（x1，x3）T，XN

5、=（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,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，x3中必有一个为零，而另一个大等于零。 只要取 x2=min30/（1/2），40/2=20 就有 x1=20，x3=0 这样 X（3）

6、=（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）判断是否为最优解，是停止，否则转下一步；,（3）转换可行基，并求出相应的基可行解，使目标函数值有所改进，转（2）。,9,确定初始的基本可行解,确

7、定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定.,在线性规划标准型中设法得到一个m阶单位矩阵I作为初始可行基。,若在化标准形式前，m个约束方程都是“”的形式，那么在化标准形时只需在一个约束不等式左端都加上一个松弛变量xn+i (i=12m)。,10,判断现行的基本可行解是否最优,设有标准形式的线性规划问题：min z=cX；AX=b，X0； 现假定 A中存在一可行基B,且B为单位阵 这样 AX=b可以描述成如下形式，也就是用非基变量表示基变量 x1 + a1,m+1xm+1 + + a1nxn=b1 x2 + a2,m+1xm+1 + +

8、 a2nxn=b2 xm + am,m+1xm+1 + + amnxn=bm 即 从上述约束方程中可以得到对应于基B的基可行解 X=（b1，b2，bm，0，0）T,11,用非基变量表示目标函数有：,令 有 式中 j为基可行解X的检验数。 更一般性：,12,向量形式,假如已求得一个基本可行解,将这一基本可行解代入目标函数，可求得相应的目标函数值,其中分别表示基变量和 非基变量所对应的价值系数子向量。,13,要判定是否已经达到最小值，只需将 代入目标函数，使目标函数用非基变量 表示，即：,其中 称为非基变量N的检验向量，它的各个分量称为检验数。若N的每一个检验数均小于等于0，即N 0，那么现在的基

9、本可行解就是最优解。,14,定理1：最优解判别定理 对于线性规划问题 若某个基本可行解所对应的检验向量， 则这个基本可行解就是最优解。,定理2：无穷多最优解判别定理 若是一个基本可行解，所对应的检验向量 ，其中存在一个检验数m+k=0， 则线性规划问题有无穷多最优解。,15,定理3：无最优解（无界）判别定理 若 是一个基本可行解，有一个检验数 ， 但是 ，则该线性规划问题无最优解。,证：令 ，则得新的可行解 将上式代入 因为 , 故当+时，Z。,16,如果现行的基本可行解不是最优解，即在检验向量 中存在正的检验数，则需在原基本可行解的基础上寻找一个新的基本可行解，并使目标函数值有所改善。,基本

10、可行解的改进,具体做法是： 先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值）， 再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。 由此可得一个新的基本可行解，由 可知，这样的变换一定能使目标函数值有所减少。,17,换入变量的确定 最大减少原则,假设检验向量 ， 选取最大正检验数所对应的非基变量为换入变量，即若 则选取对应的 为换入变量， 由于且为最大， 因此当由零增至正值， 可使目标函数值 最大限度的减少。,18,如果确定为换入变量，方程 其中为中与对应的系数列向量。 现在需在 中确定一个基变量为换出变量。,换出

11、变量的确定 最小比值原则,当由零慢慢增加到某个值时， 的非负性可能被打破。 为保持解的可行性，可以按最小比值原则确定换出变量： 若,则选取对应的基变量 为换出变量。,19,单纯形表(1),20,单纯形表(2),21,计算步骤： （1）构造单纯形表1和2。 （2）求 。 （3）若 ，则此时基解就是最优解，否则转（4）。 （4）若 ，则无最优解，否则转（5）。 （5）求 。 （6）以 为主元对初始单纯形表做换基运算得新单纯形表，转（2）。,22,4 单纯形表,例1 求解LP问题,x1 x2 x3 x4 x5,RHS,23,x1 x2 x3 x4 x5,RHS,检验数,转轴元,24, 最优解：x*=

12、(6.5, 2.5, 0.5, 0, 0)T,最优值：z*= -1.5,25,例2：,解LP问题,4 单纯形表,26,x1 x2 x3 x4 x5, 此问题无最优解,RHS,27,例3：,解LP问题,4 单纯形表,28,x1 x2 x3 x4 x5, 此问题有多解。,RHS,29,练习： 1、用单纯形法求解 min z=6x14x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20,2、用单纯形方法求解线性规划问题,30,因为非基变量x4的检验数 ，由无穷多最优解判别定理， 本例的线性规划问题存在无穷多最优解,X*=（20，20，0，0）T，Z*=200,最优解最优值,31,无

13、最优解,无最优解与无可行解时两个不同的概念。 无可行解是指原规划不存在可行解，从几何的角度解释是指线性规划问题的可行域为空集； 无最优解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优值，即目标函数在可行域内可以趋于无穷小（或者无穷大）。无最优解也称为无有限最优解，或无界解。,32,借助人工变量求初始的基本可行解,假定我们下面研究的线性规划都是非退化的，将线性规划问题化为标准型,如果约束方程组中包含有一个单位矩阵I，那么已经得到了一个初始可行基。,否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基

14、，即可求得一个初始的基本可行解。,33,首先将原问题化为标准型,添加人工变量，并在目标函数中分别赋予,例4: 线性规划问题:,34,加入人工变量后的约束方程组与原约束方程组是不等价的。,加上人工变量以后，线性规划的基本可行解不一定是原线性规划的问题的基本可行解。 只有当基本可行解中所有人工变量都为取零值的非基变量时，该基本可行解对原线性规划才有意义。因为此时只需去掉基本可行解中的人工变量部分，剩余部分即为原线性规划的一个基本可行解而这正是我们引入人工变量的主要目的。,35,初始基本可行解 对原线性规划没有意义的,但是我们可以从X(0)出发进行迭代，迭代结果有两种： 1.一旦所有的人工变量都从基

15、变量迭代出来，变成只能取零值的非基变量，那么我们实际上已经求得了原线性规划问题的一个初始的基本可行解。此时可以把所有人工变量剔除，开始正式进入求原线性规划最优解的过程。 2. 如果最优单纯形表的基变量中仍含有人工变量，那么该线性规划就不存在可行解。,36,大M法,以后的计算与单纯形表解法相同，只需认定是一个很大的正数即可。 1.假如在单纯形最优表的基变量中不包含人工变量，则最优解中剔除人工变量即为原问题的最优基本可行解。 2.否则说明原问题无可行解。,为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的系

16、数。,37,38,解： 首先将原问题化为标准型 添加人工变量，并在目标函数中分别赋予,例5、用大M法求解下面的线性规划问题:,39,x1 x2 x3 x4 x5 x6 x7,RHS,40,x1 x2 x3 x4 x5 x6 x7,RHS,41,x1 x2 x3 x4 x5 x6 x7,RHS,最优解 最优值,42,无可行解,通过大法求初始的基本可行解。但是如果在大法的最优单纯形表的基变量中仍含有人工变量，那么该线性规划就不存在可行解。 人工变量的值不能取零，说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程。此时线性规划问题的可行域为空集。,43,例6、求解下列线性规划问题,44,x

17、1 x2 x3 x4 x5 x6 x7 x8,RHS,45,x1 x2 x3 x4 x5 x6 x7 x8,RHS,在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人工变量x7=1为基变量，所以原线性规划不存在可行解。,46,两阶段法,两阶段法引入人工变量的目的和原则与大M法相同，所不同的是处理人工变量的方法。,两阶段法的步骤： 1. 求解一个辅助线性规划。目标函数取所有人工变量之和，并取极小化； 2. 如果辅助线性规划存在一个基本可行解，使目标函数的最小值等于零，则所有人工变量都已经“离基”。表明原问题已经得了一个初始的基本可行解，可转入第二阶段继续计算； 否则说明原问题没有可行

18、解，可停止计算。,47,第一阶段：加入人工变量,构造初始可行基.,48,用单纯形法求解,若g=0, 进入第二阶段,否则,原问 题无可行解。 第二阶段：去掉人工变量，还原目标函数系数，做 出初始单纯形表。,49,例：求解下列线性规划问题,50,将原问题化成标准型：,解:,用两阶段方法来求解。,51,第一阶段的线性规划问题为,x1 x2 x3 x4 x5 x6 x7,RHS,52,x1 x2 x3 x4 x5 x6 x7 RHS,53,x1 x2 x3 x4 x5 x6 x7 RHS,得原问题的基可行解X=(1,3,0,0,0,)T。,第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数

19、从上表的最后一个单纯形表出发，继续计算。,54,x1 x2 x3 x4 x5 RHS,55,x1 x2 x3 x4 x5 RHS,得原标准线性规划问题的最优解X=（0，5/2，3/2，0，0）T，最优值是-3/2。 所以最初的线性规划问题的最优解X=（0，5/2，3/2）T，最优值是3/2。,56,例：求解下列线性规划问题,57,将原问题化成标准型：,解:,用两阶段方法来求解。,58,第一阶段的线性规划问题为,x1 x2 x3 x4 x5 x6 RHS,59,x1 x2 x3 x4 x5 x6 RHS,60,x1 x2 x3 x4 x5 x6 RHS,61,x1 x2 x3 x4 x5 x6 RHS,第二阶段：将上表中的人工变量去除，目标函数换成原问题的目标函数从上表的最后一个单纯形表出发，继续计算。,62,x1 x2 x3 x4 RHS,所以最初的线性规划问题的最优解X=(3/5，6/5)T， 最优值是18/5。,63,