93

Assignment Problems (Chapter 4)

Chapter 4
ASSIGNMENT PROBLEMS

4.1. ASSIGNMENT PROBLEMS

4.1.1. Introduction
Aproblem in which ndifferent facilities are assigned to ndifferent tasks, such a problem is known as an assignment
problem. For example, if there is availability of threc men and there are three jobs to be done where each man have
capabilityof doing any job but because of individualquality variation, it takes different time amount for each of them
to carry out cach job. Here the problem is how to bring about the assignment of men to the jobs such that total time
spent on jobs can be minimised. Assignment model is basically aspecial type of linear programming in which the
mainobjective is to bring about assignment of anumber of origins to an equal destination number so as to maximise
profit or minimise cost. A one-to-one basis needs is to be followed while assigning values.

"Assignment
alternatives."
Problem is the technique of selecting the best possible assignment of tasks from a number of

Assignment problems are associated with matching of objects in two distinct set or bringing out optimal pairing. For
example. in a children's garment aales depot, there are four sales counter and four salesmen. Now the problem is how
assignment of salesmen should b done to the counters in such amanner that the total service time is minimised altogether.
4.1.2. Mathematical Model of Assignment Problem
Given n facilities (resources) and jobs (or activities), and effectiveness (in terms of time, profit, cost, etc.) of each
facility (resource) for each job (activity), the problem lies in assignment of each resource to one and onty one job
(activity)
table 4.1.
such that there is optimisation of given efectiveness measure. For this problem, the data matrix is shown in
Table 4.1
Resources Supply
(workers) J,
W, C2 .... Cin
W: C21 C22 .. C2n 1

W, Cn2 . Cnn
Demand 1... 1

It is observed from the table that the data matrix looks exactly like the transpòrtation cost matrix. Only exception
being availability (or supply) of cach resource and the demand is takcn to be one at each destinations. The fact that
lies behind this is assignment on a one-to-one basis.
Let x; denote the assignment of facility i to job j such that:
if facility is assigned to job j
X; |0otherwise
Then. the mathematical model of the assignment problem can be stated as:

Minimise Z=) e,x

94 (Unit-i)
MBA Sccond Semester (Operations Research) MDU
Subject to the constraints
ZX=1, for all i (resource
availability)
Zx=1, for all j(activity requirement)
And Xij = 0or 1, for all iand j.
Where Cij represents the cost of assignment of resource i to activity J.
1t 1s Clear from the above data that the assignment problem is a special case of transportation problem possessin2
following twocharacteristics:
1) The cost matrix is absolutely a square
matrix, and
4 Tne optimal problem solution would be alwäys addresscd so that in a given cost matrix's column or row, only
one assignment will be there.

4.1.3. Applications of Assignment Model

Assignment model possess several applications. Some of them are as follows:
I) Assignment of operations to job.
N1achines allocauon ior optimal space utilization.
3) Salesmen assignment to difierent sales areas.
4) Emplovee's assignment to machines.
5) Effectiveness of teachers and subjects.
4.1.4. Solution of Assignment Problems
Foliowinig four methods are widely used for solving an assignment problem:
1)(Enumeration Metho+ Among the given resources (like men,machines etc.) and activities (like sales area, jobs,
eic.), d ist of all possible assignments is prepared while using this method. Now, an assignment is selected
having minimum cost and maximum profit (time of distance). In case, same minimum cost or maximum profit is
possessed by two or more assignments; then ther are multiple optimal solutions to the problem. Generally, there
are a total of n! Possible assignments for a problem with n job/workers. For example, in a problem with n =5
jobs/workers, one need to evaluate total of 5! or 120 assignments. However, this method is unsuitable in case
when n is large because manual calculations are difficult. Hence_ Enumeration method is applicable with small n
atues

2) Simplex Method Simplex method can be used for solving the assignment problem because each assignment
problem can be formulated as a or iateger LPP which are solved simply by simplex method. In the genera!l
mathematical formulation of assignment problen, it is seen that there are n + n o, 2h equalities and nxn
decision. For example, to solve a problem with 5 workers/jobs, there will be 10 equalities and 25 deci_ion
variables which are hard to solve manually.
3) (Transportation Method Assignment problem is known to be aspecial case of transportation problem and thus it
can be solved by the use of transportation methods. However, for a generai assignment problem, every basic
feasible solution having a square payoff matrix of order nmust have assignments m+n -i=ntñ-1n-tBut
any solution cannot possess more than nassignments due to special structure of the problem. Thus, there is inherent
degeneration of the assignment problem. So, for removing the degeneracy, dummy allocation of (n - 1) number is
required so as to proceed with such transportation method. Thus, it can be evaluated that degeneracy problem at
each solution makes the method of transportation inefficient computationally for assignment problem solution.
4 Hungarian Assignment Method (HAM):)It is observable that none of the above mentioned three working
methods tuSotve un assignment problem is efficient. Amethod specially designed to handle assignment problems is
an efficient way that is based on the opporturity cost concepi, known as Hungarian Assignment Method.
This HAM method modifies successively the colugns and rows of the efiectiveness mazix uail there is
observance of at least one zem compePeR in-cachcolumn and rowsothat acomplete assgnment can be made
correspondingtothese zeros. When applied to the original effectiveness matrix, the complete assignment conzs
out to be an optimal assignment in which the resulting total effectiveness comes out to De miuimal, There will
always be aconvergence of this method to optimal assignments in finite steps which are sechnically termed as
assign1nent algorithm.
 95
