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.