Paul
Posts:
162
Registered:
12/7/09


Re: nondiscrete knapsack
Posted:
Oct 28, 2010 6:35 PM


On Oct 28, 5:29 pm, "analys...@hotmail.com" <analys...@hotmail.com> wrote:
> > What if we made the equality the main constraint and put the > inequality in the Lagrangean?
No joy. Your only constraint then (absent upper bounds on x and y) is x + y = 5 (plus the sign restrictions), so you'll get either (5, 0) or (0, 5) as the solution, depending on the multiplier you use in the relaxation. It turns out the ideal penalty multiplier is 1 (the dual value of the capacity constraint in the original LP), in which case (5, 0) and (0, 5) are both optimal in the relaxed problem  as is (2, 3), thus satisfying the Ghost of Lagrange, but it's not an extreme point in the relaxed problem, so you have no obvious way to find it.
/Paul