Assignment Problems (Chapter 4)

4.1.5. Flood Techniques/Hungarian Method to Solve Assignment Problems

Following are the various stepg which are involved in the assignment algorithm: (Figure 4.1)
Step 1: Lowest cost inshe row is subtracted from each row:
Step 2: Lowest cost in the column is subtracted from each column of this new cost matrix;
Step 3: Minimum number of vertical and horizontal lines are drawn soas to necessarily cover all zeros at least ance.
If in an x n matrix, minimum number of lines isn, ihen for the given assignment problem, one has an opimal
solution corresponding to a set of independent zeros i.e., a set of zeros where no two zeros ín the set ocCur in ne
same row oF column.

Step 4: In the case when minimum number of lines in n xn matrix is less than n then smallest number is-selected
which do not hav a line through it.
Step 5: Thi_ number is then subtracted from all elements that are. covered by lines and added to the elements which
are located at the intersection of two lnes. Step (3) is applied again to find a solution among the new set of zeros. In
case, no result is found, this step is repeated and usage of step (3) and (4) is continued until we find a solution of the
assignment problem.
START

Hat Prepare the assignment table

eaen who tuce

Is it a balanced Add dummy row (s) or
problem? No
column (s)
that
Yes
Convert it into a

It is a maximization Yes
minimization problem by
subtracting all the elements
problem? from the largest element

.No

Obtain the reduced cost table. For this:

1) Subtract the minimum elernent in cach row from all the
elements of that row and then
2) Subtract the minimum clerent in each colunn frona all
the elements of that colunn

Draw minimumn number of lines to cover all the zeros

in the table

Subtract the smailest

Does the
number of lines drawn uncovered element from
No all the uncovered
equal the order of
the matrix? elements. Add it to the
elements that lie at the
Yes
intersection of lines.
Keep the remaining
Optimum solution elements unchanged in
cbtained the revised cost table

Stop
Figure 4.1: Flow Chart for the Hungarian Method
96 (Unit-Il)
MBA Second Semester (Operations Research) MDU
Step 6: The job assignments are made with the help of given optimal solution as indicated by the 'zero' elements.
The procedure for this is as
follows:
Slocated whichis containingonly one zero' element. The job coresponding to dhis clemcnt is assigned
iOrresponding person. All zeros in the column corresponding to the element are crossed out, if any. This
Indicates the fact that there is no moe availability of particular person or job.
)srepeated for cach of such rows that contains only one zero in that. The same operation is performed
ilariy with respect to each column containing only one 'zero' element in the row in which there is element, if any.
ae when there is no column or row with only one 'zero' element left in them, then arbitrarily selection of a
Tow/cotumn is made and one of the iobs or person is chosen to make assignment. Now the remaining zeros are
Crossed in the row and column with respect to which we have done the assignment.
V) Repeat steps (i) to (iii) until we have dore all the
assignments.
V) Total cost is determined with refereruce to the original cost table. Sallet
Example 1: Solve the following assignment problem using Hungarian Method.
Tasks
Men |A B D
1 45 40 50 67
57 12 63 55
3 4 5 48 64
4 41 45 60 55

Solution: Applying Hungarian Method, we have the following steps:

Step 1) Row Reduction: Select the lowest element of each row and subtract it from the other elements of that row
as follows:
asks -4
Men B D
1 5 10 27
2 15 21 13
3 1 16
4 19 14

