《线性规划问题的几何意义》由会员分享，可在线阅读，更多相关《线性规划问题的几何意义（29页珍藏版）》请在金锄头文库上搜索。
1、 两个变量的两个变量的LPLP的解的启示：的解的启示： (1)(1)可行域非空时，它是有界或无界凸多边形（ 凸集） ，顶点个数只有有限个。(4)(4)若最优解存在，则最优解或最优解之一一定是 可行域的凸集的某个顶点。(5)(5)若在两个顶点上同时取到最优解，则这两点的 连线上 任一点都是最优解(2)(2)求解线性规划问题时，解的情况有：唯一最优解；无穷多最优解；无界解；无可行解。 (3)(3)若可行域非空且有界则必有最优解，若可行域无 界，则可能有最优解，也可能无最优解。2.1 基本概 念凸集 凸组合 顶点1.凸集定义定义1 1：设K是n维欧氏空间的一点集，若任意两点X(1)K，X(2)K以及
2、实数 0，1使X X(1)(1)+(1-+(1-)X)X(2)(2)K K，；则称K为凸集凸集。 凸集凸集注意注意: 空集和单点集也是凸集。几何意义几何意义：如果集合中任意两点连线上的一切点 都在该集合中，则称该集合为凸集。 非凸集非凸集凸集性质凸集性质 二个凸集的二个凸集的交交还是凸集还是凸集 二个凸集的二个凸集的并并不一定是凸集不一定是凸集v实心圆，实心球体，实心立方体等都是凸集，圆环 不是凸集。从直观上讲，凸集没有凹入部分，其内 部没有空洞。图1-7中的(a)(b)是凸集，(c)不是凸集 。v图1-2中的阴影部分是凸集。2. 凸组合 vv定义定义2 2：设X(1)，X(2)，X(k)是n
3、维欧氏空间En中的k个点。若存在1，2，k，满足 (1)0i1, i=1,2,，k; (2)且使X=1X(1)+2X(2)+kX(k)则称X为X(1)，X(2)，X(k)的凸组合凸组合。（当0i1时，称为严格凸组合）.3. 顶 点定义定义3 3：设K是凸集，XK； 若x不能成为K中任意两个不同的点X(1)、X(2)的连线上的一个内点，则称X 为K的一个顶点顶点(或极点极点)。 定义定义3 3 ：设K是凸集，XK；若X不能用K中任意不同的两 点X(1)和X(2)的线性组合表示为 X=X(1)+(1-)X(2) ，(01) ，则称X为K的一个顶点顶点(或极点极点)。 v图中O,Q1,Q2,Q3,Q
4、4都是顶点。多边形上的点是顶点多边形上的点是顶点圆周上的点都是顶点圆周上的点都是顶点2.2 几个 定理定理1 : 若线性规划问题存在可行域，则其可行域 是凸 集 证：为了证明满足线性规划问题的约束条件的所有点的所有点( (可行解可行解) )组成的集合是凸集，组成的集合是凸集， 只要证明只要证明D D中任意两点连线上的点必然在中任意两点连线上的点必然在D D内即可。内即可。是D内任意两点；X(1) X(2)设：设：v则有v令X=(x1，x2，xn)T为x(1) , x(2)连线上的任意 一点，即v X=X(1) +(1-)X(2) (01)vX的每一个分量是v将它代入约束条件，引理 1 ：线性规
5、划问题的可行解X=(x1,x2, ，xn)T为基可行解的充要条件是X的正分量所 对应的系数列向量是线性独立的。 vv证证: (1) 必要性 由基可行解的定义可知。v (2) 充分性 若向量P1，P2，Pk线性独立，则必有km；v当k=m时，它们恰构成一个基，v从而X=(x1,x2,xk,00)为相应的基可行解。v当km时，则一定可以从其余的列向量中取出m- k个与P1，P2，Pk构成最大的线性独立向量组 ，其对应的解恰为X，v所以根据定义它是基可行解。定理2 ：线性规划问题的基可行解X对 应于 可行 域D的顶点。证证：不失一般性，假设基可行解X的前m个分量为正 。故现在分两步来讨论，分别用反证
6、法。（1-8）(1)若X不是基可行解，则它一定不是可行域D的 顶点 v根据引理1，若X不是基可行解，则其正分量所 对应的系数列向量P1，P2，Pm线性相关，v即存在一组不全为零的数i,i=1,2,m使得 1P1+2P2+mPm=0 (1-9)v用一个0的数乘(1-9)式再分别与(1-8)式相 加和相减，这样得到 (x1-1)P1+(x2-2)P2+(xm-m)Pm=b (x1+1)P1+(x2+2)P2+(xm+m)Pm=b另一方面，当充分小时，可保证 xii0，i=1,2,m即X(1)，X(2)是可行解 。v这证明了X 不是可行域 D 的顶点。 现取 X(1)=(x1-1),(x2-2),(
7、xm-m),0,，0 X(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)连线的中点(2) 若X不是可行域D的顶点，则它一 定不是基可行解因为X不是可行域 D 的顶点，故在可行域D中可找到不 同的两点 X(1)=(x1(1),x2(1),xn(1)T X(2)=(x1(2),x2(2),xn(2)Tv使 X=X(1)+(1-) X(2) ， 01v设X是基可行解，对应向量组P1Pm线性独立。v当jm时，有xj=xj(1)=xj(2)=0，由于X(1)，X(2)是可行 域的两点。应满足
8、将这两式相减，即得v因X(1)X(2)，所以上式系数不全为零，故向量组P1,P2,， Pm线性相关，与假设矛盾。即X不是基可行解。引理2： 若K是有界凸集，则任何一 点 XK可表示为K的顶点的凸组合。 v本引理证明从略，用以下例子说明这引理 。vv例例5 5： 设X是三角形中任意一点，X(1),X(2) 和X(3)是三角形的三个顶点，试用三个顶点 的坐标表示X(见图1-8) x x1 1x x2 2X X(1)(1)X X(2)(2)X X(3)(3)X XXXX =X =X X+(1-+(1-)X)X(2)(2)(0 (0 1) 1)X=X= X X(1) (1) +(1- +(1- )X)
9、X(3)(3)(0 (0 1) 1)解：任选一顶点X(2)，做一条连线XX(2)；并 延长交 于X(1)、X(3)连接线上一点X。因 X是X(1) 、X(3)连线上一点，故可用X(1)、 X(3)线性组合表示为 vX=X(1)+(1-)X(3) 01v又因X是X与X(2)连线上的一个点，故vX=X+(1-)X(2) 01v将X的表达式代入上式得到vX=X(1)+(1-)X(3)+(1-)X(2)v=X(1)+(1-)X(3)+(1-)X(2) 令 1=,2=(1-),3=(1-)v这就得到 X=1X(1)+2X(2)+3X(3)vii=1,0i1定理 3 若可行域有界，线性规划问题的目标 函数
10、一定可以在其可行域的顶点上达到最优 。 证证：设X(1),X(2)，X(k)是可行域的顶点，若X(0)不是顶点 ，且目标函数在X(0)处达到最优z*=CX(0)(标准型是 z=max z)。因X(0)不是顶点，所以它可以用D的顶点线 性表示为（1- 10）在所有的顶点中必然能找到某一个顶点X(m)，使CX(m)是所 有CX(i)中最大者。并且将X(m)代替(1-10)式中的所有X(i)，这 就得到因为 ：v由此得到 CX(0)CX(m)v根据假设CX(0)是最大值，所以v只能有 CX(0)=CX(m)v即目标函数在顶点X(m)处也达到最大值 。假设 是目标函数达到最大 值的顶点，若是这些顶点的
11、凸组合，即于是设：，于 是 ：结论：若目标函数在多个顶点处达到最大结论：若目标函数在多个顶点处达到最大; ;这时在这时在 这些顶点的凸组合上也达到最大值。此时，称这这些顶点的凸组合上也达到最大值。此时，称这 种线性规划问题有无限多个最优解。种线性规划问题有无限多个最优解。可行域为非封闭的无界区域唯一最优解 无穷多个最优解 无界解结论：若可行域为无界，则可能无最优解，也可能结论：若可行域为无界，则可能无最优解，也可能 有最优解，若有，必在某个顶点上得到。有最优解，若有，必在某个顶点上得到。有益的启示有益的启示：v在可行域中寻找线性规划问题的最优解可以转化为只在可行域的顶点中找。由于凸多边形的顶点
12、是有限的，因而基可 行解的个数也是有限的，v这就保证了线性规划若有最优解，一定 可以在有限步内得到最优解。从而把一 个无限的问题转化为一个有限的问题v线性规划问题若存在两个或两个以上的 最优解，则一定有无穷多个最优解小结线小结线性规划的基本定理性规划的基本定理定理定理1 1 线性规划问题的可行解集是凸集。（线性规划问题的可行解集是凸集。（ 即连接线性规划问题任意两个可行解的线段即连接线性规划问题任意两个可行解的线段 上的点仍然是可行解。上的点仍然是可行解。) ) 引理引理1 1 线性规划问题的可行解线性规划问题的可行解x x为基可行解为基可行解 的充分必要条件是：的充分必要条件是：x x的非零
13、（或正）分量的非零（或正）分量 所对应的系数矩阵的列向量是线性无关。所对应的系数矩阵的列向量是线性无关。 定理定理2 2 线性规划问题的可行解集线性规划问题的可行解集D D中的点中的点x x 是顶点的充分必要条件是：是顶点的充分必要条件是：x x是基可行解。是基可行解。 推论推论 可行解集可行解集D D中的顶点个数是有限的。中的顶点个数是有限的。引理引理2 2 若可行解集若可行解集D D是有界的凸集，则是有界的凸集，则D D 中任意一点中任意一点x x，都可表示成都可表示成D D的顶点的凸组的顶点的凸组 合。合。 定理定理3 3 若可行解集若可行解集D D有界，则线性规划问题有界，则线性规划问
14、题 的最优解，必定在的最优解，必定在D D的顶点上达到。的顶点上达到。结论结论1 1 若可行解集若可行解集D D无界，则线性规划问题无界，则线性规划问题 可能有最优解，也可能无最优解。若有最优可能有最优解，也可能无最优解。若有最优 解，也必在顶点上达到。解，也必在顶点上达到。结论结论2 2 若目标函数在多个顶点上达到最优若目标函数在多个顶点上达到最优 值。则这些顶点的凸组合也是最优值。（有值。则这些顶点的凸组合也是最优值。（有 无穷多最优解）无穷多最优解）线性规划问题的所有可行解构成的集合是凸集 ，也可能为无界域，它们有有限个顶点，线 性规划问题的每个基可行解对应可行域的一 个顶点； 若线性规划问题有最优解，必在某顶点上得到 。虽然顶点数目是有限的(它不大于个)，若 采用“枚举法”找所有基可行解，然后一一 比较，最终可能找到最优解。 但当n,m的数较大时，这种办法是行不通的， 所以要继续讨论，如何有效地找到最优解， 有多种方法，这里仅介绍单纯形法单纯形法。
