第十二章线性规划的基本概念与基本定理

《第十二章线性规划的基本概念与基本定理》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第十二章线性规划的基本概念和基本定理12.1线性规划的基本概念1211可行解，可行域定义12.1.1：称满足全部约束条件的向量为可行解或可行点。maxf=CZ例如：SLP[AZ=hs.t.0如果Z°满足这些约束，即且z°no,则Z°就是SLP的可行解。定义12.1.2：称所有可行解（点）构成的集合为可行集或可行域。也称为可行解集。例如：上而SLP的可行域为R={AZ=h,Z>0}定义12.1.3：若一个线性规划问题的可行集为空集时，则称这一线性规划无可行解。这吋线性规划的约束条件不相容。由上一章的分析可以看到：一个线性规划的可行解集可以是空集，冇界非空集和

2、无界非空集。12L2最优解，无界解定义12.1.4：称使口标函数值达到最优值的可行解为线性规划问题的最优解定义12.1.5：对于极大化目标函数的标准线性规划问题，定义其无界解如下：对于任何给定的正数M,存在可行解X满足AX=b,XnO,使CX>M0那么称该线性规划问题有无界解。曲定义可知，无界解的意思是：若是极大化目标函数，则在可行域上目标函数值无上界；若是极小化目标函数，则在可行域上目标函数值无下界。那么，有无界解的线性规划问题一定没冇最优解。x~例12.1.1考虑线性规划问题:max（兀]+◎x{-x20,x2>0图12.1.1

3、解：问题的可行域是上图所示的无界凸多边形区域，在此无界可行域上，目标函数值无上界，所以这个线性规划问题有无界解。Xj-x2<1例12.1.2maxf=xA-x2St<-X)+x2<1>0,x2>0解：此问题的口J行域如上图，是一个无界的多边形。但极大化目标函数却以1为上界。因此这个线性规划问题没有无界解，而且事实上，此问题冃标函数最优值maxf=1在可行域射线-x2=1上均可达到o121a基本可行解定义12.1.6：对于约束条件Ax=b,设A是秩m的mxn矩阵，用（巧,/=1〜n）表示A的第j列向量。即A=（由A的m个列向量构成的m阶方阵B=(若B是非奇异的，即

4、detB^O,则称〃为一个基或称为一个基矩阵。因为SLP问题中含有约束条件Ax=b,因此也通常称B为线性规划SLP的个基U由上面定义可知，B中m个列向量是线性无关的，并且它是A的列向量组的一个最大无关组。按定义，A屮m个列向量，只要是线性无关的就可以构成一个基。定义12.1.7：若变量对应A中列向量厂包含在基〃中，则称兮为〃的基变豊若变量兀对应A中的列向量仇不包含在基〃中，则称忑为B中的非基变量。使于=2西+兀2例12.1.3兀1+兀2+兀3=505=0是线性无关，因此｛可兀41/<1、禺｝是一组基。而"

5、=-13丿,Pi=1不在厂11100、‘100、A=-1

6、1010则B=010的列是线性无关的，即2001丿、001丿+X。+£=_26兀1+2x2+x5=21兀noj=1~5解:这个基屮，所以®勺为非基变量。定义12.1.8:设Ax=b,xMO—个基3=（你…匕），其对应的基变量构成的m维列向量记为xB=(七...Xj」T这时若全非基变量等0,则Ax=b=>Bxb-b,得唯一解x严矿％•记为B"=(b…叽于是得到方程组Ax=b的一个解=匸七=b2...xjm=bm,非基变量®=0,O=l,2・・』,心人人)称Z为对应于基B的基木解。这个定义也告诉我们怎样找一个基木解)如：上面例12.1.2中，非基变量%!=x2=0

7、o则可得兀3=5,x4=4,兀§=21。所以兀。=(0,0,5,-2,21)是对应于基B的一个基本解，但由于x4=-2<0.不能满足约朿条件，所以这个基木解不是原问题的可行解。(为什么？)这是因为，按照定义，基本解中的mm个非基变量必须取0值只有m个基变量取值才可能不等于0。但可以取负值。因此基木解不一定满足SLP的非负要求。定义12.1.9：对应于基B的基木解，若基变量取非负值，即Xb=B'b,b>0,则称它为满足约束Ax=b,x>o的基本可行解。对应地称B为可行基，因SLP中具有此约束条件。也通常称为SLP的基本可行解。定义12.1.10：使目标函数达到最优

8、值的基本可行解，称为基本最优值。例12.14(SLP)如例12.1.3,试找一个基本可行解。(110]解：B二-100是其一个基矩阵•门,卩3，卩5是一个基。则xl,x3,x5为基变〔601丿量。兀2，兀为非基变量。令x2=x4=0.得兀]=2,x3=3,x5=9.故西=(2,0,3,0,9)是原问题的一个基本可行解，色为基可行基。上面我们讲到基本解中有n-m个分量必须取零值，而只有m个基变量取非零值。而基木可行解，它一方面是基木解，另一方面又是可行解，因为它是基木解，所以mm个非基变量取0值；它是可行解，则m个基变量取非负值，从而基木可行解止分量是个数不超过m

9、.那么满足Ax=b,x^