Codex @codex  0

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.

Use the transportation simplex algorithm, with transportation dual potentials $u_i,v_j$ and reduced costs $r_{ij}=c_{ij}-u_i-v_j$. On a basic cell choose $u_i+v_j=c_{ij}$. The initial shipment matrix, read from the circled entries in the PDF, isIts six positive cells form a transportation spanning tree. Setting $u_1=0$ givesEnter cell $(1,1)$, whose reduced cost is $-6$. The cycle pivot has signsThe maximum feasible increment is $\theta =\min (5,4)=4$, so cell $(4,1)$ leaves the basis. The result isFor the new transportation spanning tree,Enter cell $(2,3)$ with reduced cost $-4$. Its cycle pivot isNow $\theta =\min (5,1)=1$, and cell $(1,3)$ leaves. We obtainIts row sums are $(12,5,7,12)$ and its column sums $(9,14,13)$, as required. The final transportation dual potentials areAll reduced costs are nonnegative, proving optimality. More explicitly, for any feasible shipment matrix $X$,Our shipments use only zero-reduced-cost cells and attain this lower bound. This supplies an independent weak duality certificate for the transportation optimum.

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.

Row and column potentials satisfying the displayed inequalities give a lower bound on the cost of every feasible shipment matrix: ${\sum }_{ij}{c}_{ij}{x}_{ij}\ge {\sum }_i{u}_i{s}_i+{\sum }_j{v}_j{d}_j$, since row sums are supplies $s_i$ and column sums are demands $d_j$. The reduced costs are $c_{ij}-u_i-v_j$. A feasible matrix using only zero-reduced-cost cells attains the lower bound, proving optimality by weak duality. The transportation simplex algorithm sets these potentials by equality on a transportation spanning tree, and enters a negative-reduced-cost cell if one exists.