Optimality condition in Linear Programming

Consider a Linear program in the standard form: ” Minimize over subject to and ” where the matrix has rank and are vectors. Let be a Basic Feasible Solution. Then is optimal if and only if for some Basis of :

Additionally is then the optimal solution to the Dual problem in linear programs: ” Maximize over subject to ”

We will only prove the following lemma (which gets us pretty close to the above statement)

Lemma

Consider a Linear program: ” Minimize over subject to and ” where , and . Suppose is a Basic Feasible Solution with Support Then is optimal if and only if

for some satisfying where is submatrix of obtained by taking -th columns of for all

Moreover, is then feasible and optimal solution for the Dual problem in linear programs: ” Maximize over subject to “

Proof

Start from the Dual problem in linear programs: ” Maximize over subject to ” Note that a feasible is primal optimal and feasible is dual optimal if and only if Complimentary slackness holds (due to Dual problem in linear programs > Lemma) i.e. i.e. (due to Support of being )

Suppose is primal optimal. By Strong duality in linear programs, there is some feasible that is dual optimal. By the observation above, this means

By feasibility of :

Suppose some satisfying also satisfies:

Then is feasible, and so Complimentary slackness holds. This happens if and only if is primal optimal and is dual optimal.