Step 2) Column Reduction: Select the lowèst elemént of each column and subtract it from the other elements of
that column às follows:
Tasks
Men A olel D
1 0 14
2 15 21
3 3 3
4 4 19 1

Step 3) Draw Lines: Now we have to draw minimum number of lines in auch a manner that it covers all zeros. For
this one has to first cover those rows/columns that contain maximum zeros.

Men
Tasks o 21 2G
B
A
5
C D
14
4 32 og
t5
3
-
As the total number of ines drawn is 4 which are equal to rows/columns (n = 4), so ie solutioa is opün
The assignment can be made oy scanning all zeros. The assignments are shown by square svmbol às shown
in lable 4.2: Table 4.2: Assignaleat of Tasks
Tasks
Meu

X
1 2
 97
Assignment Problems (Chapter 4)
third ad
SIep 4) Optimal Solution: The assignment madc occur in the following seauence. Since the first, assigned
[-B. 3-Cand 4-À, As the task B is 1o e
rows have only one zero, hcnce assignment will be second row is O
zero occur in the
men l, we cross-out other zeros oCcur in the sccond column. The only
men 2 and task D. Hence the assignment will be 2-D.
The optimal soution will be as follows:
Men Tasks Cost
1 B 40
2 D 55
3 C 48
4 A 41
Total 184

4.1.6. Special Cases in Assignment Problems

There are ieus basiccategorics for the assignment problems. These are as follows:
Special Cases in Assignment Problems

Balanced Assignment Problem

Unbalanced Assignment Problem

Minimisation Assignment Problem

Maximisation Assigament Problern

Multiple Optimal Solution

Traveling Salesman's Problem

[Link] Balanced Assignment Problems

A problem with equal number of rows and equal number of columns is known as a balanced problem. For example,
if there are 4 workers and 4jobs in a problem, such a problem is termed as abalanced assignment problem.
Example 2: Soive the following assignment problem using Hungarian method:
Job
Typist A C
P 85 55 30 40
90 40 -70 45 o
70 60 60 50
75 40 35

Solution: Applying Hungarian Method, we have the following steps:

Step 1) Row Reduction: Select the lowest element of each row and subtract it from the other elements of that row
as follovws:
A B D
P 55 25 10 Jusestelareateachen
50 30
R 20 10 10 0
40 20

R Cabmn Reduction: Select the lowest element of each column and subtract it from the other
elements f
that column as follows:
A C D
P 35 25
30 30 5
R 10 10
S 20 20 33
98 (Unit-ll)
MBA Second Semester (Operations Rescarch) MDU

p that
Brawit Lines:Now we have to draw minimum number of lines (horizontal and vertiçal) in such a manner
S n a l l eht t
covers all zeros.
B C
uncudala
P 35 10
Od
addral
30

S 20 20

Here the number of lines drawn (3) is less than the order of cost matrix (n = 4), bence this solution is not
opimal. For obtaining the optimal solution, we have to subtract the minimurh unçovered value of cost
matrix from other uncovered clements af matrix, except intersection point of lines where the values are
Sdded.
A C
P 30 25 0 5
25 30
R 0 15 15

S 15 5 0 15

Now, again lines are drawn in order to coverall zeros. Lel

D L e l

30 25

Ro 4 5 - - 5 . f
15

Since again the total number of lines that covering the all zeros (3) is not equal to order of the matrix (n=4),
hence the solution is not optimal. Again deduct the mininmum uncovered value from all other uncovered
vafues, exceptfrom the values of point of interseçion lines, where the values are added.
A B C D
P 25 20
25 35 0
R 15 20 0
S 10 0 10

Now, again lines are drawn in order to cover all zeros.

B C D
P 20
B
R 20
S

Now, the numbers of ine (4) is equal to order of matrix (n =4). Hence this provides optimal solution. The
assignment will be as follows: A D

P 25 20 O
25 |O 35
RO 15 20
S 10| O 10

Step 4) Optimal Solution: The sequence of assignments will be as below:

Typist Job Cost
P D 40
B 40
R 70
35
Total 185
 99
