In broad terms a linear programme is an optimisation problem of a linear function where there are linear bounds on the variables.

Linear programme general form

Linear programme

It helps to standardise this into the following form. Note the use of matrix notation here.

Linear programme standard form

We can convert all linear programmes into standard form using the following Lemma.

All linear programmes can be represented in standard form

Geometric view

From now on we just consider linear programmes in standard form.

We can consider the feasible $x$ such that $x \geq 0$ and $x^T A \leq b$.

As there are $n$ variables we know $x \in \mathbb{R}^n$, more over as $x \geq 0$ we have that it lies in the positive region on $\mathbb{R}^n$.

Each row of $Ax \leq b$ defines a half space, so the feasible $x$ lie in the positive region of $x \in \mathbb{R}^n$ cut out by these half spaces.

So the feasible region is cut out by $n + m$ half spaces in $\mathbb{R}^n$.

The vertices in this feasible space are ones that lie on a 0-dimensional intersection of the boundary of the half spaces. In the example above these would be

$$(0,0), (0,200), (100,200), (300,0), \mbox{ and } (300, 133.33..).$$

Linear programme solvers

When it comes to solving a linear programming problem.

Statement

There are polynomial time algorithms like the ellipsoid method and interior-point method but in practice these can be slower than the much more widely used simplex method which can be exponential in its worst cases.

Simplex method

As vertices are extremal points with regards to the constraints we have that if the maximum of the objective function exists then it must be achieved on one of the vertices. Therefore the idea of the simplex algorithm is to start at a vertex then compare the objective function to all other vertices connecting to it.

So in short

1. Start at x = 0, if that is feasible.
2. Find all vertices adjacent to x along an edge.
3. compare the objective function of all vertices and
	1. If the current x is highest return that value.
	2. Switch x to be the highest of the objective functions found around x.
4. Go to step 2.

This only works if there is a point in the feasible region that achieves this maximum. Here we have 2 constraints:

• There is a point in the feasible region.
• That some point achieves a maximum - this happens when the region is bounded and has finite volume.

These are summarised by the two types of linear programme.

Infeasible linear programme

Unbounded linear programme

Determining if a linear programme is infeasible

Suppose we have a linear programme in standard form which may or may not be a Infeasible linear programme. For any inequality and $x \in \mathbb{R}^n$

$$ \sum_i a_{i,j} x_j \leq b_i$$

we can satisfy it by adding an arbitrarily small $z \in \mathbb{R}$ to the left hand side

$$ z + \sum_i a_{i,j} x_j \leq b_i.$$

If $z \geq 0$ we now that the original $x \in \mathbb{R}^n$ satisfied the inequality.

In summary from our original linear programme we can extend it to include an $n+1$‘th variable $z$. We augment the $m$ constraints to include this variable $z$ on the left hand side. This is now a feasible linear programme.

Moreover, we can change the objective function of the linear programme to simply maximise $z$ and if that value is positive we have a feasible point in the original linear programme.

Checking if a linear programme is feasible

Aside: How to verify solutions?

Lets try to upper bound the objective function $x_1 + 6 x_2 + 10 x_3$, we will do this with linear combinations of the inequalities. Lets consider the following

$$ \begin{align*} (x_2) * 1/3 + (x_1 + 3x_2 + 2 x_3) + (x_2 + 3x_3) * 8/3 & \leq 200 * 1/3 + 1000 + 500 * 8/3\\ x_1 + x_2(1/3 + 1 + 8/3) + x_3 (2 + 3 * 8/3) & \leq 2400\\ x_1 + 6 x_2 + 10 x_3 \leq 2400 \end{align*} $$

This then gives that the objective function is bounded above 2400, so the point provided must be optimal as we can never get a larger objective score.

Though I picked some values for the linear combination, how do we more generically find them and when will I know the bound is low enough?

Dual linear programme

How do we get which linear combinations will be “optimal”?

Define $y_i$ for $1 \leq i \leq m$ and take $y_i \geq 0$ linear combinations of each of the constraints defined by

$$\sum_j a_{i,j} x_j \leq b_i.$$

With the goal to finish with an equation of the form

$$ \sum_j c_j x_j \leq \sum_i y_i \left ( \sum_j a_{i,j} x_j \right ) = \sum_j \left ( \sum_i y_i a_{i,j} \right ) x_j \leq C = \sum_i y_i b_i.$$

For the optimum bound we would like to minimise the quantity on the right.

To do this define a new linear programme.

Dual linear programme

If in the original linear programme we have $n$ variables and $m$ constraints. In the dual linear programme we have $m$ variables and $n$ constraints.

We call the initial linear programme the primal linear programme however we will try not to use that term.

Dual of a Dual

The dual dual linear programme is the original linear programme

Weak duality

The intuition behind the dual linear programme was that it bounded the objective function. So lets check if that is true.

Weak duality theorem (linear programme)

This means the example above gives us a good way to check for optimal points.

If a point in a linear programme has equal objective function to a point in its dual linear programme they are both optimal

Check for unbounded linear programme

Another corollary of the Weak duality theorem helps us identify when we have unbounded linear programmes.

Unbounded linear programmes have infeasible duals

Note that as the dual dual linear programme is the original linear programme this also gives us that if the dual linear programme is unbounded then the original linear programme is infeasible.

This gives us a nice check for if a linear programme is unbounded. As we know Checking if a linear programme is feasible can be done, we just need to check if the dual linear programme is feasible - if it is then the original linear programme is bounded. If the dual linear programme is not feasible then we still need to check if the original linear programme is feasible or not (note a linear programme can’t be both infeasible and unbounded).

Therefore we have a nice algorithm to check if we have a solvable linear programme.

Algorithm

Strong duality theorem

Strong duality theorem (linear programme)

This can be reformulated in terms of optimal points.

Strong duality theorem optimum (linear programme)

As a cool corollary we can use this to prove Max-flow min-cut Theorem using the restatement of the problems in terms of linear programmes.