‘Assignment Problem’ PDF Quick download link is given at the bottom of this article. You can see the PDF demo, size of the PDF, page numbers, and direct download Free PDF of ‘Assignment Problem In Operations Research’ using the download button.
Assignment Problem Example With Solution Book PDF Free Download
Assignment Problem PDF
In Block 1 of this course, we have discussed the basic concepts related to Linear Programming Problems and the Simplex method for solving them.
The Transportation Problem was also discussed in Block 1. In this unit, we explain the Assignment problem and discuss various methods for solving it.
The assignment problem deals with allocating various resources (items) to various activities (receivers) on a one-to-one basis, i.e., the number of operations is to be assigned to an equal number of operators where each operator performs only one operation.
For example, suppose an accounts officer has 4 subordinates and 4 tasks.
The subordinates differ in efficiency and take different times to perform each task. If one task is to be assigned to one person in such a way that the total person hours are minimized, the problem is called an assignment problem.
Though the assignment problem is a special case of transportation problems, it is not solved using the methods described in Unit 4.
We use another method called the Hungarian method for solving an assignment problem. It is shorter and easier compared to any method of finding the optimal solution to a transportation problem.
In this unit, we discuss various types of assignment problems, including the traveling salesman problem, and apply the Hungarian method for solving these problems.
In the next unit, we shall discuss the fundamental structure and operating characteristics of a queueing system and explain a single server M/M/1 queueing model with Poisson input and exponential service time.
Objectives After studying this unit, you should be able to: formulate an assignment problem;· determine the optimal solutions of assignment problems using the· Hungarian method; obtain the solutions for special cases of assignment problems, i.e,· maximization problem, unbalanced assignment problems, alternative optimal solutions and restriction on assignments; and solve the travelling salesman problem as an assignment problem.·
An assignment problem may be considered as a special type of transportation problem in which the number of sources and destinations are equal.
The capacity of each source as well as the requirement of each destination is taken as 1. In the case of an assignment problem, the given matrix must necessarily be a square matrix which is not the condition for a transportation problem.
Suppose there are n persons and n jobs and the assignment of jobs has to be done on a one-to-one basis.
This assignment problem can be stated in the form of an n×n matrix of real numbers (known as the cost matrix) Maximisation Problem There may be an assignment problem in the form of a maximization problem.
For example, profits (or anything else like revenues), which need maximization may be given in the cells instead of costs/times.
To solve such a problem, we find the opportunity loss matrix by subtracting the value of each cell from the largest value chosen from among all the given cells.
When the value of a cell is subtracted from the highest value, it gives the loss of the amount caused by not getting the opportunity that would have given the highest value.
The matrix so obtained is known as the opportunity loss matrix and is handled in the same way as the minimization problem.
Let us explain this case with the help of an example.
The Unbalanced Assignment Problem The assignment problem wherein the number of rows is not equal to the number of columns is said to be an unbalanced assignment problem.
Such a problem is handled by introducing dummy row(s) if the number of rows is less than the number of columns and dummy column(s) if the number of columns is less than the number of rows.
All the elements of such a dummy row/column are taken as zero. The augmented problem is then solved by the Hungarian method as explained earlier.
Alternative Optimal Solutions Such solutions
Exist if while assigning zeroes, i.e., while carrying out Step 4 of the Hungarian method, we neither find any row nor any column, which has a single zero.
Then we first move row-wise and then column-wise to locate a row/column having two zeroes. We draw a rectangle arbitrarily around any one of these zeroes and cross the other.
Alternatively, the zero around which the rectangle has been drawn could have been crossed and the rectangle could have been drawn around the other zero.
This will lead to two alternative optimum solutions. While assigning zeroes, i.e., while carrying out Step 4 of the Hungarian method, we may neither find any row nor any column, which has single or two zeroes.
Then we first move row-wise and then column-wise to locate a row/column having three or more zeroes. This will lead to three or more alternative solutions.
Restriction on Assignments
Sometimes, in an assignment problem, there may be a case when a particular resource (say, a person) cannot be assigned a particular activity (say, a job).
To handle such a problem, we assign a very large cost (or time or anything else which is to be minimized) to that case and represent it by ∞ M, where M denotes a very high cost.
This is done to restrict the entry of this pair of resource-activity in the final solution.
| Author | – |
| Language | English |
| No. of Pages | 18 |
| PDF Size | 1 MB |
| Category | Education |
| Source/Credits | egyankosh.ac.in |
Assignment Problem Example With Solution PDF Free Download