TRANSPORTATION

The places where the goods originate from

(the plants in our example) are called the
sources or the origins and places where they
are to be supplied are the destinations. In this
terminology, the problem of the manufacturer
is to decide as to how many units be
transported from different origins to different
destinations so that the total transportation
cost is the minimum.

Transportation Problem
PROBLEM STATEMENT
 Transportation Problem as a Special Case of LPP
Ques: A firm owns facilities at seven places. It has manufacturing plants at A, B, and C with
daily output of 500, 300 and 200 units of an item respectively. It has warehouses at P, Q, R
and S with daily requirement of 180, 150, 350 and 320 units respectively. The transportation
charges per unit on different routes are given below

The firm wants to send the output from various plants to warehouses involving minimum
transportation cost. How should it route the product so as to achieve its objective?
The LPP at hand would involve 18 variables in all - 12 decision variables and 6 artificial
variables. To solve it would need to carry out at least 6 iterations on a matrix of the order 6 x
18. It makes it virtually impossible (when working manually) to use simplex method for solving
even this moderate-sized problem.
Solution To Transportation Problem Transportation Method
Solution To Transportation Problem Transportation Method
 Solution To Transportation Problem Transportation Method
Step 1: Obtaining the Initial Feasible Solution
The first step in using the transportation method is to obtain a feasible solution, namely, the
one that satisfies the rim requirements (i.e. the requirements of demand and supply). The
initial feasible solution can be obtained by several methods. The commonly used are:
1. The North-West Corner (NWC) Rule,
2. Least Cost Method (LCM) and
3. The Vogel's Approximation Method (VAM).
In case of a tie in the largest cost difference, although either of them may be
chosen, it is preferable to choose the cost difference corresponding to which the
largest number of units may be assigned or corresponding to which the cell
chosen has minimum cost.
(i) The Vogel's approximation method is also called the Penalty
Method because the cost differences that it uses are nothing
but the penalties of not using the least-cost routes. Since the
objective function is the minimisation of the transportation
cost, in each iteration that route is selected which involves the
maximum penalty of not being used.
(ii) The initial solution obtained by VAM is found to be the best
of all as it involves the lowest total cost among all the three
initial solutions. Of course, it does not come as a rule, but
usually VAM provides the best initial solution. Therefore, this
method is generally preferred in solving the problems.
 Solution To Transportation Problem Transportation Method
Step 2: Testing the Optimality
• After obtaining the initial basic feasible solution, the next step is to test whether it is optimal
or not.
• There are two methods of testing the optimality of a basic feasible solution. One of these is
called the stepping-stone method in which optimality test is applied by calculating the
opportunity cost of each empty cell. The other method is called as the modified distribution
method (MODI). This one is easier to apply and more efficient than the stepping-stone
method. It is based on the concept of dual variables that are used to evaluate the empty cells.
Using these dual variables, the opportunity cost of each of the empty cells is determined.
• Thus, while both the methods involve determining opportunity costs of empty cells, the
methodology employed by them differs. The opportunity cost values indicate whether the
given solution is optimal or not.
 Solution To Transportation Problem Transportation Method
Step 3: Improving the Solution
• By applying either of the methods, if the solution is found to be optimal, then the process
terminates as the problem is solved.
• If the solution is not seen to be optimal, then a revised and improved basic feasible solution is
obtained. This is done by exchanging a non-basic variable for a basic variable. In simple terms,
rearrangement is made by transferring units from an occupied cell to an empty cell that has
the largest opportunity cost, and then adjusting the units in other related cells in a way that
all the rim requirements are satisfied. This is done by first tracing a closed loop.
• The solution so obtained is again tested for optimality (step 2) and revised, if necessary. We
continue in this manner until an optimal solution is finally obtained.
 Stepping-stone Method

Initial Basic Feasible

Solution by NWC

Each of the non-basic variables (empty cells) is considered one by one

AS = 13-12+8-14 = -5
Saving of Rs.5
Since the opportunity cost of
all the empty cells are
negative, the solution
obtained is optimal
Modified Distribution Method (MODI)
Initial Basic Feasible Solution by NWC
 Some Special Topics
1. Unbalanced Transportation Problems
2. Prohibited Routes
3. Unique vs Multiple Optimal Solutions
4. Degeneracy
5. Maximisation Problems
 Some Special Topics
• Unbalanced Transportation Problems

• Prohibited Routes

