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