= Solution
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 gives
$$
X_{NW}=
\begin{pmatrix}
3&3&0&0\\
0&2&2&0\\
0&0&5&3
\end{pmatrix}.
$$
It 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 is
$$
\boxed{
X_D=
\begin{pmatrix}
3&0&3&0\\
0&0&4&0\\
0&5&0&3
\end{pmatrix}}.
$$
Its 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.
Back to article page
