运筹学线性规划.pptx

定义定义2：称所有可行解（点）构成的集合为可行集可行集或可行域。也称为可行解集可行解集。例如：上面 SLP 的可行域为R=x|Ax=b,x0定义定义3：若一个线性规划问题的可行集为空集时，则称这一线性规划无可行解无可行解。这时线性规划的约束条件不约束条件不相容相容。由上一章的分析可以看到：一个线性规划的可行解集可以是空集，有界非空集和无界非空集。二 最优解，无界解最优解，无界解定义定义4：称使目标函数值达到最优值的可行解为线性规划问题的最优解最优解。解解：问题的可行域是上图所示的 无界 凸多边形区域，在此无界可行域上，目标函数值无上界，所以这个线性规划问题有无界解。定义定义5：对于极大化目标函数的标准线性规划问题，定义其无界解如下：对于任何给定的正数M，存在可行解 x 满足 Ax=b，x 0，使 cx M。那么称该线性规划问题有无界解无界解。由定义可知，无界解的 意思 是：若是极大化目标函数，则在可行域上目标函数值无上界；若是极小化目标函数，则在可行域上目标函数值无下界。那么，有无界解的线性规划问题一定没有最优解。maxs.t 例例1 1.考虑线性规划问题：例例2.max f=s.t 解：此问题的可行域如上图，是一个无界的 多边形。但极大化目标函数却以1为上界。因此这个线性规划问题没有无界解，而且事实上，此问题目标函数最优值max f=1在可行域射线 上均可达到。三三.基、基本可行解基、基本可行解定义定义6：对于约束条件Ax=b，设A是秩m的mn矩阵，用(Pj,j=1 n)表示A的第j列向量。即A=()。由A的m个列向量构成的m阶方阵 B=()若B是非奇异的，即detB0，则称B为一个基基或称为一个基矩阵基矩阵。因为SLP问题中含有约束条件Ax=b，因此也通常称B为线性规划SLP的一个基。解：A=使min f=满足例3.求x1-x5由上面定义可知，B中m个列向量是线性无关的，并且它是A的列向量组的一个最大无关组。按定义，A中m个列向量，只要是线性无关的就可以构成一个基。定义定义7 7：若变量 对应A中列向量 包含在基B中，则称 为B 的基变量基变量；若变量 对应A中的列向量 不包含在基B中，则称 为B中的非基变量非基变量。定义定义8 8：设Ax=b,x 0一个基 ，其对应的基变量构成的m维列向量记为 这时若取非基 是线性无关，因此 是一组基。而 不在这个基中，所以x1,x2为非基变量。的列是线性无关的，即则于是得到方程组Ax=b的一个解：非基变量 称之为对应于基B的基本解基本解。这个定义也告诉我们怎样找一个基本解）变量等于0，则 Ax=b BxB=b,得唯一解xB=B-1b.记为 如：上面例2中，非基变量 x1=x2=0.则可得x3=5,x4=-2,x5=21.所以x0=(0,0,5,-2,21)是对应于基B的一个基本解，但由于x4=-2=0，则称它为满足约束 Ax=b,x=o的基本可行解基本可行解。对应地称B为可行基，因SLP中具有此约束条件。也通常 称为SLP的基本可行解。上面我们讲到基本解中有n-m个分量必须取零值，而只有m个基变量取非零值。而基本可行解，它一方面是基本解，另一方面又是可行解，因为它是基本解，所以n-m个非基变量取0值；它是可行解，则m个基变量取非负值，从而基本可行解正分量是个数不超过m.定义定义1010：使目标函数达到最优值的基本可行解，称为基基本最优值本最优值。例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为基可行基。那么满足Ax=b,x 0的正分量个数不超过m的可行解（Rank(Am n)=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.已知约束条件为：其可行域如上图，可行解（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去掉，约束变为 对于这个基B=(p1,p3)的基本可行解（4，0，0，0）T。除了非基变量 x2=x4=0外，还有基变量 x3=0,这样的基本可行解称为退化的基本可行解退化的基本可行解。定义定义11：有基变量取 0 值的基本可行解，称为退化的基本可行解，它对应的基B称为退化的可行基退化的可行基。m个基变量均取正值的基本可行解，称为非退化的基本可行解非退化的基本可行解对应基B称为非退化的可行基非退化的可行基。如果一个线性规划问题的所有基本可行解都是非退化的，则称这个线性规划问题是非退化的。线性规划问题是非退化的。由以上定义可知，如果约束问题有m 个基变量，则在退化的基本可行解中，正分量个数一定小于m。在基本可行解中取正值的变量一定是基变量。这样基本可行解中正分量个数也不会超过m。但是上面的例4已经说明，正分量个数不超过 m 的可行解不一定是基本可行解，还要看可行解中正分量对应的列向量是否线性无关而定。然而基本可行解中正分量对基本可行解中正分量对应的系数矩阵的列向量一定线性无关应的系数矩阵的列向量一定线性无关。证明证明：（1）必要性.假定x0是基本可行解，由基本可行解定义可知，x0中的正分量一定是基变量，基变量对应系数矩阵A中的列向量一定在基B中，则 线性无关。充分性.假定x0正分量对应A中的列向量线性无关，只要证明x0是基本可行解。因为矩阵A的秩m，则k m（k是x0的正分量个数）定理定理1 1：设设 A A是是m nm n 矩阵，秩为矩阵，秩为 m m ,对于对于Ax=b,Ax=b,x 0 x 0有：有：（1 1）可行解）可行解 x x0 0=是基本可行解的充要条件是是基本可行解的充要条件是 x x0 0 的的正分量正分量 对应对应A A中的列向量中的列向量 线性无关。线性无关。（2 2）如果）如果 x=(0,0.0)x=(0,0.0)T T 即即 x=0 x=0 是可行解，则它一定是基本可行是可行解，则它一定是基本可行解。解。当k=0，则可写成：因此，（SLP）问题的可行集是一个多面凸集。多面凸集可以有界，亦可无界。例例8 8：将下面的约束条件：写成Ax=b的形式一般地，我们可以把任何线性规划问题的条件都写成 Ax=b的形式。例如：解：上面的约束条件可以转化为：其图如下（1），是一个二维有界的多面凸集。（1）（2）所确定的是一个无界的多面凸集。如上图（2）2.2 线形规划的基本定理线形规划的基本定理一一 基本可行解与极点解的等价性本可行解与极点解的等价性例如多边形，多面体的顶点，圆周上，球面上的顶点等都是顶点。若x0是可行域的极点，设x的正分量 要证明x 是基本可行解，由上节的定理1知，只需证明这些数分量对应A中的列向量 线性无关。上面我们已经说（SLP）的可行域是由直线，平面或超平面为边界构成的凸多边形或凸多面体（亦即多面凸集）因此线形规划问题可行域的顶点就是极点。定理定理3 x是线形规划（是线形规划（SLP）可行域可行域R的极点的充要条件的极点的充要条件是：是：x是基本可行解。是基本可行解。证明：必要性。设x是可行域的极点，要证明x是基本可行解。若x=0是可行域的极点。则x=0是可行解，由上节定理1中（2）即知x是基本可行解。现在构造一个n维列向量y，它的第 分量分别为 ，其余分量为0，则有y0。且 Ay=0由于 0。（1=i=0因而 是两个可行解。分别记为：有：因 故 取 则 这表明：x可以表示成R中其它点的凸组合。这与 x是R的极点相矛盾。故必要性得证。充分性：设x是（SLP）的基本可行解。要证x是可行域的极点。若x=0 是基本可行解，而存在可行域中的点，使x=0 能表成：的形式。即 =0 因此 这表明x=0不能表成可行域中两点的凸组合，因此是极点。若x0是基本可行解。由定理1知，x的正分量 对应A中列向量 线形无关。反证法：若基本可行解x不是可行域的极点。则可行域中存在异于x的不同两点设为y和z。或 且 时 =0 所以上式变为：而 故 因而y与z是可行解，应满足 两式相减得 因为y与z是不相同的两点。他们的分量至少有一个不相等。即 不全为0。因此 线性相关。这与x是基本可行解相矛盾。故x是基本可行解。则必为可行域的顶点。证明：（1）设有可行解 若 =0，则由定理1（2）知 就是基本可行解。若 0，不妨设 的正分量为前k个。二二 基本定理基本定理 定理定理4 4 假定线性规划（SLP）的A是mn的矩阵。秩为m，且A的列向量 均不是零向量。（1）若有可行解，则必有基本可行解（即非空可行集若有可行解，则必有基本可行解（即非空可行集R必有极点）必有极点）（2）若有最优解，则目标函数必定在基本可行解上（极若有最优解，则目标函数必定在基本可行解上（极点）达到极值。（即若有最优解，则必有基本最优解）点）达到极值。（即若有最优解，则必有基本最优解）（3）若目标函数在多于一个极点上达到最优，则必在这若目标函数在多于一个极点上达到最优，则必在这些极点的凸组合上达到最优些极点的凸组合上达到最优。由于 线性相关，于是存在不全为零的数 使得 不妨设至少有一个 ,否则可取 构造n维列向量 ,则知 因为存在 则可取 而 如果正分量对应A中列向量 线性无关，则由定理1（1）知 就是基本可行解。如果正分量A中的列向量 线性相关，有定理1（1）知 不是基本可行解。（下面的证明思想就是构造比 正分量要少的新可行解 ，考虑 是不是基本可行解。）这样得出一个正分量是个数比 少的可行解 ，它除了后面的n-k个分量等于0外，前面k个分量中的第l个分量也等于0。这样我们便可以在线性相关向量组 中去掉向量 如果剩下的向量线性无关，由定理1（1）即知 就是基本可行解。否则再重复上面的步骤，可以得到可行解 它的正分量个数越来越少，经过有限步，必然得到一个可行解 。则可见是可行解。它的第l个分量令或者 则它必为基本可行解（定理1（2）或者 但其正分量个数或者大于1对应的列向量线性无关，或者正分量个数等于1，这时对应A中只有一个列向量，因为已假定A的列向量不是零向量，而一个非零向量必然线性无关。因此不论怎样 就是基本可行解（定理1（1）（2）设 是（SLP）最优解。并设 是目标函数最优值，即 。现在证明是存在基本可行解 是最优解。如果 ，则因 是最优解，首先必须是可行解。因此，就是基本可行解（定理1（2），取 就得到基本最优解 。如果 则 中必有正分量不妨设 ,其中 。若正分量对应A中的列向量 线性无关，则 就是基本可行解（定理1（1），取 即得到基本最优解 .若正分量对应A中的列向量 线性相关，则存在不全为零的数 使：。构造n维列向量y使其第1，2，k分量分别为 而其余分量为0，则有y0且 取可见 0且 即 和 是两个可行解，分别记为 及 。它们的目标函数值分别为：因为 是最优解，所以：,又因为 故 于是有 ;这表明 及 均为最优解。又由 的取法知 当 时 ,这时 中第l分量等于0，当 时 ,这时 中第l 分量等于0。所以 至少有一个的正分量个数比 的正分量个数要少，记这个解为 。那么 也是最优解。可见，如果 不是基本最优解，即 的正分量对应A中的列向量线性相关，那么总可以令一个最优解 ，其正分量个数比 正分量个数少。如果 是基本最优解，即 的正分量对应A中的列向量线性无关，则取 ,即证明3（2）。（ii）只有唯一的一个正分量，因A的列向量均为非零故 的正分量对应A中的列向量线性无关。同（I）一样可知 即为基本最优解。（iii）=0这时 =0是可行解。由上面的证明已知 =0就是基本最优解。到此，我们证明了定理的第（2）部分。（i）的正分量对应A中的列向量线性无关，因此 是基本可行解。取 即为基本最优解（3）假定目标函数在极点 上达到最优值 又设它们的任意凸组合为：如果 的正分量对应A中的列向量线性相关，则可重复上述步骤，得到最优解经过有限步必达到下面的三种情形之一：上面，定理3，定理4是线性规划的两个很重要的定理。证明了线性规划的基本可行解等同于可行域的顶点。并且，如果线性规划有最优解，则必在可行域的顶点上达到最优。这样，一个有最优解的（SLP）问题，是一定可以从可行域的极点中（即基本可行解中）求得最优解的。而又故知 的凸组合也是目标函数的最优值点。至此，我们全面证明了定理4。而基本可行解是对应A中的m个线性无关的列向量。A只有n个列向量。从n个列向量中取出m 个线性无关向量相成的向量组。其数目上有限的。因此基本可行解的数量也是有限的。它不会超过：个。这样对一个有最优解的线性规划利用穷举法可以在有限步内找到基本最优解。但运算是很大的。我们后面要学习的单纯形方法就是根据这一基本定理在有限个基本可行解中寻找基本最优解。另外，定理4还告诉我们，若目标函数在多于一个极点上达到最优，则在这些极点的凸组合上也达到最优。例：考虑线性规划：解：可行域极点为：M1（0.0），M2（2.0）M3（1.2）M4（0.1），其目标函数值分别为f1=0 f2=2 f3=2 f4=1/2，在M2M3的凸组合上（即 在线段 M2M3上）也达到最优。事实上，可以用图解法来说明这一点。因目标函数等值线 x1+1/2x2=2与可行域的边 重合，该直线段上的点对应目标函数值均有f=2。2.3 极射向、可行解的表示定理极射向、可行解的表示定理一一 极射向极射向 设A是mn矩阵，rank（A）=m。A=（p1p2pn）对于A的一个基B=（pj1 pj2 pjm )相应有 。设这在单纯形算法里是一个重要矩阵。其中 =I是m阶单位矩阵。它的每一列 （i=1m）是第I个分量为1的单位向量。若x是非基变量。对应中的第j列向量为：定义极方向：其中定义定义18 （极方向）设B是（SLP）的一个基。对于非基变量xj 下面通过对非基变量xj对应 列中的元素 来定义极方向。因此，如果xj是基B的非基变量，就有极方向Dj存在，而Dj的分量由 列中 反号及1和0组成。具体的说，Dj中第 分量取值为 的第i分量的反号即-.Dj中第j分量取值为1，其余非基变量下标（除去j）所对应的分量取值为0。下面举例说明极方向的概念：例：考虑线性规划问题：显然 是一个基阵，B-1=B先将它化为标准形式：问题的可行域如上图所示。问题是哪个取 ，哪个取 。因为B=（p4，p3）=（pj1,pj2)即j1=4，j2=3。由定义即知：于是，可得D1。并同理可得D2的表示式如下：则对应非基变量 的极方向分别为：我们来看它们的分量是怎样取值先考虑 ,由定义 =1，是非基变量所以 =0,再 看基变量 对应 中的 怎样取值，按定义，应取 元素的值 及 。定理定理5 （极方向性质）设Dj是基B的非基变量xj极方向，则有ADj=0.证明：设 易验证：一般的我们有：因为即 （*）=又由极方向定义及（*）式有：在上例中由已知A及D1的表达式得A D1=0即为下式 定义定义1919：对于极方向 若满足 0 0。则称 为极 方向。因此上例中 是极方向，而 不是。定理定理6 6 设B是线形规划（SLP）的一个可行基，对应基本可行解为 。若对某个非基变量 ，存在极射向 0且满足C 0。则此线形规划问题目标函数无上界，故无最优解。上例中 0在线形规划中这种极方向比较重要。事实上，我的以上例中线形规划存在可行性解，同时又存在极方向 0。由图象又可见其可行域是无界的。此方程由知 可由 及 表示出来。当取 =1，=0时，得到 =1，=0。这就是D1由D1及P2的前两个坐标构成平面上向量分别为 也画在前面的坐标图中。证明：因为 0而由Th.5.A =0则对 实数0。满足：A（+）=A =b +0因此 +是可行解。由定理中的条件C 0当时，目标函数f=C（+）=C +C 这表明目标函数无上界。无最优解。证毕。这个定理告诉我们，当存在极射向 0时那么 +，也是可行解，而 中一定有正分是（因为至少有 =1）但由于a 0可以取任意大的正数。所以可行解 +对于 中正分量的那些坐标随+而趋于+这表示只要存在 ,可行域必是无界的。但我们已经说过，有无界可行域并不意味就有无界解，而加上条件CDj0后，目标函数就无上界了。这时就有无界解。因而无最优解。我们在回过头来考虑上面的例子：在上面的例子中 =（1,0,1,0)T 及C=（1.-1.0.0)T 故满足CD1=10。而这个线形规划又存在基可行解 =（0,0,1,2)T当0时，+=（,0,1+,2)T 也是可行解。但当 时，坐标x=因此可行域是无界的而目标函数f=C（+）=无上界，二二 可行解的表示定理可行解的表示定理 当可行域无界时，除了考虑可行域的极点外，还要考虑极射向。上节已经分析出结论：（SLP）可行域的极点（基可行解）不超过 个是有限的。设共有r个极点：如果（SLP）存在极射向，一样的分析可知，极射向也是有限个。设为：于是有下面的表示定理：定理定理7 设 非空。A是mn阵，rankA=m且A的列向量均不为零向量。则x是可行解(即xR)的充要条件是：存在非负实数 使得 证明：先证充分性。若x能表示成（*）式，要证xR。可见xR再证必要性。即xR，要证x能表成（*）式。知x可以表成（*）式，即现考虑x0的情形。证明的方法是对x 正分量的个数进行数学归纳法。第一步。假定某线性规划问题可行解x的正分量最少是t个（t1）要证x能表成（*）式，不妨设x的前t个分量均大于0。即则 x 就可以表成 （*）式形式：但x的正分量个数比t小，这与假设 问题可行解的正分量个数最少是t相矛盾。因此P1,P2,Pt线性无关。这样，由 TH.1（1）即知x是一个基本可行解，设它是x1,xi,xr中的xi，这时只要取 第三步，要证明正分量个数等于k的可行解x也可以表成（*）式。不失一般性设 ，假定正分量 对应A中列向量为 。如果 线性无关，则由 知x是一个基可行解。由第一步的证明知x可以表成（*）式。如果 （k2）线性相关，这时在 中一定存在最大无关组，不妨设为 因此 中每一个向量都可由 线性表出。设 （）但rank（A）=m。因此一定可以在A的其余列中选出适当的m+s-k个向量，不妨设为 ，使得 第二步，假定正分量个数小于k（k1）的可行解x，由归纳法假定x能够表成（*）式。线性无关，从而构成一个基，记为 （s1）由于s1。因此 不在基B中，即 为一非基变量，则有极方向，设为：（）-（）得：即有：（）由定理5知AD=0。再根据（）式即得：根据极方向定义有 。而 及 均为非基变量，所以 （）下面来证明而 线性无关。故有这样 下面分两种情形来讨论：（1）若D0。则D是极方向。不妨设这个极方向就是 中的 。由于 的分量 ，因此 必然存在正分量，取令，显然且因此 R。但，即 的第1至第k分量中的第e分量是0，即 的k 个分量里至少有一个0分量，而它的后面n-k个分量均为0（x及D的后n-k个分量均为0）由此知 的正分量个数小于k，且 R。于是x就表示成了（*）式形式了。（2）若当中有负分量。因 这样当中必同时有正，负分量。作 其中：由归纳假设知 可表示为（*）式，设为：因此有：易见即 和 均为可行解。而且也就是设 和 的正分量个数都小于k，由归纳法假定知 ，均可以表示成（*）式。设为：又从 及 中消去D，即得：解 的表达式代入上式即得：根据归纳法证明原理，即原命题得证。显然有其中 推论：若定理7中的可行域R是有界的，则xR的充要条件是x能表成 的凸组合。即：注：当可行集非空有界时，只存在极点，不存在极射向。证明：（反证法）如果存在极射向 。且 中必有正分量（例如 ）而可行集非空，则必有可行解。设 则对那么中对应 中正分量的坐标随而趋于 。这与可行域有界矛盾因此非空有界可行域不存在极射向。可行解的表示定理也是线形规划的一个基本定理，在后面的大规模分解算法里，将会适用这个定理。这个推论表明当可行域有界时，可行解由（*）式表示，因为这时可行域没有极射向，因此表示式中只有相关凸组合。利用这个推论可得到一个最优解存在定理。定理定理8：若线形规划（若线形规划（SLPSLP）的可行域的可行域R R非空有界，则必有非空有界，则必有最优解。最优解。证明：设 是R的全部极点，由上面推论知：可表成极点的凸组合：其目标函数值为：令于是此式表明：任意可行解处目标函数的值均不超过极点 处的目标值 。故极点 即为最优解。这个定理表明：（SLP）的可行域R中非空有界，则必有最优解，或唯一，或多个（在极点及凸组合上）而不可能是有可行解而无最优解的情形。