线性规划与单纯形法清华大学运筹学件.pptx
会计学1线性规划与单纯形法清华大学运筹学件线性规划与单纯形法清华大学运筹学件第第1章章 线性规划与单纯形法线性规划与单纯形法 第第第第2 2节线性规划问题的几何意义节线性规划问题的几何意义节线性规划问题的几何意义节线性规划问题的几何意义n n2.1 基本概念n n2.2 几个定理第1页/共39页2.1 基本概念基本概念1.1.凸集2.2.凸组合3.3.顶点第2页/共39页1.1.凸集凸集n n设设K K是是n n维维欧欧氏氏空空间间的的一一点点集集，若若任任意意两两点点X X(1)(1)K K，X X(2)(2)K K的的连连线线上上的的所所有有点点XX(1)(1)+(1-)X+(1-)X(2)(2)K K，(01)(01)；则称；则称K K为凸集。为凸集。n n 图图1-71-7第3页/共39页n n实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。图1-7中的(a)(b)是凸集，(c)不是凸集。n n图1-2中的阴影部分 是凸集。n n任何两个凸集的交集是凸集，见图1-7(d)第4页/共39页2.凸组合凸组合 n n设设X X(1)(1)，X X(2)(2)，X X(k)(k)是是n n维维欧欧氏氏空空间间E E中中的的k k个个点点。若存在若存在 1 1，2 2，k k，且，且0i1,i=1,2,0i1,i=1,2,，k;k;n n使使X=X=1 1X X(1)(1)+2 2X X(2)(2)+k kX X(k)(k)n n则则称称X X为为X X(1)(1)，X X(2)(2)，X X(k)(k)的的凸凸组组合合。（当当0 0 i i1 1时，称为严格凸组合）时，称为严格凸组合）.第5页/共39页3.顶点顶点n n设设K K是是凸凸集集，X XK K；若若X X不不能能用用不不同同的的两两点点X X(1)(1)K K和和X X(2)(2)K K的线性组合表示为的线性组合表示为n nX=XX=X(1)(1)+(1-)X+(1-)X(2)(2)，(0(0 1)1)n n则称则称X X为为K K的一个顶点的一个顶点(或极点或极点)。n n图中图中0 0，QQ1 1,2,3,42,3,4都是顶点。都是顶点。第6页/共39页2.2 几个定理几个定理n n定理1 若线性规划问题存在可行域，则其可行域n n是凸集 第7页/共39页证：为了证明满足线性规划问题的约束条件证：为了证明满足线性规划问题的约束条件证：为了证明满足线性规划问题的约束条件证：为了证明满足线性规划问题的约束条件的所有点(可行解)组成的集合是凸集，只要证明D中任意两点连线上的点必然在D内即可。设是D内的任意两点；X(1)X(2)。第8页/共39页第9页/共39页第10页/共39页引理引理引理引理 1 1 线性规划问题的可行解线性规划问题的可行解线性规划问题的可行解线性规划问题的可行解X=(xX=(x1 1,x,x2 2,，x xn n)T T为为为为基可行解的充要条件是基可行解的充要条件是基可行解的充要条件是基可行解的充要条件是X X的正分量所对应的系数列向的正分量所对应的系数列向的正分量所对应的系数列向的正分量所对应的系数列向量是线性独立的。量是线性独立的。量是线性独立的。量是线性独立的。第11页/共39页定理定理定理定理2 2 2 2 线性规划问题的基可行解线性规划问题的基可行解线性规划问题的基可行解线性规划问题的基可行解X X X X对应于可行对应于可行对应于可行对应于可行 D D D D的顶点。的顶点。的顶点。的顶点。证证：不失一般性，假设基可行解X的前m个分量为正。故现在分两步来讨论，分别用反证法。（1-8）第12页/共39页(1)(1)(1)(1)若若若若X X X X不是基可行解，不是基可行解，不是基可行解，不是基可行解，则它一定不是可行域则它一定不是可行域则它一定不是可行域则它一定不是可行域D D D D的顶点的顶点的顶点的顶点n n根据引理1，若X不是基可行解，则其正分量所对应的系数列向量P1，P2，Pm线性相关，即存在一组不全为零的数i,i=1,2,m使得n n1P1+2P2+mPm=0 (1-9)n n用一个0的数乘(1-9)式再分别与(1-8)式相加和相减，。第13页/共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)连线的中点第14页/共39页另一方面，当另一方面，当另一方面，当另一方面，当充分小时，可保证充分小时，可保证充分小时，可保证充分小时，可保证 n nxii0，i=1,2,mn n即X(1)，X(2)是可行解。n n这证明了X 不是可行域 D 的顶点。第15页/共39页(2)(2)(2)(2)若若若若X X X X不是可行域不是可行域不是可行域不是可行域D D D D的顶点，则它一定不是基可行解的顶点，则它一定不是基可行解的顶点，则它一定不是基可行解的顶点，则它一定不是基可行解因为X不是可行域 D 的顶点，故在可行域D中可找到不同的两点n nX(1)=(x1(1),x2(1),xn(1)Tn nX(2)=(x1(2),x2(2),xn(2)Tn n使 X=X(1)+(1-)X(2)，01n n设X是基可行解，对应向量组P1Pm线性独立。当jm时，有xj=xj(1)=xj(2)=0，由于X(1)，X(2)是可行域的两点。应满足第16页/共39页将这两式相减，即得第17页/共39页n n因X(1)X(2)，所以上式系数不全为零，故向量组P1,P2,，Pm线性相关，与假设矛盾。即X不是基可行解。第18页/共39页引理引理引理引理2 2 若若若若K K是有界凸集，则任何一点是有界凸集，则任何一点是有界凸集，则任何一点是有界凸集，则任何一点X XK K可表示为可表示为可表示为可表示为K K的顶点的顶点的顶点的顶点的凸组合。的凸组合。的凸组合。的凸组合。n n本引理证明从略，用以下例子说明这引理。本引理证明从略，用以下例子说明这引理。n n例5 设X是三角形中任意一点，X(1),X(2)和X(3)是三角形的三个顶点，试用三个顶点的坐标表示X(见图1-8)第19页/共39页解解解解 任选一顶点任选一顶点任选一顶点任选一顶点X X X X(2)(2)(2)(2)，做一条连线，做一条连线，做一条连线，做一条连线XXXXXXXX(2)(2)(2)(2)；并延长交于；并延长交于；并延长交于；并延长交于X X X X(1)(1)(1)(1)、X X X X(3)(3)(3)(3)连接线上一点连接线上一点连接线上一点连接线上一点XXXX。因。因。因。因XXXX是是是是X(1)X(1)X(1)X(1)、X(3)X(3)X(3)X(3)连线连线连线连线上一点，故可用上一点，故可用上一点，故可用上一点，故可用X X X X(1)(1)(1)(1)、X X X X(3)(3)(3)(3)线性组合表示为线性组合表示为线性组合表示为线性组合表示为n nX=X(1)+(1-)X(3)01n n又因X是X与X(2)连线上的一个点，故n nX=X+(1-)X(2)01n n将X的表达式代入上式得到n nX=X(1)+(1-)X(3)+(1-)X(2)n n=X(1)+(1-)X(3)+(1-)X(2)第20页/共39页令令令令 1 1 1 1=,=,=,=,2 2 2 2=(1-),=(1-),=(1-),=(1-),3 3 3 3=(1-)=(1-)=(1-)=(1-)n n这就得到n nX=1X(1)+2X(2)+3X(3)n nii=1,0i1第21页/共39页定理定理定理定理 3 3 若可行域有界，线性规划问题的目标函若可行域有界，线性规划问题的目标函若可行域有界，线性规划问题的目标函若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。数一定可以在其可行域的顶点上达到最优。数一定可以在其可行域的顶点上达到最优。数一定可以在其可行域的顶点上达到最优。证证 设X(1),X(2)，X(k)是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最优z*=CX(0)(标准型是z=max z)。因X(0)不是顶点，所以它可以用D的顶点线性表示为第22页/共39页定理定理3的证明：的证明：证：证：设X(1),X(2)，X(k)是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最优z*=CX(0)(标准型是z=max z)。第23页/共39页代入目标函数得代入目标函数得代入目标函数得代入目标函数得在所有的顶点中必然能找到某一个顶点X(m)，使CX(m)是所有CX(i)中最大者。并且将X(m)代替(1-10)式中的所有X(i)，这就得到（1-10）第24页/共39页n n由此得到 X(0)CX(m)n n根据假设CX(0)是最大值，所以只能有 CX(0)=CX(m)n n即目标函数在顶点X(m)处也达到最大值。有时目标函数可能在多个顶点处达到最大;这时在这些顶点的凸组合上也达到最大值。称这种线性规划问题有无限多个最优解。第25页/共39页假设假设假设假设是目标函数达到最大值的顶点，若是这些顶点的凸组合，即是目标函数达到最大值的顶点，若是这些顶点的凸组合，即是目标函数达到最大值的顶点，若是这些顶点的凸组合，即是目标函数达到最大值的顶点，若是这些顶点的凸组合，即于是设：第26页/共39页于是：于是：第27页/共39页另外，若可行域为无界，则可能无最优解，也可能有另外，若可行域为无界，则可能无最优解，也可能有另外，若可行域为无界，则可能无最优解，也可能有另外，若可行域为无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上得到。根据以上讨论，最优解，若有也必定在某顶点上得到。根据以上讨论，最优解，若有也必定在某顶点上得到。根据以上讨论，最优解，若有也必定在某顶点上得到。根据以上讨论，可以得到以下结论：可以得到以下结论：可以得到以下结论：可以得到以下结论：线线性性规规划划问问题题的的所所有有可可行行解解构构成成的的集集合合是是凸凸集集，也也可可能能为为无无界界域域，它它们们有有有有限限个个顶顶点点，线线性性规规划划问问题题的的每个基可行解对应可行域的一个顶点；每个基可行解对应可行域的一个顶点；若若线线性性规规划划问问题题有有最最优优解解，必必在在某某顶顶点点上上得得到到。虽虽然然顶顶点点数数目目是是有有限限的的(它它不不大大于于个个)，若若采采用用“枚枚举举法法”找找所所有有基基可可行行解解，然然后后一一一一比比较较，最最终终可可能能找找到到最最优优解解。但但当当n,mn,m的的数数较较大大时时，这这种种办办法法是是行行不不通通的的，所所以以要要继继续续讨讨论论，如如何何有有效效地地找找到到最最优优解解，有有多种方法，多种方法，这里仅介绍这里仅介绍单纯形法单纯形法。第28页/共39页第第2节节 结束结束第29页/共39页第30页/共39页第31页/共39页第32页/共39页第33页/共39页第34页/共39页第35页/共39页第36页/共39页第37页/共39页第38页/共39页
