《线性规划》034第二章22最优基可行解=续=第六次课

1、问题：若典式中有检验数问题：若典式中有检验数 ，但对应的系数，但对应的系数中却有正数，那么又有什么结论呢？中却有正数，那么又有什么结论呢？0r (1,2,)irbim 2.2 2.2 最优基可行解的求法最优基可行解的求法定理定理2.4 (P28)对于对于LP的一个基的一个基B，若，若 且且 ，则对应基则对应基B的基解的基解 x(0)便是便是LP的最优解。的最优解。10B b 10NBNc B N c 检验数非正检验数非正问题：当一个基可行解的非基变量的检验数不全非正时问题：当一个基可行解的非基变量的检验数不全非正时是是 否最优解？如何判别？否最优解？如何判别？情形一：情形一：定理定理2.5 (

2、P30)若基可行解若基可行解 x(0) 对应的典式中，有某个检验数对应的典式中，有某个检验数 ，且相应地且相应地 ，则，则LP无最优解无最优解(此时此时目标函数在可行域上无界目标函数在可行域上无界)。0 (1,2,)r ibim 0r 情形二：情形二：T12(,)rrmrbbb0r 00ib (1,2,)im (0)()f x若基可行解若基可行解 x(0)对应的典式中，有某个检验数对应的典式中，有某个检验数 ，而而 中至少有一个大于零，并且中至少有一个大于零，并且 ，则必存在另一基可行解，则必存在另一基可行解，其对应的目标其对应的目标函数值比函数值比 小。小。定理定理2.6 (P31)T12(

3、,)rrmrbbb0r 00ib (1,2,)im (0)()f x若基可行解若基可行解 x(0)对应的典式中，有某个检验数对应的典式中，有某个检验数 ，而而 中至少有一个大于零，并且中至少有一个大于零，并且 ，则必存在另一基可行解，则必存在另一基可行解，其对应的目标其对应的目标函数值比函数值比 小。小。情形二：情形二：定理定理2.6 (P31)2.2 2.2 最优基可行解的求法最优基可行解的求法注：注：(1)、定理定理2.6说明，对于一个说明，对于一个非退化非退化的基可行解，当有某的基可行解，当有某 个检验数个检验数 ，而对应系数，而对应系数 不全非正时不全非正时此基可行解必不是最优解此基可

4、行解必不是最优解，此时必，此时必存在改进的存在改进的基可行解。基可行解。0r (1,2,)irbim 问题：如何改进基可行解？问题：如何改进基可行解？定理定理2.6也说明，满足定理也说明，满足定理2.6的问题必有最优解！的问题必有最优解！ 对应基解中基变量值部分。对应基解中基变量值部分。 T110200,mbbbB b 对于对于LP的一个基可行解，如果其基分量值都是正的一个基可行解，如果其基分量值都是正的，就称它是一个的，就称它是一个；否则；否则(即基分量值有等即基分量值有等于零的于零的)，就称它为，就称它为。非退化非退化2.2 2.2 最优基可行解的求法最优基可行解的求法s.t. 12345

5、12123412335min321532340(1,2,5)ifxxxxxxxxxxxxxxxxix B2对应的基解为对应的基解为 ，且为基可行解。，且为基可行解。(2)T(0,0,1,4,3)x 符合定理符合定理2.6，需改进基可行解。，需改进基可行解。非基变量非基变量x1的检验数的检验数1, 03 以例以例1(P28)为例来考虑：如何改进基为例来考虑：如何改进基(基可行解基可行解)？由由f=6-3x1+3x2可知，若将非基变量可知，若将非基变量x1变成基变量变成基变量(取值从取值从0变成变成正数，即正数，即x1逐渐增加逐渐增加)，可以使目标函数值减小。所以只要目标，可以使目标函数值减小。所

6、以只要目标函数的表达式中还存在有负系数的非基变量，就表明目标函数函数的表达式中还存在有负系数的非基变量，就表明目标函数值还有减小的可能，从而需要将非基变量与基变量进行对换。值还有减小的可能，从而需要将非基变量与基变量进行对换。把非基变量转换为基变量，称为进基。把非基变量转换为基变量，称为进基。此处此处x1作为进基变量作为进基变量基基B2对应的典式为：对应的典式为：s.t. 12121213425min633321834530 (1,2,5)ixxxfxxxxxxxxxi (2)对于基对于基B2=( p3，p4，p5 )2.2 2.2 最优基可行解的求法最优基可行解的求法基基B2对应的典式为：对

7、应的典式为：s.t. 12121213425min6 33321834530 (1,2,5)ixxxfxxxxxxxxxi (2)对于基对于基B2=( p3，p4，p5 )把非基变量转换为基变量，称为进基。把非基变量转换为基变量，称为进基。此处此处x1作为进基变量作为进基变量因为基变量总数是因为基变量总数是m , 所以换入一个之所以换入一个之后还必须换出一个。后还必须换出一个。把基变量转换为非基变量，称为离基。把基变量转换为非基变量，称为离基。x1为进基变量，但为进基变量，但x2仍为非基变量，故仍为非基变量，故x2=0。代入。代入、 、 式可得：式可得：怎样确定离基变量？怎样确定离基变量？由于

8、随着由于随着x1的增加，目标函数值在减小的增加，目标函数值在减小 ，当，当x1增加到最大增加到最大1/3时，时，目标函数会减到最小。目标函数会减到最小。34511113,48,3xxxxxx 为了保证解的可行性，需要为了保证解的可行性，需要3411511 3,4 8,3000 xxxxxx 解得解得11114,338xxx (舍去舍去)113x 即即而当而当x1 =1/3时，时， x3=0，故用非基变量，故用非基变量x1替换基变量替换基变量x3 ( x3离基离基)。1 4min,3 8 2.2 2.2 最优基可行解的求法最优基可行解的求法基基B2对应的典式为：对应的典式为：s.t. 12121

9、213425min6 33321834530 (1,2,5)ixxxfxxxxxxxxxi (2)对于基对于基B2=( p3，p4，p5 )把非基变量转换为基变量，称为进基。把非基变量转换为基变量，称为进基。此处此处x1作为进基变量作为进基变量因为基变量总数是因为基变量总数是m , 所以换入一个之所以换入一个之后还必须换出一个。后还必须换出一个。把基变量转换为非基变量，称为离基。把基变量转换为非基变量，称为离基。怎样确定离基变量？怎样确定离基变量？为了保证解的可行性，需要为了保证解的可行性，需要3411511 3,4 8,3000 xxxxxx 11 41min,3 83x 即即而当而当x1

10、=1/3时，时， x3=0，故用非基变量，故用非基变量x1替换基变量替换基变量x3 ( x3离基离基)。得到改进基为得到改进基为基基B1=( p1，p4，p5 ) B1恰为最优基恰为最优基=011m in0,1, 2, 3iiibbib bi0为典式为典式中约束方中约束方程的右端程的右端常数常数00min0,1,2,iriirrrsbbbimbb 若基可行解若基可行解 x(0)对应的典式中，有某个检验数对应的典式中，有某个检验数 ，而而 中至少有一个大于零，并且中至少有一个大于零，并且 ，则必存在另一基可行解，则必存在另一基可行解，其对应的目标其对应的目标函数值比函数值比 小。小。T12(,)

11、rrmrbbb0r 00ib (1,2,)im (0)()f x2.2 2.2 最优基可行解的求法最优基可行解的求法情形二：情形二：定理定理2.6 (P31) (2)、改进基可行解的求法、改进基可行解的求法(P32)注：注：、把对应于正检验数、把对应于正检验数r 的非基变量的非基变量xr 转变为基变量转变为基变量，称称 它为它为进基变量进基变量(或换入变量或换入变量)；或基可行解的转移或基可行解的转移、从原基变量中选取一个成为非基变量，称此变量为、从原基变量中选取一个成为非基变量，称此变量为离离 基变量基变量(或换出变量或换出变量)，此离基变量的下标，此离基变量的下标js由下列最小由下列最小

