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

第十二章 线性规划的基本概念和基本定理12.1 线性规划的基本概念12.1.1可行解，可行域定义 12.1.1：称满足全部约束条件的向量为可行解或可行点.max f 二 CZ 例如：SLP f AZ 二 bs.t 0如果Z0满足这些约束，即AZ0 = b且Z0 0，则Z0就是SLP的可行解.定义 12.1.2：称所有可行解（点）构成的集合为可行集或可行域.也称为可 行解集.例如：上面SLP的可行域为R二AZ二b,Z 0定义 12.1.3：若一个线性规划问题的可行集为空集时，则称这一线性规划 无可行解.这时线性规划的约束条件不相容.矚慫润厲钐瘗睞枥庑赖。由上一章的分析可以看到：一个线性规划的可行解集可以是空集，有界非 空集和无界非空集.12.1.2最优解，无界解定义 12.1.4：称使目标函数值达到最优值的可行解为线性规划问题的最优 解定义 12.1.5：对于极大化目标函数的标准线性规划问题，定义其无界解如下：对于任何给定的正数M，存在可行解X满足AX二b, X 0，使CX M .那么称该线性规划问题有无界解.聞創沟燴鐺險爱氇谴净。由定义可知，无界解的意思是：若是极大化目标函数，则在可行域上目标函数值无上界；若是极小化目标函数，则在可行域上目标函数值无下界 .那么，例 12.1.1 考虑线性规划问题：max(x + x )12x1有无界解的线性规划问题一定没有最优解.x - x 11 2 st 彳一x + x 0, x 012图 12.1.1解：问题的可行域是上图所示的无界凸多边形区域，在此无界可行域上 目标函数值无上界，所以这个线性规划问题有无界解.酽锕极額閉镇桧猪訣锥。x 一 x 1例 1212nax f 二 x x12st1 2v x + x 0, x 012解：此问题的可行域如上图，是一个无界的多边形 .但极大化目标函数却以1 为上界 .因此这个线性规划问题没有无界解，而且事实上，此问题目标函数最优值max f=l在可行域射线x x二1上均可达到.1212.1.3. 基本可行解定义12.1.6:对于约束条件Ax=b，设A是秩m的mxn矩阵，用(P , j=1jn)表示A的第j列向量.即A=(p .p ).由A的m个列向量构成的m阶方阵1nB=( p , p .p )謀荞抟箧飆鐸怼类蒋薔。 j1 j2jm若B是非奇异的，即detB工0,则称B为一个基或称为一个基矩阵.因为SLP问题中含有约束条件Ax=b，因此也通常称B为线性规划SLP的 一个基.由上面定义可知，B中m个列向量是线性无关的，并且它是A的列向量组 的一个最大无关组.按定义，A中m个列向量，只要是线性无关的就可以构成一个基.定义12.1.7：若变量x对应A中列向量p包含在基B中，则称x为B的jjj基变量；若变量x对应A中的列向量p不包含在基B中，则称x为B中的非基k k k变量.x + x + x = 5123. x + x + x = 2例12.1.3求xx满足V 124使f = 2x + x156 x + 2 x + x = 21121 2 5x 0, i = 1 5i1 110 01 0 0、A=110 10则 B =0 1 0、6 2 0 0 1 丿0 0 1 丿解:的列是线性无关的， 即0r 1r 1 p=0是线性无关，因此x x x 是一组基.而p =1,p =1511J3451【0 J2【2 J不在这个基中，所以x , x为非基变量.12定义12.1.8：设Ax=b,x0 个基B =(p .p)，其对应的基变量构成j1j m的m维列向量记为x = (xBj1.x)t这时若全非基变量等0,则Ax=b n Bx = b,B得唯一解x = B-i b.记为B-i b = (b. b t)于是得到方程组Ax=b的一个解非基变量B1 m=b ,x =b .x=b ,ij 22jmmx = 0,( j = 1,2.n,i丰j j )称之为对应于基B的基本解这个定义也告诉我们怎 ji, m样找一个基本解)茕桢广鳓鯡选块网羈泪。如：上面例12.1.2中，非基变量x = x = 0 .则可得x = 5, x = 4, x = 21.12345所以x = (0,0,5, -2,21)是对应于基B的一个基本解，但由于x =-20，则称它为满足约束Ax=b, xo的基本可行解.对应地称B为可行基，因SLP中具有此约束条件.也通常称为SLP的基本 可行解.定义 12.1.10：使目标函数达到最优值的基本可行解，称为基本最优值.例12.1.4：(SLP)如例12.1.3，试找一个基本可行解.1 1 0、解：B =-100是其一个基矩阵.p , p , p是一个基.则x ,x ,x为基变135135I 6 0 1 丿量.x ,x 为非基变量.令x = x = 0.得x = 2, x = 3, x = 9.故x = (2,0,3,0,9)是24241351原问题的一个基本可行解， B 为基可行基.渗釤呛俨匀谔鱉调硯錦。1上面我们讲到基本解中有n-m个分量必须取零值，而只有m个基变量取非 零值.而基本可行解，它一方面是基本解，另一方面又是可行解，因为它是基本 解，所以n-m个非基变量取0值；它是可行解，则m个基变量取非负值，从而 基本可行解正分量是个数不超过m.铙誅卧泻噦圣骋贶頂廡那么满足Ax=b,x、0的正分量个数不超过m的可行解.Rank(A ) = m是否 mxn 一定是基本可行解呢？我们举例说明这个问题.x + x + x = 4123例 12.1.5.已知约束条件为： 0, x 0, x 0, x 01234它有正分量个数等于m(m=2)的可行解.x二3, x二1, x二0, x二0但它不1234是基本可行解.证明：(反证法)假设可行解x=(3,1,0,0)T面约束的基本可行解因为基本可 行解中非基变量取 0 值，基变量取非负值.擁締凤袜备訊顎轮烂蔷。在这个可行解中x ,x非零正值，因此x ,x不可能是非基变量，只能是基变1 2 1 2量.按定义，基变量对应的系数矩阵中的列向量p ,p应构成一个基矩阵B.但12这里p ,p是线性相关的(p二p ),这与B是基矩阵矛盾故知x=(2,1,0,0)t是基1 2 1 2 可行解.贓熱俣阃歲匱阊邺镓騷。由此例可见，虽然可行解(3, 1，0，0)t正分量个数不超过m,但它的正 分量对应的列向量线性无关，不能与一基矩阵相联系，所以它不是一个基本可 行解.坛摶乡囂忏蒌鍥铃氈淚。现在我们把例12.1.4中松弛变量x ,x去掉，约束变为34x + x 41 2 2 x + 2 x 0, x 012x1图 12.1.2其可行域如图12.1.2,可行解(3, 1, 0，0)t用x ,x表示为图上点(3, 121) .由图可见这不是可行域的顶点.而我们今天将证明基本可行解是可行域的顶点.而在例中 p,p 线性无关，所以 B=( p,p )是一个基矩阵，对应的基本解为1 2 1 2(4, 0, 0, 0)t用坐标x ,x表示则为平面上的点(4, 0),是上图可行域的 12顶点.对于这个基B=( p ,p )的基本可行解(4, 0, 0, 0 ) T.除了非基变量13x二x二0外，还有基变量x二0,这样的基本可行解称为退化的基本可行解蜡箱243定义12111 :有基变量取0值的基本可行解，称为退化的基本可行解，它 对应的基B称为退化的可行基.m 个基变量均取正值的基本可行解，称为非退化的基本可行解，对应基 B 称为非退化的可行基.如果一个线性规划问题的所有基本可行解都是非退化的， 则称这个线性规划问题是非退化的.買鲷鴯譖昙膚遙闫撷凄。由以上定义可知，如果约束问题有 m 个基变量，则在退化的基本可行解 中，正分量个数一定小于 m.在基本可行解中去正值的变量一定是基变量 .这样基本可行解中正分量个数 也不会超过 m. 但是上面的例 4已经说明，正分量个数不超过 m 可行解不一定 是基本可行解，还要看可行解中正分量对应的列向量是否线性无关而定.綾镝鯛駕櫬然而基本可行解中正分量对应的系数矩阵的列向量一定线性无关.定理1211设A是mxn矩阵，秩为m,对于Ax=b, x0有：(1 )可行解xo二(xo,xo.xo)t是基本可行解的充要条件是x的分量1 2 n0xo ,xo .xo ，对应 A 中的列向量 p , p .p 线性无关.j1 j2 jkj1 j2jk(2)如果x=(0,0.0)即x=0是可行解，则它一定是基本可行解.证明：(1)必要性.假定xo是基本可行解，由基本可行解定义可知，xo中 的正分量一定是基变量，基变量对应系数矩阵 A 中的列向量一定在基 B 中，则 p ,p .p 线性无关.驅踬髏彦浃绥譎饴憂锦。j1 j2jk充分性假定xo正分量对应A中的列向量线性无关，只要证明xo是基本可行解.因为矩阵A的秩m,则kW m ( k是xo的正分量个数)当k=m时，只要m个线性无关的向量构成一个基，而对应xo中的分量x ,x .x ，取正值的列向量 p ,p .p 线性无关.因此也构成一个基，所以 xo j1 j2 jmj1 j2 jk就是对应于该基的一个非退化的基本可行解.当kvm时，因rank(A)=m现在p ,pp线性无关，可以再从A的其余j1 j2 jk列中找出适当m-k个向量，不妨设p .p使p ,p p p .p线性无关，jk+1jmj1j2jk jk+1jm从 而 构 成 A 的 一 个 基 ， 对应 xo中的基 变 量取值 为 ：xo O.xo o,xo = O.xo = o j1jkjk +1jm因为有取o值的基变量，所以xo是对应于基(p ,p p p.p)的一j1j2jkjk +1jm个退化基本可行基解.(2)因为A的秩为m,所以在A中一定存在m个线性无关的列向量，将 其构成一个B,对应于可行解x=(0,0，。厂中的基变量取0值，所以可行解x=0 是对应于基B的退化的基本可行解锹籁饗迳琐筆襖鸥娅薔。根据这个定理，基本可行解也可以定义如下：定义12.112：设A是mxn矩阵，秩为m,对于Ax=b, x0的可行解x, 如果满足：(1) x的正分量个数小于或等于m(2) 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平行且方向相同.于是有0=X 1当九=0日寸，z=y；九=1日寸，z=x構氽頑黉碩饨荠龈话骛x - y|l当九由0连续变动到1时，点z由y沿此直线连续的变动到x,且因z-y平行 x-y，则有：z y =九(x y)于是有：z x + (1九)y这说明当0X 1时，九x + (1-九)y表示以x，y为端点的直线段上的所有 点，因而它代表以x，y为端点的直线段.一般地，如果x，y是n维欧氏空间Rn中的两点，则有如下定义：定义 12.1.13 ： 如果 x=(x1 x2)T,y=(y1 y2)T 是 Rn 中任意两点， 定义z 九x +(1 九)y，比oj )z(z,z ,.z )T 的点所构成的集合为以 x， y 为端点的线段， 对应 1 2 n九-0,九-1的点x, y叫做这线段的端点，而对应0九 1的点叫做这线段的内点.輒峄陽檉簖疖網儂號泶。定义12114：设R是Rn中的一个点集，(即R Rn )，对于任意两点xG R, yG R以及满足0X 1的实数九，恒有九x + (1-九)y则称R为凸集.尧侧閆繭絳根据以上定义 12.1.12 及 12.1.13 可以看到，凸集的几何意义是：连接凸集 中任意两点的直线段仍在此集合内.识饒鎂錕缢灩筧嚌俨淒。例如实心的圆，实心的矩形，实心的球体，实心的长方体等等均是凸集，圆周不是凸集.直观地看，凸集是没有凹入的部分，其内部没有孔洞 .凍鈹鋨劳臘锴痫(a)(b)(c)(d)图 12.1.3上图中(a)(b)是凸集，而(c)(d)不是凸集.例12.1.5:集合fxI x + x -2x = 5,xe R3是R3中的一个凸集.(可按定义 123证明)例 1216: R = x I 2x + x 4,-x + x 0,x 0,x e R3 是 R2 中的一1 2 1 2 1 2个凸集.例 12.1.7 :( LP ) 问 题max cxs.t , Ax 0的可行域R = IxA 0 xn e证 明 : 设 x1 e R, x 2 e R 由 定 义 知 ， 只 要 证 明 x1, x2 的 任 意 凸 组 合九xi + (1九)x2 e R,0 X 1 即可.因 Ax 0,Ax2 0, VX e0,1有Xxi + (1-X)x2 01AXx1 + (1-X)x2 = XAx1 + (1-X)Ax2 o是 Rns.t, Ax 0中的一个凸集.(证明与例 12.1.7相似)恥諤銪灭萦欢煬鞏鹜錦。定义12.1.16 :设A是m x n矩阵，b是m维列向量，集合 R = x | Ax b, x e Rn 如果R不是凸集，则称R为多面凸集.注：此处b的分量可取负值.一般地，我们可以把任何线性规划问题的条件都写成AX 0写成：AX bf Af b -Ax -b n-Ax-bx 0v-1丿v 0丿因此，（SLP）问题的可行集是一个多面凸集.多面凸集可以有界，亦可无 界.2 x + x 41 2例12.1.8：将下面的约束条件：-x + x 0, x 0121f 4 1f x )110v x 丿201丿v 0丿厂2解：上面的约束条件可以转化为：-10其图如下（1），是一个二维有界的多面凸集.1)(2)图 12.1.4例9. Ax b为f 1-1-1、0丿I x2丿所确定的是V-1丿个无界的多面凸集.如上图2)12.2 线形规划的基本定理12.2.1基本可行解与极点解的等价性定义1221：设集合R匸Rn为凸集，又设x e R但不能为R中其他任意两点 的凸组合，则称x为R的极点（或顶点）. 例如多边形，多面体的顶点，圆周上，球面上的顶点等都是顶点.上面我们已经说（SLP）的可行域是由直线，平面或超平面为边界构成的 凸多边形或凸多面体（亦即多面凸集）因此线形规划问题可行域的顶点就是极 点.硕癘鄴颃诌攆檸攜驤蔹。定理12.2.1 x是线形规划（SLP）可行域R的极点的充要条件是x是基本 可行解.证明：必要性设x是可行域的极点，要证明x是基本可行解若x=0是可行 域的极点则x=0是可行解，由上节定理12.1.1中(2)即知x是基本可行解阌擻若xHO是可行域的极点，设x的正分量x x .x要证明x是基本可行 j1 j 2jk解， 由上节的定理 12.1.1 知， 只需证明这些数分量对应 A 中的列向量p p p 线形无关.氬嚕躑竄贸恳彈瀘颔澩。j1 j 2jk利用反证法：若p p . p线性相关，则存在不全为0得数rr .r j1 j 2jk 1 2 k使得 r p + r p +. + r p = 01 j12 j 2k jk现在构造一个n维列向量y，它的第j jj分量分别为rrr，其余1 2 k 1 2 k分量为 0，则有 yH0.且 Ay= y p + y p +. + y p =0 由于 3y H0. (1WiW 1 j12 j 2k jkik)，x + 9 y三0因而x9 y是两个可行解.分别记取min ；舌丰01可见且11x = -(x + 9 y) + -(x 9 y)1i 0.y丰0.故x,丰x”,x丰x,x丰x”取1X =,则x = Xx, + (1-九)x,这表明：x可以表示成R中其它点的凸组合.这与x是 R 的极点相矛盾.故必要性得证.怂阐譜鯪迳導嘯畫長凉。充分性：设x是(SLP)的基本可行解要证x是可行域的极点若x=0是基 本可行解，而存在可行域中的点，使x=0能表成：谚辞調担鈧谄动禪泻類 Xx1 + (1X)x2,x1 e R,x2 e R.X e 0,1的形式.即 Xx 1 + (1 X)x2 =0 因此x1 0,x2 0,X0,1 X0，表明x=0不能表成可行域中两点的凸组合，因此是极点.若xH0是基本可行解.由定理1知，x的正分量x x x，对应A中列 j1 j 2jk向量p pp线形无关.嘰觐詿缧铴嗫偽純铪锩。j1 j 2jk反证法：若基本可行解x不是可行域的极点则可行域中存在异于x的不同 两点设为y和z.x = X y + (1X) z.(0 X 0,1 X 0, y 0, z 0 故jjjjy = z = 0,( j丰j jj )因而y与z是可行解，应满足j j1 2kAy = y p + y p +y p = bj1 j1j2 j 2jk jk 两式相减得Az = z p + z p +z p = bj1 j1j 2 j2jk jkj2-zj2)2 +因 为 y 与 z 是不相同的两点.他们的分量至少有一个不相等.即y - z (i = 1 k)ji ji不全为0.因此p p .p线性相关.这与x是基本可行解相矛盾.故x是基 j1j 2jk本可行解.则必为可行域的顶点.12.2.2基本定理定理12.2.2假定线性规划（SLP）的A是mXn的矩阵.秩为m,且A的列 向量 p p p1 2 n均不是零向量.（1）若有可行解,则必有基本可行解（即非空可行集 R 必有极点） .（ 2）若有最优解,则目标函数必定在基本可行解上（极点）达到极值 . （即若有最优解,则必有基本最优解） .（3）若目标函数在多于一个极点上达到最优,则必在这些极点的凸组合上 达到最优.证明：（1）设有可行解 x0 = （x0, x0,x0）T1 2 n若xo =0，则由定理12.1.1 （2）知xo就是基本可行解.若xo H0,不妨设xo的正分量为前k个.xo 0xo 0 xo 012k而xo = 0, xo = 0，如果正分量对应A中列向量p p p线性无关，则k+1n1 2k由定理12.1.1 （1）知xo就是基本可行解.如果正分量A中的列向量p p .p线12k性相关，有定理 12.1.1（1）知 p p p 不是基本可行解.（下面的证明思想就12k是构造比xo正分量要少的新可行解x1，考虑x1是不是基本可行解.）鶼渍螻偉阅劍鲰由 于 p p p 线性相 关， 于是存在不全为零的 数 y,y y 使得12k12ky p + y p +y p = 不妨设至少有一个y 0（1 i 0(1 i k)则可取纣忧蔣氳頑莶驅藥悯骛1122k kimin1i0x0 0(1 l 0,1 i k .若正分量对应A中的列12 ki向量线性无关，则就是基本可行解（定理12.1.1（1），取x0即得到基本最优 解x* = x0.若正分量对应A中的列向量p p .p线性相关，则存在不全为零的数1 2 ky y .y使y p + y p + y p = 0 .构造n维列向量y使其第1，2，k分1 2 k 1 12 2k k量分别为0，而其余分量为0，则有yH0且Ay = y p + y p +y p = 0取1 12 2k kI x 0min =x0o(i i 0 且 x + 0 y 0.A(x 0 y) = b 艮卩 x + 0 y 和x-0 y是两个可行解，分别记为x,及x”.銚銻縵哜鳗鸿锓謎諏涼。它们的目标函数值分别为cx,二cxo +0 cy cx”二cxo -0 cy因为xo是最优解，所以： cxo - cx, = -0 cy 0， cxo - cx” =0 cy 0又因为00，故cy = 0于是有cx, = ex” = cxo。这表明x,及x”均为最优解.又由0的取法知xo -0 |yj = 0, y丰0,1 i k当y0时xo -0y = 0,这时x, = xo -0 y中第1分量等于0，当y 0时这时 iiiixo +0y = 0中第1分量等于0.所以x,x,至少有一个的正分量个数比xo的正分量 ii个数要少，记这个解为xi .那么xi也是最优解.可见，如果xo不是基本最优解， 即xo的正分量对应A中的列向量线性相关，那么总可以令一个最优解xi，其正 分量个数比xo正分量个数少.如果xi是基本最优解，即xi的正分量对应A中的 列向量线性无关，挤貼綬电麥结鈺贖哓类。则取 x* = xi , 即证明 i2.2.i(2).如果xi的正分量对应A中的列向量线性相关，则可重复上述步骤，得到最优解x2x3xq 经过有限步必达到下面的三种情形之一：(i) xq的正分量对应A中的列向量线性无关，因此xq是基本可行解.取 x* = xq 即为基本最优解.(ii) xq只有唯一的一个正分量，因A的列向量均为非零故xq的正分量对 应A中的列向量线性无关.同(I) 一样可知x* = xq即为基本最优解.赔荊紳谘侖驟辽輩(iii) xq =0这时xq =0是可行解.由上面的证明已知x* = xq =0就是基本最优 解.到此，我们证明了定理的第(2)部分.（3）假定目标函数在极点X1X2X3XS上达到最优值f *又设它们的任意凸组合为：x =工九xi,工九=1,0X 1,1 i 0 iiii=1i=1i=1故知xix2xs的凸组合也是目标函数的最优值点.至此，我们全面证明了定理 12.2.2.上面，定理 12.2.1，定理 12.2.2 是线性规划的两个很重要的定理.证明了线 性规划的基本可行解等同于可行域的顶点.并且，如果线性规划有最优解，则必 在可行域的顶点上达到最优.塤礙籟馐决穩賽釙冊庫。这样，一个有最优解的（SLP ）问题，是一定可以从可行域的极点中（即 基本可行解中）求得最优解的.而基本可行解是对应A中的m个线性无关的列向量.A只有n个列向量.从n个列向量中取出m个线性无关向量相成的向量组.其数目上有限的.因此基本可行解的数量也是有限的.它不会超过：Cmnn! 个 （n 一 m）! m!我们后面要学习的单纯形方法就是根据这一基本定理在有限个基本可行解 中寻找基本最优解.另外，定理 12.2.2 还告诉我们，若目标函数在多于一个极点 上达到最优，则在这些极点的凸组合上也达到最优.仓嫗盤紲嘱珑詁鍬齊驁。（1.2）M4（0.1），其目标1函数值分别为f=0 f2=2 f3=2 f4=-在MM2的凸组合上（即在线段MM2上）也21达到最优事实上，可以用图解法来说明这一点因目标函数等值线xz+ -x2=2与1 2 2可行域的边MM重合，该直线段上的点对应目标函数值均有f=2.绽萬璉轆娛閬蛏鬮23推论12.3.3：若（SLP）的可行域R是有界的，则xGR的充要条件是x能 表成X1X2.Xr的凸组合.即：X =工九Xi,九 0,工九=1i iii=1i=1定理12.3.4:若线形规划（SLP）的可行域R非空有界，则必有最优解.证明：设X1 X2.Xr是R的全部极点，由上面推论知：Vx G R可表成极点的凸组合：x =工九 xi 0,工 X = 1iii=1i=1cx =工九Cxi 令f * =max Ji = cxe,1 e r 于是 i=i 1ir其目标函数值为cx W 工九 f * = f *ii=1此式表明：任意可行解处目标函数的值均不超过极点xe处的目标值f *故极点xe即为最优解.这个定理表明：（SLP）的可行域R中非空有界，则必有最优解，或唯一，或多个（在极点及凸组合上）而不可能是有可行解而无最优解的情形 .骁顾燁习题 121. 证明下面两个线性规划问题等价。（1） max z =cx （2） max z =cxs.t.b Ax b12 s. 0Ax + x = ba2x 0,x 0a2. 在数学规划问题中，目标函数为分式函数，且约束条件中的函数是线性的，则称此问题为分式规划.现考虑如下分式规划问题昇、10 x + 20 x +10 max f x =+23x + 4 x + 2012x + 3x 501 2s.t 3x + 2x 0, x 012将以上规划转化为等价的线性规划问题.3. 设有两个线性规划问题(1) max z = cx (2) max z =ucxI Ax = bI Ax = X bs.t s.t 0 丨x 0其中，u , X为正实数，两个问题中的A , c , b相同，现问若第一个问题有 最优解，第二个问题是否有最优解？若有，那么两个问题的最优解之间有什么 关系?鎦诗涇艳损楼紲鯗餳類。