Weak duality theorem (linear programme)

Statement

Lemma

Let be a feasible point for a linear programme given by , , and . Let be a feasible point for the dual linear programme then we have the following inequality

Proof

Recall that the dual linear programme was specified by , and . So we have and so we have