sci.op-research
back to index
Group: sci.op-research
From: saneman
Date: Tuesday, February 12, 2008 4:39 AM
Subject: Lagrange multipliers in IP problems
From: saneman
Date: Tuesday, February 12, 2008 4:39 AM
Subject: Lagrange multipliers in IP problems
Given the following IP problem:
(IP)
z = max cx
Dx <= d
x \in Z+
the lagrangian relaxation for u > 0 is:
(IP(u))
z(u) = max cx + u(d-Dx)
x \in Z+
In (IP(u)) 'u' is called the Lagrange multiplier or the dual variable
associated with the constraint: Dx <= d.
But how can a coefficient in the objective function be a dual variable?
Comparing (IP(u)) with the below example '4' would be the dual variable
associated with constraint 2:
max z = 2x1 + 4x2
st. 3x1 + x2 <= 1 (y1)
x1 + 7x2 <= 3 (y2)
But I don't think that makes sense. Normally y2 is said to be the dual
variable associated with constraint 2. How can '4' also be the dual
variable associated with constraint 2?