12、值出现在哪一行取得所确定：值出现在哪一行取得所确定：从而新的基阵与原基阵的差异在于：原基阵的列向量从而新的基阵与原基阵的差异在于：原基阵的列向量 被列向量被列向量pr所代替。所代替。sjpbir为为xr在典式中的正系数在典式中的正系数若基可行解若基可行解 x(0)对应的典式中，有某个检验数对应的典式中，有某个检验数 ，而而 中至少有一个大于零，并且中至少有一个大于零，并且 ，则必存在另一基可行解，则必存在另一基可行解，其对应的目标其对应的目标函数值比函数值比 小。小。T12(,)rrmrbbb0r 00ib (1,2,)im (0)()f x2.2 2.2 最优基可行解的求法最优基可行解的求法

13、情形二：情形二：定理定理2.6 (P31) (3)、从原基解的典式导出新基解的典式的方法、从原基解的典式导出新基解的典式的方法(P34)注：注：、若使用计算机编程求解、若使用计算机编程求解LP，可按照，可按照(2.33)(2.37)的的 公式编制程序，以实现旧典式向新典式的转换；公式编制程序，以实现旧典式向新典式的转换；、对简单问题用手工计算时，可以直接对原典式使用、对简单问题用手工计算时，可以直接对原典式使用 消去法消去法获得新典式。获得新典式。2.2 2.2 最优基可行解的求法最优基可行解的求法为得出为得出B0对应的典式，作如下步骤：对应的典式，作如下步骤：例例4(P35) 求解下列线性规

14、划问题：求解下列线性规划问题：s.t. 124135234235min232122250 (1,2,5)ifxxxxxxxxxxxxxi (1)对于对于B0=( p1，p4，p5 )第一个方程只有基变量第一个方程只有基变量x1，其系数为，其系数为1第二个方程只有基变量第二个方程只有基变量x4，其系数为，其系数为1第三个方程只有基变量第三个方程只有基变量x5，其系数为，其系数为1(1)、将方程、将方程的的(-2)倍加到方程倍加到方程中，得中，得(2)、从方程、从方程、中解出中解出x1、 x4，代入目标函数的表达式。代入目标函数的表达式。21322xxx 解题步骤：解题步骤：1、首先将原问题化为典

15、式、首先将原问题化为典式(消去法消去法)103020121001101A 解：该问题的解：该问题的系数矩阵为系数矩阵为12345(,)p p p p p 显然，显然，B0是一个基，因为是一个基，因为0102010001B 10 用它代替第一个约束方程；用它代替第一个约束方程；s.t. 23232352143min4222250 (1,2,5)ifxxxxxxxxxxxxi 2.2 2.2 最优基可行解的求法最优基可行解的求法所以，基阵所以，基阵B0对应的典式为：对应的典式为：解：解：在在B0对应的典式令非基变量对应的典式令非基变量x2=x3=0 , 得得21322xxx 1452,2,5xxx

16、 故故B0对应的基解为对应的基解为 ，且为基可行解。，且为基可行解。(0)T(2,0,0,2,5)x 例例4(P35) 求解下列线性规划问题：求解下列线性规划问题：s.t. 124135234235min232122250 (1,2,5)ifxxxxxxxxxxxxxi 解题步骤：解题步骤：2、根据定理、根据定理2.4、2.5、2.6判别此判别此 基可行解的最优性基可行解的最优性(1)对于对于B0=( p1，p4，p5 )也不满足定理也不满足定理2.5，但符合定理，但符合定理2.6，故需要改进基可行解。，故需要改进基可行解。对于基对于基B0，不符合定理，不符合定理2.4，故，故 x (0)不是

