资源预览内容
第1页 / 共47页
第2页 / 共47页
第3页 / 共47页
第4页 / 共47页
第5页 / 共47页
第6页 / 共47页
第7页 / 共47页
第8页 / 共47页
第9页 / 共47页
第10页 / 共47页
亲,该文档总共47页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
精品课程运筹学,第三节 单纯形方法,3.1 单纯形方法,3.2 单纯形表,精品课程运筹学,3.1 单纯形方法,考虑标准形式的LP问题,如果它有最优解,则必可在某一基本可行解处达到,因而只需在基本可行解集合中寻求即可,4.非退化,基本假定:,精品课程运筹学,先找一个基本可行解,判断它是否为最优解,如果不是,就找一个更好的基本可行解,再进行判断,如此迭代进行,直到找到最优解,或者判定该问题无界.,需要解决的两个问题 如何得到第一个基本可行解; 如何判别和进行迭代.,基本思想,精品课程运筹学,精品课程运筹学,典式,精品课程运筹学,精品课程运筹学,引入记号,即,检验数向量,精品课程运筹学,精品课程运筹学,定理1.3.1,最优性准则,精品课程运筹学,定理1.3.2 (无界准则),精品课程运筹学,精品课程运筹学,精品课程运筹学,定理1.3.3 (可迭代准则),精品课程运筹学,令,精品课程运筹学,精品课程运筹学,精品课程运筹学,精品课程运筹学,精品课程运筹学,换基过程,精品课程运筹学,基矩阵,基变量,出基列 出基变量,进基列 进基变量,精品课程运筹学,新基矩阵,精品课程运筹学,新基矩阵,精品课程运筹学,定理1.3.4,对于任何非退化的线性规划问题,从任何基本可行解开始,经过有限多次迭代,或得到一个基本可行的最优解,或做出该线性规划问题无界的判断.,精品课程运筹学,单纯形方法步骤,第1步,第2步,第3步,第4步,第5步,第6步,精品课程运筹学,单纯形方法步骤,第7步,精品课程运筹学,3.2 单纯形表,对于给定LP问题的一个线性方程组,精品课程运筹学,精品课程运筹学,基变量的值,思考:是否都可经过简单初等行变换化成典式?,精品课程运筹学,若将k=4引入基,需计算,精品课程运筹学,利用初等行变换化为对应的典式:,精品课程运筹学,精品课程运筹学,精品课程运筹学,进基,离基,精品课程运筹学,精品课程运筹学,精品课程运筹学,精品课程运筹学,转轴元,旋转列,旋转行,精品课程运筹学,旋转,精品课程运筹学,例1.3.1,求解问题,解,精品课程运筹学,精品课程运筹学,迭代后,精品课程运筹学,迭代后,精品课程运筹学,例1.3.2,求解问题,精品课程运筹学,解,这个问题的约束方程组是与例1.3.1最优解对应的约束方程组,只是目标函数不同.,精品课程运筹学,用表格表示为,精品课程运筹学,所以原问题解无界,化为典式后,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号