《三节单纯形方法复习课程》由会员分享,可在线阅读,更多相关《三节单纯形方法复习课程(47页珍藏版)》请在金锄头文库上搜索。
1、精品课程运筹学,第三节 单纯形方法,3.1 单纯形方法,3.2 单纯形表,精品课程运筹学,3.1 单纯形方法,考虑标准形式的LP问题,如果它有最优解,则必可在某一基本可行解处达到,因而只需在基本可行解集合中寻求即可,4.非退化,基本假定:,精品课程运筹学,先找一个基本可行解,判断它是否为最优解,如果不是,就找一个更好的基本可行解,再进行判断,如此迭代进行,直到找到最优解,或者判定该问题无界.,需要解决的两个问题 如何得到第一个基本可行解; 如何判别和进行迭代.,基本思想,精品课程运筹学,精品课程运筹学,典式,精品课程运筹学,精品课程运筹学,引入记号,即,检验数向量,精品课程运筹学,精品课程运筹
2、学,定理1.3.1,最优性准则,精品课程运筹学,定理1.3.2 (无界准则),精品课程运筹学,精品课程运筹学,精品课程运筹学,定理1.3.3 (可迭代准则),精品课程运筹学,令,精品课程运筹学,精品课程运筹学,精品课程运筹学,精品课程运筹学,精品课程运筹学,换基过程,精品课程运筹学,基矩阵,基变量,出基列 出基变量,进基列 进基变量,精品课程运筹学,新基矩阵,精品课程运筹学,新基矩阵,精品课程运筹学,定理1.3.4,对于任何非退化的线性规划问题,从任何基本可行解开始,经过有限多次迭代,或得到一个基本可行的最优解,或做出该线性规划问题无界的判断.,精品课程运筹学,单纯形方法步骤,第1步,第2步,
3、第3步,第4步,第5步,第6步,精品课程运筹学,单纯形方法步骤,第7步,精品课程运筹学,3.2 单纯形表,对于给定LP问题的一个线性方程组,精品课程运筹学,精品课程运筹学,基变量的值,思考:是否都可经过简单初等行变换化成典式?,精品课程运筹学,若将k=4引入基,需计算,精品课程运筹学,利用初等行变换化为对应的典式:,精品课程运筹学,精品课程运筹学,精品课程运筹学,进基,离基,精品课程运筹学,精品课程运筹学,精品课程运筹学,精品课程运筹学,转轴元,旋转列,旋转行,精品课程运筹学,旋转,精品课程运筹学,例1.3.1,求解问题,解,精品课程运筹学,精品课程运筹学,迭代后,精品课程运筹学,迭代后,精品课程运筹学,例1.3.2,求解问题,精品课程运筹学,解,这个问题的约束方程组是与例1.3.1最优解对应的约束方程组,只是目标函数不同.,精品课程运筹学,用表格表示为,精品课程运筹学,所以原问题解无界,化为典式后,