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

第二章线性规划的基本概念与基本定理第1页，共58页，2023年，2月20日，星期三定义2：称所有可行解（点）构成的集合为可行集或可行域。也称为可行解集。例如：上面SLP的可行域为R={Z|AZ=b,Z≥0}定义3：若一个线性规划问题的可行集为空集时，则称这一线性规划无可行解。这时线性规划的约束条件不相容。由上一章的分析可以看到：一个线性规划的可行解集可以是空集，有界非空集和无界非空集。二最优解，无界解定义4：称使目标函数值达到最优值的可行解为线性规划问题的最优解。第2页，共58页，2023年，2月20日，星期三解：问题的可行域是上图所示的无界凸多边形区域，在此无界可行域上，目标函数值无上界，所以这个线性规划问题有无界解。定义5：对于极大化目标函数的标准线性规划问题，定义其无界解如下：对于任何给定的正数M，存在可行解X满足AX=b，X≥0，使cX>M。那么称该线性规划问题有无界解。由定义可知，无界解的意思是：若是极大化目标函数，则在可行域上目标函数值无上界；若是极小化目标函数，则在可行域上目标函数值无下界。那么，有无界解的线性规划问题一定没有最优解。 maxs.t

例1.考虑线性规划问题：第3页，共58页，2023年，2月20日，星期三例2.maxf=s.t解：此问题的可行域如上图，是一个无界的多边形。但极大化目标函数却以1为上界。因此这个线性规划问题没有无界解，而且事实上，此问题目标函数最优值maxf=1在可行域射线 上均可达到。三.基、基本可行解定义6：对于约束条件Ax=b，设A是秩m的mｘn矩阵，用(Pj,j=1~n)表示A的第j列向量。即A=()。由A的m个列向量构成的m阶方阵B=()若B是非奇异的，即detB‡0，则称B为一个基或称为一个基矩阵。因为SLP问题中含有约束条件Ax=b，因此也通常称B为线性规划SLP的一个基。第4页，共58页，2023年，2月20日，星期三解：A=使minf=满足例3.求x1----x5由上面定义可知，B中m个列向量是线性无关的，并且它是A的列向量组的一个最大无关组。按定义，A中m个列向量，只要是线性无关的就可以构成一个基。定义7：若变量对应A中列向量包含在基B中，则称为B的基变量；若变量对应A中的列向量不包含在基B中，则称为B中的非基变量。第5页，共58页，2023年，2月20日，星期三定义8：设Ax=b,x0一个基，其对应的基变量构成的m维列向量记为这时若全非基是线性无关，因此是一组基。而不在这个基中，所以x1,x2为非基变量。的列是线性无关的，即则第6页，共58页，2023年，2月20日，星期三于是得到方程组Ax=b的一个解：非基变量称之为对应于基B的基本解。这个定义也告诉我们怎样找一个基本解）变量等于0，则Ax=bBxB=b,得唯一解xB=B-1b.记为如：上面例2中，非基变量x1=x2=0.则可得x3=5,x4=-2,x5=21.所以x0=(0,0,5,-2,21)是对应于基B的一个基本解，但由于x4=-2<0.不能满足约束条件，所以这个基本解不是原问题的可行解。（为什么？）这是因为，按照定义，基本解中的n-m个非基变量必须取0值只有m个基变量取值才可能不等于0。但可以取负值。因此基本解不一定满足SLP的非负要求。

