1、1,第二章 单纯形法,单纯形法的一般原理 表格单纯形法 借助人工变量求初始的基本可行解 单纯形表与线性规划问题的讨论 改进单纯形法,2,考虑到如下线性规划问题 其中一个mn矩阵，且秩为m，总可以被调整为一个m维非负列向量，为n维行向量，为n维列向量。 根据线性规划基本定理： 如果可行域= n / =，0非空有界， 则上的最优目标函数值=一定可以在的一个顶点上达到。 这个重要的定理启发了Dantzig的单纯形法， 即将寻优的目标集中在D的各个顶点上。,单纯形法的一般原理,3,Dantzig的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。其基本思路是从一个初始的基本可行解出发，寻找一
2、条达到最优基本可行解的最佳途径。 单纯形法的一般步骤如下： （1）寻找一个初始的基本可行解。 （2）检查现行的基本可行解是否最优，如果为最优， 则停止迭代，已找到最优解，否则转一步。 （3）移至目标函数值有所改善的另一个基本可行解， 然后转会到步骤（2）。,4,确定初始的基本可行解,确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定 为了讨论方便，不妨假设在标准型线性规划中，系数矩阵中前m个系数列向量恰好构成一个可行基，即 =（），其中 =（1，2，m）为基变量x1，x2，xm的系数列向量 构成的可行基， =(m+1，Pm+2， Pn)为非
3、基变量xm+1，xm+2， xn的 系数列向量构成的矩阵。,5,所以约束方程 就可以表示为,用可行基的逆阵-1左乘等式两端，再通过移项可推得：若令所有非基变量, 则基变量由此可得初始的基本可行解,6,问题：要判断m个系数列向量是否恰好构成一个基并不是一件容易的事。基由系数矩阵中m个线性无关的系数列向量构成。但是要判断m个系数列向量是否线性无关并非易事。即使系数矩阵中找到了一个基B，也不能保证该基恰好是可行基。因为不能保证基变量B=-1b0。为了求得基本可行解 ，必须求基的逆阵-1。但是求逆阵-1也是一件麻烦的事。结论：在线性规划标准化过程中设法得到一个m阶单位矩阵I作为初始可行基，,7,若在化
4、标准形式前，约束方程中有“”不等式，那么在化标准形时除了在方程式左端减去剩余变量使不等式变成等式以外，还必须在左端再加上一个非负新变量，称为人工变量若在化标准形式前，约束方程中有等式方程，那么可以直接在等式左端添加人工变量。,为了设法得到一个m阶单位矩阵I作为初始可行基，可在性规划标准化过程中作如下处理：,若在化标准形式前，m个约束方程都是“”的形式，那么在化标准形时只需在一个约束不等式左端都加上一个松弛变量xn+i (i=12m)。,8,判断现行的基本可行解是否最优,假如已求得一个基本可行解,将这一基本可行解代入目标函数，可求得相应的目标函数值,其中分别表示基变量和非基变量所对应的价值系数子
5、向量。,9,要判定是否已经达到最大值，只需将代入目标函数，使目标函数用非基变量表示，即：,其中 称为非基变量N的检验向量，它的各个分量称为检验数。若N的每一个检验数均小于等于0，即N0，那么现在的基本可行解就是最优解。,10,定理1：最优解判别定理 对于线性规划问题若某个基本可行解所对应的检验向量，则这个基本可行解就是最优解。,定理2：无穷多最优解判别定理 若是一个基本可行解，所对应的检验向量，其中存在一个检验数m+k=0，则线性规划问题有无穷多最优解。,11,基本可行解的改进,如果现行的基本可行解不是最优解，即在检验向量 中存在正的检验数，则需在原基本可行解的基础上寻找一个新的基本可行解，并
6、使目标函数值有所改善。具体做法是：先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值），再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。由此可得一个新的基本可行解，由 可知，这样的变换一定能使目标函数值有所增加。,12,换入变量和换出变量的确定：,换入变量的确定 最大增加原则,假设检验向量 ， 若其中有两个以上的检验数为正，那么为了使目标函数值增加得快些，通常要用“最大增加原则”，即选取最大正检验数所对应的非基变量为换入变量，即若 则选取对应的 为换入变量， 由于且为最大， 因此当由零增至正值，可使目标函数值 最大限
7、度的增加。,13,换出变量的确定 最小比值原则 如果确定为换入变量，方程其中为中与对应的系数列向量。现在需在 中确定一个基变量为换出变量。 当由零慢慢增加到某个值时， 的非负性可能被打破。为保持解的可行性，可以按最小比值原则确定换出变量： 若,则选取对应的基变量 为换出变量。,14,定理3：无最优解判别定理 若 是一个基本可行解，有一个检验数 ，但是，则该线性规划问题无最优解。,证：令 ，则得新的可行解将上式代入因为 , 故当+时，Z+。,15,用初等变换求改进了的基本可行解,假设是线性规划 的可行基，则令非基变量，则基变量。可得基本可行解 。,用逆阵左乘约束方程组的两端，等价于对方程组施以一
8、系列的初等“行变换”。变换的结果是将系数矩阵中的可行基变换成单位矩阵I，把非基变量系数列向量构成的矩阵变换成，把资源向量b变换成。,16,且改进了的基本可行解只是在的基变量的基础上用一个换入变量替代其中一个换出变量，其它的基变量仍然保持不变。这些基变量的系数列向量是单位矩阵I中的单位向量。为了求得改进的基本可行解 ，只需对增广矩阵 施行初等行变换，将换入变量的系数列向量变换成换出变量所对应的单位向量即可。,由于行初等变换后的方程组与原约束方程组 或同解,17,例1,解：,()确定初始的基本可行解。 ，基变量 ，非基变量 。,18,(2) 检验 是否最优。检验向量 因为1=3，3=4 均大于零，
9、所以不是最优解。,19,（3）基本可行解的改进 选取换入变量因为max3，4=4，取x3为换入变量。 选取换出变量 且 ， 选取x4为换出变量.,20,（4）求改进了的基本可行解 对约束方程组的增广矩阵施以初等行变换，使换入变量x3所对应的系数列向量 变换成换出变量x4所对应的单位向量 , 注意保持基变量x5的系数列向量 为单位向量不变。,第一行除以,第二行减去第一行,21,可得改进的基本可行解。 ，基变量，非基变量。基本可行解目标函数值易见目标函数值比原来的Z=-1增加了， 再转向步骤(2),22,（2）检验 是否最优。检验向量因为，所以仍不是最优解。,23,（3）基本可行解的改进 选取换入
10、变量因为，取为换入变量。 选取换出变量且 ，选取为换出变量.,24,（4）求改进了的基本可行解 对约束方程组的增广矩阵施以初等行变换，使换入变量所对应的系数列向量变换成换出变量所对应的单位向量 ,第二行乘以/,第一行减以第二行的/倍,25,可得改进的基本可行解。 ，基变量，非基变量基本可行解目标函数值 比Z=15增加了，再转向步骤(2),26,（2）检验 是否最优。检验向量因为所有检验数均小于零，所以是最优解，,27,表格单纯形法,通过例我们发现，在单纯形法的求解过程中，有下列重要指标：每一个基本可行解的检验向量根据检验向量可以确定所求得的基本可行解是否为最优解。如果不是最优又可以通过检验向量
11、确定合适的换入变量。每一个基本可行解所对应的目标函数值通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值有效地增加，直至求得最优目标函数为止。 在单纯形法求解过程中，每一个基本可行解都以某个经过初等行变换的约束方程组中的单位矩阵为可行基。当=时，-1=，易知：,28,可将这些重要结论的计算设计成如下一个简单的表格，即单纯形表来完成：,29,例2、试利用单纯形表求例1中的最优解解：得初始的单纯形表：,初始基本可行解，Z= -1，,1 2 2 1 0,8,x4,-1,3 0 4 0 0,-1,Z,3 4 1 0 1,7,x5,1,x1 x2 x3 x4 x5,b,XB,CB,5 2 3 -
12、1 1,C,30,换入变量，换出变量，为主元进行旋转变换,基本可行解，Z= 15，,1/2 1 1 1/2 0,4,x3,3,1 -4 0 -2 0,15,Z,5/2 3 0 -1/2 1,3,x5,1,x1 x2 x3 x4 x5,b,XB,CB,5 2 3 -1 1,C,1 2 2 1 0,8,x4,-1,3 0 4 0 0,-1,Z,3 4 1 0 1,7,x5,1,x1 x2 x3 x4 x5,b,XB,CB,5 2 3 -1 1,C,8/2,7/1,31,最优解 最优值,换入变量，换出变量，/为主元进行旋转变换,4/1/2,1/2 1 1 1/2 0,4,x3,3,1 -4 0 -2
13、 0,15,Z,3/5/2,5/2 3 0 -1/2 1,3,x5,1,x1 x2 x3 x4 x5,b,XB,CB,5 2 3 -1 1,C,0 2/5 1 3/5 -1/5,17/5,x3,3,0 -26/5 0 -9/5 -2/5,81/5,Z,1 6/5 0 -1/5 2/5,6/5,x1,5,x1 x2 x3 x4 x5,b,XB,CB,5 2 3 -1 1,C,32,例3、用单纯形方法求解线性规划问题解：本题的目标函数是求极小化的线性函数，可以令则这两个线性规划问题具有相同的可行域和最优解，只是目标函数相差一个符号而已。,33,0 1 0 1 0,3,x2,2,0 0 1 2 -1
14、,2,x3,0,-,0 1 0 1 0,3,x2,2,4/1,1 0 1 0 0,4,x3,0,3/1,0 1 0 1 0,3,x4,0,_,1 0 1 0 0,4,x3,0,0 0 0 0 -1,8,Z,1 0 0 -2 1,2,x1,1,1 0 0 -2 0,6,Z,2/1,1 0 0 -2 1,2,x5,0,1 2 0 0 0,0,Z,8/2,1 2 0 0 1,8,x5,0,x1 x2 x3 x4 x5,b,XB,CB,1 2 0 0 0,C,最优解最优值,2/2,3/1,-,34,因为非基变量x4的检验数4=0，由无穷多最优解判别定理，本例的线性规划问题存在无穷多最优解。事实上若以x
15、4为换入变量，以x3为换出变量，再进行一次迭代，可得一下单纯形表：,最优解 最优值最优解的一般表示式,35,对于极小化的线性规划问题的处理：先化为标准型，即将极小化问题变换为极大化问题，然后利用单纯形方法求解直接利用单纯形方法求解，但是检验是否最优的准则有所不同，即： 若某个基本可行解的所有非基变量对应的检验数 （而不是），则基本可行解为最优解否则采用最大减少原则（而非最大增加原则）来确定换入变量，即： 若则选取对应的非基变量xm+k为换入变量确定了换入变量以后，换出变量仍采用最小比值原则来确定。,36,借助人工变量求初始的基本可行解,若约束方程组含有“”不等式，那么在化标准形时除了在方程式左
16、端减去剩余变量，还必须在左端加上一个非负的人工变量。因为人工变量是在约束方程已为等式的基础上，人为的加上去的一个新变量，因此加入人工变量后的约束方程组与原约束方程组是不等价的。加上人工变量以后，线性规划的基本可行解不一定是原线性规划的问题的基本可行解。只有当基本可行解中所有人工变量都为取零值的非基变量时，该基本可行解对原线性规划才有意义。因为此时只需去掉基本可行解中的人工变量部分，剩余部分即为原线性规划的一个基本可行解而这正是我们引入人工变量的主要目的。,37,考虑线性规划问题： 为了在约束方程组的系数矩阵中得到一个m阶单位矩阵作为初始可行基，在每个约束方程组的左端加上一个人工变量 可得到：,
17、38, 添加了m个人工变量以后，在系数矩阵中得到一个m阶单位矩阵，以该单位矩阵对应的人工变量 为基变量， 即可得到一个初始的基本可行解这样的基本可行解对原线性规划没有意义的。但是我们可以从X(0)出发进行迭代，一旦所有的人工变量都从基变量迭代出来，变成只能取零值的非基变量，那么我们实际上已经求得了原线性规划问题的一个初始的基本可行解。此时可以把所有人工变量剔除，开始正式进入求原线性规划最优解的过程。,39,大M法,大M法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵I，那么已经得到了一个初始可行基。否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其
18、它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。 为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的负系数-。这样只要基变量中还存在人工变量，目标函数就不可能实现极大化。 以后的计算与单纯形表解法相同，只需认定是一个很大的正数即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解。,40,例4、用大M法求解下面的线性规划问题:解： 首先将原问题化为标准型添加人工变量，并在目标函数中分别
19、赋予-,41,-,0 1 -1/2 -1/2 0 1/2 1/2,3/2,X2,2,1 0 -1/2 1/2 0 1/2 -1/2,1/2,X1,-1,-,-1 1 0 -1 0 0 1,1,X2,2,1/2,2 0 -1 1 0 1 -1,1,X6,-M,1/1,-1 1 0 -1 0 0 1,1,X7,-M,2/1,1 1 -1 0 0 1 0,2,X6,-M,0 0 1/2 3/2 0 -1/2-M -3/2-M,5/2,Z,0 0 1/2 1/2 1 -1/2 -1/2,3/2,X5,0,1+2M 0 -M 2+M 0 0 -2-2M,2-M,Z,2/1,1 0 0 1 1 0 -1,
20、2,X5,0,-1 2+2M -M -M 0 0 0,-3M,Z,3/1,0 1 0 0 1 0 0,3,X5,0,X1 x2 x3 x4 x5 x6 x7,b,XB,CB,-1 2 0 0 0 -M -M,C,42,0 1 0 0 1 0 0,3,X2,2,1 0 0 1 1 0 -1,2,X4,0,1 1 -1 0 0 1 0,2,X2,2,2 0 -1 1 0 1 -1,1,X4,0,-,0 1 -1/2 -1/2 0 1/2 1/2,3/2,X2,2,1/2/1/2,1 0 -1/2 1/2 0 1/2 -1/2,1/2,X1,-1,-1 0 0 0 -2 -M -M,6,Z,-1 0
21、 1 0 1 -1 0,1,X3,0,-3 0 2 0 0 -2-M -M,4,Z,-1 0 1 0 1 -1 0,1,X5,0,0 0 1/2 3/2 0 -1/2-M -3/2-M,5/2,Z,3/2 /1/2,0 0 1/2 1/2 1 -1/2 -1/2,3/2,X5,0,X1 x2 x3 x4 x5 x6 x7,b,XB,CB,-1 2 0 0 0 -M -M,C,最优解 最优值,43,两阶段法,两阶段法引入人工变量的目的和原则与大M法相同，所不同的是处理人工变量的方法。两阶段法的步骤： 求解一个辅助线性规划。目标函数取所有人工变量之和，并取极小化；约束条件为原问题中引入人工变量后包
22、含一个单位矩阵的标准型的约束条件。 如果辅助线性规划存在一个基本可行解，使目标函数的最小值等于零，则所有人工变量都已经“离基”。表明原问题已经得了一个初始的基本可行解，可转入第二阶段继续计算；否则说明原问题没有可行解，可停止计算。 求原问题的最优解。在第一阶段已求得原问题的一个初始基本可行解的基础上，继续用单纯形法求原问题的最优解,44,例5、用两阶段法求解例4中的线性规划问题。解：首先将问题化为标准型添加人工变量x6,x7,并建立辅助线性规划如下：,由于辅助线性规划的目标函数是极小化，因此最优解的判别准则应为：,45,0 1 -1/2 -1/2 0 1/2 1/2,3/2,X2,0,1 0
23、-1/2 1/2 0 1/2 -1/2,1/2,X1,0,-,-1 1 0 -1 0 0 1,1,X2,0,1/2,2 0 -1 1 0 1 -1,1,X6,1,1/1,-1 1 0 -1 0 0 1,1,X7,1,2/1,1 1 -1 0 0 1 0,2,X6,1,0 0 0 0 0 1 1,0,W,0 0 1/2 1/2 1 -1/2 -1/2,3/2,X5,0,-2 0 1 -1 0 0 2,1,W,2/1,1 0 0 1 1 0 -1,2,X5,0,0 -2 1 1 0 0 0,3,W,3/1,0 1 0 0 1 0 0,3,X5,0,x1 x2 x3 x4 x5 x6 x7,b,XB
24、,0 0 0 0 0 1 1,C,辅助规划所有检验数：,原问题已得一个初始基本可行解，,46,由上表可知，通过若干次旋转变换，原问题的约束方程组已变换成包含一个单位矩阵的约束方程组该约束方程组可作为第二阶段初始约束方程组，将目标函数则还原成原问题的目标函数，可继续利用单纯形表求解。,47,-1 0 0 0 -2,6,Z,1 0 0 1 1 0 1 0 0 1 -1 0 1 0 1,231,X4X2X3,020,-3 0 2 0 0,4,Z,2 0 -1 1 0 1 1 -1 0 0 -1 0 1 0 1,121,X4X2X5,020,0 0 1/2 3/2 0,5/2,Z,1/2/1/2-3/
25、2/1/2,1 0 -1/2 1/2 0 0 1 -1/2 -1/2 0 0 0 1/2 1/2 1,1/23/23/2,X1X2X5,-120,x1 x2 x3 x4 x5,b,XB,CB,-1 2 0 0 0,C,可得最优解 ，目标函数值maxZ=6，与用大M法的结果完全相同。,48,单纯形表与线性规划问题的讨论,无可行解,通过大法或两阶段法求初始的基本可行解。但是如果在大法的最优单纯形表的基变量中仍含有人工变量，或者两阶段法的辅助线性规划的目标函数的极小值大于零，那么该线性规划就不存在可行解。 人工变量的值不能取零，说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程。此时线性规
26、划问题的可行域为空集。,49,例6、求解下列线性规划问题解：首先将问题化为标准型令，则,故引入人工变量，并利用大M法求解,50,C,-3 -2 -1 0 0 0 -M -M,CB,XB,b,x1 x2 x3 x4 x5 x6 x7 x8,0-M-M,x4x7x8,643,1 1 1 1 0 0 0 01 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1,6/1-3/1,Z,-7M,-6-4M,-15-M,-3+M -2+M -1-2M 0 -M -M 0 0,0-M-2,x4x7x2,343,1 0 2 1 0 1 0 -11 0 -1 0 -1 0 1 00 1 -1 0 0
27、 -1 0 1,3/14/1-,Z,Z,-3+M 0 -3-M 0 -M -2 0 2-M,-3-M-2,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为基变量，所以原线性规划不存在可行解。,51,无最优解,无最优解与无可行解时两个不同的概念。 无可行解是指原规划不存在可行解，从几何的角度解释是指 线性规划问题的可行域为空集； 无最优解则是指线性规划问题存在可行解，但是可行解的目 标函数达
28、不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为有限最优解，或无界解。 判别方法：无最优解判别定理在求解极大化的线性规划问题过程中，若某单纯形表的检验 行存在某个大于零的检验数，但是该检验数所对应的非基变量 的系数列向量的全部系数都为负数或零，则该线性规划问题 无最优解，,可以,可以,52,例7、试用单纯形法求解下列线性规划问题：解：引入松弛变量x3,x4化为标准型,因但所以原问题无最优解,53,退化解,当线性规划问题的基本可行解中有一个或多个基变量取零值时，称此基本可行解为退化解。 产生的原因：在单纯形法计算中用最小比值原则确定换出变量时，有时存在两个或两个以上相
29、同的最小比值，那么在下次迭代中就会出现一个甚至多个基变量等于零。遇到的问题：当某个基变量为零，且下次迭代以该基变量作为换出变量时，目标函数并不能因此得到任何改变（由旋转变换性质可知，任何一个换入变量只能仍取零值，其它基变量的取值保持不变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完全相同。从几何角度来解释，这两个退化的基本可行解对应线性规划可行域的同一个顶点，解决的办法：最小比值原则计算时存在两个及其以上相同的最小比值时，选取下标最大的基变量为换出变量，按此方法进行迭代一定能避免循环现象的产生（摄动法原理）。,54,例8、求解下述线性规划问题：解：引入松弛变量化标准型,55,0,0,
30、0,-24,2,-80,3,0,Z,-5,-6,0,-42,0,-8,0,5,Z,1,0,0,0,1,0,0,1,x3,2,1,2,0,6,0,-24,1,1,x1,3,3,2,1,30,0,-8,0,3,x5,0,0,-3,0,-42,5,-8,0,0,Z,1,1,0,0,1,0,0,1,x7,0,0,1,0,6,-1,-24,1,0,x1,3,0,-1,1,30,-3,-8,0,0,x5,0,-,1,1,0,0,1,0,0,1,x7,0,0,0,1,0,6,-1,-24,1,0,x6,0,0,0,0,1,36,-4,-32,1,0,x5,0,x7,x6,x5,x4,x3,x2,x1,b,X
31、B,CB,0,0,0,-24,2,-80,3,C,第一次迭代中使用了摄动法原理，选择下标为6的基变量x6离基。,可得最优解 ，目标函数值maxZ=，,56,无穷多最优解,无穷多最优解判别原理：若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。例：最优表：非基变量检验数，所以有无穷多最优解。最优解集为可行域两个顶点的凸组合：,57,改进单纯形法的特点 利用单纯形表求解线性规划时，每一次迭代都把整个单纯形表计算一遍，事实上我们关心的只是以下一些数据：基本可行解 ，其相应的目标函数值 ，非基变量检验数 ，及其换入变量 ， 设主
32、元列元素 ，及其换出变量 ，设 利用它们可得到一组新的基变量以及新的可行基1。,改进单纯形法,为基变量下标,为非基变量下标,58,对任一基本可行解，只要知道，上述关键数据都可以从线性规划问题的初始数据直接计算出来。因此如何计算基本可行解对应的可行基的逆阵成为改进单纯形法的关键改进单纯形法推导出从可行基变换到1时，到的变换公式。当初始可行基为单位矩阵时，变换公式将更具有优越性，因为这样可以避免矩阵求逆的麻烦以下推导从到的变换公式：,59,假设当前基，,基变换中用非基变量取代基变量可得新基前后二个基相比仅相差一列，且比较以上二式，可得,其中表示第个元素为1，其它元素均为零的单位列向量，为主元列元素。,60,假设 ，则,第列（换出变量对应列 ）,第行,所以由,主元素,61,改进单纯形法的步骤（1）根据给出的线性规划问题的标准型，确定初始基变量和初始可行基。求初始可行基B的逆阵-1，得初始基本可行解。 （2）计算单纯形乘子 ，得目标函数当前值（3）计算非基变量检验数，若N0，则当前解已是最优解，停止计算；否则转下一步。（4）根据，确定非基变量为换入变量，计算,若0，则问题没有有限最优解，停止计算，否则转下一步。,
