I've seen the claim (in the title) several places, but can't quite understand why it's true.

From what I understand so far, the revised simplex method solves an LP in standard computational form, $$\min c^Tx: Ax = b, x \geq 0$$

which has a corresponding dual problem $$\max b^Ty : A^Ty \leq c$$

But this isn't even an LP in standard computational form, so how do aspects of the simplex algorithm carry over? If we were to transform this dual problem into standard computational form, since $y$ is unconstrained we'd end up with $y^+, y^-$ and a bunch of slack variables, so it's quite hard to imagine how to derive the correct pivoting rules in this scenario.

Is there something I'm not getting, or is the dual revised simplex method derived in a different way?

  • $\begingroup$ Note that the simplex method can handle free variables directly. (Chapter 1 textbook algorithms are not representative of what is being used in practice, but are pedagogical tools), $\endgroup$ May 30 at 17:40

Your Answer

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

Browse other questions tagged or ask your own question.