线性规划问题解的概念和性质

.,第五节线性规划问题解的概念和性质,线性规划问题的解,线性规划问题,求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。,.,第五节线性规划问题解的概念和性质,可行解：满足约束条件、的解X0=(x1，x2，xn)T为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。基：设A为约束条件的mn阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子矩阵（非奇异子矩阵）（B0），称B是线性规划问题的一个基。设：,称B中每个列向量Pj(j=12m)为基向量。与基向量Pj对应的变量xj(j=12m)为基变量。除基变量以外的变量为非基变量。,.,第五节线性规划问题解的概念和性质,范例,A=,x1x2x3x4x5,a1a2a3a4a5,可取B0=（a3,a4,a5）为基（|B0|0）,这时称a3,a4,a5为基向量，而a1,a2为非基向量；称x3,x4,x5为基变量，而x1,x2为非基变量。,.,第五节线性规划问题解的概念和性质,基解（基本解）：某一确定的基B，令非基变量等于零，由约束条件方程解出基变量，称这组解为基解（基本解）。可见，有一个基就可以求出一个基本解。在基解中变量取非0值的个数不大于方程数m，基解的总数不超过基可行解：满足变量非负约束条件的基本解，简称基可行解。可行基：对应于基可行解的基称为可行基。,.,第五节线性规划问题解的概念和性质,基本解范例的标准形,maxz=3x1+5x2,s.t.,x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x50,取B0=（a3,a4,a5）为基，令一切非基变量x1=x2=0,可解得基变量x3=8，x4=12，x5=36则得一特解X0=(0，0，8，12，36)T,称为一个(关于B0为基的)基本解。,.,第五节线性规划问题解的概念和性质,也可取B1=(a2,a3,a4)为基,得X1=(0，9，8，-6，0)T还可取B2=(a1,a2,a3)为基,得X2=(4，6，4，0，0)T等等。基本可行解满足非负性约束的基本解。如X0，X2；而X1不可行。对基本(可行)解而言：在其分量中，若有一个或更多个基变量取值为0，则称其为一个退化的基本(可行)解，否则为非退化的。如设：X=(0，6，5，0，0)T是一个基本可行解，其中x5=0为基变量，则该X为退化的基本可行解。,.,第五节线性规划问题解的概念和性质,非退化的基本(可行)解，并恰有nm个0分量。,基本可行解对应的基，称为可行基；最优基本解对应的基，称为最优基。如：基B0=(a2,a3,a4)对应X0=(0，0，8，12，36)T可行基B1=(a2,a3,a4)对应X1=(0，9，8，-6，0)T不可行基B2=(a1,a2,a3)对应X2=(4，6，4，0，0)T,恰有m个非0分量，,为可行基,为非可行基,为最优基,x*,x*,B*,.,第五节线性规划问题解的概念和性质,例：求线性规划问题的所有基矩阵。,解:约束方程的系数矩阵为25矩阵,r(A)=2，2阶子矩阵有10个，其中基矩阵（不等于0）只有9个，即,.,第五节线性规划问题解的概念和性质,凸性的几个基本概念一、凸集设SEn，对任意两点XS，YS，若对满足01的一切实数，都有X+(1-)YS则称S为凸集。,凸集,凸集,非凸集,非,表示S中两点X，Y连线上的任一点,凸集的几何意义：凸集S中任意两点X，Y连线上的点，都在凸集S中。,.,第五节线性规划问题解的概念和性质,二、极点设凸集SEn,XS，如果X不能用S中不同的两点Y和Z表示为X=Y+(1-)Z(01)则称X为S的一个极点。三、凸组合设XiEn,实数i0,i=1,2,s,且i=1，则称X=1X1+2X2+sXs为点X1，X2，Xs的一个凸组合。,.,第五节线性规划问题解的概念和性质,线性规划的解的性质性质1：LP问题标准型的可行域R=XAX=b,X0是凸集。性质2：LP问题标准型的一个基本可行解与可行域R的一个极点互相对应。性质3：线性规划的基本定理对于一个给定的标准型LP问题标准型来说：若标准型有可行解，则必有基本可行解；若标准型有最优解，则必有最优基本解。性质4：若LP问题的可行域R,则R至少有一极点。性质5：LP问题可行域R的极点数目必为有限个。,.,第五节线性规划问题解的概念和性质,仅就标准形LP问题说明其合理性。因标准型是一个m阶n维的LP问题，则从其系数阵的n列中取出m列，所构成其基的个数不超过,基本可行解