Decision Mathematics 1 Complete Guide — Edexcel A-Level 数学决策数学 1 完全指南

Decision Mathematics 1: A Complete Guide to the Edexcel Module | 决策数学 1：Edexcel 模块完整指南

决策数学（Decision Mathematics）是 A-Level 数学课程中最贴近现实世界的一支。它研究的不是抽象的公式，而是实实在在的算法与优化问题：如何用最少的路线修路、如何安排工程进度、如何在有限资源下取得最大收益。Edexcel 的 Decision Mathematics 1（简称 D1）模块把这些内容系统化，帮助学生在计算机科学、运筹学、物流与工程管理等领域打下坚实基础。

Decision Mathematics is the branch of A-Level Mathematics that is closest to the real world. Instead of abstract formulas, it studies concrete algorithms and optimisation problems: how to build roads with minimum cost, how to schedule an engineering project, and how to obtain maximum profit from limited resources. The Edexcel Decision Mathematics 1 module, usually shortened to D1, organises these ideas systematically and gives students a solid foundation for computer science, operational research, logistics and engineering management.

本文按照 Edexcel D1 教学大纲的六大核心板块展开：算法、图论、最小生成树、最短路、关键路径分析与线性规划，并补充二分图匹配与考试技巧。每一节都配有可直接用于考试的追踪方法与例题思路，中英对照，方便不同学习习惯的学生使用。

This article follows the six core blocks of the Edexcel D1 syllabus: algorithms, graph theory, minimum spanning trees, shortest paths, critical path analysis and linear programming, with additional sections on bipartite graph matching and exam technique. Every section includes tracing methods and example strategies that can be applied directly in the exam, presented in both Chinese and English so that students with different study habits can all benefit.

1. Module Overview: Where D1 Sits in the A-Level Mathematics Course | 模块全景：D1 在 A-Level 数学课程中的位置

在 2017 年改革之前，Edexcel A-Level 数学采用模块化结构，学生从纯数学（C1 到 C4）与应用数学模块中选考。D1 与 M1（力学）、S1（统计）并列，是常见的 AS 阶段应用模块之一。改革之后，新的 A-Level 数学不再单设 D1 考试，决策数学内容并入进阶数学（Further Mathematics）的 Decision Mathematics 1 与 Decision Mathematics 2 单元。因此，无论你学习的是旧大纲还是新大纲，D1 的核心内容都是一样的。

Before the 2017 reform, Edexcel A-Level Mathematics used a modular structure in which students chose from pure mathematics units (C1 to C4) and applied units. D1 stood alongside M1 (Mechanics) and S1 (Statistics) as one of the common applied units taken at AS level. After the reform, the new A-Level Mathematics no longer has a separate D1 paper; the decision mathematics content moved into the Further Mathematics qualification as the Decision Mathematics 1 and Decision Mathematics 2 units. Either way, whether you are studying the old or the new syllabus, the core content of D1 is the same.

旧大纲的 D1 考试通常为 1.5 小时，满分 75 分，约占 A-Level 数学总成绩的 12.5%。考试允许使用科学计算器，但不允许使用图形计算器。试卷由简答题与较长的应用题组成，后者通常要求考生完成一个完整的算法追踪，并解释结果的现实含义。

Under the old specification, the D1 exam lasted 1.5 hours and was worth 75 marks, roughly 12.5 percent of the total A-Level Mathematics grade. A scientific calculator was allowed but graphical calculators were not. The paper consisted of short questions and longer applied questions, the latter usually requiring a complete algorithm trace plus an interpretation of the result in the context of the problem.

D1 的六个核心板块环环相扣：算法是工具，图论是语言，最小生成树与最短路解决网络优化，关键路径分析解决项目管理，线性规划解决资源分配，二分图匹配解决任务指派。理解板块之间的关联，比孤立记忆每个方法要有效得多。

The six core blocks of D1 are closely linked: algorithms are the tools, graph theory is the language, minimum spanning trees and shortest paths solve network optimisation, critical path analysis handles project management, linear programming handles resource allocation, and bipartite matching handles task assignment. Understanding the connections between blocks is far more effective than memorising each method in isolation.

2. Algorithm Basics: Pseudocode and Flowcharts | 算法基础：伪代码与流程图

算法是一组明确的、有序的步骤，用于解决某一类问题。D1 中算法的三个特征是：有限性（必须在有限步内结束）、确定性（每一步都有唯一解释）和有效性（每一步都能实际执行）。考试中常要求考生判断一段文字或一串指令是否构成算法，判据就是这三条。

