Here's a problem from a college course on Algorithms. The topic under
study is Linear Programming and in particular, the area of Duality.

Formulate the dual of the linear program:
maximize: 18 x1 + 12.5 x2
subject to these constraints: 
x1 + x2 <= 20, x1 <= 12, x2 <= 16, x1 >= 0, x2 >= 0

Hi, g8z:

Thanks for the interesting question.

First the short answer (to this specific problem), and then some words
about how to find the answer (in the general case).

The "original" linear program here is of the form:

MAX: 18 x1 + 12.5 x2

s.t.    x1 +      x2 <= 20
        x1           <= 12
                  x2 <= 16

and     x1, x2 >= 0

Its dual linear program is then of the form:

MIN: 20 y1 + 12 y2 + 16 y3 

s.t.    y1 +    y2         >= 18
        y1         +    y3 >= 12.5

and     y1, y2, y3 >= 0

More generally, if you have a "maximization" problem in standard
linear program form, like this:

MAX:  b*x 

s.t. A x <= c

and x >= 0

where now x is a "vector" of nonnegative values and b*x represents a
dot product defining the objective function, then there is a
well-defined dual "minimization" problem:

MIN:  c*y

s.t. A' y >= 0

and y >= 0

where A' denotes the matrix transpose of A, and the new vector of
nonnegative unknowns y is the right size to make the expressions above
sensible.

That is, your original problem had three constraints in two unknowns,
so its dual winds up with two constraints in three unknowns.  Much
more can be said about the relationships between the solutions (or
infeasibility) of one problem and the other, but your question doesn't
really reach into that material.

Actually either problem may be considered the "original" and the other
its dual.  For a convenient Web site to consult these definitions,
see:

http://www.nist.gov/dads/HTML/linearprogrm.html

http://www.nist.gov/dads/HTML/duallinear.html

regards, mathtalk-ga

Perfect answer. This is exactly what I was looking for. Thanks, mathtalk. :)