运筹学期末复习要点与知识点体系#

目录#

• 第一章：线性规划与单纯形法辅助技术
• 第二章：对偶理论与对偶单纯形法
• 第三章：灵敏度分析
• 第四章：运输问题
• 第五章：指派问题
• 第六章：目标规划
• 第七章：整数规划
• 第八章：图与网络优化：最大流问题
• 第九章：动态规划

---

第一章：线性规划与单纯形法辅助技术#

当约束条件中包含 $\ge$ 或 $=$ 时，很难直接得到一个可行基。为此需要引入**人工变量（Artificial Variables）**来构造初始基可行解。

1. 大M法（Big M Method）#

• 核心做法：在目标函数中加入人工变量，并给予其一个极大的惩罚系数。对于极大化问题（Max）惩罚系数为 $-M$；对于极小化问题（Min）惩罚系数为 $+M$（其中 $M$ 是一个无限大的正实数）。
• 最优解判别：
  • 若最优单纯形表中，所有人工变量都已出基（即取值为 $0$），则当前解即为原问题的最优解。
  • 若所有检验数已满足最优性条件，但基变量中仍含有非零的人工变量，则说明原问题无可行解。

2. 两阶段法（Two-Phase Method）#

• 第一阶段：不考虑原目标函数，构造一个辅助目标函数，令其为所有人工变量之和并要求最小化（$\min w = \sum x_{ai}$）。
  • 若第一阶段的最优目标值 $w^* > 0$，说明原问题无可行解，迭代终止。
  • 若 $w^* = 0$，说明存在可行解，去掉人工变量，进入第二阶段。
• 第二阶段：将第一阶段得到的基可行解作为初始解，代入原问题的真实目标函数中，继续用单纯形法求解。

---

第二章：对偶理论与对偶单纯形法#

1. 对偶问题的构造规律（★ 大题必考点）#

原始问题（Primal）与对偶问题（Dual）之间的转换是考试的重难点。可以通过以下规律（以原始为 Max 变为对偶为 Min 的“大化小”为例）进行快速转换：

• 系数互换：原始目标函数的系数 $c$ 变成对偶约束的右端项；原始约束的右端项 $b$ 变成对偶目标函数的系数。
• 矩阵转置：原始约束的技术系数矩阵 $A$ 经转置变成对偶约束的系数矩阵 $A^T$。
• 变量与约束的符号对应关系（对称对偶关系）：

原始问题（Primal - Max）	对偶问题（Dual - Min）
约束条件	变量
$\le$（标准方向）	$\ge 0$
$\ge$	$\le 0$
$=$	无约束
变量	约束条件
$\ge 0$	$\ge$（标准方向）
$\le 0$	$\le$
无约束	$=$

2. 互补松弛定理（Complementary Slackness Theorem）#

• 经济与数学意义：若 $X^*$ 和 $Y^*$ 分别为原问题和对偶问题的可行解，它们是最优解的充要条件是：对偶变量乘以对应的原问题松弛变量等于 $0$，且原问题变量乘以对应的对偶问题松弛变量等于 $0$。 $y_i^* \cdot s_i^* = 0 \quad \text{且} \quad x_j^* \cdot e_j^* = 0$
• 考试应用：题目中经常给出原问题的最优解 $X^*$，要求直接写出对偶问题的最优解 $Y^*$。
  1. 利用此定理，凡是原最优解中大于 $0$ 的变量（$x_j^* > 0$），其对应的对偶约束必然取等号（对偶松弛变量 $e_j^* = 0$）；
  2. 原约束中取严格不等式的（松弛变量 $s_i^* > 0$），其对应的对偶变量必为 $0$（$y_i^* = 0$）。
  3. 借此可列出方程组直接求出对偶解，无需用单纯形法重新计算。

3. 影子价格（Shadow Price）#

• 定义：对偶变量的最优解 $y_i^*$ 在经济学上称为资源的影子价格。它代表在资源最优利用时，该种资源每增加一个单位能给总收益带来的边际增量。
• 关键结论：
  1. 若某种资源在最优生产方案中仍有剩余（松弛变量 $> 0$），则其影子价格必定为 $0$（说明继续增加该资源无法带来更多利润）。
  2. 影子价格反映了资源的稀缺程度。影子价格越大，说明该资源越稀缺，企业越有动力去购进。

