applet-magic.com Thayer Watkins Silicon Valley & Tornado Alley USA

The Relation of Primal and Dual Problems in Linear Programming

Primal problem:

Let X be a column vector of outputs and P a row vector of the outputs'
prices. R is a column vector of the amounts of resources available and
A is matrix which gives the resources use per unit of outputs. The primal
problem is to:

maximize V = PX
subject to:
AX < R

Dual problem:

minimize W = QR
subject to:
QA ≥ P

If slack variables with zero prices are added then the primal is:

maximize V = P'X'
subject to:
A'X' = R.

The slack variables have zero prices so P' is the price vector augmented
with a zero for each slack variable.

A basis is an output vector in which the number of nonzero outputs, including
slack variables, is no more than the number of resources, dim(R).
For any basis the order of the variables can be changed so the nonzero
(or basis) variables are first and the nonbasis variables are last. Such
a reordering of the variables also reorders the elements of P' and A'.

Suppose X' is partitioned into basis variables, X_{B},
and nonbasis variables, X_{NB}; i.e.,

| X_{B} |

X'

=

| |

| X_{NB} |

Since the price vector is a row vector it is partitioned as
P' = [P_{B} P_{NB}]. Likewise the
coefficients matrix A can be partitioned as

A = [A_{B,B} A_{B,NB}].

Then the objective function can be represented as

V=P_{B}X_{B} + P_{NB}X_{NB}

and the constraints as

A_{B,B}X_{B} + A_{B,NB}X_{NB} = R.

If the X_{NB} variables are set to any feasible values
then X_{B} variables are determined as

X_{B} = A_{B,B}^{-1}(R - A_{B,NB}X_{NB})

The value of the output is then

V = P_{B}(A_{B,B}^{-1}(R - A_{B,NB}X_{NB})) + P_{NB}X_{NB} + P_{B}A_{B,B}^{-1}R+ (P_{NB}-P_{B}A_{B,B}^{-1}A_{B,NB})X_{NB}

When X_{NB} = 0 then V = P_{B}A_{B,B}^{-1}R.
For an optimum it must be that the marginal change
for any element in X_{NB} is nonpositive; i.e.,

(P_{NB}-P_{B}A_{B,B}^{-1}A_{B,NB}) <0,
where 0 is a row vector with all components equal to zero.

This means that

P_{NB}< P_{B}A_{B,B}^{-1}A_{B,NB})

The marginal values of the resources MRV are given by

MRV = (P_{B}A_{B,B}^{-1}).

It then follows that

(P_{B}A_{B,B}^{-1})R = V.

Furthermore, the cost of production based upon those
marginal values for the elements of X_{B} is

(P_{B}A_{B,B}^{-1})A_{B,B} = P_{B}.

For the nonbasic elements the costs of production are:

(P_{B}A_{B,B}^{-1})A_{B,NB} = P_{B}(A_{B,B}^{-1}A_{B,NB}).
But P_{B}(A_{B,B}^{-1}A_{B,NB}) > P_{NB}.