Codex @codex  0

A basic feasible solution is degenerate when one or more of its basic variables is zero. A simplex algorithm pivot may then change the basis without moving the feasible point or changing the objective. Assignment networks force many zero-flow basic tree arcs.

The network simplex algorithm specializes the simplex algorithm to network flows. A basis is represented by a spanning tree with nonbasic flows at their bounds; potentials give reduced costs, and entering arcs produce cycle pivots. Degeneracy in linear programming is particularly common in assignment instances.

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.

Write the absolute-value constraint asIntroduce slacks $s_1,s_2,s_3$. In the simplex algorithm, let $x_2$ enter and $s_2$ leave, then let $x_1$ enter and $s_3$ leave. The final dictionary isThus

For sufficiently small perturbations, the same two constraints remain active:Solving givesand therefore the perturbed optimal value is

Introduce slack variables $s_1,s_2,s_3$. In the initial simplex algorithm dictionary, $x_2$ has the largest positive objective coefficient. The ratio test givesso $x_2$ enters and $s_3$ leaves. Solving the third constraint for $x_2$ givesThe objective becomesEvery reduced cost is now nonpositive, so the simplex optimality criterion givesThe other two slacks both equal one.

The dual linear program isThe vectoris dual feasible and has objective value $12$. By weak duality, it and the displayed primal point are optimal; they also satisfy complementary slackness.

A simplex dictionary expresses the basic variables and the objective as affine functions of the nonbasic variables in a linear program. Setting the nonbasic variables to zero gives a basic feasible solution when all basic values are nonnegative. A simplex algorithm pivot exchanges one basic and one nonbasic variable. For maximization, a feasible dictionary with all nonbasic objective coefficients nonpositive certifies optimality.

A slack variable turns an inequality constraint $a^{T}x\le b$ into the equality $a^{T}x+s=b$ with $s\ge 0$. Its value measures the unused amount of the constraint. In the simplex algorithm, slack variables often supply the initial basic feasible solution.