Question

This question is about the “Pivoting” step in the Simplex algorithm procedure. The step updates the Simplex tableau by pivoting on the intersection of the entering-variable column and the leaving-variable row, i.e. perform EROs on the tableau to get a 1 in the pivot position, and 0s above and below it. We know that one ERO type is “Add a multiple of one row to another row.” Consider that we are trying to make a nonzero element above or below the pivot position become 0. Please provide detailed explanations for the following questions. (a) Will adding a multiple of the reduced cost row (row 0) to the row in which the nonzero element exists induce a wrong solution? (b) Will adding a multiple of a constraint row other than the leaving-variable row to the row in which the nonzero element exists induce a wrong solution? (c) Is it always most efficient to add a multiple of the leaving-variable row to the row in which the nonzero element exists?

Answer 1

A) adding a multiple of reduced cost row to the row in which non zero element exists doesn't induce a wrong solution but it may give you another solution. As in the simple algorithm , you may find different optimal solution. It is because of the geometry of simplex, every optimal solution occurs at the corner point of simplex.  

B) I don't think so that it will induce a wrong solution . It is because if you look at the corresponding system of equations, you are just manipulating them, adding , multiplying or subtracting by a multiple of equation respectively .