（1）当存在多个 j 0 时，始终选取下标值为最小 的变量作为换入变量；（2）当计算值出现两个 以上相同的最小比值时，始终选取下标值为最小 的变量作为换出变量。
3.无可行解的判别
本章第四节单纯形法迭代原理中，讲述了用 单纯形法求解时如何判别问题结局属唯一最优解、 无穷多最优解和无界解。当线性规划问题中添加 人工变量后，无论用大M法或两阶段法，初始单 纯形表中的解因含非零人工变量，故实质上是非 可行解。当求解结果出现所有时，如基变量中仍 含有非零的人工变量（两阶段法求解时第一阶段 目标函数值不等于零），表明问题无可行解。
的逆阵，将J中的第L个数改为k ，转入 （2）。
§1-9.单纯形法应用实例
例1-12 合理利用线材问题
现要做100套钢架，每套用长为2.9m，2.1m和1.5m的 元钢各一根，已知原料长7.4m，问应如何下料，使用 的原材料最省。
解 最简单做法是，在每一根原材料上截取2.9m， 2.1m和1.5m的元钢各一根组成一套，每根原材料 省下料头0.9m。为了做100套钢架，需用原材料 100根，有90米料头,若改为用套裁，这可以节约 原材料。下面有几种套裁方案，都可以考虑采用， 见表1-13。
0,
得到最优解，停止；否则，记为k主元列，
转入（4）。
（4）计算 B1 pk ,若B1 pk 0， 得无界解，停 止：否则转入（5）。
（5）求
min i
{((BB11pbk))
|
(B 1
pk
)i
0}
(B 1b)l (B 1 pk )l
并记l为主元行。 （6）构造矩阵 Elk用 Elk 左乘B 1 得到新基
2 6Biblioteka 11 0以 表x31,-x115。为表基中变当量所列有c出j 初 z始j 单0纯形表时，，进基行变迭量代中计仍算含有，非过零程的见
人工变量x，5 2 故例1-12的线性规划问题无可行解。
cj
2
1 0 0 -M
CB 基 b
0 -M
xx53
2 6
cj zj
2 -M
x1
x5
2 2
cj zj
min z 0x1 0.1x2 0.2x3 0.3x4 0.8x5
x1 2x2
x4
100
s.t.
3x1
2x3 x2 2x3
2x4 x5 3x5
100 100
x1, x2 , x3 , x4 , x5 0
计算得到最优下料方案是：按Ⅰ 方案下料30根；Ⅱ方案 下料10根；Ⅳ方案下料50根。即需90根原材料才能制造 100套钢架。
§1-7.单纯形法计算中的几个问题
一、单纯形法计算中的几个问题 1.目标函数极小化时解的最优性判别
对于目标函数值极小化的线性规划问题，这时只需以 所有检验数作为判别表中解是否最优的标志。 2.退化
按最小比值来确定换出基的变量时，有时出现存在 两个以上相同的最小比值，从而使下一个表的基可行解 中出现一个或多个基变量等于零的退化解。退化解的出 现原因是模型中存在多余的约束，使多个基可行解对应 同一顶点。当存在退化解时，就有可能出现迭代计算的 循环，尽管可能性极其微小。为避免出现计算的循环， 1974年勃兰特（Bland）提出了一个简便有效的规则：
2 . 单纯形法计算步骤的框图见page35图1-
§1-8修正单纯形法
一、修正单纯形法的基本思想
运用单纯形法时，如果知道可行基的逆 B 就
能利用 B 原始数据计算基变量的取值及检验
数，从而能够确定一个基本可行解，并判断它
是否为最优解。因此在整个计算过程中，只要
保存原始数据和现行的逆即可。修正单纯刑法
(1-37)
将（1-36）逐个代入(1-37)并整理得到
1 2
例1-13 配料问题
某工厂要用三种原材料C、P、H混合调配出三种 不同规格的产品A、B、C。已知产品的规格要 求，产品单价，每天能供应的原材料数量及原材 料单价，分别见表1-14和表1-15，该厂应如何安 排生产，使利润收入为最大？
产品名称 A
B
规格要求
原材料C不少于50% 原材料P不少于25% 原材料C不少于25% 原材料P不少于50%
x1 x2 x3 x4 x5
[1] 1 1 0 0
2
2 0 -1 1
2+2M 1+2M 0 -M 0
1 1 100 0 0 -2 -1 1
0 -1 -2-2M -M 0
二、单纯形法小结
1. 对给定的线性规划问题应首先化为标准形式， 选取或构造一个单位矩阵作为基，求出初始基 可行解并列出初始单纯形表。对各种类型线性 规划问题如何化为标准形式及如何选取初始基 变量可参见page35表1-14。
例1-11 用单纯形法求解线性规划问题
max z 2x1 x2
s.t.
2
x1 x1
x2 2 2x2 6
x1 , x 0
解 用图解法可看出本例无可行解。现用单纯形法求解，在添加松
驰变量和人工变量后，模型可写成
max z 2x1 x2 0x3 0x4 Mx5
s.t. 2x1x1 x22x2x3 x4 x5
单价(元/kg) 50
35
D
不限
25
原材料名称
C P H
每天最多供应量(kg) 单价(元/kg)
100
65
100
25
60
35
解 如以 A表c 示产品A中C的成分，Ap 表示产品A中P的成分，依次
类推。有(1-36)
Ac
1 2
A, Ap
1 4
A, Bc
1 4 B, Bp
1 B(1-36)
2
这里
Ac Ap AH A Bc B p BH B
为了得到100套钢架，需要混合使用各种下料方案。设 按Ⅰ方案下料的原材料要数为，Ⅱ方案为，Ⅲ方案为， Ⅳ方案为，Ⅴ方案为。根据表1-13的方案，可列出以下 数学模型：
方案 下料数(根) Ⅰ Ⅱ Ⅲ Ⅲ Ⅴ 长度m
2.9
12
1
2.1
2 21
1.5
31
2
3
合计 7.4 7.3 7.2 7.1 6.6 料头 0 0.1 0.2 0.3 0.8
的基本思想就是给定初始基本可行基后，通过
修改新基的逆
B
进而完成其他运算。在整个
计算过程中，始终保持先行基的逆B 。
二、修正单纯形发的步骤
（1）求一个初始基B并求出它的逆B ， 写出基底描述J。
（2）求单纯形乘子Y (CBT B )T 。
（3）求 j c j Y T p j
及max{ jJ
j } k ,若 k