Department of Civil engineering, faculty of engineering

Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

A5. Transportation Problem in Linear Programming

The transportation problem is a classic optimization problem in linear programming that deals
with efficiently transporting goods from multiple suppliers to multiple consumers at minimum
cost. It's often used in logistics and supply chain management. The goal is to find the optimal
transportation plan that minimizes the total transportation cost while satisfying supply and
demand constraints.
Formulation of Transportation Problem
Let you are supplying the resources from m source (Si) to n destinations (Dj) such that:
ai: the quantity available at the source Si
bj: the quantity required at the destination Dj
cij: cost of transportation of one unit resource from Si to Dj
xij: units of resources transported from Si to Dj
1<= i <= m, 1 <= j <= n

Fig. 1. Transportation Problem

So, the Total Cost of Transposition is:
(c11x11 + c12x12 + c13x13 + …… + c1nx1n) + (c21x21 + c22x22 + c23x23 + …… + c2nx2n) + …….. +
(cm1xm1 + cm2xm2 + cm3xm3 + …… + cmnxmn)
As we already mentioned, our objective is to minimize the Total Cost:
Min Z = (c11x11 + c12x12 + c13x13 + …… + c1nx1n) + (c21x21 + c22x22 + c23x23 + …… + c2nx2n) +
…….. + (cm1xm1 + cm2xm2 + cm3xm3 + …… + cmnxmn)
Subject to:
xi1 + xi2 + ……. + xin = ai & x1j + x2j + …….. + xmn = bj

1
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

xij >= 0,
i = 1, 2, 3, ……, m, j = 1, 2, 3, ……., n
The below-given matrix can also represent the above diagram.
Table 1.

Types of Transportation Problems

The two categories of transportation problems are balanced and unbalanced transportation
problems.
Balanced Transportation Problem: The problem is considered to be a balanced
transportation problem when both supplies and demands are equal.

Unbalanced Transportation Problem: Unbalanced transportation problem is defined as a

situation in which supply and demand are not equal. A dummy row or a dummy column is
added to this type of problem, depending on the necessity, to make it a balanced problem.
The problem can then be addressed in the same way as the balanced problem.

2
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

Example 1: Check which types of Transportation Problem it is.

Table 2.
Destination
Source Supply
A B C
1 2 7 4 5
2 3 3 1 8
3 5 4 7 7
4 1 6 2 14
Demand 7 9 18

Solution:
Total Supply = 5 + 8 + 7 + 14 = 34
Total Demand = 7 + 9 + 18 = 34
Hence, Total Supply = Total Demand
Therefore, it is a Balanced Transportation Problem.
Example 2: Check whether the given problem is Balanced or Unbalanced.
Table 3.
D1 D2 D3 Availability
S1 4 3 2 10
S2 2 5 0 13
S3 3 8 6 12
Required 8 5 4 --

Solution:
Total Supply = 10 + 13 + 12 = 35
Total Demand = 8 + 5 + 4 = 17
Hence, Total Supply is not equal Total Demand

3
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

Therefore, the given transportation problem is Unbalanced Transportation Problem.

Example 3: Suppose you have three suppliers (S1, S2, S3) with capacities, and three consumers
(C1, C2, C3) with demands. The transportation cost per unit from each supplier to each
consumer is given in the table below:
Table 4.
C1 C2 C3
S1 6 5 7
S2 8 6 4
S3 9 7 4

Objective: Minimize the total transportation cost.

Decision Variables: Let xij represent the quantity of goods transported from supplier i to
consumer j.
Objective Function: Minimize Z = ∑i∑j(cij × xij), where cij is the transportation cost per unit
from supplier i to consumer j.
Constraints:
1. Supply Constraints:
• ∑jxij ≤ Supplyi for each supplier i.
2. Demand Constraints:
• ∑ixij = Demandj for each consumer j.
3. Non-Negativity Constraints:
• xij ≥ 0 for all i,j.
Solution: Using linear programming techniques or optimization solvers, the optimal
transportation plan can be obtained. The solution will provide the quantity of goods to be
transported from each supplier to each consumer, minimizing the total transportation cost.
Sensitivity Analysis:
Sensitivity analysis in the transportation problem involves understanding how changes in
supply, demand, or transportation costs impact the optimal solution. Key elements for
sensitivity analysis include:
1. Changes in Supply or Demand: Increase or decrease in the supply or demand at a
particular location and observe the effect on the optimal solution.
2. Changes in Transportation Costs: Modify the transportation costs and assess the
impact on the optimal solution.

