This is a true and false question. The actual question reads:

"In solving a linear program by the simplex method, starting with a feasible tableau, a different feasible point is generated after every pivot step"

This is what I have written down as the answer so far;

The statement is true. Starting from a feasible tableau, after every pivot step we would get a better minimized/maximized (depending on what the question asks for) value of the objective function. Thus, we would get a different feasible point after every pivot until we can not pivot anymore; in which at that point the tableau is optimal.

Is my answer correct? Any help would be much appreciated!

  • $\begingroup$ Yes, the statement is true. But your subsequent explanation really does not answer why, because it does not specifically address why the pivots remain feasible as you approach the solution. What if were to develop a method that eventually converges to the optimal point, but in doing so somehow fluctuates between infeasibility and feasibility? $\endgroup$ – Michael Grant Mar 7 '15 at 20:19
  • $\begingroup$ I know I have to work on my reasoning, that is always the hardest part for me. Okay, here's what I have in mind, since we start with a feasible tableau, given that we follow the pricing rule and ratio test correctly, every pivot step will yield a different feasible point. We will not be fluctuating between infeasibility/feasibility since we would have stop pivoting when we fail the pricing rule, in which at that point we have arrived at the optimal tableau. $\endgroup$ – user200793 Mar 7 '15 at 20:38
  • $\begingroup$ I think that's closer. I would argue that, the way that the question is worded, whether or not you eventually converge is irrelevant. The only thing that matters is that when you select a new variable to enter the basis, that you don't go "too far" with it. That is, you increase it's value only as much as feasibility allows, and you adjust all other active variables to compensate. $\endgroup$ – Michael Grant Mar 7 '15 at 22:39

Your answer is only correct if the feasible region is simplicial, meaning that if you are working in dimension $d$ then every feasible tableau can be obtained once and only once as an intersection of $d$ equations. Otherwise, it is possible that when you pivot, you will get the same answer you had before, but now as an intersection of different equations, and in fact it is even possible (if you're not careful with your pivot rule) that you will get a cycle and thus not even converge to an optimal solution. This was the case for the original pivot rule proposed, and it took a bit of time to find a pivot rule that provably had no cycles.

  • $\begingroup$ This is what I understand so far;So assuming that we do the pricing and ratio test correctly in choosing which rows and columns to pivot, the statement is true. $\endgroup$ – user200793 Mar 7 '15 at 20:22
  • $\begingroup$ The way the question is worded, convergence is actually irrelevant. All that matters is that the process produces nothing but feasible points after an initial one is found. $\endgroup$ – Michael Grant Mar 7 '15 at 22:39

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.