OPERATIONS RESEARCH -

DISTRIBUTION MODELS:
Transportation and Assignment Problems
 INTRODUCTION

Distribution Models
This chapter describes two special –purpose algorithms: the transportation
model and the assignment model. Model formulation and manual solution
are covered for each of these classes of problems.
 TRANSPORTATION PROBLEM/MODEL
Transportation problem deals with the distribution of goods from point of supply to point of
demand
• Aim: To determine the optimum transportation schedule that minimizes total transportation
cost / time or maximize total profit.
• The problem can be represented by a net work flow diagram and function (model)
• Efficient solution algorithms exist to solve network problems
Characteristics of Transportation Problems
i. It is assumed that the commodities/goods are homogeneous so that a destination can
receive its demand from one or more sources
ii. A limited supply of one commodity is available at certain sources or origins.
iii. There are m sources and n destinations
iv. number of variables in the model is m x n
v. number of constraints is m + n (constraints are for source capacity and destination
demand)
vi. There is a demand for a commodity at several destinations
vii. The quantities of supply at each source and the demand at each destination are
constant.
viii. Costs appear only in objective function (objective is to minimize total cost of shipping)
 Characteristics Cont’d
ix. The shipping or transportation costs per unit from each source to each destination
are assumed to be constant.
x. coefficients of decision variables in the constraints are either 0 or 1
xi. No shipments are allowed between sources or between destinations.
xii. The problem is to determine how many units to transport from each source to each
destination so that all destination demands are satisfied and total transportation costs
are minimized.
 TRANSPORTATION MODEL cont’d

Objective Of Transportation Problem:

1. To identify the optimal shipping routes-minimum cost route
2. To identify the maximum amount that can be shipped over the optimum route
3. To determine the total transportation cost or the profit of transportation
Steps of Transportation Method
I. Formulate the problem and set up in the matrix form
II. Obtain an initial basic feasible solution (NWCM, LCM, VAM). Feasibility:
allocations must be = m+n-1
III. Test the initial solution for optimality (Stepping stone method, MODI method)
IV. Determine new solution (Stepping stone method)
V. Repeat steps III and IV until an optimal solution is reached
 The problem can be represented in the form of transportation table:

Warehouses, j W1 W2 W3 Wn Capacity
(sj)
Factories,i
F1 X11, C11 X12,C12 X13, C13 X1n, C1n s1

F2 .. .. .. ..

F3 .. .. .. ..

Fm Xm1, Cm1 .. .. Xmn, Cmn sn

Requirement d1 .. .. dn 
(di)
m = no of origins/sources/rows n= no of destinations/columns, demand centers
 Example:
Suppose that a firm has three factories /sources of supply/ & four warehouses /point
of demand/. The firm's production capacity at the three factories, the demand for the
four distribution centers located at various regions & the cost of shipping each unit
from the factories to the warehouses through each route is given as follows:
Production centers Demand/Destination center
Origin Factories Production Destination Destination DD forecast
(sources) Capacity (units) center
1 F1 5000 1 W1 6000
2 F2 6000 2 W2 4000
3 F3 2500
3 W3 200
Total supply 13, 500
4 W4 1500
Total demand 13,500
m= number of origins/sources of supply
n= number of destination/dd centers
• Express the transportation problem as a LPP if management would like to
determine how much of its production should be shipped from each plant to
each destination center at a minimum cost.
 Example: cont’d
The cost of shipping each unit from the factories to the warehouses through each
route is given as follows.
Transportation cost per unit

Origin, i Destination (Warehouses), j Factory capacity

W1 W2 W3 W4 (SS), Si
F1 C11 = 3 2 7 6 5000
F2 7 C22 = 5 2 3 6000
F3 2 5 4 5 2500
Warehouse requirement 6000 4000 2000 1500 13500
(units of DD), bi

• Express the transportation problem as a LPP if management would like to

determine how much of its production should be shipped from each plant to
each destination center at a minimum cost.
• Determine an optimal shipping schedule (plan) that minimizes the total
transportation cost.
Transportation Problem
• Network representation of transportation problem