An algorithm is a precise, ordered set of steps for solving a class of problems. Three features of algorithms matter in D1: finiteness (the process must stop after a finite number of steps), determinism (every step has exactly one interpretation) and effectiveness (every step can actually be carried out). In the exam you may be asked to judge whether a piece of text or a list of instructions is an algorithm; the three criteria above are the basis for your answer.

伪代码是算法的人性化表达，介于自然语言与编程语言之间。Edexcel 官方教材使用一套固定的伪代码约定：输入用 INPUT，输出用 PRINT，赋值用左箭头或等号，条件分支用 IF…THEN…ELSE，循环用 FOR…TO…NEXT 与 REPEAT…UNTIL。看懂这些关键字，是完成算法追踪题的前提。

Pseudocode is a human-friendly way of expressing an algorithm, sitting between natural language and a programming language. The official Edexcel textbooks use a fixed set of pseudocode conventions: INPUT for input, PRINT for output, a left arrow or equals sign for assignment, IF…THEN…ELSE for conditional branching, and FOR…TO…NEXT together with REPEAT…UNTIL for loops. Understanding these keywords is the prerequisite for completing algorithm tracing questions.

流程图用图形符号表达同样逻辑：椭圆表示开始与结束，矩形表示处理或赋值，菱形表示判断分支，箭头表示流程方向。考试中偶尔会要求补全流程图中的空缺框，判断依据是：每个菱形必须有两个出口，每个处理框只有一个出口。

A flowchart expresses the same logic with graphical symbols: ovals mark the start and the end, rectangles mark processing or assignment, diamonds mark decisions, and arrows mark the direction of flow. Occasionally the exam asks you to fill in a missing box in a flowchart; the rules to remember are that every diamond needs two exits and every processing box has one exit.

追踪（tracing）是 D1 最重要的考试技能：给定一组输入，用表格记录每一轮循环后每个变量的值，最后读出输出。追踪时务必逐行执行，变量更新后立刻改写表中数值，绝不能心算跳步，因为评分按步骤给分，跳步会直接丢分。

Tracing is the single most important exam skill in D1: given a set of inputs, you use a table to record the value of every variable after each pass through a loop, then read off the output at the end. When tracing, execute line by line and update the table immediately after each variable changes. Never skip steps by mental arithmetic, because marks are awarded per step and skipping steps loses marks directly.

3. Sorting and Searching: Bubble Sort, Quick Sort and Binary Search | 排序与查找：冒泡排序、快速排序与二分查找

冒泡排序是 D1 要求掌握的第一种排序算法。它的思路是反复比较相邻两项，如果顺序错误就交换，每一轮结束时最大的未排序项会”冒泡”到正确位置。对于 n 个数，最多需要 n-1 轮。考试中常见的做法是写一个 pass 的表格，把每一轮比较和交换都记录下来。

Bubble sort is the first sorting algorithm you must master in D1. The idea is to repeatedly compare adjacent pairs and swap them if they are in the wrong order; at the end of each pass the largest unsorted item “bubbles” up to its correct position. For n numbers, at most n-1 passes are needed. In the exam, the standard technique is to write out a table for each pass, recording every comparison and swap.

快速排序效率更高，是冒泡排序的递归版本。它的步骤是：选一个枢纽项（pivot），把所有比枢纽小的项按原顺序放在左边，比枢纽大的项按原顺序放在右边，枢纽居中；然后对左右两个子列表重复同样操作，直到每个子列表长度不超过 1。枢纽通常取当前列表的第一项。

Quick sort is more efficient and is the recursive version of sorting. The procedure is: choose a pivot, place all items smaller than the pivot to its left in their original order and all items larger than the pivot to its right in their original order, with the pivot in the middle; then repeat the same operation on the left and right sublists until every sublist has length at most 1. The pivot is usually taken as the first item of the current list.

二分查找（binary search）用于在有序列表中定位某一项。方法是：取列表中间位置的项与目标比较；如果相等则找到；如果目标更小，只在左半部分继续；如果目标更大，只在右半部分继续。每一轮把搜索范围缩小一半，因此 n 个元素的列表最多需要约 log2(n) 次比较。

Binary search is used to locate an item in an ordered list. The method is: compare the middle item of the list with the target; if they are equal the item is found; if the target is smaller, continue only in the left half; if the target is larger, continue only in the right half. Each round halves the search range, so a list of n elements needs at most about log2(n) comparisons.

