基础解及基础可行解.pptVIP

OperationsResearchProf.WangSchoolofEconomicsManagementpage**第四讲OperationsResearchProf.WangSchoolofEconomicsManagementpage**第四讲第三讲（上）

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