Practice: The Revised Simplex Method

(a) The basis matrix and its inverse. With $x_3$ in row 1 and $x_1$ in row 2, the basis columns in that order are $A_3=(1,0{)}^{\mathsf{T}}$ and $A_1=(2,2{)}^{\mathsf{T}}$:

Check: ✓ (b) Basic values. , so $x_3=4$ and $x_1=4$. The full point is $x=(4,0,4,0)$, with objective $-4(4)-3(0)=-16$. Both basic values are nonnegative, so the basic solution is feasible. Checking the constraints directly: $2(4)+0+4=12$ ✓ and $2(4)+0+0=8$ ✓. (c) Multipliers and pricing. The basic costs in basis order are $c_B=(c_3,c_1{)}^{\mathsf{T}}=(0,-4{)}^{\mathsf{T}}$, so

Pricing the nonbasic columns $x_2$ and $x_4$:

, so $x_2$ enters: each unit of $x_2$ lowers the objective by $1$ once the basic variables adjust. ${\overline{c}}_4=2$ is positive, so returning $x_4$ to the basis would raise the objective. (d) Direction, ratio test, update. For the entering column only:

Both components are strictly positive, so both rows are eligible. The ratios are $x_{B(1)}/u_1=4/2=2$ and $x_{B(2)}/u_2=4/(1/2)=8$. The minimum is $2$ at row 1, so $x_3$ leaves, $\theta =2$, and the new basis is $B^{\prime }=\{2,1\}$ with $x_2$ now in row 1. The new point: $x_2=\theta =2$, and the remaining basic variable $x_1=4-2(1/2)=3$. So $x=(3,2,0,0)$ with objective $-4(3)-3(2)=-18$, down from $-16$ by $\theta {\overline{c}}_2=2(-1)=-2$ ✓ (e) What was computed, and what a tableau would have carried. Computed this iteration: $A_B^{-1}$ (4 entries), $x_B$ (2), $p^{\mathsf{T}}$ (2), two reduced costs (2 scalars), and one direction $u$ (2). Fourteen numbers. A full tableau would have carried the whole $3\times 5$ array, all four variable columns plus the right-hand side, across two constraint rows and the objective row, and updated every entry at the pivot. A quantity never needed: the direction for column 4, $A_B^{-1}{A}_4$. The tableau maintains that column at every iteration; here $x_4$ was priced as a single scalar, found positive, and dismissed, so its direction was never formed. On a program with hundreds of columns this is where the saving lies: most columns are priced and discarded, and only the entering one has a direction computed.