C11 3 1 D1
S1 1
5000 C12 2 6000

c14
C13 7 2 D2
c21
c22 4000
S2 2 c23
6000 c24
3 D3
c31 2000
c32
c33

S3 3 c34
4 D4
2500
1500
SOURCES
DESTINATIONS
Formulation of TP as LPP
• How do we formulate TP as an LP?
• Let xij = quantity of product to be shipped from source i to destination j
• Let cij = cost of shipping/unit from source i to destination j
• Let si be the row i total supply
• Let dj be the column j total demand
• The LPM formulation of the TP problem is:
Let Xij be the amounts shipped from the origin i to the destination j
Min Z = cijxij (Objective Function)
Subject to
xij < si for each origin i (Capacity Constraint)
xij > dj for each destination j (Requirement Constraint)
xij > 0 for all i and j (Non Negativity Restriction)
 Example:
Min z = 3 x11 + 2x12 + 7x13 + 6x14 + 7 x21 + 5x22 + 2x23 +….. + 5x34
Subject to
x11 + x12 + x13 + x14 ≤ 5000 (F1 supply constraint)
x21 + x22 + x23 + x24≤ 6000 (F2 supply constraint)
x31 + x32 + x33 + x34≤ 2500 (F3 supply constraint)
x11 + x21 + x31 ≤ 6000 (W1 demand constraint)
x12 + x22 + x32 ≤ 4000 (W2 demand constraint)
x13 + x23 + x33 ≤ 2000 (W3 demand constraint)
x14 + x24 + x34 ≤ 1500 (W4 demand constraint)

xij ≥ 0 for i = 1, 2, 3 and j = 1, 2, 3,4 (nonnegativity)

Origin/ Factory
source Warehouses/ destination Capacity
W1 W2 W3 W4 /Supply
F1 3 2 7 6
5000

F2 7 5 2 3
6000

F3 2 5 4 5
2500

Demand
6000 4000 2000 1500 13500

Balanced transportation problem!

SOLUTION MECHANISM
• The transportation problem is solved in two phases:
• Phase I — Obtaining an initial feasible solution
• Phase II — Moving toward optimality
• Phase I: Finding the initial solution
• North West Corner Method
• Least Cost Method/ Largest profit method
• Vogel’s Approximation (penalty) Method
• Phase II: Testing optimality and finding optimal solution
• Stepping Stone Method
• MODI (Modified Distribution) Method- Testing optimality
SPECIAL CASES IN TRANSPORTATION
• Alternative Optimum Solutions
• Unbalanced Transportation Problems
• When Supply exceeds Demand
• When Demand exceeds Supply
• Degeneracy in Transportation Problem
• Prohibited Routes
• Profit maximization in a Transportation Problem
 SPECIAL CASES IN TRANSPORTATION PROBLEM

• Degeneracy in Transportation Problem

Any basic feasible solution having less then (m +n – 1) non-negative allocations is
called a degenerate solution.
• Unbalanced Transportation Problems
• When Supply exceeds Demand
• When Demand exceeds Supply
To solve the transportation problem by its special purpose algorithm, it is required
that the sum of the supplies at the origins equal the sum of the demands at the
destinations. If the total supply is greater than the total demand, a dummy
destination is added with demand equal to the excess supply, and shipping costs
from all origins are zero. Similarly, if total supply is less than total demand, a dummy
origin is added.
• Prohibited Routes
When solving a transportation problem by its special purpose algorithm,
unacceptable shipping routes are given a cost of +M (a large number).
• Profit maximization in a Transportation Problem
Finding an initial feasible solution – Phase I
NORTH- WEST CORNER METHOD (NWCM)/ Algorithm
• NWCM starts the solution/ allocation process in the Upper Left-Hand (Northwest)
corner ( Cell 1,1) of the transportation tableau, the reason for its name. When starting
the solution, allocate to the Northwest corner as many units as possible.
• This method does not take into account the cost of transportation in starting the
solution.
Northwest corner rule (From the reading material)
• 1. Begin with the upper left hand cell (Left, upper most in the table), & allocate as
many units as possible to that cell. This will be the smaller amount of either the row
supply or the column demand. Adjust the row & column quantities to reflect the
allocation.
• 2. Subtract from the row supply & from the column demand the amount allocated
• 3. If the column demand is now zero, move to the cell next to the right, if the row supply
is zero, move down to the cell in the next row. If both are zero, move first to the next
cell on the right then down one cell.
• 4. Once a cell is identified as per step (3), it becomes a northwest cell. Allocate to it an
amount as per step (1)
• 5. Repeat, the above steps (1) - (4) until all the remaining supply and demand is gone.
 Example
