Linear Prograaming Problems and Their Duals
Below are two maximisation problems.Minimise
\[O_1=45I+50L+60A\]
subject to\[I+2L+4A \geq 6\]
\[3I+3L+2A \geq 3\]
\[I+3L+A \geq 2\]
\[I, \: L, \: A \geq 0\]
The solution which maximises
\[O_1\]
is \[I=0, \: L=1/5, \: A=7/5\]
and returns \[O_1=94\]
Maximise
\[O_2=6B+3E+2M\]
subject to\[B+3E+M \leq 45\]
\[2B+3E+3M \leq 50\]
\[4B+2E+M \geq 60\]
\[B, \: E, \: M \geq 0\]
The solution which maximises
\[O_2\]
is \[B=13, \: E=0, \: M=8\]
and returns \[O_2=94\]
These two problems are called duals.
Write the first problem as minimise
\[O_1=\begin{pmatrix}45\\50\\60\end{pmatrix} \cdot \begin{pmatrix}I\\L\\A\end{pmatrix}\]
subject to \[\left( \begin{array}{ccc} 1 & 2 & 4 \\ 3 & 3 & 2 \\ 1 & 3 & 1 \end{array} \right) \begin{pmatrix}I\\L\\A\end{pmatrix} \geq \begin{pmatrix}6\\3\\2\end{pmatrix}\]
\[I, \: L, \: A \geq 0\]
The dual is:
Write the second problem as maximise
\[O_2=\begin{pmatrix}6\\3\\2\end{pmatrix} \cdot \begin{pmatrix}B\\E\\M\end{pmatrix}\]
subject to \[\left( \begin{array}{ccc} 1 & 3 & 1 \\ 2 & 3 & 3 \\ 4 & 2 & 1 \end{array} \right) \begin{pmatrix}B\\E\\M\end{pmatrix} \leq \begin{pmatrix}45\\50\\60\end{pmatrix}\]
\[B, \: E, \: M \geq 0\]
In general the dual of the minimisation problem
Minimise
\[O_1= \mathbf{b} \cdot \mathbf{x}\]
subject to \[A \mathbf{x} \geq \mathbf{c}\]
where
\[\mathbf{x}, \mathbf{b}, \: \mathbf{c}\]
are n - tuples and \[A\]
is an \[n \times n\]
matrix, and \[x_i \geq 0, \: i=1,2,...,n\]
is the problem
Maximise
\[O_2= \mathbf{c} \cdot \mathbf{y}\]
subject to \[A^T \mathbf{y} \geq \mathbf{b}\]
where
\[\mathbf{y}, \mathbf{b}, \: \mathbf{c}\]
are n - tuples and \[A\]
is the \[n \times n\]
matrix above, and \[y_i \geq 0, \: i=1,2,...,n\]
According to The Fundamental Theorem of Linear Programming, if a linear programming problem and its dual have a feasible point,, then they have the same optimal point. If one has no point, then neither does the other.