Linear programming: maximising and minimising with constraints

Linear programming is a mathematical decision method for choosing quantities when resources are limited. A manager might ask how many products to make, how many shifts to staff or how to divide a budget so that profit, service or efficiency reaches its best feasible value.

Its central idea is to express the goal as an objective function, express limitations as linear constraints, then search for the optimum within the feasible region. The same framework handles maximisation and minimisation, from school projects to Australian businesses and public services.

Turning a story into variables

Start by naming the quantities that can change. Imagine a stall at a Melbourne community market deciding how many trays of plain cake, (x), and gluten-free cake, (y), to bake. These are decision variables, and each should have a clear unit so that every coefficient has meaning.

The goal becomes an objective function. If the stall earns $10 from each plain tray and $14 from each gluten-free tray, its contribution can be written as (P = 10x + 14y). Maximising (P) means finding the largest total contribution among all acceptable production mixes.

Resource limits become constraints. Suppose shared oven time gives (2x + y \leq 120) minutes, while packaging gives (x + 3y \leq 120) units. Non-negativity adds (x \geq 0) and (y \geq 0). Together, these inequalities describe which combinations the stall can actually produce.

Writing useful constraints

A constraint expresses a limit that every feasible solution must obey. Less-than-or-equal signs represent limited resources, such as oven minutes, labour hours or stock. Greater-than-or-equal signs represent minimum requirements, such as meeting customer demand or covering a fixed cost.

The non-negativity constraints prevent mathematically possible but meaningless values such as negative production. If products must be whole, the model needs integer restrictions. Rounding a fractional answer is not always safe because the rounded mix might exceed a limit, and solving the model with integer restrictions is known as integer linear programming.

The familiar routine of buying bread and milk at Woolworths or Coles depends on many such decisions. A distribution network might choose vehicle routes, warehouse capacity and delivery frequency to minimise cost while meeting store demand and refrigerated-space limits. The mathematics is the same even when the scale changes from cake trays to truckloads.

Reading the feasible region

Graph each constraint as a straight boundary line, find its intercepts, and shade the side containing valid solutions. The overlap is the feasible region: every point inside it satisfies every constraint at once. A solution outside that region breaks at least one stated limit.

The corner point theorem states that, for a linear objective over a bounded feasible region, an optimum occurs at a corner point. Graphically, the objective (P = 10x + 14y) represents parallel profit lines. Sliding one line across the region shows which direction improves the objective and where it last touches a feasible corner.

For a Sydney commuter service, planners might maximise passengers carried by choosing standard and accessible buses under fleet and driver limits. This stage depends on accurate graphs and intersections, so the geometry homework support material provides useful reinforcement for the geometrical part of the method.

Maximising profit and benefit

For the market-stall model, the feasible corners are ((0,0)), ((60,0)), ((48,24)) and ((0,30)). Substituting them into (P = 10x + 14y) gives $0, $600, $816 and $420 respectively. The largest value is $816 at ((48,24)), so the stall should prepare 48 plain trays and 24 gluten-free trays under the stated assumptions.

At this optimum, both resource constraints are binding. The oven limit and packaging limit are fully used, while no surplus labour or packaging remains. A different objective, such as maximising customer satisfaction or community access, would produce different coefficients and could therefore select another mix.

The same structure appears in resource industries. At an iron ore operation in Western Australia’s Pilbara, a planning team might maximise tonnes moved from stockpiles to rail while conveyor hours, loading equipment and train slots limit throughput. With a constant margin per tonne, the tonnage target becomes the objective and each operating limit becomes a linear constraint.

Minimising cost and time

Minimisation works with the same machinery but seeks the smallest objective value. Consider an Australian business buying electricity in peak and off-peak periods. Let (x) and (y) represent blocks of peak and off-peak supply, with each block equal to 1,000 kWh. Costs might be (C = 150x + 80y) dollars, subject to (x + y \geq 1000), (x \leq 600) and (y \leq 700).

The relevant feasible corners are ((300,700)), ((600,400)) and ((600,700)). Their costs are $101,000, $122,000 and $145,000, making ((300,700)) the least-cost combination. These choices operate within the National Electricity Rules, while consumer energy contracts must also respect the Australian Consumer Law.

Minimisation also appears in delivery routes, manufacturing waste and staffing schedules. The optimum is not simply the smallest quantity; it is the least expensive feasible combination. Practice with the inequality graphs and corner calculations in online maths revision support provides a useful check before relying on a solver.

Moving beyond two variables

A two-variable model can be drawn as a region in a plane. With three or more variables, the same feasible set exists in higher-dimensional space. Its corners are still candidate optima, but finding them by hand becomes impractical. The simplex algorithm handles this by moving between feasible corner points while improving the objective value.

A farm in the Murray-Darling Basin might allocate hectares among wheat, cotton and pasture. Maximum profit could depend on irrigation water, labour, fodder and seed supplies. If each hectare has a constant profit and input requirement, those figures can be placed in an objective function and a set of linear inequalities.

Calculators and spreadsheet Solver tools can handle larger models, including profit maximisation and cost minimisation with hundreds of variables. Their results still depend on the coefficients supplied. If returns diminish as production rises, or if staffing cost changes sharply after a threshold, a linear model may be inappropriate and a nonlinear one may be needed.

Checking the answer and its limits

Sensitivity analysis examines how the optimum responds to a change. A binding constraint is one that is fully used, while slack measures unused capacity in a non-binding constraint. The shadow price of a binding resource estimates the objective’s improvement from a small increase in that resource, provided the coefficients and other limits remain unchanged.

Three warnings deserve attention. An infeasible model has no combination satisfying every constraint. An unbounded model permits unlimited improvement because no effective limit blocks it. Multiple optima occur when the objective is parallel to an active edge, giving several equally good solutions. These signals usually point to a missing constraint, an unrealistic coefficient or an unsuitable objective.

Mathematical feasibility is not the same as practical feasibility. A production roster must still meet employment and safety rules, while a commercial promise must remain consistent with Australian consumer protections. Such requirements should enter the model numerically whenever possible. The computed optimum should also be checked against the original assumptions rather than accepted solely because software produced it.

Linear programming gives a repeatable way to turn competing goals and limited resources into a transparent decision. Its strength comes from showing not only which option performs best, but also which limits make that option possible.

The durable lesson is to define the decisions, state the objective honestly, include every relevant linear limit, and verify the resulting optimum against the real situation.