第一章---线性规划--第三节

1、1,第一章 线性规划及单纯形法,Linear Programming,第三节 线性规划的几何思路,一、LP问题的解的概念,三、几个基本定理,17,二、凸集及其顶点,定义1：满足约束(2)、(3)的X=(X1 Xn)T称为 LP问题的可行解，全部可行解的集合称 为可行域。,定义2：满足(1)的可行解称为LP问题的最优解,线性规划问题的解的概念,18,可行解与最优解：,19,定义3：基(基矩阵) A (秩为m）中一个子矩 阵B是可逆矩阵(满秩子矩阵)，则方阵B称 为LP问题的一个基。,线性规划问题的解的概念,基、基向量、基变量：,Pj(j=1,2.m)为基向量,xj(j=1,2.m)为基变量,20

2、,定义4：在约束方程中，令所有非基变量xm+1, xm+2,，xn为0，对应于基B ，有 X=(x1,x2,xm,0, ,0)T, 称X为LP问 题的基解,线性规划问题的解的概念,基解：,21,定义5：满足非负约束条件的基解X= 称为基可行解。对应于基可行解的基称为可行基。,基可行解、可行基：,线性规划问题的解的概念,说明：,线性规划问题的解的概念,约束方程组具有基解的数目最多是 个。 一般基可行解的数目要小于基解的数目。,几种解的概念之间的关系,线性规划问题的解的概念,第三节 线性规划的几何思路,一、LP问题的解的概念,三、几个基本定理,17,二、凸集及其顶点,凸集及其顶点,凸集,集合K中，

3、若任意两点X(1)K，X(2)K的连线上的所有点 X(1)+(1-)X(2)K，(01)； 则称K为凸集。,凸集及其顶点,凸集,实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。左图中的(a)(b)是凸集，(c)不是凸集。 右图中的阴影部分是凸集。 任何两个凸集的交集是凸集，见左图(d),凸集及其顶点,顶点,设K是凸集，XK；若X不能用不同的两点X(1)K 和X(2)K的线性组合表示为 X=X(1)+(1-)X(2)，(01) 则称X为K的一个顶点(或极点)。 图中0，Q1,2,3,4都是顶点。,第三节 线性规划的几何思路,一、LP问题的解的概

4、念,三、几个基本定理,17,二、凸集及其顶点,几个基本定理,定理1 若线性规划问题存在可行解，则问题的可,是凸集,行域,证：为了证明满足线性规划问题的约束条件,的所有点(可行解)组成的集合是凸集，只要证明 D中任意两点连线上的点必然在D内即可。 设 是D内的任意两点；X(1)X(2)。,几个基本定理,几个基本定理,几个基本定理,引理 1 线性规划问题的可行解X=(x1,x2,，xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。,几个基本定理,几个基本定理,定理2 线性规划问题的基可行解X对应于可行 域D的顶点。,证：不失一般性，假设基可行解X的前m个分量为正。故,现在分两

5、步来讨论，分别用反证法。,（1）,几个基本定理,若X不是基可行解，则它一定不是可行域D的顶点,根据引理1，若X不是基可行解，则其正分量所对应的系数列向量P1，P2，Pm线性相关，即存在一组不全为零的数i,i=1,2,m使得 1P1+2P2+mPm=0 (2) 用一个0的数乘(2)式再分别与(1)式相加和相减。,定理2的证明（续）,几个基本定理,这样得到(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)

6、, 0,，0由X(1),X(2)可以得到X=（1/2）X(1)+（1/2）X(2)， 即X是X(1)，X(2)连线的中点,定理2的证明（续）,几个基本定理,另一方面，当充分小时，可保证,xii0，i=1,2,m 即X(1)，X(2)是可行解，又因X=（1/2）X(1)+（1/2）X(2) 。 这证明了X 不是可行域 D 的顶点。,定理2的证明（续）,几个基本定理,(2) 若X不是可行域D的顶点，则它一定不是基可行解,因为X不是可行域 D 的顶点，故在可行域D中可找到不同的两点 X(1)=(x1(1),x2(1),xn(1)T X(2)=(x1(2),x2(2),xn(2)T 使 X=X(1)+

7、(1-) X(2) ， 01 设X是基可行解，对应向量组P1Pm线性独立。当jm时，有xj=xj(1)=xj(2)=0，由于X(1)，X(2)是可行域的两点。应满足,定理2的证明（续）,几个基本定理,将这两式相减，即得,因X(1)X(2)，所以上式系数不全为零，故向量组P1,P2,，Pm线性相关，与假设矛盾。即X不是基可行解。,定理2的证明（续）,几个基本定理,定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解。,（补充）定理4：可行域有界，目标函数最优 值必可在顶点得到（证明可参考运筹学教材编写组编）,1.线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点； 2.若线性规划问题有最优解，必在某顶点上得到。虽然顶点数