4
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

3. Degeneracy: Check for degeneracy in the solution, where there may be multiple
optimal solutions or unused transportation routes.
4. Shadow Prices (Dual Prices): Interpret the dual prices associated with supply and
demand constraints, providing information on the impact of changes in resource
availability.
Interpretation:
• Optimal Solution: The optimal transportation plan that minimizes the total cost.
• Shadow Prices: Provide insights into the impact of changes in supply or demand on
the total cost.
• Allowable Ranges: Identify how much supply or demand can change without affecting
the optimality of the solution.
• Degeneracy: Check for situations where there are more than one optimal solution or
unused routes.
Example 4: Consider a transportation problem with three suppliers (S1, S2, S3) and three
consumers (C1, C2, C3). The transportation costs, supply, and demand are given as follows:
4 6 8
𝐶𝑜𝑠𝑡 𝑀𝑎𝑡𝑟𝑖𝑥 (𝑐𝑖𝑗 ): [5 7 9 ]
6 8 10
30
𝑆𝑢𝑝𝑝𝑙𝑦 𝑀𝑎𝑡𝑟𝑖𝑥 (𝑠𝑖 ): [50]
70
20
𝐷𝑒𝑚𝑎𝑛𝑑 𝑀𝑎𝑡𝑟𝑖𝑥 (𝑑𝑗 ): [40]
50
Solution Steps:
1. Formulate the LP Problem:
• Define decision variables, objective function, and constraints.
2. Solve the LP Problem:
• Use optimization techniques to find the optimal solution.
3. Interpret the Solution:
• Determine the optimal transportation plan and the minimum total transportation
cost.
Solution Steps in Detail:
1. Formulate the LP Problem:
Objective Function:
Minimize Z = 4x11 + 6x12 + 8x13 + 5x21 + 7x22 + 9x23 + 6x31 + 8x32 + 10x33

5
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

Constraints:
Supply Constraints:
x11 + x12 + x13 = 30
x21 + x22 + x23 = 50
x31 + x32 + x33 = 70
Demand Constraints:
x11 + x21 + x31 = 20
x12 + x22 + x32 = 40
x13 + x23 + x33 = 50
Non-negativity Constraints: xij ≥ 0 for all i,j.
2. Solve the LP Problem:
Use linear programming solvers or algorithms to find the optimal values of xij that minimize
the total transportation cost.
3. Interpret the Solution:
Suppose the optimal solution is found as follows:
𝑥11 𝑥12 𝑥13 20 10 0
𝑂𝑝𝑡𝑖𝑚𝑎𝑙 𝑇𝑟𝑎𝑛𝑠𝑝𝑜𝑟𝑡𝑎𝑡𝑖𝑜𝑛 𝑃𝑙𝑎𝑛: [𝑥21 𝑥22 𝑥23 ] = [ 0 30 20]
𝑥31 𝑥32 𝑥33 10 0 30
Basic Structure of Transportation Problem

In the above table D1, D2, D3 and D4 are the destinations where the products/goods are to be
delivered from different sources S1, S2, S3 and S4. Si is the supply from the source Oi. dj is the
demand of the destination Dj. Cij is the cost when the product is delivered from source Si to
destination Dj.

6
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

Let's consider a simple example to illustrate the transportation problem:

The optimal total transportation cost is calculated using the optimal values of xij.
Methods of Solving Transportation Problems
There are three ways for determining the initial basic feasible solution. They are:
1. NorthWest Corner Cell Method.
Let’s us solve example 4 using this method.
Table 5.
D1 D2 D3 D4 S
O1 20 10 0 0 30