定义9对应于基B的基本解，若基变量取非负值，即xB=B-1b>=0，则称它为满足约束Ax=b,x>=o的基本可行解。对应地称B为可行基，因SLP中具有此约束条件。也通常称为SLP的基本可行解。第7页，共58页，2023年，2月20日，星期三上面我们讲到基本解中有n-m个分量必须取零值，而只有m个基变量取非零值。而基本可行解，它一方面是基本解，另一方面又是可行解，因为它是基本解，所以n-m个非基变量取0值；它是可行解，则m个基变量取非负值，从而基本可行解正分量是个数不超过m.定义10：使目标函数达到最优值的基本可行解，称为基本最优值。例4：（SLP)如例3，试找一个基本可行解。解：是其一个基矩阵.p1,p3,p5是一个基。则x1,x3,x5为基变量。x2,x4为非基变量。令x2=x4=0.得x1=2,x3=3,x5=9.故x1=(2,0,3,0,9)是原问题的一个基本可行解，B1为基可行基。第8页，共58页，2023年，2月20日，星期三那么满足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不是基可行解。例5.已知约束条件为：第9页，共58页，2023年，2月20日，星期三其可行域如上图，可行解（3，1，0，0）T。用x1,x2表示则为图上点（3，1）。由图可见这不是可行域的顶点。而我们将证明基本可行解是可行域的顶点。而在例4中p1,p3线性无关，所以B=(p1,p3)是一个基矩阵，对应的基本解为（4，0，0，0）T。用坐标x1,x2表示则为平面上的点（4，0），是上图可行域的顶点。由此例可见，虽然可行解（3，1，0，0）T

正分量个数不超过m，但它的正分量对应的列向量不是线性无关的，不能与一基矩阵相联系，所以它不是一个基本可行解。现在我们把例4中松弛变量x3,x4去掉，约束变为第10页，共58页，2023年，2月20日，星期三对于这个基B=(p1,p3)的基本可行解（4，0，0，0）T。除了非基变量x2=x4=0外，还有基变量x3=0,这样的基本可行解称为退化的基本可行解。定义11：有基变量取0值的基本可行解，称为退化的基本可行解，它对应的基B称为退化的可行基。

m个基变量均取正值的基本可行解，称为非退化的基本可行解对应基B称为非退化的可行基。如果一个线性规划问题的所有基本可行解都是非退化的，则称这个线性规划问题是非退化的。由以上定义可知，如果约束问题有m个基变量，则在退化的基本可行解中，正分量个数一定小于m。在基本可行解中取正值的变量一定是基变量。这样基本可行解中正分量个数也不会超过m。但是上面的例4已经说明，正分量个数不超过m的可行解不一定是基本可行解，还要看可行解中正分量对应的列向量是否线性无关而定。然而基本可行解中正分量对应的系数矩阵的列向量一定线性无关。第11页，共58页，2023年，2月20日，星期三

定理1：设A是mn矩阵，秩为m,对于Ax=b,x0有：（1）可行解x0=是基本可行解的充要条件是x0的分量对应A中的列向量线性无关。（2）如果x=(0,0….0)T即x=0是可行解，则它一定是基本可行解。证明：（1）必要性.假定x0是基本可行解，由基本可行解定义可知，x0中的正分量一定是基变量，基变量对应系数矩阵A中的列向量一定在基B中，则线性无关。充分性.假定x0正分量对应A中的列向量线性无关，只要证明x0是基本可行解。因为矩阵A的秩m，则km（k是x0的正分量个数）第12页，共58页，2023年，2月20日，星期三当k<m时，因rank(A)=m现在线性无关，可以再从A的其余列中找出适当m-k个向量，不妨设使

线性无关，从而构成A的一个基，对应x0中的基变量取值为：因为有取0值的基变量，所以x0是对应于基（）的一个退化基本可行基解。当k=m时，只要m个线性无关的向量构成一个基，而对应x0中的分量取正值的列向量线性无关。因此也构成一个基，所以x0就是对应于该基的一个非退化的基本可行解。第13页，共58页，2023年，2月20日，星期三定义１２：设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的退化的基本可行解。根据这个定理，基本可行解也可以定义如下：第14页，共58页，2023年，2月20日，星期三四.凸集我们先考察二维平面上直线段上任意一点的表示形式。取x.y为平面上两点，用以原点为起点的向量来表示x和y。并设z是线段xy上任意一点，得向量z-y.它与向量x-y平行且方向相同。于是有

