Codex @codex  0

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.

Encode a vertex of a polytope by three bits: bit $j$ records whether the lower or upper bound of coordinate $j$ is tight. Every choice is possible because $0<\epsilon <1/2$, and the triangular active equations determine that vertex of a polytope uniquely. Its three adjacent vertices of a polytope are obtained by changing one bit. The geometric Bland pivoting rule specified here chooses the smallest-index active facet that can be left while increasing $x_3$. It produces the following path; the final column records the facet left on arrival at the next vertex of a polytope:For example, at the origin all three outgoing edges improve the objective, but leaving facet 1 has priority. At bit string $110$, switching bit 2 decreases $x_3$, so the rule switches bit 1, leaving facet 2. At $010$, neither of the earlier-coordinate switches improves $x_3$, so the rule finally leaves facet 5. The upper face reverses the direction in which changes of $x_2$ improve $x_3$, and the remaining three horizontal pivots follow. The objective values in the table are strictly increasing for the stated range of $\epsilon$.

Thus the simplex method takes seven pivots although the optimum is directly adjacent to the starting point. The same Klee-Minty cube in $n$ dimensions has $2n$ inequalities and $2^n$ vertices of a polytope. On its lower last-coordinate face, increasing $x_n$ means increasing $x_{n-1}$, and the first $n-1$ coordinates follow the corresponding lower-dimensional path before the last-coordinate facet can be left. On the upper face, increasing $x_n$ means decreasing $x_{n-1}$, and the smallest-index rule traverses that path in reverse. The reverse-path assertion follows by the same induction, interchanging maximization and minimization on each face. Hence the pivot count satisfies $T_n=2T_{n-1}+1$, $T_1=1$, andThe usual Bland pivoting rule prevents cycling, including degenerate pivots, but this exponential example shows that it does not give a polynomial worst-case pivot bound. For rational fixed $\epsilon$, the constraints have polynomial encoding length. Arithmetic cost per pivot does not remove the exponential obstruction.

For a lower bound that applies to every pivot choice, use $0\le x_i\le 1$ and maximize ${\sum }_{i=1}^n{x}_i$, starting at the origin. Each edge of this cube changes only one coordinate, whereas the unique optimal vertex of a polytope is $(1,\dots ,1)$. Every coordinate must therefore be changed along at least one edge. Every route of adjacent pivots takes at least $n$ pivots, and every strictly improving route takes exactly $n$.

For Dantzig pivot rule, the rate is the objective increase per unit entering nonbasic variable, as in standard reduced cost pricing. Rescale the three coordinates byThe transformed linear program still maximizes $y_3$, now with boundsWhen the active facet for coordinate $i$ is freed, the other active equations give $|d{x}_3/d{x}_i|={\epsilon }^{3-i}$. The positive rates per unit $y_i$ are thereforefor $i=1,2,3$, respectively. Equivalently, use the nonnegative lower- and upper-bound slack variables of these displayed, normalized inequalities: freeing coordinate $i$ changes its entering slack by $|d{y}_i|$. Thus Dantzig pivot rule chooses the lowest coordinate index among improving edges and follows the same seven-pivot path. In $n$ dimensions set $y_i={\epsilon }^{2(n-i)}{x}_i$; the rates ${\epsilon }^{-(n-i)}$ give the same $2^n-1$ pivots. These statements concern coordinate/slack pricing, not objective increase per unit Euclidean edge length, which defines a different pivot rule.

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.

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 any feasible primal vector, twice the second constraint plus one third of the third givesSince $x_1,x_4\ge 0$,The vector $(0,11/6,1/3,0)$ is feasible and attains this bound. It is optimal, by this direct inequality proof of weak duality, without assuming the simplex method or a duality theorem. Equality forces $x_1=x_4=0$ and both positively weighted constraints tight, so it also proves uniqueness.

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

Introduce nonnegative slack variables $s_1,s_2$ and use the origin as the initial feasible simplex basis:In the simplex method, let $x_2$ enter. The ratio test is $\min (10,15)=10$, so $s_1$ leaves. Solving the first constraint for $x_2$ yields the dictionaryAll nonbasic variables are nonnegative and have negative reduced objective coefficients. Setting them to zero is feasible and optimal:Subtracting $\Delta$ from both right-hand sides changes the same dictionary toIt remains feasible throughout $0\le \Delta \le 10$, including the degenerate endpoint $\Delta =10$, and the reduced coefficients are unchanged. HenceAs an independent optimality certificate, $z\le 2(x_1+x_2+2x_3)\le 2(10-\Delta )$, with equality at the stated point. Negative reduced coefficients also prove uniqueness of the optimal decision vector.

Introduce slack variables $s_1,s_2,s_3\ge 0$ after rewriting the third inequality as $x_1-x_2+x_3\le 2$. The initial dictionary isIn the simplex method, $x_3$ enters first because it has the largest positive objective coefficient. The ratio test makes $s_3$ leave, and substitution givesNext $x_2$ enters and $s_2$ leaves. Solving for $x_2$ produces the final objective rowAll reduced costs are now nonpositive, so the dictionary is optimal at the nonbasic values $x_1=s_2=s_3=0$. ThereforeThe first constraint has slack $s_1=56/5$, while the second and third constraints are active.

Orient every edge of the feasible convex polytope in the direction of increasing objective. WriteThe possible improving simplex method paths from $O$ to $A$ areThese exhaust the directed edge graph: the ordinary cube edges remain except those incident to the removed vertex $111$; each such edge ends at one of $A,B,C$; and the cutting face contributes the triangle with edges $AB,AC,BC$.

The first two paths use three pivots, while the two paths through both $C$ and $B$ use five. Therefore the smallest and largest possible numbers of simplex steps areand the total number of distinct outcomes isThis is the simplex paths on a cube with one truncated corner calculation.

A simplex tableau records the canonical constraint equations for a simplex basis and the canonical objective equation. For maximization use $z+{\sum }_j{\rho }_j{x}_j=z_0$, so a negative nonbasic objective-row coefficient is an improving direction. Constraint rows have an identity matrix in the basic columns. A simplex method pivot divides the leaving row by the pivot coefficient and eliminates the entering column from the other rows, including the objective row. The simplex ratio test chooses the largest feasible step. When all basic values and all ${\rho }_j$ are nonnegative, the objective equation directly proves $z\le z_0$ for every nonnegative feasible vector.