区分三个算法的适用场景是高频考点：数据无序且规模小时用冒泡排序，数据无序且规模大时用快速排序，数据有序时用二分查找。考试还可能给出”最少比较次数”或”最多比较次数”的追问，回答时要说明排序轮次与查找轮次的计数方式。

Distinguishing the use of the three algorithms is a high-frequency exam question: use bubble sort for small unordered lists, quick sort for large unordered lists, and binary search when the list is already ordered. The exam may follow up by asking for the minimum or maximum number of comparisons; when answering, explain clearly how you count the passes in sorting versus the rounds in searching.

4. Graph Fundamentals: Vertices, Edges and Degrees | 图论基础：顶点、边与度数

图（graph）由顶点（vertex）与边（edge）组成，是 D1 描述网络的语言。简单图没有自环也没有重边；多重图允许两个顶点之间有多条边；有向图的每条边有方向；加权图的每条边带一个数值权重。D1 的图通常都是简单加权图或无向图。

A graph consists of vertices and edges, and it is the language D1 uses to describe networks. A simple graph has no loops and no multiple edges; a multigraph allows several edges between the same pair of vertices; a directed graph gives every edge a direction; a weighted graph attaches a numerical weight to every edge. The graphs in D1 are usually simple weighted graphs or undirected graphs.

顶点的度数（degree）是与该顶点相连的边的条数，有向图中还区分入度与出度。一个重要的定理是握手引理：所有顶点度数之和等于边数的两倍，因为每条边贡献了两个度数。由握手引理立刻可得推论：任何图中奇度顶点的个数一定是偶数。

The degree of a vertex is the number of edges incident to it; in a directed graph you also distinguish in-degree from out-degree. An important theorem is the handshaking lemma: the sum of all vertex degrees equals twice the number of edges, because every edge contributes two degrees. A direct corollary of the handshaking lemma is that the number of odd-degree vertices in any graph is always even.

欧拉定理把图的连通性与奇点联系起来：一个连通图存在一条经过每条边恰好一次的闭合回路（欧拉回路），当且仅当所有顶点度数都是偶数；如果恰好有两个奇点，则存在一条从其中一个奇点到另一个奇点的欧拉路径。这个定理直接支撑后面中国邮递员问题的解法。

Euler’s theorem links connectivity to odd vertices: a connected graph has a closed route that traverses every edge exactly once (an Euler circuit) if and only if every vertex has even degree; if there are exactly two odd vertices, there is an Euler path from one odd vertex to the other. This theorem directly supports the solution of the route inspection problem later.

判断图的性质时，建议先在草稿纸上重新画出给出的图，标注每条边的权重与每个顶点的度数。很多学生因为看不清原图而数错度数，导致后续算法全部出错。图形清晰是图论题的第一道保险。

When deciding the properties of a graph, redraw the given graph on your draft paper first and label every edge weight and every vertex degree. Many students miscount degrees because they cannot read the original diagram clearly, and every subsequent algorithm then goes wrong. A clear diagram is the first line of defence in graph questions.

5. Minimum Spanning Trees: Kruskal’s Algorithm | 最小生成树：Kruskal 算法

最小生成树（minimum spanning tree, MST）是连接图中所有顶点、且总权重最小的连通子图，它一定是一棵树：有 n 个顶点就有 n-1 条边，且不含回路。典型应用是设计成本最低的道路或电缆网络，把若干城市全部连通。

A minimum spanning tree (MST) is a connected subgraph that joins every vertex of the graph with minimum total weight; it is always a tree: with n vertices it has exactly n-1 edges and contains no cycles. A typical application is designing the cheapest road or cable network that connects all cities.

Kruskal 算法的步骤是：第一步，把所有边按权重从小到大排序；第二步，从最小权重的边开始依次检查，如果加入这条边不会形成回路就选择它，否则跳过；第三步，重复直到选够 n-1 条边。算法的核心判据是”不成环”，判断时可以看这条边的两个端点是否已经被已选边连通。

Kruskal’s algorithm works as follows: first, sort all edges by weight from smallest to largest; second, inspect the edges in that order and select each edge if adding it does not create a cycle, otherwise skip it; third, repeat until n-1 edges have been selected. The core criterion is “no cycle”, and you can check it by asking whether the two endpoints of the edge are already connected by the selected edges.

