Editing Linear programming (section)

== Complementary slackness ==
It is possible to obtain an optimal solution to the dual when only an optimal solution to the primal is known using the complementary slackness theorem. The theorem states:

Suppose that '''x'''&nbsp;=&nbsp;('''x'''<sub>1</sub>,&nbsp;'''x'''<sub>2</sub>,&nbsp;...&nbsp;,&nbsp;'''x'''<sub>''n''</sub>) is primal feasible and that '''y'''&nbsp;=&nbsp;('''y'''<sub>1</sub>,&nbsp;'''y'''<sub>2</sub>,&nbsp;...&nbsp;,&nbsp;'''y'''<sub>''m''</sub>) is dual feasible. Let ('''w'''<sub>1</sub>,&nbsp;'''w'''<sub>2</sub>,&nbsp;...,&nbsp;'''w'''<sub>''m''</sub>) denote the corresponding primal slack variables, and let ('''z'''<sub>1</sub>,&nbsp;'''z'''<sub>2</sub>,&nbsp;...&nbsp;,&nbsp;'''z'''<sub>''n''</sub>) denote the corresponding dual slack variables. Then '''x''' and '''y''' are optimal for their respective problems if and only if
* '''x'''<sub>''j''</sub> '''z'''<sub>''j''</sub>&nbsp;=&nbsp;0, for ''j''&nbsp;=&nbsp;1,&nbsp;2,&nbsp;...&nbsp;,&nbsp;''n'', and
* '''w'''<sub>''i''</sub> '''y'''<sub>''i''</sub>&nbsp;=&nbsp;0, for ''i''&nbsp;=&nbsp;1,&nbsp;2,&nbsp;...&nbsp;,&nbsp;''m''.

So if the ''i''-th slack variable of the primal is not zero, then the ''i''-th variable of the dual is equal to zero. Likewise, if the ''j''-th slack variable of the dual is not zero, then the ''j''-th variable of the primal is equal to zero.

This necessary condition for optimality conveys a fairly simple economic principle.  In standard form (when maximizing), if there is slack in a constrained primal resource (i.e., there are "leftovers"), then additional quantities of that resource must have no value.  Likewise, if there is slack in the dual (shadow) price non-negativity constraint requirement, i.e., the price is not zero, then there must be scarce supplies (no "leftovers").