Transportation and Assignment

PRESENTATION ON
TRANSPORTATION &
ASSIGNMENT PROBLEM
TRANSPORTATION PROBLEM
 Transportation Problem is one of the subclasses of LPPs.
 The objective is to transport various quantities of a single

homogenious commodity that are initially stored at various
origins to different destinations in such a way that the
transportation cost is minimum
 To achieve this we must know the amount & location of

available supplies and the quantities demanded.
 In addition, we must know the costs that result from

transporting one unit of commodity from various
origins to various destinations
DEFINITIONS…
 Feasible Solution:
Any set of non negative allocations (xij =0) which satisfies the row &
coloumn sum (RIM requirement)
 Basic feasible Solution:

A feasible solution is called a basic feasible solution if the number of non
negative allocations is equal to m+n-1, Where ‘m’ is the no: of rows, ‘n’
the no: of columns in a transportation table
 Non-Degenerate Basic Feasible Solution

Any feasible solution to a transportation problem containing m origins
& n destinations is said to be non-degenerate, if it contains m+n-
1 occupied cells & each allocation is in independent positions
 Degenerate Basic Feasible Solution

If a basic feasible solution contains less than m-n-1 non negetive
allocations, it is said to be degenerate.
OPTIMAL SOLUTION
 Optimal Solution is a feasible solution which minimises the total
cost
 The solution of a transportion problem can be obtained in two

stages, namely initial solution & optimum solution.
 Initial solutuin can be obtained by using any one of the following 3

methods :
 North West Corner Rule (NWCR)
 Last Cost Method or Matrix Minima Method
 Vogel’s Approximation Method (VAM)
 VAM is preferred over the other two methods since the initial
basic feasible solution obtained by this method is either optimal or
very close to the the optimal solution.
NORTH WEST CORNER RULE (NWCR)
 Step 1: Starting with cell ath the upper left corner (North West) of
the transportation matrix we allocate as much as possible so that
either the capacity of the first row is exhausted or the destination
requirement of the first column is satisfied ie, xn = min(a1b1)
 Step 2: If b1>a1, we move down vertically to the second row & make
the second allocation of magnitude x22=min (a2b1-xn) in the cell
(2,1)
If b1< a1, move horizontally to the second column and ,make the
second allocation of magnitude x12=min (a1,xn-b1) in the cell (1,2)
if b1=a1 there is a tie for the second allocation. We make the second
allocations of magnitude
x12=min(a1-a1,b1)=0 in the cell (1,2)
or x21=min (a2,b1-b1)=0 in the cell (2,1)
 Step 3 : Repeat steps 1 & 2 moving down towards the lower right
corner of the transportation table untill all the rim requirements are
satisfied.
LEAST COST METHOD OR MATRIX MINIMA
METHOD
 Step 1: Determine the smallest cost in the cost matrix of the transportation table. Let
it be cij. Allocate xij=min(ai,bj) in the cell (i,j)
 Step 2: xij=a, cross of the ith row of the transportation table and decrease bj by ai.
Then go to step 3
xij=bj, cross of the jth column of the transportation table and decrease ai
by bj. Then go to step 3
if xij=ai=bj cross off either the ith row or the jth column but not both.
 Step 3: Repeat step 1 & 2 for the resulting reduced

transportation tabe untill all the rim reqts are satisfied.
Whenever the minimum cost is not unique, make an
arbitrary choice among the minima.
VOGEL’S APPROXIMATION METHOD
(VAM)
 Step 1: Find the penalty cost of, namely the diff between the smallest and the next
smallest costs in each row & column.
 Step 2: Among the penalties as found in step 1, choose the maximum penalty. If this
maximum penalty is more than one, chose any one arbitarily
 Step 3: In the selected row or column as by step 2, find outthe

cell having the least cost. Allocate to this cell as much as possible
depending on the capacity & reqts.
 Step 4: Delete the row or column which is fully exhausted. Again

compute the column & row penalties for the reduced transportation
table & then go to step 2. Repeat the procedure untill all the rim
reqts are satisfied.
ASSIGNMENT PROBLEM
 The objective of assignment problem is to assign a no: of
origins (jobs) to the equal no: of destinations (persons) at a
minimum cost or maximum Profit.
 It is concerned with assigning jth jobs to nth persons.
 The assignment problem can be stated in the form of n x n cost

matrix [cij] of real nos
DIFF B/W TRANSPORTATION AND ASSIGNMENT
PROBLEM
 Tran: No: of sources & no: of destinations need not be equal.
Assi: The no: of sources & Destinations must be equal. The cost Matrix Must be a Square Matrix
 Tran: xij , the quantity to be transported from ‘ith’ origin to ‘jth’ destination can take any possible positive
