线性规划与单纯形法-第3节.ppt

《线性规划与单纯形法-第3节.ppt》由会员分享，可在线阅读，更多相关《线性规划与单纯形法-第3节.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、（第三版）运筹学教材编写组 编清华大学出版社运筹学运筹学 第1章 线性规划与单纯形法 第3节 单纯形法 钱颂迪 制作第1章 线性规划与单纯形法第第3节节 单纯形法单纯形法3.1 举例3.2 初始基可行解的确定3.3 最优性检验与解的判断3.4 基变换3.5 迭代（旋转运算）单纯形法求解线性规划的思路：一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或最小值为止。这样问题就得到了最优解，先举一例来说明。注：单纯

2、形是指0维中的点，一维中的线段，二维中的三角形，三维中的四面体，n维空间中的有n+1个顶点的多面体。例如在三维空间中的四面体，其顶点分别为(0，0，0)，(1，0，0)，(0，1，0)，(0，0，1)。具有单位截距的单纯 形 的 方 程 是 xi1，并 且 xi0，i=1,2,m。3.1 举例例6 试以例1来讨论如何用单纯形法求解。例1的标准型为：约束方程(1-12)式的系数矩阵 从(1-12)式中可以看到x3,x4,x5的系数列向量P3,P4,P5是线性独立的，这些向量构成一个基 对应于B的变量x3,x4,x5为 基变量.从(1-12)式中可以得到（1-13）将(1-13)式代入目标函数(1

3、-11)得到当令非基变量x1=x2=0，便得到z=0。这时得到一个基可行解X(0)X(0)=(0,0,8,16,12)T 这个基可行解表示：工厂没有安排生产产品、；资源都没有被利用，所以工厂的利润指标z=0。从分析目标函数的表达式(1-14)可以看到非基变量x1,x2(即没有安排生产产品，)的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品或，就可以使工厂的利润指标增加。所以只要在目标函数(1-14)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换。如何确定换入变量，换出变量一般选择正系数最大的那

4、个非基变量x2为换入变量，将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量，可按以下方法来确定换出变量。现分析(1-13)式，当将x2定为换入变量后，必须从x3,x4,x5中确定一个换出变量，并保证其余的都是非负，即x3,x4,x50。当x1=0,由(1-13)式得到x2取何值时，才能满足非负要求 从(1-15)式中可以看出，只有选择x2=min(8/2,-,12/4)=3时，才能使(1-15)式成立。因当x2=3时，基变量x5=0，这就决定用x2去替换x5。以上数学描述说明了每生产一件产品，需要用掉各种资源数为(2，0，4)。由这些资源中的薄弱环节，就确定了产品的产量。这

5、里就是由原材料B的数量确定了产品的产量x2=12/4=3件。为求得以x3,x4,x2为基变量的一个基可行解和进一步分析问题，需将(1-13)中x2的位置与x5的位置对换。得到用高斯消去法将(1-16)式中x2的系数列向量变换为单位列向量。其运算步骤是：=/4；=-2;=,并将结果仍按原顺序排列有：再将(1-17)式代入目标函数(1-11)式得到 从目标函数的表达式(1-18)中可以看到，非基变量x1的系数是正的，说明目标函数值还可以增大，X(1)还不是最优解。于是再用上述方法，确定换入、换出变量，继续迭代，再得到另一个基可行解X(2)X(2)=(2,3,0,8,0)T再经过一次迭代，再得到一个

6、基可行解X(3)X(3)=(4,2,0,0,4)T而这时得到目标函数的表达式是：z=14-1.5x3-0.125x4 (1-19)再检查(1-19)式，可见到所有非基变量x3,x4的系数都是负数。这说明若要用剩余资源x3,x4，就必须支付附加费用。所以当x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。所以X(3)是最优解。即当产品生产4件，产品生产2件，工厂才能得到最大利润。通过上例，可以了解利用单纯形法求解线性规划问题的思路。现将每步迭代得到的结果与图解法做一对比，其几何意义就很清楚了。原例1的线性规划问题是二维的，即两个变量x1,x2；当加入松弛变量x3,x4,x5后，变换为高