举例：考虑一个五个顶点的图，最小权重的边是 AB（权重 3），选择它；接着是 CD（权重 4），选择它；接着 AC（权重 5），A 与 C 尚未连通，选择它；接着 BD（权重 6），但 B 与 D 已经通过 A-C-D 连通，跳过；直到选出 4 条边为止。最终树的权重就是各边权重之和。

For example, consider a graph with five vertices. The smallest edge is AB with weight 3, so select it; next is CD with weight 4, select it; next is AC with weight 5, and since A and C are not yet connected, select it; next is BD with weight 6, but B and D are already connected through A-C-D, so skip it; continue until 4 edges are selected. The total weight of the tree is the sum of the selected edge weights.

Kruskal 的常见失分点有三个：忘记先排序；在图上画完边后没有逐条说明”选择或跳过”的理由；以及把”不成环”误判为”不成三角形”。记住：只要两个端点已被已选边连通，任何加入都会成环，与具体形状无关。

There are three common ways to lose marks with Kruskal’s algorithm: forgetting to sort the edges first; drawing the selected edges without explaining the “select or skip” reason for each one; and confusing “no cycle” with “no triangle”. Remember: if the two endpoints are already connected by selected edges, adding the edge always creates a cycle, regardless of the shape.

6. Prim’s Algorithm: Matrix and Table Methods | Prim 算法：矩阵法与表法

Prim 算法从任意一个顶点出发，逐步扩展生成树：每一步在”已选顶点集合”与”未选顶点集合”之间，选择权重最小的那条边，把新的顶点加入集合，直到所有顶点都被选入。与 Kruskal 全局选边不同，Prim 是局部扩张，任何顶点作为起点都能得到同一棵最小生成树。

Prim’s algorithm starts from any vertex and grows the spanning tree step by step: at each step it chooses the edge of minimum weight between the set of selected vertices and the set of unselected vertices, adds the new vertex to the set, and repeats until every vertex has been selected. Unlike Kruskal, which selects edges globally, Prim expands locally, and any starting vertex leads to the same minimum spanning tree.

D1 考试中 Prim 算法有两种考法。第一种是直接在图上操作：用铅笔标出已选顶点，每次在已选与未选之间找最小边。第二种是给出距离表（distance table）或邻接矩阵，要求用列表法完成追踪：维护一个”已选顶点”列表，每一轮从已选顶点行中找出指向未选顶点的最小项，记录新顶点与边权。

Prim’s algorithm appears in two forms in the D1 exam. The first is direct work on the graph: mark the selected vertices in pencil and each time find the smallest edge between selected and unselected vertices. The second gives a distance table or adjacency matrix and asks you to complete a table-based trace: maintain a list of selected vertices, and in each round find the smallest entry in the rows of selected vertices that points to an unselected vertex, then record the new vertex and the edge weight.

表法的典型书写格式是：第一列写轮次，第二列写新加入的顶点，第三列写加入的边及其权重，最后一列更新已选顶点列表。评卷时看重的是每一轮的”候选边比较”，所以即使最终树画对了，没有中间表格也会扣过程分。

The typical table format is: the first column records the round number, the second column the newly added vertex, the third column the edge and its weight, and the last column the updated list of selected vertices. The examiner rewards the comparison of candidate edges in each round, so even if your final tree is correct, missing the intermediate table loses method marks.

Kruskal 与 Prim 的对比题几乎每年都考：两者都产生最小生成树，Kruskal 适合边少（稀疏）的图，Prim 适合顶点少而边多（稠密）的图。另外注意，当图中有多条权重相同的边时，最小生成树可能不唯一，但总权重相同。

A comparison question between Kruskal and Prim appears almost every year: both produce a minimum spanning tree; Kruskal suits sparse graphs with few edges, while Prim suits dense graphs with many edges but few vertices. Also note that when several edges share the same weight, the minimum spanning tree may not be unique, but the total weight is the same.

7. Dijkstra’s Algorithm: Tracing the Shortest Path | Dijkstra 算法：最短路径追踪

Dijkstra 算法解决加权图中单源最短路径问题：从一个起点出发，找到到达每个其他顶点的最短路径及其长度。它的核心思想是贪心：每次把当前”临时距离”最小的顶点永久标号，然后用它去更新所有相邻顶点的临时距离。

Dijkstra’s algorithm solves the single-source shortest path problem in a weighted graph: starting from one vertex, it finds the shortest path and its length to every other vertex. The core idea is greedy: each time it permanently labels the vertex with the smallest current temporary distance, then uses that vertex to update the temporary distances of all its neighbours.

