Here's another problem involving Duality and Linear Programming:

Suppose that we have a linear program that is not in standard form. We
could produce the dual by first converting it to standard form, and
then taking the dual. It would be more convenient, however, to be able
to produce the dual directly. Explain how, given an arbitrary linear
program, we can directly take the dual of that linear program.

---

Request for Question Clarification by mathtalk-ga on 14 Nov 2002 22:55 PST

Hi, g8z:

Would you give a careful definition of what is included in "an
arbitrary linear program"?  How far from "standard" form would we
deviate?  Is it simply a matter of allowing constraints to be
inequalities of either direction?  Could there be equality
constraints?  What becomes of the requirement for nonnegativity of the
solution variables?

regards, mathtalk

---

Clarification of Question by g8z-ga on 17 Nov 2002 11:55 PST

By an arbitrary linear program I mean some function that we're trying
to maximize or minimize, and a set of constraints that is not in
standard Ax + By = C form. Deviation from standard form can be assumed
to be only so much that we easily convert to standard form by changing
a sign, e.g. <= to >= to =, adding a slack variable, multiplying by a
constant like -1 etc. As far as the nonnegativity of the solution
variables, I think that an arbitrary linear program should not assume
that we necessarily have that constraint. There should be some way to
take the dual directly without having to convert to standard form (by
adding nonnegativity constraints, etc.)

Hi, g8z-ga:

Thanks for the clarification.  I think that, with your condition:

"As far as the nonnegativity of the solution variables, I think that
an arbitrary linear program should not assume that we necessarily have
that constraint."

one can definitively show that there is no "dual" program that can be
invoked on such general linear programs.

Of course to make this precise would itself involve a careful
definition of what constitutes a "dual" program.  I suspect you are
not interested in paying even your listed price for a "negative"
result of this type, which would nonetheless require substantial
effort on my part to explain.

Let me give one nugget for your own contemplation, however.  An aspect
of a linear program in "standard" maximization form is that the origin
is always a feasible point.  The "dual" minimization problem is
therefore never unbounded, as may be seen from the positive
coefficients in the dual objective function taken together with the
nonnegativity constraints on dual variables.  One should therefore
suspect that these nonnegativity constraints play a vital role in even
so simple a connection between original and dual problems as:

unbounded original problem <==> infeasible dual problem

regards, mathtalk-ga