单纯形法原理讲解ppt课件.ppt_第1页
单纯形法原理讲解ppt课件.ppt_第2页
单纯形法原理讲解ppt课件.ppt_第3页
单纯形法原理讲解ppt课件.ppt_第4页
单纯形法原理讲解ppt课件.ppt_第5页
已阅读5页，还剩24页未读， 继续免费阅读

下载本文档

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

文档简介

,本节通过一个引例，可以了解利用单纯形法求解线性规划问题的思路，并将每一次的结果与图解法作一对比，其几何意义更为清楚。,引例（上一章例）,求解线性规划问题的基本思路,1、构造初始可行基；2、求出一个基可行解（顶点）3、最优性检验：判断是否最优解；4、基变化，转2。要保证目标函数值比原来更优。,从线性规划解的性质可知求解线性规划问题的基本思路。,第1步确定初始基可行解,根据,显然，可构成初等可行基B。,为基变量,第2步求出基可行解,基变量用非基变量表示，并令非基变量为0时对应的解,是否是最优解？,第3步最优性检验,分析目标函数,检验数,0时，,无解换基，继续,只要取或的值可能增大。,换入？基变量换出？基变量,考虑将或换入为基变量,第4步基变换,换入基变量：,换入变量,均可换入。,换出变量,使换入的变量越大越好同时，新的解要可行。,选非负的最小者对应的变量换出,为换入变量，应换出？变量。,思考：当时会怎样？,因此，基由变为,为换入变量，应换出变量。,转第2步,继续迭代,可得到:,最优值,最优解,结合图形法分析（单纯形法的几何意义）,A(0,3),B(2,3),C(4,2),D(4,0),单纯形法迭代原理,从引例中了解了线性规划的求解过程，将按上述思路介绍一般的线性规划模型的求解方法单纯形法迭代原理。,观察法:直接观察得到初始可行基约束条件:加入松弛变量即形成可行基。（下页）约束条件:加入非负人工变量,以后讨论.,1、初始基可行解的确定,1、初始基可行解的确定,不妨设为松弛变量，则约束方程组可表示为,1、初始基可行解的确定,2、最优性检验与解的判别,2、最优性检验与解的判别,代入目标函数有：,2、最优性检验与解的判别,(1)最优解判别定理：若：为基可行解，且全部则为最优解。（2）唯一最优解判别定理：若所有则存在唯一最优解。,2、最优性检验与解的判别,（3）无穷多最优解判定定理：若：且存在某一个非基变量则存在无穷多最优解。（4）无界解判定定理：若有某一个非基变量并且对应的非基变量的系数则具有无界解。,2、最优性检验与解的判别,（4）之证明：,2、最优性检验与解的判别,最优解判断小结（用非基变量的检验数）,以后讨论,3、基变换,换入变量确定对应的为换入变量.(一般),注意：只要对应的变量均可作为换入变量,此时，目标函数,换出变量确定,3、基变换,则对应的为换出变量.,4、迭代运算,写成增广矩阵的形式,进行迭代.,例：,4、迭代运算,非基变量,基变量,001,通过初等行变换化主列为,主元,4、迭代运算,每次迭代的信
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论