Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have some LP problem and I'm willing to solve it (this is an exercise from some optimization-related book).

Now, Mathematica tells me that the problem is unbounded and I want to make a generic proof of that.

What would be the easiest way to prove that the selected linear optimization problem is unbounded (and obviously, doesn't have an exact solution?).

LinearProgramming[

{1, 2, 1, -1, 0},

{{0, 10, 1, 2, 3}, {-1, 5, 1, 1, 1}, {2, -1, 1, -3, 0}}, 

{{25, 0}, {10, 0}, {6, -1}}, 

{{-Infinity, Infinity}, {0, Infinity}, {0, Infinity}, 
 {-Infinity, Infinity}, {-Infinity, Infinity}}, 

 Method -> "RevisedSimplex"]
share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

Use duality. If you can prove that the dual problem is infeasible, then the original problem must either be infeasible or unbounded. Then show that the original problem is feasible (i.e., by finding at least one point in the feasible region).

Detecting infeasibility for your dual should be straightforward. You will have three variables, three equality constraints, and two inequality constraints in the dual. Three equations with three dual variables will (in this case) produce a unique solution. Then you just need to verify that this unique solution does not satisfy the two remaining inequality constraints.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.