Linear Programming - Duality


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 cTx subject to Axb, x ≥ 0;
with the corresponding symmetric dual problem,
Minimize bTy subject to ATyc, y ≥ 0.

An alternative primal formulation is:

Maximize cTx subject to Axb;
with the corresponding asymmetric dual problem,
Minimize bTy subject to ATy = 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*, then the dual also has an optimal solution, y*, such that cTx*=bTy*.

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 also Farkas' lemma).

Read more about this topic:  Linear Programming

Other articles related to "duality":

Mukti - Hinduism - Vedanta
... There are three main approaches in Vedanta Shankara's strict non-duality (advaita) non-duality with qualifications (such as Ramanuja’s vishishtadvaita) duality (Madhva ...
Conic Optimization - Duality - Semidefinite Program
... minimize subject to is given by maximize subject to. ...
Correlation (projective Geometry)
... A correlation is a duality (collineation from a projective space onto its dual space, taking points to hyperplanes (and vice versa) and preserving incidence) from ... For dimensions 3 and higher, self-duality is easy to test A coordinatizing skewfield exists and self-duality fails if and only if the skewfield is not ...
Lefschetz Duality
... In mathematics, Lefschetz duality is a version of Poincaré duality in geometric topology, applying to a manifold with boundary ... There are now numerous formulations of Lefschetz duality or Poincaré-Lefschetz duality, or Alexander-Lefschetz duality ...
Duality - Other
... Duality, a large format audio mixing console by Solid State Logic Duality (CoPs) refers to the notion of a duality in a Community of Practice Dual (grammatical number) grammatical number that ...