0

When reducing rows in linear programming you pick the one with the lowest test ratio in a certain column, why is that? What does the test ratio mean?

Mike Flynn
  • 1,917
  • When you start proceeding along that face, the constraint corresponding to the test ratio is the first one to be violated. – Inquest Aug 06 '13 at 20:23

1 Answers1

0

The simplex algorithm often used in linear programming consists of walking along the edges of a convex polyhedron to find the vertex that maximizes the target function. Each intermediate step corresponds to a vertex of the polyhedron, i.e. a point where as many of the inequalities as possible are "sharp" (the point is on as many faces as possible). To move to the next vertex, we "leave" one face and move along an edge (i.e. with all other inequalities remaining sharp) until we hit another face for the first time. So the decision consists of

  1. Which face should we leave in order to increase the target function? (If there is no such face, we are done) This is why a column with positive coefficient in the target function is picked
  2. To which face should we move? Of course the (infinitely prolonged) edge intersects almost all face (hyperplanes) of the polyhedron, but most intersections are outside the polyhedron. Only the first intersection in positive directon is the one that delimites the polyhedron. That's why we need to find the row that leads to the smallest movement in positive direction. This is controlled exactly by the test ratio
Hagen von Eitzen
  • 374,180