D1 考试使用盒式标号法（box labelling）：每个顶点旁画一个小盒子，盒子分成两部分，上面写”永久标号”（最终距离），下面写”临时标号”（当前最佳距离）。每一步：找出临时标号最小的未永久顶点，将其永久化；对该顶点的每个邻居，如果 起点到该顶点的永久距离 加上 该边权重 小于邻居当前的临时标号，就更新邻居的临时标号并记下前驱顶点。

The D1 exam uses box labelling: next to each vertex you draw a small box split into two parts, with the permanent label (final distance) on top and the temporary label (current best distance) below. At each step: find the unpermanently labelled vertex with the smallest temporary label and make it permanent; for each neighbour of that vertex, if the permanent distance to the current vertex plus the edge weight is smaller than the neighbour’s current temporary label, update the neighbour’s temporary label and record the predecessor vertex.

例如求 A 到 F 的最短路径：起点 A 标号 0 并永久化；A 的邻居 B、C 分别获得临时标号 4、7；B 的临时标号 4 最小，永久化 B；B 的邻居 C、D、E 更新为 min(7, 4+2=6) 得 6、min(inf, 4+3)=7、min(inf, 4+9)=13；然后永久化 C（6），再更新 D 为 min(7, 6+1=7) 保持 7、E 为 min(13, 6+6=12) 得 12……以此类推，直到 F 被永久化。

For example, to find the shortest path from A to F: label the start A with 0 and make it permanent; neighbours B and C receive temporary labels 4 and 7; B has the smallest temporary label 4, so make B permanent; update B’s neighbours: C becomes min(7, 4+2=6) which is 6, D becomes min(infinity, 4+3) which is 7, E becomes min(infinity, 4+9) which is 13; then make C permanent with 6, update D to min(7, 6+1=7) which stays 7 and E to min(13, 6+6=12) which is 12, and continue until F is made permanent.

追踪完成后，从终点沿”前驱”标记一路回溯到起点，反向写出顶点序列，就是最短路径。注意：Dijkstra 只适用于非负权重的图；如果图中存在负权重边，D1 大纲不要求处理，直接指出不适用即可。常见错误是忘记在每次永久化后更新邻居，或把临时标号当最终答案。

After the trace, follow the predecessor marks backwards from the destination to the start and reverse the vertex sequence to obtain the shortest path. Note that Dijkstra only applies to graphs with non-negative weights; if the graph contains negative edges, the D1 syllabus does not require you to handle it, so simply state that it does not apply. Common mistakes are forgetting to update neighbours after each permanent labelling and mistaking a temporary label for the final answer.

8. Route Inspection: The Chinese Postman Problem | 中国邮递员问题：路线检查

路线检查问题（route inspection）也叫中国邮递员问题：邮递员必须走遍某街区每一条街道至少一次，最后回到邮局，问最短路线长度是多少。如果图中所有顶点度数都是偶数，根据欧拉定理存在欧拉回路，答案就是所有边权之和；如果存在奇点，就必须重复走一些边。

The route inspection problem is also known as the Chinese postman problem: a postman must walk along every street in a district at least once and finally return to the post office; what is the minimum length of the route? If every vertex in the graph has even degree, an Euler circuit exists by Euler’s theorem and the answer is the sum of all edge weights; if there are odd vertices, some edges must be repeated.

解法分四步：第一步，找出图中所有奇度顶点（由握手引理知个数为偶数）；第二步，把奇点两两配对，计算每一对之间最短路径的长度；第三步，在所有配对方案中选择”重复总长度”最小的一种，被选中的路径上的边就是要重复走的边；第四步，最短路线长度等于所有边权之和加上重复边的长度。

The solution has four steps: first, find all odd-degree vertices in the graph (their number is even by the handshaking lemma); second, pair the odd vertices and compute the length of the shortest path within each pair; third, among all pairing schemes choose the one with the smallest total repeated length, and the edges on the chosen paths are the edges to be repeated; fourth, the minimum route length equals the sum of all edge weights plus the length of the repeated edges.

当图有 4 个奇点时，配对方案有 3 种，需要逐一计算。典型例子：奇点为 A、B、C、D，最短路径长度为 AB=4、CD=5、AC=6、BD=6、AD=7、BC=8，则三种配对方案的总重复长度为 4+5=9、6+6=12、7+8=15，最小为 9，对应重复 A-B 与 C-D 之间的路径。

