First check whether the number of rows is equal to the numbers of columns, if it is so, the assignment problem is said to be balanced.

**Solution
of assignment problems (Hungarian Method)**

First check whether the
number of rows is equal to the numbers of columns, if it is so, the assignment
problem is said to be balanced.

**Step :1 **Choose the least element
in each row and subtract it from all the elements of that** **row.

**Step :2 **Choose the least element
in each column and subtract it from all the elements of that** **column.
Step 2 has to be performed from the table obtained in step 1.

**Step:3 **Check whether there is
atleast one zero in each row and each column and make an** **assignment as
follows.

(i) Examine the rows successively until a row with exactly one zero is found. Mark that zero by , that means an assignment is made there . Cross ( Ã—) all other zeros in its column. Continue this until all the rows have been examined.

(ii) Examine the columns
successively until a columns with exactly one zero is found. Mark that zero by , that means an assignment is made there .
Cross ( Ã— ) all other zeros in its row. Continue this until all the columns
have been examined

**Step :4 **If each row and each
column contains exactly one assignment, then the solution is optimal.

**Example
10.7**

Solve the following
assignment problem. Cell values represent cost of assigning job A, B, C and D
to the machines I, II, III and IV.

*Solution:*

Here the number of rows
and columns are equal.

âˆ´
The given assignment problem is balanced. Now let us find the solution.

**Step 1:** Select a smallest element in each row and subtract this from all
the elements in its row.

Look for atleast one
zero in each row and each column.Otherwise go to step 2.

**Step 2:** Select the smallest element in each column and subtract this from
all the elements in its column.

Since each row and
column contains atleast one zero, assignments can be made.

**Step 3 **(Assignment):

Examine the rows with exactly one zero. First three rows contain more than one zero. Go to row D. There is exactly one zero. Mark that zero by (i.e) job D is assigned to machine I. Mark other zeros in its column by Ã— .

**Step 4:** Now examine the columns with exactly one zero. Already there is
an assignment in column I. Go to the column II. There is exactly one zero. Mark
that zero by . Mark other zeros in its rowby Ã— .

Column III contains more
than one zero. Therefore proceed to Column IV, there is exactly one zero. Mark
that zero by . Mark other zeros in its row by Ã— .

**Step 5:** Again examine the rows. Row B contains exactly one zero. Mark
that zero by .

Thus all the four
assignments have been made. The optimal assignment schedule and total cost is

The optimal assignment
(minimum) cost

= â‚¹ 38

**Example
10.8**

Consider the problem of
assigning five jobs to five persons. The assignment costs are given as follows.
Determine the optimum assignment schedule.

*Solution:*

Here the number of rows
and columns are equal.

âˆ´
The given assignment problem is balanced.

Now let us find the
solution.

**Step 1:** Select a smallest element in each row and subtract this from all
the elements in its row.

The cost matrix of the
given assignment problem is

Column 3 contains no
zero. Go to Step 2.

**Step 2:** Select the smallest element in each column and subtract this from
all the elements in its column.

Since each row and
column contains atleast one zero, assignments can be made.

**Step 3 (Assignment):**

Examine the rows with
exactly one zero. Row B contains exactly one zero. Mark that zero by (i.e) PersonB is assigned to Job 1. Mark other zeros in its column by Ã— .

Now, Row C contains
exactly one zero. Mark that zero by . Mark other zeros in its
column by Ã— .

Now, Row D contains
exactly one zero. Mark that zero by . Mark other zeros in its
column by Ã— .

Row E contains more than
one zero, now proceed column wise. In column 1, there is an assignment. Go to
column 2. There is exactly one zero. Mark that zero by . Mark
other zeros in its row by Ã— .

There is an assignment
in Column 3 and column 4. Go to Column 5. There is exactly one zero. Mark that
zero by . Mark other zeros in its row by Ã— .

Thus all the five
assignments have been made. The Optimal assignment schedule and total cost is

The optimal assignment
(minimum) cost = ` 9

**Example
10.9**

Solve the following
assignment problem.

*Solution:*

Since the number of
columns is less than the number of rows, given assignment problem is unbalanced
one. To balance it , introduce a dummy column with all the entries zero. The
revised assignment problem is

Here only 3 tasks can be
assigned to 3 men.

**Step 1:** is not necessary, since each row contains zero entry. Go to Step
2.

**Step 2 :**

**Step 3 (Assignment) :**

Since each row and each
columncontains exactly one assignment,all the three men have been assigned a
task. But task S is not assigned to any Man. The optimal assignment schedule
and total cost is

The optimal assignment
(minimum) cost = â‚¹ 35

Tags : Procedure, Example Solved Problem | Operations Research , 12th Business Maths and Statistics : Chapter 10 : Operations Research

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

12th Business Maths and Statistics : Chapter 10 : Operations Research : Solution of assignment problems (Hungarian Method) | Procedure, Example Solved Problem | Operations Research

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.