+线性规划与单纯形法运筹学第三版课件.ppt

1、运筹学运筹学（第三版）运筹学教材编写组 编清华大学出版社 第1章 线性规划与单纯形法 第2节 线性规划问题的几何意义钱颂迪 制作第1页，共39页。第1章 线性规划与单纯形法 第2节线性规划问题的几何意义 2.1 基本概念 2.2 几个定理第2页，共39页。2.1 基本概念凸集凸组合顶点第3页，共39页。1.凸集 设K是n维欧氏空间的一点集，若任意两点X(1)K，X(2)K的连线上的所有点X(1)+(1-)X(2)K，(01)；则称K为凸集。图1-7第4页，共39页。实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。图1-7中的(a)(b)是凸集

2、，(c)不是凸集。图1-2中的阴影部分 是凸集。任何两个凸集的交集是凸集，见图1-7(d)第5页，共39页。2.凸组合 设X(1)，X(2)，X(k)是n维欧氏空间E中的k个点。若存在1，2，k，且0i1,i=1,2,，k;使X=1X(1)+2X(2)+kX(k)则称X为X(1)，X(2)，X(k)的凸组合。（当0i1时，称为严格凸组合）.kii11第6页，共39页。3.顶点 设K是凸集，XK；若X不能用不同的两点X(1)K和X(2)K的线性组合表示为 X=X(1)+(1-)X(2)，(01)则称X为K的一个顶点(或极点)。图中0，Q1,2,3,4都是顶点。第7页，共39页。2.2 几个定理

3、定理1 若线性规划问题存在可行域，则其可行域 是凸集 njjjjxbxPXD10,第8页，共39页。证：为了证明满足线性规划问题的约束条件njjjjnjxbxP1,2,1,0,的所有点(可行解)组成的集合是凸集，只要证明D中任意两点连线上的点必然在D内即可。设是D内的任意两点；X(1)X(2)。TnTnxxxXxxxX222212112111,第9页，共39页。则有 njjjjnjjjjnjxbxPnjxbxP122111,2,1,0,2,1,0,令 X=(x1，x2，xn)T为 x(1),x(2)连线上的任意一点，即 X=X(1)+(1-)X(2)(01)X 的每一个分量是 21)1(jjj

4、xxx，将它代入约束条件，得到 第10页，共39页。bbbbxPxPxPxxPxPnjnjjjjjnjjjnjnjjjjjj11221111211又因 01,0,0,21jjxx，所以 xj0，j=1,2,n。由此可见 XD，D 是凸集。证毕。第11页，共39页。引理 1 线性规划问题的可行解X=(x1,x2,，xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。证证:(1)必要性由基可行解的定义可知。(2)充分性若向量P1，P2，Pk线性独立，则必有 km；当 k=m 时，它们恰构成一个基，从而 X=(x1,x2,xk,00)为相应的基可行解。当 km 时，则一定可以从其

5、余的列向量中取出 m-k 个与 P1，P2，Pk 构成最大的线性独立向量组，其对应的解恰为 X，所以根据定义它是基可行解。第12页，共39页。定理定理2 2 线性规划问题的基可行解X对应于可行 D的顶点。证：证：不失一般性，假设基可行解X的前m个分量为正。故mjjjbxP1现在分两步来讨论，分别用反证法。（1-8）第13页，共39页。若X不是基可行解，则它一定不是可行域D的顶点 根据引理1，若X不是基可行解，则其正分量所对应的系数列向量P1，P2，Pm线性相关，即存在一组不全为零的数i,i=1,2,m使得 1P1+2P2+mPm=0 (1-9)用一个0的数乘(1-9)式再分别与(1-8)式相加

6、和相减，。第14页，共39页。这样得到(x1-1)P1+(x2-2)P2+(xm-m)Pm=b(x1+1)P1+(x2+2)P2+(xm+m)Pm=b 现取X(1)=(x1-1),(x2-2),(xm-m),0,，0X(2)=(x1+1),(x2+2),(xm+m),0,，0由X(1),X(2)可以得到X=（1/2）X(1)+（1/2）X(2)，即X是X(1)，X(2)连线的中点第15页，共39页。另一方面，当充分小时，可保证 xii0，i=1,2,m 即X(1)，X(2)是可行解。这证明了X 不是可行域 D 的顶点。第16页，共39页。(2)若X不是可行域D的顶点，则它一定不是基可行解因为X

7、不是可行域 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 设X是基可行解，对应向量组P1Pm线性独立。当jm时，有xj=xj(1)=xj(2)=0，由于X(1)，X(2)是可行域的两点。应满足第17页，共39页。mjmjjjjjbxPbxP1121与 mjjjjxxP1210将这两式相减，即得第18页，共39页。因X(1)X(2)，所以上式系数不全为零，故向量组P1,P2,，Pm线性相关，与假设矛盾。即X不是基可行解。第19页，共39页。引理2 若K是有界

8、凸集，则任何一点XK可表示为K的顶点的凸组合。本引理证明从略，用以下例子说明这引理。例5 设X是三角形中任意一点，X(1),X(2)和X(3)是三角形的三个顶点，试用三个顶点的坐标表示X(见图1-8)第20页，共39页。解 任选一顶点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的表达式代入上式得到 X=X(1)+(1-)X(3)+(1-)X(2)=X(1)+(1-)X(3)+(1

9、-)X(2)第21页，共39页。令 1=,2=(1-),3=(1-)这就得到 X=1X(1)+2X(2)+3X(3)ii=1,0i1第22页，共39页。定理 3 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。证证 设X(1),X(2)，X(k)是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最优z*=CX(0)(标准型是z=max z)。因X(0)不是顶点，所以它可以用D的顶点线性表示为 kikiiiiiixX1101,0,第23页，共39页。定理3的证明：证：证：设X(1),X(2)，X(k)是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达

10、到最优z*=CX(0)(标准型是z=max z)。第24页，共39页。代入目标函数得 kikiiiiiCXXCCX110在所有的顶点中必然能找到某一个顶点X(m)，使CX(m)是所有CX(i)中最大者。并且将X(m)代替(1-10)式中的所有X(i)，这就得到（1-10）mkimikiiiCXCXCX11第25页，共39页。由此得到 X(0)CX(m)根据假设CX(0)是最大值，所以只能有 CX(0)=CX(m)即目标函数在顶点X(m)处也达到最大值。有时目标函数可能在多个顶点处达到最大;这时在这些顶点的凸组合上也达到最大值。称这种线性规划问题有无限多个最优解。第26页，共39页。假设是目标函

11、数达到最大值的顶点，若是这些顶点的凸组合，即 1X，2X，kX kikiiiiiXX111,0,于是 kiiikiiiXCXCXC11 kimXCi,2,1,设：第27页，共39页。于是：mmXCkii1第28页，共39页。另外，若可行域为无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上得到。根据以上讨论，可以得到以下结论：线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，必在某顶点上得到。虽然顶点数目是有限的(它不大于个)，若采用“枚举法”找所有基可行解，然后一一比较，最终可能找到最优解。但当n,m的数较大时，这种办法是行不通的，所以要继续讨论，如何有效地找到最优解，有多种方法，这里仅介绍单纯形法。第29页，共39页。第2节 结束第30页，共39页。第31页，共39页。第32页，共39页。第33页，共39页。第34页，共39页。第35页，共39页。第36页，共39页。第37页，共39页。第38页，共39页。第39页，共39页。