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.

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: