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<m:

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

Advertisements