TRANSPORTATION PROBLEM –
BALANCED TRANSPORTATION
PROBLEM
Real-world scenario:
There are n supply stations, each with a capacity of aj tons, where j = 1, n. These goods need to
be transported to m demand stations, each requiring bi tons, where i = 1, m. The cost of
transporting 1 ton of goods from supply station j to demand station i is Cij dollars.
The task is to create a transportation plan such that:
1. All goods from the supply stations are delivered.
2. The demand at each demand station is met.
3. The total transportation cost is minimized.
Representation:
Let Xij (in tons) represent the amount of goods transported from supply station j to demand
station i, where i = 1, m and j = 1, n.
a1 a2 … an
b1
c11 c12 c1n
b2
c21 c22 c2n
bm
cm1 cm2 cmn
Objective:
Minimize the total transportation cost:
∑∑ CijXij → min
Subject to:
∑ Xij = aj (for all j = 1, n) (supply constraints)
∑ Xij = bi (for all i = 1, m) (demand constraints)
Xij ≥ 0 (for all i, j)
Initial Basic Feasible Solution
20 40 70 30 50 20 40 40
50 30
1 4 5 7 1 4 5 7
20 40
9 6 9 3 9 6 9 3
40 20
4 6 1 5 4 6 1 5
50 60
1 2 3 5 1 2 3 5
Northwest Corner Rule:
Step 1: Start with the top-left corner of the transportation matrix and allocate as much as possible
to that cell.
Step 2: Move right if there is remaining capacity in the current row or down if the capacity has
been fulfilled.
Step 3: Repeat until all demands and supplies are met.
Least Cost Method:
Step 1: Select the cell with the smallest cost and allocate as much as possible to that cell.
Step 2: From the remaining cells, choose the next one with the smallest cost and continue the
process.
Step 3: Repeat until all supplies and demands are met.
Improved Solutions
Stepping Stone Method:
Definition: The stepping stone method is based on adjusting the transportation plan by shifting
allocations along a closed loop. This is done to reduce transportation costs iteratively.
For each cell, calculate the opportunity cost Δij:
Δij = ui + vj – cij where ui and vj are the row and column potentials, respectively.
Optimality Test: If Δij ≤ 0 for all unallocated cells, the current solution is optimal.
- ui: row potentials (m rows)
- vj: column potentials (n columns)
- cij: Cost corresponding to selected cell
System of equations with m + n – 1 selected cells
Simplex Method for Transportation:
Step 1: Compute the initial basic feasible solution and calculate row and column potentials.
Step 2: If all opportunity costs Δij ≤ 0, the solution is optimal.
Step 3: If not, adjust the allocation along the closed loop to move towards a better solution.
