Linear Programming and Optimisation

Linear programming provides a powerful mathematical framework for making optimal decisions when resources are limited. Whether you’re managing supply chains, allocating budgets, or scheduling projects, it transforms vague objectives into precise, solvable models. Mastering its techniques—from intuitive graphs to powerful algorithms—equips you to tackle a vast array of real-world optimisation problems systematically and efficiently.

Formulating the Linear Programming Problem

Every linear programming (LP) problem begins with translating a word-based scenario into a precise mathematical model. This formulation is the critical first step and consists of three core components.

First, you must define the decision variables. These are the unknown quantities you can control, typically representing amounts to produce, resources to allocate, or activities to undertake. For example, if a company produces two products, you might let $x$ represent the units of Product A and $y$ represent the units of Product B. These variables are always non-negative ($x\ge 0,y\ge 0$), a constraint often implied in real-world contexts.

Next, you construct the objective function. This is a linear expression of the decision variables that you seek to either maximize (like profit or revenue) or minimize (like cost or waste). If Product A generates a profit of $\pounds 5$ per unit and Product B generates $\pounds 3$ per unit, the objective function to maximize would be $P=5x+3y$.

Finally, you identify the constraints. These are linear inequalities (or equations) that model the limitations of the system, such as available raw materials, labour hours, or machine capacity. Each constraint restricts the values the decision variables can take. For instance, if producing one unit of A uses 2 hours of labour and one unit of B uses 1 hour, with only 100 total labour hours available, the constraint is $2x+y\le 100$. The complete LP model is the combination of the objective function and all constraints, defining the search space for the optimal decision.

Solving Two-Variable Problems Graphically

The graphical method offers an intuitive way to solve LP problems with two decision variables. It provides a visual foundation for understanding core concepts like the feasible region and optimality.

To begin, plot every constraint on an $x$-$y$ coordinate plane. Each inequality corresponds to a half-plane. The area where all constraints overlap—including the non-negativity conditions—is the feasible region. This region contains every possible combination of $x$ and $y$ that satisfies all the problem's limitations. It is always a convex polygon, which may be bounded or unbounded.

The fundamental theorem of linear programming states that if an optimal solution exists, it will occur at a vertex (corner point) of this feasible region. To find it, you can use the objective line method. First, sketch the objective function line for an arbitrary value (e.g., set $P=30$ to graph $5x+3y=30$). Then, slide this line parallel to itself in the direction of increasing (for maximisation) or decreasing (for minimisation) value. The last point of contact between this moving line and the feasible region will be a vertex where the optimum is achieved. The coordinates of this vertex are your optimal solution, which you find by solving the simultaneous equations of the two lines that intersect there.

The Simplex Algorithm for Multivariable Problems

When problems involve more than two variables, the graphical method becomes impossible. This is where the simplex algorithm comes into play. It is an iterative algebraic procedure that systematically navigates from one vertex of the feasible region to an adjacent one, improving the objective function at each step until the optimum is found.

The algorithm operates on a standard form of the LP model. This form requires all constraints to be equations (not inequalities) and all variables to be non-negative. You convert inequalities to equations by adding slack variables. For example, the constraint $2x+y\le 100$ becomes $2x+y+s=100$, where $s\ge 0$ is a slack variable representing unused labour.

The simplex method starts at an initial feasible solution (often where all decision variables are zero and slack variables equal the resource limits). It uses a simplex tableau—a tabular arrangement of coefficients—to organise calculations. At each iteration, the algorithm performs a pivot operation: a non-basic variable (currently zero) with potential to improve the objective is chosen to enter the basis, and a basic variable is chosen to leave, ensuring feasibility is maintained. This process repeats until no entering variable can improve the objective, signalling that the optimal solution has been reached. While performing it by hand can be lengthy, understanding its logic—the movement from vertex to vertex along edges of the feasible region—is crucial.

Integer Programming and Its Implications

Often, solutions must be whole numbers; you cannot produce 3.7 cars or hire 2.5 people. Integer programming deals with linear programming problems where some or all decision variables are restricted to integer values. This simple-sounding requirement has profound impacts on solution methods and optimal values.

An LP problem with an added integer constraint is called an integer programming (IP) problem. When all variables must be integers, it's a pure integer program; when only some must be, it's a mixed-integer program. The immediate consequence is that the feasible region is no longer a continuous polygon but a set of discrete lattice points within it. You cannot simply solve the associated LP (the "LP relaxation") and round the answer, as this can lead to infeasible or highly suboptimal solutions.

Solving IP problems requires more advanced algorithms like branch-and-bound. This method systematically partitions the feasible region into subproblems (branching) and uses bounds from the LP relaxation to prune subproblems that cannot contain the optimal integer solution. The presence of integer constraints means the optimal value of an IP problem is always worse than or equal to the optimal value of its LP relaxation; you often pay a price, known as the integrality gap, for requiring whole-number solutions. This makes integer programming problems computationally harder but essential for accurate modelling in logistics, scheduling, and resource allocation.

Common Pitfalls

1. Misidentifying Constraints as Equations: A frequent error is modelling a capacity limit (e.g., "use up to 100 hours") as an equation ($=100$) instead of an inequality ($\le 100$). This falsely implies the resource must be fully exhausted, which may not be optimal or even feasible. Always check the wording: "at most," "no more than," and "up to" indicate inequalities.

1. Incorrectly Plotting the Feasible Region: When graphing, students often shade the wrong side of an inequality line. A reliable test is to substitute the origin ($(0,0)$), if it's in the feasible region, into the inequality. If the origin satisfies it (e.g., $0\le 100$ is true), then the half-plane containing the origin is the correct one to shade.

1. Assuming Rounding is Sufficient for Integer Solutions: After finding an optimal LP solution of, say, $x=3.2,y=6.7$, rounding to $(3,7)$ might violate a constraint or yield a far lower profit than the true integer optimum. Integer programming problems require dedicated solution methods; rounding is not a reliable technique.

1. Forgetting Non-Negativity Constraints: While often implied, the conditions $x\ge 0,y\ge 0$ are explicit constraints and must be included in both the formulation and the graphical representation. Omitting them can lead to an incorrectly defined feasible region and a nonsensical optimal solution.

Summary

• Formulating an LP problem requires precisely defining decision variables, constructing a linear objective function to maximise or minimise, and stating all linear constraints as inequalities.
• For two-variable problems, the graphical method lets you identify the feasible region and locate the optimal solution at a vertex by sliding the objective function line.
• The simplex algorithm solves larger problems algebraically by using slack variables to convert inequalities to equations and iteratively pivoting between vertices in a simplex tableau until no further improvement is possible.
• Integer programming adds the requirement for integer solutions, necessitating algorithms like branch-and-bound and often resulting in an optimal value worse than the standard LP solution, highlighting the integrality gap.