Practice: One Iteration of the Simplex Method

With $B=\{1,4\}$ the basic columns are $A_1=(2,1{)}^{\mathsf{T}}$ and $A_4=(0,1{)}^{\mathsf{T}}$, and $c_B=(-3,0{)}^{\mathsf{T}}$. This gives $y^{\mathsf{T}}=c_B^{\mathsf{T}}{A}_B^{-1}=(-3/2,0)$. The nonbasic reduced costs are ${\overline{c}}_2=-2-(-3/2)(1)-0(2)=-1/2$ and ${\overline{c}}_3=0-(-3/2)(1)-0(0)=3/2$. Only ${\overline{c}}_2$ is negative, so $x_2$ enters. The direction is $u=A_B^{-1}{A}_2=(1/2,3/2{)}^{\mathsf{T}}$. Both components are strictly positive, so both rows enter the ratio test: $6/(1/2)=12$ and $6/(3/2)=4$. The minimum is ${\theta }^{\ast }=4$, attained in the second row, so $x_4$ leaves. The new basis is $\{1,2\}$ with $x_2=4$, $x_1=6-4(1/2)=4$, and $x_3=x_4=0$. The objective moves from $-18$ to $-20$, a fall of ${\theta }^{\ast }|{\overline{c}}_2|=4\times 1/2=2$.

No positive components. The ratio test is taken over rows where the direction is strictly positive, because only those bound how far the step may go before a basic variable reaches zero. If no component is positive, the test is over an empty set and returns no leaving variable: moving along the direction keeps every basic variable nonnegative however far it goes. The objective falls without limit, so the program is unbounded and the method stops there rather than pivoting.

The second row should not be in the ratio test at all, because $u_2=-2$ is negative. As the entering variable rises to $\theta$, the second basic variable becomes $x_{B(2)}-\theta u_2=3-\theta (-2)=3+2\theta$, which increases. It moves away from zero, so it never limits the step and its ratio is not a step length. Only the first row qualifies, giving ${\theta }^{\ast }=8/4=2$, and the first basic variable leaves. The student's answer is also self-evidently wrong before any analysis: a negative step length would move backwards along the edge, away from the improvement the reduced cost promised.

An empty ratio test means no basic variable falls as the entering variable rises, so none of them ever reaches zero. The entering variable can increase without limit while every constraint continues to hold, which is precisely the condition for the program to be unbounded. The patch is wrong because a negative ratio is not a step length: taking it moves backwards along the edge, and the row it names was never approaching zero, so the resulting point violates feasibility while the code reports a successful pivot. The correct behavior is to terminate and report that the program is unbounded, optionally returning the ray direction. As the entering variable rises to $\theta$, the basic values $x_{B(i)}-\theta u_i$ all increase or hold steady because each $u_i\le 0$, so feasibility is preserved for every $\theta \ge 0$; the objective changes by $\theta {\overline{c}}_j=-2\theta$, which falls without bound. There is therefore no finite optimum to find.