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

一可行解，可行域定义一：称满足全部约束条件的向量为可行解或可行点或容许点。0..maxZbAZtsCZf0000.0ZZbAZZ则且满足这些约束，即如果•例如：SLP就是SLP的可行解。第二章线性规划的基本概念和基本定理•§2.1线性规划的基本概念定义2：称所有可行解（点）构成的集合为可行集或可行域。也称为可行解集。例如：上面SLP的可行域为R={Z|AZ=b,Z≥0}定义3：若一个线性规划问题的可行集为空集时，则称这一线性规划无可行解。这时线性规划的约束条件不相容。由上一章的分析可以看到：一个线性规划的可行解集可以是空集，有界非空集和无界非空集。二最优解，无界解定义4：称使目标函数值达到最优值的可行解为线性规划问题的最优解。解：问题的可行域是上图所示的无界凸多边形区域，在此无界可行域上，目标函数值无上界，所以这个线性规划问题有无界解。定义5：对于极大化目标函数的标准线性规划问题，定义其无界解如下：对于任何给定的正数M，存在可行解X满足AX=b，X≥0，使cXM。那么称该线性规划问题有无界解。由定义可知，无界解的意思是：若是极大化目标函数，则在可行域上目标函数值无上界；若是极小化目标函数，则在可行域上目标函数值无下界。那么，有无界解的线性规划问题一定没有最优解。121xx2x1x21,21121lxx121xxlxx21021xxmax0,011212121xxxxxxs.t例1.考虑线性规划问题：例2.maxf=s.t21xx0,011212121xxxxxx•解：此问题的可行域如上图，是一个无界的多边形。但极大化目标函数却以1为上界。因此这个线性规划问题没有无界解，而且事实上，此问题目标函数最优值maxf=1在可行域射线上均可达到。121xx三.基、基本可行解定义6：对于约束条件Ax=b，设A是秩m的mｘn矩阵，用(Pj,j=1~n)表示A的第j列向量。即A=()。由A的m个列向量构成的m阶方阵B=()npp....1mjjjppp...,21•若B是非奇异的，即detB‡0，则称B为一个基或称为一个基矩阵。•因为SLP问题中含有约束条件Ax=b，因此也通常称B为线性规划SLP的一个基。100260101100111•解：A=212xx使minf=5~1,0212625521421321ixxxxxxxxxxi满足例3.求x1----x5•由上面定义可知，B中m个列向量是线性无关的，并且它是A的列向量组的一个最大无关组。•按定义，A中m个列向量，只要是线性无关的就可以构成一个基。•定义7：若变量对应A中列向量包含在基B中，则称为•B的基变量；若变量对应A中的列向量不包含在基B中，•则称为B中的非基变量。jxjxjpkxkpkx•定义8：设Ax=b,x0一个基，其对应的基变量构成的m维列向量记为这时若全非基mjjppB...1TjjBmxxx)...(11005p•是线性无关，因此是一组基。而•不在这个基中，所以x1,x2为非基变量。543xxx211,01121pp010,00143pp的列是线性无关的，即100010001B则于是得到方程组Ax=b的一个解：非基变量称之为对应于基B的基本解。这个定义也告诉我们怎样找一个基本解）•变量等于0，则Ax=bBxB=b,得唯一解xB=B-1b.记为TmbbbB)...(11mjjjbxbxbxm...,2121),....2,1(,0,1mjjjinjx•如：上面例2中，非基变量x1=x2=0.则可得x3=5,x4=-2,x5=21.所以x0=(0,0,5,-2,21)是对应于基B的一个基本解，但由于x4=-20.不能满足约束条件，所以这个基本解不是原问题的可行解。（为什么？）•这是因为，按照定义，基本解中的n-m个非基变量必须取0值只有m个基变量取值才可能不等于0。但可以取负值。因此基本解不一定满足SLP的非负要求。•定义9：对应于基B的基本解，若基变量取非负值，即xB=B-1b=0，则称它为满足约束Ax=b,x=o的基本可行解。•对应地称B为可行基，因SLP中具有此约束条件。也通常称为SLP的基本可行解。上面我们讲到基本解中有n-m个分量必须取零值，而只有m个基变量取非零值。而基本可行解，它一方面是基本解，另一方面又是可行解，因为它是基本解，所以n-m个非基变量取0值；它是可行解，则m个基变量取非负值，从而基本可行解正分量是个数不超过m.定义10：使目标函数达到最优值的基本可行解，称为基本最优值。•例4：（SLP)如例3，试找一个基本可行解。1060010111B解：是其一个基矩阵.p1,p3,p5是一个基。则x1,x3,x5为基变量。X2,x4为非基变量。令x2=x4=0.得x1=2,x3=3,x5=9.故x1=(2,0,3,0,9)是原问题的一个基本可行解，B1为基可行基。那么满足Ax=b,x0的正分量个数不超过m的可行解（Rank(Amn)=m）是否一定是基本可行解呢？•我们举例说明这个问题。它有正分量个数等于m(m=2)的可行解:x1=3,x2=1,x3=0,x4=0但它不是基本可行解。证：（反证法）假设可行解x=(3,1,0,0)T是上面约束的基本可行解。因为基本可行解中非基变量取0值，基变量取非负值。在这个可行解中x1,x2非零正值，因此x1,x2不可能是非基变量，只能是基变量。按定义，基变量对应的系数矩阵中的列向量p1,p2应构成一个基矩阵B.但这里p1,p2是线性相关的（p1=p2),这与B是基矩阵矛盾。故知x=(2,1,0,0)T不是基可行解。0,0,0,082244321421321xxxxxxxxxx例5.已知约束条件为：其可行域如上图，可行解（3，1，0，0）T。用x1,x2表示则为图上点（3，1）。由图可见这不是可行域的顶点。而我们将证明基本可行解是可行域的顶点。而在例4中p1,p3线性无关，所以B=(p1,p3)是一个基矩阵，对应的基本解为（4，0，0，0）T。用坐标x1,x2表示则为平面上的点（4，0），是上图可行域的顶点。0)0,4(m)1,3(1x2x•由此例可见，虽然可行解（3，1，0，0）T正分量个数不超过m，但它的正分量对应的列向量不是线性无关的，不能与一基矩阵相联系，所以它不是一个基本可行解。0,08224212121xxxxxx•现在我们把例4中松弛变量x3,x4去掉，约束变为对于这个基B=(p1,p3)的基本可行解（4，0，0，0）T。除了非基变量x2=x4=0外，还有基变量x3=0,这样的基本可行解称为退化的基本可行解。定义11：有基变量取0值的基本可行解，称为退化的基本可行解，它对应的基B称为退化的可行基。m个基变量均取正值的基本可行解，称为非退化的基本可行解对应基B称为非退化的可行基。如果一个线性规划问题的所有基本可行解都是非退化的，则称这个线性规划问题是非退化的。由以上定义可知，如果约束问题有m个基变量，则在退化的基本可行解中，正分量个数一定小于m。在基本可行解中取正值的变量一定是基变量。这样基本可行解中正分量个数也不会超过m。但是上面的例4已经说明，正分量个数不超过m的可行解不一定是基本可行解，还要看可行解中正分量对应的列向量是否线性无关而定。然而基本可行解中正分量对应的系数矩阵的列向量一定线性无关。定理1：设A是mn矩阵，秩为m,对于Ax=b,x0有：（1）可行解x0=是基本可行解的充要条件是x0的分量对应A中的列向量线性无关。（2）如果x=(0,0….0)T即x=0是可行解，则它一定是基本可行解。Tnxxx)...,(00201000...,21kjjjxxxkjjjppp...,21证明：（1）必要性.假定x0是基本可行解，由基本可行解定义可知，x0中的正分量一定是基变量，基变量对应系数矩阵A中的列向量一定在基B中，则线性无关。kjjjppp...,21充分性.假定x0正分量对应A中的列向量线性无关，只要证明x0是基本可行解。因为矩阵A的秩m，则km（k是x0的正分量个数）当km时，因rank(A)=m现在线性无关，可以再从A的其余列中找出适当m-k个向量，不妨设使线性无关，从而构成A的一个基，对应x0中的基变量取值为：因为有取0值的基变量，所以x0是对应于基（）的一个退化基本可行基解。kjjjppp...,21mkjjpp...1kjjjppp...,21mkjjpp...10...0,0...0000011mkkjjjjxxxxkjjjppp...,21mkjjpp...1•当k=m时，只要m个线性无关的向量构成一个基，而对应x0中的分量取正值的列向量线性无关。因此也构成一个基，所以x0就是对应于该基的一个非退化的基本可行解。mjjjxxx...,21kjjjppp...,21•定义１２：设A是mn矩阵，秩为m，对于Ax=b,x0的可行解x，如果满足：•（１）x的正分量个数小于或等于m（２）x的正分量对应A中的列向量线性无关。则称x是一个基本可行解。若x=0是可行解，则定义它是一个基本可行解。注：定义９与定义１２的等价性可由定义７推出。（2）因为A的秩为m,所以在A中一定存在m个线性无关的列向量，将其构成一个B,对应于可行解x=(0,0,…0)T中的基变量取０值，所以可行解x=0是对应于基B的退化的基本可行解。根据这个定理，基本可行解也可以定义如下：四.凸集我们先考察二维平面上直线段上任意一点的表示形式。取x.y为平面上两点，用以原点为起点的向量来表示x和y。并设z是线段xy上任意一点，得向量z-y.它与向量x-y平行且方向相同。于是有当时，z=y；时，z=x•当由0连续变动到1时，点z由y沿此直线连续的变动到x，且因z-y平行x-y，则有：于是有：)(yxyzyxz)1(2x1xxyz10yxyz01•这说明当时，表示以x.y为端点的直线段上的所有点，因而它代表以x.y为端点的直线段。一般地，如果x.y是n维欧氏空间Rn中的两点，则有如下定义：10yx)1(定义13：如果x=(x1…xn)T,y=(y1…yn)T是Rn中任意两点，定义的点所构成的集合为以x,y为端点的线段，对应的点x,y叫做这线段的端点，而对应的点叫做这线段的内点。)1,0(,)1(yxzTnzzzz),...,(211,010•定义14：设R是Rn中的一个点集，（即），对于任意两点以及满足的实数,恒有则称R为凸集。nRRRyRx,10(1)xyR•根据以上定义12及13可以看到，凸集的几何意义是：连接凸集中任意两点的直线段仍在此集合内。•例如实心的圆，实心的矩形，实心的球体，实心的长方体等等均是凸集，圆周不是凸集。•直观地看，凸集是没有凹入的部分，其内部没有孔洞。例5：集合是R3中的一个凸集。（可按定义证明）3321,52|Rxxxxx例7：（LP）问题：的可行域证明：设由定义知，只要证明x1,x2的任意凸组合即可。因0,,.maxxbAxtscxn|,0,RnRxAxbxxR是中的凸集。RxRx21,10,)1(21Rxx0,,0,2211xbAxxbAx2121212|24,5,0,0,RxxxxxxxxR例6：是R2中的一个凸集。上图中(a)(b)是凸集，而(c)(d)不是凸集。xy(a)xy(b)xy(c)xy(d)•定义15：设x1,x2…xk是Rn中的k个点，若存在实数满