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 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.