Assignment Problems (Chapter 4)
[Link]. Unbalanced (Non Square Matrix) Assignment Problems
his is the case when number of jobs and number of facilities are not equal and it is termed as unbalanced
assignment problem. This type of matrix isnot square and since HAM needs a square matrix, So neugus J
fãcilities are added to matrix and zero costs are assigned to matrix's corresponding cells. Then, these cels ao u
like the real cost cellswhile solving the problem and arctermed as dummy rows
columns
There is need of cqual number of rows and columns for using the Hungarian assignment method. However, while
there is a non-squafe matrix, the assignment problem is called an unbalanccd in which dummy row(s) orcount)
are added so as tO make it a square one. For example-assumea cost matrix of order 4x3, in such a case, a dumiy
Column needs to be added with zero cost element to make it a square matrix. Now, Hungarian method is
solve such problems. appicabe to

Example 3: A computer science faculty of a college decides to arrange special seminars on four modern topics n
order to motivate students for academic discussion. These topics are Computer Network, Information System,
Operating System and E-Commerce. Each seminar should be held once per week at 12:00 0' Clock. The schedul1ng
of these seminars should be done in such a manner that number of students (not attending) is kept to a
The number of students which are unable to attend a soecificsemtnar of partictular day is shown in minimum.
table below:
Computer Network Information System Operating System E-Commerce
(CN) (IS) (OS) (E-Comm)
Monday 40 60 20
Tuesday 40 30

54 Wednesday
Thursday.
60
30
20
30
40
30
20
30
20
30
Friday 10 20 10 30
Find the optima! schedule of these seminars, Also, find the number of students who are unable to attend at
seminar. least one

Solution: It is an unbalanced problem with five numbers of days and four seminar topics. For
problem, we introduce a ummy coluinn with zero values as fottows: balancing this
Computer Network Information SystemOperating System E-Commerce Dummy
(CN) (S) (OS) (E-Comm) (E)
Monday 50 40 50 20
Tuesday 40 30 40 30
Wednesday 60 20 30 20
Thursday 30 30 20 30 0
Friday 10 20 10 30

Now applying Hungarian methods, we have the following steps:

Step 1) Row Reduction: Select the lowest element of each row and
subtract it from the
Since the lowest element in each row is "0' hence there is no change in each row. other elements of that row.
Step 2) Column Reduction: Select the lowest element of each
column and subtract it from the other elements of
that column as follows:
CN IS OsE-CommE
Monday 40 20 40
Tuesday 30 1030 10
Wednesday 50 0 20 0
Thursday 20 10|10 10 0
Friday 0 0 0 10
Sten 3) Draw Lines: Now we have to draW minimum number of lines
(horizontal and yertical) in such a monn
that it covers all zeros.
CN .S QS E-Comm E
Monday 40 20 40
Tuesday P30 10 30
Wednesday 5 otot
Thursday °20 10 10
Friday
100 (Unit-II)
MBASecond Semester (Operations Research) MDU

Since the number of lines (4)is less than the order of matrix (n=5), hence this solution is not oplimal.

FOr obtaining the optimal solution, we have to subtract the minimum uncovered value of matrix from other
uncovered elements of matrix, except interscction point of lines where the values are added.
CN IS OS E-Comm
Monday 30 10 30 -
Tuesday 20 20-+ 10
Wednesday 0 20 10 10
Thursday 10 10

Friday 20 10

Now, again lines are drawn in order to cover all zeros.

CN S OS E-Comm
Monday
Tuesday 20 20 10

Wednesday 50 0 10
Thursday 10 10
Friday 200

Now, the numbers of line (5) is equal to order of matrix (n =5). Hence it is optimal solution. The assignment
will be as follows:
CN IS OS E-CommE
Monday 30 10 30
Tuesday 20 20 10
Wednesday 50 0 20 10 10
Thursday 10 10

Friday X 20

Step 4) Optimal Sokution: The sequence of assignments will, be, as follows:

Subject No. of Students
Day
E-Commerce (E-Comm) 20
Monday
No Seminar 0
Tuesday
20
Wednesday Information System(IS)
Operating System(0S) 20
Thursday
Computer Network(CN) 10
Friday

Seminar = 20+0+ 20 + 20+ 10= 70

Number of Student Missing at Least One
Minimisation Assignment Problems problem. The main objective of
[Link]. distance data in a minimisation assignment
involvement of cost, time and while a constant
There is
the final objective function. In minimization assignment problems,
such a problem is to minimize
column or row in the given cost matrixanassignment causing minimization
quantity is subtracted or added to every optimal
leads tÒ minimization of the total cost in other matrix. In such a case, an
also
of total cost in one of the matrix
solution is the one having zero tötal cost.
the. following cost matrix using Hungarian method:
npk 4:Find the optimal assignment for
Region's
Salesmen R,| Rg R4
35 27 28 37-27
S
28 34 30 40
S , 3 5 24 32 33
S4 24 3225 82
 101