When the graph has 4 odd vertices, there are 3 pairing schemes and each must be evaluated. A typical example: odd vertices A, B, C, D with shortest path lengths AB=4, CD=5, AC=6, BD=6, AD=7, BC=8; the three schemes give repeated totals of 4+5=9, 6+6=12 and 7+8=15; the minimum is 9, which means repeating the paths between A-B and C-D.

如果题目要求”从某点出发不要求回到原点”，那是路线检查的变体：只需让终点是另一个奇点，答案等于所有边权之和加上配对中除去起点到终点那一对的重复长度。看清题目是”回到起点”还是”不必回到起点”，这是本题最大的分水岭。

If the question asks for a route that starts at one point and does not need to return, that is a variant of route inspection: the finish point should be another odd vertex, and the answer equals the sum of all edge weights plus the repeated length of all pairs except the pair containing the start and finish. Reading carefully whether the question says “return to the start” or “not required to return” is the biggest fork in the road for this topic.

9. Critical Path Analysis: EST, LST and Float | 关键路径分析：最早时间、最迟时间与浮动

关键路径分析（critical path analysis, CPA）用于项目管理：一个工程由若干活动组成，活动之间有先后依赖关系，问整个工程最短需要多久完成、哪些活动耽误不得。D1 用活动网络（activity network）表示依赖关系，每个活动用一条有向边表示，顶点表示事件（时间点）。

Critical path analysis (CPA) is used in project management: a project consists of activities with dependencies between them, and the questions are how long the whole project takes at minimum and which activities cannot be delayed. D1 uses an activity network to represent dependencies: each activity is a directed edge and each vertex is an event, that is, a point in time.

最早开始时间（earliest start time, EST）通过前向扫描计算：从起点开始，起点的 EST 为 0；沿箭头方向推进，每个事件的最早时间是所有进入该事件的活动的最早完成时间中的最大值；最早完成时间等于 EST 加上活动时长。前向扫描的规则是”取最大”。

The earliest start time (EST) is computed by a forward scan: start from the source vertex with EST 0; moving in the direction of the arrows, the earliest time of each event is the maximum of the earliest completion times of all activities entering that event; the earliest completion time equals the EST plus the activity duration. The rule of the forward scan is “take the maximum”.

最迟开始时间（latest start time, LST）通过后向扫描计算：从终点开始，终点的最迟时间等于它的最早时间；逆着箭头方向推进，每个事件的最迟时间是所有从该事件出发的活动的最迟开始时间中的最小值。后向扫描的规则是”取最小”。

The latest start time (LST) is computed by a backward scan: start from the sink vertex whose latest time equals its earliest time; moving against the arrows, the latest time of each event is the minimum of the latest start times of all activities leaving that event. The rule of the backward scan is “take the minimum”.

总浮动（total float）等于 最迟开始时间减最早开始时间。浮动为 0 的活动叫关键活动，关键活动连成的路径就是关键路径，整条路径的长度就是项目最短工期。赶工（crashing）时，只有压缩关键路径上的活动才能缩短总工期，压缩非关键活动毫无作用。

Total float equals the latest start time minus the earliest start time. Activities with zero float are critical activities, the chain of critical activities is the critical path, and the length of that path is the minimum project duration. When crashing the project, only compressing activities on the critical path shortens the total duration; compressing non-critical activities has no effect.

CPA 的失分点集中在符号混乱：有的教材用 EST/LST，有的用 EET/LET，还有的用”最早开工/最迟完工”。考试时统一采用题目给定的符号，并在草稿上把前向扫描结果写在事件上方、后向扫描结果写在事件下方，一目了然，也方便检查浮动计算。

CPA loses marks mostly through symbol confusion: some textbooks use EST/LST, some use EET/LET, and some use “earliest start/latest finish”. In the exam, use the symbols given in the question, and on your draft write the forward scan results above each event and the backward scan results below each event. This keeps everything visible and makes float calculations easy to check.

10. Linear Programming: Formulating and Optimising | 线性规划：建模与最优化

线性规划（linear programming, LP）解决资源分配问题：在若干线性约束下，求目标函数的最大值或最小值。建模三步走：第一，定义决策变量（通常用 x、y 表示产量、数量）；第二，写出目标函数（如利润 P = 3x + 2y）；第三，把每条限制写成线性不等式，并注明 x、y 的非负约束。

