第二节单纯形法

第二节 单纯形法单纯形法是求解线性规划的主要算法， 1947年由美国斯坦福大学教授丹捷格（ G.B.Danzig）提出。尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的 “ 市场 ” 占有率。单纯形法是一种迭代的算法（设计在单纯形表上实现），它的思想是在可行域的角点（称为基本可行解）中寻优。检验这个角点是否最优否是 停止确定一个初始角点寻找一个更好的角点 一、单纯形法的步骤1.将模型化为标准型 标准型的特征： Max型、等式约束、非负约束非 标准形式如何化为标准1) Min型化为 Max型 加负号因为，求一个函数的极小点，等价于求该函数的负函数的极大点。注意： Min型化为 Max型求解后，最优解不变，但最优值差负号。 2) 不等式约束化为等式约束分析： 以 例 1.1中煤的约束为例之所以 “ 不等 ” 是因为左右两边有一个差额，称为 “ 松弛量 ” ，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为 X3 ， 则有X3称为松弛变量。问题： 它的实际意义是什么？ 煤资源的 “ 剩余 ” 。2.建立初始单纯形表前提：模型 的系数阵 A中含 I（ 单位阵）。否则用人工变量法。初始单纯形表的结构全体变量名变量的价格系数约束系数阵与 A中的 I 相应的变量（称基变量）名基变量 的价格系数约束右端项3. 检验该单纯形表是否最优检验数：每个变量的检验数等于该变量的价格系数减去 与该变量的系数列之积。法则：如果全体检验数均非正，则本表为最优，相应的最优解 否则转 4。练习： 写出下列线性规划的标准型和初始单纯形表，并检验该表是否最优。由于检验数中有正的，故本表不是最优。4. 计算下一张单纯形表（ 1）确定本表的进基、出基变量和主元选本表正检验数中最大者，其相应的变量 xk 进 基；计算 与 xk 的 系数列之比（记 ，称检验比） ,选 中最小者相应的变量 xl 出基（注意：当 xk 的系数列中有零或负值时，相应 不算）； xk 列与 xl 行的 交叉元即主元。 例如（ 2）基于主元计算下一张单纯形表用 初等行变换方法，先将主元消成 1，再用此 1将其所在列的其余元消成 0，所得结果写在新表上；转第 3步（即检验 新表是否最优）。 例如例 1.7：用单纯形法求解例 1.1 （请解释其实际意义）练习：用单纯形法求解下面的线性规划 总结表的规律：1. 表中基变量的系数列有何特征？2. 基变量的检验数有何特征？ 均为单位向量列； 均为零。例 1.8：填出表中空白：问题：如果空白的不是基变量列怎么办呢？3. 表上每一列的含义：4. 每张表上 B-1的位置在哪？ 对应于初表中 I 的位置。事实上，因此，若已知初表和任意表的 B-1， 则 可用矩阵与向量法的乘法计算得到任意表中的空白列。