7、维的。这时可以想象，满足所有约束条件的可行域是高维空间的凸多面体(凸集)。这凸多面体上的顶点，就是基可行解。初始基可行解 X(0)=(0,0,8,16,12)T就相当于图1-2中的原点(0，0)，X(1)=(0,3,2,16,0)T相当于图1-2中的Q4点(0，3)；X(2)=(2，3，0，8，0)T相当于图1-2中的 Q3点(2，3)，最优解X(3)=(4，2，0，0，4)T相当于图1-2中的 Q2点(4，2)。从初始基可行解X(0)开始迭代，依次得到X(1)，X(2)，X(3)。这相当于图1-2中的目标函数平移时，从0点开始，首先碰到Q4，然后碰到Q3，最后达到Q2。下面讨论一般线性规划问

8、题的求解。一般线性规划问题的求解 3.2 初始基可行解的确定为了确定初始基可行解，要首先找出初始可行基，其方法如下。(1)直接观察(2)加松弛变量(3)加非负的人工变量(1)直接观察若线性规划问题从Pj(j=1,2,n)中一般能直接观察到存在一个初始可行基(2)加松弛变量对所有约束条件是“”形式的不等式，可以利用化为标准型的方法，在每个约束条件的左端加上一个松弛变量。经过整理，重新对xj及aij(i=1,2,m;j=1,2,n)进行编号，则可得下列方程组x1,x2,xm 为松弛变量于是含有mm单位矩阵，以B 作为可行基。将(1-22)式每个等式移项得令xm+1=xm+2=xn=0，由(1-23

9、)式可得xi=bi (i=1,2,m)得到一个初始基可行解又因bi0(在1-3节中已做过规定)，所以得到一个初始基可行解X=(x1,x2,xm,0，0)T n-m个 =(b1,b2,bm,0，0)T n-m个(3)加非负的人工变量对所有约束条件是“”形式的不等式及等式约束情况，若不存在单位矩阵时，就采用人造基方法。即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束再加上一个非负的人工变量，总能得到一个单位矩阵。关于这个方法将在本章第5节中进一步讨论。3.33.3最优性检验与解的判别最优性检验与解的判别对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和

10、无可行解四种情况，为此需要建立对解的判别准则。一般情况下，经过迭代后(1-23)式变成 将 代入目标函数(1-20)式，整理后得令1最优解的判别定理若 为对应于基B的一个基可行解，且对于一切j=m+1,n，有j0，则X(0)为最优解。称j为检验数。当所有非基变量的j0时，由（1-27）式可知已不存在任一可换入的非基变量，使目标函数继续增大。所以以j0，为最优解的判别准则。2.无穷多最优解判别定理若 为一个基可行解，对于一切j=m+1，,n，有j0，又存在某个非基变量的检验数m+k=0，则线性规划问题有无穷多最优解。证:只需将非基变量xm+k换入基变量中，找到一个新基可行解X(1)。因m+k=0

11、，由(1-27)知z=z0，故X(1)也是最优解。由2.2节的定理3可知X(0)，X(1)连线上所有点都是最优解。3无界解判别定理若 为一基可行解，有一个m+k0，并且对i=1,2,，m，有 存在。那么该线性规划问题具有无界解(或称无最优解)。证:构造一个新的解 X(1)，它的分量为 因 ，所以对任意的0都是可行解，把x(1)代入目标函数内得z=z0+m+k因m+k0，故当+，则z+，故该问题目标函数无界。以上讨论都是针对标准型，即求目标函数极大化时的情况。当求目标函数极小化时，一种情况如前所述，将其化为标准型。如果不化为标准型，只需在上述1，2点中把j0改为j0，第3点中将m+k0改写为m+

