运筹学第2章 单纯形法 2.1 单纯形法的基本思想
该方法简捷、规范，是举世公认的解决LP问，题行之有效单纯形法（Simplex Method）是美国著名运筹学家丹捷格（Dantzig）1947年首先提出的通用方法。
? 单纯形法不仅是解决LP问题的最基本的算法之一，而且成为解决整数规划和非线
性规划某些算法的基础。
2、单纯形法的3种形式—— 方程组形式（代数形式）、表格形式、矩阵形式
3、单纯形法的基本思路——基于LP问题的标准形，先设法找到某个基本可行解（称为初始基本可行解）；
开始实施从这个基本可行解向另一个基本可行解的转换，要求这种转换不仅容易实现，而且能改善（至少保持）目标函数值；
继续寻找更优的基本可行解，进一步改进目标函数值。当某一个基本可行解不能再改善时，该解就是最优解。（或者是出现无可行解、无最优解、无穷多最优解的情况） 2.1.1 方程组形式的单纯形法
例1 一个企业需要同一种原材料生产甲、乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，获得的利润也不相同（如下表）。请问，该企业应如何安排生产计划，才能使获得的利润达到最大？ 甲 乙 可利用的资源总量 原材料（吨） 2 3 100 加工时间（小时） 4 2 120 单位利润（百元） 6 4 解：该问题的LP模型为：
将该问题的LP模型化为标准形
max z ? 6x1?4x2?2x1?3x2?100?s.t. ?4x1?2x2?120?x,x?0?12
12
123
124
1234
函数约束的增广矩阵为：
很显然 R（A） = R（A，b）= 2 < 5，即该方程组有无穷多组解。 系数矩阵为： 1234
决策变量向量为： T
1234
?10?选取 B ? ? ? 3 ? 4 ? ? ? ? 为基，则 x , x 为基变量，x , 为非基变量
?01?341x2??
令非基变量 x 1 ? x 2 ? 0 ，则可以得到一基本 可行解为： X ? 0 , 0 , 100 , 120 T 下面的计算都是以它为初始点逐次实施转
0
换，故将其称为初始基本可行解。此时，Z=0，其经济含义为：该企业没 有安排甲、乙两种产品的生产，当然也就没有利润可言。
1234条典
? 初始基本可行解所对应的可行基是一个m阶的单位阵； ? 目标函数表达式中所有的基变量的系数全部为0。
? 这是单纯形法所必需的！！！ ? 分析目标函数表达式
1234
? 非基变量的系数都是正数，若将它们转换为基变量，目标函数值则就会可能增加。 ? 经济含义：每分别多生产一个单位产品甲、乙，目标函数值分别增加6、4，即利润
分别增加600元、 400元。
? 增加的单位产品对目标函数的贡献值，这就是检验数的概念。
? 只要目标函数表达式中还存在正检验数，就需要把它所对应的非基变量变为基变
量！
单纯形法一次只能把一个非基变量变为基变量
max z ? 6x?4x?100?2x?3x?x ?s.t. ?4x?2x ?x?120?x,x,x,x?0??2310100??A,b????4201120????????2310?A???4201????????X??x,x,x,x???max z ?6x?4x?0x?0xmax z ?6x?4x?0x?0x? 选择先将哪个非基变量变为基变量？
? 增加单位产品甲比增加单位产品乙对目标函数值的贡献大。（检验数大）
? 一般选择正系数最大所对应的那个非基变量作为换入变量，将它换入到基变量中 去，与此同时还要确定基变量中有一个要换出来变为非基变量！
? 增加单位产品甲比乙对目标函数的贡献值大（600>400），故先把非 基变量 x 1 变成基变量，称为让 x 1 进基，同时称 x 1为进基变量。
最大检验数规则
若记检验数为 ? ? 1 , 2 , ? , n ，其中包括 j j基变量的检验数（它们全部为0），最大检验数规 则的数学表达式为：
jjk
对于本例，则有 1故选择让 进基。
1? 当确定一个非基变量进基后，相应的就要从基变量中换出某一个基变量，使 其变为非基变量，称为让该变量离基，同时称其为离基变量。如何选择离基变量呢?
仍为非基变量即 2
31
41
?100120?120x1?min ?,?30?? 244??当且仅当 x 1 ? 30 时，原基变量中才有一个变量等于0，即 ，故
4选择 x 4 离基。因此可以确定：
?100120?120 x1?min ?,?30?? 4?4?2这样既确定了离基变量，同时又保证另外的基变量 x ? 0 ，也即保证了下面
3转换得到的解仍然是一个基本可行解。 记得：满足条典！！！
? 为了求得以 x x 3 为基变量的一个新的基本可行解，又为使其满足条典，以便检1,验它是否最优，必须对方程组进行一番初等变换，其主要目的是让进基变量 x 1的系数列向量变为单位向量。
? 在这里，我们把上式中的最小比值120/4的分母4称为主元。主元所在方程为主方
程。
??max ???0 ? ???xmax ?6,4??6????x2x?0?x?100?2x?0??x?120?4x?0x?0换基运算：
得到：
1? 2x2?x3?x4?40??2?1?x?1x ?x4?3012?24?z?6x1?4x211?? ?6?30?x2?x4??4x224??3 ?180?x2?x42令新的非基变量 x ? x ? 0 ,得到新的基本可行解: X1??30,0,40,0?T Z?18024? 经济含义——只安排生产甲产品30个单位，此时可获得利润180百元。 ? 这个方案比前方案优，但是否已经是最优？ ? 分析： 3
z?180?x2?2x4? 非基变量 x 2 的系数仍为正数，由最大检验数规则，则确定 x 2 为进基变量。再按最
小比值规则，确定 x 3 为离基变量。 ? 主方程中所含的基变量就是离基变量。
11? x?x?x4?20 23??24 ?13?x ?x?x4?2013?48?
24
344
34
最小比值规则
? 当确定进基变量后，以进基变量的系数列向量中的正数为分母，以相应的方程右端
常数为分子求最小比值，所得到的最小比值的分母就是主元。主元所在的方程中的基变量就是离基变量。即：
?bi?bl min ?ik?0??
?aik?alk
? 令新的非基变量 x 4 ? 0,得到新的基本可行解: X??20,20,0,0?T Z?200x 3 ?2
? 经济含义——分别生产甲、乙产品20个，此时可获得利润200百元。
3z?180?x?x211?3??180??20?x?x??x24?2?15?200?x?x24?
