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