Linear Programming: What is the rationale behind the Gauss Jordan Row operations we do after determining the leaving and entering variables?

Question

Let's say this was the starting iteration table of the simplex method:

After identifying the entering and leaving variables, we do these Gauss Jordan row operations wherein,

Why do we do this?

Answer 1

Overview

I'm going to address the question why the solutions keep the same by these pivot row operations, before addressing the question why we want to do these operations.

Why can we do this?

Note that the problem is unchanged after usual row operations: the ones that college students do to systems of linear equations.

$\require{action}$ \begin{array}{cccc} \hline \texttip{\text{pivot elt}}{selected first} & \texttip{\text{pvt relt } 1}{pivot row element 1} & \cdots & \texttip{\text{pvt relt } n}{pivot row element n} \\ \hline \texttip{\text{pvt celt } 1}{pivot column element 1} & \ddots & \vdots & \vdots \\ \hline \texttip{\text{pvt celt } 2}{pivot column element 2} & \cdots & \vdots & \vdots \\ \hline \vdots & \cdots & \vdots & \vdots \\ \hline \texttip{\text{pvt celt } n}{pivot column element n} & \cdots & \vdots & \vdots \\ \hline \end{array}

In the simplex algorithm, one always choose a positive pivot element so that the solution at the RHS is always nonnegative.

1. In step (1b), this is just division by a positive scalar $a_{11}$ of a linear equation. This won't change the constraint at all. \begin{array}{cccc} \hline \texttip{1}{pivot element} & \text{new pvt relt } 1 & \cdots & \text{new pvt relt } n \\ \hline \text{pvt celt }1 & \ddots & \vdots & \vdots \\ \hline \text{pvt celt }2 & \ddots & \vdots & \vdots \\ \hline \vdots & \cdots & \vdots & \vdots \\ \hline \text{pvt celt }m & \ddots & \vdots & \vdots \\ \hline \end{array}
2. In step (2), we subtract each other non-pivot row by the current pivot row multiplied by a suitable constant. The equation $$\text{New row} = \text{Current row} (\times 1) - \text{pivot column element} \times \text{new pivot row} \tag{given}\label1$$ is actually the pivotal condensation.

Therefore, such elementary row operations don't alter the solutions of the linear equations.

Why do we want this?

In your table, observe that $z = 5x_1 + 4x_2$. Even thought we can't write $\dfrac{\partial z}{\partial x_1} = 5$ (since each feasible solution is an extreme point/corner of the convex feasible region), but you know that at a certain neighbourhood of the current basic solution, the rate of increase of $z$ with respect to $x_1$ is $5$---that's the maximal rate of increase, that's why we introduce a new decision variable into the basis while kicking out one at a time.