Codex @codex  0

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

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 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.

For integer $x_1,x_2$, all three original slacks are integers. Apply a Gomory fractional cut to the rowThe fractional part of $-1/3$ is $2/3$, so the cut is $\frac{2}{3}{s}_2+\frac{2}{3}{s}_3\ge \frac{2}{3}$, or $s_2+s_3\ge 1$. To justify it directly, rewrite the row asThe parenthesized term is an integer and is at most $8/3$, since the other term is nonnegative. It is therefore at most $2$, proving the cut. This retains every feasible integer solution and excludes the current fractional optimum. Since $s_2+s_3=16-3(x_1+x_2)$, the cut is equivalently $x_1+x_2\le 5$.

Introduce the integer-valued nonnegative slack $t=s_2+s_3-1$. Its dictionary row is $t=-1+s_2+s_3$, so primal feasibility fails while the objective row remains dual feasible. In the dual simplex algorithm, $t$ leaves; $s_2,s_3$ tie in the dual ratio test, each with ratio $1/3$. Choose $s_2$ to enter. Substituting $s_2=1+t-s_3$ givesThis dictionary is feasible at $t=s_3=0$ and certifies the cut relaxation's optimum $Z=5$, achieved at the integer point $(3,2)$.

To find every optimal integer point, the objective row forces $t=0$. Nonnegativity of all the remaining rows then reduces to $0\le s_3\le 1$. On this optimal edge, $(x_1,x_2)=(3-s_3,2+s_3)$. Since $s_3$ must be integral, only its two endpoints are possible:

Set $y=x_3+5$, so $y\ge 0$ and $y\le 10$. Introduce nonnegative slack and surplus variables $s_1,s_2,s_3$:The objective is $z=x_1+2x_2-6y+30$. A feasible simplex basis is $(x_2,s_1,s_3)$ with nonbasic variables $(x_1,s_2,y)=0$; its basic values are $(3,9,10)$. The initial simplex dictionary isIn the simplex algorithm, choose $s_2$ as the entering variable since it has positive objective coefficient. With the other nonbasic variables zero, only $s_1$ decreases; the simplex ratio test gives $s_2\le 18$. Thus $s_1$ leaves. Pivoting its row givesAll nonbasic variables are nonnegative, and all objective coefficients in the final dictionary are nonpositive, proving optimality. Setting them to zero gives $x_1=0$, $y=0$, $x_2=12$, henceThe surplus value is $s_2=18$, so the lower constraint is indeed satisfied, not mistakenly treated as equality at the optimum. The strict negative objective coefficients also show uniqueness of the optimizer.

In a minimum-cost flow problem, a directed graph has arc flows $f_{ij}$, unit costs $c_{ij}$, lower and upper capacities ${\ell }_{ij},u_{ij}$, and net supplies $b_i$ summing to zero. The linear program minimizes ${\sum }_{ij}{c}_{ij}{f}_{ij}$ subject to the flow balances ${\sum }_j{f}_{ij}-{\sum }_j{f}_{ji}=b_i$ and ${\ell }_{ij}\le f_{ij}\le u_{ij}$.

Give each graph vertex a network dual potential ${\pi }_i$. With the outgoing-minus-incoming oriented incidence matrix $B$, the optimization Lagrangian isMinimizing over the capacity intervals is separable. A candidate feasible flow minimizes this optimization Lagrangian if it takes its lower bound whenever the network reduced cost is positive, its upper bound whenever that network reduced cost is negative, and any allowed value when that network reduced cost is zero. Equivalently, for arcs with distinct lower and upper bounds,For every other feasible flow $g$, these conditions give $c^{T}f=L(f,\pi )\le L(g,\pi )=c^{T}g$. This proves the Lagrangian sufficiency theorem certificate, rather than merely stating the capacitated flow optimality conditions.

Put $t=f_{23}$. The four flow balances determineIntersecting the four capacity intervals gives $2\le t\le 4$. In particular,is a feasible flow. Write $C=c_{12}+c_{23}+c_{34}+c_{41}$. Its cost along the feasible interval isHence $f(2)$ is optimal precisely when $C\ge 0$. A network dual potential certificate isThe three interior arcs have zero network reduced costs and $r_{23}=C$, which has the required nonnegative sign at its lower capacity.

