Duality in Linear Programming

Every linear programming problem has a corresponding dual problem. The dual is itself a linear program, and the dual of the dual is the original problem. The optimal solution of the primal can be obtained from the dual; sometimes solving a linear program via duality theory is simpler and reveals the essence of the problem more clearly. Inspired by duality theory, the performance of the simplex method has been improved, and some non-simplex methods for solving linear programs have emerged, which this article does not cover in detail.

The Dual Relationship

Consider a dual problem of the following form

minimizecTxsubject toAx≥bA≥0\begin{align*} minimize\quad c^{T}x \\ subject\ to\quad Ax\ge b\\ A\ge0 \end{align*}

We call this the primal problem, and its corresponding dual form is defined as

maximizeλTbsubject toλTA≤cTλ≥0\begin{align*} maximize\quad \lambda^{T}b \\ subject\ to\quad \lambda^{T} A\le c^{T}\\ \lambda \ge0 \end{align*}

where λ\lambda is called the dual vector, and this kind of duality is called the symmetric form of duality. In addition, for the standard form of a linear program, whose constraint is Ax=bAx=b, this is equivalent to

Ax≥b−Ax≥−b\begin{align*} Ax\ge b\\ -Ax\ge -b \end{align*}

Therefore, a primal problem containing equality constraints can be written as

minimizecTxsubject to[A−A]x≥[b−b]x≥0\begin{align*} minimize\quad c^{T}x\\ subject\ to\quad \begin{bmatrix} A\\-A \end{bmatrix}x\ge \begin{bmatrix} b\\-b \end{bmatrix}\\ x\ge 0 \end{align*}

This has the same structure as the primal problem in symmetric form, so the dual of the above problem is

maximize[uT vT][b−b]subject to[uT vT][A−A]≤cTu,v≥0\begin{align*} maximize\quad [u^{T}\ v^{T}] \begin{bmatrix} b\\-b \end{bmatrix}\\ subject\ to\quad [u^{T}\ v^{T}] \begin{bmatrix} A\\-A \end{bmatrix}\le c^{T}\\ u,v\ge 0 \end{align*}

The dual problem can be rearranged as

maximize(u−v)Tbsubject to(u−v)TA≤cTu,v≥0\begin{align*} maximize\quad (u-v)^{T}b\\ subject\ to\quad (u-v)^{T}A\le c^{T}\\ u,v\ge 0 \end{align*}

Letting λ=u−v\lambda=u-v, the above problem then becomes

maximizeλTbsubject toλTA≤cT\begin{align*} maximize\quad \lambda^{T}b\\ subject\ to\quad \lambda^{T}A\le c^{T} \end{align*}

Note that here, since u,v≥0,λ=u−vu,v\ge 0,\lambda=u-v, the nonnegativity constraint is gone. This relationship is called the asymmetric form of duality.

Properties of the Dual Problem

Here we present some basic conclusions about the dual problem, without proof for now. Weak Duality Lemma: Suppose xx and λ\lambda are feasible solutions of the primal and dual problems of a linear program (in symmetric and asymmetric forms), respectively. Then cTx≥λTbc^{T}x\ge \lambda^{T}b, that is, “maximum value ≤\le minimum value.”

Theorem 1: Suppose x0x_{0} and λ0\lambda_{0} are feasible solutions of the primal and dual problems, respectively. If cTx0=λ0Tbc^{T}x_{0}=\lambda_{0}^{T}b, then x0x_{0} and λ0\lambda_{0} are the optimal solutions of their respective problems.

Theorem 2 (Duality Theorem): If the primal problem has an optimal solution, then its dual problem also has an optimal solution, and the optimal values of their objective functions are equal.

Theorem 3 (Complementary Slackness Conditions): Let xx and λ\lambda be feasible solutions of the primal and dual problems, respectively. Then a necessary and sufficient condition for them to be the optimal solutions of their respective problems is

1.(cT−λTA)x=02.λT(Ax−b)=0\begin{align*} 1.\quad(c^{T}-\lambda^{T}A)x=0\\ 2.\quad\lambda^{T}(Ax-b)=0 \end{align*}
  • Technology