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

下载本文档

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

文档简介

第二节单纯形法

单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Dantzig）提出。尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。

单纯形法是一种迭代的算法（设计在单纯形表上实现），它的思想是在可行域的角点（称为基本可行解）中寻优。检验这个角点是否最优否是停止确定一个初始角点•寻找一个更好的角点••1.将模型化为标准型

标准型的特征：Max型、等式约束、非负约束一、单纯形法的步骤非标准形式如何化为标准1)Min型化为Max型

加负号

因为，求一个函数的极小点，等价于求该函数的负函数的极大点。注意：Min型化为Max型求解后，最优解不变，但最优值差负号。

2)

不等式约束化为等式约束分析：以例1.1中煤的约束为例之所以“不等”是因为左右两边有一个差额，称为“松弛量”，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为X3

，则有X3称为松弛变量。问题：它的实际意义是什么？

——

煤资源的“剩余”。练习：请将例1.1的约束化为标准型解：增加松弛变量则约束化为易见，增加的松弛变量的系数恰构成一个单位阵I。2.建立初始单纯形表

前提：模型的系数阵A中含I（单位阵）。否则用人工变量法。初始单纯形表的结构全体变量名变量的价格系数约束系数阵与A中的I相应的变量（称基变量）名基变量的价格系数约束右端项例1.5：列出例1.1标准模型的初始单纯形表3.检验该单纯形表是否最优检验数：每个变量的检验数等于该变量的价格系数减去与该变量的系数列之积。法则：如果全体检验数均非正，则本表为最优，相应的最优解否则转4。例1.6：检验例1.1的初始单纯形表是否最优相应于x1的系数列练习：计算x2的检验数。由于检验数中有正的，故本表不是最优。练习：写出下列线性规划的标准型和初始单纯形表，并检验该表是否最优。由于检验数中有正的，故本表不是最优。确定一个初始角点检验这个角点是否最优寻找一个更好的角点否是停止下一步？4.计算下一张单纯形表（1）确定本表的进基、出基变量和主元

•选本表正检验数中最大者，其相应的变量xk进基；

•计算与xk的系数列之比（记，称检验比）,选中最小者相应的变量xl出基（注意：当xk的系数列中有零或负值时，相应不算）；

•

xk列与xl行的交叉元即主元。[]例如（2）基于主元计算下一张单纯形表

•用初等行变换方法，先将主元消成1，再用此1将其所在列的其余元消成0，所得结果写在新表上；

•转第3步（即检验新表是否最优）。[]例如例1.7：用单纯形法求解例1.1问题：标准模型的A中是否含I？——松弛变量系数恰好构成I。[][][]（请解释其实际意义）练习：用单纯形法求解下面的线性规划

[]总结表的规律：表中基变量的系数列有何特征？基变量的检验数有何特征？——均为单位向量列；——均为零。例1.8：填出表中空白：问题：如果空白的不是基变量列怎么办呢？3.表上每一列的含义：4.每张表上B-1的位置在哪？——对应于初表中

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论