当时，z=y；时，z=x当由0连续变动到1时，点z由y沿此直线连续的变动到x，且因z-y平行x-y，则有：于是有：这说明当时，表示以x.y为端点的直线段上的所有点，因而它代表以x.y为端点的直线段。一般地，如果x.y是n维欧氏空间Rn中的两点，则有如下定义：第15页，共58页，2023年，2月20日，星期三定义13：如果x=(x1…xn)T,y=(y1…yn)T是Rn中任意两点，定义的点所构成的集合为以x,y为端点的线段，对应的点x,y叫做这线段的端点，而对应的点叫做这线段的内点。

定义14：设R是Rn中的一个点集，（即），对于任意两点以及满足的实数,恒有则称R为凸集。根据以上定义12及13可以看到，凸集的几何意义是：连接凸集中任意两点的直线段仍在此集合内。例如实心的圆，实心的矩形，实心的球体，实心的长方体等等均是凸集，圆周不是凸集。直观地看，凸集是没有凹入的部分，其内部没有孔洞。第16页，共58页，2023年，2月20日，星期三例5：集合是R3中的一个凸集。（可按定义证明）例7：（LP）问题：的可行域证明：设由定义知，只要证明x1,x2的任意凸组合即可。因例6：是R2中的一个凸集。上图中(a)(b)是凸集，而(c)(d)不是凸集。(a)(b)(c)(d)第17页，共58页，2023年，2月20日，星期三定义15：设x1,x2…xk是Rn中的k个点，若存在实数满足使则称x是x1,x2…xk的凸组合。

定理2：(SLP)问题的可行集是Rn中的一个凸集（证明与例7相似）

定义16：设A是矩阵，b是m维列向量，集合如果R是凸集，则称R为多面凸集。注：此处b的分量可取负值。有可见故知R是凸集。注：可以用归纳法证明：如果R是凸集，则R中任意有限个点的凸组合均在R中。第18页，共58页，2023年，2月20日，星期三约束条件为Ax=b，x>=0，则可写成：因此，（SLP）问题的可行集是一个多面凸集。多面凸集可以有界，亦可无界。例8：将下面的约束条件：写成Ax<=b的形式一般地，我们可以把任何线性规划问题的条件都写成Ax<=b的形式。例如：第19页，共58页，2023年，2月20日，星期三解：上面的约束条件可以转化为：其图如下（1），是一个二维有界的多面凸集。（1）（2）第20页，共58页，2023年，2月20日，星期三所确定的是一个无界的多面凸集。如上图（2）

§2.2线形规划的基本定理一基本可行解与极点解的等价性例如多边形，多面体的顶点，圆周上，球面上的顶点等都是顶点。第21页，共58页，2023年，2月20日，星期三若x≠0是可行域的极点，设x的正分量要证明x是基本可行解，由上节的定理1知，只需证明这些数分量对应A中的列向量线性无关。上面我们已经说（SLP）的可行域是由直线，平面或超平面为边界构成的凸多边形或凸多面体（亦即多面凸集）因此线形规划问题可行域的顶点就是极点。定理3

x是线形规划（SLP）可行域R的极点的充要条件是：x是基本可行解。证明：必要性。设x是可行域的极点，要证明x是基本可行解。若x=0是可行域的极点。则x=0是可行解，由上节定理1中（2）即知x是基本可行解。第22页，共58页，2023年，2月20日，星期三现在构造一个n维列向量y，它的第分量分别为，其余分量为0，则有y≠0。且

Ay==0由于≠0。（1<=i<=k），取可见〉0且xy>=0因而是两个可行解。分别记为：

