1、上页上页上页上页下页下页下页下页返回返回返回返回第一节第一节 单纯形法原理单纯形法原理 继续继续继续继续返回返回返回返回上页上页上页上页下页下页下页下页返回返回返回返回 本节通过一个引例，可以了解利用本节通过一个引例，可以了解利用单纯形法求解线性规划问题的思路，并单纯形法求解线性规划问题的思路，并将每一次的结果与图解法作一对比，其将每一次的结果与图解法作一对比，其几何意义更为清楚。几何意义更为清楚。第一节第一节 单纯形法原理单纯形法原理 上页上页上页上页下页下页下页下页返回返回返回返回引例引例（上一章例）（上一章例）上页上页上页上页下页下页下页下页返回返回返回返回求解线性规划问题的基本思路1、
2、构造初始可行基；2、求出一个基可行解（顶点）3、最优性检验：判断是否最优解；4、基变化，转2。要保证目标函数值比 原来更优。从线性规划解的性质可知求解从线性规划解的性质可知求解线性规划问题的基本思路。线性规划问题的基本思路。上页上页上页上页下页下页下页下页返回返回返回返回第1步 确定初始基可行解 根据根据显然显然，可构成初等可行基可构成初等可行基B。为基变量上页上页上页上页下页下页下页下页返回返回返回返回 第2步 求出基可行解 基变量用非基基变量用非基变量表示，并变量表示，并令非基变量为令非基变量为 0时对应的解时对应的解是否是最优解？上页上页上页上页下页下页下页下页返回返回返回返回第3步 最
3、优性检验分析目标函数检验数检验数0 时，时，无解无解换基，继续换基，继续只要取只要取 或或 的的 值可能增大。值可能增大。换入？基变量换入？基变量换出？基变量换出？基变量考虑将考虑将 或或 换入为基变换入为基变量量上页上页上页上页下页下页下页下页返回返回返回返回第4步 基变换换入基变量：换入变量 （即选最大非负检验数对应的变量）一般选取一般选取 对应的变量均可均可换入。上页上页上页上页下页下页下页下页返回返回返回返回换出变量使换入的变量越大越好同时，新的解要可行。选非负 的最小者对应的变量换出为换入变量，应换出？变量。思考：当 时会怎样？上页上页上页上页下页下页下页下页返回返回返回返回因此，基
4、由 变为 转第转第2步：基变量用非基变量表示。步：基变量用非基变量表示。第第3步：最优性判断步：最优性判断 检验数检验数 存在正，按第存在正，按第4步换基继续步换基继续迭代迭代 均非正，停止均非正，停止 （这时的解即是最优解）（这时的解即是最优解）为换入变量，应换出 变量。上页上页上页上页下页下页下页下页返回返回返回返回 转转 第第2步步上页上页上页上页下页下页下页下页返回返回返回返回 继续迭代,可得到:最优值最优解上页上页上页上页下页下页下页下页返回返回返回返回结合图形法分析（单纯形法的几何意义）6 5 4 3 2 1 0 x2|123456789x1A(0,3)B(2,3)C(4,2)D(
5、4,0)上页上页上页上页下页下页下页下页返回返回返回返回单纯形法迭代原理单纯形法迭代原理从引例中了解了线性规划的求解过程，将按上述思路介绍一般的线性规划模型的求解方法单单纯形法迭代原理纯形法迭代原理。上页上页上页上页下页下页下页下页返回返回返回返回单纯形法迭代原理单纯形法迭代原理由定理3可知，如果线性规划问题存在最优解，一定有一个基可行解是最优解。因此单纯形法迭代的基本思想是：先找出一个基可行解，判断其是否为最优解，如为否，则转换到相邻的基可行解，并使目标函数值不断增大，一直找到最优解为止。上页上页上页上页下页下页下页下页返回返回返回返回观察法:直接观察得到初始可行基约束条件:加入松弛变量即形
6、成可行基。（下页）约束条件:加入非负人工变量,以后讨论.1、初始基可行解的确定上页上页上页上页下页下页下页下页返回返回返回返回1 1、初始基可行解的确定、初始基可行解的确定 不妨设不妨设 为松弛变量，为松弛变量，则约束方程组可表示为则约束方程组可表示为上页上页上页上页下页下页下页下页返回返回返回返回1 1、初始基可行解的确定、初始基可行解的确定 其系数矩阵中存在一单位矩阵上页上页上页上页下页下页下页下页返回返回返回返回1 1、初始基可行解的确定、初始基可行解的确定称为基向量，同时对应的变量称为基变量，其它变量称为非基变量。上页上页上页上页下页下页下页下页返回返回返回返回 1 1、初始基可行解的
7、确定、初始基可行解的确定上页上页上页上页下页下页下页下页返回返回返回返回2 2、最优性检验与解的判别、最优性检验与解的判别上页上页上页上页下页下页下页下页返回返回返回返回 2 2、最优性检验与解的判别、最优性检验与解的判别上页上页上页上页下页下页下页下页返回返回返回返回 2 2、最优性检验与解的判别、最优性检验与解的判别上页上页上页上页下页下页下页下页返回返回返回返回(1)最优解判别定理：若：为基可行解，且全部 则 为最优解。（2）唯一最优解判别定理：若所有 则存在唯一最优解。2 2、最优性检验与解的判别、最优性检验与解的判别上页上页上页上页下页下页下页下页返回返回返回返回（3）无穷多最优解判
8、定定理：若：且存在某一个非基变量 则存在无穷多最优解。（4）无界解判定定理：若有某一个非基 变量 并且对应的非基变量的系数 则具有无界解（或无最优解）。2 2、最优性检验与解的判别、最优性检验与解的判别上页上页上页上页下页下页下页下页返回返回返回返回（4）之证明）之证明：2 2、最优性检验与解的判别、最优性检验与解的判别上页上页上页上页下页下页下页下页返回返回返回返回最优解判断小结 （用非基变量的检验数）所有 基变量中有非零人工变量某非基变量检验数为零唯一最优解无穷多最优解无可行解对任一 有 换基继续YYYYNNN无界解N以后以后讨论讨论上页上页上页上页下页下页下页下页返回返回返回返回3、基变
9、换注意注意：只要只要 对应的变对应的变量量 均可作为入基变量均可作为入基变量此时，目标函数此时，目标函数l入基变量确定入基变量确定上页上页上页上页下页下页下页下页返回返回返回返回 出基变量确定3 3、基变换、基变换则对应的则对应的 为出基变量为出基变量.Z 大大大大（在可行的范围内（在可行的范围内）上页上页上页上页下页下页下页下页返回返回返回返回4、迭代运算 写成增广矩阵的形式,进行迭代.上页上页上页上页下页下页下页下页返回返回返回返回4 4、迭代运算、迭代运算例：上页上页上页上页下页下页下页下页返回返回返回返回4 4、迭代运算、迭代运算非基变量非基变量基变量基变量001通过初等行变通过初等行变换化主列为换化主列为主元主元上页上页上页上页下页下页下页下页返回返回返回返回 4 4、迭代运算、迭代运算每次迭代的信息都每次迭代的信息都每次迭代的信息都每次迭代的信息都在增广矩阵及目标在增广矩阵及目标在增广矩阵及目标在增广矩阵及目标函数中。函数中。函数中。函数中。检验数检验数上页上页上页上页下页下页下页下页返回返回返回返回第一节第一节 单纯形法迭代原理单纯形法迭代原理
