Linear Programming

Imagine you're running a small factory. You have limited raw materials, limited machine hours, and limited labour. You make two products, each with different profit margins. How many of each should you produce to maximise your profit? That's a Linear Programming Problem (LPP), and it's one of the most practical applications of mathematics in the business world. Linear programming is used by companies to optimise supply chains, by airlines to schedule flights, by investment firms to balance portfolios, and even by sports teams to allocate training resources. It's all about making the best possible decision given a set of constraints. The word 'linear' means everything is a straight line — no curves, no squares, no complicated functions. Just nice, simple linear relationships. An LPP has three essential components: decision variables (what you can control — like how many units to produce), an objective function (what you want to maximise or minimise — like profit or cost), and constraints (the limits you have to work within — like time, money, or materials). Plus, there are always non-negativity constraints: you can't produce negative quantities. The standard form of an LPP is: optimise Z = c₁x₁ + c₂x₂ + ... subject to a₁₁x₁ + a₁₂x₂ ≤ b₁, a₂₁x₁ + a₂₂x₂ ≤ b₂, ..., and x₁, x₂ ≥ 0. All constraints are linear inequalities. The first step in solving any LPP is formulating it — translating a word problem into mathematical expressions. This means identifying the decision variables, writing the objective function, and listing all constraints. This is often the hardest part for students, but it's just pattern recognition. Look for keywords: 'maximise' or 'minimise', 'at least' (≥), 'at most' (≤), 'not more than' (≤), 'not less than' (≥). Once you have the mathematical formulation, you solve it using the graphical method. The graphical method works when you have two decision variables (x and y) because we can draw the constraints on a 2D graph. Each constraint is a straight line, and the inequality tells you which side of the line is valid. The region where ALL constraints are satisfied simultaneously is called the feasible region — it's usually a polygon (convex polygon, to be exact). The key theorem of linear programming states that the optimal solution (maximum or minimum of Z) lies at one of the vertices (corner points) of the feasible region. So you don't need to check every point inside — just the corners. The corner point method: (1) find all corner points of the feasible region, (2) evaluate the objective function Z at each corner, (3) pick the corner with the largest Z (for maximisation) or smallest Z (for minimisation). That corner gives the optimal values of x and y, and the corresponding Z is the optimal value. Sometimes, the optimal solution isn't unique. If the objective function line is parallel to one of the constraint boundaries, then every point on that entire edge is optimal — giving multiple optimal solutions. Sometimes the feasible region is unbounded (goes on forever in some direction). In that case, a maximum might not exist (Z keeps increasing), but a minimum usually does. And sometimes the constraints contradict each other, giving an empty feasible region — in which case no solution exists (infeasible problem). By the end of this chapter, you'll be able to take any real-world optimisation problem with two variables, formulate it mathematically, graph the constraints, and find the optimal solution. Linear programming is one of those rare maths topics where what you learn in class directly applies to real business and engineering decisions.