运筹学1-3.ppt

《运筹学1-3.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三节单纯形方法§3.1单纯形方法§3.2单纯形表精品课程《运筹学》§3.1单纯形方法考虑标准形式的LP问题如果它有最优解，则必可在某一基本可行解处达到，因而只需在基本可行解集合中寻求即可4.非退化基本假定：精品课程《运筹学》先找一个基本可行解，判断它是否为最优解，如果不是，就找一个更好的基本可行解，再进行判断，如此迭代进行，直到找到最优解，或者判定该问题无界.需要解决的两个问题如何得到第一个基本可行解；如何判别和进行迭代.基本思想精品课程《运筹学》精品课程《运筹学》精品课程《运筹学》典式精品课程《运筹学》精品课程《运筹学》引入记号即检验数向量精品课程《运

2、筹学》精品课程《运筹学》定理1.3.1最优性准则精品课程《运筹学》定理1.3.2（无界准则）精品课程《运筹学》精品课程《运筹学》精品课程《运筹学》定理1.3.3（可迭代准则）精品课程《运筹学》令精品课程《运筹学》精品课程《运筹学》精品课程《运筹学》精品课程《运筹学》精品课程《运筹学》换基过程精品课程《运筹学》基矩阵基变量出基列出基变量进基列进基变量精品课程《运筹学》新基矩阵精品课程《运筹学》新基矩阵精品课程《运筹学》定理1.3.4对于任何非退化的线性规划问题，从任何基本可行解开始，经过有限多次迭代，或得到一个基本可行的最优解，或做出该线性规划问题无界的判断

3、.精品课程《运筹学》单纯形方法步骤第1步第2步第3步第4步第5步第6步精品课程《运筹学》单纯形方法步骤第7步精品课程《运筹学》§3.2单纯形表对于给定LP问题的一个线性方程组精品课程《运筹学》精品课程《运筹学》基变量的值思考：是否都可经过简单初等行变换化成典式？精品课程《运筹学》若将k=4引入基，需计算精品课程《运筹学》利用初等行变换化为对应的典式：精品课程《运筹学》精品课程《运筹学》精品课程《运筹学》RHS进基离基精品课程《运筹学》精品课程《运筹学》精品课程《运筹学》精品课程《运筹学》转轴元旋转列旋转行精品课程《运筹学》旋转精品课程《运筹学》例1.3.1

4、求解问题解精品课程《运筹学》精品课程《运筹学》迭代后精品课程《运筹学》迭代后精品课程《运筹学》例1.3.2求解问题精品课程《运筹学》解这个问题的约束方程组是与例1.3.1最优解对应的约束方程组，只是目标函数不同.精品课程《运筹学》用表格表示为精品课程《运筹学》所以原问题解无界化为典式后精品课程《运筹学》