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