4. 对偶单纯形法（Dual Simplex Method）#

对偶单纯形法并不是去求解对偶问题，而是一种求解原始问题的方法。它的核心逻辑与普通单纯形法恰好相反。

• 基本思想：在保持“对偶可行性”（即所有检验数 $\sigma_j \le 0$ 的最优性形式）的前提下，通过换基迭代逐步消除原解的不可行性（消除右端项 $b$ 中的负值），最终使原问题可行，从而得到最优解。
• 适用条件：所有非基变量的检验数均 $\le 0$（Max问题），但基解中存在负值（原问题不可行）。
• 常见应用场景：在灵敏度分析中引入新约束条件导致原最优解失效时，或者在割平面法的每一步迭代中。
• 迭代步骤：
  1. 确定出基变量（先选行）：在基变量中，选择**负得最多（绝对值最大）**的那一个作为出基变量。 $x_r = \min \{x_k \mid x_k < 0\}$
  2. 确定入基变量（再选列）：利用 $\theta$ 比例规则，只对出基变量所在行中**系数为负（$a_{rj} < 0$）**的非基变量计算比例： $\theta = \min \left\{ \frac{\sigma_j}{a_{rj}} \ \middle|\ a_{rj} < 0 \right\}$ 对应最小 $\theta$ 值的非基变量 $x_s$ 为入基变量。
  3. 旋转变换（Pivot）：以 $a_{rs}$ 为主元素进行消元变换，使该元素变为 $1$，同列其他元素变为 $0$，然后重新检查是否所有 $x_B \ge 0$。

---

第三章：灵敏度分析（Sensitivity Analysis）#

当线性规划的某些参数发生变化时，我们利用最终单纯形表提供的信息，快速判断对原最优基和最优解的影响：

1. 右端项 $b$（资源限量）发生变化#

• 特点：$b$ 的改变不影响检验数，但会影响解的可行性。
• 分析方法：计算新的解 $X_B' = B^{-1}b'$。
  • 若 $B^{-1}b' \ge 0$，说明原最优基依然可行，原检验数不变，此时原基依然最优。
  • 若 $B^{-1}b'$ 出现负值，说明原基可行性丧失。需要将新数值填入表中，使用对偶单纯形法继续迭代直至重新找到可行最优解。

2. 价值系数 $c_j$（目标系数）发生变化#

• 特点：$c$ 的改变只影响检验数，不影响解的可行性（$B^{-1}b$ 依然非负）。
• 分析方法：重新计算所有非基变量的检验数 $\sigma_j' = c_j' - c_B' B^{-1}P_j$。
  • 若所有检验数依然满足最优性条件（Max 问题全 $\le 0$），则最优解 $X^*$ 不变。
  • 若出现检验数不满足最优性条件，说明原最优解失效，需要从当前表出发继续用单纯形法迭代。

3. 增加新的约束条件#

• 分析方法：将现有的最优解代入新的约束条件中。
  • 若满足，则原最优解依然有效。
  • 若不满足，需将新约束作为新的一行加入最终单纯形表中，利用对偶单纯形法求解。

---

第四章：运输问题（Transportation Problem）#

1. 模型结构与基可行解性质（★ 客观题考点）#

• 系数矩阵特点：运输问题是线性规划的特例，其系数矩阵 $A$ 的每一列中只有两个元素为 $1$，其余均为 $0$（对应一个起点和一个终点）。
• 产销平衡问题：
  • 设产地有 $m$ 个，销地有 $n$ 个。在产销平衡时，独立约束方程的个数为 $m+n-1$。因此，基变量（非零运量）的个数最多为 $m+n-1$。
  • 产销平衡的运输问题必定存在可行解，因此必定存在最优解。
• 产销不平衡问题：
  • 产大于销：虚设一个销地，需求量为产销差额，各产地到该虚设销地的运价为 $0$。
  • 销大于产：虚设一个产地，产量为销产差额，该产地到各销地的运费为 $0$。
  • 基变量变化：不平衡问题通过虚设转化为平衡问题后，相当于多了一行或一列，此时其基变量的个数最多为 $m+n$。

2. 表上作业法（★ 计算题大题常考）#

