运筹学单纯形法计算步骤ppt课件.ppt

第四节单纯形法的计算步骤 为书写规范和便于计算 对单纯形法的计算设计了 每一次迭代对应一张单纯形表 含初始基可行解的单纯形表称为初始单纯形表 含最优解的单纯形表称为最终单纯形表 本节介绍用单纯形表计算线性规划问题的步骤 单纯形表 在上一节单纯形法迭代原理中可知 每一次迭代计算只要表示出当前的约束方程组及目标函数即可 B基矩阵 N非基阵 基变量XB 非基变量XN 0 单纯形表 单纯形表 21000 检验数 单纯形表结构 单纯形表 C 已知 21000 24 65 1 C 检验数 单纯形表结构 单纯形表 基可行解 单纯形表结构 单纯形表 有时不写此项 求 单纯形表结构 单纯形表 求 单纯形表结构 单纯形表 求 不妨设此为主列 主行 单纯形表结构 单纯形表 主元 用单纯形表求解例1 表1 列初始单纯形表 单位矩阵对应的变量为基变量 23000 000 81612 23000 23000 000 81612 23000 正检验数中最大者对应的列为主列 最小的值对应的行为主行 主元化为1主列单位向量换出换入 表1 列初始单纯形表 单位矩阵对应的变量为基变量 23000 003 2163 000 2 3 4 正检验数中最大者对应的列为主列 最小的值对应的行为主行 主元化为1主列单位向量换出换入 表2 基变换 初等行变换 主列化为单位向量 主元为1 23000 203 283 00 201 4 表3 基变换 初等行变换 主列化为单位向量 主元为1 00 3 2 1 80 23000 203 442 检验数 0 表4 最终单纯形表 用单纯形表求解LP问题例 解 化标准型 21000 000 15245 21000 表1 列初始单纯形表 单位矩阵对应的变量为基变量 210000150510002462010051100121000 主元化为1主列单位向量换出换入 正检验数中最大者对应的列为主列 最小的值对应的行为主行 表1 列初始单纯形表 单位矩阵对应的变量为基变量 21000015051002412 601 600104 60 1 6101 30 1 30 检验数 0确定主列 最小确定主行 主元 表2 基变换 初等行变换 主列化为单位向量 主元为1 检验数 0 表3 基变换 初等行变换 主列化为单位向量 主元为1 210000150510002462010051100121000 思考 一般主列选择正检验数中最大者对应的列 也可选择其它正检验数的列 以第2列为主列 用单纯形法求解 正检验数对应的列为主列 单纯形法的解的情况 单纯形法求解线性规划问题 解的情况也有四种 唯一最优解 上面的情况 所有的检验数都小于等于0 并且非基变量的检验数都小于零无穷多解无界解无解 下界讨论 单纯形法的解的情况 例2 第一步 转换为标准形式 单纯形法的计算步骤 构造单纯形表 单纯形法解的情况 8 0 14 0 和 2 4 8 4 0 0 都是最优解 当有一个非基变量的检验数 imp 值为0时 线性规划问题有多重最优解任意最优解为 8 0 14 0 1 2 4 8 4 0 0 C D 1 2 单纯形法的解的情况 单纯形法求解线性规划问题 解的情况也有四种 唯一最优解 上面的情况 所有的检验数都小于等于0 并且非基变量的检验数都小于零无穷多解 所有的检验数都小于等于0 至少有一个非基变量的检验数为0无界解无解 下界讨论 单纯形法解的情况 例 转换为标准形式 单纯形法的基本思想 最优解的判断若为一基本可行解 有一个 并且对一切 有 那么该线性规划问题有无界解 单纯形法解的情况 X3可以增长到无穷大 所以线性规划问题有无界解 单纯形法的解的情况 单纯形法求解线性规划问题 解的情况也有四种 唯一最优解 上面的情况 所有的检验数都小于等于0 并且非基变量的检验数都小于零无穷多解 所有的检验数都小于等于0 至少有一个非基变量的检验数为0无界解 如果某imp 0