线性规划的基本概念与基本定理VIP免费

253第十二章线性规划的基本概念和基本定理12.1线性规划的基本概念12.1.1可行解，可行域定义12.1.1：称满足全部约束条件的向量为可行解或可行点.例如：SLPmax..0fCZAZbstZ如果0Z满足这些约束，即0AZb且00Z，则0Z就是SLP的可行解.定义12.1.2：称所有可行解（点）构成的集合为可行集或可行域.也称为可行解集.例如：上面SLP的可行域为{,0}RAZbZ定义12.1.3：若一个线性规划问题的可行集为空集时，则称这一线性规划无可行解.这时线性规划的约束条件不相容.矚慫润厲钐瘗睞枥庑赖。由上一章的分析可以看到：一个线性规划的可行解集可以是空集，有界非空集和无界非空集.12.1.2最优解，无界解定义12.1.4：称使目标函数值达到最优值的可行解为线性规划问题的最优解定义12.1.5：对于极大化目标函数的标准线性规划问题，定义其无界解如下：对于任何给定的正数M，存在可行解X满足,0AXbX，使CXM.那么称该线性规划问题有无界解.聞創沟燴鐺險爱氇谴净。由定义可知，无界解的意思是：若是极大化目标函数，则在可行域上目标函数值无上界；若是极小化目标函数，则在可行域上目标函数值无下界.那么，有无界解的线性规划问题一定没有最优解.残骛楼諍锩瀨濟溆塹籟。例12.1.1考虑线性规划问题：12max()xx121212110,0xxstxxxx图12.1.1解：问题的可行域是上图所示的无界凸多边形区域，在此无界可行域上，目标函数值无上界，所以这个线性规划问题有无界解.酽锕极額閉镇桧猪訣锥。121xx2x1x11,22121xxl121xx12xxl0254例12.1.212maxfxx121212110,0xxstxxxx解：此问题的可行域如上图，是一个无界的多边形.但极大化目标函数却以1为上界.因此这个线性规划问题没有无界解，而且事实上，此问题目标函数最优值maxf=1在可行域射线121xx上均可达到.彈贸摄尔霁毙攬砖卤庑。12.1.3.基本可行解定义12.1.6：对于约束条件Ax=b，设A是秩m的mｘn矩阵，用(jP,j=1~n)表示A的第j列向量.即A=(1....npp).由A的m个列向量构成的m阶方阵B=(12,...mjjjppp)謀荞抟箧飆鐸怼类蒋薔。若B是非奇异的，即detB0，则称B为一个基或称为一个基矩阵.因为SLP问题中含有约束条件Ax=b，因此也通常称B为线性规划SLP的一个基.由上面定义可知，B中m个列向量是线性无关的，并且它是A的列向量组的一个最大无关组.按定义，A中m个列向量，只要是线性无关的就可以构成一个基.定义12.1.7：若变量jx对应A中列向量jp包含在基B中，则称jx为B的基变量；若变量kx对应A中的列向量kp不包含在基B中，则称kx为B中的非基变量.厦礴恳蹒骈時盡继價骚。例12.1.3求15~xx满足1231241255262210,1~5ixxxxxxxxxxi使122fxx解：111001101062001A则100010001B的列是线性无关的，即5001p是线性无关，因此345xxx是一组基.而12111,102pp，不在这个基中，所以12,xx为非基变量.定义12.1.8：设Ax=b,x≥0一个基1...mjjBpp，其对应的基变量构255成的m维列向量记为1(...)mTBjjxxx这时若全非基变量等0，则Ax=bBBxb,得唯一解1BxBb.记为11(...)TmBbbb于是得到方程组Ax=b的一个解1212,...mjjjmxbxbxb，非基变量1,0,(1,2....,)jmxjnijj称之为对应于基B的基本解.这个定义也告诉我们怎样找一个基本解）茕桢广鳓鯡选块网羈泪。如：上面例12.1.2中，非基变量120xx.则可得3455,4,21xxx.所以0(0,0,5,2,21)x是对应于基B的一个基本解，但由于4x=-2<0.不能满足约束条件，所以这个基本解不是原问题的可行解.（为什么？）鹅娅尽損鹌惨歷茏鴛賴。这是因为，按照定义，基本解中的n-m个非基变量必须取0值只有m个基变量取值才可能不等于0.但可以取负值.因此基本解不一定满足SLP的非负要求.籟丛妈羥为贍偾蛏练淨。定义12.1.9：对应于基B的基本解，若基变量取非负值，即1BxBb，b>0，则称它为满足约束Ax=b,x>o的基本可行解.預頌圣鉉儐歲龈讶骅籴。对应地称B为可行基，因SLP中具有此约束条件.也通常称为SLP的基本可行解.定义12.1.10：使目标函数达到最优值的基本可行解，称为基本最优值.例12.1.4：（SLP)如例12.1.3，试找一个基本可行解.解：110100601B是其一个基矩阵.135,,ppp是一个基.则135,,xxx为基变量.24,xx为非基变量.令240xx.得1352,3,9xxx.故1(2,0,3,0,9)x是原问题的一个基本可行解，1B为基可行基.渗釤呛俨匀谔鱉...