Lecture_14_Introduction ana mathematical formaulation

14.1 Introduction to Transportation Problem
Lecture 14
Transportation Problem :
Introduction ana mathematical formaulation
The Transportation problem is to transport various amounts of a single homogeneous commodity
that are initially stored at various origins, to different destinations in such a way that the total
transportation cost is a minimum.
It can also be defined as to ship goods from various origins to various destinations in such a
manner that the transportation cost is a minimum.
The availability as well as the requirements is finite. It is assumed that the cost of shipping is
linear.
14.2 Mathematical Formulation
Let there be m origins, ith origin possessing ai units of a certain product
Let there be n destinations, with destination j requiring bj units of a certain product
Let cij be the cost of shipping one unit from ith source to jth destination
Let xij be the amount to be shipped from ith source to jth destination
It is assumed that the total availabilities ?ai satisfy the total requirements ?bj i.e.
?ai = ?bj (i = 1, 2, 3 … m and j = 1, 2, 3 …n)
The problem now, is to determine non-negative of xij satisfying both the availability constraints
as well as requirement constraints
and the minimizing cost of transportation (shipping)
This special type of LPP is called as Transportation Problem.
1
14.3 Tabular Representation
Let ‘m’ denote number of factories (F1, F2 … Fm)
Let ‘n’ denote number of warehouse (W1, W2 … Wn)
W?
F
?
W1 W2 … Wn Capacities
(Availability)
F1 c11 c12 … c1n a1
F2 c21 c22 … c2n a2
.
.
.
.
.
.
.
.
.
.
.
.
Fm cm1 cm2 … cmn am
Required b1 b2 … bn ?ai = ?bj
W?
F
?
W1
W2
…
Wn
Capacities
(Availability)
F1 x11 x12 … x1n a1
F2 x21 x22 … x2n a2
.
.
.
.
.
.
.
.
.
.
.
.
Fm xm1 xm2 … xmn am
Required b1 b2 … bn ?ai = ?bj
In general these two tables are combined by inserting each unit cost cij with the corresponding
amount xij in the cell (i, j). The product cij xij gives the net cost of shipping units from the factory
Fi to warehouse Wj.
14.4 Some Basic Definitions
? Feasible Solution
A set of non-negative individual allocations (xij ? 0) which simultaneously removes
deficiencies is called as feasible solution.
? Basic Feasible Solution
A feasible solution to ‘m’ origin, ‘n’ destination problem is said to be basic if the number
of positive allocations are m+n-1. If the number of allocations is less than m+n-1 then it
is called as Degenerate Basic Feasible Solution. Otherwise it is called as Non-
Degenerate Basic Feasible Solution.
? Optimum Solution
A feasible solution is said to be optimal if it minimizes the total transportation cost.