O2 0 30 20 0 50
O3 10 0 30 0 70

D 20 40 50 40 150

Explanation: Given three sources O1, O2 and O3 and four destinations D1, D2, D3 and D4. For
the sources O1, O2 and O3, the supply is 30, 50 and 70 respectively. The destinations D1, D2,
D3 and D4 have demands 20, 40, 50 and 40 respectively.
▪ According to Northwest Corner method, (O1, D1) must be the starting point i.e. the
north-west corner of the table. Each value in the cell is considered as the cost per
transportation.
▪ Compare the demand for column D1 and supply from the source O1 and allocate the
minimum of two to the cell (O1, D1) as shown in Table 7.
▪ The demand for Column D1 is completed so the entire column D1 will be canceled. The
supply from the source O1 remains 30 – 20 = 10.
Table 6.
D1 D2 D3 D4 S

O1 20 10 0 0 30-20=10
(20)
O2 0 30 20 0 50

O3 10 0 30 0 70

D 20 40 50 40 150
0

7
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

Table 7.
D1 D2 D3 D4 S

O1 20 10 0 0 30-20=10
(20) (10) 0
O2 0 30 20 0 50

O3 10 0 30 0 70

D 20 40-10=30 50 40 150
0

Table 8.
D1 D2 D3 D4 S

O1 20 10 0 0 30-20=10
(20) (10) 0
O2 0 30 20 0 50-30=20
(30)
O3 10 0 30 0 70

D 20 40-10=30 50 40 150
0 0

Table 9.
D1 D2 D3 D4 S

O1 20 10 0 0 30-20=10
(20) (10) 0
O2 0 30 20 0 50-30=20
(30) (20) 0
O3 10 0 30 0 70

D 20 40-10=30 50-20=30 40 150

0 0

▪ Proceeding in the same way, the final values of the cells will be:

8
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

Table 10.
D1 D2 D3 D4 S

O1 20 10 0 0 30-20=10
(20) (10) 0
O2 0 30 20 0 50-30=20
(30) (20) 0
O3 10 0 30 0 70-30=40
(30) (40) 0
D 20 40-10=30 50-20=30 40 150
0 0 0 0

▪ Note: In the last remaining cell, the demand for the respective columns and rows are
equal which was cell (O3, D4). In this case, the supply from O3 and the demand for D4
is 40 which was allocated to this cell. At last, nothing remained for any row or column.
Now just multiply the allocated value with the respective cell value (i.e. the cost) and
add all of them to get the feasible (basic) solution i.e. (20 * 20) + (10 * 10) + (30 * 30)
+ (20 * 20) + (30 * 30) + (40 * 0) = 2700
2. Least Call Cell Method (Minimum Cost).
▪ According to the Least Cost Cell method, the least cost among all the cells in the table
must be found which is 6 (i.e. cell (O2, D1)).
▪ Now check the supply from row O2 and demand for column D1 and allocate the smaller
value to the cell. The smaller value is 150 so allocate this to the cell.
Table 11.

D1 D2 D3 D4 S

O1 6 7 8 100
10
(100) 0
O2 4 5 200-150=50
7 13
(150) (50) 0
7 8 300-275=25
O3 7 8
(275) (25) 0
150 100 275 75-50=25
D 600
0 0 0 0

▪ The supply from O2 is completed so cancel this row and the remaining demand for
column D1 is 200 – 150 = 50.

9
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

