运筹学课程笔记

发表于 2024-12-20 更新于 2025-12-30 分类于课程笔记阅读次数：本文字数： 1.5k 阅读时长 ≈ 1 分钟

本文是运筹学的课程学习笔记。

规划论
- 线性规划
  - 不等式转化为等式约束：添加松弛变量
    - 如果松弛变量为零，表明资源全部用完，该资源是匮乏的；如果松弛变量为正，表明资源尚有余存，该资源是充裕的
  - 无限制变量：拆成两个 $y=y^--y^+$ ，单纯形法中，二者不可能同时取正
  - 单纯形法：
    - 首先构造初始解， $x_i=0$
    - 选进基变量：系数最大；离基变量：z/a最小
    - 枢轴行：1) 在基列中以进基变量替换离基变量 2) 新的枢轴行=当前枢轴行÷枢轴元素
      其他所有行，包括Z行：新的行=当前行-当前枢轴列的系数×新的枢轴列
  - 阶段一试图求一个初始基本可行解，找到一个解以后，调用阶段二求解原问题
    - 一阶段目标值为0表示解存在
  - 单纯形法的特殊情况：
    - 退化：约束多余，至少有一个基变量在下一次迭代中为零，并称新的解退化。遇到退化时不可以停止计算，因为可能出现暂时退化。
    - 可选择最优解：目标函数可以在多于一个解点处相同的最优解
    - 无界解：解空间中至少又一个变量是无界的
    - 不可行解：具有不相容约束的线性规划模型没有可行解。仅当模型有可行空间时，人工变量在最优解处可以取零
  - 灵敏度分析：约束右端项变化一个单位对目标函数的影响。只有在变化量处于灵敏度范围内时，对偶价格才有效
- 整数规划方法：分支定界法、0-1规划
- 动态规划
整数规划
- 对于足够大的数M，或者-或者约束/如果-那么约束可以用下面两个并的约束代替
  
  My_{ij}+(x_i-x_j)\ge p_j$ 和 $My_{ji}+(x_j-x_i)\ge p_i
- 分支定界法：
  - 维护两个量：上界（对应线性规划问题的最优解）和下界（满足整数约束的最优解）
    - 每个松弛问题的最优值均是相应整数规划问题最优值的上界。
    - 在求解子问题的松弛问题时：
      1. 若松弛问题无可行解，则相应的子问题也无可行解，舍弃不再分支。
      2. 若松弛问题的解满足整数性约束，则此解为相应子问题的最优解，此时不再分支。如果目标函数值大于目前的下界值，则修改下界值。
      3. 如果松弛问题的解不满足整数性约束，但目标函数值不大于目前的下界值，则不再分支。(剪枝）
      4. 若松弛问题的解不满足整数性约束，但目标函数值大于目前的下界值，则对应的子问题需要进一步分支。
- 0-1型整数规划：
  - 采用优化后的穷举法
    - 对每个解，依次代入约束条件左侧，求出数值，看是否适合不等式条件，如某一条件不适合，同行以下各条件就不必再检查，因而就减少了运算次数。
    - 一般常重新排列 $x_i$ 的顺序使目标函数中 $x_i$ 的系数是递增(不减)的。这样，最优解容易比较早的发现。
图论
- 基本概念
- 欧拉回路：经过每条边一次的回路；欧拉路
- 哈密顿回路：经过每个点一次的回路；哈密顿路
- 最短路、最大流最小割定理、生成树
- Ford-Fulkerson可用于解决最大流问题
计算理论
- 问题分类：
  - P：可多项式求解；NP：可多项式验证；EXP：可指数复杂度求解
  - NP-Complete：一个NP问题，且所有NP都可以归约成NPC问题，例：3-SAT、SAT、Hamiton路
  - NP-Hard：所有问题都可以归约成NP-Hard
  - $P \subseteq NP \subseteq EXP,~P \neq EXP$
  - $\text{NP} \neq \text{co-NP} \to \text{P} \neq \text{NP}$
- 问题归约：
  - $X \le_P Y$ ：X不难于Y、X可以在多项式复杂度内归约成Y
数值计算
- KKT条件：有不等式约束问题的必要条件，通常结合Lagrange乘数法
- x为极小值 = x的Hessian矩阵正定 = Hessian矩阵的每一个顺序主子式都 >0（即左上角的k阶矩阵）