有：第23页，共58页，2023年，2月20日，星期三因故取则这表明：x可以表示成R中其它点的凸组合。这与x是R的极点相矛盾。故必要性得证。充分性：设x是（SLP）的基本可行解。要证x是可行域的极点。若x=0是基本可行解，而存在可行域中的点，使x=0能表成：的形式。即=0因此这表明x=0不能表成可行域中两点的凸组合，因此是极点。若x≠0是基本可行解。由定理1知，x的正分量对应A中列向量线形无关。反证法：若基本可行解x不是可行域的极点。则可行域中第24页，共58页，2023年，2月20日，星期三存在异于x的不同两点设为y和z。或且时=0所以上式变为：而故因而y与z是可行解，应满足两式相减得因为y与z是不相同的两点。他们的分量至少有一个不相等。即不全为0。因此线性相关。这与x是基本可行解相矛盾。故x是基本可行解。则必为可行域的顶点。第25页，共58页，2023年，2月20日，星期三证明：（1）设有可行解若=0，则由定理1（2）知就是基本可行解。若≠0，不妨设的正分量为前k个。二基本定理

定理4假定线性规划（SLP）的A是m×n的矩阵。秩为m，且A的列向量均不是零向量。（1）若有可行解，则必有基本可行解（即非空可行集R必有极点）（2）若有最优解，则目标函数必定在基本可行解上（极点）达到极值。（即若有最优解，则必有基本最优解）（3）若目标函数在多于一个极点上达到最优，则必在这些极点的凸组合上达到最优。第26页，共58页，2023年，2月20日，星期三由于线性相关，于是存在不全为零的数使得不妨设至少有一个,否则可取构造n维列向量,则知

因为存在则可取而如果正分量对应A中列向量线性无关，则由定理1（1）知就是基本可行解。如果正分量A中的列向量线性相关，有定理1（1）知不是基本可行解。（下面的证明思想就是构造比正分量要少的新可行解，考虑是不是基本可行解。）第27页，共58页，2023年，2月20日，星期三这样得出一个正分量是个数比少的可行解，它除了后面的n-k个分量等于0外，前面k个分量中的第l个分量也等于0。这样我们便可以在线性相关向量组中去掉向量如果剩下的向量线性无关，由定理1（1）即知就是基本可行解。否则再重复上面的步骤，可以得到可行解它的正分量个数越来越少，经过有限步，必然得到一个可行解。则可见是可行解。它的第l个分量令第28页，共58页，2023年，2月20日，星期三或者则它必为基本可行解（定理1（2））或者但其正分量个数或者大于1对应的列向量线性无关，或者正分量个数等于1，这时对应A中只有一个列向量，因为已假定A的列向量不是零向量，而一个非零向量必然线性无关。因此不论怎样就是基本可行解（定理1（1））（2）设是（SLP）最优解。并设是目标函数最优值，即。现在证明是存在基本可行解是最优解。如果，则因是最优解，首先必须是可行解。因此，就是基本可行解（定理1（2）），取就得到基本最优解。如果则中必有正分量不妨设,其中。若正第29页，共58页，2023年，2月20日，星期三分量对应A中的列向量线性无关，则就是基本可行解（定理1（1）），取即得到基本最优解.若正分量对应A中的列向量线性相关，则存在不全为零的数使：。构造n维列向量y使其第1，2，……k分量分别为而其余分量为0，则有y≠0且取可见>0且即和是两个可行解，分别记为及。它们的目标函数值分别为：第30页，共58页，2023年，2月20日，星期三因为是最优解，所以：,又因为故于是有;这表明及均为最优解。又由的取法知

