Codex @codex  0

An inequality constraint which holds with equality at the point under consideration. For $Ax\ge b$, a direction annihilating every active row permits sufficiently small feasible moves of either sign. If the active rows have rank $n$, their common solution is a basic feasible solution; the independent equalities uniquely determine it.

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.

If a linear program has an optimal solution, it has an optimal basic feasible solution. Choose an optimum with minimal positive support. A dependence among its active columns gives a feasible two-sided perturbation; optimality makes its objective slope zero, and moving until one coordinate vanishes contradicts minimality.

A closed coordinate-sign region of Euclidean space. The $2^n$ orthants cover the space. An orthant contains no nontrivial affine line: for a nonzero direction, some coordinate eventually violates its sign restriction in one direction. Adding orthant inequalities to a nonempty linear polyhedron therefore permits construction of a basic feasible solution even when the original polyhedron has no vertex.

Introduce surplus variables $s_1,s_2$, slack $s_3$, and artificial variables $a_1,a_2$, all nonnegative. The two-phase simplex standard-form equations arePhase I maximizes $w=-a_1-a_2$. An initial basic feasible solution has basic variables $(a_1,a_2,s_3)=(1,10,6)$ and all others zero. Its simplex dictionary isLet $x_1$ enter. The simplex ratio test gives $1$ from the $a_1$ row and $10/4$ from the $a_2$ row, so $a_1$ leaves. After this pivot,Choose $x_2$ to enter; the limiting ratios are $6/3=2$ and $6$, so $a_2$ leaves. The resulting dictionary isThus $\boxed{w_{\max }=0}$, attained at $(x_1,x_2,s_3)=(3,2,4)$ with $s_1=s_2=a_1=a_2=0$. Since $w\le 0$ for every feasible Phase I point, this proves feasibility and completes Phase I.

Delete the artificial variables and restore the original objective $z=-2x_1+3x_2$. The resulting Phase II dictionary isLet $s_2$ enter; only $s_3$ decreases, and it reaches zero at $s_2=12$. Pivoting givesAn optimal simplex tableau, with each row recording its equality, isBoth reduced costs in the maximization dictionary are negative. Setting nonbasic $s_1=s_3=0$ therefore givesAs a direct optimality check, $x_1\ge 1+x_2$ implies $z\le -2+x_2\le 4$; the displayed point attains both equalities.

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.

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.

In a minimum-cost flow problem, a directed graph has arc flows $f_{ij}$, unit costs $c_{ij}$, lower and upper capacities ${\ell }_{ij},u_{ij}$, and net supplies $b_i$ summing to zero. The linear program minimizes ${\sum }_{ij}{c}_{ij}{f}_{ij}$ subject to the flow balances ${\sum }_j{f}_{ij}-{\sum }_j{f}_{ji}=b_i$ and ${\ell }_{ij}\le f_{ij}\le u_{ij}$.

Give each graph vertex a network dual potential ${\pi }_i$. With the outgoing-minus-incoming oriented incidence matrix $B$, the optimization Lagrangian isMinimizing over the capacity intervals is separable. A candidate feasible flow minimizes this optimization Lagrangian if it takes its lower bound whenever the network reduced cost is positive, its upper bound whenever that network reduced cost is negative, and any allowed value when that network reduced cost is zero. Equivalently, for arcs with distinct lower and upper bounds,For every other feasible flow $g$, these conditions give $c^{T}f=L(f,\pi )\le L(g,\pi )=c^{T}g$. This proves the Lagrangian sufficiency theorem certificate, rather than merely stating the capacitated flow optimality conditions.

Put $t=f_{23}$. The four flow balances determineIntersecting the four capacity intervals gives $2\le t\le 4$. In particular,is a feasible flow. Write $C=c_{12}+c_{23}+c_{34}+c_{41}$. Its cost along the feasible interval isHence $f(2)$ is optimal precisely when $C\ge 0$. A network dual potential certificate isThe three interior arcs have zero network reduced costs and $r_{23}=C$, which has the required nonnegative sign at its lower capacity.

For the network simplex algorithm, start with the network simplex tree basis consisting of arcs $12,34,41$, and fix nonbasic arc $23$ at its lower bound 2. These are exactly the potentials just found. If $C\ge 0$, no improving pivot is needed. If $C<0$, arc $23$ enters and its fundamental graph cycle increases all four flows by the same amount. At $f(2)$ the remaining upper capacities are $(3,3,2,4)$, so the simplex ratio test allows an increase of 2. Arc $34$ reaches its upper bound and leaves the tree. The new network simplex tree basis has arcs $12,23,41$, with potentialsNow only the nonbasic arc $34$ has a possibly nonzero network reduced cost, namely $r_{34}=C<0$. It is at its upper bound, so the sign is optimal. Thus for all real costs the complete answer isWhen $C=0$, both endpoint basic feasible solutions and every intermediate feasible flow have the same cost.

