📚 Edexcel Decision Mathematics 2: Core Algorithms and Exam Techniques | Edexcel 决策数学2：核心算法与应试技巧
Decision Mathematics 2 extends the algorithmic toolbox introduced in D1, moving from simple sorting and critical paths to optimisation problems that arise in logistics, economics and operations research. This revision guide summarises the most examinable algorithms, common pitfalls and efficient checking strategies for the Edexcel AS and A level Further Mathematics specification.
决策数学2 在 D1 的基础上扩展了算法工具箱，从简单的排序和关键路径分析，转向物流、经济学和运筹学中的优化问题。本复习指南总结了 Edexcel AS 和 A level 高等数学大纲中最常考的算法、常见错误以及高效的检查策略。
1. Transportation Problems: Initial Feasible Solutions | 运输问题：初始可行解
The transportation problem aims to minimise the total cost of shipping goods from several supply points to several demand points, with each supply and demand constraint satisfied exactly. An initial feasible solution is often found by the north-west corner method or the least-cost method.
运输问题的目标是最小化从若干供应点向若干需求点运输货物的总成本，并且每个供应量和需求量约束都必须恰好满足。初始可行解通常用西北角法或最小成本法求得。
If a supply point has capacity 60 and the nearest demand point requires 45, the remaining 15 units must be allocated to the next demand point. The north-west corner method starts in the top-left cell and exhausts row or column capacity at each step; the least-cost method instead scans all unallocated cells and chooses the smallest unit cost among them.
如果某个供应点容量为 60，最近的需求点需要 45，那么剩余的 15 个单位必须分配给下一个需求点。西北角法从左上角的单元格开始，每步用完一行或一列的容量；而最小成本法则扫描所有未分配的单元格，选择其中单位成本最小的单元格。
Examiners often require you to show the allocation table clearly, with each used cell containing both the amount shipped and its unit cost. Check that total allocated supply equals total allocated demand; if the problem is unbalanced, add a dummy row or column with zero cost before constructing the initial solution.
考官通常要求你清楚地展示分配表，每个已用单元格中同时标出运输量和单位成本。检查总分配供应量是否等于总分配需求量；如果问题不平衡，需要在构造初始解之前添加一个成本为零的虚拟行或虚拟列。
| From / To | A | B | Supply |
|---|---|---|---|
| Warehouse 1 | 4 | 6 | 50 |
| Warehouse 2 | 7 | 3 | 40 |
| Demand | 55 | 35 | 90 |
In the table above, total supply equals total demand, so no dummy row or column is needed. A correct initial allocation should use exactly m + n − 1 occupied cells, where m is the number of rows and n is the number of columns.
在上表中，总供应量等于总需求量，因此不需要添加虚拟行或虚拟列。一个正确的初始分配应恰好使用 m + n − 1 个已占用单元格，其中 m 是行数，n 是列数。
2. Improving the Solution: Stepping-Stone Method | 改进解：闭回路法
Once an initial solution is obtained, its total cost can usually be reduced by shifting units along closed paths. The stepping-stone method evaluates each unused cell by forming a closed loop through existing basic cells and calculating the net cost change.
一旦得到初始解，通常可以通过沿闭回路转移货物来降低总成本。闭回路法通过经过现有基变量单元格形成闭合回路，并计算每个未用单元格的净成本变化来评估是否值得调整。
For an unused cell, trace a loop that moves alternately horizontally and vertically through occupied cells until returning to the start. Assign + and − signs alternately, beginning with + at the unused cell. The cell is worth entering the basis if the sum of signed unit costs, known as the improvement index, is negative.
对于某个未使用的单元格，沿水平或垂直方向交替经过已占用的单元格，画出一条闭合回路，直到回到起点。从该未用单元格开始，交替标上 + 号和 − 号。如果带符号的单位成本之和，即改进指数，为负，则该单元格值得进入基变量。
When you move units around the loop, choose the smallest quantity among the cells with a − sign. This quantity becomes the new allocation in the entering cell; the cell reaching zero leaves the basis. Degenerate cases require careful bookkeeping because a basic cell may carry zero units, and the loop must still be drawn through it.
当你在回路上转移货物时，应选择所有带 − 号单元格中最小的运输量。这个数量成为进入单元格的新分配量；变为零的单元格离开基变量。退化情况下需要仔细记录，因为某个基变量单元格可能运输量为零，而闭回路仍必须经过它。
The optimal solution is reached when every unused cell has a non-negative improvement index. Always recalculate the total cost after each iteration and compare it with the previous cost to confirm that the total has decreased or stayed the same.
当每个未使用的单元格都具有非负改进指数时，就达到了最优解。每次迭代后都要重新计算总成本，并与前一次成本比较，以确认总成本已经下降或保持不变。
3. The Hungarian Algorithm for Assignment Problems | 指派问题的匈牙利算法
The assignment problem is a special transportation problem where each supply point provides exactly one worker and each demand point requires exactly one task. The Hungarian algorithm minimises total cost by working on a square cost matrix, where rows represent workers and columns represent tasks.
指派问题是运输问题的一种特殊情况：每个供应点恰好提供一名工人，每个需求点恰好需要一项任务。匈牙利算法通过处理方阵形式的成本矩阵来最小化总成本，矩阵的行代表工人，列代表任务。
The algorithm has four main steps: subtract the smallest entry in each row from every entry in that row; subtract the smallest entry in each column; cover all zeros with a minimum number of lines; if the number of lines equals the matrix order, an optimal assignment is found, otherwise adjust the matrix and repeat the covering step.
该算法有四个主要步骤：从每一行的每个元素中减去该行的最小元素；从每一列中减去该列的最小元素；用最少数量的线覆盖所有零；如果线的数量等于矩阵的阶数，则找到了最优分配，否则调整矩阵并重复覆盖步骤。
To adjust the matrix when too few lines cover all zeros, find the smallest uncovered entry. Subtract it from every uncovered entry and add it to every entry covered by two lines. Entries covered by one line remain unchanged. This creates at least one new zero.
当覆盖所有零的线数量不足时，需要调整矩阵：找出未被覆盖的最小元素，从每个未被覆盖的元素中减去它，并把它加到两条线交叉处的元素上。被一条线覆盖的元素保持不变。这样至少会产生一个新的零。
If there are more rows than columns or vice versa, add dummy rows or columns with zero cost before applying the algorithm. Maximisation problems can be converted to minimisation by subtracting every entry from the largest entry, or by negating all costs and then adding a constant to remove negative entries if required.
如果行数多于列数或列数多于行数，需要在应用算法之前添加成本为零的虚拟行或虚拟列。最大化问题可以通过用最大元素减去每个元素，或对所有成本取负并在必要时加上常数以消除负值，从而转化为最小化问题。
4. Travelling Salesman Problem: Upper and Lower Bounds | 旅行商问题：上界与下界
The travelling salesman problem asks for the shortest tour that visits every vertex exactly once and returns to the starting vertex. Because the number of Hamiltonian cycles grows factorially, exact methods rely on obtaining good upper and lower bounds for the optimal tour length.
旅行商问题要求找出一条经过每个顶点恰好一次并回到起点的最短环游。由于哈密顿环的数量呈阶乘增长，精确方法依赖于为最优环游长度求出良好的上界和下界。
A quick upper bound can be found by the nearest neighbour algorithm: start at any vertex, repeatedly visit the nearest unvisited vertex, then return to the start. This tour may not be optimal, but its length gives an upper bound. A better upper bound can be obtained by using the nearest neighbour algorithm from several different starting vertices and taking the shortest tour.
可以用最近邻算法快速求出一个上界：从任一顶点出发，反复访问最近且未访问过的顶点，最后返回起点。这个环游未必最优，但其长度给出了一个上界。从多个不同起点运行最近邻算法并取最短环游，可以得到更好的上界。
A lower bound is found by deleting a vertex and finding a minimum spanning tree for the remaining vertices. The length of the minimum spanning tree plus the two shortest edges from the deleted vertex gives a lower bound. If this lower bound equals the length of a known tour, that tour is optimal.
下界的求法是：删除一个顶点，对剩余顶点求最小生成树。最小生成树的长度加上从被删除顶点连出的两条最短边，就得到一个下界。如果这个下界等于某个已知环游的长度，那么这个环游就是最优的。
The branch-and-bound method uses these bounds to systematically exclude subsets of tours. At each branch, compute a lower bound; if it exceeds the current best upper bound, that branch cannot contain the optimum and can be discarded without further exploration.
分支定界法利用这些界系统地排除环游子集。在每一步分支时计算下界；如果它超过当前最佳上界，则该分支不可能包含最优解，可以直接舍弃而不必继续搜索。
5. Dynamic Programming: Stage-and-State Approach | 动态规划：阶段与状态方法
Dynamic programming solves multi-stage decision problems by working backwards from the final stage. At each stage, the decision-maker chooses an action that minimises the immediate cost plus the optimal
Published by TutorHao | IB Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图