当时,这时中第l分量等于0，当时,这时中第l分量等于0。所以至少有一个的正分量个数比的正分量个数要少，记这个解为。那么也是最优解。可见，如果不是基本最优解，即的正分量对应A中的列向量线性相关，那么总可以令一个最优解，其正分量个数比正分量个数少。如果是基本最优解，即的正分量对应A中的列向量线性无关，则取,即证明3（2）。第31页，共58页，2023年，2月20日，星期三（ii）只有唯一的一个正分量，因A的列向量均为非零故的正分量对应A中的列向量线性无关。同（I）一样可知即为基本最优解。（iii）=0这时=0是可行解。由上面的证明已知=0就是基本最优解。到此，我们证明了定理的第（2）部分。（i）的正分量对应A中的列向量线性无关，因此是基本可行解。取即为基本最优解（3）假定目标函数在极点上达到最优值又设它们的任意凸组合为：如果的正分量对应A中的列向量线性相关，则可重复上述步骤，得到最优解经过有限步必达到下面的三种情形之一：第32页，共58页，2023年，2月20日，星期三上面，定理3，定理4是线性规划的两个很重要的定理。证明了线性规划的基本可行解等同于可行域的顶点。并且，如果线性规划有最优解，则必在可行域的顶点上达到最优。这样，一个有最优解的（SLP）问题，是一定可以从可行域的极点中（即基本可行解中）求得最优解的。而又故知的凸组合也是目标函数的最优值点。至此，我们全面证明了定理4。第33页，共58页，2023年，2月20日，星期三而基本可行解是对应A中的m个线性无关的列向量。A只有n个列向量。从n个列向量中取出m个线性无关向量相成的向量组。其数目上有限的。因此基本可行解的数量也是有限的。它不会超过：个。这样对一个有最优解的线性规划利用穷举法可以在有限步内找到基本最优解。但运算是很大的。我们后面要学习的单纯形方法就是根据这一基本定理在有限个基本可行解中寻找基本最优解。另外，定理4还告诉我们，若目标函数在多于一个极点上达到最优，则在这些极点的凸组合上也达到最优。第34页，共58页，2023年，2月20日，星期三例：考虑线性规划：解：可行域极点为：M1（0.0），M2（2.0）M3（1.2）M4（0.1），其目标函数值分别为f1=0f2=2f3=2f4=1/2，在M2M3的凸组合上（即在线段M2M3上）也达到最优。事实上，可以用图解法来说明这一点。因目标函数等值线x1+1/2x2=2与可行域的边重合，该直线段上的点对应目标函数值均有f=2。第35页，共58页，2023年，2月20日，星期三§2.3极射向、可行解的表示定理一极射向设A是m×n矩阵，rank（A）=m。A=（p1p2……pn）对于A的一个基B=（pj1pj2……pjm)相应有。设这在单纯形算法里是一个重要矩阵。其中=I是m阶单位矩阵。它的每一列（i=1~m）是第I个分量为1的单位向量。若x是非基变量。对应中的第j列向量为：第36页，共58页，2023年，2月20日，星期三定义极方向：其中定义18（极方向）设B是（SLP）的一个基。对于非基变量xj下面通过对非基变量xj对应列中的元素来定义极方向。第37页，共58页，2023年，2月20日，星期三因此，如果xj是基B的非基变量，就有极方向Dj存在，而Dj的分量由列中反号及1和0组成。具体的说，Dj中第分量取值为的第i分量的反号即-.Dj中第j分量取值为1，其余非基变量下标（除去j）所对应的分量取值为0。下面举例说明极方向的概念：例：考虑线性规划问题：第38页，共58页，2023年，2月20日，星期三显然是一个基阵，B-1=B先将它化为标准形式：问题的可行域如上图所示。第39页，共58页，2023年，2月20日，星期三问题是哪个取，哪个取。因为B=（p4，p3）=（pj1,pj2)即j1=4，j2=3。由定义即知：于是，可得D1。并同理可得D2的表示式如下：则对应非基变量的极方向分别为：我们来看它们的分量是怎样取值先考虑,由定义=1，是非基变量所以=0,再看基变量对应中的怎样取值，按定义，应取元素的值及。第40页，共58页，2023年，2月20日，星期三定理5（极方向性质）设Dj是基B的非基变量xj极方向，则有ADj=0.证明：设

