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.

Continue the simplex algorithm using dictionaries, with nonbasic variables zero at the current vertex. The given basis has payoffThus $x_2$ enters. Its positive row coefficients give ratios $11$ for $z_1$ and $77/4$ for $z_2$; the $x_1$ row does not restrict this increase. Therefore $z_1$ leaves. After that pivot,Now $x_3$ enters. Only the $z_2$ row decreases along this move, and its ratio is $11/11=1$, so $z_2$ leaves. The final dictionary isAll reduced payoff coefficients are nonpositive. Since the slacks must be nonnegative, $f\le 41$, attained with $z=0$. Hence $\boxed{x^{\ast }=(7,22,1),f^{\ast }=41}$. Direct substitution makes all three original constraints equalities. The final dictionary is the optimal tableau expressed with basic variables on the left, not just a proposed feasible vertex.

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.

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.

An equality representation of a linear program in which each basic variable and the objective function are expressed using nonbasic variables, and all variables are nonnegative. Introducing slack variables into $Ax\le b$ gives $s=b-Ax$. Setting the nonbasic variables to zero yields its basic solution; nonnegative resulting basic values make this a basic feasible solution. A simplex algorithm pivot exchanges a basic and nonbasic index and rewrites these expressions.

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.