§1-2 线性规划问题的几何意义.ppt

Operational Research * 第2节 线性规划问题 的几何意义 2.1 基本概念 2.2 几个定理 第1章 线性规划与单纯形法 * 1．凸集 设K是n维欧氏空间的一点集，若任意两点X(1)?K，X(2)?K的连线上的所有点? X(1)+(1-?)X(2) ? K(0 ≤ ? ≤1)；则称K为凸集。 2.1 基本概念 实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。 X=? X(1)+(1-?)X(2) 就是以X(1), X(2)为端点的线段方程，点X的位置由?的值确定，当? =0时，X=X(2)，当? =1时，X=X(1)。 * 任何两个凸集的交集是凸集。 凸集（续） 图1-2中的阴影部分是凸集。 * 2．凸组合 凸组合 设X(1), X(2), …, X(k)是n 维欧氏空间E中的k个点。若存在? 1, ? 2, …, μk，且0≤? i≤1，i =1, 2, …, k ； ，使X=? 1X(1) +? 2X(2) + … +? k X(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, Q2, Q3, Q4都是顶点。 X是凸集K的极点，即X不可能是K中某一线段的内点，只能是K中某一线段的端点。 O * 2.2 几个定理 定理1 若线性规划问题存在可行域，则其可行域 是凸集。 证 为了证明满足线性规划问题的约束条件 的所有点（可行解）组成的集合是凸集，只要证明D中任意两点连线上的点必然在D内即可。 * 定理1（续） 定理1（续） 设 是D内的任意两点，X(1)≠X(2)。 则有 * 令X=(x1, x2, …, xn)T为X (1), X(2)连线上的任意一点，即 X=?X(1)+(1-?)X(2) (0≤?≤1) 将它代入约束条件，得到 定理1（续） X的每一个分量是 * 又因为 ，所以 ， 。由此可见，X?D，D是凸集。 定理1（续） * 引理 1 线性规划问题的可行解X=(x1, x2, …, xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。 引理1 证 必要性：由基可行解的定义可知。 充分性：若向量P1, P2, …, Pk线性独立，则必有k≤m； 当k=m时，它们恰构成一个基，从而X=(x1, x2, …, xk, 0, …, 0)为相应的基可行解。 当k＜m时，则一定可以从其余的列向量中取出m-k个与P1, P2, …, Pk构成最大的线性独立向量组，其对应的解恰为X，所以根据定义它是基可行解。 * 定理2 线性规划问题的基可行解X对应于可行域D的顶点。 证 不失一般性，假设基可行解X的前m个分量为正。故 现在分两步来讨论，分别用反证法。 定理2 (1) 若X不是基可行解，则它一定不是可行域D的顶点； (2) 若X不是可行域D的顶点，则它一定不是基可行解。 * (1) 若X不是基可行解，则它一定不是可行域D的顶点。 根据引理1，若X不是基可行解，则其正分量所对应的系数列向量P1, P2, …, Pm线性相关，即存在一组不全为零的数? i，i=1, 2, …, m使得 定理2（续） 用一个?＞0的数乘(2)式再分别与(1)式相加和相减。 * 定理2（续） 相加减后得到 现取 由X(1), X(2)可以得到 ，即X是X(1)，X(2)连线的中点。 * 此外，当? 充分小时，可保证 即X(1), X(2)是可行解，即证明了X不是可行域 D 的顶点。 定理2（续） * 使 定理2（续） (2) 若X不是可行域D的顶点，则它一定不是基可行解。 因为X不是可行域D的顶点，故在可行域D中可找到不同的两点 * 定理2（续） 假设X是基可行解，对应向量组P1, P2,