线性规划

线性规划性质与求解线性规划问题方法，约束的极点集和基本可行解集等价（即基本可行解点就是极点），从而线性规划问题可归结为求最优基本可行解。

线性规划

• 基本性质
  • 1、可行域为凸集
  • 2、若存在有限最优解，则最优值一定在某极点
  • 3、存在有限最优解的充要条件：cdi为非负数，其中di为可行域的极方向
• 基本可行解
  • 约束的极点集和基本可行解集等价（即基本可行解点就是极点），从而线性规划问题可归结为求最优基本可行解
• 求解线性规划问题
  • 非单纯形表
  • 线性规划的对偶问题
    • 性质
      • 对偶定理
        • cx>=wb
      • 若线性规划问题存在一个对应基B的最优基本可行解，则单纯形乘子w=Cb*B-1是对偶问题的一个最优解
      • 互补松弛性质
    • 通过求解对偶问题来求解原问题
  • 单纯形表
    • 有现成单位阵
    • 无现成单位阵
      • 引入人工变量（最优条件:判别数全为负数；；若出现正判别数对应的y全为负，则问题无界，不存在有限最优解；；若出现人工变量不为0，则无可行解）
        • 两阶段法
          • 若第一阶段达到最优解后，人工变量为基变量，则需要驱离人工变量（在人工变量对应行选非零项做对应列的列主元消去
        • 大M法
      • 不引入人工变量，将b变为负（最优条件：b全为正）
        • 对偶单纯形表
          • 若无对偶可行基本解，则引入扩展问题，使判别数全为0