17、最优解。不是最优解。s.t. 23232352143min4222250 (1,2,5)ifxxxxxxxxxxxxi 从基从基B0=( p1，p4，p5 )对应的典式：对应的典式：2.2 2.2 最优基可行解的求法最优基可行解的求法解：解：可知，非基变量可知，非基变量x2对应的检验数对应的检验数2, 01 例例4(P35) 求解下列线性规划问题：求解下列线性规划问题：解题步骤：解题步骤：3、若非最优解，根据定理、若非最优解，根据定理2.6进行改进，直至最优基可行解。进行改进，直至最优基可行解。(2) 基基B0 改进到基改进到基B1故取故取x2为进基变量。为进基变量。此时此时122322bbb

18、 211, 120300bbb 225 于是于是0222 5min0min,1 1iiibbb 22202bb s=2，即最小值出现在第二，即最小值出现在第二行，对应第二个基变量行，对应第二个基变量x4故故s=2，js=4，则取，则取x4为离基变量。为离基变量。所以得到新基为所以得到新基为B1=( p1，p2，p5 )120011001 1102010011B 10 B1的确为基阵的确为基阵145xxx001,2,min0,irrriisrimbbbbb r=2s.t. 23123234235min4222250 (1,2,5)ifxxxxxxxxxxxxi 2.2 2.2 最优基可行解的求法

19、最优基可行解的求法为得出为得出B1对应的典式，作如下步骤：对应的典式，作如下步骤：例例4(P35)(3)对于对于B1=( p1，p2，p5 )第一个方程只有基变量第一个方程只有基变量x1，其系数为，其系数为1第二个方程只有基变量第二个方程只有基变量x2，其系数为，其系数为1第三个方程只有基变量第三个方程只有基变量x5，其系数为，其系数为1(1)、将方程、将方程的的2倍、倍、(-1)倍加到方程倍加到方程 、中去；中去；(2)、从方程、从方程中解出中解出x2，代入目标函数的表达式。代入目标函数的表达式。解：解：基基B0对应的典式：对应的典式：解题步骤：解题步骤：1、求出新基的典式、求出新基的典式(

20、消去法消去法)s.t. 34343134245min232622330 (1,2,5)ifxxxxxxxxxxxix 2.2 2.2 最优基可行解的求法最优基可行解的求法所以，基阵所以，基阵B1对应的典式为：对应的典式为：解：解：在在B1对应的典式令非基变量对应的典式令非基变量x3=x4=0 , 得得1256,2,3xxx 故故B1对应的基解为对应的基解为 ，且为基可行解。，且为基可行解。(1)T(6,2,0,0,3)x 解题步骤：解题步骤：2、根据定理、根据定理2.4、2.5、2.6判别判别 此基可行解的最优性此基可行解的最优性(3)对于对于B1=( p1，p2，p5 )但符合定理但符合定理

21、2.6，故需要改进基可行解。，故需要改进基可行解。对于基对于基B1，不符合定理，不符合定理2.4，故，故 x (1)不是最优解。不是最优解。s.t. 23232352143min4222250 (1,2,5)ifxxxxxxxxxxxxi 例例4(P35)基基B0对应的典式：对应的典式：s.t. 34343134245min232622330 (1,2,5)ifxxxxxxxxxxxix 从基从基B1=( p1，p2，p5 )对应的典式：对应的典式：2.2 2.2 最优基可行解的求法最优基可行解的求法解：解：可知，非基变量可知，非基变量x3对应的检验数对应的检验数3, 01 例例4(P35)

