《线性规划的基本概念与基本定理》由会员分享，可在线阅读，更多相关《线性规划的基本概念与基本定理（17页珍藏版）》请在金锄头文库上搜索。
1、第十二章 线性规划的基本概念和基本定理12.1 线性规划的基本概念12.1.1可行解，可行域定义 12.1.1：称满足全部约束条件的向量为可行解或可行点.maxf 二CZ 例如：SLPf AZ 二 bs.t 0如果Z0满足这些约束，即AZ0 = b且Z0 0，则Z0就是SLP的可行解.定义 12.1.2：称所有可行解（点）构成的集合为可行集或可行域.也称为可 行解集.例如：上面SLP的可行域为R二AZ二b,Z 0定义 12.1.3：若一个线性规划问题的可行集为空集时，则称这一线性规划 无可行解.这时线性规划的约束条件不相容.矚慫润厲钐瘗睞枥庑赖。由上一章的分析可以看到：一个线性规划的可行解集可
2、以是空集，有界非空 集和无界非空集.12.1.2最优解，无界解定义 12.1.4：称使目标函数值达到最优值的可行解为线性规划问题的最优 解定义 12.1.5：对于极大化目标函数的标准线性规划问题，定义其无界解如下：对于任何给定的正数 M，存在可行解X满足AX二b, X 0，使CX M .那么称该线性规划问题有无界解.聞創沟燴鐺險爱氇谴净。由定义可知，无界解的意思是：若是极大化目标函数，则在可行域上目标函 数值无上界；若是极小化目标函数，则在可行域上目标函数值无下界 .那么，有图 12.1.1解：问题的可行域是上图所示的无界凸多边形区域，在此无界可行域上，目 标函数值无上界，所以这个线性规划问题
3、有无界解.酽锕极額閉镇桧猪訣锥。x 一 x 1例 12.1.2 max f 二 x x12st1 2v x + x 0, x 012解：此问题的可行域如上图，是一个无界的多边形.但极大化目标函数却以1 为上界.因此这个线性规划问题没有无界解，而且事实上，此问题目标函数最优 值max f=1在可行域射线x x二1上均可达到.1212.1.3. 基本可行解定义1216：对于约束条件Ax=b,设A是秩m的mxn矩阵，用(P , j=1 n)j表示 A 的第 j 列向量.即 A=( p p ).由 A 的 m 个列向量构成的 m 阶方阵 1nB=( p , p .p )謀荞抟箧飆鐸怼类蒋薔。 j1 j
4、2jm若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变量.p5(0 r 1r 1 0是线性无关，因此x x x 是一组基.而p =1,p =11J34510 J22 J，不在这x + x + x = 5123
5、. x + x + x = 2例12.1.3求xx满足V 124使f = 2x + x156x+ 2 x + x=2112125x 0,i =1 i5r 11100、r100解： A =11010则 B =010的列是线性无关的， 即62001丿001丿个基中，所以x ,x为非基变量.12定义1218 :设Ax=b, x0 个基B =(p .p)，其对应的基变量构j1 j m成的m维列向量记为x = (x .x )t这时若全非基变量等0则Ax=b n Bx二b,Bj1 jmB得唯一解x = B-ib .记为B-i b = (b. b t)于是得到方程组Ax=b的一个解B1 m=b ,x =b
6、.x=bij 22jmm非基变量x = 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， B 则称它为满足约束 Ax=b, xo 的基本可行解.預頌圣鉉儐歲龈讶骅籴。对应地称B为可行基，因SLP中具有此约束条件.也通常 称为SLP的基本 可行解.定义 12.1.10：使目标函数达到最优值的基本可行解，称为基本最优
7、值.例12.1.4：(SLP)如例12.1.3,试找一个基本可行解.1 1 0、解：B =-100是其一个基矩阵.p , p , p是一个基.则x ,x ,x为基变13513516 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 值；它是可行解，则
8、 m 个基变量取非负值，从而 基本可行解正分量是个数不超过m.铙誅卧泻噦圣骋贶頂廡。那么满足Ax=b,x 0的正分量个数不超过m的可行解.Rank(A ) = m是否一 mxn 定是基本可行解呢？我们举例说明这个问题.x + x + x = 4123例 12.1.5.已知约束条件为： 0, x 0, x 0, x 0它有正分量个数等于m(m=2)的可行解.x二3, x二1, x二0, x二0但它不1234是基本可行解.证明：(反证法)假设可行解x=(3,1,0,0)T面约束的基本可行解因为基本可行 解中非基变量取0 值，基变量取非负值.擁締凤袜备訊顎轮烂蔷。在这个可行解中x ,x非零正值，因此
9、x ,x不可能是非基变量，只能是基变1 2 1 2量.按定义，基变量对应的系数矩阵中的列向量p ,p应构成一个基矩阵B.但这12里p ,p是线性相关的(p = p ),这与B是基矩阵矛盾.故知x=(2丄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,
10、可行解(3, 1, 0, 0)t用x,x表示为图上点(3, 1). 12由图可见这不是可行域的顶点.而我们今天将证明基本可行解是可行域的顶点.而 在例中p ,p线性无关，所以B=( p ,p )是一个基矩阵，对应的基本解为(4, 0,1 2 1 20，0)T用坐标x ,x表示则为平面上的点(4, 0),是上图可行域的顶点.对于这12个基B=(p ,p )的基本可行解(4, 0, 0, 0)T .除了非基变量x二x二0夕卜，还1324有基变量x二0，这样的基本可行解称为退化的基本可行解蜡變黲癟報伥铉锚鈰赘3定义 12.1.11：有基变量取 0 值的基本可行解,称为退化的基本可行解,它对应的基B称
11、为退化的可行基.m 个基变量均取正值的基本可行解，称为非退化的基本可行解，对应基 B 称为非退化的可行基.如果一个线性规划问题的所有基本可行解都是非退化的， 则称这个线性规划问题是非退化的.買鲷鴯譖昙膚遙闫撷凄。由以上定义可知，如果约束问题有 m 个基变量，则在退化的基本可行解中， 正分量个数一定小于 m.在基本可行解中去正值的变量一定是基变量 .这样基本可行解中正分量个数 也不会超过 m. 但是上面的例 4 已经说明，正分量个数不超过 m 可行解不一定 是基本可行解，还要看可行解中正分量对应的列向量是否线性无关而定.綾镝鯛駕櫬然而基本可行解中正分量对应的系数矩阵的列向量一定线性无关.定理12
12、.1.1设A是mxn矩阵，秩为m,对于Ax=b, x三0有：(1 )可行解x0二(x0,x Q.x )t是基本可行解的充要条件是x的分量1 2 n0x0 , x0 .x0 ，对应 A 中的列向量 p , p . p 线性无关.j1 j2 jkj1 j2 jk(2)如果x=(O,O.0)即x=Q是可行解，则它一定是基本可行解.证明：(1)必要性假定xq是基本可行解，由基本可行解定义可知，xq中的 正分量一定是基变量，基变量对应系数矩阵 A 中的列向量一定在基 B 中，则 p , p .p 线性无关.驅踬髏彦浃绥譎饴憂锦。j1 j2 jk充分性假定xq正分量对应A中的列向量线性无关，只要证明xq是
13、基本可行解.因为矩阵A的秩m,则kW m ( k是xq的正分量个数)当k=m时，只要m个线性无关的向量构成一个基，而对应xQ中的分量x ,x .x ，取正值的列向量p ,p .p线性无关.因此也构成一个基，所以xQ就 j1 j2 jmj1 j2 jk是对应于该基的一个非退化的基本可行解.当kvm时，因rank(A)=m现在p , p .p线性无关，可以再从A的其余列 j1 j2 jk中找出适当m-k个向量，不妨设p .p使p , p .p p .p线性无关，从而jk+1 jmj1 j2 jk jk+1 jm构成A的一个基，对应xq中的基变量取值为：xq Q.xq Q,xq = Q.xo = Q猫虿j1jkjk +1jm因为有取Q值的基变量，所以xq是对应于基(p ,p .p p .p )的 j1 j2 jk jk +1jm一个退化基本可行基解.(2)因为A的秩为m ,所以在A中一定存在m个线性无关的列向量，将 其构成一个B,对应于可行解x=(Q,Q，Q)T中的基变量取0值，所以可行解x=Q 是对应于基 B 的退化的基本可行解.锹籁饗迳琐筆襖鸥娅薔。根据这个定理，基本可行解也可以定义如下：定义12.112：设A是mxn矩阵，秩为m,对于Ax=b, x0的可行解