• 确定初始基可行解：
  • 最小元素法：优先在运费最小的格子中分配运量。方法简单，但可能偏离最优解较远。
  • 伏格尔法（Vogel’s Approximation Method）：通过计算行/列中“最小运费与次小运费的差额”（惩罚值/罚值），优先将运量分给差额最大的一行或一列，能够获得非常接近最优解的初始方案。
• 检验数的计算：
  • 闭合回路法：对每一个空格（非基变量）引闭合回路（拐角点除该空格外必须都是基变量），计算回路中运价的交替正负和。
  • 位势法：为每行引入 $u_i$，每列引入 $v_j$。对所有基变量满足 $u_i + v_j = c_{ij}$。令 $u_1=0$ 即可解出所有位势，进而空格的检验数为 $\sigma_{ij} = c_{ij} - (u_i + v_j)$。
• 解的调整： 若存在非基变量的检验数不满足最优性（求最小化运费问题时出现负检验数），则选取最负的检验数格作为调入变量，沿闭合回路进行运量调整（调整量为回路中负号格的最小运量值）。

---

第五章：指派问题（Assignment Problem）#

1. 模型基础#

• 运输问题的进一步特例，要求 $n$ 个人分派做 $n$ 项工作。决策变量 $x_{ij}$ 只能取 $0$ 或 $1$。

2. 匈牙利算法（Hungarian Method）（★ 计算题重点）#

• 求解步骤：
  1. 行规约：每行减去该行最小元素。
  2. 列规约：每列减去该列最小元素（确保每行每列都有“0”元素）。
  3. 最少盖零线：用最少数量的水平线或垂直线覆盖矩阵中所有的“0”。
     • 若盖零线数量等于矩阵阶数 $n$，则可以直接确定最优方案（0元素所在位置即为指派方案）。
     • 若盖零线数量小于 $n$，则需对矩阵进行调整。
  4. 矩阵调整：在未被覆盖的元素中找出最小值。未被覆盖的元素减去该值；双线交叉点处的元素加上该值；单线覆盖的元素保持不变。重复上述步骤，直到最少盖零线数等于 $n$。

---

第六章：目标规划（Goal Programming）#

1. 核心思想与解的性质#

• 满意解 vs 最优解：传统线性规划追求的是“最优解”；但在实际决策中，由于多个目标之间往往存在冲突，无法同时达到最优。因此，目标规划退而求其次，追求的是**“满意解”**。当约束发生冲突时，通过求得一个各方都能接受、偏差最小的满意方案来辅助决策。

2. 偏差变量（Deviation Variables）（★ 客观题常考点）#

• 引入了正偏差变量 $d^+$（表示决策值超过目标值的数值）和负偏差变量 $d^-$（表示决策值未达到目标值的数值）。
• 核心性质：
  1. $d^+ \ge 0, d^- \ge 0$。
  2. 对于任意一个可行的决策方案，正负偏差变量中至少有一个为 $0$，即它们的乘积恒等于 $0$（$d^+ \cdot d^- = 0$）。

3. 目标函数与优先因子#

• 目标函数方向：目标规划的目标函数一定是求最小化（Minimize），其本质是使偏差量尽可能小。
• 优先因子（$P_1, P_2, P_3 \dots$）：当存在多个目标时，赋予它们不同的优先级，满足级设关系（$P_1 \gg P_2 \gg P_3$），即先满足高优先级，再在满足高优先级的条件下去争取满足低优先级。

4. 目标函数构造规则（★ 建模核心口诀）#

根据具体的管理要求，目标函数的建立有以下三类基本形式：

1. 恰好达到目标值（希望既不超过也不低于）：最小化正负偏差之和，即 $\min (d^+ + d^-)$。
2. 不超过目标值（允许未达到，但不允许超过）：最小化正偏差，即 $\min d^+$。
3. 不低于目标值（允许超过，但不允许未达到）：最小化负偏差，即 $\min d^-$。

---

第七章：整数规划（Integer Programming, IP）#

当线性规划模型中，变量（部分或全部）限制为整数时，称为整数规划。

1. 分枝定界法（Branch and Bound Method）（★ 必考大题）#

该方法可用于求解纯整数规划和混合整数规划。

• 基本思想：将全部可行解空间反复分割为越来越小的子集（分枝），并对每个子集内的解集计算一个目标边界（定界），以剪掉那些不可能包含最优解的子枝（剪枝），从而避免穷举。
• 核心操作（以 Max 问题为例）：
  • 下界（LB）：当前已知的任何一个整数可行解的目标函数值。
  • 上界（UB）：对子问题进行“松弛”（不考虑整数限制，当作普通 LP 求解）得到的最大目标函数值。
  • 分枝原则：选择松弛解中不满足整数限制的非整数变量 $x_j = [x_j] + f_j$（其中 $[x_j]$ 为整数部分，$f_j$ 为小数部分），构造两个子问题，分别加入约束： $x_j \le [x_j] \quad \text{与} \quad x_j \ge [x_j] + 1$
  • 剪枝条件：
    1. 子问题的松弛解已经是整数（无须再分，此时更新下界 LB）。
    2. 子问题无可行解。
    3. 子问题的上界（松弛最优解值）小于等于当前已知的下界（说明该分枝再往下找也无法超越已有的最好整数解）。

2. 割平面法（Gomory’s Cutting Plane Method）#

• 基本思想：首先不考虑整数约束，求出松弛问题的最优解。若最优解含有非整数，则从非整行中抽取出一条**“割平面约束”**（Cutting Plane）加入原问题。该约束能够切掉一部分非整数可行域，但绝不切掉任何一个整数可行解。
• 计算特点：引入割平面约束后，最终表的右端项会出现负数，且最优性检验数依然满足。因此，割平面法在后续迭代中必须配合使用对偶单纯形法进行求解。

---

第八章：图与网络优化：最大流问题（Maximum Flow Problem）#

1. 增广链（Augmenting Path）#

在已知可行流的网络中，从源点 $s$ 到汇点 $t$ 的一条无向链，如果满足以下条件，则称为增广链：

• 前向弧（与链方向一致的有向边）：未饱和，即其上的流量 $f_{ij} < c_{ij}$（容量限额）。
• 后向弧（与链方向相反的有向边）：有流量，即其上的流量 $f_{ji} > 0$。
• 调整量 $\theta$ 计算： $\theta = \min \left\{ \min_{\text{前向弧}}(c_{ij} - f_{ij}),\ \min_{\text{后向弧}}(f_{ji}) \right\}$ 调整时，前向弧上的流量加上 $\theta$，后向弧上的流量减去 $\theta$。

2. 最大流-最小割定理（Max-Flow Min-Cut Theorem）（★ 高频考点）#

• 割（Cut）：一个弧集合，若将其从网络中去掉，网络将不再连通，源点和汇点被划分到两个不相交的顶点子集 $S$ 和 $T$ 中。割中从 $S$ 指向 $T$ 的所有弧的容量之和称为割的容量。
• 定理内容：在一个有向网络中，从源点到汇点的最大流量等于将源点和汇点分开的最小割的容量。
• 考试应用：题目常要求在网络中找出一个“最小割”，或者通过寻找“最小割的容量”来直接验证求出的最大流是否正确。

---

第九章：动态规划（Dynamic Programming, DP）#

1. 最优化原理（Principle of Optimality）#

• 由贝尔曼（Bellman）提出：一个最优策略的子策略总是最优的。即：不论过去的状态和决策如何，对于前面的决策所形成的新状态而言，余下的决策必须构成最优策略。

2. 动态规划的五大基本要素（★ 概念题常设考点）#

1. 阶段（Stage, $k$）：多阶段决策过程中，将过程划分为若干个相互联系的阶段。
2. 状态（State, $s_k$）：每个阶段开始时过程所处的状况。状态必须具有无后效性（即当前阶段以后的状态仅由当前状态和当前决策决定，与过去的历史无关）。
3. 决策（Decision, $u_k$）：当过程处于某一阶段的某个状态时，可以做出的选择。
4. 状态转移方程（State Transition Equation）：描述相邻两个阶段之间状态的变化关系，其一般形式为： $s_{k+1} = v_k(s_k, u_k)$ 代表第 $k+1$ 阶段的状态由第 $k$ 阶段的状态和第 $k$ 阶段的决策共同决定。
5. 指标函数与逆推方程：动态规划一般采用逆推解法，其基本方程（Bellman 方程）形式为： $f_k(s_k) = \max / \min \{ r_k(s_k, u_k) + f_{k+1}(s_{k+1}) \}$