Assignment Problems (Chapter 4)

Solution: After applying the Hungarian method, we have the following steps:
subtract it from the other elements or hat Iow
Dlep 1) Kow Reduction: Select the lowest element of cach row and
as follows:

Salesman Regions
R R, R R4
S 10
S, 6 2 12

S. 11 8 9

SA 8 58

Step 2) Column Reduction: Select the lowest clement of each column and subtract it from the other elements Of
that column as follows:
Salesman Regions
R, R R, R
S 8 0 1
S 6 1 3
S 11 .7
S ( 0 49

Step 3) Draw Lines: Now we have to draw minimum number of lines (horizontal and vertical) in such a manner
that it covers all zeros.

Salesman Regions
R1 R, R3 R4
S
S 6 1 3

Since the number of lines (4) is equal to the order of matrix (n=4), hence solution is optimal. The assignment
can be made by scanning all zeros. Assign zero with the symbol I in the rowthat contains only one zero and
Cross out all other zeros of corresponding column. Same process will be done along column. The
assignments are shown in table below:
Regions
Salesman
R R, R3 R
S 8 0

S 6 3

S 11 7

S. 8 49

Step 4) Optimal Solution: The order of assignment willbe as follows:

Si ’R2

S; > Ra
S4’ R3
Hence Minimum Cost = 27 +28 + 33+ 25 =113.

[Link]. Maximisation Assignment Problems

There is involvemènt of sales, revenue and profit data in a maximization assignment problem. A maximisation
problem is first convèrted into a minimisation problem. The process of converting amaximization matriy to
minimization is termed as a Regret matrix. The highest profit value is found from the original profit values A
nrofit values are then subtracted from the highest profit value and the resulting matrix is Regret matriy Baf
using the Hungarian method, maximisation problem needs to be changed to minimisation. The transformainn
maximization to minimization matrix is done through any of following two ways:
from the entire assignment table and all other
1) Highest element is selected elements are subtracted from the
highest element.
2 The sions of allvalues are changed in the table ie. the matrix elements are multiplied by -l.
102 (Unit-lI)
MBA Second Semester (Opcrations Research) MDU

t p l e , the following matrices show the transfomation of profit matrix (maximization) to cost matrix
(minimization): Profit Matrix Cost Matrix

6 1
12| 17 1
Subtract from 18
14 16 12
15 18 13 3 0

Multiple Optimal Solutions

In the reduced assignment matrix, while an assignment is made, there are two or more ways to strike off a number or
Certain zeros. This is an indication of multiple optimal solutions for the problem with the same objective function
value. Decision maker may be used to obtain more suitable solution in such cases.

Example 5: Let consider the following matrix that shows the four jobs (J1, Je, Js, J4) done by four machines (M;. Me,
M3, M4). Using Hungarian method, assign the jobs in sucha manner that it maximizes the total profit.
M M; M, M4
J 15 11 13 15
J, 13 12 12 13
J3 14 15 16 14
Ja 16 13 11 17

Soiution: We have the following steps after applying Hungarian method:

Step 1) Maximisation to Minimisation: As it is amaximisation problem, hence we have to subiract every value of
table from the maximum value (17) in order totransform it into minimisation problem. Now minimsation
problem will be as follows:
M, M, M, M,
2 6

J
J, 3 2 3
J 1 4 6

Step 2) Row Reduction: Now, select the smallest element of each row and subtract it from the other elements of
that row as follows:
M, M,M, M,
4
1

0
J, 6 0

Step 3) Column Reduction: Similar processis applied on column, that is, select the smallest element of cach
column and subtract it from the other elements of that column. We get the following table:
M, M M M
J 3 2 0
J 1
J5 2 2
Ji13 6

Step 5) Draw Lines: Now we have to draw minimùn number of lines (horizontal and vertical) in such a manner
that it covers all zeros.
MM,| M3: M4
J3 2

J
Ja it
Assignment Problems (Chapter 4) 103

Since the number of lines (4) is equalto the order of matrix (n=4), hence solution is optimal. The assignment
Can be made by scanning all zeros. The assignments are shown below:
M, M M, M4
J,o 3 2

Js 2
Ja 1 3 6

Step 4) Optimal Solution: The sequence of assignments are as follows:

