Practice: The Full Tableau Simplex Method

(a) The initial tableau. | basis | $x_1$ | $x_2$ | $x_3$ | $x_4$ | RHS |
|---|---|---|---|---|---|
| $x_3$ | 1 | 1 | 1 | 0 | 4 |
| $x_4$ | 2 | 2 | 0 | 1 | 8 |
| $\overline{c}$ | $-2$ | $-1$ | 0 | 0 | 0 | No elimination is needed because the basic variables $x_3$ and $x_4$ are slacks with cost zero: their columns are already unit vectors in the constraint rows, and their entries in the objective row are already zero. Had a basic variable carried a nonzero cost, the objective row would have to be cleared in its column before it held reduced costs. The basic solution is $x=(0,0,4,8)$ with objective $0$. (b) One iteration. Entering column. ${\overline{c}}_1=-2$ and ${\overline{c}}_2=-1$ are both negative. Taking the most negative, $x_1$ enters: each unit of $x_1$ lowers the objective by $2$ before the step length is considered. Ratio test. Column 1 holds $1$ in row 1 and $2$ in row 2, both strictly positive, so both rows are eligible. The ratios are $4/1=4$ and $8/2=4$. A tie. Either row may leave; take row 1, so $x_3$ leaves at $\theta =4$. Pivot. The pivot entry is $1$, so row 1 is unchanged. Row 2 becomes row 2 minus $2\times$ row 1:

The objective row becomes objective row plus $2\times$ row 1:

the objective being the negation of the bottom-right entry $8$. (d) The feature. The basic variable $x_4$ sits at zero, so the basic feasible solution is degenerate. The tie in the ratio test is what produced it: two basic variables reached zero at the same step, and only one could leave. What it implies: more than one basis describes this same corner, so the correspondence between bases and points is no longer one-to-one here. In a longer run it would raise the possibility of a pivot with $\theta =0$, where the basis changes but the point does not, and repeated stalling of that kind can cycle without an anti-cycling rule. What it does not imply: the answer is not wrong, the problem is not ill-posed, and the optimality verdict stands. Degeneracy is a property of this vertex, not a defect in the computation. (e) Verification against the original. Substituting $x=(4,0,0,0)$: - constraint 1: $4+0+0=4$ ✓
- constraint 2: $2(4)+2(0)+0=8$ ✓
- sign restrictions: every component is $\ge 0$ ✓
- objective: $-2(4)-1(0)=-8$, matching the value read from the tableau ✓ This check does not rely on any tableau entry being correct, which is why it is the one to run before reporting an answer.