精品课程运筹学,第三节 单纯形方法,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最优解对应的约束方程组，只是目标函数不同.,精品课程运筹学,用表格表示为,精品课程运筹学,所以原问题解无界,化为典式后,