易验证：一般的我们有：因为第41页，共58页，2023年，2月20日，星期三即（*）=又由极方向定义及（*）式有：在上例中由已知A及D1的表达式得AD1=0即为下式第42页，共58页，2023年，2月20日，星期三

定义19：对于极方向若满足≥0。则称为极方向。因此上例中是极方向，而不是。定理6设B是线形规划（SLP）的一个可行基，对应基本可行解为。若对某个非基变量，存在极射向≥0且满足C>0。则此线形规划问题目标函数无上界，故无最优解。上例中≥0在线形规划中这种极方向比较重要。事实上，我的以上例中线形规划存在可行性解，同时又存在极方向≥0。由图象又可见其可行域是无界的。此方程由知可由及表示出来。当取=1，=0时，得到=1，=0。这就是D1由D1及P2的前两个坐标构成平面上向量分别为也画在前面的坐标图中。第43页，共58页，2023年，2月20日，星期三证明：因为≥0而由Th.5.A=0则对实数λ>0。满足：A（+

λ）=A=b+

λ≥0因此+λ是可行解。由定理中的条件C>0当λ→∞时，目标函数f=C（+λ）=C+λC→

∞这表明目标函数无上界。无最优解。证毕。这个定理告诉我们，当存在极射向0时那么+λ，也是可行解，而中一定有正分是（因为至少有=1）但由于a>0可以取任意大的正数。所以可行解+λ对于中正分量的那些坐标随λ→+∞而趋于+∞这表示只要存在,可行域必是无界的。第44页，共58页，2023年，2月20日，星期三但我们已经说过，有无界可行域并不意味就有无界解，而加上条件CDj>0后，目标函数就无上界了。这时就有无界解。因而无最优解。我们在回过头来考虑上面的例子：在上面的例子中=（1,0,1,0)T

及C=（1.-1.0.0)T

故满足CD1=1>0。而这个线形规划又存在基可行解=（0,0,1,2)T当λ>0时，+=（,0,1+,2)T

也是可行解。但当→∞时，坐标x=→∞因此可行域是无界的而目标函数f=C（+）=→∞无上界，第45页，共58页，2023年，2月20日，星期三二可行解的表示定理当可行域无界时，除了考虑可行域的极点外，还要考虑极射向。上节已经分析出结论：（SLP）可行域的极点（基可行解）不超过个是有限的。设共有r个极点：如果（SLP）存在极射向，一样的分析可知，极射向也是有限个。设为：于是有下面的表示定理：

定理7设非空。A是m×n阵，rankA=m且A的列向量均不为零向量。则x是可行解(即x∈R)的充要条件是：存在非负实数使得第46页，共58页，2023年，2月20日，星期三

证明：先证充分性。若x能表示成（*）式，要证x∈R。可见x∈R再证必要性。即x∈R，要证x能表成（*）式。第47页，共58页，2023年，2月20日，星期三

知x可以表成（*）式，即现考虑x≠0的情形。证明的方法是对x正分量的个数进行数学归纳法。第一步。假定某线性规划问题可行解x的正分量最少是t个（t≥1）要证x能表成（*）式，不妨设x的前t个分量均大于0。即第48页，共58页，2023年，2月20日，星期三则x就可以表成

（*）式形式：但x’的正分量个数比t小，这与假设问题可行解的正分量个数最少是t相矛盾。因此P1,P2,…,Pt线性无关。这样，由TH.1（1）

即知x是一个基本可行解，设它是x1,…,xi,…,xr中的xi，这时只要取第49页，共58页，2023年，2月20日，星期三第三步，要证明正分量个数等于k的可行解x也可以表成（*）式。不失一般性设，假定正分量对应A中列向量为。如果线性无关，则由知x是一个基可行解。由第一步的证明知x可以表成（*）式。如果（k≥2）线性相关，这时在中一定存在最大无关组，不妨设为因此中每一个向量都可由线性表出。设