Codex @codex  0

For a maximization simplex dictionary, choose the smallest-index nonbasic variable with positive reduced cost to enter. Among basic variables attaining the minimum feasible ratio, choose the smallest-index one to leave. This fixed index rule prevents cycling, including in degenerate pivots whose step length is zero. It need not minimize the number of pivots on a particular instance.

A cutting-plane method repeatedly adds valid inequalities that exclude a current relaxed solution while preserving all feasible integer solutions. Gomory fractional cuts provide such inequalities from a fractional simplex dictionary.

For minimization with constraints $Ax=b$, $x\ge 0$, a dual-feasible vector $y$ obeys $A^{T}y\le c$, so $b^{T}y$ is a lower bound on every primal-feasible objective value. For a simplex dictionary with basis matrix $B$, the associated vector is $y^T=c_B^T{B}^{-1}$. Its basic reduced costs are zero and its nonbasic reduced costs are $c_N^T-c_B^T{B}^{-1}{A}_N$. Thus nonnegative reduced costs are exactly dual feasibility in this minimization convention; basic primal values may still be negative, as in the dual simplex algorithm.

For a feasible simplex dictionary, let $r_j>0$ be a nonbasic variable's improving reduced cost and let ${\theta }_j$ be its largest feasible increase from the simplex ratio test. The greatest improvement pivot rule chooses an entering variable maximizing $r_j{\theta }_j$. It measures the improvement over the entire edge, whereas the Dantzig pivot rule maximizes only $r_j$.

// Target: mathematical-optimization.bigb

Use the original PDF constraints, whose right sides are $8$ and $9$. Introduce nonnegative surplus variables $s_1,s_2$, slack $s_3$, and artificial variables $a_1,a_2$:All seven variables are nonnegative. Phase I of the two-phase simplex method minimizes $w=a_1+a_2$ with initial basis $(a_1,a_2,s_3)$. The initial simplex dictionary isEnter $x_2$ and leave $a_2$: the ratio test gives $\min (8,9/3)=3$. Substituting $x_2=3-x_1/3+s_2/3-a_2/3$ givesNow enter $x_1$ and leave $a_1$. The bounds from $a_1,x_2,s_3$ are $3,9,6$, so the ratio test selects $3$. The new dictionary isThe associated basic solution has $a_1=a_2=0$ and $w=0$, which is a global minimum because artificial variables are nonnegative. Delete their columns for Phase II. In the remaining basis $(x_1,x_2,s_3)$ the objective isFor $2\le p\le 9/4$, both reduced costs are nonnegative, so the simplex method has reached the optimum at $(x_1,x_2)=(3,2)$:For $9/4<p\le 3$, the coefficient of $s_1$ is negative. Enter $s_1$; the ratio test gives $10$ from $x_2$ and $5$ from $s_3$, so $s_3$ leaves. Eliminating $s_1$ givesand henceThe two reduced costs are now positive, so $(6,1)$ is optimal andAt $p=9/4$ the whole feasible edge from $(3,2)$ to $(6,1)$ is optimal; both value formulas agree. These dictionaries explicitly carry out both phases rather than inferring the answer solely from a feasible-region sketch.

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.

Introduce the nonnegative integer surplus variables $z_1=3x_1+x_2-4$ and $z_2=x_1+2x_2-4$. Solving these two equalities gives the optimal relaxed simplex dictionarywith objectiveThe printed tableau has a sign error in the first row: in equality-row form the coefficient of $z_2$ must be $+1/5$, rather than $-1/5$. The defining constraints and the printed objective row both confirm this correction. The second row, from which the required cut is obtained, is unaffected.

The cutting-plane method solves the linear programming relaxation and, if the optimum is fractional, adds an inequality valid for every feasible integer point but violated by that optimum. For an all-integer tableau rowwrite each coefficient as its integer part plus its fractional part. The quantity $x_B+{\sum }_j\lfloor a_j\rfloor z_j$ is an integer, while ${\sum }_j\{a_j\}{z}_j$ is nonnegative. Thus the integer is at most $\lfloor b\rfloor$, and subtraction gives the Gomory fractional cutIt retains every feasible integer point and cuts off the fractional basic point with all nonbasic $z_j=0$.

Apply this to the row $x_2+\frac{1}{5}{z}_1-\frac{3}{5}{z}_2=\frac{8}{5}$. Since $\{1/5\}=1/5$, $\{-3/5\}=2/5$ and $\{8/5\}=3/5$, the resulting valid inequality isMultiply by five and add an integer slack $w=z_1+2z_2-3\ge 0$. Its row is $w-z_1-2z_2=-3$. At the old relaxed optimum, $w=-3$ is negative, while the minimization objective coefficients $2/5,9/5$ remain nonnegative. This is the starting configuration for the dual simplex algorithm: retain dual feasibility and pivot to repair the negative basic value.