• Unique vs Multiple Optimal Solutions

Obtain Initial Basic Feasible Solution (IBFS) through VAM
Test for Optimality using MODI
 Some Special Topics
• Degeneracy
We have already seen that a basic feasible solution of a transportation problem has m + n —
1 basic variables, which means that the number of occupied cells in such a solution is one
less than the number of rows plus the number of columns. It may happen sometimes that
the number of occupied cells is smaller than m + n — 1. Such a solution is called a
degenerate solution.

Degeneracy in a transportation problem can figure in two ways. Degeneracy can arise in the
first instance when an initial feasible solution is obtained (see Example 5.3). Secondly,
the problem may become degenerate when two or more cells are vacated simultaneously in
the process of transferring units along the closed path.
 Some Special Topics
5. Maximisation Problem
 Sensitivity Analysis
(a) Change in the objective function coefficient of a non-basic variable —
which means a change in the cost element of an unoccupied cell.
(b) Change in the objective function coefficient of a basic variable — a
change in the cost element of an occupied cell.
(c) Changing a particular source supply and a particular destination demand by
a given amount.
(d) Setting upper or lower limits on the values of xij variables. In other words,
the effect of a decision to dispatch a certain maximum or minimum number of
units on a given route.
From the calculations, it is evident that the least positive value for k is 1 while the least negative value is -5. Accordingly,
-5 ≤ k ≤ 1 will cause no change in the current optimal solution. Thus, C13 = 12 + k or 12 - 5 = 7 and 12 + 1 = 13. In simple words,
if the cost element, 12, of the route AR changes between 7 and 13, no change in the current solution would take place.

Similarly, if we consider the cost coefficient of the cell

BR and change it to 8 + k, we can work out the revised
values of ∆ij. It will be seen that for this cell we get
-1 ≤ k ≤ 5, implying that the reduction can be up to 1
and increase up to 5 in this cost value without changing
the optimal solution. Notice, however, that in each
case, the distribution pattern remains unchanged but
the total transportation cost would change due to
change in a cost element.
 If we increase the supply at plant A by three units and
demand at warehouse Q by three units,
then revised total cost = 9,440 + 3 x 0 + 3 x 10 = 9,470.

Let us consider how the new values of the decision

variables (the quantities, xij’s sent on various routes)
would change.

(a) If xij is a basic variable, so that the route

represented by source and destination where
change takes place is an occupied cell, then the
xij is revised to xij + k.
To illustrate, if the supply at plant A is increased by
three units and the demand at warehouse Q by
three units, then we revise the quantity sent on this
route to 153. This is shown in Table 5.28.
The new total cost is 9,440 + 0 x 3 + 10 x 3 = 9,470.
 If we increase the supply at plant C by ten units and
demand at warehouse P by ten units, then revised total
cost = 9,440 + (10x-6) + (10x11) = 9,490.

Let us consider how the new values of the decision

variables (the quantities, xij’s sent on various routes)
would change.

(b) If the route where change takes place is an unoccupied cell,

then we draw a closed loop starting with that cell. Once this is
done, we select the cell (on the closed loop) in the same row in
which supply is increased and add k to the xij value in that cell.
Then, we go round the loop, alternately subtracting and adding k
to the xij values in those cells.
To illustrate, suppose we add 10 units to the supply of plant C
and demand at warehouse P. Now, since the route CP is empty,
we draw a closed loop as: CP — CS — AS — AR — BR — BP — CP.
The occupied cell in the plant C row on the closed loop is CS. So
we add 10 units to this cell, subtract 10 units from AS, and
further add to AR, subtract from BR and, finally, add to the cell
BP. The revised solution is given in Table 5.29.
 Previous Optimal Solution New Optimal Solution

It is evident that 150 units from source B would remains unsupervised the total transportation
cost works out to be 9690.
 Transhipment Problem
Ques: A firm owns facilities at seven places. It has manufacturing plants at A, B, and C with
daily output of 500, 300 and 200 units of an item respectively. It has warehouses at P, Q, R and
S with daily requirement of 180, 150, 350 and 320 units respectively. The transportation
charges per unit on different routes are given below
The firm wants to send the output from
various plants to warehouses involving
minimum transportation cost. How should it
route the product so as to achieve its
objective?

Now, assume that it is possible for the item in question to be shipped between sources and
between destinations as well. The costs involved are shown here:
 16

Start with optimal solution obtained previously.