单纯形法

运筹学第二章总结，单纯形法是一种用于求解线性规划问题的迭代方法。包含单纯形法(≤)、 大M法(≥或=)、两阶段法(含人工变量等内容。

单纯形法

• 单纯形法（≤）
  • step1:化为标准型
  • step2:得到 初始基本可行解、初始单纯形表
  • step3:观察 检验数Cj-Zj（非基变量）
    • 所有非基变量检验数≤0
      • 得到最优解
    • 至少有一个非基变量的检验数＞0 且对应的系数向量中至少有一个aij＞0
      • 继续迭代
    • 至少有一个非基变量的检验数＞0 但对应的系数向量中所有aij≤0
      • 无最优解
  • step4:确定输入、输出变量
    • 确定输入变量Xk（标出对应列）
      • 最大检验数对应变量
    • 确定输出变量XL（标出对应行）
      • q=min{bi/aik|aik＞0}=bl/alk 即bi与对应行第k列的系数的比值，最小的比值对应的 变量系数所在行代表输出行
    • 得到主元素alk（第k列第l行对应的系数）
  • step5:系数变换，迭代得到新的单纯形表
    • aij(上面一横)
      • 换出行：=alj/alk
      • 非换出行：=aij-aik*alj/alk
    • bij（上面一横）
      • 换出行：=bl/blk
      • 非换出行：=bi-aik*bl/alk
  • step6:重复step3-5,不断迭代，直到通过检验
• 大M法（≥或=）
  • 找不到初始基变量时，设置人工变量，并令它的系数为
    • 求min:M
    • 求max:-M
    • M为充分大的正数，无经济意义
  • 解法与单纯形法相同
  • 最优解要求
    • 最优单纯形表中，基变量中不含人工变量
• 两阶段法（含人工变量）
  • 阶段一
    • step1:更换目标函数（定义新的目标函数系数）
      • 人工变量：
        • cij=-1,求max
        • cij=1,求min
      • 非人工变量：cij=0
    • step2:单纯形法求解
      • 目标函数值=0
        • 阶段二
      • 否则原问题无可行解
        • 结束计算
  • 阶段二
    • step3:恢复目标函数，去掉人工变量
      • 以step2中得到的单纯形表为基础进行系数变换， 得到更新后的单纯形表
    • step4:利用单纯形法迭代，直到找到最优解
• 解的讨论（基于单纯形表）
  • 无可行解
    • 最优单纯形表中含人工变量
  • 无限届解
    • 求解过程中，单纯形表内的大于0的检验数对应的系数列向量 中aij的值全部为负数或0
  • 退化解
    • 基本可行解中的非零变量个数＜约束条件数
  • 多重解
    • 通过检验的最优单纯形表中：检验数为0的个数＞基变量个数 （如果最后存在两组最优解，那么一定有无穷多组最优解）