▪ Now let’s select (O2, D4). Find the demand and supply for the respective cell and
allocate the minimum among them to the cell and cancel the row or column whose
supply or demand becomes 0 after allocation.
▪ If there are two cells among the unallocated cells that have the least cost. Choose any
at random.
▪ Now just multiply the cost of the cell with their respective allocated values and add all
of them to get the feasible (basic) solution i.e. (4 * 150) + (7 * 100) + (7 * 275) + (5 *
50) + (8 * 25) =
3. Vogel’s Approximation Method (VAM).
▪ For each row find the least value and then the second least value and take the absolute
difference of these two least values and write it in the corresponding row difference as
shown in the image below. In row O1, 1 is the least value and 3 is the second least value
and their absolute difference is 2. Similarly, for row O2 and O3, the absolute differences
are 3 and 1 respectively.
▪ For each column find the least value and then the second least value and take the
absolute difference of these two least values then write it in the corresponding column
difference as shown in the figure. In column D1, 2 is the least value and 3 is the second
least value and their absolute difference is 1. Similarly, for column D2, D3 and D4, the
absolute differences are 2, 2 and 2 respectively.
▪ These value of row difference and column difference are also called as penalty. Now
select the maximum penalty. The maximum penalty is 3 i.e. row O2. Now find the cell
with the least cost in row O2 and allocate the minimum among the supply of the
respective row and the demand of the respective column. Demand is smaller than the
supply so allocate the column’s demand i.e. 250 to the cell. Then cancel the column D1.
▪ From the remaining cells, find out the row difference and column difference.
▪ Again, select the maximum penalty which is 3 corresponding to row O1. The least-cost
cell in row O1 is (O1, D2) with cost 1. Allocate the minimum among supply and demand
from the respective row and column to the cell. Cancel the row or column with zero
value.

10
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

Table 12. Row difference

D1 D2 D3 D4 S

O1 1 7 300
3 4 2 3 - -
(300) 0
2 5 400-250=150
O2 6 9 3 1 1 1
(250) (150) 0
O3 500-200=300
3 3 2 1 1 1 0
8 300-50=250
(50) (250) (200) c c c
0
250 350-300=50 400-250=150 200
D 1200
0 0 0 0

1 2 2 2

- 2 2 2
Column
- 3 2 7
difference
- 3 2 -

▪ No balance remains. So, multiply the allocated value of the cells with their
corresponding cell cost and add all to get the final cost i.e. (300 * 1) + (250 * 2) + (50
* 3) + (250 * 3) + (200 * 2) + (150 * 5) = 2850
Optimal solution for a Transportation Problem.
There are two phases to solve the transportation problem. In the first phase, the initial basic
feasible solution must be found, and the second phase involves optimization of the initial basic
feasible solution that was obtained in the first phase.
There are basically two methods in which a transportation problem can be solved:
1. Modified Distribution (MODI) Method – UV Method
MODI Method Steps (Rule)
Step 1: Find an initial basic (feasible) solution using any one of the three methods NWCM,
LCM or VAM.
Step 2: Find ui and vj for rows and columns. To start
▪ assign 0 to ui or vj where maximum number of allocations in a row or column
respectively.
▪ Calculate other ui's and vj's using cij = ui + vj, for all occupied cells.
Step 3: For all unoccupied cells, calculate dij = cij - (ui + vj).
Step 4: Check the sign of dij
▪ If dij > 0, then current basic feasible solution is optimal and stop this procedure.

11
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

▪ If dij = 0 then alternative solution exists, with different set allocation and same
transportation cost. Now stop this procedure
Step 5: Select the unoccupied cell with the largest negative value of dij and include it in the
next solution.
Step 6: Draw a closed path (or loop) from the unoccupied cell (selected in the previous step).
The right angle turn in this path is allowed only at occupied cells and at the original unoccupied
cell. Mark (+) and (-) sign alternatively at each corner, starting from the original unoccupied
cell.
Step 7:
▪ Select the minimum value from cells marked with (-) sign of the closed path.
Assign this value to selected unoccupied cell (So unoccupied cell becomes occupied
cell).
▪ Add this value to the other occupied cells marked with (+) sign.
▪ Subtract this value to the other occupied cells marked with (-) sign.
Step 8: Repeat Step-2 to step-7 until optimal solution is obtained. This procedure stops when
all dij ≥ 0 for unoccupied cells.
Table 13.
D1 D2 D3 D4 Supply
O1 19 (5) 30 50 10 (2) 7
O2 70 30 40 (7) 60 (2) 9
O3 40 8 (8) 70 20 (10) 18
Demand 5 8 7 14

vi
Table 14.
ui
v1 v2 v3 v4

