Editing Linear programming (section)

== Duality ==
{{Main|Dual linear program}}
Every linear programming problem, referred to as a ''primal'' problem, can be converted into a [[dual problem]], which provides an upper bound to the optimal value of the primal problem. In matrix form, we can express the ''primal'' problem as:

: Maximize '''c'''<sup>T</sup>'''x'''  subject to ''A'''''x''' ≤ '''b''', '''x''' ≥ 0;
:: with the corresponding '''symmetric''' dual problem,
: Minimize  '''b'''<sup>T</sup>'''y'''  subject to ''A''<sup>T</sup>'''y''' ≥ '''c''', '''y''' ≥ 0.

An alternative primal formulation is:

: Maximize '''c'''<sup>T</sup>'''x''' subject to ''A'''''x''' ≤ '''b''';
:: with the corresponding '''asymmetric''' dual problem,
: Minimize  '''b'''<sup>T</sup>'''y''' subject to ''A''<sup>T</sup>'''y''' = '''c''', '''y''' ≥ 0.

There are two ideas fundamental to duality theory. One is the fact that (for the symmetric dual) the dual of a dual linear program is the original primal linear program. Additionally, every feasible solution for a linear program gives a bound on the optimal value of the objective function of its dual.  The [[weak duality]] theorem states that the objective function value of the dual at any feasible solution is always greater than or equal to the objective function value of the primal at any feasible solution. The [[strong duality]] theorem states that if the primal has an optimal solution, '''x'''<sup>*</sup>, then the dual also has an optimal solution, '''y'''<sup>*</sup>, and '''c'''<sup>T</sup>'''x'''<sup>*</sup>='''b'''<sup>T</sup>'''y'''<sup>*</sup>.

A linear program can also be unbounded or infeasible. Duality theory tells us that if the primal is unbounded then the dual is infeasible by the weak duality theorem. Likewise, if the dual is unbounded, then the primal must be infeasible. However, it is possible for both the dual and the primal to be infeasible.  See [[dual linear program]] for details and several more examples.