[企业管理]MBA运筹学2第二-五章线性规划

1、irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999第二三四五章第二三四五章 线性规划线性规划2.1 线性规划问题与标准形式线性规划问题与标准形式2.2 线性规划问题的几何解释线性规划问题的几何解释2.3 单纯型法方法单纯型法方法irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999问题的提出（问题的提出（1）【例】派公司是一个生产高尔夫器材的小型公司，公司决定生产中高价位的高尔夫袋。产品的生产过程有四个程序：切割并印染原材料、缝合、成型、检查和包装，不同价位高尔夫袋生产程序的耗时

2、信息如下表，表中还列出了派公司在本轮生产过程中每个部门的最大生产时间。irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999问题的提出（问题的提出（2）会计部门的数据表明，生产一个标准袋的利润是10美元，生产一个高级袋的利润是9美元。如何安排两种产品的生产才能使公司获得最大利润？耗时/标准袋耗时/高档袋最大生产时间切割印染0.70.71 1630630缝合0.50.55/65/6600600成型1 12/32/3708708检查包装0.10.10.250.25135135irwin/mcgraw-hill the mcgraw-hill

3、companies, inc., 1999问题的提出（问题的提出（3）设x1、x2分别为两种高尔夫袋的生产量，则该计划问题可用如下数学模型表示为：0,13525. 01 . 07083/26006/55 . 06307 . 0. .910max212121212121xxxxxxxxxxtsxxsirwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.1 线性规划问题与标准形式线性规划问题与标准形式 典例典例1-生产计划问题生产计划问题例例2. 某工厂在计划期内要生产产品i和产品ii这两种产品，已知生产单位产品所需的设备台时及a、b两种

4、设备计划期的有效台时，如下表：问如何安排生产最有利？ 产品 i 产品 ii 设备有效台时 设备 a 2 2 8 设备 b 0 2 4 单位产品利润 1 元 2 元 解 设产品i和产品ii的产量分别为x1和x2件, 利润为z, 则: z = x1 + 2 x2max目标函数 2 x1 + 2 x2 8 0 x1 + 2 x2 4 x1 , x2 0约束条件s.t.非负条件irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999abov

5、e,irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999 典例典例2-配料问题配料问题 z = 3x1 + 2 x2min目标函数 12 x1 + 3 x2 4 2 x1 + 3 x2 2 3 x1 + 15 x2 5 x1 + x2 = 1 x1 , x2 0约束条件s.t.irwin/mcgraw-hill the

6、mcgraw-hill companies, inc., 1999典例典例3-食谱问题食谱问题例3食品营养成份大米白菜鸡蛋猪肉营养成份的需要量(周)蛋 白 质a11a12a13a14b1某维生素a21a22a23a24b2某矿物质a31a32a33a34b3单 价(元)c1c2c3c4问在满足营养的条件下,如何安排食谱最有利?解:设每人每周食用大米、白菜、鸡蛋、猪肉的数量分别为x1、 x2、 x3、 x4z=c1x1+ c2x2+ c3x3+ c4x4mina11x1+ a12x2+ a13x3+ a14x4 b1=a21x1+ a22x2+ a23x3+ a24x4 = b2a31x1+ a

7、32x2+ a33x3+ a34x4 = b3x1, x2 , x3 , x4 0irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999 食谱问题的拓展食谱问题的拓展食品营养成份大米白菜鸡蛋猪肉食品n营养成份的需要量(周)蛋 白 质a11a12a13a14a1nb1某维生素a21a22a23a24a2nb2某矿物质a31a32a33a34a3nb3营养成份 mam1am2am3am4amnbn单 价(元)c1c2c3c4cn问在满足营养的条件下,如何安排食谱最有利?z=c1x1+ c2x2+ c3x3+ c4x4 + . + cnxnmi

8、na11x1+ a12x2+ a13x3+ a14x4 +.+ a1nxn = b1a21x1+ a22x2+ a23x3+ a24x4 +.+ a2nxn = b2a31x1+ a32x2+ a33x3+ a34x4 +.+ a3nxn = b3am1x1+ am2x2+ am3x3+ am4x4 +.+ amnxn = bmx1, x2 , x3 , . xn 0数学模型irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999new bedford steel炼焦煤供应问题 ashleybedfordconsoldunbyearlamf

9、lorencegastonhopt 供应量 (千吨/年） 300 600 510 655 575 680 450490工会（u）/非工会（n） u u n u n u n n 卡车（t）/ 铁路（r） r t r t t t r r可燃率（%） 15 16 18 20 21 22 23 25 价格 (/ 吨） 49.50 50.00 61.00 63.50 66.50 71.00 72.5080.00new bedford steel (nbs)是一家小型的炼钢企业。炼焦煤是一家小型的炼钢企业。炼焦煤(coking coal)是是nbs公司炼钢时所必需的一种原材料，每年的需求量是公司炼钢时所必

10、需的一种原材料，每年的需求量是100至至150万吨。现在到了万吨。现在到了该公司计划明年生产的时候了，他们收到了来自八家供应商的报价。该公司计划明年生产的时候了，他们收到了来自八家供应商的报价。irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999new bedford steel炼焦煤供应问题irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999nbs供应问题的数学表达变量：a = 从 ashley 处定购的炼焦煤量（千吨）b = 从 bedford 处定购的炼焦煤量（千吨）c =

11、 从 consol 处定购的炼焦煤量（千吨）d = 从 dunby 处定购的炼焦煤量（千吨）e = 从 earlam 处定购的炼焦煤量（千吨）f = 从 florence处定购的炼焦煤量（千吨）g = 从 gaston 处定购的炼焦煤量（千吨）h = 从 hopt 处定购的炼焦煤量（千吨）irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999供应成本成：49.5a + 50b + 61c + 63.5d + 66.5e + 71f + 72.5g + 80h供应约束：a + b + c + d + e + f + g + h = 1,22

12、5工会煤矿的约束：a + b c + d e + f g h 0卡车运输量约束：b + d + e + f 720火车运输量约束：a + c + g + h 650平均可燃率约束：可改写成： 4a 3b c + d + 2e + 3f + 4g + 6h 0各煤矿的炼焦煤供应量约束：a 300，b 600，c 510，d 655，e 575，f 680，g 450， h 490非负约束：a 0，b 0，c 0，d 0，e 0，f 0，g 0，h 019hgfedcbah25g23f22e21d20c18b16a15irwin/mcgraw-hill the mcgraw-hill compan

13、ies, inc., 1999nbs的炼焦煤供应问题的线性最优化模型的炼焦煤供应问题的线性最优化模型minimize cost=49.5a+50b+61c+63.5d+66.5e+71f+72.5g+80hsubject to：supply：a + b + c + d + e + f + g + h = 1,225union：a + b c + d e + f g h 0truck：b + d + e + f 720rail： a + c + g + h 650vol： 4a 3b c + d + 2e + 3f + 4g + 6h 0acap：a 300bcap：b 600ccap：c 51

14、0dcap：d 655ecap：e 575fcap： f 680gcap：g 450hcap：h 490nonnegativity conditions：a0, b0, c0, d0, e0, f0, g0, h0irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999nbs的炼焦煤供应问题的线性最优化模型的炼焦煤供应问题的线性最优化模型求解，得：a= 55千吨， b=600千吨， c= 0千吨， d= 20千吨， e=100千吨， f= 0千吨， g=450千吨， h= 0千吨；最小成本 = 73,267.50千美元；平均供应成本 = 7

15、3,267.50 / 1,225 = 59.81美元/吨irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999二、线性规划数学模型的几种表达形式二、线性规划数学模型的几种表达形式一般形式一般形式目标函数： max （min） z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn

16、 0简写形式形式目标函数： max （min） z = 约束条件： s.t. （ =, ）bi , i=1,2,. m xj 0 , j=1 , 2 , . n 1njjjc x1nijjjaxirwin/mcgraw-hill the mcgraw-hill companies, inc., 1999向量形式c=(c1 , c2, , cn ) 价值向量,二、线性规划数学模型的几种表达形式二、线性规划数学模型的几种表达形式12mbbbb限定向量12jjjmjaapa变量xj对应的系数列向量12nxxxx1(min)(,)0njjjm axzcxp xbx irwin/mcgraw-hill

17、the mcgraw-hill companies, inc., 1999二、线性规划数学模型的几种表达形式二、线性规划数学模型的几种表达形式矩阵形式111212122212nnmmmnaaaaaaaaaa约束条件系数矩阵max(min)( , )0zcxaxbx irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999第二节第二节 线性规划问题的标准形式线性规划问题的标准形式一、标准形式标准形式目标函数： max z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + + a1n

18、xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0max0zcxaxbx或即:同时满足如下四个条件:目标函数求极大约束条件全为等式约束条件右端常数项全为非负变量取值全为非负irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.1 线性规划问题与标准形式线性规划问题与标准形式 为了今后讨论的方便，我们称以下两种形式的线性规划问题为线性规划的规范形式（canonical form）：minzctxs.t.axb x0m

19、axzctx s.t.axbx0 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.1 线性规划问题与标准形式线性规划问题与标准形式 而称以下的形式为标准形式（standard form）： max zctxs.t.axb x0 对于各种非标准形式的线性规划问题，我们总可以通过以下的变换，将其转化为标准形式。1 极小化目标函数的问题2 约束条件不是等式的问题3 变量无符号限制的问题irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 极小化目标函数的问题极小化目标函数的问

20、题设目标函数为nnxcxcxcz2211min令zz，则以上极大化问题和极小化问题有相同的最优解，即nnxcxcxcz2211 max但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即minzmax z irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992 约束条件不是等式的问题约束条件不是等式的问题设约束条件为 ( i=1,2,m)可以引进一个新的变量xn+i，使它等于约束右边与左边之差显然xn+i也具有非负约束，即xn+i0，这时新的约束条件成为当约束条件为bxaxaxaninii2211xbax

21、axaxniiiiinn()1122iinniniibxxaxaxa2211axaxaxbiiinni1122irwin/mcgraw-hill the mcgraw-hill companies, inc., 1999 2 约束条件不是等式的问题约束条件不是等式的问题时，类似地令则同样有xn+i0，新的约束条件成为ininiiinbxaxaxax)(2211 为了使约束由不等式成为等式而引进的变量xn+i称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。xa xa xa xbn iiiinni()1122a xaxa xxbiiinn

22、n ii1122irwin/mcgraw-hill the mcgraw-hill companies, inc., 19993 变量无符号限制的问题变量无符号限制的问题 在标准形式中，每一个变量都有非负约束。当一个变量xj没有非负约束时，可以令xj=xj-xj” 其中xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当xj的符号取决于xj和xj”的大小。irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.2 线性规划问题的几何解释线性规划问题的几何解释对于只有两个变量的线性规划问题，可以在二维直角坐标平面上表示线性

23、规划问题。max z= x1+3x2s.t x1+x26 -x1+2x28 x1, x2 0例1.4.1的线性规划问题的可行域如图1.4.1中阴影部分所示。irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.2 线性规划问题的几何解释线性规划问题的几何解释123456xz=0z=3z=6z=9z=12z=15.3013456约 束 条 件 （ 1）约 束 条 件 （ 2）c-1-8-2-3-4-5-6-7x21irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.2 线性规

24、划问题的几何解释线性规划问题的几何解释在以上问题中，目标函数等值线在平行移动过程中与可行域的最后一个交点是b点，这就是线性规划问题的最优解，这个最优解可以由两直线x1+x2=6-x1+2x2=8的交点求得xx12431 43, 最优解的目标函数值为 346314334321xxzirwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.2 线性规划问题的几何解释线性规划问题的几何解释定义定义1.4.3 设s是n维空间中的一个点集。若对任意n维向量x1s，x2s，且x1x2，以及任意实数（01），有x=x1+(1-)x2s则称s为n维空间中

25、的一个凸集。点x称为点x1和x2的凸组合。以上定义有明显的几何意义，它表示凸集s中的任意两个不相同的点连线上的点（包括这两个端点），都位于凸集s之中。图1.4.2表示二维平面中一些凸集和非凸集的例子。irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.2 线性规划问题的几何解释线性规划问题的几何解释xxxxxx121212xxxxxx121212(a)凸集 (b)凸集 (c)凸集 (d)非凸集 (e)非凸集(d)非凸集 (f)非凸集 irwin/mcgraw-hill the mcgraw-hill companies, inc.,

26、 19992.2 线性规划问题的几何解释线性规划问题的几何解释定义定义1.4.4 设s为一凸集，且xs，x1s，x2s。对于01，若x x=x1+(1-)x x2则必定有x=x x1=x x2，则称x为s的一个极点。运用以上的定义，线性规划的可行域以及最优解有以下性质：1、若线性规划的可行域非空，则可行域必定为一凸集。2、若线性规划有最优解，则最优解至少位于一个极点上。这样，求线性规划最优解的问题，从在可行域内无限个可行解中搜索的问题转化为在其可行域的有限个极点上搜索的问题。最后，来讨论线性规划的可行域和最优解的几种可能的情况。1、可行域为封闭的有界区域2、可行域为非封闭的无界区域可行域为非封

27、闭的无界区域irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.2 线性规划问题的几何解释线性规划问题的几何解释3、可行域为空集，因而没有可行解。以上几种情况的图示如下：(a)可行域有界 (b)可行域有界 (c)可行域无界 唯一最优解 唯一最优解 唯一最优解 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.2 线性规划问题的几何解释线性规划问题的几何解释(d)可行域无界 (e)可行域无界 (f)可行域为空集 多个最优解 目标函数无界 无可行解 图1.4.3线性规划可行

28、域和最优解的几种情况 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.3 单纯形法方法单纯形法方法 设线性规划的约束条件为ax=bx0其中a为mn的矩阵，nm，秩a=m，b为m1向量。定义定义2.6 线性规划的基(basis) 设b是a矩阵中的一个非奇异的mm子矩阵，则称b为线性规划的一个基(矩阵).定义定义2.72.7设b是线性规划的一个基（矩阵），线性规划的解:称为线性规划与基b b对应的基础解。若其中b b-1b b0 0，则称以上的基础解为一基础可行解，相应的基b b称为可行基。定理定理2.1 线性规划的基础可行解就是可

29、行域的极点。线性规划的基础可行解就是可行域的极点。 0bbxxx1nbirwin/mcgraw-hill the mcgraw-hill companies, inc., 19992.3 单纯形法方法单纯形法方法1 单纯形原理的矩阵描述单纯形原理的矩阵描述 2 单纯形表单纯形表 3 初始基础可行解初始基础可行解 4 退化和循环退化和循环 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 单纯形原理的矩阵描述单纯形原理的矩阵描述设标准的线性规划问题为max z=ctxs.t.ax=b(1.6.1)x0并设a=a1，a2，an其中a

30、j(j=1，2，n)是a矩阵的第j个列向量。b=a1，a2，am是a的一个基。irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 单纯形原理的矩阵描述单纯形原理的矩阵描述这样，矩阵a可以分块记为a=b，n，相应地，向量x和c可以记为 并设r为非基变量的下标集合。利用以上的记号，（1.6.1）中的等式约束ax=b可以写成bxb+nxn=b即xb=b-1b-b-1nxn(1.6.2)这就是在约束条件中，基变量用非基变量表出的形式。 xxxcccbnbn,irwin/mcgraw-hill the mcgraw-hill companie

31、s, inc., 19991 单纯形原理的矩阵描述单纯形原理的矩阵描述对于一个确定的基b，目标函数z可以写成 ztbtntbnbtbntncx ccxxcxc x,.将(1.6.2)式代入以上目标函数表达式，得到目标函数z用非基变量表出的形式 zbtnntnbtbtntncbbbnxc xc bbc bncx()()1111irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 单纯形原理的矩阵描述单纯形原理的矩阵描述(1.6.2)和(1.6.3)式表示，非基变量的任何一组确定的值，基变量和目标函数都有一组确定的值与之对应。特别，当xn

32、=0时，相应的解 xxxbb0bn1就是对应于基b的基础解。如果b是一个可行基，则有 xxxbb00bn1irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 单纯形原理的矩阵描述单纯形原理的矩阵描述下面我们来详细说明如何实现以上步骤。步骤1、获得初始基础可行解的一般化的方法将在下一节中叙述。在这里，我们假定已经获得了一个初始的可行基b，基b对应的基础解为 xxxbb0bn1当前的目标函数值为zbtbbt01c xc b birwin/mcgraw-hill the mcgraw-hill companies, inc., 19991

33、 单纯形原理的矩阵描述单纯形原理的矩阵描述步骤2、确定进基的非基变量xk由(1.6.1)可知，当前目标函数值用非基变量用非基变量表出的形式是 zzcxbtbtntnbtjjjj rc b bc b ncxc b a1101()()令c b abtjjz1irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 单纯形原理的矩阵描述单纯形原理的矩阵描述则 rjjjjxczzz)(0如果对于所有jr，有zj-cj0，则任何非基变量xj的值由0开始增加都不会使z减少，因此当前基b已是最优基，相应的基础可行解xxxb b0bn1如果有kr，使zk

34、-ck0，则非基变量xk的增加将会使目标函数值减少。为了使目标函数值下降得快一些，一般选取满足 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 单纯形原理的矩阵描述单纯形原理的矩阵描述 zczc zckkj rjjjjmax|0的非基变量xk为进基变量。由于除xk以外的非基变量的值均保持为0不变，这时目标函数可以表示为 zzzcxzzcxjjjj rkkk00()()步骤3、确定基变量中离基的变量xbr在(1.6.2)中，令irwin/mcgraw-hill the mcgraw-hill companies, inc., 19

35、991 单纯形原理的矩阵描述单纯形原理的矩阵描述 bb byba1111bbbyyyrmjjjrjmj则(1.6.2)可以表示为 xbba xbybjjj rjjj rx1当进基变量xk的值由0增加到某一正值，其余非基变量均保持为0时，上式成为 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 单纯形原理的矩阵描述单纯形原理的矩阵描述xbybkkx即 xxxbbbyyyxbbrbmrmrkmkk111kirwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 单纯形原理的矩阵

36、描述单纯形原理的矩阵描述在(1.6.6)中，有以下几种情形：（1）如果向量yk中所有的分量yik0，则xk的增加将不会使任何xbi(i=1，2，.，m)减少，这时xk可无限增加，同时所有的基变量仍保持非负。同时由于xk在目标函数中的系数zk-ck0，由(1.6.5)可知当xk增加时目标函数将无限减少，即目标函数无界。（2）如果向量yk中至少有一个分量yik0，则xk由0开始增加将会使相应的基变量xbi的值由当前的值bi开始减少。当xk增加到 min|10 i miikikrrkbyybyirwin/mcgraw-hill the mcgraw-hill companies, inc., 199

37、91 单纯形原理的矩阵描述单纯形原理的矩阵描述相应的基变量xbr=0，而其余的基变量xbi0（i=1，2，.，m，ir），这时基变量xbr离基，它在基b中相应的列向量abr将换出基矩阵，进基变量xk在a矩阵中相应的列向量ak将取代基矩阵b中abr的位置，得到新的可行基 b=ab1，ab2，abr-1，ak，abr+1，abm新的基b相应的基变量的值为 xbbbrbmkkmmkkrrkrrkmmkrrkxxxbyxxbyxbybybybyby111k11kirwin/mcgraw-hill the mcgraw-hill companies, inc., 19991 单纯形原理的矩阵描述单纯形原

38、理的矩阵描述b相应的非基变量的值为xn=0b对应的目标函数值为步骤4、由新的基b重新确定非基变量集合r，并重新计算(1.6.4)以判定b是否为最优基。若不是，计算(1.6.4)(1.6.8)以实现进一步的基变换。 zzzcxzzcbykkkkkrrk00()()irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992 单纯形表单纯形表 单纯形算法的实质是将非基变量视为一组参数，并将目标函数和基变量都表示成为由非基变量表示的形式。即（1.6.2）和（1.6.3）两式。这样就可以讨论当非基变量变化时，目标函数和基变量随之变化的情况。我们可以用

39、一个矩阵来表示单纯形法迭代中所需要的全部信息，这就是所谓的单纯形表。设线性规划问题为max z=ctxs.t. ax=b(1.7.1)x0并设b是a的一个可行基，并记a=b b，n，相应地将目标函数系数向量c以及变量x表示为 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992 单纯形表单纯形表 cccxxxbnbn,则(1.7.1)可表为0xxbxxnbxxccnbnbnbtntbtsz,. .max即 irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992 单纯形表单纯形表

40、 zbtbntnbnbnc xc xbxnxbxx00,将(1.7.3)的系数写成矩阵形式，有zxbxnrhs10-cbt-cnt0bnbirwin/mcgraw-hill the mcgraw-hill companies, inc., 19992 单纯形表单纯形表称以上矩阵为线性规划问题的系数矩阵（并不是单纯形表）。为了将约束中的基变量用非基变量表出，用b-1左乘以上系数矩阵的后m行，得到 zxbxnrhs1-cbt0-cnt0ib-1nb-1b为了将第一行中的目标函数z用非基变量xn表出，在矩阵的后m行左乘cbt后加到第一行上，消去基变量在目标函数中的系数，得到irwin/mcgraw-hill the mcgraw-hill companies, inc., 19992 单纯形表单纯形表zxbxnrhs10tcbtb-1bcbtb-1n-cnt0ib-1nb-1b以上矩阵的第一行与(1.6.3)完全等价，后m行与(1.6.2)完全等价。这一矩阵称为与基b对应的单纯形表。单纯形表可以由系数矩阵经过一系列行变换得到，这些行变换使