Suppose that a firm has three factories / sources of supply /& four warehouses/point of
demand/.The firm's production capacity at the three factories, the demand for the four
destination centers located at various regions & the cost of shipping each unit from the
factories to the warehouses through each route is given as follows:

Origin/ Warehouses/ destination Factory

source Capacity
W1 W2 W3 W4 /Supply
F1 3 2 7 6 5000
F2 7 5 2 3 6000
F3 2 5 4 5 2500
Demand 6000 4000 2000 1500 13500
Develop an initial feasible solution using NWCM & Compute the total cost
Example Cont’d

Origin/ Warehouses/ destination Factory

source Capacity
W1 W2 W3 W4 /Supply
F1 5000 3 2 7 6 5000
F2 7 5 2 3 6000 5000
1000 4000 1000 1000
F3 2 5 4 1500 5 2500 1500
1000
Demand 6000 4000 2000 1500 13500
1000 1000
Is the initial solution basic? A solution is basic when m+n-1 of the
cells contain an allocation/ m+n-1 of the routes are in use
initial solution is basic b/c m+n-1 = 3=4-1 =6 routes are in use or 6
cells are occupied or have an allocation.
Total cost of initial feasible solution using the NMCR

Route Units Cost/unit Total cost on

From To Shipped the routes
F1 W1 X11 =5000 3 15000

F2 W1 X21 =1000 7 7000

F2 W2 X22 =4000 5 20000

F2 W3 X23 =1000 2 2000

F3 W3 X33 =1000 4 4000

F3 W4 X34 =1500 5 7500

Total transportation cost 55,500

 Finding an initial feasible solution – Phase I
Minimum-Cost Method (simple)
• Step 1:
Select the cell or route with the least cost. Assign as many units as possible i.e., the
minimum of its row supply or column demand to this cell. If a tie exists, choose the one over
which the largest quantity can be shipped.
• Step 2:
Adjust the row supply and column demand by the amount allocated in step 1. If both are
simultaneously reduced to 0, assign an allocation of 0 to any other bordering unoccupied
cell in the row or column.
Step 3.
If row ss and / or column dd are satisfied cross out either of them or both from further
consideration by drawing a line over it.
Step 4.
Repeat the above steps until all row supplies have exhausted and column demands have
been met

• Consider the previous example and

• Cost is relevant in making the allocation unlike the NWCR!!!!!
 Example Cont’d

Origin/ Warehouses/ destination Factory

source Capacity
W1 W2 W3 W4 /Supply
F1 1000 3 4000 2 7 6 5000 1000
2500
F2 2500 7 5 2 1500 3 6000 4000
2000
F3 2500 2 5 4 5 2500
Demand 6000 4000 2000 1500 13500
3500 2500
Is the initial solution basic? A solution is basic when m+n-1 of the
cells contain an allocation/ m+n-1 of the routes are in use
initial solution is basic b/c m+n-1 = 3+4-1 =6 routes are in use or 6
Total cost of initial feasible solution using the MCM
Route Units Cost/unit Total cost on
From To Shipped the routes
F1 W1 X11 =1000 3 3000

F1 W2 X12 =4000 2 8000

F2 W1 X21 =2500 7 17500

F2 W3 X23 =2000 2 4000

