Transportation Problem | Sahithyan's Notes

Minimizes the cost of shipping a single commodity from $m$ supply points to $n$ demand points, given a per-unit shipping cost $c_{ij}$ for every supply-demand pair.

\text{minimize } z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij}

Subject to:

$\sum_{j=1}^{n} x_{ij} \le a_i$ for every supply point $i$ (supply capacity)
$\sum_{i=1}^{m} x_{ij} \ge b_j$ for every demand point $j$ (demand requirement)
$x_{ij} \ge 0$

Variations

Balanced

Total supply equals total demand: $\sum_i a_i = \sum_j b_j$ . Every constraint becomes an equality.

A feasible solution exists iff the problem is balanced.

A balanced transportation problem with $m$ supply and $n$ demand points has $m + n - 1$ basic variables in any basic feasible solution (BFS), the most positive allocations a BFS can have.

Balance makes the last of the $m + n$ supply/demand equality constraints redundant, since it follows from the rest once totals match, leaving $m + n - 1$ independent constraints. A basic solution has exactly 1 basic variable per independent constraint.

Unbalanced

Total supply and demand differ. Add a dummy supply point (if demand exceeds supply) or a dummy demand point (if supply exceeds demand) with 0 shipping cost, absorbing the excess, to rebalance it.

The zero-cost dummy route is treated as an ordinary least-cost cell during an initial feasible-solution method. Resolve ties using the adopted tie-breaking rule.

Maximization

Convert to an equivalent minimization problem by negating every cost $c_{ij}$ (or subtracting each from the largest cost in the matrix), then solve as usual.

Restricted

A route is prohibited (e.g. no road between a supply and demand point). Assign it a very large cost $M$ , which drives $x_{ij}$ to 0 in any optimal solution.

Transportation Table

A transportation table lays out a transportation problem as a grid: one row per supply point, one column per demand point.

Conventions:

Cell $(i,j)$ carries the shipping cost $c_{ij}$ and the allocation $x_{ij}$ .
The rightmost column holds each row’s supply $a_i$ .
The bottom row holds each column’s demand $b_j$ .
A cell is occupied when $x_{ij} > 0$ , unoccupied otherwise.

Example, unsolved (only the costs, supply, and demand are known):

	$D_1$	$D_2$	$D_3$	Supply
$O_1$	4	6	8	20
$O_2$	3	5	2	70
$O_3$	3	9	6	25
Demand	30	25	20

Total supply is $115$ , total demand is $75$ : unbalanced.

Loop

A closed path of occupied cells (plus a chosen unoccupied cell) that alternates horizontal and vertical moves, turning only at occupied cells, and returns to the unoccupied cell. Exactly one such loop exists for a given unoccupied cell in a non-degenerate BFS.

Solving Transportation Method

To construct an initial BFS, there are 2 methods. Only 1 is needed to proceed to the stepping stone method.

Least Cost Method

Step:

Allocate as much as possible to the cell with the lowest cost in the matrix.
A tie in the lowest cost is broken by choosing the cell allowing the larger allocation.
Cross out the exhausted row or column.
Repeat on the remaining cells until fully allocated.

Vogel’s Approximation Method

Penalty is the difference between the lowest and second-lowest cost in it.

Steps:

For every remaining row and column, compute the penalty.
Select the row or column with the largest penalty.
A tie is broken by choosing the row or column whose lowest-cost cell allows the larger allocation. If still tied, choose the one with the lower cost in that cell. If that also ties, choose the lowest-indexed row or column.
Allocate as much as possible to its lowest-cost cell in the chosen row or column.
Cross out the exhausted row or column and recompute penalties.
Repeat until fully allocated.

Generally gives a BFS closer to optimal than the least cost method.

When the 2 smallest costs are equal, either of the following penalty conventions is acceptable:

Set the penalty to 0.
Use the difference between the smallest and next smallest costs.

Using the difference is preferred. Both conventions produce a feasible solution.

Stepping Stone Method

Improves an initial BFS to optimality.

For every unoccupied cell, trace its loop.
Alternate $+$ and $-$ signs around the loop, starting with $+$ at the unoccupied cell.
Sum the costs around the loop with their signs. This is the cell’s improvement index.
If every improvement index is $\ge 0$ , the solution is optimal. Stop.
Otherwise, the cell with the most negative improvement index enters the basis.
Shift the minimum allocation among $-$ cells in its loop, adding it at $+$ cells and subtracting it at $-$ cells.
The $-$ cell with the minimum allocation leaves the basis (becomes 0/unoccupied).

Repeat until every improvement index is $\ge 0$ .

When several unoccupied cells have negative improvement indices, select the cell that gives the greatest total cost reduction after multiplying the improvement by the allocatable quantity in its loop. Do not compare the improvement indices alone.

Degenerate BFS

A BFS is degenerate iff it has fewer than $m+n-1$ positive allocations.

A non-degenerate BFS has exactly $m+n-1$ positive allocations. Every unoccupied cell then has exactly 1 loop back to the occupied cells, which the stepping stone method needs to compute improvement indices.

Causes:

Initial allocation
1 allocation exhausts its row and column together. Example: supply $(10,10)$ , demand $(10,10)$ . Allocating $10$ to $(1,1)$ empties row $1$ and column $1$ at once, leaving only 1 more allocation instead of the expected $m+n-1=3$ .
Pivot tie
A pivot’s loop has 2 or more $-$ cells tied at the minimum allocation. Only 1 leaves the basis. The rest drop to $0$ too.

Fix: allocate $0$ to an unoccupied cell that doesn’t close a loop with the occupied cells. This restores the count to $m+n-1$ , and the cell counts as occupied in loops despite shipping nothing.

(m+n-1)-\text{number of occupied cells}=1

then 1 zero allocation is required. Select its location so that the required closed loops can be formed.

A dummy row or column’s allocation is a real basic variable, not a placeholder: it counts toward $m+n-1$ and takes part in loops like any other occupied cell.

Worked Example

Solving the table from Transportation Table. Total supply is $115$ , total demand is $75$ : unbalanced. Add a dummy demand point $D_4$ with demand $40$ and cost $0$ to balance it.

	$D_1$	$D_2$	$D_3$	$D_4$	Supply
$O_1$	4	6	8	0	20
$O_2$	3	5	2	0	70
$O_3$	3	9	6	0	25
Demand	30	25	20	40

Least cost method proceeds as follows:

1 /

occupied cell 0 allocation this step loop path + cell − cell

Lowest cost is 0, tied across the whole dummy column $D_4$ . $O_2 D_4$ allows the largest allocation ( $\min(70,40)=40$ , against $O_1$ ‘s 20 and $O_3$ ‘s 25). Allocate 40. $D_4$ exhausted.

Lowest remaining cost is 2 at $O_2 D_3$ . Allocate $\min(30,20) = 20$ . $D_3$ exhausted.

Lowest remaining cost is 3, tied between $O_2 D_1$ and $O_3 D_1$ . $O_3 D_1$ allows the larger allocation ( $\min(25,30)=25$ against $\min(10,30)=10$ ). Allocate 25. $O_3$ exhausted.

Lowest remaining cost is 3 at $O_2 D_1$ . Allocate $\min(10,5) = 5$ . $D_1$ exhausted.

Lowest remaining cost is 5 at $O_2 D_2$ . Allocate $\min(5,25) = 5$ . $O_2$ exhausted.

	$D_1$	$D_2$	$D_3$	$D_4$	Supply
$O_1$	4	6 20	8	0	0
$O_2$	3 5	5 5	2 20	0 40	0
$O_3$	3 25	9	6	0	0
Demand	0	0	0	0

z = 275

Only $O_1 D_2$ remains. Allocate the remaining 20. 6 basic variables equals $m+n-1$ , non-degenerate.

/* This block is passed through unscoped, so every rule keeps the .walkthrough prefix explicitly. */ .walkthrough [data-live] { display: none; } .walkthrough .stack { display: block; } .walkthrough .stack > .step { opacity: 1; visibility: visible; margin-top: 16px; } .walkthrough .stack .step [data-stage] { display: revert; } .walkthrough .stack .step [data-stage] table { display: revert; } .walkthrough .foot { display: none; }

Vogel’s approximation method proceeds as follows:

1 /

occupied cell 0 allocation this step loop path + cell − cell

	$D_1$	$D_2$	$D_3$	$D_4$	Supply	Penalty
$O_1$	4	6	8	0	20	4
$O_2$	3	5	2	0	70	2
$O_3$	3	9	6	0	25	3
Demand	30	25	20	40
Penalty	0	1	4	0

Row penalties are $O_1 = 4$ , $O_2 = 2$ , $O_3 = 3$ . Column penalties are $D_1 = 0$ , $D_2 = 1$ , $D_3 = 4$ , $D_4 = 0$ . $O_1$ and $D_3$ tie at 4. $O_1$ ‘s lowest-cost cell ( $O_1 D_4$ , cost 0) allows $\min(20,40)=20$ ; $D_3$ ‘s ( $O_2 D_3$ , cost 2) also allows $\min(70,20)=20$ , so the lower cost wins: $O_1$ .

	$D_1$	$D_2$	$D_3$	$D_4$	Supply	Penalty
$O_1$	4	6	8	0 20	0	–
$O_2$	3	5	2	0	70	–
$O_3$	3	9	6	0	25	–
Demand	30	25	20	20
Penalty	–	–	–	–

Allocate 20 to $O_1 D_4$ . $O_1$ exhausted.

	$D_1$	$D_2$	$D_3$	$D_4$	Supply	Penalty
$O_1$	4	6	8	0 20	0	–
$O_2$	3	5	2	0	70	2
$O_3$	3	9	6	0	25	3
Demand	30	25	20	20
Penalty	0	4	4	0

Row penalties are $O_2 = 2$ , $O_3 = 3$ . Column penalties are $D_1 = 0$ , $D_2 = 4$ , $D_3 = 4$ , $D_4 = 0$ . $D_2$ and $D_3$ tie at 4. $D_2$ ‘s lowest-cost cell ( $O_2 D_2$ ) allows $\min(70,25)=25$ , more than $D_3$ ‘s $\min(70,20)=20$ .

	$D_1$	$D_2$	$D_3$	$D_4$	Supply	Penalty
$O_1$	4	6	8	0 20	0	–
$O_2$	3	5 25	2	0	45	–
$O_3$	3	9	6	0	25	–
Demand	30	0	20	20
Penalty	–	–	–	–

Allocate 25 to $O_2 D_2$ . $D_2$ exhausted.

	$D_1$	$D_2$	$D_3$	$D_4$	Supply	Penalty
$O_1$	4	6	8	0 20	0	–
$O_2$	3	5 25	2	0	45	2
$O_3$	3	9	6	0	25	3
Demand	30	0	20	20
Penalty	0	–	4	0

Row penalties are $O_2 = 2$ , $O_3 = 3$ . Column penalties are $D_1 = 0$ , $D_3 = 4$ , $D_4 = 0$ . Largest is $D_3$ (4), whose lowest cost is $O_2 D_3$ (2).

	$D_1$	$D_2$	$D_3$	$D_4$	Supply	Penalty
$O_1$	4	6	8	0 20	0	–
$O_2$	3	5 25	2 20	0	25	–
$O_3$	3	9	6	0	25	–
Demand	30	0	0	20
Penalty	–	–	–	–

Allocate 20 to $O_2 D_3$ . $D_3$ exhausted.

	$D_1$	$D_2$	$D_3$	$D_4$	Supply	Penalty
$O_1$	4	6	8	0 20	0	–
$O_2$	3	5 25	2 20	0	25	3
$O_3$	3	9	6	0	25	3
Demand	30	0	0	20
Penalty	0	–	–	0

Row penalties are $O_2 = 3$ , $O_3 = 3$ . Column penalties are $D_1 = 0$ , $D_4 = 0$ . $O_2$ and $O_3$ tie at 3, and both offer $\min(25,20)=20$ at cost 0 in $D_4$ : tied on every rule, so the lowest-indexed row wins, $O_2$ .

	$D_1$	$D_2$	$D_3$	$D_4$	Supply	Penalty
$O_1$	4	6	8	0 20	0	–
$O_2$	3	5 25	2 20	0 20	5	–
$O_3$	3	9	6	0	25	–
Demand	30	0	0	0
Penalty	–	–	–	–

Allocate 20 to $O_2 D_4$ . $D_4$ exhausted.

	$D_1$	$D_2$	$D_3$	$D_4$	Supply	Penalty
$O_1$	4	6	8	0 20	0	–
$O_2$	3 5	5 25	2 20	0 20	0	–
$O_3$	3	9	6	0	25	–
Demand	25	0	0	0
Penalty	–	–	–	–

Only $D_1$ remains, so no penalty is needed. Allocate $O_2 D_1 = 5$ . $O_2$ exhausted.

	$D_1$	$D_2$	$D_3$	$D_4$	Supply	Penalty
$O_1$	4	6	8	0 20	0	–
$O_2$	3 5	5 25	2 20	0 20	0	–
$O_3$	3 25	9	6	0	0	–
Demand	0	0	0	0
Penalty	–	–	–	–

z = 255

Allocate $O_3 D_1 = 25$ . 6 basic variables equals $m+n-1$ , non-degenerate.

Applying the stepping stone method to the least cost method’s BFS above (occupied cells $O_1 D_2$ , $O_2 D_1$ , $O_2 D_2$ , $O_2 D_3$ , $O_2 D_4$ , $O_3 D_1$ ). Each step below traces the loop for one unoccupied cell, with $+$ and $-$ marking the alternating signs around it.

1 /

occupied cell 0 allocation this step loop path + cell − cell

	$D_1$	$D_2$	$D_3$	$D_4$	Supply
$O_1$	4	6 20	8	0	20
$O_2$	3 5	5 5	2 20	0 40	70
$O_3$	3 25	9	6	0	25
Demand	30	25	20	40

z = 275

