第1章+线性规划与单纯形法-第2节-清华大学运筹学第三版课件

运筹学（ 第三版）运筹学教材编写组 编清华大学出版社第 1章 线性规划与单纯形法 第 2节 线性规划问题的几何意义钱颂迪 制作第 1章 线性规划与单纯形法 第 2节线性规划问题的几何意义 2.1 基本概念 2.2 几个定理2.1 基本概念 凸集 凸 组 合 顶 点1.凸集 设 K是 n维欧氏空间的一点集，若任意两点 X(1) K， X(2) K的连线上的所有点 X(1)+(1-)X(2) K，(01)； 则称 K为凸集。 图 1-7 实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。图 1-7中的 (a)(b)是凸集， (c)不是凸集。 图 1-2中的阴影部分是凸集。 任何两个凸集的交集是凸集，见图 1-7(d) 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)的凸组合。（当 0 i 1时，称为严格凸组合） .3. 顶点 设 K是凸集， X K； 若 X不能用不同的两点X(1) K和 X(2) K的线性组合表示为 X=X(1)+(1-)X(2)， (0 1) 则称 X为 K的一个顶点 (或极点 )。 图中 0， Q1,2,3,4都是顶点。2.2 几个定理 定理 1 若线性规划问题存在可行域，则其可行域 是凸集 证：为了证明满足线性规划问题的约束条件的所有点 (可行解 )组成的集合是凸集，只要证明 D中任意两点连线上的点必然在 D内即可。设是 D内的任意两点； X(1)X (2)。引理 1 线性规划问题的可行解 X=(x1,x2, ，xn)T为基可行解的充要条件是 X的正分量所对应的系数列向量是线性独立的。 定理 2 线性规划问题的基可行解 X对应于可行D的顶点。证： 不失一般性，假设基可行解 X的前 m个分量为正。故现在分两步来讨论，分别用反证法。（ 1-8）(1)若 X不是基可行解，则它一定不是可行域 D的顶点 根据引理 1，若 X不是基可行解，则其正分量所对应的系数列向量 P1， P2， ， Pm线性相关，即存在一组不全为零的数 i,i=1,2,m 使得 1P1+ 2P2+ mPm=0 (1-9) 用一个 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现取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)连线的中点另一方面，当 充分小时，可保证 xi i0 ， i=1,2,m 即 X(1)， X(2)是可行解。 这证明了 X 不是可行域 D 的顶点。 (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)+(1-) X(2) ， 0 1 设 X是基可行解，对应向量组 P1P m线性独立。当 j m时，有 xj=xj(1)=xj(2)=0，由于 X(1)， X(2)是可行域的两点。应满足将这两式相减，即得 因 X(1)X (2)， 所以上式系数不全为零，故向量组 P1,P2, ， Pm线性相关，与假设矛盾。即 X不是基可行解。引理 2 若 K是有界凸集，则任何一点X K可表示为 K的顶点的凸组合。 本引理证明从略，用以下例子说明这引理。 例 5 设 X是三角形中任意一点， X(1),X(2)和X(3)是三角形的三个顶点，试用三个顶点的坐标表示 X(见图 1-8) 解 任选一顶点 X(2)， 做一条连线 XX(2)； 并延长交于 X(1)、 X(3)连接线上一点 X 。 因 X 是 X(1)、 X(3)连线上一点，故可用 X(1)、 X(3)线性组合表示为 X=X (1)+(1-)X (3) 0 1 又因 X是 X 与 X(2)连线上的一个点，故 X=X+(1-)X (2) 0 1 将 X 的表达式代入上式得到 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) i i=1,0 i 1定理 3 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。证 设 X(1),X(2)， ， X(k)是可行域的顶点，若 X(0)不是顶点，且目标函数在 X(0)处达到最优 z*=CX(0)(标准型是 z=max z)。因 X(0)不是顶点，所以它可以用 D的顶点线性表示为定理 3的证明：证： 设 X(1),X(2)， ， X(k)是可行域的顶点，若 X(0)不是顶点，且目标函数在 X(0)处达到最优 z*=CX(0)(标准型是 z=max z)。 代入目标函数得在所有的顶点中必然能找到某一个顶点 X(m)， 使 CX(m)是所有 CX(i)中最大者。并且将 X(m)代替 (1-10)式中的所有 X(i)，这就得到（ 1- 10） 由此得到 X(0)CX (m) 根据假设 CX(0)是最大值，所以只能有 CX(0)=CX(m) 即目标函数在顶点 X(m)处也达到最大值。有时目标函数可能在多个顶点处达到最大 ;这时在这些顶点的凸组合上也达到最大值。称这种线性规划问题有无限多个最优解。假设是目标函数达到最大值的顶点，若是这些顶点的凸组合，即于是设：于是：另外，若可行域为无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上得到。根据以上讨论，可以得到以下结论：线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点；若线性规划问题