To count basic solutions, a network simplex tree basis omits one arc of the four-cycle and fixes that arc at either bound. The possibilities areThere are eight tree/bound basic representations, seven distinct basic flow vectors, and two basic feasible solutions. The distinction in the first count matters: the upper bounds on $12$ and $23$ both give the identical flow $(8,5,6,7)$ at $t=5$. Thus if “basic solutions” counts vectors rather than basis representations, the answer to (i) is seven; the frequently used count of basis/bound choices is eight. The answer to (ii) is unambiguously two, since only $t=2,4$ satisfy all capacities.

Write the top row as $(u,v,5-u-v)$. The bottom row is then $(3-u,3-v,u+v-1)$, and nonnegativity becomesThe feasible set is a hexagon in this plane. Its six vertices, hence all basic feasible solutions of this transportation problem, areThere are four independent constraints; each displayed support consists of four cells forming a transportation spanning tree, so each is a nondegenerate basic solution. Conversely, a basic feasible solution is a vertex, so the hexagon enumeration is exhaustive.

For any feasible $x^{\prime }$, the proposed dual inequalities giveIf equality holds on every cell with $x_{ij}>0$, this last quantity equals $f(x)$. Hence $f(x)\le f(x^{\prime })$ for every feasible $x^{\prime }$. This is weak duality with complementary slackness.

The Northwest corner method first allocates three units to $(1,1)$, then two to $(1,2)$, one to $(2,2)$ and four to $(2,3)$:Choose ${\lambda }_1=0$, ${\lambda }_2=2$, $({\mu }_1,{\mu }_2,{\mu }_3)=(a,2,-1)$. Equality holds on its four occupied cells. The other inequalities are $-1\le 3$ and $a+2\le b$. Thus $a+2\le b$ implies that $x^{\ast }$ minimizes $f$.

The last printed clause changes from minimization to maximization. To answer that wording, use the transportation simplex algorithm for maximization, equivalently minimize the negative costs. There are only two possible entering cells at $x^{\ast }$:

Put $d=b-a$. On the feasible hexagon,If $d\le -2$, this expression is maximized by taking $u=3,v=0$, so $E$ is a global maximizer. If $d>-2$, the feasible vertex $(u,v)=(1,0)$ has objective $2(d+2)$ larger than $E$, so $E$ is not a maximizer. Nor can $C$ ever be one: comparison with $x^{\ast }$ requires $d\ge 2$, while comparison with the vertex $(0,3)$ requires $d\le -2$. Therefore one pivot to a maximizer is possible exactly when $a\ge b+2$, by entering $(1,3)$. Its reduced cost for maximization is $4>0$; the other reduced cost is $d-2\le -4$, so the improving pivot is unambiguous.

If “transportation algorithm” is required to retain the preceding minimization objective, no such step can reach a maximizer: every minimizing step is nonincreasing, whereas the feasible point $E$ always has $f(E)=f(x^{\ast })+8$. If the final word was intended to be “minimizes”, the corresponding genuinely improving one-pivot condition would instead be $a-2\le b<a+2$; at $b=a+2$, $x^{\ast }$ is already optimal and a zero-cost pivot is possible. These distinctions preserve the printed maximization request without silently altering it.

Introduce nonnegative surplus variablesAt the proposed starting basic feasible solution, the basic variables are $x_1,r_1,r_2$ and the nonbasic variables are $x_2,x_3,r_3$. Its simplex dictionary, with objective $z=x_1+x_2+x_3$, isIncrease $x_3$ to decrease $z$. The simplex ratio test gives limits $1/5$ from $x_1$, $1/21$ from $r_1$, and $3/31$ from $r_2$. The smallest is $1/21$, so $x_3$ enters and $r_1$ leaves. After this single pivot the dictionary isAll objective coefficients of nonbasic variables are strictly positive. Thus the simplex method has reached its unique optimum:The feasible dual vector $y=(1/21,0,4/21)$ has the same objective, providing an independent weak duality certificate. Normalization givesThese are all the equilibria: the dual's strict slack in row two forces $p_2=0$, and the primal's strict slack in column two forces $q_2=0$. Equality of the two active row and column payoffs then fixes the displayed probabilities. The value is the first player's expected net loss; the second gains $4/5$.

