Codex @codex  0

Introduce surplus variables $s_1,s_2$, slack $s_3$, and artificial variables $a_1,a_2$, all nonnegative. The two-phase simplex standard-form equations arePhase I maximizes $w=-a_1-a_2$. An initial basic feasible solution has basic variables $(a_1,a_2,s_3)=(1,10,6)$ and all others zero. Its simplex dictionary isLet $x_1$ enter. The simplex ratio test gives $1$ from the $a_1$ row and $10/4$ from the $a_2$ row, so $a_1$ leaves. After this pivot,Choose $x_2$ to enter; the limiting ratios are $6/3=2$ and $6$, so $a_2$ leaves. The resulting dictionary isThus $\boxed{w_{\max }=0}$, attained at $(x_1,x_2,s_3)=(3,2,4)$ with $s_1=s_2=a_1=a_2=0$. Since $w\le 0$ for every feasible Phase I point, this proves feasibility and completes Phase I.

Delete the artificial variables and restore the original objective $z=-2x_1+3x_2$. The resulting Phase II dictionary isLet $s_2$ enter; only $s_3$ decreases, and it reaches zero at $s_2=12$. Pivoting givesAn optimal simplex tableau, with each row recording its equality, isBoth reduced costs in the maximization dictionary are negative. Setting nonbasic $s_1=s_3=0$ therefore givesAs a direct optimality check, $x_1\ge 1+x_2$ implies $z\le -2+x_2\le 4$; the displayed point attains both equalities.

Use the original PDF: the objective is $z=-x_1+3x_2$, and the second constraint has coefficient $2$ on $x_2$. The TeX transcription corrupts both, as well as the nonnegativity condition. Introduce surplus variables $s_1,s_2$, slack variables $s_3,s_4$, and artificial variables $a_1,a_2$, all nonnegative. The two-phase simplex Phase One problem isThe initial basis $(a_1,a_2,s_3,s_4)$ has values $(3,6,2,5)$, and its objective dictionary is $w=9-3x_2+s_1+s_2$. Enter $x_2$: the ratio test makes $s_3$ leave at $x_2=2$. The resulting dictionary includeswith $w=3-3x_1+s_1+s_2+3s_3$. Enter $x_1$ next; $a_1$ leaves at $x_1=1/2$. Nowand $w=3/2-s_1/2+s_2+3s_3/2+3a_1/2$. Enter $s_1$; the ratio test makes $a_2$ leave at $s_1=3$. This produces $x_1=2$, $x_2=4$, $s_1=3$, $s_4=1$ with both artificial variables zero. Since $w\ge 0$ always, the Phase One minimum is zero, proving feasibility and providing an original-variable basis.

Delete the artificial columns. The starting Phase Two dictionary isEnter $s_2$, whose reduced gain is positive. Only $s_4$ decreases, and it leaves at step one. Eliminating $s_2=1-s_3-s_4$ gives the optimal dictionaryEquivalently, with row equations written as the displayed coefficients times the variables equal to the right-hand side, the optimal simplex tableau isThe objective row represents $z+s_3+2s_4=12$. Nonnegative nonbasic variables cannot improve the objective, so reading them as zero provesBoth nonbasic reduced costs are strictly unfavorable, so this optimal point is unique.

For the linear program in maximization form, a nonnegative multiplier $y$ of the resource inequalities giveswhenever $A^{T}y\ge c$. Equivalently, the Lagrangian is $b^{T}y+(c-A^{T}y{)}^{T}x$; its supremum over $x\ge 0$ is finite exactly when $A^{T}y\ge c$. Minimizing this bound gives the dual linear programThe displayed inequality proves weak duality directly.

For the final simplex tableau, the basic-variable order is $(x_2,x_1)$. With $z_1,z_2$ interpreted as the ordinary unpriced slack variables, its constraint equations giveThe bottom row is read in the reduced-cost convention $r_j=c_j-c_B^T{B}^{-1}{A}_j$, with right side minus the basic objective value. It says the reduced costs of $z_1,z_2$ are $0,-1/2$. Thus optimality requires $z_2=0$, while $z_1$ can increase without changing the objective until $x_2$ reaches zero. The complete primal optimum set is

Reconstructing a linear program from a final simplex tableau exposes a source inconsistency. The slack columns areBecause the first basic column is that of $x_2$, the original constraint data areThe slack reduced costs give $y^T=(0,1/2)$ andConsequently the recovered homogeneous linear program isEvery point in the optimum segment has value $15/2$. Since the segment contains a point with both variables positive, complementary slackness forces both dual column inequalities to be equalities. They give the unique dual optimum