u1 19 10

u2 40 60

u3 8 20

Iteration-1 of optimality test

1. Find ui and vj for all occupied cells (i,j), where cij = ui + vj
▪ Substituting, v4 = 0, we get
c11 = u1 + v1 = 19, v1 = 9
c14 = u1 + v4 = 10, u1 = 10
c23 = u2 + v3 = 40, v3 = -20

12
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

c24 = u2 + v4 = 60, u2 = 60
c32 = u3 + v2 = 8, v2 = -12
c34 = u3 + v4 = 20, u3 = 20
Table 15.
D1 D2 D3 D4 Supply ui
O1 19 (5) 30 50 10 (2) 7 u1 = 10
O2 70 30 40 (7) 60 (2) 9 u2 = 60
O3 40 8 (8) 70 20 (10) 18 u3 = 20
Demand 5 8 7 14
vj v1 = 9 v2 = -12 v3 = -20 v4 = 0

2. Find dij for all unoccupied cells(i,j), where dij = cij - (ui + vj)
▪ d12 = c12 - (u1 + v2) = 30 - (10 - 12) = 32
▪ d13 = c13 - (u1 + v3) = 50 - (10 - 20) = 60
▪ d21 = c21 -(u2 + v1) = 70 -(60 + 9) = 1
▪ d22 = c22 - (u2 + v2) = 30 - (60 - 12) = -18
▪ d31 = c31 - (u3 + v1) = 40 - (20 + 9) = 11
▪ d33 = c33 - (u3 + v3) = 70 - (20 - 20) = 70
Table 16.

D1 D2 D3 D4 Supply ui

O1 19 (5) 30 [32] 50 [60] 10 (2) 7 u1 = 10

O2 70 [1] 30 [-18] 40 (7) 60 (2) 9 u2 = 60

O3 40 [11] 8 (8) 70 [70] 20 (10) 18 u3 = 20

Demand 5 8 7 14

vj v1 = 9 v2 = -12 v3 = -20 v4 = 0

3. Now choose the minimum negative value from all dij (opportunity cost) = d22 = [-18]
and draw a closed path from S2D2.
Closed path is O2D2→O2D4→O3D4→O3D2.
Closed path and plus/minus sign allocation...

13
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

Table 17.
D1 D2 D3 D4 Supply ui
O1 19 (5) 30 [32] 50 [60] 10 (2) 7 u1 = 10
O2 70 [1] 30 [-18] (+) 40 (7) 60 (2) (-) 9 u2 = 60
O3 40 [11] 8 (8) (-) 70 [70] 20 (10) (+) 18 u3 = 20
Demand 5 8 7 14
vj v1 = 9 v2 = -12 v3 = -20 v4 = 0

4. Minimum allocated value among all negative position (-) on closed path = 2
Subtract 2 from all (-) and add it to all (+)
Table 18.
D1 D2 D3 D4 Supply
O1 19 (5) 30 50 10 (2) 7
O2 70 30 (2) 40 (7) 60 9
O3 40 8 (6) 70 20 (12) 18
Demand 5 8 7 14

5. Repeat steps 1 to 4, until an optimal solution is obtained.

Iteration-2 of optimality test
1. Find ui and vj for all occupied cells(i,j), where cij = ui + vj
Substituting, u1=0, we get
▪ c11 = u1 + v1⇒ v1 = c11 - u1 ⇒ v1 = 19 – 0 ⇒ v1 =19
▪ c14 = u1 + v4 ⇒ v4 = c14 - u1 ⇒ v4 = 10 – 0 ⇒ v4 = 10
▪ c34 = u3 + v4 ⇒ u3 = c34 - v4 ⇒ u3 = 20 – 10 ⇒ u3 = 10
▪ c32 = u3 + v2 ⇒ v2 = c32 - u3 ⇒ v2 = 8 – 10 ⇒ v2 = -2
▪ c22 = u2 + v2 ⇒ u2 = c22 - v2 ⇒ u2 = 30 + 2 ⇒ u2 = 32
▪ c23 = u2 + v3 ⇒ v3 = c23 - u2 ⇒ v3 = 40 – 32 ⇒ v3 = 8
Table 19.
D1 D2 D3 D4 Supply ui
O1 19 (5) 30 50 10 (2) 7 u1 = 0
O2 70 30 (2) 40 (7) 60 9 u2 = 32
O3 40 8 (6) 70 20 (12) 18 u3 = 10
Demand 5 8 7 14
vj v1 = 19 v2 = -2 v3 = 8 v4 = 10

