A-Level Further Mathematics: Decision Mathematics

Decision Mathematics provides the logical and algorithmic toolkit for solving complex real-world optimization problems. It transforms abstract networks, schedules, and resource allocations into structured models that can be analyzed and solved systematically. Mastering its concepts, from graph theory to linear programming, equips you with the ability to design efficient routes, manage large-scale projects, and allocate scarce resources optimally—skills vital in fields like logistics, computer science, and operations research.

Graph Theory: Modeling Connections

At its core, graph theory is the study of connections. A graph is a collection of vertices (or nodes) connected by edges (or arcs). This simple structure can model anything from computer networks and social media connections to transportation maps. A directed graph (digraph) has edges with a specific direction, useful for representing one-way streets or task dependencies, while an undirected graph has bidirectional connections.

The structure of a graph can be efficiently represented using an adjacency matrix. For a graph with n vertices labeled 1 to n, the adjacency matrix A is an $n\times n$ matrix where the entry $a_{ij}$ equals 1 if there is an edge from vertex i to vertex j, and 0 otherwise. For a weighted graph, where edges have values (like distances or costs), $a_{ij}$ contains the weight of that edge.

Understanding connectivity is fundamental. A graph is connected if there is a path between every pair of vertices. The degree of a vertex is the number of edges incident to it; in a digraph, we distinguish between indegree (edges coming in) and outdegree (edges going out). Analyzing connectivity helps determine the robustness of a network or the feasibility of a route.

Algorithms for Optimization

Decision Mathematics is renowned for its step-by-step algorithms that guarantee optimal solutions to specific problems. A key area is finding the shortest path between two vertices in a weighted network. Dijkstra's algorithm solves this efficiently. You start at the initial vertex, permanently label it with a distance of zero, and then iteratively label the nearest unvisited vertex from any permanently labeled vertex. This process continues until the destination vertex is permanently labeled, at which point its label is the length of the shortest path. Tracing back through the labels reveals the route itself.

For problems requiring connection of all vertices at minimum total cost without creating cycles, you need a minimum spanning tree. Two primary algorithms solve this. Kruskal's algorithm involves sorting all edges in ascending order of weight and adding them one by one to the tree, rejecting any edge that would form a cycle. Prim's algorithm starts at any vertex and grows the tree by iteratively adding the cheapest edge that connects a vertex in the tree to a vertex not yet in the tree. Both yield a minimum spanning tree, but their step-by-step processes differ.

A famous and computationally difficult problem is the travelling salesman problem (TSP): finding the shortest possible route that visits each vertex exactly once and returns to the start. For the A-Level, you typically encounter the classical TSP on a complete graph. While finding the absolute optimal tour is complex for large networks, you will apply algorithms to find good upper and lower bounds, such as using a minimum spanning tree to construct a tour.

Linear Programming: Maximizing and Minimizing

Linear programming (LP) is a method for finding the optimal value (maximum or minimum) of a linear objective function, subject to a set of linear constraints (inequalities). You first model a real-world scenario, like maximizing profit given resource limits, using decision variables.

For problems with two variables, the graphical method is powerful. You plot the constraints as half-planes on an $xy$-axis. The feasible region where all constraints overlap is a polygon. The optimal solution lies at a vertex of this region. You find it by evaluating the objective function at each vertex coordinate or by drawing a profit line and sliding it across the feasible region until it last touches a vertex.

For more complex problems with multiple variables, the simplex method is used. This is an algebraic, iterative algorithm performed within a simplex tableau. You move from one vertex of the multidimensional feasible region to an adjacent vertex that improves the objective value, pivoting on tableau elements until no further improvement is possible, indicating the optimal solution. At A-Level, you will perform the simplex method by hand on carefully constructed problems, interpreting each tableau to track the values of variables and the objective function.

Critical Path Analysis: Planning Projects

Critical path analysis (CPA) is a project management technique using a network of activities to plan, schedule, and control complex projects. Each activity is represented as an edge on an activity-on-arc network. Nodes represent the start and end of activities, with dummy activities (dashed arcs) used to correctly represent dependencies.

The process involves calculating key timings for each event (node):

• Earliest Event Time (EET): The longest time from the start to reach that event.
• Latest Event Time (LET): The latest time an event can occur without delaying the overall project.

The float or total float of an activity is the amount of time it can be delayed without affecting the project completion time. It is calculated as: $LE{T}_{\text{end}}-EE{T}_{\text{start}}-\text{duration}$. Activities with zero float are critical activities and form the critical path—the longest path through the network. Any delay on the critical path directly delays the entire project. This analysis allows for resource scheduling, enabling you to level resources by exploiting the float of non-critical activities.

Common Pitfalls

1. Misidentifying Graph Types and Connectivity: A common error is confusing directed and undirected graphs when constructing an adjacency matrix. For an undirected graph, the matrix must be symmetric. Also, ensure you correctly apply the definition of connectivity; a graph with all vertices connected in pairs is not necessarily "fully connected" (complete)—it just needs a path, not a direct edge, between vertices.

1. Incorrect Algorithm Application: When applying Dijkstra's or Prim's algorithm, students often fail to follow the exact, iterative labeling process, leading to incorrect permanent labels. With Kruskal's, the mistake is forgetting to check for cycles before adding an edge. Always state each step clearly in your working and use a standard, recognized layout for tables and labels to avoid confusion.

1. Simplex Method Sign Errors and Interpretation: The simplex method is procedural. A single arithmetic error when pivoting corrupts the entire tableau. Double-check each row operation. Furthermore, know how to read the final tableau: the objective function value is in the top-right, and the values of the basic variables are found in the right-hand column corresponding to their identity matrix columns.

Summary

• Graph theory provides the language and models (vertices, edges, adjacency matrices) to represent networks and analyze their connectivity and structure.
• Optimization algorithms like Dijkstra's (shortest path), Kruskal's, and Prim's (minimum spanning tree) offer systematic, step-by-step methods to find optimal solutions within weighted networks.
• Linear programming solves resource allocation problems, using the graphical method for two variables and the algebraic simplex method for more complex, multi-variable scenarios.
• Critical path analysis uses activity networks to calculate event times, identify the critical path, and determine float, enabling efficient project scheduling and resource management.
• Success in Decision Mathematics relies on precise, meticulous application of algorithms and a clear understanding of how each mathematical model translates into a practical, solvable problem.