**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
**c**T**x**subject to*A***x**≤**b**,**x**≥ 0;- with the corresponding
**symmetric**dual problem,

- with the corresponding
- Minimize
**b**T**y**subject to*A*T**y**≥**c**,**y**≥ 0.

An alternative primal formulation is:

- Maximize
**c**T**x**subject to*A***x**≤**b**;- with the corresponding
**asymmetric**dual problem,

- with the corresponding
- Minimize
**b**T**y**subject to*A*T**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***, then the dual also has an optimal solution, **y***, such that **c**T**x***=**b**T**y***.

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":

... There are three main approaches in Vedanta Shankara's strict non-

**duality**(advaita) non-

**duality**with qualifications (such as Ramanuja’s vishishtadvaita)

**duality**(Madhva ...

**Duality**- Semidefinite Program

... minimize subject to is given by maximize subject to. ...

... 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 ...

**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 ...