Exercises — Linear programming — simplex method (intro)

(a) The picks are $x_1,x_2$ → 2 decision variables. (b) One slack per $\le$ constraint (not counting $x\ge 0$, which is handled by keeping variables non-negative). Two constraints → 2 slacks $s_1,s_2$. (c) Total = decisions + slacks $=2+2=4$.

Non-basic $x_1=x_2=0$, so the corner is the ==origin $(0,0)$==. Then $z=5(0)+4(0)=0$. The slacks $s_1=24,s_2=6$ just say "at the origin all the resource is still unused" — both constraints are slack, neither is tight.

Slacks: $x_1+s_1=4,2x_2+s_2=12,3x_1+2x_2+s_3=18$. The $z$-row is $z-3x_1-5x_2=0$, i.e. coefficients $(-3,-5)$. Enter: most negative is $-5$ under $x_2$ → $x_2$ enters (raising $x_2$ raises $z$ fastest per unit). Ratio test — only rows where the $x_2$-column entry is positive:

• Row $s_1$: $x_2$-entry is $0$ → skip (a $0$ never bounds the increase).
• Row $s_2$: $12/2=6$.
• Row $s_3$: $18/2=9$.

Smallest ratio is $6$ → $s_2$ leaves. Pushing $x_2$ to $6$ makes $s_2=0$ (constraint $2x_2\le 12$ becomes tight) while others stay $\ge 0$. New corner: $x_1=0,x_2=6$, so $(0,6)$ with $z=3(0)+5(6)=30$.

After the first pivot, $x_2$ is basic ($=6$), and the $z$-row still has a negative under $x_1$, so we pivot again. Carrying the row-reduction to completion (enter $x_1$, ratio test picks the $3x_1+2x_2\le 18$ row) lands us at the intersection of $2x_2=12$ and $3x_1+2x_2=18$: $2x_2=12\Rightarrow x_2=6,3x_1+2(6)=18\Rightarrow 3x_1=6\Rightarrow x_1=2.$ Corner $(2,6)$, and $z=3(2)+5(6)=6+30=36$. The $z$-row is now all $\ge 0$ → optimal. Check the third constraint on the way: $x_1=2\le 4$ ✓, both used up sensibly. See the corner walk in the figure below.

The $z$-row equation is $z=2x_1+7x_2-4s_2$ (move the negatives across). So $\partial z/\partial x_2=7$, the largest positive rate. $x_2$ enters — increasing it raises $z$ by $7$ per unit, more than $x_1$'s $2$; the $s_1,s_2$ columns ($0$ and $+4$) either help nothing or reduce $z$, so we would never increase them. "Most negative in the $z$-row" is exactly "biggest positive rate of gain".

Yes — optimal, because every $z$-row coefficient is $\ge 0$. Reading $z=\text{(const)}-3x_2-1s_1-5(\cdot )$: raising any currently-non-basic variable can only lower $z$ (a $0$ leaves it unchanged). With no direction of improvement left, we sit on the top corner. This is the parent note's optimality test stated as a picture: the objective ramp no longer tilts uphill in any feasible direction.

Why negate? The simplex loop is built to maximize. Minimizing $z$ is the same as maximizing $w=-z=x_1+3x_2$, since $\min z=-\max (-z)$. Slacks: $x_1+x_2+s_1=5,x_1+2x_2+s_2=8$. The $w$-row coefficients are $(-1,-3)$. Pivot 1 — enter $x_2$ (most negative $-3$). Ratios: $5/1=5$, $8/2=4$ → $s_2$ leaves. New corner: on the line $x_1+2x_2=8$ with $x_1=0$ → $x_2=4$, giving $(0,4)$, $w=3(4)=12$. The $w$-row still shows a negative under $x_1$, so continue. Pivot 2 — enter $x_1$. The binding pair is $x_1+x_2=5$ and $x_1+2x_2=8$. Solve: $\text{subtract: }(x_1+2x_2)-(x_1+x_2)=8-5\Rightarrow x_2=3,x_1=5-3=2.$ Corner $(2,3)$: $w=2+3(3)=2+9=11$? Check both objectives carefully: $w=x_1+3x_2=2+9=11$. Compare $(0,4)$: $w=12$. Since $12>11$, the corner $(0,4)$ is actually the better one for $w$ — the $x_1$ column would not improve $w$ here, so the $w$-row is already all $\ge 0$ after pivot 1. Optimum: $(0,4)$, $w=12$. Therefore $\min z=-w=-12$ at $(0,4)$. (Moral: always evaluate — the ratio/entering rules propose a move, but the optimality test is what confirms you have arrived.)

By strong duality, the dual's optimal (a minimization) equals the primal's optimal. So the dual optimum is $36$. Usefulness: after you finish the primal by simplex, computing any feasible dual solution with value $36$ proves you reached the true optimum — a second, independent certificate beyond "the $z$-row went all non-negative". This is why the tableau's final $z$-row entries under the slack columns are exactly the dual variable values.

A tie means the entering variable hits two constraints at the exact same value — more than $m$ constraints pass through one corner. That corner is degenerate (over-determined). Practical danger: a pivot may swap basis variables while $z$ does not change (a "stall"), and in rare cases the method can cycle back to a basis it already visited, never terminating. Fixes: Bland's rule (break ties by choosing the variable with the smallest index) guarantees termination. Geometrically the vertex is fine; the bookkeeping just needs an anti-cycling tie-break.

Slack: $x_1-x_2+s_1=1$. The $z$-row is $(-1,-1)$; say $x_2$ enters. Its column entry in the only constraint row is $-1$ (negative). The ratio test uses only positive entries — there are none. That means: as $x_2$ grows, $s_1=1-x_1+x_2$ grows too, so no constraint ever stops $x_2$. We can raise $x_2$ (and $z$) without limit → the LP is unbounded, $z\to +\infty$. The signal in the tableau: a negative $z$-row entry whose entire column has no positive entry = unbounded objective. (See figure — the feasible region opens upward forever.)

Convert the $\ge$: $x_1+x_2\ge 5\Rightarrow -(x_1+x_2)\le -5$, whose RHS is $-5<0$. The basic starting solution $x_1=x_2=0$ gives slack $=-5<0$ → not feasible, so the origin is not a valid starting corner; plain simplex needs $\mathbf{b}\ge 0$. The one-line reason no solution exists: a sum cannot be both $\le 2$ and $\ge 5$, so the feasible region is empty (the two half-planes never overlap). Handling requires the two-phase or Big-M method to find a feasible corner first — which here reports infeasibility.

The entering variable is the one with the most negative $z$-row coefficient. The leaving variable is chosen by the smallest positive ratio RHS ÷ column entry. We stop when every $z$-row coefficient is ==$\ge 0$. A ratio-test column with no positive entries signals an unbounded objective. A tie in the ratio test signals a degenerate== vertex and risks cycling.