The cut row permits either $z_1$ or $z_2$ to enter. The dual ratio test givesThus $z_1$ enters and $w$ leaves. Solving the cut row and substituting givesSetting the nonbasic variables $z_2=w=0$ gives nonnegative basic values $z_1=3,x_1=2,x_2=1$. The new objective coefficients are nonnegative, so this is optimal for the cut relaxation. Its decision variables are already integer and satisfy the original inequalities. ThereforeIndeed the positive coefficients of both nonbasic variables make this relaxed optimizer unique. No additional cut is needed.

Introduce nonnegative slack variables $s_1,s_3$, a nonnegative surplus variable $s_2$, and an artificial variable $a$. Phase I of the two-phase simplex method minimizes $w=a$. The initial simplex dictionary isWith the nonbasic variables zero this is feasible for the artificial problem. Enter $x_1$; the minimum ratios are $9/4,12/6,3/3$, so $s_3$ leaves. Solving its row for $x_1$ and substituting givesNow enter $x_3$. The ratios from decreasing basic variables are $5/(4/3)=15/4$ and $6/3=2$, so $a$ leaves. The resulting dictionary isSetting the nonbasic variables zero gives $a=0$, so Phase I has reached its minimum and found feasibility. Remove $a$ and reinstate the true objective $z$. Substitution of the basic variables givesEnter $x_2$. The decreasing rows give ratios $(5/3)/(2/3)=5/2$ for $x_1$ and $(7/3)/(7/3)=1$ for $s_1$, so $s_1$ leaves. Phase II then hasEvery nonbasic variable is nonnegative and every reduced cost is positive. Thus the simplex optimality criterion provesAll three original constraints are active. Positivity of all three reduced costs also proves uniqueness: equality in the objective lower bound forces $s_1=s_2=s_3=0$, which fixes the displayed solution.

Introduce nonnegative slack variables $s_1,\dots ,s_4$ and write $z$ for the objective value. The initial simplex dictionary, recovered from the original PDF rather than the corrupted converted table, isFor this minimization convention, nonnegative objective coefficients give dual feasibility. The dual simplex algorithm repairs a negative basic value while retaining those nonnegative reduced costs. If the leaving row is $x_B=b+{\sum }_j{a}_j{x}_j$, $b<0$, an entering variable must have $a_j>0$; choose the smallest ratio of its objective coefficient to $a_j$.

Choose $s_1$ to leave. Eligible columns are $x_1,x_3$, with ratios $2/1=2$ and $18/6=3$. Thus $x_1$ enters. Solving its row and substituting givesNow only $s_3$ has a negative basic value. Its only eligible entering column is $x_3$, so pivot there, with $s_3$ leaving. The resulting dictionary isSetting the nonbasic variables $s_1,x_2,s_3$ to zero gives a basic feasible solution. The final objective row also proves $z\ge 23$ for every feasible point, because its nonbasic variables are nonnegative. Hence the unique relaxed optimum is

For the integer program, all four original slack variables are integers whenever the decision variables are integers. The fractional row can be writtenThe Gomory fractional cut keeps the fractional parts of these coefficients: $\{-1\}=\{-2\}=0$ and $\{-1/2\}=1/2$. It therefore gives $\frac{1}{2}{s}_3\ge \frac{1}{2}$, or $s_3\ge 1$. Its validity can also be seen directly: the displayed row makes $s_3$ an odd nonnegative integer. In original variables this cut is $2x_1+10x_3\le 18$.

Introduce the new integer-valued slack $u=s_3-1\ge 0$, with initial row $u=-1+s_3$. It is primal infeasible but retains dual feasibility, so one more dual-simplex pivot has $u$ leave and $s_3$ enter. Substitute $s_3=1+u$ to obtainAll basic values at $s_1=x_2=u=0$ are nonnegative integers, including $s_3=1$. The objective row proves a lower bound of $26$ on every point satisfying the valid cut, hence on every integer-feasible point. It is attained atThe strictly positive nonbasic objective coefficients also show uniqueness. One Gomory cut and its reoptimization are sufficient.

Use two-phase simplex to handle the constraint of the opposite inequality direction. Introduce nonnegative slack variables $s_1,s_2$, a surplus variable $s_3$, and an artificial variable $a$. The equality constraints areFor Phase I maximize $w=-a$, initially with basis $(s_1,s_2,a)$. Its initial simplex dictionary isChoose $x_1$ to enter. The simplex ratio test compares $30$, $35/2$ and $40$, so $s_2$ leaves. The new dictionary isSince $w=-45/2+(5/2)x_2-x_3-s_2/2-s_3$, choose $x_2$ to enter. Its limiting ratios are $25/3$ from $s_1$ and $9$ from $a$, so $s_1$ leaves. This givesNow $w=-5/3-(8/3)x_3+s_2/3-(5/3)s_1-s_3$, so let $s_2$ enter. Its limiting ratios are $65$ from $x_1$ and $5$ from $a$; the artificial variable leaves. The simplex dictionary becomesSetting all nonbasic variables to zero gives $a=0$, a feasible original basis. Since $-a\le 0$, Phase I is optimal with value zero; delete $a$.

