Operation Research

OR

👋 Welcome to OR!

LP & Simplex

• Basic concept
  • 约束方程系数矩阵，,
  • 当确定某一子矩阵为基矩阵时，基矩阵对应的列向量为基向量，其余列向量为非基向量
  • 基向量对应的变量为基变量，非基变量对应的变量为非基变量
  • 基变量、非基变量是针对某一确定 基 而言，不同 基 对应的基变量和非基变量也不同
  • 可行解：满足约束方程的解
  • 最优解：使目标函数达到最优值的解
  • 基本解：对于某一确定的基B，令非基变量为0，解出基变量，这组解称基B 的基本解
  • 基本可行解：基本解是可行解
  • 基本最优解：基本解是最优解
  • 基可行解对应的基：可行基；基本最优解对应的基：最优基
  • 凸集、凸组合、极点
• Simplex
  • LP标准型
    • 目标函数最大值（最小值）、约束条件均为等式方程、变量、常数
    • 无约束，转化为
    • + 松弛变量 - 剩余变量
  • 单纯性表
    • 最大化问题，检验数小于等于0得到最优解
    • 多重最优解：存在非基变量检验数等于0
    • 无界解：某检验数大于0且对应向量小于等于0
  • 大M法、两阶段法
    • 大M
      • 约束条件引入人工变量，最大化问题目标函数
    • 两阶段
      • 第一阶段目标函数为最小化人工变量和，求得解
      • 基可行解作为初始可行解（单纯性表续），为原目标函数
    • 无可行解
      • 大M法：最优解中含有不为0的人工变量
      • 两阶段：第一阶段的最优值不为0
  • 退化与循环
    • 基本可行解中存在基变量为0，为退化基本可行解

Dual Problem

• 对偶性质

  • 对称性：对偶问题的对偶是原问题

  • 最优性：为LP、DP的可行解，是最优解当且仅当

  • 弱对偶性：为

    LP、DP

    的可行解，则$CX

    ≤Y

    b$

    • 对偶问题任意解的值为原问题目标值上界；原问题任意解的值为对偶问题目标值下界
    • 问题可行且具有无界解，则另一问题无可行解
    • 原问题可行，另一问题不可行，则原问题无界解

  • 对偶性：LP有最优解，则DP也有最优解，且最优值相等

    • LP DP都有可行解，则都有最优解
    • 一个问题无最优解，另一问题也无最优解

  • 互补松驰性：为LP、DP的可行解，和是松弛变量的可行解，X* Y是最优解当且仅当$YsX=0$$、Y*Xs=0$

  • 检验数的相反数

    对应DP的一组基本解

    • 第j个决策变量检验数的相反数对应DP第j个松弛变量的解
    • 第i个松弛变量检验数的相反数对应DP第i个对偶变量的解
    • • 检验数对应LP的一组基本解

Dijkstra

• Dijkstra Algorithm
• Bellman-Ford、Floyd algorithm

Branch and Bound

Branch and Cut

• Branch and bound + Cutting plane

Lagrangian Relaxation

Column Generation

Branch and price

DW decomposition

Benders decomposition