Question

Q1. (Basic Concept of the Simplex Procedure) (3 marks) 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

Solution:Q1:

(a) We know that pivot operation is simply the Gaussian elimination or elementary row operation(ERO). The given problem will not be changed if we multiply any equation by a nonzero constant, or add or subtract a multiple of any equation to or from any other equation. We divide the entire pivot row by the value of the pivot element.The new form of the pivot row is always a multiple of the current pivot row, so a multiple of this new form of the pivot row can be added to or subtracted from the other rows.

Therefore, adding a multiple of the reduced cost row (row 0) to the row in which the nonzero elements exists induce no wrong solution.

(b) If we subtract or add multiples of a row other than the pivot row from or to a row, the columns for the other basic variables can become inaccurate result or a wrong result.

Therefore adding a multiple of a constraint row other than the row in which leaving-variable row to the nonzero elements exists induce a wrong solution.

(c) Yes, it is always most efficient to add a multiple of the leaving-variable row to the row in which the nonzero elements exists.