M,
M,
Ja M,
J4 M4

Hence Total Profit =15+ 12+ 16 +17=60

[Link]. Multiple Optimal Soiutions
There can be more than one possible assignment combination for an assignment problem and this is termed as
multiple optimal solutions. But in such case, there is same optimal answer for all the possible combinations.
Whenever in the final assignment problem table there are multiple zeroes in any rows or columns, it is visibie that
there are multiple solutions to the specific problem.
Example 6: There are five workers available for five different jobs. The working time (in hours) of each job
performed by different persons is well-known from their previous records. It is shown in table below:
Job
J, J,J3 J4J5
A 2 2 7 1

B 6 7 6 1
Worker
6 5 3
4 2 3 1

E|5 3 1

Find the assignment of workers to different jobs in order to minimise the working tim. Also calculate the minimum
time needs for the completion of jobs.
Solution: Applying Hungarian method, we have the following steps:
Step 1) Row Reduction: First, select the smallest element of each row and subtract it from the other elements of
that row. We get following table:
Job
J, J J, J4 J,
|<aA A 1
5
1

6
6

Worker
C3 5 2 0
D3 6 2
E4 2

Step 2) Column Reduction: Similar process is applied on column, that is, select the smallest element of each
column and subtract it from the other elementsof that column. We get the following table:
Job

A 4
B 4 6 3
Worker
D 2 5
E3 2
104 (Unit-il) MDU
MBASecond Semester (Opcrations Research)

Sep 3) Draw Lines: Now we have todraw minimum number of lines (horizontal and vertical) in such a manner
that it covers al zeros.
Job
J J

B 4 5
Worker
C24
D

E3 I | 7 2 |

Since the number of ines drawn (4) is less than the order of the matrix (n = 5), hence the solution is not
optimal.
For obtaining the optimal solution, we have to subtract thg minimum uncovered value (1) of matrix from
other uncovered elements of matrix, except intersectionpoint of lines where the values are added.
Job

A 0 4

B 2 0
Worker
4 3
D 5 1

Now, again lines are drawn in order to cover all zeros at least once. We get the following table:
Job
J Ja
A
B 3
Worker 2 A

2 5

E 2 6

Now, the numbers of line (4) is again less than the order of matrix (n =5). Hence it is not optimal solution.
Again we have to apply similar method as shown above. We get the following table:
Job
J
A0 9 0 6 3

B 1 5 2 2 0
Worker
C 4 0

D 3 1

4 1

Again we have to draw minimum number of lines for determining optimal solution.
Job
J Jh J J, J.
A -
B 2
Worker
C0 4 1
D 3
E 4
 Assignment Problems (Chapter 4) 105

Now, the numbers of line (5) is cqual to order of matrix (n =5). Hence it is optimal solution. The ass1gament
will be as follows:
Job Job
J, J, J JA J J

<e 3 A lol6 3

20 R 1 5 2 0
Worker Worker 4
4 1 0 1
|
DXo DX 1
E O4 o41
Optimal Assignment I Optimal Assignment II -
Job

A 3
B 1 2 2 0
Worker 4 1
D X 3 ol 1
EX[01 4 A BC D
Optimal Assignment II
A
Step 4) Optimai Solution: There exists three optimal assignments as shown below:
Table 4.3: Optimal Assignments
Optimal Assignment| Optimal Assignment Optimal Assignment
(I) ()
Worker Job Working Time Job Working TimeJob Working Time
A
B J. 1 J
C J. 3 J
4 J 3
D J, J,
5 3 J 3
J
Total 13 13 13

Hence from the table above, it is clear that the minimum tine required for the completion of jobs is 13
hours.

