Hi all,

I'm trying to understand the connection between Lagrangian duality and the dual of a linear program.

Let's say we want to maximize cx, subject to Ax<=b and x >= 0

Now, the lagrangian dual would be:

g(y) = Maximize cx + y(b-Ax) to x, subject to x>=0

Or, after some rearranging:

g(y) = Maximize yb +(c-Ay)x, subject to x >= 0

Obviously, the only solution which is not infinity, is where (c-Ay)<=0

In that case, g(y) = yb, and the optimal x(y) is 0

If we then minimize this lagranguan dual, we actually get the dual of the linear program as expected:

minimize g(y)=by, subject to y>=0 and Ac>=0

However, what I don't understand is that the optimal x(y) of the lagranguan dual function g(y) is 0, because this would mean that the original linear program has its optimum at x=0, which off course is not necessarily the case.

I'm probably forgetting something, and I have the feeling that my confusion has something to do with the fact that only non-basic variables will be zero in the optimal lineair program.

Anyway who can help me out here?

Tnx!

Kind regards,

Varno