单纯形法原理讲解课件

1、单纯形法原理讲解,本节通过一个引例，可以了解利用单纯形法求解线性规划问题的思路，并将每一次的结果与图解法作一对比，其几何意义更为清楚。,单纯形法原理讲解,引例（上一章例）,单纯形法原理讲解,求解线性规划问题的基本思路,1、构造初始可行基； 2、求出一个基可行解（顶点） 3、最优性检验：判断是否最优解； 4、基变化，转2。要保证目标函数值比 原来更优。,从线性规划解的性质可知求解线性规划问题的基本思路。,单纯形法原理讲解,第1步 确定初始基可行解,根据,显然 ， 可构成初等可行基B 。,为基变量,单纯形法原理讲解,第2步 求出基可行解,基变量用非基变量表示，并令非基变量为 0时对应的解,是否是最

2、优解？,单纯形法原理讲解,第3步 最优性检验,分析目标函数,检验数,0 时，,无解 换基，继续,只要取 或 的 值可能增大。,换入？基变量 换出？基变量,考虑将 或 换入为基变量,单纯形法原理讲解,第4步 基变换,换入基变量：,换入变量,均可换入。,单纯形法原理讲解,换出变量,使换入的变量越大越好 同时，新的解要可行。,选非负 的最小者对应的变量换出,为换入变量，应换出 ？ 变量。,思考：当 时会怎样？,单纯形法原理讲解,因此，基由 变为,为换入变量，应换出 变量。,单纯形法原理讲解,转 第2步,单纯形法原理讲解,继续迭代, 可得到:,最优值,最优解,单纯形法原理讲解,结合图形法分析（单纯形法

3、的几何意义）,A(0,3),B(2,3),C(4,2),D(4,0),单纯形法原理讲解,单纯形法迭代原理,从引例中了解了线性规划的求解过程，将按上述思路介绍一般的线性规划模型的求解方法单纯形法迭代原理。,单纯形法原理讲解,观察法:直接观察得到初始可行基 约束条件: 加入松弛变量即形成可行基。（下页） 约束条件: 加入非负人工变量, 以后讨论.,1、初始基可行解的确定,单纯形法原理讲解,1、初始基可行解的确定,不妨设 为松弛变量，则约束方程组可表示为,单纯形法原理讲解,1、初始基可行解的确定,单纯形法原理讲解,2、最优性检验与解的判别,单纯形法原理讲解,2、最优性检验与解的判别,代入目标函数有：

4、,单纯形法原理讲解,2、最优性检验与解的判别,单纯形法原理讲解,(1) 最优解判别定理：若： 为基可行解，且全部 则 为最优解。 （2）唯一最优解判别定理：若所有 则存在唯一最优解。,2、最优性检验与解的判别,单纯形法原理讲解,（3）无穷多最优解判定定理：若： 且存在某一个非基变量 则存在无穷多最优解。 （4）无界解判定定理：若有某一个非基 变量 并且对应的非基变量的系数 则具有无界解。,2、最优性检验与解的判别,单纯形法原理讲解,（4）之证明：,2、最优性检验与解的判别,单纯形法原理讲解,最优解判断小结 （用非基变量的检验数）,以后讨论,单纯形法原理讲解,3、基变换,换入变量确定 对应的 为换入变量. (一般),注意：只要 对应的变量 均可作为换入变量,此时，目标函数,单纯形法原理讲解,换出变量确定,3、基变换,则对应的 为换出变量.,单纯形法原理讲解,4、迭代运算,写成增广矩阵的形式,进行迭代.,单纯形法原理讲解,例：,4、迭代运算,非基