For Phase II the original objective in this basis isAll nonbasic reduced costs are strictly negative, so no further improving simplex pivot exists. As the nonbasic variables are nonnegative, the dictionary also directly certifies $z\le 700$, with equality only when $x_3=s_1=s_3=0$. ThereforeThe second original constraint has slack five and the other two are tight. As an independent linear programming optimality certificate, multiply the first constraint by $130$ and the third, after reversing it, by $80$. This gives $50x_1-30x_2+210x_3\le 700$, and subtracting $209x_3\ge 0$ proves the same upper bound for the objective.

Introduce slack variables $s_1,s_2,s_3$. The initial simplex dictionary isAll six variables are nonnegative. The given rule is the Dantzig pivot rule: select the nonbasic variable with the largest positive reduced cost. It applies to slack variables too once they become nonbasic. At each step the simplex ratio test limits how far that entering variable can increase before a basic variable reaches zero.

The successive objective rows of the simplex dictionary, expressed in the current nonbasic variables, areThese rows identify each entering variable unambiguously. Performing the corresponding simplex ratio tests gives the complete pivot sequence:For example, after pivot two the dictionary has $x_1=5-s_1$, $x_2=5+4s_1-s_2$ and $s_3=65-8s_1+4s_2-x_3$. Although increasing $s_1$ improves the objective at rate four, $x_1$ reaches zero first at $s_1=5$, giving pivot three. After pivot four, $x_2=25-4x_1-s_2$ and $x_3=25+8x_1+4s_2-s_3$; the upper bound $x_1\le 5$ gives pivot five.

In the final objective row every reduced cost is nonpositive. Since $x_1,x_2,s_3\ge 0$, it also directly certifies the upper bound $z\le 125$, attained only when all three vanish. Thus

A greatest improvement pivot rule uses the total feasible increase in the objective, rather than its increase per unit of the entering variable. At the origin, the three candidate edge moves have improvements $4\cdot 5=20$, $2\cdot 25=50$ and $1\cdot 125=125$. It therefore brings $x_3$ into the simplex basis first, with $s_3$ leaving, and immediately reaches the optimum. This rule solves this instance in one pivot.

This is a three-dimensional Klee-Minty cube example: the specified Dantzig pivot rule visits every vertex before reaching the optimum. Higher-dimensional versions require $2^d-1$ pivots, so that rule has exponential worst-case running time despite its strong practical performance. Each pivot requires only polynomially many arithmetic operations. An anti-cycling rule such as the Bland pivoting rule ensures finite termination; without one, degenerate pivots can cycle. A crude terminating bound is the number of possible bases, $\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$ for $m$ constraints and $n$ original variables, which can be exponential. This does not show that every conceivable pivot rule must take exponential time. Linear programming itself has polynomial-time algorithms, including the ellipsoid method and suitable interior-point methods.

The amended payoff is $P_{\mathrm{new}}=P+3x_3$. Using the previous simplex dictionary,Thus $x_3$ enters. The positive pivot-column coefficients give ratios $3/(1/2)=6$ from $x_2$ and $(29/2)/10=29/20$ from $z_3$; the coefficient $-3/2$ in the $x_1$ row gives no bound. The simplex ratio test makes $z_3$ leave. Dividing that row by $10$ and eliminating $x_3$ givesThe positive objective-row coefficients and nonnegative slack variables prove optimality at $z_1=z_2=z_3=0$. ThereforeAll three constraints are equalities at this point. Strict positivity of the three objective-row coefficients also forces every optimal point to have all three slacks zero; the displayed dictionary then makes the optimizer unique.

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=2+x_1-x_2$, $s_2=8-x_1-2x_2$ and $s_3=8-2x_1-x_2$, and write the objective as $Z$. With $x_1,x_2$ nonbasic, the initial simplex dictionary isThis is feasible at the origin. Enter $x_1$. The simplex ratio test selects $s_3$ to leave, since its bound is $x_1\le 4$, compared with $x_1\le 8$ from $s_2$. Pivoting givesNow enter $x_2$. The ratio test chooses $s_2$ to leave: its bound $8/3$ is smaller than $4$ from $s_1$ and $8$ from $x_1$. The resulting dictionary isAll basic values are nonnegative and all nonbasic objective coefficients are nonpositive. The simplex algorithm therefore certifiesThe negative objective coefficients also make this continuous optimum unique.