The primal formulation is:
$ \max < \mathbf c, \mathbf x > $
s.t.
$\left\{ \begin{array}{l}
< \mathbf a_1, \mathbf x > = b_1\\
< \mathbf a_2, \mathbf x > \leq b_2\\
x_1 \geq 0\\
\end{array} \right. $
The dual formulation is expressed as:
$ \min (b_1y_1 + b_2y_2) $
s.t.
$\left\{ \begin{array}{l}
a_{11}y_1 + a_{21}y_2 \geq c_1\\
a_{12}y_1 + a_{22}y_2 \leq c_2\\
y_1, y_2 \geq 0\\
\end{array} \right. $
Let $\mathbf c = (5,-6) $, $\mathbf a_1 = (2,-1) $, $\mathbf a_2 = (1,3) $, $\mathbf b = (1,9) $, $\mathbf x = (x_1,x_2) $
Solution of the primal is $\mathbf x^* = (x_1^*,x_2^*) = (0,-1) $ with objective function equal to 6.
Solution of the dual is $\mathbf y^* = (y_1^*,y_2^*) = (6,0) $ with objective function equal to 6.
HOW TO GET THE DUAL FORMULATION
The dual formulation of the primal problem can be derived by writing the Lagrangian function $L$ of the primal problem and connecting heuristically such function to minimax theorem of John von Neumann. The Lagrangian function to be considered is:
$ L(\mathbf x,y_1,y_2) = < \mathbf c, \mathbf x > + < y_1, b_1 – \mathbf a^t_1 \cdot \mathbf x > + < y_2, b_2 – \mathbf a^t_2 \cdot \mathbf x > $
Minimax theorem says that:
$ \min_{y_1,y_2} \max_\mathbf x L(\mathbf x,y_1,y_2) = \max_\mathbf x \min_{y_1,y_2} L(\mathbf x,y_1,y_2)$
Taking advantage of the linearity of the dot product and putting in evidence variable $ \mathbf x $, we get
$ L = < \mathbf c, \mathbf x > + < y_1, b_1> - < y_1, \mathbf a^t_1 \cdot \mathbf x > + < y_2, b_2> - < y_2, \mathbf a^t_2 \cdot \mathbf x > = y_1 b_1 + \sum_{i=1}^2 c_i x_i – y_1 (\sum_{i=1}^2 a_{1i} x_i) + y_2 b_2 - y_2 (\sum_{i=1}^2 a_{2i} x_i) $
Maximizing $ L(\mathbf x,y_1,y_2) $ with respect to variable $ \mathbf x $ where $x1 \ge 0$ and $x_2 \in R$:
$ \max_\mathbf x L(\mathbf x,y_1,y_2) = < y_1, b_1> + < y_2, b_2> + \max_\mathbf x [\sum_{i=1}^2 (c_i-y_1 a_{1i} - y_2 a_{2i} )x_i] $
The maximum of $[\sum_{i=1}^2 (c_i-y_1 a_{1i} - y_2 a_{2i} )x_i] $ is finite and equal to 0 if and only if
$\left\{ \begin{array}{l}
c_1-y_1 a_{11} - y_2 a_{21} \leq0\\
c_2-y_1 a_{12} - y_2 a_{22} \geq0\\
y_1, y_2 \geq 0\\
\end{array} \right. $
As a consequnce the dual formulation is expressed as:
$ \min (b_1y_1 + b_2y_2) $
s.t.
$\left\{ \begin{array}{l}
a_{11}y_1 + a_{21}y_2 \geq c_1\\
a_{12}y_1 + a_{22}y_2 \leq c_2\\
y_1, y_2 \geq 0\\
\end{array} \right. $