第二章 单纯形法单纯形法(Simplex Method)是著名的美国运 筹学家丹茨格于1947年 首创的一种求解LP问题 的通用有效算法第一节 单纯形法的基本思想本节将通过方程组形式举例说明单 纯形法的运用及其基本思想 1.1 1.1 方程组形式的单纯形法方程组形式的单纯形法单纯型法的基本思路是：基于LP问题的 标准形，先设法找出一个基本可行解，并由此 开始逐次施行从一个基本可行解到另一个基本 可行解的转换这种转换不仅易于实现，还能 改善(起码是保持)目标函数值如此下去，直 到取得最优值或判明问题无解为止下面就范例说明方程组形式的单纯形法及 其基本思想例1 试用方程组形成的单纯形法求解范例( 见书52页) 区域OABCD(包括其边界)上的每一点，都是范例的LP模型的一 个解，一般称为可行解因此区域OABCD是该LP模型的解集合，一 般称为可行域，通常简记为R1.2 1.2 单纯形法的几何意义单纯形法的几何意义第二节 单纯形法的计算过程2.1 2.1 单纯形表单纯形表 表2-1 初始单纯形表的一般形式2.2 2.2 单纯形法的计算步骤：单纯形法的计算步骤：下面给出表格形式的单纯型法的计算步骤：1 把LP问题化成标准形。
2 在系数阵中找出或构造一个m阶排列矩阵作为初 始可行基，建立初始单纯形表3 如所有检验数 ，就得到一个最优基本解， 停止计算；否则转44 在所有 中，只要有一个 所对应的系数 列向量 ,即一切 ，则该LP问题无最优解，停止计算；否则转55 按最小检验数规则确定进基变量 和主列 ；再按最小比值规则确定主元alk，同时也就确定l行的基变量离基6 以alk为主元对当前表格进行一次换基运算 ，得到一个新单纯形表，返3其中1，2为预备步骤或第0次迭代；3～6为 迭代步骤2.3 2.3 单纯形法计算之例单纯形法计算之例第一节例1就是方程组形式的单纯形法计算之例下面再用单纯 形表的形式重新计算一遍，以便说明单纯形法的计算步骤和单纯形 法的使用方法计算过程如下： (第0次迭代)1 由前已知范例的标准形2 取松弛变量x3,x4,x5为基变量，可得到3 阶排列阵(单位阵) 为初始基建立初始单纯形表如下：表2-2表2-2检验行的数字是按公式(2-6)、(2-7)算出的。
其余 是基变量的检验数，它们肯定为0按公式计 算(2－7)也得同样结果 3 因 ，都小于0，故未得最优解 4 因 所定义的系数列向量 中都存在正分量，故不 是解无界的情况，应继续迭代(第1次迭代 )5 由 确定x2进 基；又由 可确定比值6所在行的基变量x4离基 ;x2列与x4行的交叉处给出主元2为醒目起见，在表中x2列和x4行 都标有箭头，分别表示主列和主行，而且主元2被套上圆圈6 按主元2对表2－2进行一次换基运算，于是得到新单纯形 表(见表2－3），返3由3 因 ,故仍未得最优解4 因 对应的列向量 中有正分量，故转5继续迭代。
第二次迭代)5 此时仅 ，故x1进基；又由 ，可知 x5离基；从而得主元36 按主元3对表2-3进行一次换基运算，又得一新表(见表2－ 4)表2－4由于表2－4中所有的检验数 ，因此已得到最优解例2 用单纯形法求解下述LP问题第三节 人工变量法单纯形法要求先从系数阵中找出一个m阶排列 阵，这往往不易做到考虑标准形LP问题：分别给每个约束方程硬行加入一个非负变量，得到以 为基变量，可以得到(2－ 9)的一个初始基本可行解：这个解x0完全是人为地加入m个变量而得到的，因此称为人造基本解，而把变量 称为人工变量 下面介绍一种具体方法3.1 3.1 大大MM法法这种方法是在原LP问题(2-8)的目标函数中添上全部人工变量， 并令其系数为一M，而M是一个充分大的正数即构造以下辅助问题 ：并用单纯形法进行求解。
1) 若迭代最终得到（FI）的最优解X*，而且X*的基变失中不 含有人工变量，则X*的前n个分量就构成原LP问题(2－8)的一个最优 基本解；否则原问题无可行解；(2) 若迭代最终结果为(FI)解无界，此时如最末单纯形表的“基 列”中不存在人工变量，则原问题(2－8)也是解无界，否则原问题无可 行解下面举例加以具体说明例3 用大M法求解下述LP问题：w 例4 现有线性规划问题，请用大M法求解（清华大学出版社 绿皮书32页）•最优解：x1=4,x2=1,x3=9,x4=x5=x6=x7=0,z=-2例题精选1.将下列线性规划问题标准化，并用单纯形方法求解 约束于2.考虑问题 约束于 用大M法求解； 。