Transportation Problem
• A special class of LP dealing with transportation of goods from sources (e.g.,
factories) to destinations (e.g., warehouses, markets).
Sources Destinations
c11, x11
1 1
node
2 2
.. .. Arc
i j
.. ..
.
m n
cmn, xmn
Network Representation of the transportation model
• Decision: To determine number of units to be shipped from each source to different destinations.
• Objective: To minimize the total shipping cost while satisfying supply and demand requirements.
1
Notations
Parameters
𝑚 : number of sources, indexed as 𝑖
𝑛 : number of destinations, indexed as 𝑗
𝑎𝑖 : supply available at source 𝑖, 𝑖 = 1, 2, … , 𝑚
𝑏𝑗 : demand at destination 𝑗, 𝑗 = 1, 2, … , 𝑛
𝑐𝑖𝑗 : cost of transporting unit item from source 𝑖 to destination 𝑗
Decision
𝑥𝑖𝑗： number of units of item to be shipped from source i to
destination 𝑗, ∀𝑖 = 1,2, … , 𝑚; 𝑗 = 1,2, … , 𝑛
Number of decision variables? : mn
2
Transportation Problem in Tabular Form
Destinations (Demand nodes) Supply
1 2 ⋯ 𝑗 ⋯ 𝑛
𝑐11 𝑐12 𝑐1𝑗 𝑐1𝑛 𝑎1
1 𝑥11 𝑥12 ⋯ 𝑥1𝑗 ⋯ 𝑥1𝑛
𝑐21 𝑐22 𝑐2𝑗 𝑐2𝑛 𝑎2
2 𝑥21 𝑥22 ⋯ 𝑥2𝑗 ⋯ 𝑥2𝑛
⋮
Sources ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
(Supply
𝑐𝑖1 𝑐𝑖2 𝑐𝑖𝑗 𝑐𝑖𝑛 𝑎𝑖
nodes)
𝑖 𝑥𝑖1 𝑥𝑖2 ⋯ 𝑥𝑖𝑗 ⋯ 𝑥𝑖𝑛
⋮
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
𝑐𝑚1 𝑐𝑚2 𝑐𝑚𝑗 𝑐𝑚𝑛 𝑎𝑚
𝑚 𝑥𝑚1 𝑥𝑚2 ⋯ 𝑥𝑚𝑗 ⋯ 𝑥𝑚𝑛
Demand 𝑏1 𝑏2 ⋯ 𝑏𝑗 ⋯ 𝑏𝑚 3
General Formulation
m n
Minimize Z = cij xij
i 1 j 1
Subject to
n
x
j 1
ij ai , i 1, 2,..., m (Supply constraints)
x
i 1
ij b j , j 1, 2,..., n (Demand constraints)
xij 0, i 1, 2,..., m and j 1, 2,..., n
4
Formulation of Balanced Transportation Problem
• For balanced Transportation problem: m n
Total supply =Total demand, i.e.
i 1
ai b j
j 1
m n
Minimize Z = cij xij
i 1 j 1
Subject to
n
x
j 1
ij ai , i 1, 2,..., m (Supply constraints)
x
i 1
ij b j , j 1, 2,..., n (Demand constraints)
xij 0, i 1, 2,..., m and j 1, 2,..., n 5
Example
• Automobile company
Plants: Delhi, Lucknow, Bangalore
Distribution Centres: Jaipur, Hyderabad
• Unit Transportation Cost
Decision Variables
Jaipur (1) Hyderabad (2) Capacity 1 2
Delhi (1) 50 300 1000 1 𝑥11 𝑥12
Lucknow (2) 100 250 1500
2 𝑥21 𝑥22
Bangalore (3) 500 125 1200
3 𝑥31 𝑥32
Demand 2300 1400
Here, Total supply = Total demand = 3700 6
Formulation
Minimize 𝑍 = 50𝑥11 + 300𝑥12 + 100𝑥21 + 250𝑥22 + 500𝑥31 + 125𝑥32
Subject to
𝑥11 + 𝑥12 = 1000
𝑥21 + 𝑥22 = 1500 Supply Constraints
𝑥31 + 𝑥32 = 1200
𝑥11 + 𝑥21 + 𝑥31 = 2300
Demand Constraints
𝑥12 + 𝑥22 + 𝑥32 = 1400
𝑥𝑖𝑗 ≥ 0, ∀𝑖 = 1, 2, 3; 𝑗 = 1, 2
Special Structure
𝑥11 𝑥12 𝑥21 𝑥22 𝑥31 𝑥32
1 1 Supply
1 1 Constraints
Integer Basic
𝐀= 1 1 Feasible solution
1 1 1 Demand
1 1 1 Constraints 7
Number of basic variables
(for a balanced transportation problem)
• Ordinarily, there is one basic variable for each functional constraint in a linear
programming problem. For transportation problems with 𝑚 sources and 𝑛
destinations, the number of functional constraints is 𝑚 + 𝑛. However, the number
of basic variables is (𝑚 + 𝑛 – 1).
• The reason is that the functional constraints are equality constraints, and this set of
𝑚 + 𝑛 equations has one extra (or redundant) equation that can be deleted without
changing the feasible region, i.e. any one of the constraints is automatically
satisfied whenever the other (𝑚 + 𝑛 – 1) constraints are satisfied.
• This fact can be verified by showing that any supply constraint exactly equals the
sum of all demand constraints minus the sum of the other supply constraints, and
that any demand constraint also can be reproduced by summing the supply
constraints and subtracting the other demand constraints.
8
Transportation Simplex method
For feasibility: Transportation problem will have feasible solutions if
and only if m n
ai b j
i 1 j 1
Transportation Simplex
Step 1: Find initial Basic Feasible Solution
Step 2: Is the solution Optimal? If yes, STOP, otherwise go to Step 3
Step 3: Determine entering variable (from non-basic variables).
Step 4: Determine leaving variable (from current basic variables).
Find the new basic solution, and go to Step 2
9
Initial Basic feasible solution
• Integer solutions property: If ai and bj (for all i, j) have integer
value, then all the basic variables will have integer value.
• General Rule for finding initial BFS:
Step 1: Select a cell (i, j) for allocation according to some criteria
(Northwest corner rule, Least cost rule, Vogel’s approximation method)
Step 2: Allocate the amount in the selected cell (i, j) as minimum of
(ai, bj), and adjust the associated amounts of supply and
demand.
Step 3: Cross out the row or column with zero supply or demand. If
both row and column are exhausted simultaneously, cross out
either row or column, and leave a zero supply (demand) in the
uncrossed row (column).
Step 4: If exactly one row or column is left uncrossed, allocate the
remaining amount to its cell according to their supply/demand
10
requirements, and stop. Otherwise, go to Step 1
Example Problem
Destination
1 2 3 4 Supply
10 0 20 11 15
1
Source 12 7 9 20 25
2
0 14 16 18 5
3
Demand 5 15 15 10 45
m n
a b
i 1
i
j 1
j 45
11
Northwest Corner Rule
1. Begin by selecting cell (1,1) (northwest corner of the table)
2. If the last selected cell is (i, j) and source i has any supply remaining, then
select the next cell as (i, j+1) (One column to right), else select cell (i+1, j)
(one row down)
1 2 3 4 Supply
10 0 20 11 15/10
1 5 10
12 7 9 20 25/20/5
2 5 15 5
0 14 16 18 5
3 5
Demand 5 15/5 15 10/5
Initial total cost, Z = 10×5+0×10+7×5+9×15+20×5+18×5 = 410
12
Least Cost Method
• Allocate as much as possible to the cell with the smallest unit cost
(Break tie arbitrarily)
1 2 3 4 Supply
10 0 20 11 0
15/0
1 15
12 7 9 20 25/10
2 15 10
0 14 16 18 5/0
3 5 0
Demand 5 15 15 10
Initial total cost, 𝑍 = 0 × 15 + 11 × 0 + 9 × 15 + 20 × 10 + 0 × 5 + 18 × 0 = 335
13
VOGEL’S APPROXIMATION METHOD
• For each row and column under consideration, calculate penalty as absolute difference
between the two smallest unit cost cij still remaining in that row or column.
• If two cells tie for the minimum cost, the penalty is set at zero.
• Identify row or column with the maximum penalty (break ties arbitrarily) and select the
cell with least cost in the selected row or column.
• Finally, the last row/column is made satisfied according to Least cost method
1 2 3 4 Supply Penalty
10 0 20 11
1 15 0 15/0 10 11 9
12 7 9 20
2 15 10 25/10 2 2 11
0 14 16 18
3 5 0 5/0 14 2 2
Demand 5 15 15 10
Penalty 10 7 7 7
Initial total cost, 𝑍 = 0 × 15 + 11 × 0 + 9 × 15 + 20 × 10 + 0 × 5 + 18 × 0 = 335 14
Summary of NWC Rule and VAM
• NWC: quick and easy
– Far from optimality because no attention to costs
• VAM: popular and gives better initial BFS
– Penalty: minimum extra unit cost for failing to make
an allocation to the cell having smallest unit cost
15
