Dual Problems in Linear Programming

Language:中文/EN

Dual Problems in Linear Programming

Every linear programming problem has a corresponding dual problem, which is also a linear programming problem. The dual of the dual problem is the original problem. The optimal solution of the original problem can be obtained from the dual problem. Sometimes, using dual theory to solve linear programming problems is simpler and provides a better understanding of the problem’s essence. Inspired by dual theory, the performance of the simplex method has been improved, and some non-simplex methods for solving linear programming problems have emerged, which will not be detailed in this article.

Dual Relationships

Consider the following form of a dual problem:

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

This is called the primal problem, and its corresponding dual form is defined as:

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

Here, λ\lambda is called the dual vector, and this type of dual is known as the symmetric form dual. For the standard form of linear programming, where the constraint is Ax=bAx=b, it is equivalent to:

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

Thus, the primal problem with equality constraints can be written as:

minimizecTxsubject to[A−A]x≥[b−b]x≥0\begin{align*} \text{minimize}\quad c^{T}x\\ \text{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 symmetric form primal problem, so the dual problem of the above is:

maximize[uT vT][b−b]subject to[uT vT][A−A]≤cTu,v≥0\begin{align*} \text{maximize}\quad [u^{T}\ v^{T}] \begin{bmatrix} b\\-b \end{bmatrix}\\ \text{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*} \text{maximize}\quad (u-v)^{T}b\\ \text{subject to}\quad (u-v)^{T}A\le c^{T}\\ u,v\ge 0 \end{align*}

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

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

Note that since u,v≥0u,v\ge 0 and λ=u−v\lambda=u-v, there is no non-negativity constraint. This relationship is called the asymmetric form dual.

Properties of Dual Problems

Here are some basic conclusions about dual problems, without proofs for now:

Weak Duality Lemma: Assume xx and λ\lambda are feasible solutions for the primal and dual problems (both symmetric and asymmetric forms), respectively, then xTx≥λTbx^{T}x\ge \lambda^{T}b, meaning “maximum value ≤\le minimum value”.

Theorem 1: Assume x0x_{0} and λ0\lambda_{0} are feasible solutions for 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 for 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 their objective functions have the same optimal value.

Theorem 3 (Complementary Slackness Condition): xx and λ\lambda are feasible solutions for the primal and dual problems, respectively. They are the optimal solutions for their respective problems if and only if:

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*}
#Mathematics