## Fundamental Theory of Linear Programming Example

Consider the linear programming problem:
Maximise
$O_1=x+y$
subject to
$x-y \leq 1$

$x+y \geq 4$

$x, \: y \geq 0$

To convert this problem into canonical form write the second inequality (constraint) as
$-x-y \leq -4$
. We have
Maximise
$O_1=x+y$
subject to
$x-y \leq 1$

$-x-y \leq -4$

$x, \: y \geq 0$

The dual to this problem is the problem
Minimise
$O_2=u-4v$
subject to
$u-v \geq 1$

$-u-v \geq 1$

$u, \: v \geq 0$

For non negative
$u, \: v$
the constraint
$-u-v \geq 1$
can never be satisfied, hence the minimisation problem has no feasible solution, so according the the Fundamental Theory of Linear Programming (if an optimal solution exists for a linear programming problem, the an optimal solution exists for the dual, with both objective functions taking the same value), no solution exists for the original problem.