2. Find dij for all unoccupied cells(i,j), where dij = cij - (ui + vj)
▪ d12 = c12 - (u1 + v2) = 30 - (0 - 2) = 32

14
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

▪ d13 = c13 -(u1 + v3) = 50 - (0 + 8) = 42

▪ d21 = c21 - (u2 + v1) = 70 - (32+19) = 19
▪ d24 = c24 - (u2 + v4) = 60 - (32 + 10) = 18
▪ d31 = c31 - (u3 + v1) = 40 - (10 + 19) = 11
▪ d33 = c33 - (u3 + v3) = 70 - (10 + 8) = 52
Table 20.
D1 D2 D3 D4 Supply ui
O1 19 (5) 30 [32] 50 [42] 10 (2) 7 u1 = 0
O2 70 [19] 30 (2) 40 (7) 60 [18] 9 u2 = 32
O3 40 [11] 8 (6) 70 [52] 20 (12) 18 u3 = 10
Demand 5 8 7 14
Vj v1 = 19 v2 = -2 v3 = 8 v4 = 10

Since all dij ≥ 0.

So final optimal solution is arrived.
Table 21.
D1 D2 D3 D4 Supply
O1 19 (5) 30 50 10 (2) 7
O2 70 30 (2) 40 (7) 60 9
O3 40 8 (6) 70 20 (12) 18
Demand 5 8 7 14

The minimum total transportation cost =19 × 5 + 10 × 2 + 30 × 2 + 40 × 7 + 8 × 6 + 20 × 12 =

743
2. Steppingstone Method Steps
Step 1: Find an initial basic feasible solution using any one of the three methods NWCM, LCM
or VAM.
Step 2:
▪ Draw a closed path (or loop) from an unoccupied cell. The right angle turn in this path
is allowed only at occupied cells and at the original unoccupied cell. Mark (+) and (-)
sign alternatively at each corner, starting from the original unoccupied cell.
▪ Add the transportation costs of each cell traced in the closed path. This is called net cost
change.
▪ Repeat this for all other unoccupied cells.

15
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

Step 3:
▪ If all the net cost change are ≥0, an optimal solution has been reached. Now stop this
procedure.
▪ If not, then select the unoccupied cell having the highest negative net cost change and
draw a closed path.
Step 4:
▪ Select minimum allocated value among all negative position (-) on closed path.
▪ Assign this value to selected unoccupied cell (So unoccupied cell becomes occupied
cell).
▪ Add this value to the other occupied cells marked with (+) sign.
▪ Subtract this value to the other occupied cells marked with (-) sign.
Step 5: Repeat Step-2 to step-4 until optimal solution is obtained. This procedure stops when
all net cost change ≥ 0 for unoccupied cells.
Example: Find the basic (feasible) solution using Voggel's Approximation method and find
the optimal solution using steppingstone method.
Table 22.
D1 D2 D3 D4 Supply
O1 19 30 50 10 7
O2 70 30 40 60 9
O3 40 8 70 20 18
Demand 5 8 7 14
Solution:
Optimality test using steppingstone method...
Table 23.

D1 D2 D3 D4 Supply

O1 19 (5) 30 50 10 (2) 7

O2 70 30 40 (7) 60 (2) 9

O3 40 8 (8) 70 20 (10) 18

Demand 5 8 7 14

16
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

Iteration-1 of optimality test

