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

\[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.