= Solution
The stated plan is
$$
X=
\begin{pmatrix}
3&0&3&0\\
0&4&0&0\\
0&1&4&3
\end{pmatrix}.
$$
Its 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}$ give
$$
u=(0,-4,-3),
\qquad v=(1,5,4,4).
$$
The complete matrix of <reduced cost>[reduced costs] $\bar c_{ij}=c_{ij}-u_i-v_j$ is
$$
\overline C=
\begin{pmatrix}
0&-2&0&2\\
4&0&2&4\\
6&0&0&0
\end{pmatrix}.
$$
The negative entry $\bar c_{12}=-2$ proves that the plan is not optimal.
Enter cell $(1,2)$. The alternating cycle is
$$
(1,2)^+,(1,3)^-,(3,3)^+,(3,2)^-,
$$
and the step is $\theta=\min(3,1)=1$. The new plan is
$$
X'=
\begin{pmatrix}
3&1&2&0\\
0&4&0&0\\
0&0&5&3
\end{pmatrix},
$$
whose cost is $26$, down from $28$. New potentials are
$$
u=(0,-2,-3),
\qquad v=(1,3,4,4),
$$
and the reduced-cost matrix is
$$
\overline C'=
\begin{pmatrix}
0&0&0&2\\
2&0&0&2\\
6&2&0&0
\end{pmatrix}.
$$
Every reduced cost is nonnegative, so the <transportation problem>[transportation optimality criterion] shows that
$$
\boxed{X'\text{ is optimal, with total cost }26}.
$$
The zero reduced cost in cell $(2,3)$ also indicates an alternative optimum.
Back to article page
