《单纯形方法》ppt课件

《《单纯形方法》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§2.3单纯形方法典式基本定理单纯形方法单纯形表（单纯形方法的实现）1947年由Dantzig提出，被称为20世纪最好的十个算法之一，是迄今为止解决线性规划问题的最成熟的方法。定理2.2.6一个标准的LP问题如果有有限的最优值，则一定存在一个基本可行解是最优解。主要思想：1）先找一个基本可行解2）判断是否为最优解3）是，stop；不是，再找一个更好的已有初始解线性规划的标准形式：=1典式(定义)=1典式（定义）001100010=0001典式（定义）典式的特点：1、约束条件中含有一个单位矩阵；2、目标函数中不含基变量。000001100010=1典式（定义）000001100010=1典式（

2、例）1典式（定义）问题：如何判断一个基本可行解是否为最优解呢？典则形式的LP问题中，目标函数中的变量系数的符号，对于判断某一个基本可行解是不是最优解非常重要。本例中是什么？典则形式的LP问题中，目标函数系数向量的负向量。称为检验数向量.2基本定理定理2.3.1例如：2基本定理例如：定理2.3.2则原问题无界。2基本定理例如：定理2.3.3对应则2基本定理定理2.3.4对于任何非退化的线性规划问题，从任何基本可行解开始，经过有限多次迭代，或者得到一个基本可行的最优解，或者作出该线性规划问题无界的判断。3单纯形方法Step1将线性规划问题化成典式,求出各个非基变量的检验数。Step2判断所有非基

3、变量的检验数是否非正,若是,则结束；否则转step3。Step3选取一个检验数大于零的非基变量为进基变量；Step4若进基变量所对应的约束条件系数全为非正数,则原问题无界,结束；否则,按最小比值原则确定出基变量；Step5进行迭代(用方程组的初等行变换法确定新的基对应的典式及检验数),转step2。4单纯形表例1求解LP问题Z01-2000x1x4x51-210001-31001-101212x1x2x3x4x5RHSZ01-2000x1x4x51-210001-31001-101212x1x2x3x4x5RHSZ001-10-1x1x2x510-52001-310002-11411检验数转

4、轴元Z001-10-1x1x2x510-52001-310002-11411Z000-0.5-0.5-1.5x1x2x3100-0.52.5010-0.51.5001-0.50.56.52.50.5最优解：x*=(6.5,2.5,0.5,0,0)T最优值：z*=-1.5例2：解LP问题4单纯形表Z012000x1x2x3100-0.52.5010-0.51.5001-0.50.56.52.50.5x1x2x3x4x5Z0001.5-2.5-3.5x1x2x3100-0.52.5010-0.51.5001-0.50.56.52.50.5此问题无界RHS例3：解LP问题4单纯形表Z0000-

5、118x1x4x2101000031-101-3/201/2463x1x2x3x4x5Z0000-118x1x3x2100-1/31/30011/3-1/30101/20226此问题有多解。RHS小结(一).将标准线性规划模型转化为典式，理解基本定理.(二).会用单纯形表解线性规划问题.(三).作业74页1216(1)