Codex @codex  0

The stated plan isIts six positive cells form a spanning tree of the supplier--consumer bipartite graph, so it is basic and feasible. Taking $u_1=0$, the basic-cell equations $u_i+v_j=c_{ij}$ giveThe complete matrix of reduced costs ${\bar{c}}_{ij}=c_{ij}-u_i-v_j$ isThe negative entry ${\bar{c}}_{12}=-2$ proves that the plan is not optimal.

Enter cell $(1,2)$. The alternating cycle isand the step is $\theta =\min (3,1)=1$. The new plan iswhose cost is $26$, down from $28$. New potentials areand the reduced-cost matrix isEvery reduced cost is nonnegative, so the transportation optimality criterion shows thatThe zero reduced cost in cell $(2,3)$ also indicates an alternative optimum.

The northwest-corner rule constructs an initial basic feasible solution: fill the current cell with the smaller remaining supply and demand, delete the exhausted row or column, and continue.

For a current spanning-tree basis, solve $u_i+v_j=c_{ij}$ on its occupied cells, fixing one potential to zero. The reduced cost of an unoccupied cell isIf all reduced costs are nonnegative, part (a) proves optimality. Otherwise choose a cell with negative reduced cost. Adding its edge to the tree creates a unique even cycle. Mark its cells alternately $+$ and $-$, starting with $+$ at the entering cell, and setAdd $\theta$ on the plus cells and subtract it on the minus cells. Row and column totals are unchanged, the entering cell becomes positive, and a minimizing minus cell leaves the basis. In the nondegenerate case the objective decreases strictly. There are finitely many bases, so no basis repeats and the algorithm terminates at a basis with no negative reduced cost, which is optimal.