The printed bottom-right entry is $-3$, but it must be $-15/2$ for this linear objective and these constraint rows. Thus no original problem in the stated homogeneous standard form has exactly the entire printed tableau. Changing that one entry to $-15/2$ gives the reconstructed problem above. Alternatively, if an affine objective is permitted, $5x_1-\frac{5}{2}{x}_2-\frac{9}{2}$ has the displayed optimum value $3$ and unchanged reduced costs; the corresponding affine dual objective is $b^{T}y-\frac{9}{2}$. Both interpretations have exactly the same primal and dual optimizer sets. The discrepancy is in the objective constant, not in the optimal segment.

Use payoff $P=-(2x_1-3x_2-2x_3)$, so maximization of $P$ is equivalent to the required minimization. In the given simplex tableau, $x_1$ can increase the payoff. The simplex ratio test has candidate ratios $3/6=1/2$ in the $z_2$ row and $15/1=15$ in the $z_3$ row; the negative coefficient in the $x_2$ row imposes no upper bound. Thus $x_1$ enters the simplex basis and $z_2$ leaves.

Divide the pivot row by $6$, then eliminate $x_1$ from the other rows. The resulting simplex dictionary isAll slack variables and original variables are nonnegative. The last row therefore proves $P\le 8$ for every feasible point; setting the nonbasic variables $x_3,z_1,z_2$ to zero attains it and leaves all basic variables nonnegative. HenceThe slack vector is $(0,0,29/2)$.

Introduce nonnegative slack variables $s_1,s_2$ and let $z$ denote profit. We display each simplex tableau as coefficients of its row equation, with the coefficient of $z$ in the objective equation implicitly one. Thus a negative coefficient in the last row permits an improving entering variable. The initial simplex tableau isUse the simplex method with $x_2$ entering. The simplex ratio test gives ratios $6/2=3$ and $6/1=6$, so $s_1$ leaves. Divide its row by two and eliminate the other $x_2$ entries:Next $x_1$ enters. The positive-column ratios are $3/(1/2)=6$ and $3/(3/2)=2$, so $s_2$ leaves. After this pivot and a row reordering,The last row is $z=14-(5/3)s_1-(2/3)s_2$, so every nonnegative feasible solution has $z\le 14$. Setting the nonbasic variables to zero givesThe equality certificate also shows uniqueness, since both nonbasic objective coefficients are strictly unfavorable.

Add the slack variable $s_3$ for the forgotten constraint. In the optimal simplex tableau from part (a), $x_1+x_2=4-(s_1+s_2)/3$. Hence the new row in canonical form isAppending it givesThe objective row remains dual feasible, but $s_3=-1$ makes the basic solution infeasible. Apply the dual simplex algorithm: $s_3$ leaves, and the eligible columns are $s_1,s_2$, whose negative coefficients can repair this row. The dual ratio test comparesThus $s_2$ enters. Pivoting on $-4/3$ and eliminating its column givesAll basic values are nonnegative and the objective equation is $z=27/2-s_1-s_3/2$. ThereforeBoth binding constraints have zero slack, and the final objective row proves global optimality. The two nonbasic penalties are strictly positive, so this optimum is unique.

The old slack variable $s_3$ is exactly the amount now sold, so rename its column $y$. No further slack is added: the PDF specifies an equality. The feasible equations are otherwise unchanged. If $z_0$ is the old profit, the new profit is $z=z_0+y$. Substituting this into the old objective equation givesThis is the simplex objective update for a priced slack variable. The altered simplex tableau isThe coefficient $-1/2$ makes $y$ an improving entering variable. Its only positive constraint-row coefficient is $1/2$ in the $x_1$ row, whose ratio is $(3/2)/(1/2)=3$. Thus $x_1$ leaves. The simplex method pivot givesThe objective equation $z=15-x_1$ proves optimality. One optimal basic solution isThe zero reduced cost of $s_1$ permits alternative optima. In fact all optimal solutions areThese satisfy both remaining inequalities, and the equality then makes their profit exactly fifteen.

For a maximization problem with unpriced unit slack variables, their columns in a final simplex tableau give $B^{-1}$, where $B$ consists of the original basic columns. The constraint right side is $\bar{b}=B^{-1}b$, so $b=B\bar{b}$. If the objective row uses reduced costs $r_j=c_j-c_B^T{B}^{-1}{A}_j$, its slack entries are $-y^T$ with $y^T=c_B^T{B}^{-1}$. Therefore $c_B^T=y^{T}B$. In a homogeneous linear objective with no constant offset, the displayed basic objective value must equal $c_B^T\bar{b}=y^{T}b$. This identity detects inconsistent tableau constants; an affine offset affects the value but not the reduced costs.

If a variable $x_k$ gains an objective coefficient $p$, the new objective is $z=z_{\mathrm{old}}+p{x}_k$. Substitute this in the old canonical objective equation and eliminate any remaining basic-column coefficients using the constraint rows. If $x_k$ is nonbasic, this simply subtracts $p$ from its objective-row coefficient. When a slack variable is sold, rename the old slack as the sales quantity; its equation already gives the correct equality and no new slack is added. Reoptimization can then start directly from the altered simplex tableau.