第2章线性规划与单纯形法线性规划（Linear Programming，简写为LP）是运筹学的一个基本分支,其理论和方法比较成熟，应用非常广泛. 借助越来越普及的计算机及其日益先进的计算机技术，它能更加快捷地渗透于军事、科研、工农业和商业等各个领域.2.1线性规划模型及其基本概念2.1.1 线性规划模型在经济活动和企业管理中，通常要考虑对有限的资源进行合理的分配，以其望获取最大的经济效益. 以下是几个例子.解: 设x1、x2和x3分别表示产品A、B和C的周产量(件/周), f表示每周获利,则根据题目的意思，f可以表达为f=12x1+14x2+8x3希望在一定条件下f 达到最大, 但x 1、x 2和x 3受到一定的限制. 生产x 1件产品A 所需零件加工工时为1.1 x 1，生产x 2件产品B 所需零件加工工时为1.2 x 2，生产x 3件产品C 所需零件加工工时为1.4 x 3，又不能超过4600工时，因此，变量x 1、x 2和x 3应满足条件：1.1x 1+1.2x 2+1.4x 3≤4600同理，分析电镀与装配两道工序的情况，可知变量x 1、x 2和x 3还应满足条件：0.5x 1+0.6x 2+0.6x 3≤21000.7x 1+0.8x 2+0.6x 3≤2500当然，变量x 1、x 2和x 3只能取非负值，故有x 1≥0,x 2≥0,x 3≥0（注：这里暂且忽略决策变量整数的要求）总而言之，本问题可表达为下列数学模型:123123123123123max 12148 (21)1.1 1.2 1.446000.50.60.62100.. (22)0.70.80.625000,0,0f x x x x x x x x x s t x x x x x x =++-++≤⎧⎪++≤⎪-⎨++≤⎪⎪≥≥≥⎩上述数学模型由三个要素组成:(1)变量,或称决策变量, x 1、x 2和x 3，是问题中要确定的未知量,用以表明问题的方案、措施,可由决策者决定和控制;(2)目标函数（2-1）,它是决策变量的函数,按优化目标分别在这个函数前加上max 或min ，分别表示最大化与最小化;(3)约束条件（2-2）,指决策变量取值时受到的各种资源条件的限制,通常表达为含决策变量的等式或不等式,前面的“s.t.” 是“subject to ”的简写. 如果问题的数学模型中,决策变量的取值可以是连续的,目标函数是决策变量的线性函数,约束条件是决策变量的线性等式或不等式,则该类问题的数学模型称为线性规划（Linear Programming 简写为L.P.）.实际问题中线性的含义:一是严格的比例性,如生产某产品对资源的消耗量和可获取的利润,同其生产数量严格成比例;二是可叠加性,如生产多种产品时对某项资源的消耗量应等于各产品对该项资源的消耗量的和.解：题意即要确定从i #仓库运到j #纺织厂的原棉数量. 故设ij x 表示从i #仓运往j #纺织厂的原棉数量（吨）f 表示总运费.则f 可表达为11121321222323224f x x x x x x =+++++因从各仓库的运出量不能超过它的库存量，故有约束1112132122235030x x x x x x ++≤++≤另外，还要保证各纺织厂的需求都得到满足，故还有约束112112221323401525x x x x x x +=+=+=同时，运输量ij x 当然应是非负的：0,1,2;1,2,3.ij x i j ≥==因而得本问题的运输模型：111213212223111213212223112112221323min 23224503040..15250 (1,21,2,3)ij f x x x x x x x x x x x x x x s t x x x x x i j =+++++⎧++≤⎫⎬⎪++≤⎭⎪⎪+=⎫⎪⎪⎪+=⎨⎬⎪⎪+=⎭⎪⎪≥==⎪⎪⎩运出量受存量约束需求量约束；运输量非负约束 一般地，对于有m 个发点和n 个收点的运输模型为⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥===≤=∑∑∑∑====),...2,1;,...2,1(0)...2,1(),...3,2,1(..min 1111n j m i x n j b x m i a x t s x c f ij m i j ij nj i ij m i nj ijij其中 ，a i 为i #发点的存量，b j 为j #收点的需求量，c ij 为从i #发点到j #收点的单位运价 .特别当∑∑===m i nj j i b a 11时，存货必须全部运走，故不等式∑=≤n j i ij a x 1可改为等式),...2,1(1m i a x i nj ij ==∑=. 例2-3 （配套下料问题）现有原料钢管100根,长为18m,需要制成一批钢架,每个钢架由10根4m 长与5根6m 长的钢管制成. 问如何下料可使制造出的钢架最多？试建立这一问题的数学模型.解 由题意,每根钢管的下料有四种可能方案：（1） 截4根4m 长的；（2） 截3根4m 长的和1根6m 长的；（3） 截1根4m 长的和2根6m 长的；（4） 截3根6m 长的.设用第j 种截法用去原料钢管x j 根(j =1,2,3,4),则用这批原料钢管截得4m 长的钢管得12343x x x ++根,6m 长钢管得23423x x x ++根,再设x 5表示制成的钢架数量，根据每个钢架的结构可知，共截得4m 长的钢管数不能少于10 x 5,即12354310x x x x ++≥6m 长的钢管数不能少于5 x 5, 即2345235x x x x ++≥当然，所用原料钢管总数不能超过100根，即1234100x x x x +++≤于是得该问题的数学模型如下：5123523451234max 4310 235..1000,(1,2,,5)j x x x x x x x x x s t x x x x x j ++≥⎧⎪++≥⎪⎨+++≤⎪⎪≥=⎩（注：这里暂变量整数要求）. 这也是一个线性规划模型. 顺便指出，它的一个最优解是123450,81,7,10,25x x x x x =====，即利用这批原料钢管最多可制造出25个钢架，且实际上只需用98根原料.一般地，设线性规划问题中含有n 个变量：x j (j=1,2,…,n ), 在目标函数中，x j 的系数为c j , x j 的取值受m 项限制,用b i (i =1,...,m )表示第i 种限制量, 通常称为“约束常数”，用a ij 表示在第i 种限制中，变量x j 取值为1个单位时所消耗或贡献的量,通常称为技术系数或工艺系数. 则上述线性规划问题的数学模型可表示为(线性规划的一般形式) 11min (max) ( )(1,2,...)..0 ()nj jj nij j i j jf c x a x b i m s t x j ===⎧≥=≤=⎪⎨⎪≥⎩∑∑对某些2.1.2线性规划的标准型为了以后研究的方便，规定下列形式的线性规划模型称为标准型：⎪⎩⎪⎨⎧=≥===∑∑==),...2,1(0),...2,1(..min 11n j x m i b x a t s x c f jnj i j ij nj jj (2-4) 即要求（1）目标函数求最小值；（2）每个变量非负；（3）除非负条件外，约束条件全部为等式（也称为约束方程）.今后记线性规划的标准型为（LP ），并称（LP ）中独立的约束方程数目为（LP ）的阶数，（LP ）中变量的数目为（LP ）的维数.如何把一般的线性规划化作标准型，其方法如下：（1） 若目标是求1max nj j j z c x ==∑，则可令f = - z改求新问题的目标函数为1min ()nj j j f c x ==-∑则新问题与原问题同解，只是目标函数反号而已.（2） 对于形如1n ijj i j a x b =≤∑的约束，可引进松弛变量 '1ni i ij j j x b a x ==-∑ 则原约束等价于⎪⎩⎪⎨⎧≥'='+∑=01inj i i j ij x b x x a （3）对于形如i n j j ij b x a ≥∑=1 的约束，可引进剩余变量i n j j ij i b x a x -=''∑=1则原约束等价于⎪⎩⎪⎨⎧≥''=''-∑=01inj i i j ij x b x x a 注：在对i b 的符号无限制时，松弛变量与剩余变量无本质区别，如x 1+2x 2≥4也可以化为-x 1-2x 2≤-4(4) 若约束条件中有形如j j j j j j b x y b b x -=≠≥的约束，则可令)0(并代入原模型中消去0(≥≥j j j j y b x x 便化作即作平移）这样(5) 若某决策变量j x 是自由变量（即符号不受限制），则可引进两个非负变量j j j j j y y x ;y y ''-'=≥''≥'令与00代入原模型中消去x j ,化为00≥''≥'j j y y 与(6)当对模型中某决策变量作平移后，新的目标函数与原来的可能会差一个常数，这时可先放弃该常数，得标准型再求解，最后在最优目标函数值中补回该常数即可.例如，⎩⎨⎧≥+=5........43min 221x t s x x f 552222+'=========⇒-='x x x x 即令 ⎩⎨⎧≥'+'+=02043221x .......t .s x x f m in先求解标准型⎩⎨⎧≥''+=043221x ........t .s x x s m in 最后f=s +20例2-4 把下列线性规划问题化为标准型：⎪⎪⎩⎪⎪⎨⎧≥=-≥+≤++=03247632121212121x x x x x x x .t .s x x z m ax 解：经过以下几步(1)令f= - z(2) 用x 3 - x 4代替自由变量x 2,其中x 3≥0,x 4≥0(3) 对第一个约束不等式引入松弛变量x 5(4) 对第二个约束不等式引入剩余变量x 6则得标准型⎪⎪⎩⎪⎪⎨⎧=≥=+-=--+=+-++--=),,,,j (x x x x x x x x x x x x .t .s x x x f m in j 65431 032477633243164315431431先给定几个名词. 定义2-1满足线性规划模型约束条件的解，称为可行解或可行点；全体可行解之集合称为可行集或可行域；使目标函数达到最优的可行解称为最优解；最优解的目标函数值称为最优值；目标函数值也简称为目标值.2.1.3线性规划的图解法对于只有两个决策变量的线性规划模型可用图解法求解（即作图求解）虽然图解法难以推广到多变量的情形，但能帮助我们直观地理解求解的思路，以下用例子来说明. 例2-5．求解线性规划⎪⎪⎩⎪⎪⎨⎧≥≥≤+≤+≤++=00280932005436048532121212121x x x x x x x x .t .s x x f m ax ， 解：我们可按以下步骤求解这个模型.（1）、分别以x 1，x 2为横坐标与纵坐标，建立平面直角坐标系.（2）、根据约束条件在平面上画出相应区域（通常是凸多边形）. 当然，先要画清楚每个约束条件的边界情况（即取等号），对应一直线，然后判断该约束不等式对应哪半张平面，其方法很简单，只需在直线一旁任取一点的坐标代入约束不等式，看看是否满足，如果满足，则这点所在的半张平面，就对应这个约束不等式，否则，另半张平面，才是对应这个约束不等式的区域. 画出每个约束不等式对应的半平面区域的交集，就得线性规划的可行域. 如图2-1.（3）、在目标函数中，把f 作为参数，就得到一族平行直线，当f=0时，直线过原点，随着f 的增大，直线向上平移，最后与C 点相交，则交点坐标就是该可行域上使f 达到最大的决策变量之值(即最优解). 此点对应的f 值就是最优值.而C 点的坐标可由方程组解出⎩⎨⎧=+=+20054280932121x x x x 解得 x 1=400/21=19.05; x 2=520/21=24.76 ,max f =3×(400/21)+5×(520/21)=3800/21=180.95 注：（1）决策变量的最优解在可行域的顶点上找到;（2）若目标函数相应的直线平行于可行域的某一边，则可能有无穷多最优解，（比如，本例改为 f=4x 1+5x 2）;（3）若目标函数f 对应的直线沿梯度方向12(,,...)T n c c c c =移动，则f 的值将增加.例2-6．求解线性规划12121212min 32421..2100f x x x x s t x x x x =+-≥⎧⎪-+≤⎨⎪≥≥⎩，显然点A 的坐标使f 达到最小，即x 1=1/4, x 2=0 时，min f =3/4 注：（1）此例的可行域是无界的; （2）此例的目标若改为max f , 则无最优解.例2-7．求解线性规划⎪⎩⎪⎨⎧≥≥≥+-≤++=00625423..2max 21212121x x x x x x t s x x f ，解：因可行域空，故无可行解.以上例子说明：-5x 图2-3（1）可行域若非空，则一般是一个凸多边形（有界或无界）; （2）最优解在可行域的顶点或边界上; （3）以下情况都是可能发生的.1） 无可行解； 2）有可行解而无最优解（f 在可行域上无界）； 3）有无穷多最优解； 4）有唯一最优解.我们可用运筹学实验软件作图解法演示.2.1.4基可行解与基本定理 2.1.4.1基可行解及其相关概念 设[]⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡==⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=∙⨯n nj j j j n m ij m n x x x a a a a b b b c c c 21212121 x A A b c ；；；； 于是标准型线性规划的矩阵形式（LP ）可写成min (..0 0T j f s t x ==⎧⎪⎨≥≥⎪⎩c xAx b x 约束方程组）（表示每个分量）定义2-2 设（LP ）中A 的秩为m , 则由A 中m 个线性无关的列构成的子阵，称为（LP ）的一个基，记为B ，与B 的列相应的变量 m B B B x ,,x ,x 21，称为（LP ）关于B 的基变量，其余变量称为非基变量.基B 记为 ][21mB B B ,,∙∙∙=A A A B ，（LP ）的系数矩阵A 中除B 外的其余列构成的子阵记为 ][21mn D D D ,,-∙∙∙=A A A D .由基变量的下标构成之集合，记为{}m B B B B I ,,21=,由非基变量的下标构成之集合记为{}m n D D D D I -= ,,21.基变量的向量记为12(,,,)mTB B B Bx x x x = ， 非基变量的向量记为T DD D D )x ,,x ,x (mn -= 21x .显然，由定义知，基B 必是可逆矩阵.例2-8 对于约束方程组 ⎩⎨⎧=++=+++423 24224324321x x x x x x x ， 取⎪⎪⎭⎫⎝⎛==∙∙1322),(32A A B，则0462≠-=-=B ，故此B 是一个基，对于此B 而言，{}{}T D T B D B )x ,x (,)x ,x (,,I ,,I 41324132====x x 在上例中令⎩⎨⎧=+=+==432220323241x x x x x x 得 解得212332-==x x ， 则解31(0,,,0)22T=-x 为关于基），（32∙∙=A A B 的基解.注：对（LP ）而言，同时满足Ax=b 与x ≥0的解，才是可行解，而基解只满足Ax=b,未必满足x ≥0，故基解未必是可行解.定义2-4 当（LP ）的一个基解，同时又是可行解，则称为基可行解. 基可行解对应的基称为可行基.显然，（LP ）的一个基解x 是基可行解的充要条件是0≥B x .定义2-5 当（LP ）的一个基可行解，同时又是最优解，则称为（LP ）的基最优解. 对应的基称为最优基.(LP)的几种解的关系可以用图2-7来描述.从以上定义可知基可行解的几点简单性质:(1)每个基可行解至多只有m 个正分量; 非退化的基可行解恰有m 个正分量;(2)基可行解数目≤基解数目≤m n C ;(3)若x =0是可行解,则它必是基可行解. 因此时在(LP)中,b=0,从而对任何基B,0B x =, 故x=0是一个退化的基可行解. 2.1.4.2线性规划的基本定理线性规划问题的解与凸集和顶点的概念密切相关, 故先给出其定义. 定义2-6 设n G R ⊂, 若对任意',"x G x G ∈∈和一切满足01α<<的实数α, 点'(1)"x x G αα+-∈, 则称集合G为R n 中的一个凸集.换言之,若连结G 上任两点的直线段整段仍在G 上,则G 是凸集. 例如R 2中的三角形域、圆域、菱形域等都是凸集,而圆环则不是凸集. R 3中的四面体、圆柱体等都是凸集, 而圆环体则不是凸集.约束方程组的解可行解基解基可行解最优解 基最 优解图 2-7定义2-7设G 是一凸集, x G ∈, 若不存在G 中不同的两点:x’与x”及实数α∈(0,1)使'(1)"x x x αα=+-, 则称x 为G 的一个顶点.换言之,若凸集G 中的点不能成为G 中任何线段内的点就称为顶点. 例如三角形域的顶点和圆域的圆周上的点都是顶点.定理2-1线性规划问题(LP)的可行集是一凸集. （请读者自己证明） 以下记, 1,2,j j P A j n ∙== .定理2-2在线性规划问题(LP )中,非零可行解x 是基可行解的充要条件是与x 的正分量相应的A 中的列向量线性无关.证明 设非零可行解x 是基可行解,由基解的定义可知x 的正分量是基变量,从而与x 的正分量相应的A 中的列向量必是x 的基中的列向量, 故线性无关.反之,若A 中与非零可行解x 的正分量相应的列向量线性无关, 则不妨设12(,,,0,0),0,1,2,T l i x x x x x i l =>= , 12,,l P P P 线性无关, A的秩为m. 故l m ≤.若l=m , 则12,,l P P P 恰好构成一个基, x 就是相应这个基的基可行解. 当l<m 时, 必可从A 的其余列向量中找出m-l 个与12,,l P P P 构成一个基, x 就是相应这个基的基可行解. 证毕.定理2-3对于线性规划问题(LP ), x 是可行集G 的顶点的充要条件是x 是基可行解.(证明略)此定理告诉我们，可行集的顶点就是基可行解. 定理2-4 (基本定理)对于标准型线性规划（LP ）（1）若有可行解，则必有基可行解；（2）若有最优解，则必有基最优解. (证明略.)以上结果说明，若最优解x 不是基最优解，则一定可构造出另一个最优解，且比x 至少少一个正分量. 如此反复，直至最优解的正分量对应的A 的列向量线性无关为止. 由定理2-2, 此时的最优解就是基最优解. 定理2-4的意义：本定理告诉我们，寻找（LP ）的最优解，无须在全部可行解（一般有无穷多）中去寻找，而只需在有限个基可行解（至多mnC 个）中去寻找. 故当m n C 不大时，可通过比较全部基可行解的目标值而求出最优解.2.2单纯形法2.2.1概述若用枚举法求解（LP ）,则计算量可能很大，例n =50,m =20.201350 4.71310c =⨯ .即（LP ）至多有这么多个基，也就有这么多个基解，若逐个比较目标值大小来求出最优解，即使用计算机以610-秒处理完一个基解，也要一年半才能算完！ 枚举法包含大量多余的计算. 单纯形法是求解（LP）的一种实用方法，于1947年由G .B.Dantzig 提出的.其基本思想是：从一个基可行解(可行域顶点)转换到另一基可行解，能使目标值更优或至多不变，如此反复，逐步改进目标值，最终求出最优图2-8ABC解，从而避免很多不必要的计算. 通过分析该顶点的数据，可判断下一步应转向那一个相邻顶点. 如图2-8，假定目标是求 f 最小值, 设f (B )=10, f (A )=8, f (C )=12 ,使用单纯形法, 当计算完点B 后, 就可以判断出下一步应转向点A 而不是点C , 从而可避免不必要的计算.为了后面讨论方便, 在无特别声明时, 我们对（LP ）约定①),2,1(0m i b i =≥; ②m<n ; ③秩(A)=m.2.2.2单纯形表在（LP ）中,把目标函数f 也视作变量,并令w=- f ，对给定的基B ,指标集{}{}m n D m B D ,D ,D I ,B ,B ,B I -== 2122也自然确定. 则约束方程组与目标函数可写作111111111111111110 00m m n m n m m m n m n m m m n m n m B B B B D D D D mB B mB B mD D mD D m B B B B D D D D a x a x w a x a x b a x a x w a x a x b c x c x w c x c x ------+++⋅+++=⎧⎪⎪⎨+++⋅+++=⎪⎪++++++=⎩. (2-5) 我们把（2-5）最后一个方程称为目标方程.若把前m+1列的系数矩阵记为Q ，则因||0B ≠，故111100 01mm mmB B mB mB B B a a Q B a a c c ==≠. (2-6) 即对每一组)(1mn DD x ,x - 的值.方程组(2-5)都有唯一解. 故可化作(2-7)的形式（即把基变量的系数矩阵化作单位矩阵）0111111111111⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧-=+++=+++=+++=++++--------f x r x r w b x y x y x b x y x y x b x y x y x m n m n m n m n m n m n i m n m n D D D D m D mD D mD Bm iD iD D iD B D D D D B(2-7) 注：(2-7)式有两个重要特点： ①目标方程中不再含有基变量； ②约束方程组中把B 化为了单位矩阵，即把kB A ∙化为了单位列向量e k =(0,0…,0,1,0,…0)T ，其中“1”在第k 个位置上. 把方程组(2-7)的数据略去w 列后列于表2-3.注：1）实际上，T （B ）中的表头的变量仍按x 1,x 2,…x n 的顺序排列;2) 相应于基B 的基解为01==---D T m i B ,)b b ,b (x x3) 相应于基B 的目标值为f 0（从目标方程中令000f f,f w D =-==即得x ）4) 最后一行各数),2,1(n j r j =称为x j 的检验数（用于检验当前的解是否最优），记12(,,,)T n r r r =r 基变量的检验数记为r B , 非基变量的检验数记为r D.显然r B =0. 若T(B)中0(1,2,)0(1,2,)i j b i m r j n -≥=≥= 与都成立，则此时的基解就是（LP ）的基最优解，0f 是最优值. 这是因为目标方程即m n m n D D D D x r x r f f w --+++==- 110对（LP ）的任一可行解x ，必有0≥jDx (j =1,2,…,n-m )，从而010f x r f f j j D m n j D ≥+=∑-=，故f 0是最优值，相应的基可行解是基最优解.例2-9 求解线性规划⎪⎩⎪⎨⎧=≥=++-=++-=4,3,2,1,0841823..2min 42132121j x x x x x x x t s x x f j解：选取{}3,2,B I =1204B ⎡⎤=⎢⎥⎣⎦即. (2-5)式为1231241232184820x x x x x x x x w ++=⎧⎪-++=⎨⎪-+=⎩由消元法得134124147/21/2141/41/427/41/42x x x x x x x x W +-=⎧⎪-++=⎨⎪++=⎩T (B )为此时，00b r -≥≥且，故得基最优解是：x 1=0,x 2=2,x 3=14,x 4=0,最优值为min f=-2. 2.2.3 转轴运算(LP)的每个基对应一张单纯形表，那么，对于只有一列不同的两个基的两张单纯形表之间有何联系，如何转换呢？定义2-7 设B 与B ’是只有一列不同的两个基, 考虑如何从T (B )转换出T (B ’)我们把B 中与B ’不同的列称为离基列(或出基列), 与离基列相应的变量称为离基变量(或出基变量), B ’中与B 不同的列称为进基列, 与进基列相应的变量称为进基变量. 例如3344{1,3,5,7}{1,4,5,7}.B B I I A x A x '∙==--------，，离基列，离基变量，进基列，进基变量.2.2.3.1 转轴公式 设}D ,D ,D {I ,}D ,D ,D {I }B ,B ,B {I ,}B ,B ,B {I m n k D m n k D m k B m k B '-'-'''=='''== 1111 )(⎩⎨⎧=∈≠='ki I t t k i B B D i i ， (2-8)即 kB x 是离基变量,t x 是进基变量与基B 相应的方程组(2-7)可写成⎪⎪⎩⎪⎪⎨⎧-=+++++=+++++⋅+=+++++⋅++）（）（）（3 2 01 00f x r x r w b x y x y w x b x y x y w x j j t t k j kj t kt B i j ij t it B k i现要把该方程组化作对B ’而言的(2-7)形式. 设0kt y ≠, 作如下变换1 (2)(5), (1)(5)(4)3(5)(6)it t kty r y ⨯⇒-⨯⇒-⨯⇒，（）.这实际上是作方程组的作行初等变换. 得到⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧--=+-++⋅+++-=++++⋅+≠-=+-++⋅++⋅+-(6)0)5( 01)4()( 000t ktkj t ktkj j t B kt t ktkj ktkj t B kt it kt k i j it kt ij ij t B kt it B r y b f x )r y y r (x w x y r y b x y y x w x y k i y y bb x )y y y y (x w x y y x k k k i 可见对B ’而言的(2-7)式与对B 而言的(2-7)式的数据之间有如下关系:)( 'D ktkjit kt kj ij ij I j ki y y k i y y y y y '∈⎪⎪⎩⎪⎪⎨⎧=≠-= ， (2-9)kiit kt i kktb b y i k y b b i ky ⎧-≠⎪⎪'=⎨⎪=⎪⎩ ，(2-10) )(''D tktkj j jI j r y y r r ∈-= ，(2-11)'00kt ktb f f r y =+， (2-12)(2-9)~(2-12)式称为转轴公式.按这些公式进行的运算称为转轴运算,简称为转轴. kt y 称为主元.2.2.3.2 转轴运算在单纯形表中的操作对转轴公式，其实只需理解其在T (B )中的算法即可. 转轴运算在单纯形表T (B )中是如何体现的呢?例2-10 在例2-9中选取{3,4},{2,4}B B I I '==，即x 3是离基变量，x 2是进基变量. T (B )如表2-5所示，其中x 2列打圆括号的数是主元，以下同.表2-5(6)(4)(3),(5)4(4)(2)(4),21(1)⇒+⇒⨯-⇒⨯以上过程表明，从T (B )转换到T (B ’)的步骤如下: (1) 确定T (B )中主元y kt （0kt y ≠）;(2) 对T (B )中第k 行各数除以y kt 产生T (B ’)中第k 行, 并在x B 中用进基变量代替离基变量;(3) 利用T (B ’)中的第k 行, 用行初等变换,把T (B )中第x t 列的非主元化作0而产生T (B ’)中其他行. 2.2.3.3 确定离基变量转轴时，我们自然希望既能保持解的可行性又能改进目标值. 这就导致了离基变量与进基变量的选择问题. 若确定了进基变量, 则应如何选择离基变量, 才能保证转轴后的基解也是可行解 (假定转轴前的基解是可行解) .设x t 是进基变量，且)m ,,i (b i 210=≥，现要求)m ,,i (b i 210=≥'由转轴公式：i=k 时(k 待定) 00>∴≥='kt ktkky y b b ， (即主元必须是正数) it ktki i y y b b b k i -='≠，时 因为00000≥'≤≥>≥i it i kt k b y ,b ,y ,b 时，自然故当当0,0,(1,0)kk i it i it it ktkt itb b by b y i m y y y y >-≥≤≤≤>时要即此式i=k 时也成立，故令min{|1,0}k i it kt itb bi m y y y =≤≤> , (2-13) 则k B x 就是离基变量.如在例2-10 的T (B )中，min{18/2,8/4}=8/4,故选42x x B =为离基变量,即应选'B I ={3,2},才能保证T(B ’)中的0≥'b .2.2.3.4 确定进基变量应如何选择进基变量,再按(2-13)确定离基变量,转轴后的目标值至少不大于原目标值?因为0,0k kt b y ≥>，故由转轴公式t ktkr y b f f +='00知，只须 000,t r f f '≤≤则. 通常令},0|min{D j j t I j r r r ∈<= (2-14)则已x t 作进基变量. 特别当0k b >时，必有'00f f <，即转轴后的目标值必下降.2.2.4单纯形法（simplex method ）我们把前两节的结果归纳后,以定理的形式列出如下.这是单纯形法的基本理论, 称为判别定理.定理2-5设B 为(LP)的一个可行基, x 为关于B 的基可行解，关于B 的(1)与(2)是从前面总结而得. (3)是新结论.证明(3) 对于(2-7)而言,每给定非基变量的一组值,都唯一确定了基变量之值.现令x t =N>0,其他非基变量为0,并注意到（2-7）式可简写为：⎪⎩⎪⎨⎧+==-=∑∑∈∈j I j j I j j ij i B x r f f m ,...,,i x y b x D D i 0)21( ，则有⎪⎩⎪⎨⎧+==-=Nr f f m ,,i ,N y b x t it i B i 0)21(因000i it b y N ≥≤>，，，故0,(1,2,)i B x i m≥= .从而相应的解x 总是 (LP)的可行解(对不同的N >0而言).又因0t r <,故若+∞→N ,则x 相应的目标值-∞→f .故f 在可行域G 上无下界.单纯形法的计算步骤如下: 1) 确定初始可行基B ，作出T (B )2) 判断T (B )中,0 12j r j n ≥= （，，）是否都成立，是:⎪⎪⎭⎫⎝⎛=⎪⎪⎭⎫ ⎝⎛=0x x x b D B 是基最优解,0f 为最优值,结束.否: 确定t ,使}|min{D j t I j r r ∈=3) 判定T(B)中)m ,,i (,y it 210=≤是否都成立，是: (LP)的目标值f 在可行域G 上无下界,结束. 否: 确定k 使}01{>≤≤=it iti kt k y ,m i |y bmin y b , 4) 以kt y 为主元作转轴得新T (B ),转2).这些步骤可用直观的流程图来描述. 如图2-11所示.图 2-11例2-11 求解L.P .⎪⎪⎩⎪⎪⎨⎧=≥≤+-≤+--≤++-=3,2,101821432482..336max 32132121321j x x x x x x x x x t s x x x z j 解:先标准化为:⎪⎪⎩⎪⎪⎨⎧=≥=++-=++--=++-+-=654321018 214 3248 233663215321421321，，，,,j x x x x x x x x x x x x .t .s x x x f m in j 若选 {4,5,6},{1,2,3}B D I I ==则B =I (单位矩阵),且初始基解 T ),,,,,(18148000=x 是可行解,按流程图的迭代过程列表表2-7在表2-9中，0,(1,2,6)j r j ≥= . 故标准化后的L.P.的最优解T,,,,,)4001004(=x , 最优值min f =-54.原L.P.的最优解T,,)1004(=x ,最优值max z =54. 例2-12 求解L.P.⎪⎩⎪⎨⎧=≥=++-=+---=432104322342132121,,,j x x x x x x x .t .s x x f m in j解:先选}2,1{},4,3{==D B I I ,基解T,,,)4200(=x 是基可行解. 迭代过程列于表2-10~表2-11.可见，2200,(1,2)i r y i <≤=，但，f 在可行域G 上无下界.单纯形表的矩阵描述利用矩阵探讨关于基B 的单纯形表T (B )上的数据与（LP ）的原始数据的关系. 选定基B 后，相应的（2-5）式的矩阵形式为:010B T T BD D x B D b w c c x ⎡⎤⎡⎤⎡⎤⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎢⎥⎣⎦， (2-15)其中c B 与c D 分别是基变量x B 与非基变量x D 在目标函数中的系数. 令01TBB Q c ⎡⎤=⎢⎥⎣⎦， 则11101T B B Q c B ---⎡⎤=⎢⎥-⎣⎦. (2-15)两边左乘1-Q 得⎥⎦⎤⎢⎣⎡-=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎦⎤⎢⎣⎡-----b B c b B x w x D B c c D B I T B D B T B T D m 1111100 略去w 列并把数据写到表上得T (B ):表2-12因1m I B B-=，故T (B )的左上角部分数据为11B B D B A--=（，）. 记1T T T D D B r c c B D -=-，又10T T T BB B r c c B B -==-，故 1111(,)(,)(,)(,)T T T T T T T B D B B D B TT T TT B D BBr r r c c B B c c B D B B D B A----==--=-=-c c c c c即检验数的计算公式为1T T T B r B A -=-c c . 其中1T B c B -称为单纯形因子.若记10,T B b B b f b -==c 则，于是T (B )又可写成2.3单纯形法的进一步探讨前面介绍了单纯形法, 但仍有一些问题未解决. 一是当(LP)有最优解时,单纯形法能否保证通过有限次转轴就找出最优解；二是如何较容易求出初始可行基. 2.3.1避免循环的方法当(LP) 没有退化的基可行解时，称(LP)为非退化的.此时,由前面分析知，当00, 0f f b k<'>时,这说明目标值越来越小，而每个目标值对应一个不同的基可行解，不可能重复，而基可行解只有有限个，故单纯形法必可经有限次转轴而算法结束.但当(LP)退化时，用单纯形法运算有可能会出现无限循环的情况（即后来出现原来出现过的可行基），目标值始终不下降, 永不终止.000 f f f B B B B ''='=→''→'→，保持1955年，Beale 构造出一个会使单纯形法出现无限循环的例. 例 2-13⎪⎪⎩⎪⎪⎨⎧=≥=+=+--+=+--++-+-=721 010312 098 62063762154212765441176215443,...,,j ,x x x x x x x x x x x x x .t .s x x x x f min j初始选I B ={1,2,3},应用单纯形法从表2-12转轴至表2-17.表2-122-13表表表表2-17从表2-17再转轴就与表2-12相同了, 这就出现了循环. 这些表尽管对应不同的基,但都对应同一基可行解(0,0,1,0,0,0,0)Tb=,则转x=. 其实只要0k轴前后的两个基可行解总是相同的. 这时转来转去,目标值并未得到改进.在1976年，R.G.Bland提出并证明了用单纯形法迭代时可避免循环的一种新方法,称为Bland方法. 在用单纯形法迭代时,只要按以下规则来确定进基变量与离基变量，就不会产生循环.从理论上讲，用Bland 方法是可以避免（LP）退化时可能出现的循环，但是，按统计规律平均而言，用Bland 方法通常要比一般的单纯形法收敛较慢（约慢40%）, 而实际计算中出现无限循环的现象是十分罕见的，故通常仍采用一般的单纯形法.2.3.2两阶段法当线性规划原模型的形式如min ..0Tf c x Ax b s t x =≤⎧⎨≥⎩且0b ≥时，添加松弛变量标准化后，松弛变量的系数列向量就构成了一个明显的初始可行基，马上可以启动单纯形法求解了(见例2-11). 当(LP)无明显的初始可行基时，我们可以在每个约束方程中添加一个非负变量（称为人工变量），构造出初始可行基（称为人造基）. 首先用人工变量之和作目标函数构造出(LP1)模型：（LP1） 1nj 1min ,1,2,..0,1,2,mn ii ij j n i i jz x a x x b i m s t x j n m +=+==⎧+==⎪⎨⎪≥=+⎩∑∑其中，,(1,2,,)n i x i m += 为人工变量.然后分两个阶段求解，第一阶段,求(LP1)的基最优解,并使其基变量中不出现人工变量；第二阶段,以(LP1)的基最优解(基变量中不含人工变量)作为(LP)的初始基可行解，开始求解(LP). 这种算法便称为两阶段法.使用两阶段法时要注意以下几点说明. 1、 (LP1)必有基最优解 设121(,,),(,,)T TNn M n n m x x x x x ++==x x （即全部人工变量）取b ,m n ,n ,n I MN B ==+++=x x 0}21{，则 是（LP1）的基可行解又因0n i z x +=≥∑ ，故z 不会无下界， 从而（LP1）必有基最优解.以下设（LP1）的基最优解为：M M N N x ˆx ,x ˆx ==，相应的最优基为B ˆ. 2、 在求解（LP1）时，首张单纯形表中∑∑=∈-=i D ij j b Z I j a r ，，)( ，（其中∑表示对有人工变量的行求和）3、 （LP ）有可行解⇔（LP1）的最优值为0（即0=Mx ˆ）（⇒）设b N =x 是（LP ）的一个可行解，则0 ==M N ,b x x ，就是（LP1）的可行解，对应的目标值为0而z ≥0，故此目标值就是最优值 （⇐）设（LP1）的最优值为0，相应的最优解为M M N N b x ˆ,b x ˆ==，则必有0=-Mb ，则N N b x ˆ=就是（LP ）的一个可行解.4、 若0=M x ˆ，且人工变量不是∧B 的基变量，则∧B 是（LP ）的可行基 这是因为此时∧B 不含人工变量的系数，即∧B 的列都是（LP ）中A 的列，又当人工变量都为0时，（LP1）与（LP ）的约束条件完全一样，故（LP1）的可行基∧B 也是（LP ）的可行基.5、 若0=M x ˆ，但某人工变量)n B ˆ(x k B ˆk>是∧B 的基变量，且在)B ˆ(T 中存在某)(0n t y kt ≤≠，则可用kt y 为主元作转轴，转轴后的目标值不变（因-k b =0）最优解也不变. 但新基的基变量中少了一个人工变量.6、 若0=M x ˆ，人工变量)n B ˆ(x kB ˆk >是∧B 的基变量，在)(∧B T 中0 (1,2,)kj y j n == ，,则这行是多余的，可删去. 这是因为当人工变量都为0时，这行实际上是恒等式0=0.7、 若出现情形4，则在进入第二阶段时，在第一阶段的最优表（即基最优解对应的表）中删去人工变量的列，并换回（LP ）的不含关于ˆB的基变量的目标方程，生成第二阶段的首张表. 以下是使用两阶段法的例子. 例2-14 求解下面线性规划⎪⎩⎪⎨⎧=≥=++-=+++--=321042423321321321,,j x x x x x x x .t .s x x x f m in j解 引入人工变量x 4,x 5,得相应的(LP1)为：4512341235min 2 4..2 40,1,2,3,4,5jz x x x x x x s t x x x x x j =+⎧+++=⎪-+++=⎨⎪≥=⎩取}5,4{=BI ，第一阶段计算如表2-18~表2-20所示.至此，第一阶段结束，0f =0, 且人工变量不是基变量.进入第二阶段，删除表2-20的人工变量x 4,x 5的列，并把最后一行r 改为原(LP)的目标函数系数c以基变量列的原主元1, 利用行初等变换把该列最后一数化为0，得此时全部0≥j r ，得(LP)最优解为T ),,(033=x , 最优值3-.例 2-15 求解(LP)⎪⎪⎩⎪⎪⎨⎧=≥=++=++++-=+++--=52104 334242343154321432321 ,,j x x x x x x x x x x x x .t .s x x x f m in j 解 由于5∙A 已是单位列向量,故只需引入两个人工变量76x x ,,可得到(LP1)的人造基⎪⎪⎩⎪⎪⎨⎧=≥=+++=++++-=++++=72104334 242743154321643276,...,,j ,x x x x x x x x x x x x x x .t .s x x z m in j取}7,5,6{=BI 得表2-23.这里，最后一行是第一、三行对应数之和的相反数.此时全部0≥jr ，故已得最优解，min z =0,但有人工变量x 6是基变量且0111≠-=y . 我们以11y 为主元作转轴后得表2-26, 它不再有人工变量是基变量.已化作情形4，仿例2-14，进入第二阶段, 见表2-27~表2-28.此时，r ≥0, 已得最优解.T )00330(,,,,*=x ，最优值 f*=-8/3.。
