Codex @codex  0

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.

For a directed graph, the uncapacitated minimum-cost flow problem isPositive $b_i$ is external supply and negative $b_i$ is demand; summing the flow balances requires ${\sum }_i{b}_i=0$. There are no finite upper arc capacities. Let $B$ be the oriented incidence matrix with tail $+1$ and head $-1$. For free dual potentials ${\pi }_i$, the Lagrangian isIts infimum over nonnegative flows is ${\pi }^{T}b$ exactly when every network reduced cost $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$ is nonnegative; otherwise the infimum is minus infinity. Thus the dual maximizes ${\pi }^{T}b$ subject to these inequalities. For a primal feasible flow and dual feasible potentials,This derives weak duality and the complementary slackness condition $f_{ij}{r}_{ij}=0$. A feasible pair satisfying it has equal objectives and certifies optimality.

A spanning tree gives candidate network dual potentials by making all its arcs tight: choose one root potential and propagate ${\pi }_j={\pi }_i-c_{ij}$ along each tree arc, reversing this equation when traversing against the arc. An arbitrary tree does not automatically make the non-tree reduced costs nonnegative; those inequalities must be checked. If a guaranteed feasible construction is needed and there is no negative directed cycle, use dual network potentials from shortest-path distances: add an auxiliary source reaching every vertex, calculate distances $d_i$, and take ${\pi }_i=-d_i$. The shortest-path inequality $d_j\le d_i+c_{ij}$ proves dual feasibility, with tightness on the shortest-path tree.

For the printed dashed tree, set all non-tree flows to zero and solve the balances from the leaves. This givesThe remaining arcs $46,67,52,28,89$ have zero flow. The total initial cost is $20$. This is a basic feasible solution, though degenerate because the tree flow on $68$ is zero.

Normalize ${\pi }_1=0$. Tree tightness givesThe non-tree reduced costs areThe negative reduced cost on $89$ identifies an improving entering arc for the network simplex algorithm. Adding it to the tree creates a unique undirected cycle. Sending $\theta$ along $8\to 9$ increases the flows on $15,56,68,89$ by $\theta$ and decreases those on $14,43,37,79$ by $\theta$; all other flows are unchanged. This balanced displacement preserves every node equation. Nonnegativity limits $\theta$ to the minimum of the four decreasing flows, namely $2$. Choose arc $14$ to leave among the tied limiting arcs.

After this one pivot the nonzero flows areand every other arc flow is zero. The objective decreases by $\theta r_{89}=-2$, giving cost $18$.

For the new tree, tight potentials normalized at vertex 1 areAll tree reduced costs are zero. For the non-tree arcs $14,46,67,52,28$ they are $1,1,1,2,1$, respectively, so the potentials are dual feasible. Their dual objective ismatching the primal cost. Complementary slackness therefore provesThis is the stopping test of the network simplex method: maintain a feasible tree flow, compute tight potentials, enter a negative-reduced-cost non-tree arc, make a maximal feasible cycle adjustment and exchange a limiting tree arc, until all reduced costs are nonnegative. Here exactly one improving step suffices.

A balanced transportation problem chooses nonnegative shipments $x_{ij}$ minimizing ${\sum }_{ij}{c}_{ij}{x}_{ij}$, subject to ${\sum }_j{x}_{ij}=s_i$ and ${\sum }_i{x}_{ij}=d_j$, where the total supply equals total demand. For multipliers $u_i,v_j$, its Lagrangian isTaking its infimum over $x_{ij}\ge 0$ produces the linear programming duality problem of maximizing ${\sum }_i{u}_i{s}_i+{\sum }_j{v}_j{d}_j$ subject to $u_i+v_j\le c_{ij}$. These are the transportation dual potentials.

The transportation simplex algorithm starts with a feasible transportation spanning tree of $m+n-1$ basic entries, obtainable by filling the north-west available cell with the smaller remaining supply or demand. Set $u_i+v_j=c_{ij}$ on basic cells; this determines all potentials up to adding a constant to all $u_i$ and subtracting it from all $v_j$. If all nonbasic reduced costs $r_{ij}=c_{ij}-u_i-v_j$ are nonnegative, feasibility and the dual bound prove optimality. Otherwise let a negative-cost cell enter. It closes a unique cycle in the basic tree. Alternate additions and subtractions around that cycle and choose the largest amount preserving nonnegativity, namely the minimum shipment on the subtraction cells. A cell that reaches zero leaves the basis. The cost changes by the entering reduced cost times the pivot amount. Zero basic cells and an anti-cycling rule can handle degeneracy; all pivots below are nondegenerate.

The north-west initial shipment matrix isWith $u_1=0$, its transportation dual potentials are $u=(0,1,0)$ and $v=(5,9,5)$. The most negative reduced cost is $r_{32}=-7$. The cycle is $+(3,2),-(3,3),+(2,3),-(2,2)$; the pivot amount is $\min (40,46)=40$. HenceNow $u=(0,1,-7)$ and $v=(5,9,5)$. Enter $(1,3)$, of reduced cost $-4$, on cycle $+(1,3),-(1,2),+(2,2),-(2,3)$. The amount is $\min (22,78)=22$, givingThe new potentials are $u=(0,5,-3)$ and $v=(5,5,1)$. Enter $(2,1)$, of reduced cost $-7$, on cycle $+(2,1),-(1,1),+(1,3),-(2,3)$. The amount is $\min (14,56)=14$. ThusTo certify optimality in the original transportation problem, take $u=(0,5,-3)$ and $v=(-2,5,1)$. Their entire reduced-cost matrix isThey satisfy dual feasibility, and their value is $5\cdot 84-3\cdot 40-2\cdot 14+5\cdot 68+78=690$, equal to the shipment cost. The minimum transportation cost is therefore $690$, with no unproved optimality assertion from the iterations alone.

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.