F2 W4 X24 =1500 3 4500

F3 W1 X31 =2500 2 5000

Total transportation cost 42,000

Note that the total cost of the initial solution is $42,000 which is less than the cost of initial
solution obtained using the NWC method ($55,500)
 Finding initial feasible solution
VOGEL'S APPROXIMATION METHOD (VAM) or PENALTY METHOD
• This method involves a determining a penalty for not using a route or
assigning a resource to a requirement or destination with minimum
transportation cost /unit.
• The objective is to make an initial allocation such that the penalties from
not using the routes are minimized. This can be done by allocating
resources to the requirements so as to avoid large penalties.
• For maximization, we are provided with profit/unit and we deduct the
next maximum from the maximum to calculate the opportunity loss
 Finding initial feasible solution
VOGEL'S APPROXIMATION METHOD (VAM) or PENALTY METHOD
The steps in VAM for minimization problems are as follows:
1. Calculate penalties for each row (column) by subtracting the smallest
from the next smallest unit transportation cost in the same row
(column)
2. Select the row or column with the largest penalty & allocate as much
unit as possible in the cell having the least cost in the selected row or
column satisfying the conditions. If there is a tie in the values of
penalties, then it can be broken by selecting the cell where maximum
allocation can be made.
3. Adjust the supply & demand & cross out the satisfied row or column. If a
row or column is satisfied simultaneously, only one of them is crossed
out & the remaining row (column) is assigned a zero supply (demand).
Any row or column with zero supply or demand should not be used in
computing future penalties.
4. Repeat step 1 to 3 until the entire available supply at various sources &
demand at various destinations are satisfied.
 Example
Suppose that a firm has three factories / sources of supply /& four warehouses/point of
demand/.The firm's production capacity at the three factories, the demand for the four
destination centers located at various regions & the cost of shipping each unit from the
factories to the warehouses through each route is given as follows:

Origin/ Factory
Warehouses/ destination
source Capacity
W1 W2 W3 W4 /Supply
F1 3 2 7 6 5000
F2 7 5 2 3 6000
F3 2 5 4 5 2500
Demand 6000 4000 2000 1500 13500

Develop an initial feasible solution using VAM & Compute the total cost
 Example

Origin/ Factory
Warehouses/ destination
source Capacity
W1 W2 W3 W4 /Supply Penalty
F1 1000 3 4000 2 7 6 5000 13
1000
F2 2500 7 5 2000 2 1500 3 6000
2500 1
F3 2 5 4 5 2500
2500 2
Demand 6000 4000 2000 1500 13500
2500 5000
Penalty 1 5 3 2 2

initial solution is basic b/c m+n-1 = 3=4-1 =6 routes are in use or 6

cells are occupied or have an allocation.
Total cost of initial feasible solution using the VAM
Route Units Cost/unit Total cost on
From To Shipped the routes
F1 W1 X11 =1000 3 3000

F1 W2 X12 =4000 2 8000

F2 W1 X21 =2500 7 17500

F2 W3 X23 =2000 2 4000

F2 W4 X24 =1500 3 4500

F3 W1 X31 =2500 2 5000

Total transportation cost 42,000

Note that the total cost of the initial solution by the MCM and VAM are identical in this example. This
is usually the case in a relatively small problems even though this is not a general rule.
Phase II: OPTIMALITY TESTS - Moving towards optimality
• Once an initial solution is available, the next step is to check its optimality. An
optimal solution is one in which there is no opportunity cost. That is, there is no
other set of transportation routes (allocations) that will reduce the total
opportunity cost. Thus we have to evaluate each unoccupied cell (represents
unused route) in the transportation table in terms of opportunity cost.
• The purpose of the optimality test is to see if the proposed solution just
generated can be improved or not. The solution to be checked for optimality
must be non-degenerate i.e the no of occupied cells must be m+n-1 ( Basic
feasible solution).
• For each empty cell, the effect of changing it to an occupied cell is examined. If
any of these changes are favorable, the solution is not optimal & a new solution
must be designed. A favorable change means an increase in the value of the
objective function in maximization problems or a decrease in minimization
problems.
• Optimum solution to a TP can be obtained by following two methods. These
methods are much simpler compared to simplex method of a LPP.
A. Stepping stone Method
B. Modified Distribution method (MODI Method)
 Cont’d