values and satisfies the rim requirements.
Assi: xij the ‘jth’ job to be assigned to the ith’ person and can take either the value 1 0r zero
 Tran: The capacity & the requirement value is equal to ai & bj for the ith’
source and jth’ destinations ( i=1, 2mj=1,2,….n)
Assi: The capacity and the requirement value is exactly one.
 Tran: The problem is unbalanced if the total supply and total demand are
not equal.
Assi: The problem is unbalanced if the cost matrix is not a square matrix
HUNGARIAN METHOD PROCEDURE
 Step1 : Prepare a cost matrix. If the cost matrix is not a square matrix then add a dummy row
(column) with zero cost element.
 Step 2 : Subtract the minimum element in each row from all the elements of the respective
rows.
 Step 3 : Further modify the resulting matrix by subtracting the minimum element of each
column from all the elements of the respective column .Thus, obtain the modified the matrix .
Step 4 :Then draw minimum number of horizontal and vertical

 lines to cover all zeros in the resulting matrix. Let the minimum
number of lines be N. Now there are two cases.
case1 If N = n,where n is the order of matrix, then an optimal

assignment can be made. So make the assignment to get the
required solution.
Case 2 If N <n, then proceed to step 5
o Step 5 : Determine the smallest uncovered element in the matrix(element not

covered by N lines). Subtract this minimum element from all uncovered elements
and add the same element at the intersection of horizontal and vertical lines. Thus
the second modified matrix is obtained.
 Step 6 : Repeat step 3 and 4 until we get the case 1 of step 3.
 Step 7 : (to make zero assignment) Examine the rows successively until a row-wise
exactly single zero is found. Circle(o)this zero to make assignment. Then mark a
cross(x) overall zeros if lying in the column of the circled zero, showing that they can
be considered for future assignment. Continue in this manner until all the zeros have
been examined. Repeat the same procedure for column also
 Step 8 : Repeat the step 6 successively until one of the following situations arises-
(1) if no unmarked zero is left .then the process ends or

 (2) if there lies more than one of the unmarked zero in any column or row
then , circle one of the unmarked zero arbitrarily and mark a cross in the
cells of remaining zeros in its row and column. Repeat the process until no
unmarked zero is left in the matrix.
 Step 9 Thus exactly one marked circled zero in each row and each column
of the matrix is obtained. The assignment corresponding to these marked
circled zeros will give the optimal assignment.
UNBALANCED ASSIGNMENT
PROBLEM
 Any assignment problem is said to be unbalanced if the number of columns and

rows are not equal.
 To make its balanced we add a dummy row or dummy column with all the entries as
zero.
MAXIMISATION IN
ASSIGNMENT PROBLEM
 Objective is to maximize the profit
 To solve this we first convert the given profit matrix in to the loss matrix by
subtracting all the elements from the highest element of the given profit
matrix.
 For this converted loss matrix we apply the steps in Hungarian method to
get the optimum assignment.
TRAVELLING SALESMAN PROBLEM
 The objective is to select the sequence which the cities are visited in such a way that
the total travelling time is minimized .
o For eg : to visit two cities (A and B) there is

no choice. To visit three cities we have two
possible routes. For four cities we have three
possible routes. In general to visit “ n ” there
are “n-1” possible routes.

Transportation and Assignment

Uploaded by

Copyright:

Available Formats

Transportation and Assignment

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Transportation and Assignment

Uploaded by

Copyright:

Available Formats

PRESENTATION ON

 The objective is to transport various quantities of a single

 To achieve this we must know the amount & location of

 In addition, we must know the costs that result from

 Basic feasible Solution:

 Non-Degenerate Basic Feasible Solution

 Degenerate Basic Feasible Solution

 The solution of a transportion problem can be obtained in two

 Initial solutuin can be obtained by using any one of the following 3

 Step 3: Repeat step 1 & 2 for the resulting reduced

 Step 3: In the selected row or column as by step 2, find outthe

 Step 4: Delete the row or column which is fully exhausted. Again

 It is concerned with assigning jth jobs to nth persons.

 The assignment problem can be stated in the form of n x n cost

Assi: The capacity and the requirement value is exactly one.

Step 4 :Then draw minimum number of horizontal and vertical

case1 If N = n,where n is the order of matrix, then an optimal

o Step 5 : Determine the smallest uncovered element in the matrix(element not

 Step 6 : Repeat step 3 and 4 until we get the case 1 of step 3.

(1) if no unmarked zero is left .then the process ends or

 Any assignment problem is said to be unbalanced if the number of columns and

o For eg : to visit two cities (A and B) there is

You might also like