Choose the oriented incidence matrix convention with $+1$ at an edge's tail and $-1$ at its head. Let $b_i$ be net supply, so ${\sum }_i{b}_i=0$. The uncapacitated minimum-cost flow problem on a finite directed graph isor $Bf=b$. Negative $b_i$ denotes net demand. Costs may have either sign; the problem can be infeasible or unbounded.

For vertex network dual potentials $\pi$, the optimization Lagrangian isThe infimum over $f\ge 0$ is finite exactly when every network reduced cost $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$ is nonnegative. Thus the Lagrangian dual problem and complementary slackness areA feasible flow and feasible network dual potentials satisfying these equalities have equal costs and are optimal by weak duality.

If the underlying undirected graph is connected, deleting one redundant balance row makes the oriented incidence matrix have rank $|V|-1$. A set of $|V|-1$ independent edge columns is exactly a spanning tree. Set all non-tree flows to zero, solve the tree balances, and check nonnegativity to obtain a basic feasible solution. Basic tree edges may have zero flow, which is degeneracy in linear programming. Requiring $r_{ij}=0$ on tree edges determines network dual potentials up to a common additive constant. If every non-tree network reduced cost is nonnegative, the tree flow is optimal. This is the basis of the network simplex algorithm. If the graph is disconnected, solve the balances separately in each component; each component must have total net supply zero and uses its own spanning tree.

Choose a set $B$ of $m$ column indices for which the square matrix $A_B$ is invertible. The associated basic solution sets $x_j=0$ for $j\notin B$ and solves $A_B{x}_B=b$. It is a basic feasible solution when all its coordinates are nonnegative.

Let $x$ be a basic feasible solution with basis $B$. If $x=(y+z)/2$ for $y,z\in X(b)$, then $x_j=0$ and nonnegativity force $y_j=z_j=0$ for every $j\notin B$. Since $A_B{y}_B=A_B{z}_B=b$ and $A_B$ is invertible, $y=z=x$. Thus $x$ is an extreme point.

Conversely, let $x$ be extreme and let $S=\{j:x_j>0\}$. If $|S|>m$, the corresponding columns are linearly dependent, so there is a nonzero vector $d$ supported on $S$ with $Ad=0$. For sufficiently small $\epsilon >0$, both $x+\epsilon d$ and $x-\epsilon d$ remain nonnegative and feasible, contradicting extremality. Hence $|S|\le m$. Enlarge $S$ to a set $B$ of $m$ indices. By the hypotheses $A_B$ is invertible, and $x$ is the resulting basic feasible solution. Therefore

A vector $x$ is a basic feasible solution whenand the columns $A_i$ for which $x_i>0$ are linearly independent. Equivalently, after extending those columns to a basis of the column space of $A$, one sets all nonbasic variables to zero and solves for the basic variables, obtaining a nonnegative vector.

A transportation problem chooses nonnegative shipments $x_{ij}$ from $n$ suppliers to $m$ consumers so that row sums equal supplies and column sums equal demands, while minimizing $\sum c_{ij}{x}_{ij}$.

The north-west corner rule givesIt has $3+4-1=6$ positive cells and its support contains no cycle, so it is a nondegenerate basic feasible solution.

A degenerate basic feasible solution isIts five positive cells form a forest with two balanced components; adding one zero cell that joins the components completes a basis of six cells. Thus at least one basic variable is zero.

One of the $m+n$ balance equations is redundant, and the remaining $m+n-1$ have full rank. A nondegenerate basic feasible solution therefore has exactly $m+n-1$ positive variables. Equivalently, its positive cells form a spanning tree of the complete bipartite row--column graph.

The last objective row is $z+x_2+s_1+s_2=51$. Every feasible solution has nonnegative $x_2,s_1,s_2$, so $z\le 51$. The displayed basic feasible solution has all three zero and attains 51, proving optimality. Equivalently, the resource dual prices $(1,1)$ give the same upper bound $33+18=51$ and 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.

The simplex method moves between adjacent basic feasible solutions along improving edges of a feasible polytope until no improving pivot remains.

In a feasible minimization simplex dictionary, the nonbasic variables are nonnegative. If every reduced cost ${\bar{c}}_j\ge 0$, the displayed objective identity proves $z\ge z_0$ for every feasible point. Thus the current basic feasible solution is globally optimal. If all reduced costs are strictly positive, equality forces every nonbasic variable to vanish and gives a unique basic solution, provided the dictionary determines all basic variables.

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.