3Solutions of linear programs

IB Optimisation

3.1 Linear programs

We’ll come up with an algorithm to solve linear program efficiently. We first

illustrate the general idea with the case of a 2D linear program. Consider the

problem

maximize x

1

+ x

2

subject to

x

1

+ 2x

2

≤ 6

x

1

− x

2

≤ 3

x

1

, x

2

≥ 0

We can plot the solution space out

x

1

x

2

x

1

− x

2

= 3

x

1

+ 2x

2

= 6

c

To maximize

x

1

+

x

2

, we want to go as far in the

c

direction as possible. It

should be clear that the optimal point will lie on a corner of the polygon of

feasible region, no matter what the shape of it might be.

Even if we have cases where c is orthogonal to one of the lines, eg

x

1

x

2

x

1

− x

2

= 3

x

1

+ x

2

= 3.5

c

A

An optimal point might be

A

. However, if we know that

A

is an optimal point,

we can slide it across the

x

1

+

x

2

= 3

.

5 line until it meets one of the corners.

Hence we know that one of the corners must be an optimal point.

This already allows us to solve linear programs, since we can just try all

corners and see which has the smallest value. However, this can be made more

efficient, especially when we have a large number of dimensions and hence

corners.