applet-magic.com
Thayer Watkins
Silicon Valley
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:

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

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: