= Dual variable
{title2=$y_i$}
A <dual variable> is a multiplier associated with a primal constraint in a <dual linear program>. In a minimization <linear program> with equality constraints $Ax=b$ and nonnegative primal variables, the <Lagrangian> $c^Tx+y^T(b-Ax)$ yields the dual objective $b^Ty$ and inequalities $A^Ty\le c$; the equality-constraint multipliers $y$ are unrestricted in sign. For a <transportation problem>, row and column <dual variables> give potentials $u_i,v_j$ satisfying $u_i+v_j\le c_{ij}$. <Complementary slackness> makes occupied routes attain equality.
Back to article page
