Linear programming duality
ID: linear-programming-duality
Linear programming duality pairs the standard maximization problemwith the minimization problemThe dual variables form nonnegative combinations of primal inequalities. If and are feasible, thenThis is weak duality, giving independently checkable bounds before any algorithm reaches an optimum.
For a feasible primal with finite optimal value, strong duality for finite-dimensional linear programs ensures attained primal and dual optima with equal values. Their objective difference decomposes into nonnegative products of variables and opposite slacks, yielding complementary slackness. The worked allocation in linear programming has primal point and dual multipliers , both with value ten. Sign conventions change for minimization, equality rows and unrestricted variables; a dual formula belongs to its declared primal form.
New to topics? Read the docs here!