2第二章 线性规划与单纯形法（第5节）.ppt

* 第五节 线性规划问题的几何意义 一、基本概念 凸集 设 K 是 n 维欧氏空间的一个点集，若存在任意两点 X(1)∈K，X(2)∈K 的连线上的一切点： 则称 K 为凸集。 注： X(1) X(2) X α 1 -α 实心圆、实心球体、实心立方体等都是凸集。 凸集没有凹入部分，其内部没有空间。 两个凸集的交集是凸集。 凸组合 设 X(1)，X(2)，…，X(k) 是 n 维欧氏空间 En 中的 k 个点，若存在 u1，u2，…，uk ，且 0≤ ui ≤1 ，i = 1, 2, … , k ； ，使 X = u1 X(1)+ u2 X(2)+…+ uk X(k) 则称 X 为 X(1)，X(2)，…，X(k) 的凸组合。 顶点 设 K 是凸集，X∈K；若 X 不能用不同的两点 X(1)∈K 和 X(2)∈K 的凸组合表示为： X=uX(1)+ (1-u) X(2)（0≤u≤1） 则称 X 为 K 的一个顶点（或极点）。 凸集 K 中满足下述条件的点 X 称为顶点：如果 K 中不存在任何两个不同点 X(1)、X(2)，使 X 成为这两个连线上的一个点。 二、基本定理 定理 1 若线性规划问题存在可行域，则可行域 是凸集 证明：可行域 K 内存在两个不同的点 X(1) 和 X(2) ： 则： 点 X(1) 和 X(2) 连线上的点 X 可表述为： 针对 X 中的每一份量，有： 下面来证明 X ∈ K ，也即证明： 证 毕。 引 理 线性规划问题的可行解 X = ( x1 , x2 , … , xn ) T 为基可行解的充要条件是 X 的正分量所对应的系数列向量线性无关。 可行解 X = ( x1 , x2 , … , xn ) T 为基可行解 可行解 X = ( x1 , x2 , … , xn ) T 的正分量所对应的系数列向量线性无关。 证：（1）必要性 可行解 X = ( x1 , x2 , … , xn ) T 为基可行解 X = ( x1 , x2 , … , xn ) T 中正分量的系数列向量线性无关。 （基解—— 令 (n-m) 个非基变量等于0，并对余下的 m 个基变量求解，所得的解称为基解。 基变量所对应的系数列向量是线性无关的。） 由基可行解定义可知，必要性成立。 （2）充分性 可行解 X = ( x1 , x2 , … , xn ) T 为基可行解 可行解 X = ( x1 , x2 , … , xn ) T 中正分量的系数列向量线性无关。 因为 X = ( x1 , x2 , … , xn ) T 为可行解， 所以 ( x1 , x2 , … , xn ) 中只有正分量和零分量。 ① 设可行解 X = ( x1 , x2 , … , xn ) T 中正分量数为 k , 则 X 可表述成： X = ( x1 , x2 , … , xk , 0 , … , 0 ) T （注：m 个约束条件和 n 个决策变量组成的线性规划问题的约束条件系数矩阵的秩为 m ，最大线性无关列向量数为m，多于 m 个列向量必然线性相关。） 因为 X = ( x1 , x2 , … , xk ,0 ,… , 0 ) T 中正分量所对应的系数列向量线性无关， 所以 k ≤ m 。 ② k = m ： ③ 由定义可知， X = ( x1 , x2 , … , xm , 0 , … , 0 ) T 为基可行解 。 X = ( x1 , x2 , … , xm ,0 , … ,0 ) T k m ： ④ X = ( x1 , x2 , … , xk , 0 , … , 0 , … , 0 ) T ( P1 , P2 , … , Pk , Pk+1 , … , Pm , … , Pn ) 必然可以从 ( Pk+1 , … , Pn ) 中找出 m – k 个向量与 ( P1 , P2 , … , Pk ) 构成最大线性无关组。 由定义可知， X = ( x1 , x2 , … , xk , 0 , … , 0 ) T 为基可行解 。 m – k 引理可以用来帮助我们判断，在线性规划问题中，什么样的可行解是基可行解。 由引理可知， X 如果为基可行解，则分量中只有正分量和 0 分量，且正分量数 ≤ m 。 例： max z = x1+x2 s.t. 2x1 + 6x2 + 2x3 + x4 = 10 3x1 + x2 + 2x3 + x4 = 8 x1, x2, x