📚 Decision Mathematics 2: Key Concepts and Methods | 决策数学2：关键概念与方法精讲
Decision Mathematics 2 (D2) is a core module in A-Level Further Mathematics that extends the modelling and optimisation techniques introduced in Decision 1. It equips students with powerful tools for solving real-world problems involving resource allocation, network flow, strategic conflict, and project planning under constraints. This revision guide unpacks the essential topics, algorithms, and their practical applications, providing clear explanations and structured examples to support exam success.
决策数学2（D2）是A-Level进阶数学中的核心模块，它在决策1的基础上拓展了建模与优化的方法。学生将学习如何运用动态规划、博弈论、网络流分析、运输与指派问题，以及带资源约束的关键路径法等工具，解决复杂的现实决策问题。本精讲梳理了各单元的核心知识点与算法，配以清晰的步骤与示例，帮助学生高效备考。
1. Dynamic Programming | 动态规划
Dynamic programming (DP) is a method for solving multi-stage decision problems by breaking them down into simpler subproblems. It works backwards from the final stage, using Bellman’s principle of optimality: an optimal policy has the property that whatever the initial state and decision, the remaining decisions must be optimal with respect to the state resulting from the first decision. The recurrence relation typically takes the form fk(xk) = min or max { rk(xk, dk) + fk+1(xk+1) } over all feasible decisions dk.
动态规划（DP）是一种通过把多阶段决策问题分解为一系列子问题来求解的方法。它依据贝尔曼最优性原理，从最后一个阶段开始逆向递推：无论初始状态和决策如何，后续决策对于由第一个决策产生的状态而言必须是最优的。递推关系通常表示为：fk(xk) = 在所有可行决策 dk 上的最小或最大值 { rk(xk, dk) + fk+1(xk+1) }。
DP is used for shortest-path problems, knapsack-type resource allocation, and production planning. A typical exam question gives a network with stages and asks for the minimum cost from start to finish. Construct a table for each stage, recording the optimal value and decision.
动态规划适用于最短路径问题、背包类型的资源分配以及生产计划问题。典型的考题会给出一个带阶段的网络，要求计算从起点到终点的最小花费。解题时需为每个阶段建表，记录最优值与对应的决策。
Example: fk(i) = minj { cij + fk+1(j) }
2. Game Theory: Zero-Sum Games | 博弈论：零和博弈
A two-person zero-sum game models strategic interaction where one player’s gain is exactly the other’s loss. The payoff matrix represents the rewards for the row player. A saddle point exists if max(min of rows) = min(max of columns); the corresponding strategies are pure. When no saddle point exists, mixed strategies are needed, and the expected value is found by solving linear equations or using a graphical method for 2×n or m×2 games.
二人零和博弈模拟了一方所得即为另一方所失的对抗情境。收益矩阵表示行玩家的赢得。如果满足 行最小值中的最大值 = 列最大值中的最小值，则存在鞍点，此时双方使用纯策略。若无鞍点，则需采用混合策略，并通过解线性方程组或对 2×n、m×2 博弈使用图解法来求期望值。
For a 2×2 matrix without a saddle point, let row player’s strategy be (p, 1-p) and column player’s be (q, 1-q). Set the expected payoffs against each of the opponent’s actions equal to obtain optimal probabilities. The value of the game is the resulting expected payoff.
对于无鞍点的 2×2 矩阵，设行玩家的混合策略为 (p, 1-p)，列玩家为 (q, 1-q)。令行玩家分别对应列玩家的两种纯策略的期望收益相等，即可解出最优概率。游戏值即为该期望收益。
E(p,q) = a₁₁pq + a₁₂p(1-q) + a₂₁(1-p)q + a₂₂(1-p)(1-q)
3. Maximum Flow and Minimum Cut | 最大流与最小割
The maximum flow problem seeks the greatest rate at which a commodity can be sent from a source S to a sink T through a capacitated network. The Max-Flow Min-Cut theorem states that the value of maximum flow equals the capacity of the minimum cut separating S and T. The labelling procedure systematically finds flow-augmenting paths and updates residual capacities until no further increase is possible.
最大流问题旨在寻找能够从源点 S 经由带容量限制的网络发送到汇点 T 的最大流量。最大流最小割定理指出，最大流的值等于分离 S 和 T 的最小割的容量。标号法系统地寻找可增流路径并更新剩余容量，直到无法再增加流量为止。
The algorithm: start with zero flow. While there is an augmenting path from S to T using edges with spare capacity or existing flow that can be reduced, push as much flow as possible along it. Record the increase and adjust residual capacities. After termination, the saturated edges on the source side of a min cut confirm optimality.
算法步骤：初始流量为零。当存在一条从 S 到 T 的增广路径（利用具有闲置容量的边或已有反向流量的边）时，沿该路径尽可能多地推送流量。记录增量并调整剩余容量。算法终止后，最小割源点一侧的饱和边可验证最优性。
Flow value = Σ f(S,i) – Σ f(i,S) ≤ capacity of any cut
4. The Transportation Problem | 运输问题
The transportation problem involves minimizing the cost of distributing goods from several suppliers (with given stocks) to several consumers (with given demands). Total supply equals total demand in a balanced problem. The initial solution is found by methods like the North-West Corner rule or the Matrix Minimum method. The optimality test uses the MODI (Modified Distribution) method with shadow costs ui and vj to compute improvement indices for unoccupied cells.
运输问题要解决的是以最低成本将货物从多个供应点（给定库存）运送至多个需求点（给定需求量）的分配方案。在平衡问题中总供给等于总需求。初始解可通过西北角法或最小元素法求得。最优性检验采用改进分配法（MODI法），引入行位势 ui 和列位势 vj 计算空格的机会成本（即改进指数）。
If any unoccupied cell has a negative improvement index (for minimisation), the solution is not optimal. Step-stone paths are used to reallocate units in a closed loop, preserving supply and demand constraints until all improvement indices are ≥ 0. The transportation algorithm can also be applied to maximisation problems by converting profits to negative costs.
对于最小化问题，若某个空格的改进指数为负，则当前解非最优。需利用踏石法在闭回路中重新分配货物，同时保持供需约束，直到所有改进指数 ≥ 0。运输问题也可用于最大化利润的情形，只需将利润转换为负的成本值处理。
Improvement index Iij = cij – (ui + vj)
5. The Assignment Problem (Hungarian Algorithm) | 指派问题（匈牙利算法）
The assignment problem seeks the optimal one-to-one matching of n workers to n tasks to minimise total cost or maximise total profit. The Hungarian algorithm reduces the cost matrix by subtracting row minima, then column minima, and covers all zeros with a minimum number of lines. If the number of lines equals n, an optimal assignment is possible by selecting independent zeros. Otherwise, the smallest uncovered element is subtracted from uncovered entries and added to double-covered entries, and the process repeats.
指派问题旨在为 n 个工人与 n 项任务之间建立一对一的分配，以最小化总成本或最大化总利润。匈牙利算法通过先逐行减去该行最小值，再逐列减去该列最小值来化简成本矩阵，然后使用最少数量的线覆盖所有的零。若线数等于 n，则可从独立零元素处得到最优分配；否则，将未被覆盖的最小元素从所有未覆盖元素中减去，并加到双重覆盖的元素上，重复此过程。
For maximisation problems, either subtract all elements from a large constant or multiply by -1 and apply the standard minimisation routine. Unbalanced problems with n ≠ m are handled by adding dummy rows or columns with zero entries, allowing an equivalent square matrix.
对于最大化问题，可将所有元素从一个大数中减去，或乘以 -1 后应用标准的最小化流程。当问题不平衡，即 n ≠ m 时，通过添加全零的虚拟行或列扩展为方阵予以处理。
For cost matrix C: C’ = C – row min – column min
6. Critical Path Analysis and Resource Levelling | 关键路径分析与资源平衡
Critical Path Analysis (CPA) identifies the longest path through a project network, determining the minimum project duration and the critical activities that cannot be delayed without extending the overall completion time. While Decision 1 focused on forward/backward passes and float calculations, Decision 2 adds resource considerations: given a fixed number of workers or machines, the project schedule must be adjusted via resource levelling and resource smoothing to avoid exceeding resource availability, often using resource histograms and activity shifting.
关键路径分析（CPA）通过项目网络找出最长路径，确定项目的最短工期以及那些无法延迟否则将延长总工时的关键活动。决策1侧重于顺推/逆推计算和时差，而决策2引入了资源约束：在给定固定数量的工人或机器的条件下，需要通过资源平衡和资源平滑来调整项目日程，避免超出资源可用量，通常会借助资源直方图和活动的平移来实现。
The process involves constructing a cascade chart, drawing an initial resource histogram, and then using total float to move non-critical activities so that resource usage peaks are reduced. The goal is to create a feasible schedule that respects both precedence constraints and resource limits, without necessarily extending the project duration if possible.
该过程包括绘制阶梯图、初始资源直方图，然后利用非关键活动的总时差进行平移，以降低资源使用的高峰。目标是生成一个既满足工序先后约束又遵守资源限制的可行日程，并尽量不延长项目工期。
Total float = LFT – EST – duration; resource limit must be ≥ max daily requirement
7. Travelling Salesman Problem: Bounds and Heuristics | 旅行商问题：界与启发式算法
The Travelling Salesman Problem (TSP) requires finding the shortest Hamiltonian cycle visiting every vertex exactly once. It is computationally hard, so decision maths uses heuristic methods to find good upper bounds (e.g. nearest neighbour algorithm) and lower bounds (e.g. minimum spanning tree bound, or a vertex deletion bound). The gap between bounds gives confidence in the solution quality.
旅行商问题（TSP）要求找到遍历每个顶点恰好一次的最短哈密顿圈。由于计算复杂度高，决策数学采用启发式方法求出一个较好的上界（如最近邻算法）和下界（如最小生成树下界，或删点法下界）。上下界之间的差距可用来评估解的质量。
The lower bound often computed is: start with a chosen vertex, delete it, find a minimum spanning tree (MST) on the remaining vertices, then add the two shortest edges from the deleted vertex to the tree. For a symmetric TSP, this gives a valid lower bound. The nearest neighbour algorithm constructs a tour by always moving to the closest unvisited vertex and finally returning to the start.
常用的下界计算方法是：选一个顶点，将其删除，在剩余顶点上求最小生成树（MST），然后加上从被删顶点出发的两条最短边。对于对称TSP，这是一个有效的下界。最近邻算法则通过总是前往最近的未访问顶点、最后返回起点来构造巡回路径，作为上界。
Lower bound = MST weight + two smallest edges from deleted vertex
8. Further Algorithms for TSP | 旅行商问题进阶算法
Beyond the basic nearest neighbour heuristic, the 2-opt (pairwise exchange) technique improves an existing tour by repeatedly replacing two edges with two others to form a shorter cycle, removing self-crossings. This can transform a good upper bound into an even better one. A practical approach combines nearest neighbour to generate an initial tour, then applies 2-opt exchanges until no further improvement is found.
除了基本的最邻近启发式，2-opt（成对交换）技术通过反复用两条新边替换原巡回中的两条边以形成更短的圈，从而消除自交叉。这可以将一个较好的上界进一步优化。实际操作中常结合最近邻生成初始路径，再应用 2-opt 交换直至无法改进。
Lower bounds can be strengthened by considering a different deletion vertex or using the ‘short cut’ bound based on a minimal 1-tree. The exam may ask to find both bounds and prove the optimal tour lies within a given range, or to explain why a certain tour is optimal if its length matches the lower bound.
可以通过考虑不同的删点或基于最小1-树来增强下界。考试中常要求学生求取上下界，指出最优巡回长度所在的范围，或者解释为何当某条路径的长度恰好等于下界时，它就是最优解。
2-opt move: replace edges (a,b) and (c,d) with (a,c) and (b,d) if it shortens the tour
9. Recurrence Relations in Decision Making | 决策中的递推关系
Recurrence relations appear in dynamic programming and in modelling financial or operational scenarios. For example, a project’s cost or profit may depend on the number of units produced previously, leading to equations of the form un+1 = a un + b. Solving a recurrence may require finding a particular solution and a complementary function, or using iterative methods to compute terms.
递推关系出现在动态规划以及金融或运营建模中。例如，项目成本或利润可能依赖于前期的产量，从而导出形如 un+1 = a un + b 的方程。求解递推关系可能需要找出特解与余函数，或使用迭代法计算各期值。
In D2, recurrence relations often underpin DP tabulation, but they can also be standalone topics like ‘reduction of a problem to a recurrence’ or ‘determine the long-term behaviour’. Understanding how to construct and solve first-order and second-order linear recurrences is essential. Stability analysis checks whether the sequence converges to a fixed point as n → ∞.
在D2中，递推关系常作为DP表格化的基础，但也可能作为独立考点，例如“将问题归结为递推关系”或“确定长期行为”。掌握一阶与二阶线性递推的构建与求解至关重要。稳定性分析则考察序列当 n → ∞ 时是否收敛到一个不动点。
Fixed point L satisfies L = aL + b → L = b/(1-a), provided |a| < 1
10. Matching and Allocation Problems | 匹配与分配问题
Matching problems involve pairing members of two disjoint sets under certain constraints, often modelled on bipartite graphs. A maximal matching cannot be extended, but a maximum matching has the largest possible cardinality. The Hungarian algorithm is used for weighted assignments, while unweighted maximum matching can be found via the alternating path algorithm, starting from an initial matching and augmenting along alternating paths.
匹配问题涉及在两个不相交集合的元素之间按照一定约束进行配对，通常用二分图建模。极大匹配不能再添加边，而最大匹配具有最多的匹配边数。加权指派使用匈牙利算法，而未加权最大匹配则可通过从初始匹配出发，沿交替路径进行增广的算法求得。
In D2, the allocation variant often combines matching with optimal assignment, such as matching tasks to machines where each machine can handle only one task, and the cost or time depends on the specific assignment. The techniques learned for the assignment problem are directly applicable, and exam questions may frame the problem through a table or a network.
在D2中，分配类问题常将匹配与最优指派结合，例如将任务分配给机器，每台机器只能处理一个任务，且成本或时间取决于具体分配。学习过的指派问题方法可直接应用，考题可能通过表格或网络图来呈现问题。
Maximum matching size = ν(G); for bipartite graphs, Kőnig’s theorem relates to vertex cover
Published by TutorHao | Maths Decision Mathematics 2 Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导