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, XB, and nonbasis variables, XNB; i.e.,

  | XB |
X' = |        |
  | XNB |

Since the price vector is a row vector it is partitioned as P' = [PB PNB]. Likewise the coefficients matrix A can be partitioned as


A = [AB,B AB,NB].
 

Then the objective function can be represented as


V=PBXB + PNBXNB
 

and the constraints as


AB,BXB + AB,NBXNB = R.
 

If the XNB variables are set to any feasible values then XB variables are determined as


XB = AB,B-1(R - AB,NBXNB)
 

The value of the output is then


V = PB(AB,B-1(R - AB,NBXNB)) + PNBXNB
+ PBAB,B-1R+ (PNB-PBAB,B-1AB,NB)XNB
 

When XNB = 0 then V = PBAB,B-1R. For an optimum it must be that the marginal change for any element in XNB is nonpositive; i.e.,


(PNB-PBAB,B-1AB,NB) < 0,
where 0 is a row vector with all
components equal to zero.
 

This means that


PNB < PBAB,B-1AB,NB)
 

The marginal values of the resources MRV are given by


MRV = (PBAB,B-1).
 

It then follows that


(PBAB,B-1)R = V.
 

Furthermore, the cost of production based upon those marginal values for the elements of XB is


(PBAB,B-1)AB,B = PB.
 

For the nonbasic elements the costs of production are:


(PBAB,B-1)AB,NB = PB(AB,B-1AB,NB).
But
PB(AB,B-1AB,NB) > PNB.
 

HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins