1、Operations Research Prof. Wang School of Economics & Managementpage 1*第四讲第三讲 （上） 基础解及基础可行解 （ 1）一、基础解定义 令 X 满足， AX=b， 若 X 0， 则 X 必有非零分量 x， x ， ，于是必存的方程式：(1)其中 a， a， 为与 x， x ， 对应的 A阵列矢量，如果列矢量 a， a， 之间线性独立，则称 X为基础解。Operations Research Prof. Wang School of Economics & Managementpage 2*第四讲基础解及基础可行解 （ 2）线
2、性独立的定义（或判断准则）为：若方程中的矢量系数 ， ， 必须全为零才能使方程满足，则称矢量 a， a， 之间线性独立。即，任何一个矢量都不能由其它矢量的线性组合所构成的一组矢量必线性独立。例如： 中， ， ，则知 a1， a2， a3之间线性相关（即线性不独立），因为任何一个矢量都可由其它两个矢量所组成。但是这三个矢量中，两两之间线性无关（独立）。 Operations Research Prof. Wang School of Economics & Managementpage 3*第四讲基础解及基础可行解 （ 3）若存在多个不同的非零基础解，则它们之间组合系数之和为 1的线性组合也必是
3、方程解，即方程必存在无穷多个解。二、基础可行解定义 o 满足等式约束 AX=b及自变量限制 X 0的解称为可行解，既是可行解又是基础解解的解称为基础可行解。即基础解与可行解之交集称为基础可行解。o 基础可行解是可行域的顶点，它是可行解的一部分。基础可行解在线性规划的求解中具有特殊重要性，下面将阐述并证明关于它的重要定理。 Operations Research Prof. Wang School of Economics & Managementpage 4*第四讲基础解及基础可行解 （ 4）三、定理对于下述标准线性规划 1、如果存在可行解，则必存在基础可行解。2、如果存在最优解，则必存在基础
4、最优解。定理 1证明：设，规划已有一个可行解 X， 且具有正分量 x，x ， （ 如果无正分量， 则 X本身即 为 落在原点的基 础 可行解）， 如果正分量 x， x ， 对应的 A阵列矢量 a， a， 线性独立，则 X即为基础可行解，如果不独立，则在下述方程：Operations Research Prof. Wang School of Economics & Managementpage 5*第四讲基础解及基础可行解 （ 5）中 (3)至少有一项 i0， 不失一般性，令 0且 0（否则等式两边乘以 -1）。设 (4)其中， x， x ， 0则用 (4)式 (3)式得(5)Operatio
5、ns Research Prof. Wang School of Economics & Managementpage 6*第四讲基础解及基础可行解 （ 6）如果， 足 够 小， 则 仍可使（ 5）式左 边 系数 0， 0， 即仍可使新的 X为 可行解。选 取 于是新的正分量少了第 项，即 X正分量比原来至少少了一项。 然后再检验新的 X正分量所对应的 A阵矢量是否线性独立，若是，则该新解 X即为基础可行解。否则，按照上述方法又可使新解 X的正分量减少，直至找到基础可行解为止。定理 2证明（略）Operations Research Prof. Wang School of Economics
6、 & Managementpage 7*第四讲第三讲（下） 单纯形概念 1 基本假设：非退化阵 2 单纯形算法 Operations Research Prof. Wang School of Economics & Managementpage 8*第四讲1 基本假设：非退化阵 （ 1）在推导单纯形算法时，在理论上作出非退化假设。标准规划形式：其中， A为 m行 n列， mn则作 2个假设：1 A阵的秩为 m， 即 m行线性独立。2 b(m维向量 )是不少于 m列的线性组合，即在 中， X至少有 m个正分量。Operations Research Prof. Wang School of E
7、conomics & Managementpage 9*第四讲1 基本假设：非退化阵 （ 2）第 1个假设表明 ， AX=b总是有解，如果该假设 失败，则有下述两种情况： 不独立，或者 不合理 例如， ， 显然两行成正比例， A阵秩为 1。若有 AX=b， b=(b1,b2)T， 必有 2种情况：设 b2=2b1， 说明不独立。b22b1， 产 生矛盾，不合理。 Operations Research Prof. Wang School of Economics & Managementpage 10*第四讲1 基本假设：非退化阵 （ 3）对于这个假设失败 ,可作如下处理 :如行间不独立 ,可消去一行或几行 ,使之独立；如果不合理 ,则方程无解 ,不考虑。第 2个假设表明，可行解的正分量个数不 少于 m个 ，若失败，即为退化问题。例如方程(1)