A. STEPPING-STONE ALGORITHM/ METHOD

• The Stepping-stone method is an iterative technique for moving from

an initial feasible solution to an optimal solution in transportation
problems.
• For the stepping- stone method to be applied to a transportation
problem, one rule about the no of shipping routes being used must be
observed. The rule is:
• “The No of occupied routes (or cells) must always be equal to one
less than the sum of the no of rows plus the no of columns."
i.e. Occupied shipping routes ( squares) = m +n-1 Non
degenerate solution or basic feasible solution
 OPTIMALITY TESTS - STEPPING-STONE METHOD Cont’d
OPTIMALITY TESTS
A. STEPPING-STONE METHOD
Rules for drawing each closed loop/path:
1. Select an unused route(cell) to be evaluated.
2. Begin at this cell, trace a closed loop/ path between the unoccupied
cell and occupied cells by alternating + and – sign and connecting
them by an arrow to indicate the direction of the allocation/movement.
3. Move vertically or horizontally (but never diagonally) to another
occupied cell “stepping –over” unoccupied or occupied cells (if
necessary) without changing them. Follow the same procedure to other
occupied cells until returning to the original empty cell.
4. Begin with a plus (+) sign at the unused cell, place alternative (-) signs
and plus signs on each cell/corner square of the closed path just
traced. i.e At each turn of the loop ( the loop may cross over itself at
times), plus and minus signs are alternately placed in the cells, starting
with a + sign in an empty cell.
 STEPPING-STONE METHOD Cont’d

5. There must be exactly one cell with a + sign and exactly one cell
with a - sign in any row or column in which the loop turns.
6. An even no of at least four cells must participate in a loop and the
occupied cells can be visited once and only once.
7. Repeat steps 1 to 4 until an improvement index has been calculated for
all unused routes or squares (cells). If all indices computed are greater
than or equal to zero, an optimal solution has been reached. If not, it is
possible to improve the current solution and decrease total shipping
costs.
Note:
• In a non-degenerate problem, there is only one possible way of drawing
the loop for each empty cell.
 STEPPING-STONE METHOD Cont’d
How to find the value of a cell evaluator
• The value of a cell evaluator is the sum of the per unit shipping costs in the
gaining cells less the sum of the per unit shipping costs in the losing cells of the
closed loop. This evaluation process must be extended to all unoccupied cells.
1. The test of optimality for a minimization (cost) problem:
• If one or more of the cell evaluators is negative, the existing solution is not
optimal. i.e: For minimization (cost) problems, all the cell evaluators must be
positive for optimality.

Analysis of test: Check all the empty cells and select for improvement the one
with the largest improvement potential.
• If the solution is not optimal, the next step in the transportation method is to
find a better solution. The operations in this step are:
a. Identify the “incoming" cell (the empty cell to be occupied). In a minimization
case, the incoming cell is located by identifying the most negative cell
evaluator.
b. Design an improved solution -By shifting units form cell to cell
STEPPING-STONE METHOD Cont’d
How to find the value of a cell evaluator
2. The test of optimality for a maximization (profit) case:
: Is the reverse of minimization case
-If one or more of the cell evaluators is positive, the existing solution is not optimal.
i.e: for a maximization (profit) case, all the cell evaluators must be negative for
optimality. If any cell evaluation is positive, the solution is not optimal.
Note:
• A cell evaluator of 0 indicates the existence of another solution just as good as the
current solution. Thus, in the final solution, if cell evaluators of 0 exist, this indicates
the existence of multiple optimal solutions.
• If two or more cells have the same value, then either may be selected.
• If two or more of the "losing" cells contain the same no of units, both will become
empty simultaneously and a “degenerate" solution will result.
• For the minimization case; when one or more cell evaluators are negatives, the cell
with the largest negative should be brought into solution because that route has the
largest potential for improvement per unit.
• The loop starts and ends at the selected unoccupied cell. Every corner element of
the loop must be an occupied cell.
Initial feasible solution by the MCM or VAM

