1、第二节 单纯形法,单纯形法是求解线性规划的主要算法 ， 1947 年由美国斯坦福大学教授丹捷格（G.B.Danzig） 提出 。
尽管在其后的几十年中 ， 又有一些算法问世 ，但单纯形法以其简单实用的特色始终保持着绝对 的“市场”占有率,1.线性规划的标准型 用单纯形法求解线性规划的前提是先将模 型化为标准型,标准型的特征：Max型、等式约束、非负约束,一、单纯形法的预备知识,非标准形式如何化为标准,1) Min型化为Max型,加负号,因为 ， 求一个函数 的极小点 ， 等价于求该 函数的负函数的极大点,注意： Min型化为Max型求解后 ， 最优解不变 ， 但最优值差负号,2) 不等式约束化为等式约束,分析：以例1中 。

2、煤的约束为例,之所以“不等”是因为左右两边有一个差额 ， 称为“松 弛量” ， 若在左边加上这个松弛量 ， 则化为等式 。
而这 个松弛量也是变量 ， 记为X3， 则有,X3称为松弛变量 。
问题：它的实际意义是什么,煤资源的“剩余,练习：请将例1的约束化为标准型,解：增加松弛变量,则约束化为,易见 ， 增加的松弛变量的系数恰构成一个单位阵I,一般地 ， 记松弛变量的向量为 Xs ， 则,问题：松弛变量在目标中的系数为何,0,3) 当模型中有某变量 xk 没有非负要求 ， 称 为自由变量, 则可令,化为标准型,2.基本概念,1）可行解与最优解,直观上 ， 可行解是可行域中的点 ， 是一个可行的方案； 最优解是可行域的角点 ， 是一个最优的方案, 。

3、2）基矩阵与基变量,基矩阵(简称基)：系数阵A中的m阶可逆子阵 ， 记 为B；其余部分称为非基矩阵 ， 记为N,基向量：基B中的列；其余称非基向量,基变量：与基向量Pj对应的决策变量xj ， 记其组成的 向量为XB；与非基向量对应的变量称非基变 量 ， 记其组成的向量为XN,6个,一般地 ， mn 阶矩阵A中基的个数最多有多少个,问题：本例的A中一共有几个基,3）基本解与基本可行解,可见：一个基本解是由一个基决定的 。
注意：基本解仅是资源约束的解 ， 并未要求其非负 ， 因此其未必可行,称非负的基本解为基本可行解（简称基可行解,例4：在上例中,求相应于基B1和B2的基本解 ， 它们是否基本可行解,上二组概念间的联系,几种解之 。

4、间的关系,问题：基本可行解是可行域中的哪些点,3.基本定理,1）线性规划的可行域是一个凸多面体,2）线性规划的最优解（若存在的话）必能在可行 域的角点获得,3）线性规划可行域的角点与基本可行解一一对应,二、单纯形法的步骤,单纯形法是一种迭代的算法 ， 它的思想是在可行域的角点基本可行解中寻优 。
由于角点是有限个（为什么？） ， 因此 ， 算法经有限步可终止,确定一个初始基可行解,检验这个基可行解是否最优,寻找一个更好的基可行解,停止,1.确定初始基可行解,由于基可行解是由一个可行基决定的 ， 因此 ， 确定初始基可行解X0相当于确定一个初始可行基B0,方法：若A中含I ， 则B0=I； 若A中不含I ， 则可用人工变量法构 。

5、 造一个I,问题：若B0=I ， 则X0=,2. 最优性检验,问题：用什么检验,目标,问题：非最优的特征为何,3. 寻找更好的基可行解,由于基可行解与基对应 ， 即寻找一个新的基可行解 ， 相当于从上一个基B0变换为下一个新的基B1 ， 因 此 ， 本步骤也称为基变换,基变换,以例1为例 ， 可按上述单纯形法的步骤求出其最优解 ， 其大致的过程如下,1）先将模型化为标准型,2) 确定初始基可行解、检验,3）换基、计算下一个基可行解、再检验 ， 直至最优,问题：当模型规模较大时 ， 计算量很大,事实上 ， 单纯形法的实现是在单纯形表上完成的,练习：对于下面的线性规划,1）用图解法求解； （2）将模型化为标准型； （3）用单纯形法步骤求 。

【运筹学|运筹学：二章二节单纯形法】6、出其最优解 ， 并指出求 解过程中每一个基可行解相当于可行域的 哪一个角点,三、单纯形表,单纯形表是基于单纯形法的步骤设计的计算格式 ， 是单纯形法的具体实现,回顾单纯形法步骤,单纯形表的主要结构,问题：第一张表的B-1=,单位阵I,检验数的公式是什么,例5：用单纯形法求解例1,问题：标准模型的A中是否含I,松弛变量系数恰好构成I,中表示进基列与出基行的交叉元 ， 下一张表将实行以它为主元的初等行变换（称高斯消去） 。
方法是：先将主元消成1 ， 再用此1将其所在列的其余元消成0,请解释其实际意义,练习：用单纯形法求解下面的线性规划,注：1. 表上每一列的含义,2. 每张表上B-1的位置在哪？对应于初表中I 的位置,例6： 填表,练习：用单纯形法求解下面的线性规划,问题：本题的单纯形终表检验数有何特点,非基变量x2 的检验数等于零,注：（1）解的几种情况在单纯形表上的体现（Max型）： - 唯一最优解：终表非基变量检验数均小于零； - 多重最优解：终表非基变量检验数中有等于零的； - 无界解：任意表有正检验数相应的系数列均非正,2） Min型单纯形表与Max型的区别仅在于：检验数反号 ， 即 - 令负检验数中最小的对应的变量进基； - 当检验数均大于等于零时为最优 。

来源：(未知)

【学习资料】网址：/a/2021/0321/0021743397.html

标题：运筹学|运筹学：二章二节单纯形法