第四次课与 表上作业法及大M法和两阶段法 .pptVIP

单纯形表 在上一节单纯形法迭代原理中可知，每一次迭代计算只要表示出当前的约束方程组及目标函数即可。 单纯形表 一、大M法 二、两阶段法 人工变量法 加入人工变量,构造初始可行基. 一、大 M 法 人工变量在目标函数中的系数为 -M, 其中，M 为任意大的正数。 例: 求解线性规划问题 解: 二、两阶段法 第一阶段: 构造如下的线性规划问题 用单纯形法求解上述问题,若ω=0,进入第二阶段,否则,原问题无可行解。 第二阶段：去掉人工变量，还原目标函数系数，做出初始单纯形表。 用单纯形法求解即可。 单纯形法计算中的几个问题 M在计算机上处理困难。 分阶段处理—— 先求初始基，再求解。 二、两阶段法 人工变量的 系数矩阵为 单位矩阵， 可构成初始 可行基。 目标函数仅含人工变量，并要求实现最大化。 若其最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，则原线性规划问题无可行解。 二、两阶段法 下面举例说明，仍用大M法的例。 例： 二、两阶段法 二、两阶段法 构造第一阶段问题并求解 解： 用单纯形法求解 * * 2.4 单纯形法的计算步骤 为书写规范和便于计算，对单纯形法的计算设计了单纯形表。每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。本节介绍用单纯形表计算线性规划问题的步骤。 E 单位阵 N 非基阵 基变量XB 非基变量XN 0 2 1 0 0 0 检验数 单纯形表结构 单纯形表 — 24/6 5/1 C 已知 2 1 0 0 0 — 24/6 5/1 C 检验数 单纯形表结构 单纯形表 基可行解： 单纯形表结构 单纯形表 2 1 0 0 0 — 24/6 5/1 C 检验数 有时不写此项 求 单纯形表结构 单纯形表 2 1 0 0 0 — 24/6 5/1 C 检验数 求 单纯形表结构 单纯形表 2 1 0 0 0 — 24/6 5/1 C 检验数 求 不妨设此为主列 主行 单纯形表结构 单纯形表 2 1 0 0 0 — 24/6 5/1