Origin/ Warehouses/ destination Factory

source Capacity
W1 W2 W3 W4 /Supply
F1 -
1000
+ 3 - 2 + 7 6 5000
4000 9 7
+
F2 2500 - 7 + 5 - 2 1500 3 6000
-1 2000
F3 2500 2 4 5 4 5 2500
7 7
Demand 6000 4000 2000 1500 13500

Is the initial solution basic? A solution is basic when m+n-1 of the

cells contain an allocation/ m+n-1 of the routes are in use
initial solution is basic b/c m+n-1 = 3=4-1 =6 routes are in use or 6
cells are occupied or have an allocation.
STEPPING-STONE METHOD Cont’d

Test of optimality
• F2W2 = F2W2-F1W2+F1W1- F2W1 = 5-2+3-7 = -1.
• F1W3 = F1W3-F2W3+F2W1-F1W1 = 7-2+7-3 =+9
• F1W4 = F1W4-F2W4+F2W1-F1W1 = 6-3+7-3 =+7
• F3W4 = F3W4-F2W4+F2W1-F3W1 = 5-3+7-2 =+7
• F3W3 = F3W3-F2W3+F2W1-F3W1 = 4-2+7-2 =+7
• F3W2 = F3W2-F1W2+F1W1-F3W1 = 5-2+3-2 =+4
 Second feasible solution by the stepping stone method
Origin/ Factory
Warehouses/ destination
source Capacity
W1 W2 W3 W4 /Supply
F1 3500 3 1500 2 8
7 6
6 5000
F2 1
7 2500 5 2000 2 1500 3 6000
F3 2500 2 4
5 4 6
5 2500
6
Demand 6000 4000 2000 1500 13500
The solution is basic b/c m+n-1 = 3=4-1 =6 routes are in use
Is the solution optimal? The stepping stone algorithm is applied to evaluate the
unoccupied cells
F2W1 = F2W1-F1W1+F1W2-F2W2 = 7-3+2-5 = 1 F3W3 = F3W3-F2W3+F2W2-F1W2+F1W
F1W3 = F1W3-F1W2+F2W2-F2W3 =7-2+5-2 = 8 = 4-2+5-2+3-2 = 6
F1W4 = F1W4-F1W2+F2W2-F2W4 =6-2+5-3 = 6 F3W4 =F3W4-F2W4+F2W2-F1W2+F1W1-F3W1
F3W2 = F2W4-F1W2+F1W1-F1W1 = 5-2+3-2 = 4 = 5-3+5-2+3-2 = 6
The solution is optimal because all the evaluations are non negative
Optimal solution with its total cost by the stepping stone method
Route Units Cost/unit Total cost on
From To Shipped the routes
F1 W1 X11 =3500 3 10500

F1 W2 X12 =1500 2 3000

F2 W2 X22 =2500 5 12500

F2 W3 X23 =2000 2 4000

F2 W4 X24 =1500 3 4500

F3 W1 X31 =2500 2 5000

Total transportation cost 39,500

.
TRANSPORTATION MODEL -OPTIMALITY TESTS
B. MODIFIED DISTRIBUTION METHOD (MODI METHOD)
• MODI is another algorithm for testing a basic feasible solution to a
transportation problem.
• MODI method offers an alternative (simple, time saving) approach for
evaluating the unoccupied cells in the transportation tableau.
• The method requires defining an index for each row and column of the
tableau. A row index is labeled Ui and column index labeled Vj. The numerical
values of Ui and Vj are calculated from the equation: ∆ij or Kij = Cij– (Ui + Vj);
for all i and j (∆ij or Kij = Cij– Ui - Vj); for all i and j. Where ∆ij or Kij
represents the net change in the O.F. of the transportation problem from
reallocating one unit to cell (ij) and Cij represents the transportation cost/unit
from origin i to destination j. Note that for occupied cells, ∆ij = Cij-Ui-Vj =0
• The values of these indices are found by requiring that the cost coefficient for
each occupied cell equal Ui+Vj, i.e., Ui+Vj = Cij for occupied cell.
MODI Method Cont’d
• The MODI method allows us to compute improvement indices quickly for
each unused cell with out drawing all of the closed paths.
• Once the largest negative index is identified, we are required to trace only
one closed path. Just as with the stepping-stone approach, this path
helps to determine the maximum No of units that can be shipped via the
best unused route.
 Cont’d

