第二章单纯形法 由上一章定理5,线性规划问题的最优解可以只限于在基可行解中去挑选。由于基可行 解有限,故原则上可采用枚举法。但从算法的角度看这显然不是简便有效的。当m、n较大 时,根本行不通。事实上m、n在100左右的线性规划问题属于小型的。而此时基可行解的数 目可能多达230(m=50,n=100)以上故必须寻找有效算法。 Danzig首先提出的单纯形算法 被实践证明是异常有效和普遍适用的。其基本思想是从一个基可行解出发,寻找一个比之更 “好”的。由此不断改进最后得到最优解 单纯形法可分为两阶段。第一阶段是寻求第一个基可行解。第二阶段是通过换基迭代 寻找最优解。下面先介绍第二阶段,然后再讲第一阶段。 §1典式及单纯形表 (一)典式 考虑标准形式的线性规划 AX=b LPX≥0 min f= CX 设已知一个可行基B是m阶单位矩阵。不失一般性可假定B位于A的前m列。这时约束 方程(1)的形式为 X Pu B, x=b +B2 +B,nx,=b2 Bmxm++…+Bmxn=b 其中b≥0,1=1…,m,显然对应基可行解X=(b1…bn,0,…0),将 x=b-∑Bx1,=1…m代入目标函数(3),得 j=m+1 CX=∑cx=∑c(b-∑周x)+∑c c-∑②cB-c)x B-e (5)
63 第二章 单纯形法 由上一章定理 5，线性规划问题的最优解可以只限于在基可行解中去挑选。由于基可行 解有限,故原则上可采用枚举法。但从算法的角度看,这显然不是简便有效的。当 m、n 较大 时,根本行不通。事实上 m、n 在 100 左右的线性规划问题属于小型的。而此时基可行解的数 目可能多达 2 50 （m=50,n=100）以上,故必须寻找有效算法。Danzig 首先提出的单纯形算法 被实践证明是异常有效和普遍适用的。其基本思想是从一个基可行解出发,寻找一个比之更 “好”的。由此不断改进,最后得到最优解。 单纯形法可分为两阶段。第一阶段是寻求第一个基可行解。第二阶段是通过换基迭代 寻找最优解。下面先介绍第二阶段，然后再讲第一阶段。 §1 典式及单纯形表 （一） 典式 考虑标准形式的线性规划 (1) 0 (2) min (3) AX b LP X f CX = = 设已知一个可行基 B 是 m 阶单位矩阵。不失一般性,可假定 B 位于 A 的前 m 列。这时约束 方程（1）的形式为 1 1 1 1 1 1 2 2 1 1 2 2 1 1 m m n n m m n n m mm m mn n m x x x b x x x b x x x b + + + + + + + + + = + + + = + + + = 其 中 0, 1, , i b i m = ， 显 然 对 应 基 可 行 解 1 ( , , ,0, ,0)T X b b = m ， 将 1 , 1, , n i i ij j j m x b x i m = + = − = 代入目标函数（3）,得 1 1 1 1 1 1 1 ( ) ( ) n m n n j j i i ij j j j j i j m j m m n m i i i ij j j i j m i CX c x c b x c x c b c c x = = = + = + = = + = = = − + = − − 记 1 m i i i f c b = = （4） 1 m j i ij j i c c = = − （5）
则原问题(LP)变为 A ≥0,j=1, ∑ 这种形式叫作线性规划问题的典式。它显然与(LP)(1)-(3)等价。 对于任何一可行基B,亦可把(LP)化为典式形式。化法如下: 仍设B位于A的前m列,即A=(B、N)。其中B=(,…,Pn),N=(Pm+1…,P) 相应地向量X和C可分为X= r C=(CB,CN 于是 (1)可写成 (B,M/ =BX+NX=b X=B6-B- NX x=a1-∑Bx,=1 a1 Blm+1…Bn 其中Bb=:,B1 Bm+t…B 把(6)代入目标函数(3)。得 CX=(CR CIx/88-b-(CPB-IN-CN)X, (7) ∑①c月-cx,=f-∑ j=m+I 其中仍为基可行解x对应的目标函数值(x=(a1,…,am0…0))。仍为目标 函数中非基变量x系数之相反数。这样我们得到一般典式的矩阵形式
64 则原问题（LP）变为 （* ） 1 1 , 1, , 0, 1, , min n i i ij j j m j n j j j m x b x i m x j n f f x = + = + = − = = = − 这种形式叫作线性规划问题的典式。它显然与（LP）(1)-(3)等价。 对于任何一可行基 B，亦可把（LP）化为典式形式。化法如下： 仍设 B 位于 A 的前 m 列，即 A=（B、N）。其中 B= 1 ( , , ) P P m ， 1 ( , , ) N P P = m n + 。 相应地向量 X 和 C 可分为 , ( , ) B B N N X X C C C X = = 。于是 （1）可写成 1 1 ( , ) B B N N B N X B N BX NX b X X B b B NX − − = + = = − （6） 或 1 , 1, , n i i ij j j m x x i m = + = − = (6) 其中 1 1 1 1 1 1 1 , m n m mm mn B b B N + − − + = = 把（6）代入目标函数（3）。得 1 1 ( , ) ( ) B B N B B N N N X CX C C C B b C B N C X X − − = = − − （7） 即 1 1 1 1 ( ) m n m n i i i ij j j j j i j m i j m f c c c x f x = = + = = + = − − = − （7） ' 其中 f 仍为基可行解 x 对应的目标函数值 1 ( ( , , ,0, ,0) ) T X = m 。 j 仍为目标 函数中非基变量 j x 系数之相反数。这样我们得到一般典式的矩阵形式：
X=B6-B-NX X≥0 ninf=CrB(CrB (二)单纯形表 设对某初始可行基B,已求得(LP)的典式为 x1= Bix,i=l, x,≥0,j=1…,n (9) x 为了计算方便,将式中的系数分离出来,象形成增广矩阵那样列成表格,称为对应于 基B的初始单纯形表 基变量xx2 x B1m+1…B1 x2 0 B2m+…B2 0 B Bn 0 0 0 n 注意表中最后一行实际上是等式:f=f0∑x1→f+∑x=f的简化和变形。 我们将看到这样写不会影响以后的运算,反而带来很多方便。 上述单纯形表又可写成矩阵形式: 基变量 B N CoBN-O 因BA=B(B,N)=(1,BN B'A-C=CBB(B, N)-(CB, CN)=(0, CBBN-CN) (10) 故这个表又可进一步简写为
65 ** 1 1 1 1 0 min ( ) B N B B N N X B b B NX X f C B b C B N C X − − − − = − = − − （8） （二） 单纯形表 设对某初始可行基 B，已求得（LP）的典式为 ： 1 1 , 1, , 0, 1, , min n i i ij j j m j n j j j m x x i m x j n f f x = + = + = − = = = − （9） 为了计算方便，将式中的系数分离出来，象形成增广矩阵那样列成表格，称为对应于 基 B 的初始单纯形表： 基变量 1 x 2 x m x m 1 x + n x 1 x 2 x m x 1 0 0 1m+1 1n 0 1 0 2m 1 + 2n 0 0 1 mm+1 mn 1 2 m f 0 0 0 m+1 n f 注意表中最后一行实际上是等式： 0 0 f f x f x f = − j j → + j j = 的简化和变形。 我们将看到这样写不会影响以后的运算，反而带来很多方便。 上述单纯形表又可写成矩阵形式： 基变量 1 x 2 x m x m 1 x + n x 1 x 2 x m x I B −1 N 1 B b− f 0 CB B N −CN −1 CB 1 B b− 因 1 1 1 B A B B N I B N ( , ) ( , ) − − − = = CB 1 B A− - 1 1 ( , ) ( , ) (0, ) C C B B N C C C B N C B B N B N − − = − = − （10） 故这个表又可进一步简写为
基变量 x2 B-A B CB-lA-C CB b 单纯形表的这种矩阵形式在线性规划的理论与计算中都是十分重要的。应该指出, 这里给出的表是对一个特殊的可行基B=(2…,P)而言。但所得结果具有普遍适用 性。如不限制基变量是前m个,引入以下符号:设S∈{,2,…,n}是基变量下标集合, R={1,2…,m}S是非基变量下标集合,这样基变量{x|i∈s}的典式可以写成 ∑x,i∈S x≥0J=12, mIn §2判别定理与换基迭代 (一)判别定理 对于给定的基B及相应的基可行解X,可针对典式作出如下判断 定理1若所有的≤0,则X是最优解。 证明:因,≤0,j=m+1…,n,故对任意可行解 f()=f-∑x≥f=f(X),故X是最优解。 可见,在进行最优性检验时,数,起着重要的判别作用称之为检 验数。为明确起见称λ为相应于变量x的检验数基变量的检验数均视为0 定理2若有某个n+>0且Bm≤0,i=1,…,m,则(LP)无最优解 证明:根据典式(*)可作一新的可行解X b,x=0,(>m,j≠m+k) 6Bm+k20i=1, 将X代入(7),得
66 基变量 1 x 2 x m x m 1 x + n x 1 x 2 x m x 1 B A− 1 B b− f CB 1 B A− -C CB 1 B b− 单纯形表的这种矩阵形式在线性规划的理论与计算中都是十分重要的。应该指出， 这里给出的表是对一个特殊的可行基 1 ( , , ) B P P = m 而言。但所得结果具有普遍适用 性。如不限制基变量是前 m 个，引入以下符号：设 S {1,2, , }n 是基变量下标集合， R= {1, 2, , }n /S 是非基变量下标集合，这样基变量 { | } i x i s 的典式可以写成 0 1, 2, , min i i ij j j R j j j j R x x i S x j n f f x = − = = − （11） §2 判别定理与换基迭代 （一） 判别定理 对于给定的基 B 及相应的基可行解 X ，可针对典式作出如下判断。 定理 1 若所有的 0 j ,则 X 是最优解。 证明：因 0 j , j m n = +1, , , 故 对 任 意 可 行 解 X ， 有 1 ( ) ( ) n j j j m f X f x f f X = + = − = ，故 X 是最优解。 可见，在进行最优性检验时，数 j 起着重要的判别作用,称之为检 验数。为明确起见称 j 为相应于变量 j x 的检验数,基变量的检验数均视为 0。 定理 2 若有某个 0 m k + 且 0, 1, , im k + =i m ，则（LP）无最优解 证明：根据典式（*）可作一新的可行解 1 X : 1 m k x + = , 1 0,( , ) j x j m j m k = + 1 0 1, , i i im k x i m = − = + 将 1 X 代入 (7) ，得
当6→+∞时,因n>0,故∫→-∞。由此可知f在可行解集合中无下 界。所以(LP)无最优解。 (二)换基迭代 设初始基可行解X不满足定理1和2的条件。即存在某Am+k>0,且对 某一i(1≤i≤m)有Bn4>0。则根据典式可造一新的基可行解X xk=0≥0,x=0,(j>m,j≠m+k) x=a- bmk i=1,…,m 这样的X自然满足(1),为了满足非负性条件(2),O的取法应满足 取b尽量大,即 0地n=B (12) 这时X为可行解。且其中至少有一个变量x1=a1-Bm+O=0。从而X的非0分量至多 是x,x2,…,x1,xm,x1…,x。以下往证H为基可行解。且在非退化情形下使目标函 数值严格下降 1、证X是基可行解。这只要证P…,P_,P,P1…,P线性无关。因已知 P,…,B,…P线性无关。故只须证明后面的向量组可由前一个线性表示就行了。首先由x 的典式有 B Into =BnkF1+…+BnB+…+ Bmk P Bn (注意f,…,P…P都是单位向量)。因Bn4≠0,故有 =-BnmP+…+1P+…-BmsP B 注意到P=BP(=1…,m),故以B乘上式两边就得到
67 m k f f = − + 当 → + 时，因 0 m k + ,故 f → − 。由此可知 f 在可行解集合中无下 界。所以（LP）无最优解。 （二） 换基迭代 设初始基可行解 X 不满足定理 1 和 2 的条件。即存在某 0 m k + ，且对 某一 i( 1 i m )有 0 im k + 。则根据典式可造一新的基可行解 1 X ： 1 1 0, 0,( , ) m k j x x j m j m k + = = + 1 1, , i i im k x i m = − = + 这样的 1 X 自然满足（1），为了满足非负性条件（2）， 的取法应满足 0 0 min im k i im k + + 取 尽量大，即 0 min im k i l im k lm k + + + = = （12） 这时 1 X 为可行解。且其中至少有一个变量 l lm k 0 l x = − = + 。从而 1 X 的非 0 分量至多 是 1 1 1 1 1 2 1 , , , , l m k x x x x − + ， 1 1 1 , , l m x x + 。以下往证 1 X 为基可行解。且在非退化情形下使目标函 数值严格下降。 1、证 1 X 是基可行解。这只要证 1 1 1 , , , , , , P P P P P l m k l m − + + 线性无关。因已知 1 , , , P P P l m 线性无关。故只须证明后面的向量组可由前一个线性表示就行了。首先由 X 的典式有 1 1 1 m k m k m k lm k l mm k m mm k P P P P + + + + + + = = + + + + （13） （注意 1 , , , P P P l m 都是单位向量）。因 0 lm k + ，故有 1 1 m k mm k 1 l m k m lm k lm k lm k P P P P + + + + + + = − + + + − 注意到 1 ( 1, , ) P B P j n j j − = = ，故以 B 乘上式两边就得到
Pim+k p P,+ B P 即P能被P1…,P1,Pk,P1…Pm线性表示,故是基可行解 2、证X在非退化情形是改进的基可行解。由(7)可得 f(X)=f-n0≤f=f(x") 而当X为非退化的基可行解时,由(12)知>0。于是f(x)0? 无解 是,取O Br>01 BI 以Bk为主元实行换基消元
68 1 1 m k mm k 1 l m k m lm k lm k lm k P P P P + + + + + + = − + + + − 即 Pl 能被 1 1 1 , , , , , , P P P P P l m k l m − + + 线性表示，故 1 X 是基可行解。 2、证 1 X 在非退化情形是改进的基可行解。由（7）可得 1 ( ) ( ) m k f X f f f X = − = + 而当 X 为非退化的基可行解时，由（12）知 0 。于是 1 f X f f X ( ) ( ) = 。即目标 函数严格下降。 以上 X 到 1 X 的更换基变量的过程，可以完全通过矩阵的初等交换，即 Guass 消去法 来实现。其实质就是把进基变量 m k x + 所对应的列向量变为单位向量（它的非 0 分量 1 位于 离基变量 所在的行）。沿用 Guass 消元的术语，元素 lm k + 称为主元（在单纯形表上常用* 号来标识）， Pm k + 称为主元列。上述变换亦称转轴变换，或 ( , ) l m k + 旋转变换。以上过程 完全可以在单纯形表中进行，其中目标函数行可看作是第 m+1 个约束方程，同样参加消元 变换。 这样，对改进解 1 X 。用定理 1 和 2 加以考察。若仍不满足，则继续重复上述换基过程。 如此迭代下去，便得一基可行解序列。其目标函数值在非退化情形，依次严格下降，因而序 列中不可能有重复的项。由于基可行解是有限的,故迭代至有限步必满足定理 1 或 2。 这个迭代过程可以用粗略的框图表示如下： 无解 否 最优解 是 是，取 min{ | 0} l i ik i lk ik = = 否 → k 0 基可行解 是否所有 0? j 是否有 0? ik 以 lk 为主元实行换基消元
例1 5x1+3x2+x3 200 x1+x2+x4 +5x 此即第一章例1的标准形式。 列表迭代如下 3 100 0 X4 00 (检验数中,若有两个以上大于0,以往的迭代一般取其中最大的) X4 163 0 55 f 0 x 2 0 f 0 0 175 表3已是最优表,故最优解和最优值分别为 (25,250,0,20)2,f(X)=-1 此与用图解法得到的结果相同 §3初始基可行解的求法
69 例 1 1 2 3 1 2 4 1 2 5 1 2 5 3 200 50 3 5 220 0, 1, ,5 min 4 3 i x x x x x x x x x x i f x x + + = + + = + + = = = − − 此即第一章例 1 的标准形式。 列表迭代如下： 1 x 2 x 3 x 4 x 5 x 3 x 4 x 5 x 5 * 3 1 0 0 1 1 0 1 0 3 5 0 0 1 200 50 220 f 4 3 0 0 0 0 （检验数中，若有两个以上大于 0，以往的迭代一般取其中最大的） 1 x 2 x 3 x 4 x 5 x x1 4 x 5 x 1 5 3 5 1 0 0 0 5 2 * 5 1 1 0 0 5 16 5 3 − 0 1 40 100 f 0 5 3 5 4 − 0 0 −160 1 x 2 x 3 x 4 x 5 x x1 x2 5 x 1 0 2 1 2 3 − 0 0 1 2 1 − 2 5 0 0 0 1 −8 1 25 20 f 0 0 2 1 − 2 3 − 0 -175 表 3 已是最优表，故最优解和最优值分别为 T x (25,25,0,0,20) * = , ( ) 175 * f X = − 此与用图解法得到的结果相同。 §3 初始基可行解的求法 10 25
回过头来,研究初始基可行解的求法,在这里我们给出两种处理方法。它们都是通过引 入所谓人工变量的办法来实现的。 (一)大M法 设问题是标准的: AX= 6 X≥0 (14) mIn f=CX 为了获得一个初始基可行解。引入人工变量y…y令y=(y1…,yn)。考察另一个 线性规划问题 AX +y=b X≥0,y≥0 (15) min z=CX+ME1 其中M>0是一个充分大的数,E=(1,1,…,1) 定理2 是问题(15)的最优解。若y°=0,则X是问题(14)的最优解。若 y≠0,则问题(14)无可行解。反之,若X是问题(14)的最优解,则是问题(15) 的最优解 证明设x是(14)的任一可行(X(15)的一个可行解。于是当y=0时, 因是(15)的最优解,而是(15)的可行解。故 CX°=CX0+MY0≤CX+MEO=CX 所以X是(14)的最优解 X 若y≠0设(14)有一可行解X,则。是(15)的一个可行解。于是 CX+MEy≤CX 因y≠0,故当M充分大时,上式不可能成立。所以这时(14)没有可行解。 反之,若X是(14)的最优解。设是(15)的任一可行解,则 、若y=0,则Ⅹ是(14)的一个可行解。于是CX≤CX=CX+MEy
70 回过头来，研究初始基可行解的求法，在这里我们给出两种处理方法。它们都是通过引 入所谓人工变量的办法来实现的。 （一） 大 M 法 设问题是标准的： 0 min AX b X f CX = = (14) 为了获得一个初始基可行解。引入人工变量 1 , , m y y 令 1 ( , , )T m y y y = 。考察另一个 线性规划问题 0, 0 min AX y b X y z CX MEy + = = + (15) 其中 M 0 是一个充分大的数，E=(1,1, ,1)。 定理 2 设 X y 是问题（15）的最优解。若 y =0,则 X 是问题（14）的最优解。若 y 0，则问题（14）无可行解。反之，若 X 是问题（14）的最优解，则 0 X 是问题（15） 的最优解。 证明 设 x 是（14）的任一可行解，则 0 X 是（15）的一个可行解。于是当 y =0 时， 因 X y 是（15）的最优解，而 0 X 是（15）的可行解。故 CX0=CX0+MEY0≤CX+ME0=CX 所以 X 是（14）的最优解。 若 y 0,设（14）有一可行解 X，则 0 X 是（15）的一个可行解。于是 CX MEy CX + 因 y 0,故当 M 充分大时，上式不可能成立。所以这时（14）没有可行解。 反之，若 X 是（14）的最优解。设 X y 是（15）的任一可行解，则 1、若 y=0，则 X 是(14）的一个可行解。于是 CX CX CX MEy = +
2、若y≠0,由于M0可以充分大,所以必有CX≤CX+MEy 因此 是(15)的最优解 0 推论若问题(15)无最优解,则问题(14)亦无最优解。 上述定理说明,为了获得(14)的最优解,可直接去求解(15)。而(15)的初始基可 行解是明显的。此法的缺点是,其中M较难确定,给上机计算带来麻烦。但手算时不必具 体给出,只要把它作为一个足够大的正参数来处理就行了。 例2 x1+2x2+3 x1+x2+5x3 +2x,+x3+ ≥0,j=1, 2 3x3+x 添加的人工变量不必非要m个,其实根据问题具体情况,只要在初始表中能凑成一个 单位矩阵I就可以了。此例只须增加二个人工变量y1y2即可。具体迭代过程如下: x 2 01 -1-M 0 00 f3M+23M+48M+40 35M+10 55 001M00101515 7 3 y 4 2 M+27M+16 8M+4 f 0 00 3M-6 6 7 0 473705 7 7 6 16 90 f 7
71 2、若 y 0，由于 M>0 可以充分大，所以必有 CX CX MEy + 因此 0 0 X 是（15）的最优解。 推论 若问题（15）无最优解，则问题（14）亦无最优解。 上述定理说明，为了获得（14）的最优解，可直接去求解（15）。而（15）的初始基可 行解是明显的。此法的缺点是，其中 M 较难确定，给上机计算带来麻烦。但手算时不必具 体给出，只要把它作为一个足够大的正参数来处理就行了。 例 2 1 2 3 1 2 3 1 2 3 4 1 2 3 4 2 3 15 2 5 20 2 10 0, 1, ,4 min 2 3 j x x x x x x x x x x x j f x x x x + + = + + = + + + = = = − − − + 添加的人工变量不必非要 m 个，其实根据问题具体情况，只要在初始表中能凑成一个 单位矩阵 I 就可以了。此例只须增加二个人工变量 1 2 y y, 即可。具体迭代过程如下： 1 x 2 x 3 x 4 x 1 y 2 y x4 1 2 1 1 0 0 1 2 3 0 1 0 2 1 5 0 0 1 10 15 20 f 1 3 3 -1 -M -M 0 x4 y1 y2 1 2 1 1 0 0 1 2 3 0 1 0 2 1 5 * 0 0 1 10 15 20 f 3M+2 3M+4 8M+4 0 0 0 35M+10 4 x 1 y 3 x 5 3 5 9 0 1 0 5 1 − 5 1 − * 5 7 0 0 1 5 1 − 5 2 5 1 1 0 0 5 1 6 3 4 f 5 − M + 2 5 7M +16 0 0 0 5 8 + 4 − M 3M-6 4 x 2 x 3 x * 7 6 0 0 1 7 9 − 7 4 7 1 − 1 0 0 7 5 7 3 − 7 3 0 1 0 7 1 − 35 10 7 15 7 15 7 25 f 7 6 0 0 0 ) 7 16 − (M + 7 4 − M + 7 90 −
7 2 001 0 15 至此,最优解和最优值分别是 555 X=22000=15 (二)二阶段法 构造一个辅助问题 b X≥0,y≥0 mn=∑y 问题(14)和(16)的解之间有如下关系 定理4若(16)的最优基可行解为 0),则x是(14)的一个可行解。若(16 的最优基可行解为 且Y°≠0,则(14)没有可行解。 证明前一结论显然成立,下面只证后者。用反证法。设X为(14)的一个可行解, 则0是(16的一个可行解。它使目标函数z取0值但此时(16)的最优值z=∑y> 产生矛盾。故(14)不可能有可行解。 定理4的一个前提是(16)有最优解。这是不成问题的。显然,(16)有一个现成的基 可行解X=b,=1…m,X=0,又因目标函数值z=∑≥0。它在可行解集合上显然有 下界0。故必有最优解(单纯形迭代只有两种结果:一是有最优解。一是可行解无下界)。 (16)的初始单纯形表具如下形式 y 0
72 1 x 2 x 3 x 1 0 0 6 7 2 3 − 3 2 0 1 0 6 1 2 1 3 1 − 0 0 1 2 1 − 2 1 0 2 5 2 5 2 5 f 0 0 0 -1 − M −1 − M -15 至此，最优解和最优值分别是 ,0,0,0) 2 5 , 2 5 , 2 5 ( * X = T , 15 * f = − （二）二阶段法 构造一个辅助问题： 1 0, 0 min m i i AX y b X y z y = + = = (16) 问题（14）和（16）的解之间有如下关系 定理 4 若（16）的最优基可行解为 0 X ，则 X 是（14）的一个可行解。若（16） 的最优基可行解为 X Y ，且 Y 0 ，则（14）没有可行解。 证明 前一结论显然成立，下面只证后者。用反证法。设 X 为（14）的一个可行解， 则 0 X 是（16）的一个可行解。它使目标函数 z 取 0 值。但此时（16）的最优值 z= 1 m i i y = = >0。 产生矛盾。故（14）不可能有可行解。 定理 4 的一个前提是（16）有最优解。这是不成问题的。显然，（16）有一个现成的基 可行解 , 1, , Y b i m i i = = ，X=0，又因目标函数值 z 1 m i i y = = 0。它在可行解集合上显然有 下界 0。故必有最优解（单纯形迭代只有两种结果：一是有最优解。一是可行解无下界）。 （16）的初始单纯形表具如下形式： 1 y … m y 1 x … n x 1 y m y 1 11 a … n a1 … … … 1 am1 … amn 1 b mb z 0 … 0 = m i i a 1 1 … = m i ain 1 = m i i b 1