1
$\begingroup$

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"]
$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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