12、k0即可。3.4 3.4 基变换基变换 若初始基可行解X(0)不是最优解及不能判别无界时，需要找一个新的基可行解。具体做法是从原可行解基中换一个列向量(当然要保证线性独立)，得到一个新的可行基，这称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行对换，就得到一个新的基可行解。1.换入变量的确定 由(1-27)式看到，当某些j0时，xj增大，则目标函数值还可以增大。这时要将某个非基变量xj换到基变量中去(称为换入变量)。若有两个以上的j0，那么选哪个非基变量作为换入变量呢?为了使目标函数值增加得快，从直观上一般选j0中的大者，即则对应的xk为换入变量。但也可以任选

13、或按最小足码选。2.换出变量的确定 设P1，P2，Pm是一组线性独立的向量组，它们对应的基可行解是X(0)。将它代入约束方程组(1-21)得到其他的向量Pm+1,Pm+2,Pm+t,Pn都可以用P1，P2，Pm线性表示，若确定非基变量Pm+t为换入变量，必然可以找到一组不全为0的数(i=1,2,m)使得在(1-29)式两边同乘一个正数，然后将它加到(1-28)式上，得到 新的基可行解。由此得到由X(0)转换到X(1)的各分量的转换公式这里 是原基可行解X(0)的各分量；是新基可行解X(1)的各分量；i,m+t是换入向量Pm+t的对应原来一组基向量的坐标。现在的问题是，这个新解X(1)的m个非零

14、分量对应的列向量是否性独立?事实上，因X(0)的第l个分量对应于X(1)的相应分量是零，即 成立。又因 将(1-32)式减(1-31)式得到由于上式中至少有l,m+t0，所以上式表明P1，P2，Pm是线性相关，这与假设相矛盾。由此可见，X(1)的m个非零分量对应的列向量Pj(j=1,2,m,jl)与Pm+t是线性独立的，即经过基变换得到的解是基可行解。实际上，从一个基可行解到另一个基可行解的变换，就是进行一次基变换。从几何意义上讲，就是从可行域的一个顶点转向另一个顶点(见1-2图解法)3.5 迭代(旋转运算)上述讨论的基可行解的转换方法是用向量方程来描述，在实际计算时不太方便，因此采用系数矩阵

15、法。现考虑以下形式的约束方程组 一般线性规划问题的约束方程组中加入松弛变量或人工变量后，很容易得到上述形式设x1,x2,xm为基变量，对应的系数矩阵是mm单位阵I，它是可行基。令非基变量xm+1,xm+2,xn为零，即可得到一个基可行解。若它不是最优解，则要另找一个使目标函数值增大的基可行解。这时从非基变量中确定xk为换入变量。显然这时为在迭代过程中可表示为其中是经过迭代后对应于的元素值。按规则确定xl为换出变量，xk,xl的系数列向量分别为 为了使xk与xl进行对换，须把Pk变为单位向量，这可以通过(1-33)式系数矩阵的增广矩阵进行初等变换来实现。变换的步骤是：(1)将增广矩阵(1-34)

16、式中的第l行除以al k，得到(2)将(1-34)式中xk列的各元素，除al k变换为1以外，其他都应变换为零。其他行的变换是将(1-35)式乘以ai k(il)后，从(1-34)式的第i行减去，得到新的第i行。由此可得到变换后系数矩阵各元素的变换关系式：是变换后的新元素。(3)经过初等变换后的新增广矩阵是(4)由(1-36)式中可以看到x1,x2,xk,，xm的系数列向量构成mm单位矩阵;它是可行基.当非基变量xm+1,，xl,xn为零时，就得到一个基可行解X(1)。在上述系数矩阵的变换中，元素al k称为主元素，它所在列称为主元列，它所在行称为主元行。元素al k位置变换后为1。例7 试用上述方法计算例6的两个基变换。解 例6的约束方程组的系数矩阵写成增广矩阵 当以x3,x4,x5为基变量，x1,x2为非基变量，令x1,x2=0，可得到一个基可行解X(0)=(0,0,8,16,12)T现用x2去替换x5，于是将x3，x4,x2的系数矩阵变换为单位矩阵，经变换后为 令非基变量x1,x5=0，得到新的基可行解X(1)=(0,3,2,16,0)T