Codex @codex  0

For an all-integer dictionary row $x_B+{\sum }_j{a}_j{x}_j=b$ with nonnegative variables, this cut follows because $x_B+{\sum }_j\lfloor a_j\rfloor x_j$ is an integer and ${\sum }_j\{a_j\}{x}_j\ge 0$. Consequently that integer is at most $\lfloor b\rfloor$. Negative coefficients use the usual fractional part $u-\lfloor u\rfloor$, so $\{-1/5\}=4/5$. Normalize a resulting inequality sensibly before introducing a new integer-valued slack variable.

Apply positive affine payoff transformations, if necessary, so both payoff matrices have strictly positive entries. Such transformations preserve best responses and Nash equilibria. The Lemke-Howson algorithm uses unnormalized nonnegative strategy vectors and slack variables satisfyingThus its two polytopes are $\{x\ge 0:Q^{T}x\le 1\}$ and $\{y\ge 0:Py\le 1\}$. A label $i\le m$ occurs when $x_i=0$ or $r_i=0$; a label $m+j$ occurs when $y_j=0$ or $s_j=0$. The complementary pivoting path drops one label from the artificial zero pair and resolves each duplicated label until all labels return.

Terminate at a completely labelled pair other than the artificial zero pair. This is equivalent to complementary slacknessA nonzero completely labelled pair has both vectors nonzero: if $x=0$, then $s=1$ forces $y=0$, and the converse is analogous. Normalize to mixed strategiesThe inequalities $Py\le 1$ imply that every row payoff against $q$ is at most $1/(1^{T}y)$, with equality on every row receiving positive probability in $p$. Thus $p$ is a best response to $q$. Likewise $q$ is a best response to $p$ using $Q^{T}x+s=1$. Hence $(p,q)$ is a Nash equilibrium. Nondegeneracy of a bimatrix game ensures the usual complementary pivoting path has a unique continuation after the label choice.

Row operations multiply each original tableau equation by an invertible matrix. The slack variable block therefore records that matrix and allows the original payoff matrix to be recovered without guessing.

From the first tableau, let $X$ be the coefficient block of $x$ and $S$ that of $s$. Since its original equations were $Q^{T}x+s=1$, we have $Q^T=S^{-1}X$. HeresoFor the second tableau, writing its $y$ and $r$ blocks as $Y,R$, the original equations $Py+r=1$ give $P=R^{-1}Y$. We obtainThus a representative pair of payoff matrices isBoth reconstructed right-hand sides are $1$, as a check on the tableau normalization. Independent transformations $P\mapsto aP+b11^T$, $Q\mapsto cQ+d11^T$, with $a,c>0$, preserve best responses and hence identify the same strategic solution up to positive affine payoff transformations.

Directly,The supports of $x^{\prime }$ and $y^{\prime }$ lie entirely among their respective best-response coordinates, confirming the Nash equilibrium found above. Since this representative is a symmetric bimatrix game, swapping the players' strategies preserves the Nash equilibrium conditions. Explicitly, $P{x}^{\prime }=(3,2,3{)}^T$ is maximized on the support of $y^{\prime }$, and $Q^T{y}^{\prime }=P{y}^{\prime }=(1,3,3{)}^T$ is maximized on the support of $x^{\prime }$. Therefore

Introduce nonnegative slack variables $s_1,s_2,s_3$ and start the simplex algorithm at $x=y=z=0$, with slacks $9,8,2$. The objective's largest positive entering coefficient belongs to $y$. Its ratio test is $9/3=3$, $8/2=4$, $2/1=2$, so $s_3$ leaves and $y$ enters.

Solve that pivot row for $y$ and substitute into the other rows and the objective $v$:This is a feasible simplex dictionary at nonbasic variables $x=z=s_3=0$. All their objective coefficients are negative, so no feasible increase can improve the objective. ThusThe negative reduced coefficients also prove uniqueness of this optimum.

The dual linear program, with nonnegative variables $u_1,u_2,u_3$, isThe feasible choice $\boxed{(u_1,u_2,u_3)=(0,0,5)}$ has objective $10$. Weak duality proves that it and the primal point are optimal. Complementary slackness also forces $u_1=u_2=0$ because the first two primal slacks are positive, and then the positive $y$ forces $u_3=5$.

Introduce integer-valued slack variables $s_1=11-2x_1-x_2$ and $s_2=6+x_1-2x_2$. Write $Z=4x_1+3x_2$. The initial simplex dictionary isIn the simplex algorithm, let $x_1$ enter. The first constraint is the only limiting one, so $s_1$ leaves at $x_1=11/2$. Substitution givesNow $x_2$ enters and $s_2$ leaves: its ratio $23/5$ is smaller than the first row's ratio $11$. The resulting simplex dictionary isAll nonbasic objective coefficients are nonpositive, and the basic values are nonnegative. Thus the continuous linear program has optimum

For integer programming, a row $x_B+{\sum }_j{a}_j{x}_j=b$ with integer variables yields the Gomory fractional cut ${\sum }_j\{a_j\}{x}_j\ge \{b\}$, where $\{u\}=u-\lfloor u\rfloor$ is the fractional part. In the first row, the coefficient of $s_2$ on the left is $-1/5$, whose fractional part is $4/5$, not $-1/5$. The two possible initial Gomory fractional cuts are thereforeIndeed $s_1+2s_2=23-5x_2$. Choose the second row: $x_2\le 4$ implies $x_2\le 9/2$, so its cut removes a strictly larger portion of the feasible polygon. This compares both printed alternatives before any further integer rounding.

Use the normalized integer slack variable $s_3=4-x_2$, rather than an unnecessarily scaled cut slack. At the current basis,The simplex dictionary is dual feasible but primal infeasible. In the dual simplex algorithm, $s_3$ leaves; the ratios of objective loss to improvement of this negative basic value are $11$ for $s_1$ and $1$ for $s_2$, so $s_2$ enters. The pivot givesThe relaxed optimum is now $(7/2,4)$, still nonintegral. The fractional $x_1$ row gives the next Gomory fractional cutThe negative left-hand coefficient $-1/2$ of $s_3$ also has fractional part $1/2$. Normalize the new integer slack variable as $s_4=7-x_1-x_2$. Its dictionary row is $s_4=-1/2+s_1/2+s_3/2$. The dual simplex algorithm chooses $s_3$ to enter: its ratio is $1/(1/2)=2$, compared with $2/(1/2)=4$ for $s_1$. Substitution givesSetting the nonbasic $s_1,s_4$ to zero gives a feasible integer solution. The final objective row bounds every point in the cut relaxation by $25$, so the integer optimum isBoth cuts are valid for every original integer feasible point, making this also a certificate for the original integer program.