How to Get the Dual Problem of a Linear Programming Problem

Posted on 2024-04-12 Edited on 2024-04-13 Views: Word count in article: 1.1k Reading time ≈ 4 mins.

Primal Problem

Max:2x_1+x_2+6x_3-x_4\\ s.t.\begin{cases} x_1+2x_2+x_3-x_4<=10\\ x_1+2x_3+x_4>=5\\ x_2+x_3+2x_4=20\\ x_1>=0,x_2<=0,x_3<=0 \end{cases}

The general vector form of the primal problem can be expressed as:

Max:z=CX\\ s.t.\begin{cases}AX<=B\\ X>=0 \end{cases}

We can represent the coefficients of the original problem as matrices:

$A=\begin{bmatrix}1&2&1&-1\\1&0&2&1\\0&1&1&2\end{bmatrix}$ $~~~~$ $B=\begin{bmatrix}10\\5\\20\end{bmatrix}$ $~~~~$ $C=\begin{bmatrix}2&1&6&-1\end{bmatrix}$

Dual Problem

The general vector form of the dual problem can be expressed as:

Min:z_d=B^TY\\ s.t.\begin{cases}A^TY>=C^T\\ Y>=0 \end{cases}

Then, we can get the matrices of coefficients of the dual problem:

$A^T=\begin{bmatrix}1&1&0\\2&0&1\\1&2&1\\-1&1&2\end{bmatrix}$ $~~~~$ $C^T=\begin{bmatrix}2\\1\\6\\-1\end{bmatrix}$ $~~~~$ $B^T=\begin{bmatrix}10&5&20\end{bmatrix}$

Step 1: Get the basic framework

Ignoring the symbol of the constraints for a moment (Replace with $?$ ), we can get the basic framework of the dual problem:

Min:\textcolor{Purple}{10}y_1+\textcolor{Purple} {5}y_2+\textcolor{Purple}{20}y_3\\ s.t.\begin{cases} \textcolor{blue}{1}y_1+\textcolor{blue}{1}y_2+\textcolor{blue}{0}y_3\quad\textcolor{red}{(?)}\quad\textcolor{OrangeRed}{2}\\ \textcolor{blue}{2}y_1+\textcolor{blue}{0}y_2+\textcolor{blue}{1}y_3\quad\textcolor{red}{(?)}\quad\textcolor{OrangeRed}{1}\\ \textcolor{blue}{1}y_1+\textcolor{blue}{2}y_2+\textcolor{blue}{1}y_3\quad\textcolor{red}{(?)}\quad\textcolor{OrangeRed}{6}\\ \textcolor{blue}{-1}y_1+\textcolor{blue}{1}y_2+\textcolor{blue}{2}y_3\quad\textcolor{red}{(?)}\quad\textcolor{OrangeRed}{-1}\\ \end{cases}

Note:

One constraint of the primal problem corresponds to a dual variable.
The dual variable is multiplied by the right side ( $B$ ) of the primal problem to obtain the objective function of the dual problem.
The coefficients of the objective function of the primal problem ( $C$ ) is on the right side of the constraints of the dual problem.

Step 2: Determines the symbol of constraints

Primal problem		Dual problem
Max		Min
Variables	>=	>=	Contraints
	<=	<=
	unconstrained	=

If the primal problem is a maximization problem, the $i$ th constraint sign of the dual problem is the same as the sign of the $i$ th variable of the primal problem.

Primal problem		Dual problem
Min		Max
Variables	>=	<=	Contraints
	<=	>=
	unconstrained	=

If the primal problem is a minimization problem, the $i$ th constraint sign of the dual problem is the opposite of the sign of the $i$ th variable of the primal problem.
If a variable is unconstrained, its corresponding constraint to the dual problem is given an equal sign.

The primal problem in this example is a maximization problem, so we can get:

Primal\quad problem:\quad Dual\quad problem\\ x_1>=0:\quad\textcolor{blue}{1}y_1+\textcolor{blue}{1}y_2+\textcolor{blue}{0}y_3\quad\textcolor{red}{>=}\quad\textcolor{Orange}{2}\\ x_2<=0:\quad\textcolor{blue}{2}y_1+\textcolor{blue}{0}y_2+\textcolor{blue}{1}y_3\quad\textcolor{red}{<=}\quad\textcolor{Orange}{1}\\ x_3<=0:\quad\textcolor{blue}{1}y_1+\textcolor{blue}{2}y_2+\textcolor{blue}{1}y_3\quad\textcolor{red}{<=}\quad\textcolor{Orange}{6}\\ x_4(unconstrained):\quad\textcolor{blue}{-1}y_1+\textcolor{blue}{1}y_2+\textcolor{blue}{2}y_3\quad\textcolor{red}{=}\quad\textcolor{Orange}{-1}\\

Step 3: Determine the symbol of decision variables

Primal problem		Dual problem
Max		Min
Contraints	>=	<=	Variables
	<=	>=
	=	unconstrained

If the primal problem is a maximization problem, the variable sign of the dual problem is the opposite of the sign of the constraint of the primal problem.

Primal problem		Dual problem
Min		Max
Contraints	>=	>=	Variables
	<=	<=
	=	unconstrained

If the primal problem is a minimization problem, the variable sign of the dual problem is the same as that of the constraint in the primal problem.