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.

Add comment

Security code
Refresh