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

第十二章 线性规划的基本概念和基本定理12.1线性规划的基本概念 12.1.1可行解，可行域定义12.1.1：称满足全部约束条件的向量为可行解或可行点。例如： SLP 如果满足这些约束，即且，则就是SLP的可行解。定义12.1.2：称所有可行解（点）构成的集合为可行集或可行域。也称为可行解集。 例如：上面 SLP 的可行域为定义12.1.3：若一个线性规划问题的可行集为空集时，则称这一线性规划无可行解。这时线性规划的约束条件不相容。由上一章的分析可以看到：一个线性规划的可行解集可以是空集，有界非空集和无界非空集。12.1.2最优解，无界解定义12.1.4：称使目标函数值达到最优值的可行解为线性规划问题的最优解定义12.1.5：对于极大化目标函数的标准线性规划问题，定义其无界解如下：对于任何给定的正数M，存在可行解 X 满足，使。那么称该线性规划问题有无界解。由定义可知，无界解的意思是：若是极大化目标函数，则在可行域上目标函数值无上界；若是极小化目标函数，则在可行域上目标函数值无下界。那么，有无界解的线性规划问题一定没有最优解。例12.1.1 考虑线性规划问题： 图12.1.1解：问题的可行域是上图所示的无界凸多边形区域，在此无界可行域上，目标函数值无上界，所以这个线性规划问题有无界解。例12.1.2 解：此问题的可行域如上图，是一个无界的多边形。但极大化目标函数却以1为上界。因此这个线性规划问题没有无界解，而且事实上，此问题目标函数最优值max f=1在可行域射线上均可达到。12.1.3. 基本可行解定义12.1.6：对于约束条件Ax=b，设A是秩m的mn矩阵，用(, j=1 n) 表示A的第j列向量。即A=()。由A的m个列向量构成的m阶方阵 B=( )若B是非奇异的，即detB0，则称B为一个基或称为一个基矩阵。 因为SLP问题中含有约束条件Ax=b，因此也通常称B为线性规划SLP的一个基。由上面定义可知，B中m个列向量是线性无关的，并且它是A的列向量组的一个最大无关组。按定义，A中m个列向量，只要是线性无关的就可以构成一个基。定义12.1.7：若变量 对应A中列向量包含在基B中，则称为B 的基变量；若变量对应A中的列向量不包含在基B中， 则称为B中的非基变量。例12.1.3 求满足 使解： 则的列是线性无关的，即是线性无关，因此是一组基。而，不在这个基中，所以为非基变量。定义12.1.8 ：设Ax=b, x0一个基，其对应的基变量构成的m维列向量记为这时若全非基变量等0，则 Ax=b ,得唯一解.记为于是得到方程组Ax=b的一个解， 非基变量称之为对应于基B的基本解。这个定义也告诉我们怎样找一个基本解）如：上面例12.1.2中，非基变量。则可得。所以是对应于基B的一个基本解，但由于=-20，则称它为满足约束 Ax=b, xo的基本可行解。对应地称B为可行基，因SLP中具有此约束条件。也通常 称为SLP的基本可行解。定义12.1.10：使目标函数达到最优值的基本可行解，称为基本最优值。例12.1.4：（SLP)如例12.1.3，试找一个基本可行解。解：是其一个基矩阵. 是一个基。则为基变量。为非基变量。令.得. 故是原问题的一个基本可行解，为基可行基。上面我们讲到基本解中有n-m个分量必须取零值，而只有m个基变量取非零值。而基本可行解，它一方面是基本解，另一方面又是可行解，因为它是基本解，所以n-m个非基变量取0值；它是可行解，则m个基变量取非负值，从而基本可行解正分量是个数不超过m.那么满足Ax=b,x0的正分量个数不超过m的可行解。是否一定是基本可行解呢？我们举例说明这个问题。例12.1.5.已知约束条件为：它有正分量个数等于m(m=2)的可行解。但它不是基本可行解。证明：（反证法）假设可行解x=(3,1,0,0)T面约束的基本可行解。因为基本可行解中非基变量取0值，基变量取非负值。在这个可行解中非零正值，因此不可能是非基变量，只能是基变量。按定义，基变量对应的系数矩阵中的列向量应构成一个基矩阵B.但这里是线性相关的（), 这与B是基矩阵矛盾。故知x=(2,1,0,0)T是基可行解。由此例可见，虽然可行解（3，1，0，0）T 正分量个数不超过m，但它的正分量对应的列向量线性无关，不能与一基矩阵相联系，所以它不是一个基本可行解。现在我们把例12.1.4中松弛变量去掉，约束变为 图12.1.2其可行域如图12.1.2，可行解（3，1，0，0）T用表示为图上点（3，1）。由图可见这不是可行域的顶点。而我们今天将证明基本可行解是可行域的顶点。而在例中线性无关，所以B=( )是一个基矩阵，对应的基本解为（4，0，0，0）T用坐标表示则为平面上的点（4，0），是上图可行域的顶点。对于这个基B=()的基本可行解（4，0，0，0）T 。除了非基变量外，还有基变量,这样的基本可行解称为退化的基本可行解。定义12.1.11：有基变量取0值的基本可行解，称为退化的基本可行解，它对应的基B称为退化的可行基。m个基变量均取正值的基本可行解，称为非退化的基本可行解，对应基B称为非退化的可行基。如果一个线性规划问题的所有基本可行解都是非退化的，则称这个线性规划问题是非退化的。由以上定义可知，如果约束问题有m 个基变量，则在退化的基本可行解中，正分量个数一定小于m.在基本可行解中去正值的变量一定是基变量。这样基本可行解中正分量个数也不会超过m. 但是上面的例4已经说明，正分量个数不超过 m 可行解不一定是基本可行解，还要看可行解中正分量对应的列向量是否线性无关而定。然而基本可行解中正分量对应的系数矩阵的列向量一定线性无关。定理12.1.1 设 A是mn矩阵，秩为 m, 对于Ax=b, x 0有： （1）可行解是基本可行解的充要条件是的分量，对应A中的列向量 线性无关。 （2）如果x=(0,0.0)T 即x=0是可行解，则它一定是基本可行解。证明：（1）必要性.假定是基本可行解，由基本可行解定义可知，中的正分量一定是基变量，基变量对应系数矩阵A中的列向量一定在基B中，则线性无关。充分性.假定正分量对应A中的列向量线性无关，只要证明是基本可行解。因为矩阵A的秩m，则km（ k是的正分量个数）当k=m时，只要m个线性无关的向量构成一个基，而对应中的分量，取正值的列向量线性无关。因此也构成一个基，所以就是对应于该基的一个非退化的基本可行解。当km时，因rank(A)=m现在线性无关，可以再从A的其余列中找出适当m-k个向量，不妨设使线性无关，从而构成A的一个基，对应中的基变量取值为： 因为有取0值的基变量，所以是对应于基（）的一个退化基本可行基解。（2）因为A的秩为m , 所以在A中一定存在m个线性无关的列向量，将其构成一个B,对应于可行解x=(0,0 ,0)T中的基变量取值，所以可行解x=0是对应于基 B的退化的基本可行解。根据这个定理，基本可行解也可以定义如下：定义12.1.12：设A是mn矩阵，秩为 m，对于 Ax=b, x0 的可行解x，如果满足：（）x 的正分量个数小于或等于 m （）x 的正分量对应 A 中的列向量线性无关。则称 x 是一个基本可行解。若 x=0 是可行解，则定义它是一个基本可行解。注：定义12.1.9与定义12.1.12的等价性可由定义12.1.7推出。12.1.4 凸集 我们先考察二维平面上直线段上任意一点的表示形式。取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维欧氏空间中的两点，则有如下定义：定义12.1.13：如果 x=(x1x2)T,y=(y1y2)T是中任意两点，定义的点所构成的集合为以x，y为端点的线段，对应 的点 x, y叫做这线段的端点，而对应的点叫做这线段的内点。定义12.1.14：设R是Rn中的一个点集，（即），对于任意两点以及满足的实数,恒有 则称R为凸集。根据以上定义12.1.12及12.1.13可以看到，凸集的几何意义是：连接凸集中任意两点的直线段仍在此集合内。例如实心的圆，实心的矩形，实心的球体，实心的长方体等等均是凸集，圆周不是凸集。直观地看，凸集是没有凹入的部分，其内部没有孔洞。(a)(b)(c)(d)图12.1.3上图中(a)(b)是凸集，而(c)(d)不是凸集。例12.1.5：集合是R3中的一个凸集。（可按定义证明）例12.1.6：是R2中的一个凸集。例12.1.7：（LP）问题： 的可行域证明：设由定义知，只要证明 x1, x2 的任意凸组合即可。因,有可见故知R是凸集。注：可以用归纳法证明：如果R是凸集，则R中任意有限个点的凸组合均在R中。定理12.1.2：(SLP)问题的可行集 是Rn中的一个凸集。（证明与例12.1.7相似）定义12.1.16：设A是矩阵，b是m维列向量，集合 如果R不是凸集，则称R为多面凸集。注：此处b的分量可取负值。一般地，我们可以把任何线性规划问题的条件都写成的形式。例如：约束条件为写成：因此，（SLP）问题的可行集是一个多面凸集。多面凸集可以有界，亦可无界。例12.1.8：将下面的约束条件：写成Ax0且 即和是两个可行解，分别记为及。它们的目标函数值分别为 因为是最优解，所以：， 又因为，故于是有 ;这表明 及均为最优解。又由的取法知当时,这时中第l分量等于0 ，当 时 这时中第l 分量等于0。 所以至少有一个的正分量个数比的正分量个数要少，记这个解为 。那么也是最优解。可见，如果不是基本最优解，即的正分量对应A中的列向量线性相关，那么总可以令一个最优解，其正分量个数比正分量个数少。如果是基本最优解，即的正分量对应A中的列向量线性无关，则取 , 即证明12.2.1（2）。 如果的正分量对应A中的列向量线性相关，则可重复上述步骤，得到最优解经过有限步必达到下面的三种情形之一：（i）的正分量对应A中的列向量线性无关，因此是基本可行解。取即为基本最优解。（ii）只有唯一的一个正分量，因A的列向量均为非零故的正分量对应A中的列向量线性无关。同（I）一样可知即为基本最优解。（iii）=0这时=0是可行解。由上面的证明已知=0就是基本最优解。 到此，我们证明了定理的第（2）部分。（3）假定目标函数在极点上达到最优值又设它们的任意凸组合为：而又故知的凸组合也是目标函数的最优值点。至此，我们全面证明了定理12.2.2。上面，定理12.2.1，定理12.2.2是线性规划的两个很重要的定理。证明了线性规划的基本可行解等同于可行域的顶点。并且，如果线性规划有最优解，则必在可行域的顶点上达到最优。这样，一个有最优解的（SLP ）问题，是一定可以从可行域的极点中（即基本可行解中）求得最优解的。而基本可行解是对应A中的m个线性无关的列向量。A只有n个列向量。从n个列向量中取出m 个线性无关向量相成的向量组。其数目上有限的。因此基本可行解的数量也是有限的。它不会超过：个。我们后面要学习的单纯形方法就是根据这一基本定理在有限个基本可行解中寻找基本最优解。另外，定理12.2.2还告诉我们，若目标函数在多于一个极点上达到最优，则在这些极点的凸组合上也达到最优。例12.2.1：考虑线性规划 ： 图12.2.1解：可行域极点为：M1（0.0），M2（2.0）M3（1.2）M4（0.1），其目标函数值分别为f1 =0 f2=2 f3=2 f4=在M1M2的凸组合上（即 在线段 M1M2 上）也达到最优。事实上，可以用图解法来说明这一点。因目标函数等值线 x1+x2=2与可行域的边重合，该直线段上的点对应目标函数值均有f=2。 推论12.3.3：若（SLP）的可行域R是有界的，则xR的充要条件是x能表成的凸组合。即：定理12.3.4：若线形规划（SLP）的可行域R非空有界，则必有最优解。证明：设是R的全部极点，由上面推论知：可表成极点的凸组合：其目标函数值为： 令 于是此式表明：任意可行解处目标函数的值均不超过极点处的目标值。故