线性规划
多面体模型
- 多面体：由一组线性约束定义的可行域。
- 极点（“绿点”）：由若干起作用约束（不等式成为等式）确定的唯一解，即可行域的顶点。
- 最优解必为某一极点（讨论三种情况：内点；边界且目标梯度与边界正交；边界且不正交）。
标准型
- 标准形式：最小化或最大化线性目标，约束为等式并附非负性限制。
- 松弛变量与引入基变量用于转化不等式为等式。
单纯形法
- 迭代在极点间移动以改善目标值，直到达到最优极点。
- 特殊情况：退化（基变量为0）、多重最优解、无界解、无可行解。
- 初始可行解的获取：人工变量法、两阶段法等。
- 对偶单纯形法：当基解满足最优性但不满足可行性时使用。
基于逆矩阵的单纯形迭代
- 使用基矩阵逆更新基解与灵敏系数，减少每步计算量。
- 通过列替换和更新公式维持效率。
对偶问题与互补关系
- 每个线性规划都有对应的对偶问题（标准型与对偶型）。
- 互补松弛（互补性条件）：原问题与对偶问题的基解在最优时满足互补松弛条件。
- 弱对偶性：任一原问题可行解的目标值都是对偶问题最优目标的下界/上界（取决于最大/最小化）。
- 强对偶性：若一方存在最优解，则另一方也存在且两者最优目标值相等。
影子价格与灵敏度分析
- 影子价格（对偶变量）表示约束右端项微小变动对目标值的边际影响。
- 灵敏度分析包括系数变化、右端项变化和基结构稳定性分析。
- 参数化线性规划：分析目标或约束参数在区间内变化对最优解的影响。
整数与0-1线性规划
- 割平面法：通过加入有效割约束逐步切除非整点解。
- 分枝定界法：枚举式搜索结合界值剪枝以求整数最优解。
- 0-1问题常见模型：选择性约束（p-选q等形式）、背包、指派等。
动态规划
- 分阶段模型：将问题分解为若干阶段和状态转移。
- 最优性原理：子问题的最优解构成原问题最优解的部分。
- 主要算法：值迭代与策略迭代（用于确定最优策略与价值函数）。
- 适用场景：序列决策、资源分配、最短路径、背包的分阶段解法等。