第二节单纯形法329

单纯形表的计算步骤

①将线性规划数学模型化成标准型②构造初始可行基-找单位阵③列初始单纯形表④计算检验数，进行最优性检验⑤基变换：选择正检验数大的对应变量进基，选最小的检验比θ对应的行变量出基。一进一出完成基变换。

⑥选择主元，以主元行为中心进行迭代运算（初等行变换）⑦重复④、⑤、⑥，直至得到最优解

单纯形法的进一步讨论人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初始基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。例用大M法解下列线性规划解：首先将数学模型化为标准型系数矩阵中不存在单位矩阵，无法建立初始单纯形表。故添加人工变量x6,x7，得到人工变量单纯形法数学模型：像这样，为了构造初始可行基得到初始基可行解，把人工变量强行的加到原来的约束条件中，由于约束条件在添加人工变量前已是等式，因此在最优解中人工变量取值必须为0。为此令目标函数中人工变量的系数为任意大的负值，用-M表示。这个方法称为大M法，M叫罚因子。其中：M是一个很大的抽象的数，可以理解为它是足够大的一个正数，再用前面介绍的单纯形法求解该模型，计算结果见下表。

-431-1010-1201002-2[1]0001410104513-2M

2+M

-1+2M

–M000-6[5]0-101-1-33001002-2100015-6M

5M

0

-M0003/58/3—4101380141001410-6/510-1/503/5003/51-2/501-2/505000031/3——3/531/511/53/531/531/519/31331/30101210015/300102/3000-5-25/3总结：基变量不含人工变量—为原问题的最优解。基变量含有人工变量

(1)若人工变量大于0，则原问题无可行解。(2)若人工变量等于0，则将人工变量作为入基变量继续迭代，可将人工变量换出基。总结两阶段法：如果线性规划问题中的aij、bi或cj等参数值与这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。第一阶段第一阶段最优解中:

如果w<0,则原问题没有可行解;

如果w=0,则若人工变量全为非基变量,则得到了原问题的基可行解.否则基可行解退化,继续迭代就可以得到基可行解.第一阶段第二阶段以第一阶段最优基作为初始基可行解,继续迭代。例用两阶段法解下列线性规划解：做辅助线性规划问题：00000-1-1CBXBB-1bx1x2x3x4x5x6x7θ-1x64-431-101040x5101-1201005-1x712-2[1]00011-212-1000-1x63-6[5]0-101-13/50x58-330010-28/30x312-210001—-650-100-20x23/5-6/510-1/501/5-1/50x531/53/5003/51-3/5-7/50x311/5-2/501-2/502/53/500000-1-1总结：在第一阶段，只有当人工变量取值为0，目标函数值才为0时，这时候的最优解是原线性规划问题的可行解，若目标函数值不为0，说明有不为0的人工变量，则原问题无可行解。总结再从上表中的最后一个表出发，继续用单纯形法计算。32-100CBXBB-1bx1x2x3x4x5θ2x23/5－6/510－1/50—0x531/53/5003/5131/3-1x311/5－2/501－2/50—500002x213010123x131/310015/3-1x319/300112/3000-5-25/3

通过大Ｍ法或两阶段法求初始的基本可行解。但是如果在大Ｍ法的最优单纯形表的基变量中仍含有人工变量，或者两阶段法的辅助线性规划的目标函数的极大值小于零，则该线性规划问题就不存在可行解。

无可行解

解的几种特殊情况

-3-2-1000-M-M

CB

XB

x1x2x3x4x5x6x7x8

θ

0-M-M

x4x7x8

643

1111000010-10-10100[1]-100-101

6/1-3/1

-3+M-2+M-1-2M0-M-M00

0-M-2

x4x7x2

343

[1]021010-110-10-101001-100-101

3/14/1-

-3+M0-3-M0-M-202-M

-3-M-2

x1x7x2

313

1021010-100-3-1-1-11101-100-101

003-3M3-M-M1-M0-1运算到检验数全负为止，基变量里仍含有非0的人工变量，所以原问题无可行解。

无界解

无界解也称无最优解，无界解与无可行解时两个不同的概念。★无可行解是指原规划不存在可行解，从几何的角度解释是指线性规划问题的可行域为空集；★无界解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无界解判别方法：

在求解极大化的线性规划问题过程中，若某单纯形表的非基变量的检验数大于0，但是该非基变量的系数列都为负数或零，则该线性规划问题为无界解。例用单纯形法求解下列LP问题2200θ

CBXB

B-1bx1

x2

x3

x4

0x3

1-11100x4

2-1/21012200因但所以原问题无界解。为什么呢？显然这是线性规划问题的可行解，此时目标函数值当M无限增大，目标函数值也无限增大。因此此线性规划问题有无界解。

退化

即计算出的θ（用于确定换出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几个基变量等于零，这就是退化（会产生退化解）。退化会出现循环。但是一般情况下还是能够把最优解找出来。但不是所有的退化情况都能得到最优解，也就是出现了死循环。为避免出现死循环，勃兰特(Bland)提出一个简便有效的规则（摄动法原理）：⑴当存在多个时，选下标最小的非基变量为换入变量；(2)当θ值出现两个以上相同的最小值时，选下标最小的基变量为换出变量。这样就避免了死循环。平时仍然用原来的方法做，只有发现出现死循环，才用这种办法。

无穷多最优解

若线性规划问题某个非基变量检验数等于零，那么该线性规划问题有无穷多最优解。例：用单纯形法求解下面的线性规划

例：用单纯形法求解下面的线性规划

直观上有什么特点？——目标与某约束斜率相同会出现什么情况呢无穷多最优解[]问题：本题的单纯形终表检验数有何特点？

——非基变量x2的检验数等于零。无穷多最优解0110[]0110[]011012.5000

解的判别：1）唯一最优解判别：终表非基变量检验数均小于零。2）无穷多最优解判别：终表某非基变量的检验数等于零。3）无界解判别：任意表有正检验数相应的系数列均非正。4）无可行解的判断：当用大M单纯形法计算得到最优解存在某人工变量>0时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基可行解。关于单纯形法的一点注：min型单纯形表与max型的区别仅在于：检验数反号，即

-令负检验数中最小的对应的变量进基；

-当检验数均大于等于零时为最优。建立模型个数取值右端项等式或不等式极大或极小新加变量系数两个三个以上