Suppose we want to maximise (or minimise) the linear function $C(x,y)=\lambda x+\mu y$ on a set $S$. Suppose $S$ is defined as the solution of  the system of three linear inequalities:

$a_1x+b_1y\leq c_1$

$a_2x+b_2y\leq c_2$

$a_3x+b_3y\leq c_3$

In general, the solution set of these inequalities will be a triangular sea of $x$ and $y$:

The points $\mathbf{a}, \mathbf{b}, \mathbf{c}$ are the extreme points on $S$. We want to prove that $C(x,y)$ is maximised at $\mathbf{a}, \mathbf{b} \text{ or } \mathbf{c}$.

## Theorem

Suppose that $S$ is a closed triangular sea of $x$ and $y$. Then $C(x,y)=\lambda x+\mu y$ attains its maximum at an extreme point of $S$.

### Proof

Proper diagrams to follow…

Suppose $k=\max_{(x,y)\in S}C(x,y)$ is attained at $(x_0,y_0)$. This we may assume because $S$ is compact and $C(x,y)$ is continuous. Now

$\lambda x+\mu y=k$

$\Rightarrow y=-\frac{\lambda}{\mu}x+\frac{k}{\mu}$ (*)

Suppose without loss of generality that $\mu>0$. Then maximising $C(x,y)$ is equivalent to maximising $k/\mu$, the $y$-intercept of the family of lines $\{L_{k/\mu}: k/\mu\in\mathbb{R}\}$ of the form (*), with slope $-\lambda/\mu$ subject to the condition that $L_{k/\mu}\cap S\neq\emptyset$.

Assume without loss of generality that $-\lambda/\mu>0$. If $(x_0,y_0)\in\text{int}(S)$, then we can move around in any sense so that $k$ is not a maximum as we can increase the $y$-intercept of any slope $-\lambda/\mu$ line:

If $(x_0,y_0)\in\text{int}(S)$ on the line $L_1$, then there contains an open ball in $S$ containing $(x_0,y_0)$. Hence we can take a point $(x_1,y_1)\in S$ on the line $L_2$ with a greater $y$-intercept.

Hence $(x_0,y_0)$ is on the boundary of $S$, $\partial S$. Assume without loss of generality that $(x_0,y_0)$ is on the line segment $\mathbf{ab}$ but not equal to $\mathbf{a}\text{ or } \mathbf{b}$. Let $m$ be the slope of the line segment $\mathbf{ab}$ (again assume w.l.o.g. that $m>0$). If $-\lambda/\mu:

Then the line going through $\mathbf{a}$ has a greater $y$-intercept so $(x_0,y_0)$ can’t be on the interior of $\mathbf{ab}$. Similarly, if $-\lambda/\mu>m$, then the line going through $\mathbf{b}$ has a greater $y$-intercept so $(x_0,y_0)$ can’t be on the interior $\mathbf{ab}$ neither.

If $-\lambda/\mu=m$:

In this case $C(x,y)$ is constant on the line segment $\mathbf{ab}$ so in particular $C(x_0,y_0)=C(\mathbf{a})=C(\mathbf{b})$ and hence the maximum is on an extreme point $\bullet$