📚 Edexcel Decision Mathematics 2: Complete Core Revision | Edexcel 决策数学2：核心考点全复习
Decision Mathematics 2 extends the graphical and algorithmic ideas from D1 into more advanced optimisation problems. The main topics are transportation, allocation, game theory, dynamic programming, network flows and the simplex method. This guide summarises the key algorithms, formulas and common exam errors for the Edexcel D2 paper.
决策数学2 将 D1 中的图论与算法思想拓展到更高级的优化问题。主要内容包括运输问题、分配问题、博弈论、动态规划、网络流与单纯形法。本指南总结了 Edexcel D2 考试中的关键算法、公式与常见错误。
1. Transportation Problems: Finding an Initial Solution | 运输问题：求初始解
to minimise the total cost of moving goods from m supply points to n demand points. Let xᵢⱼ be the number of units sent from supply i to demand j, with unit cost cᵢⱼ, supply sᵢ and demand dⱼ. The problem is balanced when Σsᵢ = Σdⱼ, so total supply equals total demand.
运输问题旨在最小化从 m 个供应点向 n 个需求点运送货物的总成本。设 xᵢⱼ 为从供应点 i 运往需求点 j 的货物数量，单位成本为 cᵢⱼ，供应量为 sᵢ，需求量为 dⱼ。当 Σsᵢ = Σdⱼ 时问题平衡，即总供应等于总需求。
Three standard methods produce an initial feasible solution: the north-west corner method, the least-cost method and Vogel's approximation method. The north-west corner method starts in the top-left cell and allocates as much as possible. The least-cost method selects the cheapest available route first. Vogel's method uses row and column penalty costs and usually gives a solution closer to optimal.
三种标准方法可产生初始可行解：西北角法、最小成本法与 Vogel 近似法。西北角法从左上角单元格开始尽量分配；最小成本法优先选择最便宜的可用路线；Vogel 法利用行与列的惩罚成本，通常给出的解更接近最优。
| Route | D1 | D2 | Supply |
|---|---|---|---|
| S1 | 4 | 6 | 30 |
| S2 | 5 | 3 | 40 |
| Demand | 25 | 45 | 70 |
Always check that the number of occupied cells equals m + n − 1. If it is smaller, the solution is degenerate and must be adjusted before optimality checks.
始终检查已占用单元格数是否等于 m + n − 1。如果小于该值，解是退化的，必须在进行最优性检验前进行调整。
2. Optimality Testing: MODI and Stepping-Stone | 最优性检验：MODI 与踏脚石法
After an initial solution is found, the modified distribution method, or MODI, tests whether it is optimal. For each basic cell, define shadow costs uᵢ and vⱼ so that:
找到初始解后，修正分配法（MODI）可检验其是否最优。对每个基变量单元格，定义影子成本 uᵢ 与 vⱼ，使：
uᵢ + vⱼ = cᵢⱼ
r the remaining shadow costs. Then compute the improvement index for every non-basic cell:
令 u₁ = 0，解出其余的影子成本。然后对每个非基变量单元格计算改进指数：
Iᵢⱼ = cᵢⱼ − (uᵢ + vⱼ)
If all Iᵢⱼ ≥ 0, the current solution is optimal. If some Iᵢⱼ is negative, the cost can be reduced by introducing that cell into the solution.
若所有 Iᵢⱼ ≥ 0，则当前解是最优解。若某个 Iᵢⱼ 为负，则将该单元格引入解中可降低成本。
The stepping-stone method finds the closed loop of occupied cells that must be adjusted. Add θ to the entering cell, then alternately subtract and add θ around the loop. Choose θ as the smallest value in a cell where θ is subtracted, keeping all allocations non-negative.
踏脚石法寻找必须调整的已占用单元格闭环。在入基单元格加 θ，然后沿闭环交替减 θ 和加 θ。选择在被减 θ 的单元格中的最小值作为 θ，保证所有分配非负。
3. Degeneracy and Unbalanced Transportation Problems | 退化与非平衡运输问题
A transportation solution is degenerate if the number of occupied cells is less than m + n − 1. In that case shadow costs cannot be found directly. To fix this, place a small artificial allocation ε in an independent empty cell, treat it as occupied, and continue the MODI method.
若已占用单元格数小于 m + n − 1，运输问题的解是退化的。此时无法直接求影子成本。解决方法是在一个独立的空单元格中放入人工分配 ε，将其视为已占用，再继续 MODI 方法。
If total supply does not equal total demand, the problem is unbalanced. Add a dummy demand point with zero cost if supply exceeds demand, or a dummy supply point if demand exceeds supply. The dummy row or column absorbs the difference and makes the tableau balanced.
如果总供应不等于总需求，问题是非平衡的。若供应大于需求，添加一个成本为零的虚拟需求点；若需求大于供应，添加虚拟供应点。虚拟行或列吸收差额，使表格平衡。
In exam answers, state clearly where the ε has been placed and remove it from the final allocation if it remains artificial. Do not forget that dummy routes have zero cost, but they still count toward the occupied cell total.
在考试答案中，应清楚说明 ε 放置的位置，并在最终分配中若仍为人工变量则将其去掉。不要忘记虚拟路线成本为零，但仍计入已占用单元格总数。
4. Assignment Problems: The Hungarian Algorithm | 分配问题：匈牙利算法
The assignment problem allocates n tasks to n workers so that the total cost is minimised, with each worker doing exactly one task. The Hungarian algorithm solves this efficiently.
分配问题将 n 项任务分配给 n 名工人，使总成本最小，且每名工人恰好完成一项任务。匈牙利算法可高效求解。
- Subtract the smallest entry in each row from every entry in that row.
- Subtract the smallest entry in each column from every entry in that column.
- Cover all zeros with the minimum number of horizontal and vertical lines.
- If the number of lines equals n, an optimal assignment is possible.
- If fewer than n lines are needed, subtract the smallest uncovered value from all uncovered entries, and add it to entries covered twice. Repeat until n lines are needed.
- 每行减去该行最小值。
- 每列减去该列最小值。
- 用最少的水平线和垂直线覆盖所有零。
- 若线数等于 n，则可进行最优分配。
- 若线数少于 n，从所有未覆盖元素中减去最小未覆盖值，并将其加到被覆盖两次的元素上。重复直到需要 n 条线。
Select independent zeros, one in each row and column, to identify the optimal assignment. If several choices exist, any set of independent zeros gives the same minimum total cost.
选择独立零，即每行每列各有一个零，以确定最优分配。如果存在多种选择，任何一组独立零都给出相同的最小总成本。
5. Maximisation and Unbalanced Assignment | 最大化与非平衡分配问题
If the assignment problem asks for maximum profit or maximum effectiveness, convert it to a minimisation problem. Replace each entry cᵢⱼ by:
如果分配问题要求最大化利润或最大化效率，应将其转化为最小化问题。将每个元素 cᵢⱼ 替换为：
new cost = C − cᵢⱼ, where C is the largest entry in the matrix
Then apply the standard Hungarian algorithm. The optimal assignment for the transformed matrix is also optimal for the original maximisation problem.
然后应用标准匈牙利算法。转换后矩阵的最优分配也是原最大化问题的最优分配。
If the matrix is unbalanced, add dummy rows or columns with zero entries so that the number of rows equals the number of columns. Dummy assignments are ignored in the final interpretation. Some problems also forbid certain assignments; replace those entries with a very large cost M for minimisation or a very small value for maximisation.
若矩阵不平衡，添加零元素的虚拟行或列，使行数等于列数。虚拟分配在最终解释中忽略。有些问题还会禁止某些分配；此时对于最小化问题将这些元素替换为非常大的成本 M，最大化问题则替换为非常小的值。
6. Game Theory: Play-Safe Strategies and Stable Solutions | 博弈论：稳妥策略与稳定解
A two-person zero-sum game is represented by a pay-off matrix for player A. Positive entries are gains for A and losses for B. Player A wants to maximise the minimum row value, while player B wants to minimise the maximum column value.
双人零和博弈可用局中人 A 的支付矩阵表示。正项表示 A 的收益、B 的损失。局中人 A 希望最大化最小行值，局中人 B 希望最小化最大列值。
The play-safe strategy for A is the row with the largest row minimum. The play-safe strategy for B is the column with the smallest column maximum. If:
A 的稳妥策略是行最小值最大的行。B 的稳妥策略是列最大值最小的列。如果：
max(row minima) = min(column maxima) = v
then the game has a stable solution or saddle point. The value v is called the value of the game, and the corresponding row and column are optimal pure strategies.
则该博弈有稳定解或鞍点。值 v 称为博弈的值，对应的行与列就是最优纯策略。
When there is no saddle point, the row and column maximin/minimax values are different. Players must then use mixed strategies, choosing actions with certain probabilities to optimise their expected pay-off.
当没有鞍点时，行与列的最大最小值/最小最大值不同。局中人此时必须使用混合策略，以一定概率选择行动以优化期望支付。
7. Mixed Strategies and the Graphical Method | 混合策略与图解法
oint, the graphical method can find optimal mixed strategies. Suppose A has two strategies with probabilities p and 1 − p. Against each of B's columns, the expected pay-off is a straight line in p.
对于没有鞍点的 2 × n 或 n × 2 博弈，图解法可求最优混合策略。设 A 有两个策略，概率分别为 p 和 1 − p。对于 B 的每一列，期望支付都是关于 p 的直线。
Player A should choose p to maximise the minimum expected pay-off. Draw all lines and identify the lower envelope. The highest point on the lower envelope gives A's optimal p and the game value for A. A similar approach works for player B by minimising the maximum expected loss.
局中人 A 应选择 p 使最小期望支付最大化。画出所有直线并确定下包络线。下包络线上最高点给出 A 的最优 p 和 A 的博弈值。对局中人 B 可用类似方法，最小化最大期望损失。
If the game is 2 × 2, you can also solve directly by equating A's expected pay-offs against B's two columns, and B's expected losses against A's two rows. Always check that the resulting probabilities lie between 0 and 1.
若博弈为 2 × 2，也可直接令 A 对 B 两列的期望支付相等，以及令 B 对 A 两行的期望损失相等来求解。始终检查所得概率是否在 0 与 1 之间。
8. Dynamic Programming: The Principle of Optimality | 动态规划：最优性原理
Dynamic programming solves multi-stage decision problems by working backwards from the final stage. Bellman's principle of optimality states that whatever the initial decision, the remaining decisions must form an optimal policy from the resulting state.
动态规划通过从最终阶段倒推来求解多阶段决策问题。贝尔曼最优性原理指出：无论初始决策如何，余下决策必须从该决策产生的状态出发构成最优策略。
A dynamic programming problem is defined by stages, states, actions and returns. The recursive relation compares the immediate return plus the optimal future return from the next state:
动态规划问题由阶段、状态、行动和收益定义。递推关系比较即时收益加上下一状态的最优未来收益：
Fₖ(s) = max or min [r(s, a) + Fₖ₊₁(s′)]
Build tables stage by stage, starting from the last stage where Fₙ is known. Then read the optimal route or allocation forward from the initial state.
从最后阶段开始逐阶段建表，其中 Fₙ 已知。然后从初始状态正向读出最优路线或分配。
Common D2 applications include shortest or longest path problems, allocating limited resources among projects, and simple knapsack-type problems. Always define notation and state clearly what each stage value represents.
D2 中常见应用包括最短或最长路径问题、在多个项目间分配有限资源，以及简单的背包类问题。始终定义符号，并清楚说明每个阶段值代表什么。
9. Network Flows: Cuts and Max-Flow Min-Cut | 网络流：割与最大流最小割
A flow network has directed arcs with capacities. Flow must satisfy capacity constraints and conservation at every vertex except the source S and sink T. The value of a flow is the total leaving the source or entering the sink.
流网络具有带容量的有向弧。流量必须满足容量约束，并在除源点 S 和汇点 T 外的每个顶点满足守恒。流的值等于离开源点或进入汇点的总流量。
A cut partitions the vertices into two sets, one containing S and the other containing T. The capacity of a cut is the sum of capacities of arcs crossing from the S side to the T side. The max-flow min-cut theorem states:
割将顶点划分为两个集合，一个包含 S，另一个包含 T。割的容量是从 S 侧穿过到 T 侧的弧的容量之和。最大流最小割定理指出：
maximum flow value = minimum cut capacity
The labelling procedure finds augmenting paths from S to T. For each forward arc with spare capacity, label the next vertex. For each backward arc with positive flow, label if flow can be reduced. Increase flow along the augmenting path by the minimum spare capacity on that path.
标号法寻找从 S 到 T 的增广路径。对每个有剩余容量的前向弧，给下一顶点标号。对每个有正流量的后向弧，若能减少流量也可标号。沿增广路径增加流量，增加量为该路径上最小剩余容量。
Repeat until no augmenting path exists. The flow is then maximum. To prove optimality, find a cut whose capacity equals the flow value.
重复直到不存在增广路径，此时流量最大。为证明最优性，找一个容量等于流量值的割。
10. Exam Tips and Common Pitfalls | 考试技巧与常见误区
Always show each step of an algorithm clearly. In transportation and assignment problems, state the initial solution method, the shadow costs, the improvement indices and the final allocation. Examiners award marks for process as well as final answers.
始终清楚展示算法的每一步。在运输与分配问题中，说明初始解方法、影子成本、改进指数与最终分配。考官不仅给最终答案分，也给过程分。
- Check balance before starting a transportation problem; add dummy rows or columns if needed.
- Remember m + n − 1 for occupied cells and use ε for degeneracy.
- In the Hungarian algorithm, cover zeros with the minimum number of lines; do not guess.
- For game theory, look for a saddle point before calculating mixed strategies.
- In network flows, write both forward and backward labels so augmenting paths are clear.
- 开始运输问题前检查是否平衡；需要时添加虚拟行或列。
- 记住已占用单元格数为 m + n − 1，退化时使用 ε。
- 匈牙利算法中，用最少线覆盖零；不要猜测。
- 博弈论中，先找鞍点再计算混合策略。
- 网络流中，写出前向与后向标号，使增广路径清晰。
Interpret your final answer in the context of the question. A minimum cost, an optimal assignment, a game value or a maximum flow should be written with correct units and a short concluding sentence.
在题目情境中解释最终答案。最小成本、最优分配、博弈值或最大流应写出正确单位，并附上简短的结论句。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图