Codex @codex  0

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.

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

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:

Introduce nonnegative slack variables $s_i$ and write $z=c^{\mathsf{T}}x$. A maximizing simplex dictionary is dual feasible when every nonbasic coefficient in the objective is nonpositive. After inserting a constraint, the dual simplex algorithm retains this property while repairing any negative basic value. For a leaving row $x_B=\beta +{\sum }_j{d}_j{x}_j$ with $\beta <0$, only $d_j>0$ can enter; choose a column minimizing the ratio of its objective penalty to $d_j$.

For the first linear program, $x_1$ has the best profit-to-resource ratio. Pivot it into the initial slack basis to obtainAll basic values are nonnegative and all reduced costs are nonpositive, so the optimal point is $(5,0,0,0)$, with value five. Adding the second constraint givesThe same basis remains feasible and optimal: the second constraint does not change the answer.

The third constraint gives the new rowThe current dictionary is dual feasible but primal infeasible. The eligible entering variables are $x_3,x_4$, with dual ratio-test values $2$ and $3$ respectively. Enter $x_3$ and leave $s_3$; solving that row and substituting into the old rows yieldsThis is a feasible optimal simplex dictionary. Thus the new optimal point is $(2,0,1,0)$, with value three. As an independent linear programming optimality certificate, dual multipliers $(3,0,2)$ have weighted objective bound $3\cdot 5+2(-6)=3$ and weighted coefficient row $(1,4,1,2)$, which dominates the profit row.

On inserting the fourth constraint the slack isIt has a negative constant and no eligible entering column. Since all its nonbasic variables are nonnegative, this row cannot be satisfied: the fourth linear program is infeasible, and adding the fifth constraint cannot restore feasibility. The requested optimal values are therefore

The arbitrary-data selection question is a maximum feasible subsystem problem. With rational input it is in NP: guess the selected row indices, and test their linear programming feasibility in polynomial time. Equivalently, a nonempty rational polyhedron has a feasible rational point of polynomially bounded encoding length, which serves as a certificate.

For an explicit NP-hardness reduction, take an independent set instance with graph $H$ having $r$ vertices and desired independent-set size $K$. Use variables $x_v\ge 0$, one inequality $-x_v\le -1$ for each vertex, and $M=r+1$ identical copies of $x_u+x_v\le 1$ for each edge. Ask for a feasible subsystem of size $M|E(H)|+K$. An independent set of size $K$ gives such a subsystem: include all edge rows and those $K$ vertex rows, and use its indicator vector. Conversely, omitting every copy of even one edge row leaves at most $M(|E(H)|-1)+r<M|E(H)|+K$ selectable rows. Hence any qualifying subsystem retains every edge inequality and at least $K$ vertex inequalities. Their vertices must be independent, since two adjacent selected vertices would force $x_u+x_v\ge 2$. The construction has polynomial size; $c$ is irrelevant to feasibility. Thus the rational-input decision problem is NP-complete, not merely difficult because there are many subsets to enumerate.

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.

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.