According to the Wikipedia article, the Simplex algorithm depends on constraining all the unknowns to be >= 0. I have a problem where one of my variables is highly likely to be negative in many cases. How can I adapt the problem so I can use Simplex?

EDIT: example: say I have x, y and z and I want to find values (both >= 0) for x and y which minimize z, where I also have the constraints:

1.4x -y +z >= 0
-x +2.2y +z >= 0
  • $\begingroup$ Multiply your variable by $-1$. Make it positive. Maybe you should give us the whole problem, because that may not be the best, or even proper, way to deal with the issue. $\endgroup$ – Raskolnikov Mar 3 '11 at 20:34
  • $\begingroup$ But what if it's positive to begin with? $\endgroup$ – user7755 Mar 3 '11 at 20:35
  • 1
    $\begingroup$ Can you give the whole problem, please? It's hard to say anything definite otherwise. $\endgroup$ – Raskolnikov Mar 3 '11 at 20:36
  • $\begingroup$ I don't see the problem. I mean, if you think there might be a negative solution, switch the sign of one variable everywhere in the problem. Solve it (maximize for z of course) and switch back. $\endgroup$ – Raskolnikov Mar 3 '11 at 20:53

The standard trick is to replace $z$ with $z^+ - z^-$ throughout.

  • $\begingroup$ ...with $z^+$ and $z^-$ both taken to be nonnegative. $\endgroup$ – Mike Spivey Mar 4 '11 at 6:36

Your Answer

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