sl.6.6. ]TraveBing Salesman's Proble returns back to the starting city by incurring the minimum cost and
In sucha problem, asalesman travel in cities and
problem is that all the
Travelling across one city is allowed only once. The assumption made in traveling salesman
by the cost incurred.
cities are connected with each other. The di_tance betwcen two cities is indicated
arranged by him in
For example, assume how posts are delivered by the postnan to the addre_see. Allthe letters are
If arrangement of
an order and then only he starts from post office to deliver all the posts and comes back finally. addressee. Same
posts to the
posts in an order is not done, he may need to travel longer distance so as to clear all the
Way, a raveling salesman needs to plar his visits in a particulár sequence.
back to head office. During his
Let us consider his journey starts from head office to branch offices and then finally
branches.
travel, he would not visit the brench onçe visited and he will be back only after visiting all the
Different types of traveling salesman's problems do exist. Some of these are as follows:
Hungarian method. In this, a
1) Cyclic Problem: This type of problem is solved by Assignment method or theand finally comes back to the
traveling salesman starts journey from_the headquarters and visits al branches
headquarters.
2) Acvclic problem: This is the second type of traveling salesman problem solved by the Dynamic prograrng
salesman starts from the headquarters and he
method. In this type of traveling salesman prcblem, journey of
visits all intermediate branches and reaches the iast branch finally and stays there.
106 (Unit-ll) (Operations Research) MDU
MBA Second Semester
This type of problenn is further classificd into two types:
1) Symmetrical: When the distancc (or time or cost) between cvery cities pair is not dependent on he jou
direction, it is said to be symmctrical acyclic problem.
ii) Asymmetrical: When for one or more cities pair, the distance (or time or cost) is dependent on ine jouy
direction i.c., it changes with the dircction, it is said tÛ be as vmmetrical acyclic problem. For exanpes
while salcsman has to visit two cities only, A and B. there is no choice as such, But while he has to ViStt
cities, there are 2! Possible routes for the jourmey. While having 4 cities, he has 3! Possible routes for tne
travel: Gcnerally, to visit n cities there are (n - 1)! Possible routes for travelling along.

There is much similarity in the ravelling salesman problem and the assignment problem. The only point where these
two varies is an additional restriction in case of travelling salesman problem that is X; is chosen such tnat nere
double visit to any city before completion of travel to all the citics.
Example 7: Solve the travelling-salesman problem given in the matrix form as shown below:
To
A C D 24
P 46 16 40
41 50
From 40 o
R 82 32 6 -
40 40 36

Soiution: Using the Hungariarn method, we get the following steps:

Siep l} Row Reduction:. Choose the smallest element of each row and subtract it from the other elements of that
rOw, We get following table:
A B D
P 300 24
1 10
R 50 0 28 3
S 4 4 0

Step 2) Coiumn Reduction: Similar method is applied on column, that is, select the
smallest
column and subtract it from the other elements of that column. We get the following table: element of each
A B C
P 30 24
0 10 0
49 0 28
S3 4 0

Step 3) Draw Lines: Now we have to draw minimum

number of lines
that it covers all zeros. The general rule is first cover those rows (horizontal and vertical) in such a manner
or columns that contain maximum number
of zeros.
A D
lo P. 30 24

R
3 3 4

Since the number of lines drawn (3) is less than the order of
optimal. For obtaining the optimal solution, we have to subiractthethe matsx(n =4), hence the solution is not
fYom other uncovered elements of matrix, except intersection point ofminimum uncovered value (3) of matriy
lines where the values are added
A B
P 27 21
0 13
49 28
 Assignment Problems (Chapter 4) 107

Again we have to draw minimum number of lines for determining optimal solution.
B C
5
P -24..

R -49-0
S

Now, the numbers of line (4) is equal to order of matrix (n 4), Hence it is optimal solution. Now the
assignment will be as follows:
A D
27 0 21
13
R 49 28
1

Step 4) Optimal Solution: Now the sequence of assignments will be as follows:

P’C.
Q’D,
R’ B, and
S ’A

Hence, minimum cost = 16 + 40 +32+ 40=7128.

4.1.7. Difference between Transportation and Assignment Problem

Transportation Problem Assignment Problemn
The matrix of such a problem may be square or rectangular Thefe must be asquare matrix for such a problem, or if not
one
square it must be converted to a square matriX.
Depending on the rim conditions, such problems may have There need to be one to one allocation of rows and columns.
any number of allocations of row and columns. Due to this reason, matrix must be a square.
The methods used to find the solution may be VAM or North- The methods used to find the optimal
solution may be
west corner methodor the matrix minimum method. Assignment algorithm or Hungarian method or Flood's
technique.
MODI test or stepping stone test may be used for checking|Drawing minimum number of vertical and horizontal lines
the optimality. to cover all zeros in the objects is used for checking the
optimality.
The allocation for basic feasible solution must be (m +n 1). There must be at least one zero in everv row and coumn.
There must be assignment of one machine to one job and
vice versa.
There may be any positive numbers in the rim as requirement. For each row and each column, there is rim requirement to
be always 1.
There is dealing with just one commodity that is moved from In an assignment problem, representation of jobs or
varying origins to varying destinations in a transportation machines is through rows whereas a coly represents
problem. machines or jobs.