Linear programming (LP) solves resource allocation problems: maximise or minimise an objective function subject to several linear constraints. The modelling process has three steps: first, define the decision variables (usually x and y for quantities); second, write the objective function (for example profit P = 3x + 2y); third, write every restriction as a linear inequality and state the non-negativity constraints on x and y.

求解的第一种方法是图解法：在坐标平面画出每条约束直线，用测试点确定可行区域（feasible region）在直线的哪一侧；所有半平面的交集就是可行域，最优解一定出现在可行域的顶点上。因此只需计算每个顶点的目标函数值，取最大或最小即可。

The first solving method is graphical: draw each constraint line on the coordinate plane and use a test point to decide which side of the line is feasible; the intersection of all half-planes is the feasible region, and the optimal solution always occurs at a vertex of the feasible region. Therefore you only need to evaluate the objective function at every vertex and take the largest or smallest value.

求解的第二种方法是等利润线法：画出目标函数的等值线 P = 3x + 2y，例如 3x + 2y = 6；把这条线平行移动，最后离开可行域的那个顶点就是最优解。当最优解要求整数（如人数、台数）时，先求连续最优解，再检查其邻近的整数格点，选择可行且目标值最优的整数点。

The second solving method is the iso-profit line: draw a level line of the objective function such as 3x + 2y = 6; slide this line parallel to itself, and the last vertex it touches before leaving the feasible region is the optimal solution. When the optimal solution must be integer valued (numbers of people or machines), find the continuous optimum first, then check the nearby integer lattice points and choose the feasible one with the best objective value.

线性规划的应用题要特别注意单位的统一与约束的完整：例如”至少生产 10 件”对应 x 大于等于 10，”最多使用 8 小时”对应 2x + 3y 小于等于 8。漏写一条约束会让可行域偏大，导致答案完全错误；因此读完题目后应逐句对照，把每个数量关系都变成不等式。

Applied LP questions require special attention to consistent units and complete constraints: for example “produce at least 10 items” gives x greater than or equal to 10, and “use at most 8 hours” gives 2x + 3y less than or equal to 8. Missing one constraint enlarges the feasible region and makes the answer completely wrong; so after reading the question, go sentence by sentence and convert every quantitative relationship into an inequality.

11. Bipartite Graphs and Matchings | 二分图与匹配

二分图（bipartite graph）的顶点分成两组，所有边都只连接不同组内的顶点。典型的 D1 应用是任务分配：左边一组是需要完成的任务，右边一组是工人或机器，边表示”该工人能胜任该任务”。问能否给每个任务安排一个不同的工人，就是一个匹配问题。

A bipartite graph has its vertices split into two groups, and every edge connects vertices from different groups. A typical D1 application is task assignment: the left group is tasks and the right group is workers or machines, with an edge meaning “this worker can do this task”. Asking whether every task can be assigned a different worker is a matching problem.

匹配（matching）是一组两两不共享顶点的边。完美匹配（complete matching）是指左侧每个顶点都恰好与右侧一个顶点匹配。判断匹配是否完美，可以尝试构造：从左侧任选一个顶点开始，选择一条边；若右侧顶点已被占用，就尝试”让位”给左侧的竞争顶点寻找替代边，这个过程叫交替路径（alternating path）搜索。

A matching is a set of edges with no shared vertices. A complete matching is one in which every vertex on the left is matched to exactly one vertex on the right. To test whether a perfect matching exists, try to construct one: start from any left vertex and choose an edge; if the right vertex is already taken, try to make the competing left vertex “step aside” by finding an alternative edge, a process called alternating path search.

匈牙利算法（Hungarian algorithm）是系统化的匹配方法：重复执行”找增广路径、翻转匹配”两步，直到找不到增广路径为止，此时匹配达到最大。D1 通常只要求理解概念并用图示方法找出最大匹配，不要求完整的匈牙利算法实现。

The Hungarian algorithm is the systematic method for matching: repeatedly perform the two steps of “find an augmenting path and flip the matching” until no augmenting path can be found, at which point the matching is maximal. D1 usually only requires you to understand the concept and find a maximum matching by a diagrammatic method, not to implement the full Hungarian algorithm.

考试中匹配题的答案要画出最终匹配的边，并说明为什么不能进一步扩大：通常是因为剩余未匹配的左侧顶点无法找到不与已匹配边冲突的边。把”尝试过程”简要写出来能获得方法分，直接给出结果而没有任何推理是危险的。