Steps in the MODI Method

The steps to evaluate unoccupied cells are as follows:
1. For an initial basic feasible solution, calculate Ui and Vj ; for rows and
columns and set

Cij = Ui + Vj for all occupied calls (i , j)

i.e: Cell cost = Raw Index +Column Index

2. For unoccupied cells, calculate opportunity cost by using the

relation:

∆ij or Kij = Cij– (Ui + Vj) or Cij– Ui - Vj; for all i and j.
Where Kij is the cell evaluator or opportunity cost
 Cont’d
3. Examine the sign of each Kij
For minimization case:
• If Kij > 0, then current basic feasible solution is optimal.
• If Kij = 0, then the current basic feasible solution will remain
unaffected but an alternative solution exists.
• If one or more Kij < 0, then an improved solution exists and
unoccupied cell (i, j) with the largest or most negative evaluation
(value) enters the basis when one occupied cell (route) leaves the
basis resulting in a new solution mix or new transportation
schedule.
4. To determine a new improved solution use the stepping-stone
method.to construct a closed path (or loop) for the unoccupied cell
with largest negative opportunity cost
5. Obtain a new improved solution by allocating units to the unoccupied
cell and calculate the new transportation cost.
6. Test the revised solution for optimality using above steps
For occupied cells
F1-W1 U1 +V1 =3
F1-W2 U1+V2 =2
F2-W2 U2+V2 =5
F2-W3 U2+V3 =2
F2-W4 U2+V4 =3
F3-W1 U3+V1 =2
The system has m=6 equations and n=7 variables. Therefore, in order to obtain a unique
solution, one of the variables must be specified or set equal to zero. In the modified distribution
algorithm U1 is customarily specified as equaling zero. So we shall always set U1 = 0 and solve
for the others. Setting U1 = 0, we get the following
0 +V1 =3, V1= 3
0+V2 =2, V2= 2
U2+V2=5, U2= 3
U2+V3=2, V3= -1
U2+V4=3, V4= 0
U3+V1=2, U3= -1
Therefore U1 =0, U2 =3, U3=-1 and V1= 3, V2= 2, V3= -1, V4= 0
Now the change in the O.F, ( the per unit change in the total cost) from reallocating one unit to
the unoccupied cell in row i and column j must be calculated using
∆ij = Cij-Ui-Vj formula in order to examine whether further improvement of the solution is
possible.
Second feasible solution by the stepping stone method
Origin/ Factory
Warehouses/ destination
source Capacity
W1 W2 W3 W4 /Supply Ui
F1 3500 3 1500 2 7 6 5000 0
F2 7 2500 5 2000 2 1500 3 6000 3
F3 2500 2 5 4 5 2500 -1
Demand 6000 4000 2000 1500 13500
Vj 3 2 -1 0

The solution is basic b/c m+n-1 = 3=4-1 =6 routes are in use, is the solution optimal?
 Second feasible solution by the stepping stone method