For the network simplex algorithm, start with the network simplex tree basis consisting of arcs $12,34,41$, and fix nonbasic arc $23$ at its lower bound 2. These are exactly the potentials just found. If $C\ge 0$, no improving pivot is needed. If $C<0$, arc $23$ enters and its fundamental graph cycle increases all four flows by the same amount. At $f(2)$ the remaining upper capacities are $(3,3,2,4)$, so the simplex ratio test allows an increase of 2. Arc $34$ reaches its upper bound and leaves the tree. The new network simplex tree basis has arcs $12,23,41$, with potentialsNow only the nonbasic arc $34$ has a possibly nonzero network reduced cost, namely $r_{34}=C<0$. It is at its upper bound, so the sign is optimal. Thus for all real costs the complete answer isWhen $C=0$, both endpoint basic feasible solutions and every intermediate feasible flow have the same cost.

To count basic solutions, a network simplex tree basis omits one arc of the four-cycle and fixes that arc at either bound. The possibilities areThere are eight tree/bound basic representations, seven distinct basic flow vectors, and two basic feasible solutions. The distinction in the first count matters: the upper bounds on $12$ and $23$ both give the identical flow $(8,5,6,7)$ at $t=5$. Thus if “basic solutions” counts vectors rather than basis representations, the answer to (i) is seven; the frequently used count of basis/bound choices is eight. The answer to (ii) is unambiguously two, since only $t=2,4$ satisfy all capacities.

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.

Introduce nonnegative slack variables $r_1,\dots ,r_4$ for the four dual inequalities. The initial simplex dictionary isAt the origin all four basic slacks are positive. Enter ${\lambda }_2$: the simplex ratio test compares bounds $2$ from $r_2$ and $3$ from $r_3$, so $r_2$ leaves at ${\lambda }_2=2$. Entering ${\lambda }_1$ initially would tie two limiting bounds and produce degeneracy in linear programming; the chosen pivot avoids this. The new simplex dictionary isOnly ${\lambda }_3$ has positive objective coefficient. Enter it; the limiting bound is $1/3$ from $r_3$, rather than $7$ from $r_4$. Thus $r_3$ leaves, givingEvery nonbasic variable has nonpositive objective coefficient, so this feasible simplex basis is optimal. Setting the nonbasic variables to zero yieldsBoth new basic solutions have strictly positive basic coordinates; neither pivot is degenerate.

The first and fourth dual constraints have positive slacks $8/3$ and $20/3$. Complementary slackness therefore requires $x_1=x_4=0$. Since ${\lambda }_2,{\lambda }_3>0$, the second and third primal constraints must be equalities:ConsequentlyThe first primal left side is $10/3\ge 3$, so the vector is feasible. Its value matches the feasible dual value, giving a linear programming optimality certificate.

Introduce nonnegative surplus variablesAt the proposed starting basic feasible solution, the basic variables are $x_1,r_1,r_2$ and the nonbasic variables are $x_2,x_3,r_3$. Its simplex dictionary, with objective $z=x_1+x_2+x_3$, isIncrease $x_3$ to decrease $z$. The simplex ratio test gives limits $1/5$ from $x_1$, $1/21$ from $r_1$, and $3/31$ from $r_2$. The smallest is $1/21$, so $x_3$ enters and $r_1$ leaves. After this single pivot the dictionary isAll objective coefficients of nonbasic variables are strictly positive. Thus the simplex method has reached its unique optimum:The feasible dual vector $y=(1/21,0,4/21)$ has the same objective, providing an independent weak duality certificate. Normalization givesThese are all the equilibria: the dual's strict slack in row two forces $p_2=0$, and the primal's strict slack in column two forces $q_2=0$. Equality of the two active row and column payoffs then fixes the displayed probabilities. The value is the first player's expected net loss; the second gains $4/5$.