Linear Programming

The key fact

In a linear programming problem, the feasible region is the set of points satisfying every constraint at once, and a feasible solution is any point in it. The objective function $Z=ax+by$ being linear means it can only reach its maximum or minimum at a corner point of that region, never somewhere in the interior.

Solving a problem, step by step

1. Name the decision variables, e.g. $x$ = chairs made and $y$ = tables made.
2. Turn each limit in the problem into an inequality in $x$ and $y$.
3. Add the non-negativity constraints $x \ge 0$ and $y \ge 0$.
4. Write the objective function $Z$ to maximise or minimise.
5. Draw each constraint's line and shade the side that satisfies it. The overlap is the feasible region.
6. Find the corner points and evaluate $Z$ at each one.

Worked example: forming the constraints

A workshop makes chairs and tables. A chair needs 2 hours of carpentry and 1 hour of finishing. A table needs 1 hour of carpentry and 3 hours of finishing. Each day there are 10 hours of carpentry and 15 hours of finishing available. The profit is ₹300 per chair and ₹400 per table. How many of each maximises profit?

Solution: Let $x$ be the number of chairs and $y$ the number of tables. Carpentry gives $2x + y \le 10$ and finishing gives $x + 3y \le 15$, with $x, y \ge 0$. The objective is $Z = 300x + 400y$. These are the same constraints as the region below, so its corners are $(0, 0)$, $(5, 0)$, $(3, 4)$ and $(0, 5)$:

The maximum profit is ₹2500, from 3 chairs and 4 tables a day.

Worked example: a tie between two corners

The feasible region for $2x+y \le 10$, $x+3y \le 15$, $x,y \ge 0$ has corners $(0,0)$, $(5,0)$, $(3,4)$, and $(0,5)$. For $Z=ax+by$ with $a,b>0$, what condition on $a$ and $b$ makes the maximum occur at both $(3,4)$ and $(0,5)$?

Solution: The maximum can only be shared by two corners if $Z$ takes the same value at both. Otherwise one would beat the other. Set them equal:

With $b = 3a$, $Z = a(x + 3y)$, so every point on the edge $x + 3y = 15$ joining $(3, 4)$ and $(0, 5)$ gives the same value, $15a$. The maximum is reached along that whole edge, not just at its two corners.

Common mistakes

• Leaving out $x, y \ge 0$. Without them the region spills into negative quantities, which make no sense for chairs or tables.
• Shading the wrong side of a line. Test a point such as $(0, 0)$: if it satisfies the inequality, shade the side containing it.
• Trusting corners in an unbounded region. If the region is unbounded, a maximum may not exist. Check whether $Z$ can grow without limit before quoting a corner value.