Origin/ Factory
Warehouses/ destination
source Capacity
W1 W2 W3 W4 /Supply Ui
F1 3500 3 1500 2 8 7 6 6 5000 0
F2 1 7 2500 5 2000 2 1500 3 6000 3
F3 2500 2 4 5 6
4 6
5 2500 -1
Demand 6000 4000 2000 1500 13500
Vj 3 2 -1 0
The solution is basic b/c m+n-1 = 3=4-1 =6 routes are in use
Is the solution optimal?
The stepping stone algorithm verified that the solution is optimal but we will
evaluate it using MODI method!!!!! is applied to evaluate the unoccupied cells
∆13 = C13-U1-V3 = 7-0-(-1) = 8, ∆13 = C14-U1-V4 = 6-0-(-0) = 6
Winding up earlier discussions
• NWCR, MCM, VAM are used to determine the initial feasible solution,
maintain feasible solution is basic that m+n-1 principle
• The stepping stone method is used to determine:
• Which route to consider or bring in to solution
• Which route to remove from solution
• The maximum amount of shipment over the new route
• The MODI method: Provides easier way to determine only which route to
consider or bring in to solution (used only for cell/route evaluation purpose)

Maximization objective function case

• The above methods can also be used to solve maximization problems if we
are provided with the profit contribution/unit of transportation.
• The only modification is to allocate units to unoccupied cells with the largest
∆ij value (select a route with the largest per unit increase in the objective
function). Difference is in the test of optimality.
• Then proceed with the usual procedure to obtain the optimal solution.
Degeneracy
• A condition that occurs when the No of occupied cells in any solutions less
than the No of rows plus the No of columns minus 1 in a transportation
table.
• The degeneracy in the transportation problems may occur at two stages:
• when obtaining an initial solution
• During improvement (or at any stage while moving to wards
optimal solution.
• To resolve degeneracy, we allocate a very small quantity close to zero to
one or more unoccupied cell so as to get m+n-1 number of occupied
cells. This amount is denoted by a Greek letter  (epsilon) or (delta).
This quantity would not affect the total cost as well as supply and
demand values.
 = Almost zero
TRANSPORTATION MODEL
Degeneracy
Example :
. Use NWCM to find initial feasible solution and test the solution for
optimality using MODI method.

A B Supply
3 3

F1 50
4 6
F2
30
Demand 50 30 80
Alternative Optimal solutions
• Alternative optimal solution can be determined by an inspection of the
opportunity costs, Kij for the unoccupied cells. If an unoccupied cell in an
optimal solution has opportunity cost of zero (∆ij =0), then an alternative
optimal solution can be formed with another set of allocations without
increasing the total transportation cost.
Prohibited Transportation Routes
• The situation may arise due to road hazards (snow, flood, etc), traffic
regulation, strikes etc, when it is not possible to transport goods from
certain sources to certain destinations. In this case, the appropriate cell
may either be completely crossed out or a very large per unit
transportation cost must be assigned to it (M) for minimization or a very
large –ve profit (-M) for maximization.
• Balancing unbalanced model/problem
• Unbalanced problem occurs when total dd and total ss are unequal. In
such a case, the unbalanced problem is converted to a balanced one as
follows
i) SS< DD , a fictitious/dummy source/ supply row is created and added to
absorb the unsatisfied dd, The fictitious supply row is created with zero
transportation cost/unit
ii) DD<SS or SS>DD, we add a fictitious/dummy destination ) dd column
to absorb the excess supply with zero transportation cost/unit
 Exercise
Suppose that a firm has three factories / sources of supply /& four warehouses/point of
demand/.The cost of manufacturing a given product is the same at each of the factories.
Because of the locations of the warehouses and factories, the cost of shipping the product
from the different factories to the warehouses varies. The capacity of the factories per
month, the requirements of the warehouses per month, and the transportation cost/unit are
presented below.

Origin/
source Warehouses/ destination
W1 W2 W3 W4 Supply
F1 15 24 11 12 5000
F2 25 20 14 16 4000
F3 12 16 22 13 7000
Demand 3000 2500 3500 4000 16000
13000

I) Formulate the problem as a balanced transportation problem

II) Develop an initial feasible solution using MCM (a) by defining minimum cost as
zero (b) by defining minimum cost as non-zero
III) Determine the optimal solution by using MODI for cell evaluation and stepping
stone algorithm for new solution