In the exam, the answer to a matching question must show the final matched edges and explain why the matching cannot be enlarged: usually because the remaining unmatched left vertex has no edge that does not conflict with existing matched edges. Writing out the attempt process briefly earns method marks; giving only the final result without any reasoning is risky.

12. Exam Technique: Common D1 Mistakes and How to Avoid Them | 考试技巧：D1 常见失分点与应对

D1 的题目本身不难，但得分率往往低于纯数学，原因几乎都是过程不规范。第一个高频失分点是算法追踪不写表格：评分标准明确要求以表格形式呈现每一轮的变量变化，心算结果不给分。对策是养成”每算一步，落笔一格”的习惯。

D1 questions are not difficult in themselves, but success rates are often lower than in pure mathematics, almost always because of poor presentation. The first high-frequency mark loser is tracing algorithms without a table: the mark scheme explicitly requires the changes of variables in each round to be shown in table form, and mental arithmetic results receive no marks. The remedy is to build the habit of writing one table cell for every step you compute.

第二个失分点是单位与措辞：路线检查题的答案要写”千米”并注明重复了哪些路段；线性规划题的最优解要回到原问题语境解释含义（如”生产 40 张桌子和 60 把椅子，最大利润 1800 元”）。只有数字没有解释，应用题的最后一问基本拿不到满分。

The second mark loser is units and wording: route inspection answers must state the unit (kilometres) and name the repeated sections; linear programming answers must interpret the optimal solution in the context of the original problem (for example “produce 40 tables and 60 chairs for a maximum profit of 1800 yuan”). Numbers without interpretation rarely earn full marks on the final applied part of a question.

第三个失分点是符号与方向错误：Dijkstra 追踪时把临时标号写在永久位置；CPA 前向扫描”取最大”与后向扫描”取最小”记反；Prim 表法漏更新已选集合。建议考前把每类算法的书写模板各做三遍，做到闭卷也能按标准格式输出。

The third mark loser is symbol and direction errors: writing temporary labels in the permanent position during Dijkstra tracing; confusing “take the maximum” in the forward scan with “take the minimum” in the backward scan of CPA; and forgetting to update the selected set in the Prim table method. Before the exam, practise each algorithm’s standard written format three times so that you can reproduce the correct layout even from memory.

时间管理上，建议按”先易后难”作答：二分查找、简单追踪等小题先拿分，关键路径与线性规划的作图题放在中间，把最后 15 分钟留给检查。检查时重点核对：算法是否按要求格式呈现、图是否重新画过、答案是否带单位与解释。

For time management, answer the easy questions first: short items such as binary search and simple tracing earn marks quickly, place the drawing questions of critical path analysis and linear programming in the middle, and keep the last 15 minutes for checking. When checking, focus on: whether the algorithm is presented in the required format, whether the graph has been redrawn clearly, and whether answers carry units and interpretations.

Summary | 总结

决策数学 D1 是 A-Level 数学中最”实用”的模块：算法提供解决问题的步骤框架，图论与最小生成树解决网络建设成本问题，Dijkstra 算法解决最短路径，中国邮递员问题解决全覆盖路线，关键路径分析管理工程进度，线性规划优化资源配置，二分图匹配解决任务指派。七个板块共用同一套”追踪-记录-解释”的答题语言。

Decision Mathematics D1 is the most “practical” module in A-Level Mathematics: algorithms provide the step-by-step framework for solving problems, graph theory and minimum spanning trees solve network construction cost problems, Dijkstra’s algorithm solves shortest path problems, the Chinese postman problem covers route coverage, critical path analysis manages project schedules, linear programming optimises resource allocation, and bipartite matching handles task assignment. All seven blocks share the same answering language of “trace, record and interpret”.

备考建议：第一，把每个算法的标准书写模板练到闭卷可输出；第二，重点突破三类综合题，即带权图上的最短路与最小生成树、含 4 个奇点的路线检查、以及多约束线性规划的整数解；第三，考前用真题限时训练，重点核对过程分。掌握了这些方法，D1 完全可以成为你的优势科目。

Study advice: first, practise the standard written template of every algorithm until you can reproduce it without notes; second, focus on three types of composite questions, namely shortest paths and minimum spanning trees on weighted graphs, route inspection with four odd vertices, and integer solutions in multi-constraint linear programming; third, do timed practice with past papers and check method marks carefully. Once you master these techniques, D1 can easily become one of your strongest subjects.

更多咨询请联系16621398022（同微信）