第一章线性规划与单纯形法ppt课件.ppt

1,第一章 线性规划与单纯形法,第一节 线性规划问题及其数学模型第二节 线性规划问题的几何意义第三节 单纯形法第四节 单纯形法的计算步骤第五节 单纯形法的进一步讨论第六节 应用举例,2,第一节 线性规划问题及其数学模型,一、 问题的提出二、 图解法三、 线性规划问题的标准形式四、 线性规划问题的解的概念,3,线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种，以下仅介绍单纯形法 。,4,一、问题的提出,例 1 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示。,每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排计划使该工厂获利最多?,5,利润 z=2x1+3x2,6,本问题的数学模型为:,这就是一个最简单的线性规划模型。,7,例2 建立LP数学模型,某家电厂家利用现有资源生产两种 产品，有关数据如下表：,如何安排生产，使获利最多？,8,如何安排生产，使获利最多？,厂家,设 产量 产量,9,每一个线性规划问题都用一组决策变量 表示某一方案，这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的；都有关于各种资源和资源使用情况的技术数据，创造新价值的数据；存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示;都有一个达到某一目标的要求，可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同，要求目标函数实现最大化或最小化。,上述两个问题具有的共同特征：,10,线性规划模型的一般形式,目标函数,满足约束条件,价值系数,技术（工艺）系数,限额系数（资源）,非负约束条件,11,二、图解法,例1是一个二维线性规划问题，因而可用作图法直观地进行求解。,12,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,4,3,0,13,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,4,3,0,Q1,可行域,14,目标值在（4，2）点，达到最大值14,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,4,3,0,Q2(4,2),Q1,可行域,x1+2x2=84x1=16,15,图解法求解步骤,由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最优的移动方向；平移目标函数的等值线，找出最优点，算出最优值。,16,练习：用图解法求解,目标函数 Max Z = 2x1 + x2 约束条件 5x2 15 6x1 +2x2 24 x1 + x2 5 x1、 x2 0,17,9 8 7 6 5 4 3 2 1 0,|123456789,x1,x2,x1 + x2 =5,目标函数 Max Z = 2x1 + x2 约束条件 5x2 15 6x1 +2x2 24 x1 + x2 5 x1、 x2 0,5 x2 = 15,图解法,12 11 10 ,18,9 8 7 6 5 4 3 2 1 0,|123456789,x1,x2,x1 + x2 = 5,目标函数 Max Z = 2x1 + x2 约束条件 5x2 15 6x1 +2x2 24 x1 + x2 5 x1、 x2 0,5 x2 = 15,图解法,12 11 10 ,可行域,19,9 8 7 6 5 4 3 2 1 0,|123456789,x1,x2,x1 + x2 = 5,目标函数 Max Z = 2x1 + x2 约束条件 5x2 15 6x1 +2x2 24 x1 + x2 5 x1、 x2 0,5 x2 = 15,12 11 10 ,x2 = -2x1,6x1+ 2x2=24 x1+ x2=5,最优解 (3.5,1.5),目标值在（3.5，1.5）点，达到最大值8.5,20,（1）无穷多最优解(多重最优解)（2）无界解（3）无可行解,上例中求解得到问题的最优解是惟一的,通过图解法，可观察到一般线性规划的解还可能出现一下几种情况：,21,无穷多最优解（多重最优解）,4x1=16,4x2=12,x1+2x2=8,x1,x2,4,8,4,3,0,可行域,Q2,Q3,Max Z = 2x1 + 4x2,22,4x1=16,x1,x2,4,0,无界解（a）,可行域,23,无界解（b）,24,当存在相互矛盾的约束条件时，线性规划问题的可行域为空集，即无可行解，也不存在最优解。,无可行解,4x1=16,4x2=12,x1+2x2=8,x1,x2,3,0,原可行域,8,增加一个新的约束条件,25,可行域和解有以下几种情况,(a)可行域有界 有唯一最优解,(b)可行域有界 有无穷多最优解,26,(c)可行域无界 有唯一最优解,(d)可行域无界 有无穷多最优解,(e)可行域无界 无最优解 (无界解),27,(f)可行域为空集 无可行解,28,LP问题,有可行解,有最优解,唯一解无穷多解,无最优解（可行域为无界,无界解）,无可行解（无解，可行域为空集）,若LP问题有最优解，则要么最优解唯一，要么有无穷多最优解,29,图解法的几点结论:（由图解法得到的启示）,可行域是有界或无界的凸多边形，凸多边形的顶点个数是有限的。若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函数值，比较即得。,30,三、线性规划问题的标准形式,在标准形式中规定约束条件的右端项bi0,31,32,用向量形式表示的标准形式线性规划,线性规划问题的几种表示形式,33,用矩阵形式表示的标准形式线性规划,34,(1) 若要求目标函数实现最小化，即min z =CX，则只需将目标函数最小化变换求目标函数最大化，即令z= z，于是得到max z= CX。(2) 约束条件为不等式。分两种情况讨论：若约束条件为“”型不等式，则可在不等式左端加入非负松弛变量，把原“”型不等式变为等式约束；若约束条件为“”型不等式，则可在不等式左端减去一个非负剩余变量(也称松弛变量)，把不等式约束条件变为等式约束。(3) 若存在取值无约束的变量xk,可令,如何将一般线性规划转化为标准形式的线性规划,35,例3 将例1的数学模型化为标准形式的线性规划。例1的数学模型在加入了松驰变量后变为,36,例4 将下述线性规划问题化为标准形式线性规划,(1) 用x4x5替换x3，其中x4，x50；(2) 在第一个约束不等式左端加入松弛变量x6；(3) 在第二个约束不等式左端减去剩余变量x7；(4) 令z= z，将求min z 改为求max z,37,例4的标准型,38,补充： 当某个变量xj0时,令xj=xj. 当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束,将其化为两个不等式,再加入松驰变量化为等式。,39,四、线性规划问题解的概念,1.可行解2.基3.基可行解4.可行基,40,（1-4）,（1-5）,（1-6）,一般线性规划问题的标准型：,41,定义满足约束条件(1-5)、(1-6)式的解X=(x1,x2，xn)T，称为线性规划问题的可行解；其中使目标函数（1-4）达到最大值的可行解称为最优解。,1、可行解,42,2、基,A是约束方程组的mn维系数矩阵，其秩为m,43,B是矩阵A中mm阶非奇异子矩阵（| B | 0） ，则称B是线性规划问题的一个基。令B = =( P1 , P2 , , Pm )Pj (j=1,2,m) 为基向量。与基向量Pj对应的变量xj称为基变量记为XB = ( x1 , x2 , , xm )T，其余的变量称为非基变量，记为 XN = ( xm+1 , xm+2 , , xn ) T 。,44,令非基变量xm+1 = xm+2 = =xn =0 线性规划问题变量的个数等于线性方程的个数（m个） 利用高斯消去法，求出一个解 X = ( x1 , x2 , , xm,0,0 )T 称X为基解（或称为基本解）,45,4x1=16,4x2=12,x1+ 2x2=8,x1,x2,4,3,0,Q1,Q2,Q3,Q4,Q6,Q7,Q8,46,满足非负条件（1-6）的基解，称为基可行解(或称为基本可行解)。 基可行解的非零分量的数目不大于m，并且都是非负的。,3、基可行解,4x1=16,4x2=12,x1+ 2x2=8,x1,x2,4,3,0,Q1,Q2,Q3,Q4,Q6,Q7,Q8,基可行解为可行域的顶点,47,对应于基可行解的基，称为可行基。约束方程组(1-5)具有的基解的数目最多是 个。一般基可行解的数目要小于基解的数目。以上提到了几种解的概念，它们之间的关系可用图1-6表明。说明：当基解中的非零分量的个数小于m时，该基解是退化解。在以下讨论时，假设不出现退化的情况。,4、可行基,48,非可行解,可行解,基可行解,基解,图1-6 线性规划标准型问题不同解之间的关系,49,例：求基解、基可行解、最优解。,50,系数矩阵,列向量,51,1,基：,52,令非基变量,得基解,X1 不是基可行解,53,2,基：,54,令非基变量,得基解,X2 是基可行解,55,3,基：,56,令非基变量,得基解,X3 是基可行解,57,4,基：,58,令非基变量,得基解,X4 是基可行解,59,5,基：,60,令非基变量,得基解,X5 不是基可行解,61,6,基：,62,令非基变量,得基解,X6 是基可行解,63,7,基：,64,令非基变量,得基解,X7 不是基可行解,65,8,基：,66,令非基变量,得基解,X8 是基可行解,67,问1：,是否是一个基?,否,因为此矩阵不可逆,或者说列向量组线性相关,68,问2：,是否是一个基?,否,因为此矩阵不可逆,或者说列向量组线性相关,69,最优解,全部基解：,70,上例中指出了一种求解线性规划问题的可能途径，就是先确定线性规划问题的基以及基解，如果是基可行解，则计算相应的解的目标函数值。由于基的个数是有限的（最多 个），因此必定可以从有限个基本可行解中找到最优解。,71,4x1=16,4x2=12,x1+ 2x2=8,x1,x2,4,8,4,3,0,Q1,约束直线的交点基解 可行域的顶点基可行解,Q2,Q3,Q4,Q5,Q6,Q7,Q8,1 4 3 -2 0 0 N Q72 2 3 0 8 0 Y Q3 3 4 2 0 0 4 Y Q2 4 4 0 4 0 12 Y Q15 8 0 0 -16 12 N Q66 0 3 2 16 0 Y Q47 0 4 0 16 -4 N Q88 0 0 8 16 12 Y Q5,是否基可行解,对应的点解,72,第二节 线性规划问题的几何意义,一、基本概念二、几个定理,73,一、 基本概念,凸集凸组合顶点,74,定义设K是n维欧氏空间的一点集，若任意两点X(1)K，X(2)K的连线上的所有点X(1)+(1)X(2)K，(01)，则称K为凸集。,1.凸集,凸,非凸,(a),(b),(d),(c),75,实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。任何两个凸集的交集是凸集，见下图所示：,76,设X(1)，X(2)，X(k)是n维欧氏空间En中的k个点。若存在1，2，k，且0i1, i=1,2,，k 使 X=1X(1)+2X(2)+kX(k)，成立 则称X为X(1)，X(2)，X(k)的一个凸组合（当0i1时，称为严格凸组合）。,2. 凸组合,77,设K是凸集，XK；若X不能用不同的两点X(1)K和X(2)K的线性组合表示为： X=X(1)+(1)X(2)，(01) 则称X为K的一个顶点(或极点)。,3. 顶点,凸集,凸集,78,二、几个定理,定理1 若线性规划问题存在可行域，则其可行域 是凸集。,79,定理1的证明：只需证明D中任意两点连线上的点必然在D内即可。 设X(1)、X(2) 是D内的任意两点；且X(1)X(2)。 AX(1)=A X(2)=b,AX=AX(1)+(1- )X(2),AX= AX(1)+A X(2) - AX(2),AX= b+b - b=b,XD,令X为X(1),X(2)连线上的任意一点，即 X=X(1)+(1-)X(2) (01)将它代入约束条件，得到,D是凸集,80,引理 1 线性规划问题的可行解X=(x1,x2,，xn)T为基可行解的充要条件是：X的正分量所对应的系数列向量是线性独立的。,证: (1) 必要性 由基可行解的定义可知。 (2) 充分性 若向量P1，P2，Pk线性独立， 则必有km； 当k=m时，它们恰构成一个基，从而 X=(x1,x2,xk,00)为相应的基可行解。 当km时，则一定可以从其余的列向量中取出m-k个与P1，P2，Pk构成最大的线性独立向量组，其对应的解恰为X，所以根据定义它是基可行解。,81,定理2 线性规划的可行解X是基可行解的充分必要条件是X是可行域D的顶点。,(1)充分性 ： X是可行域D的顶点 X是基可行解。 逆否命题 若X不是基可行解，则它一定不是可行域D的顶点。,82,根据引理1，若X不是基可行解，则其正分量所对应的系数列向量P1，P2，Pm线性相关，即存在一组不全为零的数i,i=1,2,m，使得 1P1+2P2+mPm=0 (1-9) 用一个数0乘(1-9)式再分别与(1-8)式相减和相加，得： (x11)P1+(x22)P2+(xm m)Pm=b (x1+1)P1+(x2+2)P2+(xm+m)Pm=b,不妨设X的前m个分量为正,则有,P1 x1 + Pm x m = b (1-8),83,现构造两个点X(1) ,X(2) 如下:,另一方面，当充分小时，可保证,则X(1) ,X(2) D, 且X1/2 X(1) + 1/2 X(2),所以 X 不是D的顶点.,X是 X(1) ， X(2)的中点,若X不是基可行解，则它一定不是可行域D的顶点。,84,因X不是可行域D的顶点，故在可行域D中可找到不同的两点 X(1)=(x1(1),x2(1),xn(1)T X(2)=(x1(2),x2(2),xn(2)T 使得 X=X(1)+(1) X(2) ， 01,（2）必要性 ： X是基可行解 X是可行域D的顶点。逆否命题 若X不是可行域D的顶点，则它一定不是基可行解。,85,假设X是基可行解， X的前m个分量为正，对应的向量组P1Pm线性独立，故当jm时，有xj=xj(1)=xj(2)=0。 由于X(1)，X(2)是可行域的两点，因而满足,将两式相减，得,因X(1)X(2)，所以上式中的系数不全为零，故向量组P1,P2,，Pm线性相关，与假设矛盾，即X不是基可行解。,若X不是可行域D的顶点，则它一定不是基可行解。,86,引理2 若K是有界凸集，则任何一点XK可表示为K的顶点的凸组合。 本引理的证明从略，用以下例子说明本引理的结论。例5 设X是三角形中任意一点，X(1)，X(2)和X(3)是三角形的三个顶点，试用三个顶点的坐标表示X(见图1-8),87,解：任选一顶点X(2)，做一条连线XX(2)，并延长交于X(1)、X(3)连接线上一点X。 因为X是X(1)、X(3)连线上一点，故可用X(1)、X(3)线性组合表示为：X=X(1)+(1)X(3) 01 又因X是X与X(2)连线上的一个点，故X=X+(1 )X(2) 01,X,88,将X的表达式X=X(1)+(1)X(3)代入式X=X+(1 )X(2) 得到X=X(1)+(1)X(3)+(1)X(2)=X(1)+(1 )X(3)+(1)X(2) 令 1=,2=(1 ),3=(1 )，得到X=1X(1)+2X(2)+3X(3)ii=1, 0i1,89,定理 3 若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。 证： 设X(1),X(2)，X(k)是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最优 z*=CX(0)(标准型是z*=max z)。 因X(0)不是顶点，所以它可以用D的顶点的凸组合表示。 代入目标函数得:,90,在所有的顶点中必然能找到某一个顶点X(m)，使CX(m)是所有CX(i)中最大者。并且将X(m)代替 中的所有X(i)，得到,由此得到 CX(0)CX(m)根据假设CX(0)是最大值，所以只能有 CX(0)=CX(m)即目标函数在顶点X(m)处也达到最大值。,91,定理4 ：目标函数可能在多个顶点处达到最大，这时在这些顶点的凸组合上也达到最大值，这时线性规划问题有无限多个最优解。证明：假设 是目标函数达到最大值的顶点，则对这些顶点的凸组合，有,92,设：于是：另外，若可行域为无界，则可能无最优解，也可能有最优解，若有最优解，也必定在某顶点上得到。,93,练习,证明：若X(1)、X(2)是线性规划的最优解，则X(1)、X(2)连接线段上的点也都是最优解。,则XX(1)+(1)X(2)，(01),CXCX(1)+(1)CX(2)，,CX(1)+ CX(2) CX(2),设 CX(1) CX(2)m，m为最优值,m+ m mm,X(1)、X(2)是线性规划的最优解,设X为X(1)、X(2)连接线段上的点,X是线性规划的最优解,证：,94,基本结论,线性规划问题的可行域是凸集（定理1）。可行域的每个顶点对应着一个基可行解，基可行解的个数是有限的，因此可行域的顶点个数也是有限的（定理2） 。若线性规划问题有最优解，必在某顶点上得到（定理3） 。顶点数目是有限的，若采用“枚举法”找所有基可行解，然后一一比较，最终必然能找到最优解。但当n,m较大时，这种办法是行不通的，所以要继续讨论如何有效寻找最优解的方法。,95,第三节 单纯形法,一、 初始基可行解的确定二、最优性检验与解的判断三、基变换四、迭代（旋转运算）,96,单纯形法的基本思路,要找到线性规划问题的最优解，只要在基本可行解中寻找就可以了。虽然基本可行解的数目是有限个（不超过Cnm个），但当m,n较大时，要用“穷举法”求出所有基本可行解也是行不通的。因此，必须寻求一种更有效的方法。单纯形法的基本思路是：从线性规划问题的一个基可行解开始，转换到另一个相邻的基可行解并使目标函数值增大。反复迭代，当目标函数值达到最大时，就得到了最优解。主要有三个问题：一是寻找初始基可行解，二是判别最优解，三是迭代。,97,单纯形法基本思路,是否最优解,求最优目标函数值,是,基变换,迭代,否,确定初始基可行解,98,引例,例6 试以例1来讨论如何用单纯形法求解。解：已知本例的标准型为：,99,约束条件(1-12)式的系数矩阵为:可看到x3,x4,x5的系数构成的列向量,P3 ,P4,P5是线性独立的，这些向量构成一个基B 。,100,对应于B的变量x3,x4,x5为基变量。,从(1-12)式中可以得到（1-13）,101,将(1-13)式代入目标函数(1-11)：得到：当令非基变量x1=x2=0，便得到z=0。这时得到一个基可行解X(0) X(0)=(0,0,8,16,12)T 本基可行解的经济含义是：工厂没有安排生产产品、，资源都没有被利用，所以工厂的利润为z=0。,102,从分析目标函数的表达式(1-14)可以看到： 非基变量x1,x2(即没有安排生产产品，)的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。 从经济意义上讲，安排生产产品或，就可以使工厂的利润指标增加。所以只要在目标函数(1-14)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换。,103,如何确定换入、换出变量一般选择正系数最大的那个非基变量x2为换入变量，将它换到基变量中，同时还要确定基变量中哪一个换出来成为非基变量。可按以下方法来确定换出变量：当将x2定为换入变量后，必须从x3,x4,x5中确定一个换出变量，并保证其余的变量仍然非负，即x3,x4,x50。,104,当x1=0时，由(1-13)式得到：,105,当x2取何值时，才能满足非负要求呢？ 从(1-15)式可看出，只有选择 x2=min(8/2,-,12/4)=3时，才能使(1-15)式成立。 因当x2=3时，基变量x5=0，这就决定用x2去替换x5。 以上数学描述说明，每生产一件产品，需要用掉的各种资源数为(2，0，4)。由这些资源中的薄弱环节，就确定了产品的产量。 这里就是由原材料B的数量确定了产品的产量x2=12/4=3件。,106,如何确定换入、换出变量为了求得以x3,x4,x2为基变量的一个基可行解和进一步分析问题，需将(1-13)中x2的位置与x5的位置对换，得到：,107,将(1-16)式中x2的系数列向量变换为单位列向量。其运算步骤是：=/4；=-2;=,并将结果仍按原顺序排列有：,高斯消去法,108,再将(1-17)式代入目标函数(1-11)式得到,从目标函数的表达式(1-18)可看到，非基变量x1的系数是正的，说明目标函数值还可以增大，即X(1)还不是最优解。,109,于是，再用上述方法确定换入、换出变量，继续迭代，得到另一个基可行解X(2)X(2)=(2,3,0,8,0)T 再经过一次迭代，又得到一个基可行解X(3)X(3)=(4,2,0,0,4)T 而这时得到目标函数的表达式是： z=141.5x3 0.125x4 (1-19) 再检查(1-19)式，可见所有非基变量x3,x4的系数都是负数，这说明若要用剩余资源x3,x4，就必须支付附加费用。 所以当x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。所以X(3)是最优解。即当产品生产4件，产品生产2件时，工厂可以得到最大利润。,110,小结,例1的线性规划问题是二维的，即有两个变量x1,x2。当加入松弛变量x3,x4,x5后，变换为高维的。这时可以想象，满足所有约束条件的可行域是高维空间中的凸多面体(凸集)。该凸多面体上的顶点，就是基可行解。初始基可行解为 X(0)=(0,0,8,16,12)T，对应于图中的原点(0，0)；X(1)=(0,3,2,16,0)T对应于图中的Q4点(0，3)； X(2)=(2，3，0，8，0)T对应于Q3点(2，3)；最优解X(3)=(4，2，0，0，4)T相当于图中的 Q2点(4，2)。,从初始基可行解X(0)开始迭代，依次得到X(1)，X(2)，X(3)，相当于图中的目标函数平移时，从0点开始，首先碰到Q4，然后碰到Q3，最后达到Q2。,111,一、初始基可行解的确定,为了确定初始基可行解，要首先找出初始可行基，且要求初始可行基为单位矩阵,令非基变量等于零,因为bi0,即可以得到初始基可行解。(1)直接观察(2)加松弛变量(3)加非负的人工变量,112,从线性规划问题 的系数构成的列向量Pj(j=1,2,n)中，通过直接观察，找出一个初始可行基,(1)直接观察,113,对所有约束条件为“”形式的不等式，利用化标准型的方法，在每个约束条件的左端加上一个松弛变量。经过整理，重新对xj及aij (i=1,2,m; j=1,2,n)进行编号，则可得下列方程组（x1,x2,xm 为松弛变量）：,(2)加松弛变量,114,于是，(1-22)中含有一个mm阶单位矩阵，初始可行基B即可取该单位矩阵。将(1-22)式每个等式移项得,115,令xm+1=xm+2=xn=0，由(1-23)式可得xi=bi (i=1,2,m)又因bi0(在前面已做过规定)，所以得到一个初始基可行解 X=(x1,x2,xm,0，0)T nm个 =(b1,b2,bm,0，0)T nm个,116,对所有约束条件为“”形式的不等式及等式约束情况，若不存在单位矩阵时，可采用人造基方法。即对不等式约束，减去一个非负的剩余变量，再加上一个非负的人工变量；对于等式约束，再加上一个非负的人工变量这样，总能在新的约束条件系数构成的矩阵中得到一个单位矩阵。,(3)加非负的人工变量,117,二、最优性检验与解的判别,由于线性规划问题的求解可能出现唯一最优解、无穷多最优解、无界解和无可行解等四种情况，因此，需要建立解的判别准则。一般情况下，经过迭代后(1-23)式变成 (1-24),118,将 代入目标函数，整理后得,119,令,120,若 为对应于基B的一个基可行解，且对于一切j=m+1,n，有j0，则X(0)为最优解。称j为检验数。,1、最优解的判别定理,121,若 为一个基可行解，对于一切j=m+1，,n，有j0，又存在某个非基变量的检验数m+k=0，则线性规划问题有无穷多最优解。 证: 只需将非基变量xm+k换入基变量中，找到一个新基可行解X(1)。 因m+k=0，由式（1-27） ，可知z=z0，故X(1)也是最优解。由定理4可知，X(0)和X(1)连线上所有点都是最优解。,2、无穷多最优解判别定理,122,为对应于基B的一个基可行解，且对于一切 jm+1,n，有j 0，则X（0）是唯一最优解。,若,3、唯一最优解判定定理,123,若 为一基可行解， 有一个m+k0，并且对i=1,2,，m，有ai,m+k0，那么该线性规划问题具有无界解(或称无最优解)。 证: 构造一个新的解 X(1)，它的分量为,4、无界解判别定理,124,因 ，所以对任意的 0都是可行解，把X(1)代入目标函数（1-27）内，得到z=z0+ m+k 因m+k0，故当 +，则z+，故该问题目标函数无界。,125,其它情形以上讨论都是针对标准型的，即求目标函数极大化时的情况。当要求目标函数极小化时：一种情况是将其化为标准型。如果不化为标准型，只需在上述1，2点中把j0改为j0；第3点中把j0；将第4点中将m+k0改写为m+k0即可。,126,三、基变换,若初始基可行解X(0)不是最优解及不能判别无界时，需要找一个新的基可行解。具体做法：从原可行解基中换一个列向量(当然要保证线性独立)，得到一个新的可行基，称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行对换，就得到一个新的基可行解。,127,1、换入变量的确定,由(1-27)式可知，当某些j0时，若xj增大，则目标函数值还可以增大。这时需要将某个非基变量xj换到基变量中去(称为换入变量)。若有两个以上的j0，那么选哪个非基变量作为换入变量呢?为了使目标函数值增加得快，从直观上看应选j0中的较大者，即由 应选择 xk 为换入变量。,128,2、换出变量的确定,不妨设迭代到某步,当前基可行解,129,系数矩阵,并确定选xk进基(k0)，设 xk 由 0 增加到，这时xm+1,xn中其他变量仍是非基变量 x m+1,x k-1, x k+1,x n0 =,最小比值规则,130,结论：经单纯形法得到的解,是基可行解，且z1 z0,L k,131,首先验证它是基可行解（1）非负性：由取法保证；（2）满足约束 容易验证 X1 满足下述约束方程组,132,（3）是基解： 只需要说明它的非零分量所对应的系数列向量线性独立。 X1的全部非零分量是 x 1x l-1,x k, x l+1x m,133,下面说明z1z0，因为选x k进基，所以必有k0,134,并且选定 xk 进基，x l 出基。,主元列,主元行,主元素,四、求新的基可行解,(1-34),不妨设迭代到某步,135,变换的步骤是：(1) 将增广矩阵(1-34)式中的第l行除以al k，得到,(2) 将(1-34)式中xk列的各元素，除al k变换为1以外，其他都应变换为零。其他行的变换是将(1-35)式乘以aik(iL)后，从(1-34)式的第i行减去，得到新的第i行。,136,由此可得到变换后系数矩阵各元素的变换关系式,是变换后的新元素。,137,经过初等变换后的新增广矩阵：,138,由(1-36)式中可以看到x1,x2,xk,，xm的系数列向量构成mm单位矩阵;它是可行基。当非基变量xm+1,，xl,xn为零时，就得到一个基可行解X(1),在上述系数矩阵的变换中，元素al k称为主元（素），它所在列称为主（元）列，它所在行称为主（元）行，元素al k位置变换后为1。,139,小结,初始基可行解的确定 B0I，XB=b (右边项)，XN=0最优性检验计算检验数,140,基变换-过渡到下一个相邻基可行解进基：选k 0，有多个选最大的一个出基：最小比值规则求新的基可行解用消去法将主列Pk变成,xl 出基,141,第四节 单纯型法的计算步骤,一、单纯型表二、计算步骤,142,一、 单纯型表,为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似。将(1-22)式与目标函数组成n+1个变量，m+1个方程的方程组。,143,144,为了便于迭代运算，可将上述方程组写成增广矩阵形式,若将-z看作不参与基变换的基变量，它与x1,x2,xm的系数构成一个基，这时可采用初等行变换将c1,c2,cm变换为零，使其对应的系数矩阵为单位矩阵。,145,经初等行变换，得到,-Z0,检验数cj-zj,146,E单位阵,N非基阵,基变量XB,非基变量XN,0,147,2 1 0 0 0,检验数,单纯形表结构,C,已知,148,2 1 0 0 0,24/65/1,C,检验数,单纯形表结构,基可行解：,149,单纯形表结构,2 1 0 0 0,24/65/1,C,检验数,有时不写此项,求,150,单纯形表结构,2 1 0 0 0,24/65/1,C,检验数,求,151,单纯形表结构,2 1 0 0 0,24/65/1,C,检验数,求,不妨设此为主元列,主元行,152,单纯形表结构,2 1 0 0 0,24/65/1,C,检验数,主元素,153,二、计算步骤,(1) 按数学模型确定初始可行基和初始基可行解，建立初始单纯形表。(2) 计算各非基变量xj的检验数， 检查检验数，若所有检验数 则已得到最优解，可停止计算。否则转入(3)。,154,(3)在j0,j=m+1,n中，若有某个k对应xk的系数列向量Pk0，则此问题是无界，停止计算。 否则，转入(4)。(4) 根据max(j0)=k，确定xk为换入变量，按规则计算,可确定xl为换出变量，转入(5),155,(5) 以alk为主元素进行迭代(即用高斯消去法或称为旋转运算)，把xk所对应的列向量 将XB列中的xl换为xk，得到新的单纯形表。重复(2)(5)，直到终止。,156,现用例1说明上述计算步骤,157,例1的标准型为：,158,16 4 0 1 0,2 0 0 -3/4,4-3,3 0 0 0 1/4,2 1 1 0 -1/2,24-,X(0)=(0,0,8,16,12)T Z=0,X(1)=(0,3,2,16,0)T Z=9,159,X(3)=(2,3,0,8,0)T Z=13,-412,2 1 0 1 0 -1/2,最优解：X*=（4，2，0，0，4）TZ*=14,160,4x1=16,4x2=12,x1+ 2x2=8,x1,x2,4,8,4,3,0,Q1,Q2,Q3,Q4,Q5,Q6,Q7,Q8,X(0)=(0, 0, 8,16,12)T,X*=(4，2，0，0，4)T,X(1)=(0，3，2，16，0)T,X(2)=(2，3，0，8，0)T,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,161,练习：若在初始单纯形表中，先选x1进基，结果如何？,X(0)=(0,0,8,16,12)T Z=0,162,X(1)=(4,0,4,0,12)T Z=8,84-,4 0 0 0,2-3,练习答案,4 2 1 - 0,12 4 0 0 1,3 0 -1/2 0,163,最优解：X*=（4，2，0，0，4）TZ=14,164,4x1=16,4x2=12,x1+ 2x2=8,x1,x2,4,8,4,3,0,Q1,Q2,Q3,Q4,Q5,Q6,Q7,Q8,X(0)=(0, 0, 8,16,12)T,X*=(4，2，0，0，4)T,X(1)=(4，0，4，0，12)T,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,单纯形法计算中，选取最大正检验数k对应的变量xk作为换入变量，不一定是最优的策略。,165,4x1=16,4x2=12,x1+ 2x2=8,x1,x2,4,8,4,3,0,Q1,Q2,Q3,Q4,Q5,Q6,Q7,Q8,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0,单纯形法计算中，选取最大正检验数k对应的变量xk作为换入变量，会不会使目标函数值在下一次迭代中增加最快?,166,4x1=20,4x2=12,x1+ 2x2=8,x1,x2,4,8,5,3,0,Q1,Q2,Q3,Q4,Q5,Q6,Q7,Q8,目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 4x2 12 x1、 x2 0,单纯形法计算中，选取最大正检验数k对应的变量xk作为换入变量，会不会使目标函数值在下一次迭代中增加最快? 不一定,20,167,练习 用单纯形表求解LP问题,168,解：化标准型,169,2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0,主元素化为1主元列单位向量 换出 换入,表1：列初始单纯形表 （单位矩阵对应的变量为基变量）,正检验数中最大者对应的列为主元列,最小的值对应的行为主元行,170,2 1 0 0 0 0 15 0 5 1 0 0 2 4 1 2/6 0 1 /6 0 0 1 0 4/6 0 -1/6 1 0 1/3 0 -1/3 0,表2：换基 （初等行变换，主元列化为单位向量，主元素为1）,检验数0确定主元列,最小确定主元行,主元素,171,检验数=0,最优解为X=(7/2,3/2,15/2,0,0)目标函数值Z=8.5,表3：换基 （初等行变换，主元列化为单位向量，主元素为1）,172,无穷多解举例,用单纯形表求解LP问题,173,解：化标准型,174,3 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 3 1 0 0 0,主元素化为1主列单位向量 换出 换入,表1：列初始单纯形表 （单位矩阵对应的变量为基变量）,正检验数中最大者对应的列为主元列,最小的值对应的行为主元行,175,3 1 0 0 0 0 15 0 5 1 0 0 3 4 1 2/6 0 1 /6 0 0 1 0 4/6 0 -1/6 1 0 0 0 -1/2 0,表2：换基 （初等行变换，主元列化为单位向量，主元素为1）,非基变量检验数=0，多解,检验数=0,最优解为X（1）=(4,0,15,0,1)目标函数值Z=12,176,3 1 0 0 0 0 15 0 5 1 0 0 3 4 1 2/6 0 1 /6 0 0 1 0 4/6 0 -1/6 1 0 0 0 -1/2 0,表2：换基 （初等行变换，主元列化为单位向量，主元素为1）,选此列作主元列，求另一个最优基可行解,最小确定主元行,主元素,177,检验数=0,最优解为X（2）=(7/2,3/2,15/2,0,0)目标函数值Z=12,表3：换基 （初等行变换，主元列化为单位向量，主元素为1）,178,全部最优解可以表示成：X1（1）X2，01,称为X1与X2的凸组合,179,凸组合设X1，X2，.，Xk，是n维欧氏空间En中的k个点。若存在u1，u2，.，uk，且,使得,则称X是X1，X2，.，Xk的凸组合。,180,无界解举例,181,0 x3 2 1 -1 1 0,0 x4 4 -3 1 0 1,3 2 0 0,3 2 0 0,2 ,无界解,182,第五节 单纯形法的进一步