Math AI: Network Flow and Optimisation Problems

Optimisation is the mathematical engine behind efficient decision-making in business, logistics, and technology. For your IB Math AI HL studies, mastering linear programming and its solution methods equips you with a powerful framework to model real-world constraints and find the best possible outcomes, from scheduling flights to allocating factory resources.

Formulating Linear Programming Problems

At its core, a linear programming (LP) problem involves finding the maximum or minimum value of a linear expression, subject to a set of linear inequalities. The first and most critical step is translating a word problem into a precise mathematical model. This model has three key components.

First, you must define the decision variables. These are the quantities you can control, typically represented by $x$, $y$, $z$, etc. For instance, in a production problem, $x$ could be the number of tables made and $y$ the number of chairs. Second, you construct the objective function. This is the linear expression you want to optimise—either maximise (like profit) or minimise (like cost). It will be a function of your decision variables, such as $P=50x+30y$.

Third, you write the constraints. These are the linear inequalities that model the limitations of the situation, such as available labour hours, raw materials, or storage space. Constraints also include non-negativity conditions ($x\ge 0$, $y\ge 0$), as you generally cannot produce a negative quantity of items. A fully formulated problem looks like this: Maximise $P=50x+30y$ subject to $2x+y\le 100$ (labour constraint), $x+2y\le 80$ (material constraint), and $x,y\ge 0$.

Graphical Solution and Feasible Regions

When an LP problem involves only two decision variables, you can solve it graphically. This method provides an intuitive visual understanding of the entire optimisation process. You begin by plotting each constraint inequality on the $xy$-coordinate plane. Treat each inequality as an equation to graph the boundary line, then shade the region that satisfies the inequality (e.g., for $2x+y\le 100$, you shade below the line).

The intersection of all shaded regions from every constraint (including non-negativity) forms the feasible region. This set of points represents all possible combinations of $x$ and $y$ that satisfy every constraint. The feasible region is always a convex polygon. A fundamental theorem of linear programming states that if an optimal solution exists, it will occur at one of the vertices (corner points) of this polygon.

To find the optimal solution, you first identify the coordinates of all vertices by solving the systems of equations where the boundary lines intersect. Then, you substitute the coordinates of each vertex into the objective function. The vertex that yields the highest value (for maximisation) or the lowest value (for minimisation) is the optimal solution. This graphical method is a cornerstone of the IB AI HL syllabus and is frequently tested.

The Simplex Method for Higher Dimensions

Real-world optimisation problems often involve many more than two variables (e.g., optimising a supply chain with dozens of products and warehouses). The graphical method becomes impossible in three dimensions and useless beyond that. This is where the simplex method comes in—it’s a powerful algebraic algorithm for solving LP problems with any number of variables and constraints.

The simplex method operates on a key principle: it systematically moves from one vertex of the feasible region to an adjacent vertex, each time improving the value of the objective function, until the optimum is reached. It uses a tabular format called a simplex tableau to organise the coefficients of the objective function and constraints. You work with slack variables, which transform inequalities into equations. For example, the constraint $2x+y\le 100$ becomes $2x+y+s_1=100$, where $s_1\ge 0$ is a slack variable representing unused labour.

The algorithm involves iterative steps: selecting a pivot column (the variable that will most improve the objective), selecting a pivot row (the most restrictive constraint), and performing row operations (similar to Gaussian elimination) to create a new, improved tableau. The process repeats until no further improvement is possible, at which point the optimal solution can be read directly from the final tableau. While you will not perform lengthy simplex calculations by hand in the IB exam, you are expected to understand its purpose, setup, and conceptual steps.

Application to Network Flow and Real-World Problems

The true power of linear programming is revealed in its applications. Network flow problems are a classic type of LP application where the goal is to maximise the flow of material, information, or traffic through a network of nodes and arcs (connections), subject to capacity constraints on each arc. Examples include maximising data packet flow through internet routers or oil through pipelines.

More broadly, optimisation techniques model countless real-world scenarios. In resource allocation, a factory manager can use LP to determine the product mix that maximises profit without exceeding machine time and material budgets. In scheduling, airlines use sophisticated LP models to assign crews to flights while minimising costs and complying with complex labour regulations. In diet problems (a historical LP application), the goal is to minimise the cost of a diet while meeting all nutritional requirements—each nutrient is a constraint, and each food item is a variable with an associated cost.

For your IB assessments, you will be expected to interpret the solution of an LP model in context. If the optimal solution is $(x=20,y=30)$, you must state, "The company should produce 20 tables and 30 chairs to maximise profit." You may also need to perform sensitivity analysis, which involves discussing how changes in a constraint (like an increase in available materials) might affect the optimal solution.

Common Pitfalls

1. Misformulating Constraints: A frequent error is reversing inequality signs or writing incorrect coefficients from the problem statement. Correction: Read the constraint carefully. "At most 100 hours" translates to $\le 100$. "You need at least 2 units of A" for each product means a constraint like $2x\le \text{(total units of A)}$.

1. Ignoring Non-Negativity: Forgetting that $x,y\ge 0$ is a formal constraint can lead to an incorrectly drawn feasible region. Correction: Always explicitly state non-negativity constraints as part of your initial formulation. They define the first quadrant as the primary space for your graph.

1. Incorrect Vertex Testing: Students sometimes test interior points of the feasible region or miss a vertex because they solved the system of equations incorrectly. Correction: Methodically find all intersections of the boundary lines that lie within the feasible region. Use simultaneous equations accurately, and verify each point satisfies all constraints.

1. Misinterpreting the Simplex Method's Role: Thinking the simplex method is a graphical tool or that slack variables are part of the original problem. Correction: Understand that the simplex method is an algebraic, tabular algorithm for high-dimensional problems. Slack variables are artificial constructs added to convert the problem into a standard form the algorithm can process.

Summary

• Linear programming provides a systematic method for optimisation by formulating an objective function to maximise or minimise, subject to a set of linear constraints.
• For two-variable problems, the optimal solution can be found graphically by identifying the feasible region and evaluating the objective function at each vertex.
• The simplex method is an essential algorithm for solving complex LP problems with many variables and constraints, operating by moving efficiently between vertices via simplex tableaux.
• These techniques are directly applicable to advanced real-world contexts like network flow, resource allocation, and scheduling, forming a critical part of operational research and business decision-making.
• Success in IB Math AI HL requires careful problem formulation, accurate graphical or algebraic solution, and clear contextual interpretation of the results.