Operation Research
Transportation and Assignment
Prof. Jasmin P. Bhimani
Assistant Professor
Department of Mechanical Engineering
VVP Engineering College, Rajkot
Topics Covered
• Transportation Problems definition
OR - Transportation
• Solution methods:
• North west corner method,
• least cost method,
• Vogel’s approximation method
• Degeneracy in transportation,
• Modified Distribution method,
• Unbalanced problems and profit maximization problems.
Transshipment Problems.
• Assignment Problems and Travelling sales man Problem.
Transportation Problems definition
• The transportation model deals with a special class of linear
OR - Transportation
programming problem in which the objective is to transport a
homogeneous commodity from various origins or factories to different
destinations or markets at a total minimum cost.
• Three factories A, B and C manufactures sugar and are located in
different regions. Factory A manufactures, b1 tons of sugar per year and
B manufactures b2 tons of sugar per year and C manufactures b3 tons of
sugar. The sugar is required by four markets W, X, Y and Z. The
requirement of the four markets is as follows: Demand for sugar in
Markets W, X, Y and Z is d1, d2, d3 and d4 tons respectively. The
transportation cost of one ton of sugar from each factory to market is
given in the matrix below. The objective is to transport sugar from
factories to the markets at a minimum total transportation cost.
Transportation Problems definition
Transportation cost per ton in
OR - Transportation
Market Rs. Availability
W X Y Z
C11 C12 C13 C14
A b1
C21 C22 C23 C24
Factories B b2
C31 C32 C33 C34
C b3
Demand
d1 d2 d3 d4 Σbi/Σdj
In tons
Transportation Problems definition
Transportation cost per ton in Rs.
OR - Transportation
Market Availability
W X Y Z
A C11 C12 C13 C14 b1
Factories B C21 C22 C23 C24 b2
C C31 C32 C33 C34 b3
Demand
d1 d2 d3 d4 Σbi/Σdj
In tons
Minimize Z = C11 X11 + C12 X12 + C13 X13 + C14 X14 + C21 X21 + C22
X22 + C23 X23 + C24 X24 + C31 X31 + C32 X32 + C33 X33 + C34 X34
Objective Function
Transportation Problems definition
Transportation cost per ton in Rs.
OR - Transportation
Market Availability
W X Y Z
A C11 C12 C13 C14 b1
Factories B C21 C22 C23 C24 b2
C C31 C32 C33 C34 b3
Demand
d1 d2 d3 d4 Σbi/Σdj
In tons
a11 x11 +a12 x12 + a13 x13 + a14 x14 ≤ b1
a21 x21 + a22 x22 + a23 x23 + a24 x24 ≤ b2
a31 x31 + a32 x32 + a33 x33 + a34 x34 ≤ b3 Constraints
Transportation Problems definition
Transportation cost per ton in
OR - Transportation
Rs. Availabilit
Market
y
W X Y Z
A C11 C12 C13 C14 b1
Factories B C21 C22 C23 C24 b2
C C31 C32 C33 C34 b3
Demand
d1 d2 d3 d4 Σbi/Σdj
In tons
a12 x12 + a22 x22 + a32 x32 ≥ d2 Constraints (because the sum must be greater than or
a13 x13 + a23 x23 + a33 x33 ≥ d3 equal to the demand of the market. We
a14 x14 + a24 x24 + a34 x34 ≥ d4 cannot send less than what is required
All xij and xji are ≥ 0 where i = 1,2,3 and j = 1,2,3,4. (This is because we cannot supply negative
elements)
Transportation Problems definition
• For the data given above, the mathematical model will be:
OR - Transportation
• Minimize Z = C11 X11 + C12 X12 + C13 X13 + C14 X14 + C21 X21 + C22
X22 + C23 X23 + C24 X24 + C31 X31 + C32 X32 + C33 X33 + C34 X34
Objective Function
a11 x11 +a12 x12 + a13 x13 + a14 x14 ≤ b1
a21 x21 + a22 x22 + a23 x23 + a24 x24 ≤ b2
a31 x31 + a32 x32 + a33 x33 + a34 x34 ≤ b3 Constraints
a12 x12 + a22 x22 + a32 x32 ≥ d2 Constraints
a13 x13 + a23 x23 + a33 x33 ≥ d3
a14 x14 + a24 x24 + a34 x34 ≥ d4 and
All xij and xji are ≥ 0 where i = 1,2,3 and j = 1,2,3,4. (This is because we cannot supply negative
elements)
Transportation Problems definition
• The above problem has got the following properties:
OR - Transportation
1. It has an objective function.
2. It has structural constraints.
3. It has a non-negativity constraint.
4. The relationship between the variables and the constraints are
linear.
Solution Method
1. Balancing the given problem.
OR - Transportation
2. Basic feasible solution can be obtained by three methods, they
are
(a)North - west corner method.
(b)Least - cost cell method. (Or Inspection method Or Matrix
minimum - row minimum- column minimum method)
(c)(Vogel's Approximation Method, generally known as VAM.
After getting the basic feasible solution (b.f.s.) optimality test to be
checked to identify whether the solution is optimal or not.
• There are two methods of giving optimality test:
a) Stepping Stone Method.
b) Modified Distribution Method, generally known as MODI
method.
Numerical 1 – North West Corner Method
• A company has factories at F1, F2 and F3 which supply to
OR - Transportation
warehouses at W1, W2, and W3. Weekly factory capacities are
200, 160 and 90 units, respectively. Weekly warehouses
requirement are 180,120 and 150 units, respectively. Unit shipping
costs (in Rs.) are as follows. Determine the optimal distribution to
minimize total transportation cost.
Numerical 1 – North West Corner Method
Transportation cost per ton in Rs.
Market Availability
OR - Transportation
W1 W2 W3
16 20 12
F1 200
14 8 18
Factories F2 160
26 24 16
F3 90
Demand In tons 180 120 150 450/450
Numerical 1 – Least Cost Method
Transportation cost per ton in Rs.
Market Availability
OR - Transportation
W1 W2 W3
16 20 12
F1 200
14 8 18
Factories F2 160
26 24 16
F3 90
Demand In tons 180 120 150 450/450
Numerical 1 – VAM
Transportation cost per ton in Rs.
Market Availability Raw Penalty
W1 W2 W3
OR - Transportation
16 20 12
F1 200
14 8 18
Factories
F2 160
26 24 16
F3 90
Demand
In tons
180 120 150 450/450
Column Penalty
Numerical 2 – North West Corner Method
Consider the transportation problem shown in table below. Find the initial basic
feasible solution using Northwest corner method, Least Cost Method and VAM
Method
OR - Transportation
Factory
1 2 3 4 5 Supply
20 4 32 28 20
1 3000
12 36 24 26 32
2 5000
Plant
16 8 28 24 20
3 8250
28 44 40 16 36
4 3750
Demand 3500 4000 2500 1500 4000
Comparison of NWC, LCM & VAM
Method Total Transportation Cost
N-W Corner Method
Least cost Method
Vogel’s Approximation Method
Numerical 2 – North West Corner Method
Factory
1 2 3 4 5 Supply
OR - Transportation
20 4 32 28 20
1 3000
12 36 24 26 32
2 5000
Plant
16 8 28 24 20
3 8250
28 44 40 16 36
4 3750
Demand 3500 4000 2500 1500 4000
Numerical 2 – Least Cost Method
Factory
1 2 3 4 5 Supply
OR - Transportation
20 4 32 28 20
1 3000
12 36 24 26 32
2 5000
Plant
16 8 28 24 20
3 8250
28 44 40 16 36
4 3750
Demand 3500 4000 2500 1500 4000
Numerical 2 – Vogel's Approximation Method
Factory
1 2 3 4 5 Supply
20 4 32 28 20
OR - Transportation
1 3000
12 36 24 26 32
2 5000
Plant
16 8 28 24 20
3 8250
28 44 40 16 36
4 3750
Demand 3500 4000 2500 1500 4000
Comparison of NWC, LCM & VAM
Method Total Transportation Cost
N-W Corner Method
Least cost Method
Vogel’s Approximation Method
Numerical 3 – Unbalanced Problem
A transport company has 5, 10, 7 and 3 trucks available at four different sites A,
B, C and D. Its customers have requirement of 5, 8 and 10 trucks at three
different destinations X, Y and Z respectively. The distance (in kms.) from an
OR - Transportation
origin to destination is summarized in following table.
Formulate above problem as a transportation problem and determine strategy
for a company using VAM. Test the optimality of VAM solution and determine
optimum strategy for the transport company
Customers
Sites
X Y Z
A 70 30 60
B 40 60 80
C 50 80 40
D 80 40 30
Numerical 3 – Unbalanced Problem
Factory
X Y Z Supply
OR - Transportation
70 30 60
A 5
40 60 80
B 10
Plant
50 80 40
C 7
80 40 30
D 3
Demand 5 8 10 23/25
Numerical 3 – Unbalanced Problem
Factory
X Y Z Dummy Supply
OR - Transportation
70 30 60 0
A 5
40 60 80 0
B 10
Plant
50 80 40 0
C 7
80 40 30 0
D 3
Demand 5 8 10 2 23/25
