D1.5 - Linear programming

A linear program turns a decision into variables, one linear objective to maximise or minimise, and linear constraints that describe every permitted choice. Define each variable and its unit first so every coefficient has a clear meaning.

Choose decision variables for the quantities controlled. Write the objective, such as profit, cost or output, and state maximise or minimise. Translate each independent limit, minimum, ratio or total into an equality or inequality. Clear fractions or decimals to give simplified integer coefficients when requested, then include non-negativity and any required integer condition.

If a relation fixes a third variable, substitute it into both the objective and every constraint before presenting a two-variable model. Equivalent positive rescalings of an objective have the same optimum, but changing its sign reverses maximise and minimise.

Let $x$ and $y$ be numbers of products A and B. A earns 5 and B earns 8, each A uses 2 machine-hours and 4 kg of material, each B uses 3 machine-hours and 2 kg, with 60 hours, 64 kg and at least 6 units of A required. The model is: maximise $P=5x+8y$, subject to $2x+3y\leq60$, $4x+2y\leq64$, $x\geq6$, $x,y\geq0$. If products are indivisible, also require $x,y\in\mathbb Z$.

For two variables, each linear inequality defines a half-plane. Their common intersection is the feasible region $R$; only points in $R$, including permitted boundary points, can be candidates for the optimum.

Draw each boundary by replacing its inequality with equality, using accurate intercepts or two calculated points and a ruler. Test a point not on the line to select the correct side. Apply every constraint, including non-negativity, and label the intersection that remains as $R$. Find exact vertex coordinates by solving the pairs of boundary equations that meet there.

A linear objective changes at a constant rate, so on a bounded polygonal feasible region its maximum and minimum occur at a vertex, or along a whole boundary edge when the objective line is parallel to that edge. The ruler and vertex methods therefore describe the same geometry.

For $x,y\geq0$, $x+y\leq8$, $x+2y\leq10$, maximise $P=3x+4y$. The vertices are $(0,0)$, $(8,0)$, $(6,2)$ and $(0,5)$. Their objective values are 0, 24, 26 and 20, so the maximum is $P=26$ at $(6,2)$. Sliding a line $3x+4y=k$ towards larger $k$ gives the same final contact.

After choosing the optimal point, translate its coordinates and objective value back into the problem's quantities and units. Substitute into resource expressions when the unused amount or slack is required.

When decision variables count indivisible items, only integer-coordinate points in the feasible region are allowed. The continuous graphical optimum can be fractional, so it may be a bound or guide rather than a feasible answer.

Mark or list the lattice points that satisfy every constraint. A point on a non-strict boundary is allowed, while a strict inequality excludes its boundary. Evaluate the objective at all relevant feasible integer candidates; for a small region, enumerate them all. A fixed integer variable can instead be substituted into the constraints to obtain the complete integer range of the other variable.

Never round a fractional optimum automatically. Rounding one coordinate can violate a constraint, and rounding down can miss a better feasible lattice point. Check feasibility first, then compare objective values.

Consider integer $x,y\geq0$ with $2x+y\leq9$ and $x+3y\leq10$, maximising $P=5x+4y$. The continuous boundary intersection is $(17/5,11/5)$, which is not an allowed integer point. Because both objective coefficients are positive, for each possible integer $x$ it is enough here to retain the greatest feasible $y$.

The integer optimum is therefore $(4,1)$ with $P=24$. Simply rounding the continuous point to $(3,2)$ gives only 23, while $(4,2)$ is infeasible because $2x+y=10>9$.