基础解及基础可行解

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Operations Research,Prof.Wang,School of Economics&Management,page,*,*,第四讲,第三讲（上）,基础解及基础可行解,（1）,一、基础解定义,令,X,满足，,AX,=,b,，,若,X,0，,则,X,必有非零分量,x,，,x,，,于是必存的方程式：,(1),其中,a,，,a,，,为与,x,，,x,，,对应的,A,阵列矢量，如果列矢,量,a,，,a,，,之间线性独立，则称,X,为基础解。,基础解及基础可行解,（2）,线性独立的定义（或判断准则）为：若方程,中的矢量系数,，,，必须全为零才能使方程满足，则称,矢量,a,，,a,，,之间线性独立。,即，任何一个矢量都不能由其它矢量的线性组合所构成的一,组矢量必线性独立。,例如：,中，,则知,a,1,，,a,2,，,a,3,之间线性相关（即线性不独立），因为任何一,个矢量都可由其它两个矢量所组成。但是这三个矢量中，两,两之间线性无关（独立）。,基础解及基础可行解,（3）,若存在多个不同的非零基础解，则它们之间组合系数之和为1,的线性组合也必是方程解，即方程必存在无穷多个解。,二、基础可行解定义,满足等式约束,AX,=,b,及自变量限制,X,0,的解称为可行解，既是可行解又是基础解解的解称为基础可行解。即基础解与可行解之交集称为基础可行解。,基础可行解是可行域的顶点，它是可行解的一部分。基础可行解在线性规划的求解中具有特殊重要性，下面将阐述并证明关于它的重要定理。,基础解及基础可行解,（4）,三、定理,对于下述标准线性规划,1、如果存在可行解，则必存在基础可行解。,2、如果存在最优解，则必存在基础最优解。,定理1证明：设，规划已有一个可行解,X，,且具有正分量,x,，,x,，（,如果无正分量，则,X,本身即为落在原点的基础可行,解），,如果正分量,x,，,x,，,对应的,A,阵列矢量,a,，,a,，,线,性独立，则,X,即为基础可行解，如果不独立，则在下述方程：,基础解及基础可行解,（5）,中 (3),至少有一项,i,0，,不失一般性，令,0且,0（否则等式两,边乘以-1）。设,(4),其中，,x,，,x,，0,则用(4)式,(3),式得,(5),基础解及基础可行解,（6）,如果，,足够小，则仍可使（5）式左边系数 ,0,，,0,，即仍可使新的,X,为可行解。,选取,于是新的正分量少了第,项，即,X,正分量比原来至少少了一项。,然后再检验新的,X,正分量所对应的,A,阵矢量是否线性独立，若,是，则该新解,X,即为基础可行解。否则，按照上述方法又可使,新解,X,的正分量减少，直至找到基础可行解为止。,定理2证明（略）,第三讲（下）,单纯形概念,1,基本假设：非退化阵,2,单纯形算法,1,基本假设：非退化阵,（1）,在推导单纯形算法时，在理论上作出非退化假设。,标准规划形式：,其中，,A,为,m,行,n,列，,m,0(,否则该方程乘以-1),为了求出这个原规划的第1个基础,可行解，可据此构造一个新规,划：,2,单纯形算法,（3）,则这个新规划的第1个基础可行解可立即得到：,x,j,=0 (,j,=1,n,),z,i,=,b,i,(,i,=1,m,)(4),新规划具有,m,个方程，,m,+,n,个未知量，其矩阵表达式为,2,单纯形算法,（4）,由于新规划的构成本身可提供第1个基础可行解，于是便可采用,第2阶段法去寻求新规划的最优解。其寻优结果有2种可能性：,min =0,则新规划最优解（,X,*,，,Z,*,）,的,X,*,必是原规划的1个,基础可行解。,min 0，,则说明原规划无可行解。,例1-5原规划为：,(6),则新规划为：,(7),新规划最优解为：,z,1,=3，,x,1,=0，,x,2,=0。,z,1,0。,故原规划无可行解。,2,单纯形算法,（5）,2进行第2阶段寻找最优解,1在叙述寻优步骤前，首先引入非退化定理（略）。,非退化定理,阶段2的进行步骤,令,X,是非退化阵,A,的标准线性基础可行解，则可由此导出最优,解,X*,。,设在规划：,AX,=,b,，,X,0，,C,T,X,=min,中，,B,是可行解中取正值分,量的角标,j,之集合。,即：,B,=,j,：,x,j,0,2,单纯形算法,（6）,显然，如果,A,阵具有,m,行且,B,含,m,项，则称,B,是基础解集，,B,=,m,。,因此，基础解,X,依赖于基础解集,B,中的,j,所对应的列,a,j,，,又称基础列，这,m,个基础列组成,m,n,矩阵，这是一个可逆阵。,例1-7 给出约束条件阵为：,若给定基础可行解,X,T,=1,0,1,则,x,1,0，,x,3,0,其基础解集,B,=1,3，,B,有2项，,B,=2。,则解,X,依赖于两列（1，3列）,组成的基础阵,2,单纯形算法,（7）,对于一般情况：，,可求解,m,个方程式。,定义矢量,Y,：,Y,T,a,j,=,c,j,(,j,B,),应用矩阵,M,，,可改写如下：,Y,T,M,=,其中，有,m,个分量,c,j,(,j,B,)，,唯一解为：,Y,T,=(12),此时，有2种可能性：,1)若式(12)所得解,Y,是该规划的对偶可行解，则,X,必是原问题的,最优解。从而,Y,亦是对偶问题最优解，即,X,满足：,2,单纯形算法,（8）,如何判断平衡解,Y,是对偶可行解呢？,这很容易，即判断下式是否成立：,其中，,j,B,时，等式已成立，只需判断其余(,n,m,),个非基础列,是否满足即可。若全满足，达最优，否则，未达最优，属下述,第2)种情况。,2,单纯形算法,（9）,2）若有一些非基础列,j,s,得出，,Y,T,a,s,c,s,这说明解,Y,不是对偶可,行解。因而需把目前的非基础列,a,s,引入基础列中，以便压缩,目标费用。,首先，把,a,s,表达为现有基础列的组合：,根据基础矩阵可写成：,2,单纯形算法,（10）,用,乘,(13),式并加到,若,是正数且很小，则所有(,m,+1,)个系数可全为正，于是得出,新的原问题可行解，新费用为：,2,单纯形算法,（11）,其旧费用减新费用之差为,（,z,s,c,s,）,其中，定义,要注意，,必须为正，因为它是,a,s,的系数。根据式(16)看出，,新费用减少的条件是：,z,s,c,s,0 (17),该条件即为：,y,T,a,s,c,s,。,证明：,(18),而,证毕,2,单纯形算法,（12）,由此看出，当平衡解,Y,T,不能使所有,j,满足 时，就,说明该解的费用仍可减少，故不是最优解，并且从前面推导,中看出，可以求得一个新解使其费用减少，其新费用减少值,为,（,z,s,c,s,）。,想使费用尽量小，则必须使,尽量大且保持解,可行，即使：,(19),对于(19)式之求解，可出现2种情况：,(,i),在(19)式中若所有,t,j,0,则,可取无限大值仍为可行解，,故目标函数可无穷小，即不存在最优解或无界。,2,单纯形算法,（13）,(,ii),至少有一个,t,j,0，,则可选取,为下面有限值：,(20),该,*,是此次获得最小目标,值的可行解。,设,*,是在,j,=,p,中达到，即,*,=,x,p,/,t,p,，,则在（15）式中,a,p,的系数变,为0，在非退化假设下，这是唯一一个变为0的系数，选定,*,后，式（15）即可变为：,(21),2,单纯形算法,（14）,非退化定理意味着，这个方程组定义了一个新的基础解：,B,=,s,+,B,p,(22),即，,B,中增加,s,，,且去掉,P,。,于是，（21）式可重写为：,(23),新系数是,m,个正数：,2,单纯形算法,（15）,非退化假设意味着，所有,m,个系数,x,j,为正，且,m,个列矢量,a,j,线,性无关（,j,B,），,因此，对于(,ii),状态，可计算出一个新的,基础可行解,X,，,且费用降低为,*,（,z,s,c,s,）。,然后以新解,X,作,为旧解，重复上述阶段2步骤，最后结果必在有限步内完成。,因为进行中只有下述几种可能：,出现情况1)，即有对偶解，则说明获得最优解，停止。,出现情况2)中的,(,i),，,不存在最优解，则停止。,出现情况2)中的,(,ii),，,可求出新解,X,以代替旧解,X,，,并,重复阶段2步骤。,2,单纯形算法,（16）,这个循环步骤是有限的，因为矩阵,A,的秩和,m,列子集数目有限,（即,AX,=,b,）,具有有限数目的基础解）。,设用上述方法获得一系列基础解为,X,1,，,X,2,，,则其费用必,递减为,C,T,X,1,C,T,X,2,，,由于,X,1,X,2,，,不同，故迭代次数有,限，由于非退化假设，死循环亦是不可能的.实际上，即使对,于退化问题，死循环也很少出现。,