运筹学大学课件2-1单纯形法原理文档

第一节单纯形法原理继续返回

本节通过一个引例，可以了解利用单纯形法求解线性规划问题的思路，并将每一次的结果与图解法作一对比，其几何意义更为清楚。第一节单纯形法原理

引例（上一章例）求解线性规划问题的基本思路1、构造初始可行基；2、求出一个基可行解（顶点）3、最优性检验：判断是否最优解；4、基变化，转2。要保证目标函数值比原来更优。从线性规划解的性质可知求解线性规划问题的基本思路。第1步确定初始基可行解

根据显然，可构成初等可行基B。

为基变量

第2步求出基可行解

基变量用非基变量表示，并令非基变量为0时对应的解是否是最优解？第3步最优性检验分析目标函数检验数<=0时，最优解>0时，无解换基，继续只要取或的值可能增大。换入？基变量换出？基变量考虑将或换入为基变量第4步基变换换入基变量：换入变量

（即选最大非负检验数对应的变量）一般选取对应的变量均可换入。换出变量使换入的变量越大越好同时，新的解要可行。选非负的最小者对应的变量换出为换入变量，应换出？变量。思考：当时会怎样？因此，基由变为

转第2步：基变量用非基变量表示。

第3步：最优性判断检验数存在正，按第4步换基继续迭代均非正，停止（这时的解即是最优解）为换入变量，应换出

变量。

转第2步

继续迭代,可得到:最优值Ｚ＝１４最优解结合图形法分析（单纯形法的几何意义）6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1A(0,3)B(2,3)C(4,2)D(4,0)单纯形法迭代原理从引例中了解了线性规划的求解过程，将按上述思路介绍一般的线性规划模型的求解方法——单纯形法迭代原理。单纯形法迭代原理由定理3可知，如果线性规划问题存在最优解，一定有一个基可行解是最优解。因此单纯形法迭代的基本思想是：先找出一个基可行解，判断其是否为最优解，如为否，则转换到相邻的基可行解，并使目标函数值不断增大，一直找到最优解为止。观察法:直接观察得到初始可行基≤约束条件:加入松弛变量即形成可行基。（下页）≥约束条件:加入非负人工变量,以后讨论.1、初始基可行解的确定1、初始基可行解的确定不妨设为松弛变量，则约束方程组可表示为1、初始基可行解的确定

其系数矩阵中存在一单位矩阵1、初始基可行解的确定称为基向量，同时对应的变量称为基变量，其它变量称为非基变量。

1、初始基可行解的确定2、最优性检验与解的判别

2、最优性检验与解的判别

2、最优性检验与解的判别

(1)最优解判别定理：若：为基可行解，且全部则为最优解。（2）唯一最优解判别定理：若所有则存在唯一最优解。

2、最优性检验与解的判别

（3）无穷多最优解判定定理：若：且存在某一个非基变量则存在无穷多最优解。（4）无界解判定定理：若有某一个非基变量并且对应的非基变量的系数

则具有无界解（或无最优解）。

2、最优性检验与解的判别

（4）之证明：2、最优性检验与解的判别最优解判断小结

（用非基变量的检验数）所有

基变量中有非零人工变量某非基变量检验数为零唯一最优解无穷多最优解无可行解对任一有

换基继续YYYYNNN无界解N以后讨论3、基变换注意：只要对应的变量均可作为入基变量此时，目标函数入基变量确定

出基变量确定3、基变换则对应的为出基变量.Z大大（在可行的范围内）4、迭代运算

写成增广矩阵的形式,进行迭代