Suppose we want to maximise (or minimise) the linear function on a set . Suppose is defined as the solution of the system of three linear inequalities:

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

*The points are the extreme points on . We want to prove that is maximised at .*

## Theorem

*Suppose that is a closed triangular *sea of and . *Then attains its maximum at an extreme point of .*

### Proof

**Proper diagrams to follow…**

Suppose is attained at . This we may assume because is compact and is continuous. Now

(*)

Suppose without loss of generality that . Then maximising is equivalent to maximising , the -intercept of the family of lines of the form (*), with slope subject to the condition that .

Assume without loss of generality that . If , then we can move around in any sense so that is not a maximum as we can increase the -intercept of any slope line:

*If on the line , then there contains an open ball in containing . Hence we can take a point * *on the line with a greater -intercept.*

Hence is on the boundary of , . Assume without loss of generality that is on the line segment but not equal to . Let be the slope of the line segment (again assume w.l.o.g. that ). If :

Then the line going through has a greater -intercept so can’t be on the interior of . Similarly, if , then the line going through has a greater -intercept so can’t be on the interior neither.

If :

In this case is constant on the line segment so in particular and hence the maximum is on an extreme point

## Leave a comment

Comments feed for this article