22、求解下列线性规划问题：求解下列线性规划问题：解题步骤：解题步骤：3、若非最优解，根据定理、若非最优解，根据定理2.6进行改进，直至最优基可行解。进行改进，直至最优基可行解。(4) 基基B1 改进到基改进到基B2故取故取x3为进基变量。为进基变量。此时此时123333bbb 323, 120300bbb 623 于是于是0333min0min3iiibbb 33301bb s=3，即最小值出现在第三，即最小值出现在第三行，对应第三个基变量行，对应第三个基变量x5故故s=3，js=5，则取，则取x5为离基变量。为离基变量。所以得到新基为所以得到新基为B2=( p1，p2，p3 )321100011

23、 2103012011B 30 B2的确为基阵的确为基阵125xxx001,2,min0,irrriisrimbbbbb r=3s.t. 34134234345min232622330 (1,2,5)ifxxxxxxxxxxxxi 2.2 2.2 最优基可行解的求法最优基可行解的求法为得出为得出B2对应的典式，作如下步骤：对应的典式，作如下步骤：例例4(P35)(5)对于对于B2=( p1，p2，p3)第一个方程只有基变量第一个方程只有基变量x1，其系数为，其系数为1第二个方程只有基变量第二个方程只有基变量x2，其系数为，其系数为1第三个方程只有基变量第三个方程只有基变量x3，其系数为，其系数

24、为1(1)、将方程、将方程加到方程加到方程中去；中去；(3)、从方程、从方程中解出中解出x3，代入方程代入方程与目标函数中去。与目标函数中去。解：解：基基B1对应的典式：对应的典式：解题步骤：解题步骤：1、求出新基的典式、求出新基的典式(消去法消去法)(2)、将方程、将方程两端同除以两端同除以3，得，得43511133xxx2.2 2.2 最优基可行解的求法最优基可行解的求法s.t. 4545451452321min133912433111330 (1,2,5)ifxxxxxxxxxxixx 所以，基阵所以，基阵B2对应的典式为：对应的典式为：解：解：在在B2对应的典式令非基变量对应的典式令非

25、基变量x4=x5=0 , 得得1239,4,1xxx 故故B2对应的基解为对应的基解为 ，且为基可行解。，且为基可行解。(2)T(9,4,1,0,0)x (5)对于对于B2=( p1，p2，p3 )例例4(P35) 求解下列线性规划问题：求解下列线性规划问题：s.t. 124135234235min232122250 (1,2,5)ifxxxxxxxxxxxxxi 解题步骤：解题步骤：2、根据定理、根据定理2.4、2.5、2.6判判 别此基可行解的最优性别此基可行解的最优性检验数全部非正，检验数全部非正，符合定理符合定理2.4，故，故 x(2)是最优解。是最优解。由于非基变量对应的检验数由于非

