《单纯形法原理讲解精.ppt》由会员分享，可在线阅读，更多相关《单纯形法原理讲解精.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、单纯形法原理讲解第1页，本讲稿共28页引例（上一章例）第2页，本讲稿共28页求解线性规划问题的基本思路1、构造初始可行基；2、求出一个基可行解（顶点）3、最优性检验：判断是否最优解；4、基变化，转2。要保证目标函数值比 原来更优。从线性规划解的性质可知求解线性规划问题的基本思路。第3页，本讲稿共28页第1步 确定初始基可行解根据显然，可构成初等可行基B。为基变量第4页，本讲稿共28页 第2步 求出基可行解 基变量用非基变量表示，并令非基变量为 0时对应的解是否是最优解？第5页，本讲稿共28页第3步 最优性检验分析目标函数检验数0 时，无解换基，继续只要取 或 的 值可能增大。换入？基变量换出？
2、基变量考虑将 或 换入为基变量第6页，本讲稿共28页第4步 基变换l换入基变量：（即选最大非负检验数对应的变量）（即选最大非负检验数对应的变量）一般选取 对应的变量均可换入。第7页，本讲稿共28页l换出变量使换入的变量越大越好同时，新的解要可行。选非负 的最小者对应的变量换出为换入变量，应换出？变量。思考：当 时会怎样？第8页，本讲稿共28页因此，基由 变为 转第2步：基变量用非基变量表示。第3步：最优性判断 检验数 存在正，按第4步换基继续迭代 均非正，停止（这时的解即是最优解）为换入变量，应换出 变量。第9页，本讲稿共28页 转 第2步第10页，本讲稿共28页 继续迭代,可得到:最优值最优
3、解第11页，本讲稿共28页l结合图形法分析（单纯形法的几何意义）6 5 4 3 2 1 0 x2|1 2 3 4 5 6 7 8 9x1A(0,3)B(2,3)C(4,2)D(4,0)第12页，本讲稿共28页单纯形法迭代原理从引例中了解了线性规划的求解过程，将按上述思路介绍一般的线性规划模型的求解方法单纯形法迭代原理。第13页，本讲稿共28页l观察法:直接观察得到初始可行基l约束条件:加入松弛变量即形成可行基。（下页）l约束条件:加入非负人工变量,以后讨论.1、初始基可行解的确定第14页，本讲稿共28页1、初始基可行解的确定 不妨设 为松弛变量，则约束方程组可表示为第15页，本讲稿共28页 1
4、、初始基可行解的确定第16页，本讲稿共28页2、最优性检验与解的判别第17页，本讲稿共28页 2、最优性检验与解的判别代入目标函数有：第18页，本讲稿共28页 2、最优性检验与解的判别第19页，本讲稿共28页l(1)最优解判别定理：若：为基可行解，且全部 则 为最优解。l（2）唯一最优解判别定理：若所有 则存在唯一最优解。2、最优性检验与解的判别第20页，本讲稿共28页l（3）无穷多最优解判定定理：若：且存在某一个非基变量 则存在无穷多最优解。l（4）无界解判定定理：若有某一个非基 变量 并且对应的非基变量的系数 则具有无界解。2、最优性检验与解的判别第21页，本讲稿共28页（4）之证明：2、
5、最优性检验与解的判别第22页，本讲稿共28页所有 基变量中有非零人工变量某非基变量检验数为零唯一最优解无穷多最优解无可行解对任一 有 换基继续YYYYNNN无界解N以后讨论第23页，本讲稿共28页3、基变换l换入变量确定 对应的 为换入变量.(一般)注意：只要 对应的变量 均可作为换入变量此时，目标函数第24页，本讲稿共28页 l换出变量确定3、基变换Z 大大（在可行的范围内）第25页，本讲稿共28页4、迭代运算 写成增广矩阵的形式,进行迭代.第26页，本讲稿共28页例：4、迭代运算非基变量 基变量001通过初等行变换化主列为主元第27页，本讲稿共28页 4、迭代运算每次迭代的信息都 每次迭代的信息都在增广矩阵及目标 在增广矩阵及目标函数中。函数中。检验数第28页，本讲稿共28页