Transportation problems

Explanation

• A transportation problem sends goods from $m$ sources, each with a fixed supply, to $n$ destinations, each with a fixed demand, at a known cost per unit for every route. The problem must first be balanced: if total supply exceeds total demand, add a dummy destination whose demand is the difference and whose transport costs are all zero;
• if demand exceeds supply, add a dummy source in the same way. The north-west corner method then builds a first feasible solution without looking at any cost. Start at the upper-left cell and send as many units as possible, which is the smaller of the row's remaining supply and the column's remaining demand.
• If the supply runs out, move down one row; if the demand runs out, move right one column. Repeat until every supply and every demand is used up.
• A non-degenerate solution occupies exactly $m+n-1$ cells, and if the method exhausts a row and a column at the same time it leaves fewer occupied cells than that, so a zero must be entered in an adjacent cell to keep the count right.
• The cost of the solution is the sum of each allocation multiplied by its unit cost.

Explanation

• Once a basic feasible solution is in place, shadow costs test whether it can be improved. Set $R_1=0$ and solve $R_i+K_j=C_{ij}$ for every occupied cell, which is possible exactly when $m+n-1$ cells are occupied.
• The improvement index of an unoccupied cell is $I_{ij}=C_{ij}-R_i-K_j$: it is the change in total cost caused by sending one unit along that route. A negative index means the route would save money, so the solution is not optimal; when every index is non-negative the solution is optimal.
• To improve it, choose the entering cell with the most negative index and trace the stepping-stone route: a closed cycle of horizontal and vertical moves through occupied cells, alternately adding and subtracting the same amount $\theta$.
• The value of $\theta$ is the smallest allocation in a subtracting cell, and that cell is the exiting cell, which becomes empty.
• The new cost is the old cost plus $\theta$ times the entering cell's improvement index.

Explanation

• A transportation problem with $m$ sources and $n$ destinations is a linear program in $mn$ variables. Let $x_{ij}$ be the number of units sent from source $i$ to destination $j$, so there is one variable per cell of the cost table.
• The objective is to minimise total cost, $\sum_i\sum_j C_{ij}x_{ij}$, written out in full as a linear expression. Each source gives one constraint, $\sum_j x_{ij}\leqslant s_i$, saying that the row cannot ship more than its supply, and each destination gives one constraint, $\sum_i x_{ij}\geqslant d_j$, saying that the column must receive at least its demand.
• When the problem is balanced every supply constraint is met with equality at the optimum, so the inequalities may equally be written as equations.
• Finally every variable is non-negative.
• The linear program therefore has $mn$ variables and $m+n$ constraints besides non-negativity, and a dummy row or column adds a further $n$ or $m$ variables with zero cost coefficients.