1-2线性规划问题几何意义与解的性质定理-zff.ppt

1 二 线性规划的几何意义 2 2 1基本概念 凸集 设K是n维欧式空间的一个点集 若任意两点X 1 K X 2 K的连线上一切点aX 1 1 a X 2 K 0 a 1 则称K为凸集 3 顶点 设K是凸集 X K 若X不能用不同的两点x 1 K x 2 K的线性组合表示 即X ax 1 1 a x 2 0 a 1 则称X为K的一个顶点 极 角点 凸组合 设X 1 X 2 X k 是n维欧式空间的k个点 若存在k个数u1 u2 uk满足0 ui 1 则称X u1X 1 u2X 2 ukX k 为X 1 X 2 X k 的凸组合 4 2 四个重要定理 定理1线性规划问题的可行解集 可行域 是凸集 证明思路 根据凸集定义 采用直接法证明 具体步骤 从D中任取两个不同的点X 1 和X 2 二者应满足可行解定义中的等式条件 设X是点X 1 和X 2 连线上的任意一点 有X X 1 1 X 2 证明X D 5 证明 X 1 和X 2 满足可行解定义中的等式条件 则有 设X是点X 1 和X 2 连线上的任意一点 有X X 1 1 X 2 那么有 6 7 引理1若X是LP问题的可行解 则X是基本可行解的充分必要条件是X的正分量所对应的系数列向量线性独立 证明思路 X为LP的基本可行解X的正分量所对应的系数列向量线性无关 证 必要性 对于有着秩为m的m n阶系数矩阵的LP问题 由基本可行解定义可知 其基本可行解X的非零分量数目k m 且全部为正 当k m 这m个正分量所对应的系数列向量线性无关 并恰好构成一个基 当k m 这k个正分量所对应的系数列向量线性无关 且有其他 m k 个0分量所对应的系数列向量和这k个列向量构成一个基 8 充分性 对于有着秩为m的m n阶系数矩阵的LP问题 X为其可行解 则X中所有元素大于等于0 设其中的正分量数目为k 且其对应的系数列向量P1 P2 Pk线性独立 则必有k m 否则系数矩阵的秩必然要求大于m 当k m 这k个列向量恰好构成一个基 从而可行解X为其相应的基解 则X是一个基可行解 当k m 除了P1 P2 Pk线性独立外 必然可以在其他n k个列向量中找出m k个列向量 与P1 P2 Pk构成最大的线性独立向量组 否则系数矩阵的秩必然要求小于m 其对应的解为X 所有X是一个基可行解 9 定理2 线性规划几何理论基本定理 X是LP问题的可行解 可行域中的一点 如果它是基可行解 则它必然对应于可行域D的顶点 证明思路 X为LP的基本可行解X是D的一个顶点可以利用引理1 X为LP的基本可行解X的正分量所对应的系数列向量线性无关 进行证明 10 证明思路 X不是基可行解 X不是D的顶点 11 必要性 X不是基可行解 X不是D的顶点 证明 1 X是可行解 则其所有元素大于等于0 假定其前m个分量为正 则有式 1 成立 1 2 此外 由引理1可知 如果X不是基可行解 则其正分量所对应的系数列向量P1 P2 Pm线性相关 即存在一组不全为0的数ai i 1 2 m 使得式 2 成立 2 12 必要性 X不是基可行解 X不是D的顶点 3 用一个u 0的数乘以式 2 然后与式 1 相加减 得 现取 则X 1 X 2 是该LP问题的可行解 对应可行域上的两点 13 必要性 X不是基可行解 X不是D的顶点 4 由X X 1 X 2 的分量表达可知 即X是X 1 和X 2 连线的中点 一定不是D的顶点 必要性证毕 14 充分性 X不是D的顶点 X不是基可行解 证明 1 X在可行域中 但不是顶点 则在可行域D中可找到不同的两点使X aX 1 1 a X 2 0 a 1 成立 2 假定X是基可行解 反证思路 对应基向量组P1 P2 Pm线性独立 当j m时 有 15 充分性 X不是D的顶点 X不是基可行解 3 因为X 1 和X 2 是可行解 又有下两式成立 将两式相减 可得成立 因为X 1 和X 2 是两个不同可行解 上式中系数不全为0 所以向量组P1 P2 Pm线性相关 否定 2 的假设 即X不应该是基可行解 充分性证毕 16 引理2若K是有界凸集 则此凸集上的任何一点X可表示为K的顶点的凸组合 证明思路 根据凸组合的定义证明 17 定理3若可行域有界 则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值 证明思路 1 首先 可行域有界就能够找到最优解 2 如果在非顶点X处取得最优值 则存在顶点X m 也取得相同的最优值 18 证明 设X 1 X 2 X k 是可行域D的顶点 若X 0 是可行域中的一点 但不是顶点 而LP的目标函数在X 0 处达到最优值Z CX 0 首先 X 0 是可行域中的一点 则可用D的顶点表示 因此有 那么 在所以顶点中必然可以找到一个X m 使CX m 是所有CX i 中最大者 从而有下式成立 19 即 根据假设LP的目标函数在X 0 处达到最优值Z CX 0 只能有CX 0 CX m Z 即目标函数在顶点X m 处也达到最大 20 上述定理的一些有意义的启示 LP的可行域一定是凸集 但是凸集不一定成为LP的可行域 而非凸集一定不会是LP的可行域 为什么 能举例说明吗 线性规划的基本可行解和可行域的顶点是一一对应的 类似