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

1、第十二章线性规划的基本概念和基本定理12.1线性规划的基本概念可行解，可行域定义:称满足全部约束条件的向量为可行解或可行点m axf = CZ例如：SLP'AZ=bs.t Z _0L如果Z0满足这些约束，即AZ°=b且z0 _ 0,则Z0就是SLP的可行解.定义12.1.2 :称所有可行解(点)构成的集合为可行集或可行域也称为可行解集例如：上面 SLP的可行域为R二AZ二b,Z _0定义 12.1.3 :若一个线性规划问题的可行集为空集时，则称这一线性规划无可行解.这时线性规划的约束条件不相容.矚慫润厲钐瘗睞枥庑赖。由上一章的分析可以看到：一个线性规划的可行解集可以是空集，

2、有界非空 集和无界非空集.最优解，无界解定义12.1.4 :称使目标函数值达到最优值的可行解为线性规划问题的最优 解定义12.1.5 :对于极大化目标函数的标准线性规划问题，定义其无界解如下：对于任何给定的正数M，存在可行解 X满足AX二b, X 一 0，使CX M .聞創沟燴鐺險爱氇谴净。无界解的意思是：若是极大化目标函数， 极小化目标函数，则在可行域上目标函数值无下界则在可行域上目标函.那么，有.残骛楼諍锩瀨濟溆塹籟。那么称该线性规划问题有无界解 由定义可知，数值无上界；若是 无界解的线性规划问题一定没有最优解例考虑线性规划问题：max(X| x2)X| -血-1st二-x1 x2 玄 1

3、为 _ 0, x2 _ 0图 解：问题的可行域是上图所示的无界凸多边形区域，在此无界可行域上，目标函数值无上界，所以这个线性规划问题有无界解 .酽锕极額閉镇桧猪訣锥。X"i i X2 1I例 12.1.2 max f =咅一x2st -x- +x2 <1x 0, x2 亠0解：此问题的可行域如上图，是一个无界的多边形.但极大化目标函数却以1 为上界.因此这个线性规划问题没有无界解，而且事实上，此问题目标函数最优 值max f=1在可行域射线x, -x2 =1上均可达到.彈贸摄尔霁毙攬砖卤庑。12.1.3.基本可行解定义12.1.6 :对于约束条件Ax=b，设A是秩m的mx n矩

4、阵，用(片，j=1 n)表示A的第j列向量.即A=(p1.pn).由A的m个列向量构成的m阶方阵B=( pj , pj .pj )謀养抟箧飆鐸怼类蒋薔。若B是非奇异的，即detBO,则称B为一个基或称为一个基矩阵.因为SLP问题中含有约束条件 Ax=b，因此也通常称B为线性规划SLP的 一个基.由上面定义可知，B中m个列向量是线性无关的，并且它是 A的列向量组 的一个最大无关组.按定义，A中m个列向量，只要是线性无关的就可以构成一个基 .定义12.1.7 :若变量对应A中列向量pj包含在基B中，则称为B的 基变量；若变量兀对应A中的列向量pk不包含在基B中，则称兀为B中的非基 变量.厦礴恳蹒骈