26、基变量对应的检验数42,03 51,03 由定理由定理2.4知知x(2)是该问题的最优解，最优值为是该问题的最优解，最优值为f(x(2)=1 。s.t. 34343134245min232622330 (1,2,5)ifxxxxxxxxxxxix 2.2 2.2 最优基可行解的求法最优基可行解的求法基阵基阵B1对应的典式为：对应的典式为：可见，使用定理可见，使用定理2.6，的确使得，的确使得函数值在一步步的改进函数值在一步步的改进!例例4(P35) 备注：备注：基基B0对应的典式：对应的典式：s.t. 4545451452321min133912433111330 (1,2,5)ifxxxxx

27、xxxxxixx 基基B2对应的典式为：对应的典式为：s.t. 23232352143min4222250 (1,2,5)ifxxxxxxxxxxxxi 2.2 2.2 最优基可行解的求法最优基可行解的求法定理定理2.4 (P28)对于对于LP的一个基的一个基B，若，若 且且 ，则对应基则对应基B的基解的基解 x(0)便是便是LP的最优解。的最优解。10B b 10NBNc B N c 检验数非正检验数非正情形一：情形一：定理定理2.5 (P30)若基可行解若基可行解 x(0) 对应的典式中，有某个检验数对应的典式中，有某个检验数 ，且相应地且相应地 ，则，则LP无最优解无最优解(此时此时目标

28、函数在可行域上无界目标函数在可行域上无界)。0 (1,2,)r ibim 0r T12(,)rrmrbbb0r 00ib (1,2,)im (0)()f x若基可行解若基可行解 x(0)对应的典式中，有某个检验数对应的典式中，有某个检验数 ，而而 中至少有一个大于零，并且中至少有一个大于零，并且 ，则必存在另一基可行解，则必存在另一基可行解，其对应的目标其对应的目标函数值比函数值比 小。小。情形二：情形二：定理定理2.6 (P31)首先看检验数是否全部非正首先看检验数是否全部非正(即是否满足定理即是否满足定理2.4)？若不满足定理若不满足定理2.4，即，即存在有正检验数，则用定理存在有正检验数

29、，则用定理2.5、定理、定理2.6来判别。来判别。2.2 2.2 最优基可行解的求法最优基可行解的求法单纯形法的基本过程单纯形法的基本过程：(P33)见书见书单纯形法：综合定理单纯形法：综合定理2.42.6，便可得出求解线性规划问题，便可得出求解线性规划问题LP 的一种方法，称之为单纯形法。的一种方法，称之为单纯形法。第二章第二章 单纯形方法单纯形方法2.32.3单纯形法的计算步骤、单纯形表单纯形法的计算步骤、单纯形表 第一步，第一步，对于一个已知的可行基对于一个已知的可行基 ，写出对，写出对 应的典式及应的典式及B对应的基可行解对应的基可行解x(0)，xB(0)=B-1b=(b10， b20

30、， bm0)T;12(,)mjjjBppp 0 (1,2, )jjn 第二步，第二步，检查检验数。如果所有检验数检查检验数。如果所有检验数 ， 则则x (0)就是最优解。计算结束，否则转入下一步。就是最优解。计算结束，否则转入下一步。 第三步，第三步，若有某个检验数若有某个检验数r为正数，且其所对应的系数为正数，且其所对应的系数bi r全全 部非正部非正，则该线性规划问题无最优解。计算结束，否则转入，则该线性规划问题无最优解。计算结束，否则转入 下一步。下一步。 第四步第四步，若检验数中有些为正数，且它们所对应的系数，若检验数中有些为正数，且它们所对应的系数bir中有正数，则需要换基、进行迭代

31、运算。中有正数，则需要换基、进行迭代运算。 在所有大于零的检验数中选取最大的一个，设对应的在所有大于零的检验数中选取最大的一个，设对应的非基变量为非基变量为xr， 则取则取xr为进基变量，并求最小比值：为进基变量，并求最小比值：由此确定由此确定xj s为离基变量为离基变量( (若上述最小值同时在几个比值上若上述最小值同时在几个比值上达到，则选取其中下标最小的变量为离基变量达到，则选取其中下标最小的变量为离基变量) )。然后用然后用pr代代换换pjs，得到新基，得到新基 ，再接下一步。，再接下一步。00m in0,1, 2,iriirrrsbbbimbb B 第五步第五步，求出新基，求出新基 对

32、应的典式以及基可行解对应的典式以及基可行解x (1)，然后，然后以以 取代取代B，x (1)取代取代x (0)，返回第二步。返回第二步。 BB2.32.3单纯形法的计算步骤、单纯形表单纯形法的计算步骤、单纯形表从第二步到第五步的每一次循环，称为一次从第二步到第五步的每一次循环，称为一次单纯形迭代。单纯形迭代。2.32.3单纯形法的计算步骤、单纯形表单纯形法的计算步骤、单纯形表给定给定LP的一个基，对应一个典式，一个典式的一个基，对应一个典式，一个典式便对应一个单纯形表。便对应一个单纯形表。单纯形表：是用非基变量表达基变量和目标函数的单纯形表：是用非基变量表达基变量和目标函数的系数矩阵系数矩阵。

33、s.t. 1111min()0BBNNBNfc B bc B N cxxB NxB bx 典式典式(2.12)矩阵表达矩阵表达11B AxB b 检验数检验数对应单纯形表对应单纯形表的矩阵形式的矩阵形式1111BBc B b c B A cB bB A s.t. (0)0(1,2, )min0 (1,2, )ijjj Rjijjij Rjimffxxb xbxjn 其对应单纯形表如下表其对应单纯形表如下表2-2(P39)所示：所示：基基 对应对应的典式的典式(2.14) (2.16)120(,)mjjjBppp 表表2-2 基基 对应的单纯形表对应的单纯形表10(, , ,)smjjjBppp

34、 为该基解对应的目标函数值，即为目标函数为该基解对应的目标函数值，即为目标函数的典式表达中的常数。的典式表达中的常数。2.32.3单纯形法的计算步骤、单纯形表单纯形法的计算步骤、单纯形表1000smbbb 12rn 12rnxxxx1 11 211rnbbbb12sss rs nbbbb12mmm rm nbbbb 全部决全部决策变量策变量全部检全部检验数验数即为目即为目标函数标函数的典式的典式表达中表达中的各变的各变量的系量的系数反号数反号(基变量基变量取为取为0)即为典式中约束方程的右端常数，即为典式中约束方程的右端常数，亦即为该基解的基分量的值。亦即为该基解的基分量的值。典式中约典式中约

35、束方程的束方程的系数矩阵系数矩阵第第1行行第第0行行第第s行行第第m行行基变量基变量第第1列列第第0列列第第r列列第第n列列第第2列列1sjjjmxxx 1sjjjmxxx 2.32.3单纯形法的计算步骤、单纯形表单纯形法的计算步骤、单纯形表1000smbbb 12rn 12rnxxxx1 11 211rnbbbb12sss rs nbbbb12mmm rm nbbbb 其中，其中，12,mjjjxxx为基变量，它们所对应的列实为单位列向量。为基变量，它们所对应的列实为单位列向量。 对应的列，对应的列，例如，例如，1jx注意：在注意：在初初始始单纯形表单纯形表中，决策变中，决策变量行、基变量行

36、、基变量列，均是量列，均是按照下标按照下标从从小到大小到大的顺的顺序排列的。序排列的。表表2-2 基基 对应的单纯形表对应的单纯形表10(, , ,)smjjjBppp 111000jjxb =1除除 外，其余元素包括检验数皆为外，其余元素包括检验数皆为0 。111jb 2.32.3单纯形法的计算步骤、单纯形表单纯形法的计算步骤、单纯形表用单纯形用单纯形表表计算线性规划问题的步骤计算线性规划问题的步骤(P39-40)：(1)、若原线性规划问题不是标准型，需先化成标准型，再求、若原线性规划问题不是标准型，需先化成标准型，再求出此线性规划问题对应于基出此线性规划问题对应于基 的典式，并依的典式，并

37、依据这个典式列出基据这个典式列出基B0对应的单纯形表对应的单纯形表T(B0)。120(,)mjjjBppp (2)、在表、在表T(B0)中，除中，除f (0)外，若第外，若第0列元素都列元素都0，第，第0行元素都行元素都0，则该表对应的基解便为问题的最优解，称最优基可行解，则该表对应的基解便为问题的最优解，称最优基可行解对应的单纯形表为对应的单纯形表为最优解表最优解表。计算结束，否则转入下一步。计算结束，否则转入下一步。检验数检验数为可行解为可行解(3)、若、若r 0，且且在表在表T(B0)中中r 所在列的其他元素都所在列的其他元素都0，则该，则该问题问题无无最优解最优解。计算结束，否则转入下一步。计算结束，否则转入下一步。考查检验数，即第考查检验数，即第0行元素行元素用定理用定理2.4考查考查用定理用定理2.5考查考查画