第二节单纯形法_第1页
第二节单纯形法_第2页
第二节单纯形法_第3页
第二节单纯形法_第4页
第二节单纯形法_第5页
已阅读5页，还剩13页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

第二节 单纯形法单纯形法是求解线性规划的主要算法， 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的位置在哪？ 对应于初
人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论