Starting from the least cost method’s BFS. Trace the loop of every unoccupied cell to find its improvement index.

	$D_1$	$D_2$	$D_3$	$D_4$	Supply
$O_1$	4 +	6 20 -	8	0	20
$O_2$	3 5 -	5 5 +	2 20	0 40	70
$O_3$	3 25	9	6	0	25
Demand	30	25	20	40

z = 275

Loop $O_1 D_1(+), O_2 D_1(-), O_2 D_2(+), O_1 D_2(-)$ . Improvement index $4 - 3 + 5 - 6 = 0$ .

	$D_1$	$D_2$	$D_3$	$D_4$	Supply
$O_1$	4	6 20 -	8 +	0	20
$O_2$	3 5	5 5 +	2 20 -	0 40	70
$O_3$	3 25	9	6	0	25
Demand	30	25	20	40

z = 275

Loop $O_1 D_3(+), O_1 D_2(-), O_2 D_2(+), O_2 D_3(-)$ . Improvement index $8 - 6 + 5 - 2 = 5$ .

	$D_1$	$D_2$	$D_3$	$D_4$	Supply
$O_1$	4	6 20 -	8	0 +	20
$O_2$	3 5	5 5 +	2 20	0 40 -	70
$O_3$	3 25	9	6	0	25
Demand	30	25	20	40

z = 275

Loop $O_1 D_4(+), O_1 D_2(-), O_2 D_2(+), O_2 D_4(-)$ . Improvement index $0 - 6 + 5 - 0 = -1$ : the most negative so far.

	$D_1$	$D_2$	$D_3$	$D_4$	Supply
$O_1$	4	6 20	8	0	20
$O_2$	3 5 +	5 5 -	2 20	0 40	70
$O_3$	3 25 -	9 +	6	0	25
Demand	30	25	20	40

z = 275

Loop $O_3 D_2(+), O_3 D_1(-), O_2 D_1(+), O_2 D_2(-)$ . Improvement index $9 - 3 + 3 - 5 = 4$ .

	$D_1$	$D_2$	$D_3$	$D_4$	Supply
$O_1$	4	6 20	8	0	20
$O_2$	3 5 +	5 5	2 20 -	0 40	70
$O_3$	3 25 -	9	6 +	0	25
Demand	30	25	20	40

z = 275

Loop $O_3 D_3(+), O_3 D_1(-), O_2 D_1(+), O_2 D_3(-)$ . Improvement index $6 - 3 + 3 - 2 = 4$ .

	$D_1$	$D_2$	$D_3$	$D_4$	Supply
$O_1$	4	6 20	8	0	20
$O_2$	3 5 +	5 5	2 20	0 40 -	70
$O_3$	3 25 -	9	6	0 +	25
Demand	30	25	20	40

z = 275

Loop $O_3 D_4(+), O_3 D_1(-), O_2 D_1(+), O_2 D_4(-)$ . Improvement index $0 - 3 + 3 - 0 = 0$ . Every unoccupied cell is checked: $O_1 D_4$ ‘s $-1$ is the most negative, so it enters the basis.

	$D_1$	$D_2$	$D_3$	$D_4$	Supply
$O_1$	4	6 20 -	8	0 +	20
$O_2$	3 5	5 5 +	2 20	0 40 -	70
$O_3$	3 25	9	6	0	25
Demand	30	25	20	40

z = 275

The minimum allocation among the loop’s $-$ cells is 20, at $O_1 D_2$ . Shift 20 around the loop: add 20 at the $+$ cells, subtract 20 at the $-$ cells.

	$D_1$	$D_2$	$D_3$	$D_4$	Supply
$O_1$	4	6	8	0 20	20
$O_2$	3 5	5 25	2 20	0 20	70
$O_3$	3 25	9	6	0	25
Demand	30	25	20	40

z = 255

$O_1 D_2$ leaves the basis (0/unoccupied), $O_1 D_4$ enters at 20. New cost $z = 275 - 20 = 255$ .

	$D_1$	$D_2$	$D_3$	$D_4$	Supply
$O_1$	4	6	8	0 20	20
$O_2$	3 5	5 25	2 20	0 20	70
$O_3$	3 25	9	6	0	25
Demand	30	25	20	40

z = 255

Recomputing: $O_1 D_1 = 1$ , $O_1 D_2 = 1$ , $O_1 D_3 = 6$ , $O_3 D_2 = 4$ , $O_3 D_3 = 4$ , $O_3 D_4 = 0$ . Every improvement index is $\ge 0$ : optimal at $z = 255$ . $O_3 D_4 = 0$ gives an alternate optimal solution.

This matches Vogel’s approximation method’s result exactly, both in allocations and cost: VAM reached the optimum directly, while the least cost method needed 1 stepping stone iteration to get there.