4.2. EXERCISE
4.2.1. Short Answer Type Questions annual sales (in rupees of lac) that can be generated by each
1 What is assignment problem? salesman in each territory.
2) List-out models in assignment problems. Find the optional assignment.
3) What are the advantages of assignment problem?
4) What are the limitations of assignment problem? Territory
5 What is the optimality criterion in the assignment problem? Salesmen T,| T, T: T4 Ts
S 26 4 10 !2
6) Explain Hungarian method of assignment problems?
7) What is an unbalanced case in an assignment model? S, 31 27 14
S 15 18 16 25 30
4.2.2. Long Answer Type Questions 17 12 21 30 25
1) Five Salesmen are to be assigned to five Territories based S. 20 19 25 16 10
on the past performance; the following table shows the
[Ans: S, ’ T;, S, ’ T, S, ’T, S,’T, S; ’ T}
108 (Unit-ll)
MBA Sccond Semester (Operations Research) MDU
2) Solve the assignment problem for optimal solution
using given in the table below. Dctermine he assignment pattern
hungarian method. that:
Job Minimises the total time taken,
Worker
ii) Minimises the total cost of getting the five jobs done.
A R C
Table: Employee
45 40 6 8oloell
A B C D
57 42 63 9 3 3 2
49 52 46 64
4 41 45 60 Job 3 4 10 7
55
5 4
|Ans: |B,2-’D,3C, 4-A) 6 6
3) Solve the problem of (Ans:
maximise the sales:
assignment for the given table to
i) 1-C, 2- B, 3 - A, 4 - D. 5 - E: 11hours.
Machines ii) 1-D, 2 -B, 3- A, 4-C,5- E; E;45]
A B D
7) Solve the following assignment problem to minimise time:
Table: Jobs
32 38 40 28 40) 1 2 3 4 5
40 24 28 21 36 1|2 937|1
sqof 2 6 8 7 6
3 27 33 30 37
Men 3 6 5
41 36 36 4 42 3 1
33 40 35 39 5 539 1

The five jobs are to be processed and five machines are

[Ans: 1- 1, 2-5,3-3, 4 - 4,5-2; 14. Also 1-3, 2-5,3
-1,4-4, 5 -2; 14]
available. Anymachine can process'any job with reducing 8) Solve the following assignment problem for minimum
profit(in rupees) is given above. optimal cost:
|Ans: I’ B;2 ’ A; 3’E;4’C; 5’D] Table: To City
2 3 4 5 6
4) Solve the following assignment problem: A 12 10 15 22 18
Table 10 18 25 15 16 12
III IV From City 11 10 3 9
17 16 20 4 13 13 12
12 15 8 12 11 7 13 10
3 13 \16 15 12 16
4 21 24 17 28 26
[Ans: A-2, B-6, C-3, D- 1,E-4;38]
14 10 12 11 15 9) Find the optimal solution for the assignment problem with
the following cost matrix:
[Ans: -I. 2-IV, 3-V, 4- II,5 -I1; Zmin =60] IV

A team of 5 horses and 5 riders has entered a jumping show

A 11 17 8 16 20
5)
B 7 12 6 15
contest. The number of penalty points to be expected when
13 16 15 12 16
each rider rides any horse is shown below:
21 24 17 28 26
Table: Rider
R R R3 Ra R E 14 1 15 10 12
H 5 4 7 1 [Ans: A’I,B IV, C-’ V, D -’ III, E’ II; Minimum
H, 2 3 6 5 Cost = 60]
Horse H 4 5 2 4 10) A company has four machines on which three jobs have to
6 2 3 be done. Each job can be assigned to one and only one
H 4 2 5 1 machine. The cost of each job on each machine is given in
How should the horses be allotted to the riders so 'as to the following table:
minimise the expected loss of the team? Machine
P R
[Ans: H,-Rs, H,- RÊ, H,- Ri, H4 -Ra, H_- R2; Zmin =8] A 18 24 28 32
6) Five employees of a company are to be assigned to five Job 13 17 19
jobs, which can be done by any of them. The workers get 10 15 19 22
different wages per hour. These are 5 per hour for A, B and What are the job assignments which will minimise the cost?
Ceach and 3 per hour for D and Eeach. The amount of
JAns: A ’P, B ’Q,C’ R, D’ S;
time in hours taken by each employee to do a given job is 501
Minimum Cost =