5、時盡继價骚。为 + x2 + x3 = 5使 f = 2x, x2例 12.1.3 求 X1X5 满足 J 一NF+xr-2'1 110 0'1A =-110 10则B =0(6 2 0 0 1,<0x - 0,i = 1 5解：156治+2x2+x5 =210 010的列是线性无关的，即0 10 'p5 = 0是线性无关，因此x3 x4(1、组基.而p1 =-1,P2 =1丿a.)x?是，不在这个基中，所以X1,X2为非基变量.定义12.1.8 :设Ax=b, x>0 一个基B = (pj1.pjm )，其对应的基变量构成的m维列向量记为XB=(Xji.X

6、jm)T这时若全非基变量等0,则Ax=b = Bxb二b, 得唯一解Xb =BJb .记为Bb = ( b. bT)于是得到方程组Ax=b的一个解 Xji - b1, Xj2 = b2 Xjm = bm,非基变量Xj =0,( j =1,2.n, i Hjjm)称之为对应于基B的基本解这个定义也告诉 我们怎样找一个基本解)茕桢广鳓鯡选块网羈泪。女如:上面例12.1.2 中，非基变量Xi=X2=0.则可得Xs =5,X4=4,Xs=21.所以x0 =(0,0,5, -2,21)是对应于基B的一个基本解，但由于x4 =-2<0.不能满足约 束条件，所以这个基本解不是原问题的可行解 .(为什么

7、？)鹅娅尽損鹤惨歷茏鴛賴。这是因为，按照定义，基本解中的 n-m个非基变量必须取0值只有m 个基变量取值才可能不等于0.但可以取负值.因此基本解不一定满足SLP的非负 要求.籟丛妈羥为贍债蛏练淨。定义12.1.9 :对应于基B的基本解，若基变量取非负值，即xB = B_ b , b>0， 则称它为满足约束 Ax=b, x>o的基本可行解.預頌圣鉉儐歲龈讶骅籴。对应地称B为可行基，因SLP中具有此约束条件.也通常 称为SLP的基本 可行解.定义12.1.10:使目标函数达到最优值的基本可行解，称为基本最优值.例：(SLP)如例,试找一个基本可行解. 10、解：B = -1 0 0是其

8、一个基矩阵.p-j, p3, p5是一个基.则x1,x3,x5为基变<6 0 b量.x2, x 为非基变量.令 X2 “4 =0.得 X1 = 2, X3 = 3, X5 =9.故 x, = (2,0,3,0,9)是 原问题的一个基本可行解，B1为基可行基.渗釤呛俨匀谔鱉调硯錦。上面我们讲到基本解中有n-m个分量必须取零值，而只有m个基变量取非 零值.而基本可行解，它一方面是基本解，另一方面又是可行解，因为它是基本 解，所以n-m个非基变量取0值；它是可行解，则 m个基变量取非负值，从而 基本可行解正分量是个数不超过 m.铙誅卧泻噦圣骋贶頂廡。那么满足Ax=b,x -0的正分量个数不超过

9、 m的可行解.Rank(An n)二m是否一 定是基本可行解呢？我们举例说明这个问题.X1 X2 X3 = 4例已知约束条件为：2x1 2x2 x4 =8为 - 0, x2 - 0, x3 - 0,x4 - 0它有正分量个数等于m(m=2)的可行解.为=3, x2 =1, x3 =0,X4 =0但它不是基本可行解.证明：(反证法)假设可行解x=(3,1,0,0)T面约束的基本可行解.因为基本可行 解中非基变量取0值，基变量取非负值.擁締凤袜备訊顎轮烂蔷。在这个可行解中X!,X2非零正值，因此X,X2不可能是非基变量，只能是基变 量.按定义，基变量对应的系数矩阵中的列向量 pp2应构成一个基矩阵

10、B.但这 里Pl, P2是线性相关的(Pi = P2),这与B是基矩阵矛盾.故知X=(2,1,0,0)T是基可 行解 .贓熱俣阃歲匱阊邺镓騷。由此例可见，虽然可行解(3, 1, 0, 0)T正分量个数不超过m,但它的正 分量对应的列向量线性无关，不能与一基矩阵相联系，所以它不是一个基本可行 解 .坛搏乡囂忏蒌鍥铃氈淚。现在我们把例中松弛变量x3,x4去掉，约束变为x1 x2 _ 42x1 2x2 _8禺=0,x2亠0其可行域如图，可行解(3，1, 0, 0) T用x1,x2表示为图上点(3，1). 由图可见这不是可行域的顶点.而我们今天将证明基本可行解是可行域的顶点.而 在例中口，卩2线性无关

11、，所以B=( SP2)是一个基矩阵，对应的基本解为(4,0, 0, 0) T用坐标X1,X2表示则为平面上的点(4, 0),是上图可行域的顶点.对于这 个基B=(Pi,P3)的基本可行解(4, 0, 0, 0) T .除了非基变量X2=X4=0夕卜，还 有基变量x3=0,这样的基本可行解称为 退化的基本可行解.蜡變黲癟報伥铉锚鈰赘。定义12.1.11 :有基变量取0值的基本可行解，称为退化的基本可行解，它 对应的基B称为退化的可行基.m个基变量均取正值的基本可行解，称为非退化的基本可行解，对应基B称为非退化的可行基如果一个线性规划问题的所有基本可行解都是非退化的， 则称这个线性规划问题是非退化