1. Create closed loop for unoccupied cells, we get
Table 24.
Unoccupied cell Closed path Net cost change
O1D2 O1D2→O1D4→O3D4→O3D2 30 - 10 + 20 - 8 = 32
O1D3 O1D3→ O1 D4→O2 D4→O2D3 50 - 10 + 60 - 40 = 60
O2D1 O2D1→O2D4→O1D4→ O1D1 70 - 60 + 10 - 19 = 1
O2D2 O2D2→O2D4→O3D4→O3D2 30 - 60 + 20 - 8 = -18
O3D1 O3D1→O3D4→ O1D4→ O1 D1 40 - 20 + 10 - 19 = 11
O3D3 O3D3→ O3D4→ O2D4→ O2D3 70 - 20 + 60 - 40 = 70

2. Select the unoccupied cell having the highest negative net cost change i.e. cell O2D2 = -18
and draw a closed path from O2D2. Therefore, the closed path is O2D2→O2D4→O3D4→O3D2.
Closed path and plus/minus allocation for current unoccupied cell O2D2.
Table 25.

D1 D2 D3 D4 Supply

O1 19 (5) 30 [32] 50 [60] 10 (2) 7

O2 70 [1] 30 [-18] (+) 40 (7) 60 (2) (-) 9

O3 40 [11] 8 (8) (-) 70 [70] 20 (10) (+) 18

Demand 5 8 7 14

3. Minimum allocated value among all negative position (-) on closed path = 2
Subtract 2 from all (-) and add it to all (+)
Table 26.

D1 D2 D3 D4 Supply

O1 19 (5) 30 50 10 (2) 7

O2 70 30 (2) 40 (7) 60 9

O3 40 8 (6) 70 20 (12) 18

Demand 5 8 7 14

4. Repeat the step 1 to 3, until an optimal solution is obtained.

Iteration-2 of optimality test
1. Create closed loop for unoccupied cells, we get

17
 Department of Civil engineering, faculty of engineering
Quantitative Techniques (CIV 8341) prepared by Engr. Dr. A. D. Rafindadi

Table 27.
Unoccupied cell Closed path Net cost change
O1D2 O1D2→O1D4→O3D4→O3D2 30 - 10 + 20 - 8 = 32
O1D3 O1D3→O1D4→O3D4→O3D2→O2D2→O2D3 50 - 10 + 20 - 8 + 30 - 40 = 42
O2D1 O2D1→O2D2→O3D2→O3D4→O1D4→O1D1 70 - 30 + 8 - 20 + 10 - 19 = 19
O2D4 O2D4→O2D2→O3D2→O3D4 60 - 30 + 8 - 20 = 18
O3D1 O3D1→O3D4→O1D4→O1D1 40 - 20 + 10 - 19 = 11
O3D3 O3D3→O3D2→O2D2→O2D3 70 - 8 + 30 - 40 = 52

Since all net cost change ≥ 0

So, the final optimal solution is obtained.
Table 28.

D1 D2 D3 D4 Supply

O1 19 (5) 30 50 10 (2) 7

O2 70 30 (2) 40 (7) 60 9

O3 40 8 (6) 70 20 (12) 18

Demand 5 8 7 14

The minimum total transportation cost =19×5+10×2+30×2+40×7+8×6+20×12=743

References
1. Lewis, James P. 2023. Project Planning, Scheduling, and Control: The Ultimate Hands-On Guide to
Bringing Projects in On Time and On Budget. 6th ed. New York: McGraw Hill.
https://www.accessengineeringlibrary.com/content/book/9781264286270
2. K. N. Jha, Construction project management: Theory and practice. Pearson Education India, 2011.
3. P. Roy, Principles of construction management, McGraw-HillBook Company, 1992.
4. C. S. Park and G. P. Sharp, Advanced engineering economics. John Wiley & Sons, 2021.
5. Weglarz, J. (Ed.). (2012). Project scheduling: recent models, algorithms and applications (Vol. 14).
Springer Science & Business Media.
6. Zhou, J., Love, P. E., Wang, X., Teo, K. L., & Irani, Z. (2013). A review of methods and algorithms for
optimising construction scheduling. Journal of the Operational Research Society, 64(8), 1091-1105.

18