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.