12、的.買鯛鴯譖昙膚遙闫撷凄。由以上定义可知，如果约束问题有m个基变量，则在退化的基本可行解中， 正分量个数一定小于m.在基本可行解中去正值的变量一定是基变量.这样基本可行解中正分量个数也不会超过m.但是上面的例4已经说明，正分量个数不超过m可行解不一定是基本可行解，还要看可行解中正分量对应的列向量是否线性无关而定.綾镝鯛駕櫬鹕踪韦辚糴。然而基本可行解中正分量对应的系数矩阵的列向量一定线性无关.定理设A是mXn矩阵，秩为 m,对于Ax=b, x > 0有：(1) 可行解x(x1°,x2°.xn0T是基本可行解的充要条件是Xo的分量x；,x02.xj，对应A中的列向量PjP

13、j2.Pjk线性无关.(2) 如果x=(0,0.0)即x=0是可行解，则它一定是基本可行解.证明：(1)必要性.假定x0是基本可行解，由基本可行解定义可知， x0中的 正分量一定是基变量，基变量对应系数矩阵 A中的列向量一定在基 B中，则 Pji, Pj2 .pjk线性无关.驅踬髏彦浃绥譎饴憂锦。充分性.假定x0正分量对应A中的列向量线性无关，只要证明x0是基本可行 解.因为矩阵A的秩m，贝U k<m ( k是x0的正分量个数)当k=m时，只要m个线性无关的向量构成一个基，而对应 x0中的分量xh ,xj2.xjm，取正值的列向量PjPj2. Pjk线性无关.因此也构成一个基，所以x0就

14、 是对应于该基的一个非退化的基本可行解.当k<m时，因rank(A)=m现在, Pj2 .Pjk线性无关，可以再从A的其余列中找出适当m-k个向量，不妨设卩了卩人使P, Pj2.P Pjki.Pjm线性无关，从而 构成A的一个基，对应x0中的基变量取值为：X； 0.x0k 0,x0 =0.x：m =0猫虿 驢绘燈鮒诛髅貺庑。因为有取0值的基变量，所以x0是对应于基(PjPj2.Pjk Pjk+.Pjm)的 一个退化基本可行基解.(2)因为A的秩为m ,所以在A中一定存在m个线性无关的列向量，将 其构成一个B,对应于可行解x=(0,0，0)T中的基变量取0值，所以可行解 x=0 是对应于基

15、B的退化的基本可行解.锹籁饗迳琐筆襖鸥娅薔。根据这个定理，基本可行解也可以定义如下：定义:设A是mKn矩阵，秩为 m,对于Ax=b, x >0的可行解x, 如果满足：(1) x的正分量个数小于或等于 m(2) x的正分量对应 A中的列向量线性无关.则称x是一个基本可行解.若x=0是可行解，则定义它是一个基本可行解.注：定义与定义的等价性可由定义推出.12.1.4 凸集我们先考察二维平面上直线段上任意一点的表示形式取x.y为平面上两点，用以原点为起点的向量来表示x和y. 并设z是线段xy上任意一点，得向量z-y.它与向量x-y平行且方向相同.Hz y|于是有0兰 !=丸兰1当九=0时，z=

16、y;人=1时，z=x構氽頑黉碩饨荠龈话骛。k-y|当由0连续变动到1时，点z由y沿此直线连续的变动到x，且因z-y平行 x-y，则有:z-yY.(x-y)于是有：zVx (1-Jy这说明当0岂 <1时， x (1 - )y表示以x, y为端点的直线段上的所有点， 因而它代表以x，y为端点的直线段.一般地，如果x，y是n维欧氏空间Rn中的两点，则有如下定义：定义12.1.13 :如果x=(X1x2)T,y=(y1yj 是Rn中任意两点，定义 z = x (1 - )y,C；三 0,1)Z =,Z2,.Zn)T的点所构成的集合为以x，y为端点的线段，对应欧0A的点x, y叫做这线段的端点，而

17、对应0；：' ：1的点叫做这线段的内点.輒峄陽檉簖疖 網儂號泶。定义：设R是Rn中的一个点集，(即RRn )，对于任意两点xR, r R以及满足0汨的实数恒有-x ( )y 则称R为凸集.尧侧閆繭絳闕绚勵蜆贅。根据以上定义及可以看到，凸集的几何意义是：连接凸集中 任意两点的直线段仍在此集合内.识饒鎂錕缢灩筧嚌俨淒。例如实心的圆，实心的矩形，实心的球体，实心的长方体等等均是凸集，圆 周不是凸集.直观地看，凸集是没有凹入的部分，其内部没有孔洞.凍鈹鋨劳臘错痫婦胫籴。（a）（b）（d）图 上图中(a)(b)是凸集，而(c)(d)不是凸集.例12.1.5:集合1x|xi X2-2x3 =5,

18、X，R3是R3中的一个凸集.(可按定义证明）例 :R =x | 2x!- x2乞 4, -捲x2空 5必 _ 0, x2_ 0, x R3是 R2中的一个凸集.imax cx例 12.1.7: （LP）问题：的可行域 R .x|Axb,x_0,x R,s.t. Ax 兰 b,xK0证明：设x1 R,x2 R由定义知，只要证明x1, x2的任意凸组合X1（1- ）x2R,0 乞 <1 即可.因_ b,x1 _0,Ax2 _b,x2 _0, -0,1】有'x1 （1 -，）x2 _ 0Af. x1 （1 -，）x2 Ax1 （1 -，）Ax2 b （1 -，）b 二 b可见 x1(

19、- )x R故知R是凸集.注：可以用归纳法证明：如果 R是凸集，则R中任意有限个点的凸组合均 在R中.frm a xx定理: (SLP)问题的可行集R =x| Ax b x 0、s.t ,Ax 兰 b x A 0是Rn中的一个凸集.(证明与例相似)恥諤銪灭萦欢煬鞏鹜錦。定义：设A是m n矩阵，b是m维列向量，集合Rx|Ax",xRn ?如果R不是凸集，则称R为多面凸集.鯊腎鑰诎漣鉀沩懼統庫。注：此处b的分量可取负值.一般地，我们可以把任何线性规划问题的条件都写成AX乞b的形式.例如：约束条件为AX二b,X _0写成：AX 兰 b，Z A '% _Ax 兰-b =-Ax<

20、-b、x兰 0因此，(SLP)问题的可行集是一个多面凸集.多面凸集可以有界，亦可无界2为 x2乞4|例:将下面的约束条件：x, x 1写成Axv=b的形式.论 _ 0,x2 _ 0解：上面的约束条件可以转化为:广21A-11<1:101X2丿03b0其图如下（1），是一个二维有界的多面凸集(1)(2)图 （1 _1f 0、.如上图例9.AxEb为丙“所确定的是一个无界的多面凸集（一10八x2丿-1丿（2）12.2线形规划的基本定理基本可行解与极点解的等价性定义：设集合R Rn为凸集，又设R但不能为R中其他任意两点 的凸组合，则称x为R的极点（或顶点）.例如多边形，多面体的顶点，圆周上，球

21、面上的顶点等都是顶点上面我们已经说（SLP）的可行域是由直线，平面或超平面为边界构成的凸多边形或凸多面体（亦即多面凸集）因此线形规划问题可行域的顶点就是极点硕癘鄴颃诌攆檸攜驤蔹。定理12.2.1 x是线形规划（SLP）可行域R的极点的充要条件是x是基本 可行解.证明：必要性.设x是可行域的极点，要证明x是基本可行解.若x=0是可行 域的极点则x=0是可行解，由上节定理中（2）即知x是基本可行解周擻 輳嬪諫迁择植秘騖。若x工0是可行域的极点，设x的正分量XjMj2$要证明x是基本可行解，由上节的定理知，只需证明这些数分量对应 A中的列向量pj1pj2卩氷线形无关.氬嚕躑竄贸恳彈濾颔澩。利用反证法

22、：若Pj1pj2.Pjk线性相关，则存在不全为0得数rr2rk使得 APj1 DPj2 . rkPjk =0现在构造一个n维列向量y，它的第j1 j2jk分量分别为r1r2rk，其余分量为0，则有y工0.且Ay= 丫仙-y?Pj2 - yk Pjk =0由于Ty工0. （K i< k）,釷鹆資贏車贖孙滅獅赘。min丿片M式0【可见且x +Ty>0因而x士日y是两个可行解.分别记为: iiyilJx，二 x vy R， x = x - 丁y R 有:1 1八 2（xF 2（1»）解x不是可行域的极点.则可行域中因v .0.y=0.故x，= X，,x = x，,x = X，取

23、1=-，则x = 'X， (1-%)x，这表明：x可以表示成R中其它点的凸组合.这与x 2是R的极点相矛盾.故必要性得证.怂阐譜鯪迳導嘯畫長凉。充分性：设x是(SLP)的基本可行解.要证x是可行域的极点.若x=0是基 本可行解，而存在可行域中的点，使 x=0能表成：谚辞調担鈧谄动禪泻類。 x1 (')x2，x R，x2 R. “0，11 的形式.即，x1 (1_'；)x2 =0 因此X1 _0，X2 _0_0,1-，0，表明x=0不能表成可行域中两点的凸组合，因此是极点若x工0是基本可行解.由定理1知，x的正分量Xj1Xj2.Xjk，对应A中列向量Pj1 Pj2pjk线

24、形无关.嘰觐詿缧铴嗫偽純铪锩。反证法：若基本可行解X不是可行域的极点.则可行域中存在异于X的不同 两点设为y和乙x 二 y (1 -%)z.(0 ： ：1)或 xyj (1)Zj.(j =1 n)时 x j =0 所以上式变 为：0 二yj （1 J；）Zj 而 0,1； 0,yj -0, Zj -0 故 y二 Zj =0,（j = jjj k）因而y与z是可行解，应满足 熒绐譏钲鏌觶鷹緇機库AYj1Pj1Yj2Pj2Az 二 Zj1Pj1 - Zj2Pj2 .yjk Pik 二 bj 两式相减得Zjk Pjk二 b山1 一引）Pj（yj2 Zj2）Pj2 . （yjk 一 ZjQ Pjk =

25、0因为y与z是不相同的两点他们的分量至少有一个不相等.即 比匚一召（=1 k）不全为0因此pj1 sPjk线性相关这与x是基本可行解相矛盾.故x是基本 可行解.则必为可行域的顶点.基本定理定理1222假定线性规划（SLP）的A是mx n的矩阵.秩为m,且A的列向量P1P2Pn均不是零向量（1） 若有可行解，则必有基本可行解（即非空可行集R必有极点）（2） 若有最优解，则目标函数必定在基本可行解上（极点）达到极值.（即 若有最优解，则必有基本最优解）（3）若目标函数在多于一个极点上达到最优，则必在这些极点的凸组合上 达到最优.证明：（1）设有可行解X0 =（x0，x0,x0）T若x0 =0，则由

26、定理12.1.1 （2）知x0就是基本可行解.若x0工0，不妨设x0的正分量为前k个.x0 0x2 0.x0 0而x0t=O,£=0，如果正分量对应 A中列向量P1P2Pk线性无关，则由定理12.1.1 （1）知x0就是基本可行解.如果正分量A中的列向量P2Pk线 性相关，有定理12.1.1 （1）知pp2Pk不是基本可行解.（下面的证明思想就是 构造比x0正分量要少的新可行解x1，考虑x1是不是基本可行解.）鶼渍螻偉阅劍鲰腎邏 蘞。由于P1P2Pk线性相关，于是存在不全为零的数yk使得% py P 2yk P 不妨设至少有一个yi0 （1 i - k ,）否则可取 -P1-y2P2

27、-ykPk =0 构造 n 维列向量 y =(y1,y2.yk,0,.0)T ,则知a y1 p< y p 2 yk pk = 因）为存在yi - o（1乞i込k）则可取纣忧蔣氳頑莶驅藥悯骛。minX。0匚 0(1乞I乞k).Jyi可见x° -阳是可行解.它的第I个分量x0 - v y0 = 0 ,令X = X - V y = （x - V y| ,.x J - T y|,0, x 1 - V y| 1,xk - V yk 这样得出一个正分量是个数比x°少的可行解x1，它除了后面的n-k个分量等于°外，前面k个分量中的第I个分量也等于°这样我们便可

28、以在线性相关向量组p P2Pk中去掉向量Pi如果剩下的向量线性无关，由定理（ 1）即知x2x3就是基本可行解.否则再重复上面的步骤，可以得到可行解它的正分量个 数越来越少，经过有限步，必然得到一个可行解.颖刍莖峽饽亿顿裊赔泷。或者XHO则它必为基本可行解（定理 12.1.1 （2）或者xO但其正分量个 数或者大于1对应的列向量线性无关.而或者正分量个数等于1，这时对应A中 只有一个列向量，因为已假定 A的列向量不是零向量，而一个非零向量必然线 性无关.因此不论怎样x就是基本可行解（定理（ 1）濫驂膽閉驟羥闈詔寢賻。（2 ）设x° =（X10,x2.xn0）T是（SLP）最优解.并设f

29、*是目标函数最优值，即 f* =cx°.现在证明是存在基本可行解x*是最优解.如果x° =0，则因x°是最优解，首先必须是可行解.因此，x°就是基本可行 解（定理（2），取X* =x°就得到基本最优解X*.如果x°=0则x°中必有正 分量不妨设x0 =（x10,x2,.x0,O.O）T，其中xi0 - 0,1 ： i : k .若正分量对应 A中的列向 量 线性无关，则就是基本可行解（定理（ 1），取x0即得到基本最优解x* =X0.若正分量对应A中的列向量p1 p2.pk线性相关，则存在不全为零的数 ym.yk使 y1Py

30、2P2,. ykp0.构造 n维列向量 y 使其第 1,2，k分量分别为 0，而其余分量为0，则有yM 0且Ay = %» + y2 p2十+ ykpk = 0fx00取 min 2乞 yj >0 ,=乞>0（1 兰I 兰k）.可见日 >0 且 x+日 y 30.A（x±0y） = b理yjJ yl即x 书和x - vy是两个可行解，分别记为 x,及x” .銚銻縵哜鳗鸿锓謎諏涼。它们的目标函数值分别为ex，二ex0 cy cX，二oc - cy因为 x0 是最优解，所以：ex0 - ex' - "cy 一 0，ex0 - ex” 7cy

31、一 0又因为r . 0，故cy =0于是有ex，=cx” =cx° ;这表明x,及x”均为最优解.又 由日的取法知x0 0|yi|=O,y"O,仁i兰k当yl 0时X|0 -0，这时x” = x0 - v y中第I分量等于0，当yl : 0时这时X|° ：疋 =0中第I分量等于0.所以x；x”至少有一个的正分量个数比x0的 正分量个数要少，记这个解为 x1 .那么x1也是最优解.可见，如果x0不是基本最 优解，即x0的正分量对应A中的列向量线性相关，那么总可以令一个最优解x1， 其正分量个数比x0正分量个数少.如果x1是基本最优解，即x1的正分量对应A中 的列向量

32、线性无关，挤貼綬电麥结鈺贖哓类。则取 x* -X1 ,即证明 （2）.如果x1的正分量对应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）假定目标函数

33、在极点x1x2x3Xs上达到最优值f*又设它们的任意凸 组合为：ssx 八 伙,' =1,0 一 一1,1 一 i _si =1i =iss而 ex =、' jCxi =、' i f = fi di 1ss- ' 打b = b, x - '" _ 0i 4i 4故知x1x2Xs的凸组合也是目标函数的最优值点.至此，我们全面证明了定理1222.上面，定理,定理是线性规划的两个很重要的定理.证明了线性 规划的基本可行解等同于可行域的顶点.并且，如果线性规划有最优解，则必在 可行域的顶点上达到最优.塤礙籟馐决穩賽釙冊庫。这样，一个有最优解的(SLP )问题，是一定可以从可行域的极点中(即基本可行解中)求得最优解的.而基本可行解是对应A中的m个线性无关的列向量.A只有n个列向量.从n 个列向量中取出 m个线性无关向量相成的向量组.其数目上有限的.因此基本可行解的数量也是有限的.它不会超过：cnnn!个 .裊樣祕廬廂颤谚鍘芈蔺。(n m)!