OPERATIONS RESEARCH
Lesson 9. solution of assignment problem.
Current course
How to Solve the Assignment Problem: A Complete Guide
Table of Contents
Assignment problem is a special type of linear programming problem that deals with assigning a number of resources to an equal number of tasks in the most efficient way. The goal is to minimize the total cost of assignments while ensuring that each task is assigned to only one resource and each resource is assigned to only one task. In this blog, we will discuss the solution of the assignment problem using the Hungarian method, which is a popular algorithm for solving the problem.
Understanding the Assignment Problem
Before we dive into the solution, it is important to understand the problem itself. In the assignment problem, we have a matrix of costs, where each row represents a resource and each column represents a task. The objective is to assign each resource to a task in such a way that the total cost of assignments is minimized. However, there are certain constraints that need to be satisfied – each resource can be assigned to only one task and each task can be assigned to only one resource.
Solving the Assignment Problem
There are various methods for solving the assignment problem, including the Hungarian method, the brute force method, and the auction algorithm. Here, we will focus on the steps involved in solving the assignment problem using the Hungarian method, which is the most commonly used and efficient method.
Step 1: Set up the cost matrix
The first step in solving the assignment problem is to set up the cost matrix, which represents the cost of assigning a task to an agent. The matrix should be square and have the same number of rows and columns as the number of tasks and agents, respectively.
Step 2: Subtract the smallest element from each row and column
To simplify the calculations, we need to reduce the size of the cost matrix by subtracting the smallest element from each row and column. This step is called matrix reduction.
Step 3: Cover all zeros with the minimum number of lines
The next step is to cover all zeros in the matrix with the minimum number of horizontal and vertical lines. This step is called matrix covering.
Step 4: Test for optimality and adjust the matrix
To test for optimality, we need to calculate the minimum number of lines required to cover all zeros in the matrix. If the number of lines equals the number of rows or columns, the solution is optimal. If not, we need to adjust the matrix and repeat steps 3 and 4 until we get an optimal solution.
Step 5: Assign the tasks to the agents
The final step is to assign the tasks to the agents based on the optimal solution obtained in step 4. This will give us the most cost-effective or profit-maximizing assignment.
Solution of the Assignment Problem using the Hungarian Method
The Hungarian method is an algorithm that uses a step-by-step approach to find the optimal assignment. The algorithm consists of the following steps:
- Subtract the smallest entry in each row from all the entries of the row.
- Subtract the smallest entry in each column from all the entries of the column.
- Draw the minimum number of lines to cover all zeros in the matrix. If the number of lines drawn is equal to the number of rows, we have an optimal solution. If not, go to step 4.
- Determine the smallest entry not covered by any line. Subtract it from all uncovered entries and add it to all entries covered by two lines. Go to step 3.
The above steps are repeated until an optimal solution is obtained. The optimal solution will have all zeros covered by the minimum number of lines. The assignments can be made by selecting the rows and columns with a single zero in the final matrix.
Applications of the Assignment Problem
The assignment problem has various applications in different fields, including computer science, economics, logistics, and management. In this section, we will provide some examples of how the assignment problem is used in real-life situations.
Applications in Computer Science
The assignment problem can be used in computer science to allocate resources to different tasks, such as allocating memory to processes or assigning threads to processors.
Applications in Economics
The assignment problem can be used in economics to allocate resources to different agents, such as allocating workers to jobs or assigning projects to contractors.
Applications in Logistics
The assignment problem can be used in logistics to allocate resources to different activities, such as allocating vehicles to routes or assigning warehouses to customers.
Applications in Management
The assignment problem can be used in management to allocate resources to different projects, such as allocating employees to tasks or assigning budgets to departments.
Let’s consider the following scenario: a manager needs to assign three employees to three different tasks. Each employee has different skills, and each task requires specific skills. The manager wants to minimize the total time it takes to complete all the tasks. The skills and the time required for each task are given in the table below:
The assignment problem is to determine which employee should be assigned to which task to minimize the total time required. To solve this problem, we can use the Hungarian method, which we discussed in the previous blog.
Using the Hungarian method, we first subtract the smallest entry in each row from all the entries of the row:
Next, we subtract the smallest entry in each column from all the entries of the column:
We draw the minimum number of lines to cover all the zeros in the matrix, which in this case is three:
Since the number of lines is equal to the number of rows, we have an optimal solution. The assignments can be made by selecting the rows and columns with a single zero in the final matrix. In this case, the optimal assignments are:
- Emp 1 to Task 3
- Emp 2 to Task 2
- Emp 3 to Task 1
This assignment results in a total time of 9 units.
I hope this example helps you better understand the assignment problem and how to solve it using the Hungarian method.
Solving the assignment problem may seem daunting, but with the right approach, it can be a straightforward process. By following the steps outlined in this guide, you can confidently tackle any assignment problem that comes your way.
How useful was this post?
Click on a star to rate it!
Average rating 0 / 5. Vote count: 0
No votes so far! Be the first to rate this post.
We are sorry that this post was not useful for you! π
Let us improve this post!
Tell us how we can improve this post?
Operations Research
1 Operations Research-An Overview
- History of O.R.
- Approach, Techniques and Tools
- Phases and Processes of O.R. Study
- Typical Applications of O.R
- Limitations of Operations Research
- Models in Operations Research
- O.R. in real world
2 Linear Programming: Formulation and Graphical Method
- General formulation of Linear Programming Problem
- Optimisation Models
- Basics of Graphic Method
- Important steps to draw graph
- Multiple, Unbounded Solution and Infeasible Problems
- Solving Linear Programming Graphically Using Computer
- Application of Linear Programming in Business and Industry
3 Linear Programming-Simplex Method
- Principle of Simplex Method
- Computational aspect of Simplex Method
- Simplex Method with several Decision Variables
- Two Phase and M-method
- Multiple Solution, Unbounded Solution and Infeasible Problem
- Sensitivity Analysis
- Dual Linear Programming Problem
4 Transportation Problem
- Basic Feasible Solution of a Transportation Problem
- Modified Distribution Method
- Stepping Stone Method
- Unbalanced Transportation Problem
- Degenerate Transportation Problem
- Transhipment Problem
- Maximisation in a Transportation Problem
5 Assignment Problem
- Solution of the Assignment Problem
- Unbalanced Assignment Problem
- Problem with some Infeasible Assignments
- Maximisation in an Assignment Problem
- Crew Assignment Problem
6 Application of Excel Solver to Solve LPP
- Building Excel model for solving LP: An Illustrative Example
7 Goal Programming
- Concepts of goal programming
- Goal programming model formulation
- Graphical method of goal programming
- The simplex method of goal programming
- Using Excel Solver to Solve Goal Programming Models
- Application areas of goal programming
8 Integer Programming
- Some Integer Programming Formulation Techniques
- Binary Representation of General Integer Variables
- Unimodularity
- Cutting Plane Method
- Branch and Bound Method
- Solver Solution
9 Dynamic Programming
- Dynamic Programming Methodology: An Example
- Definitions and Notations
- Dynamic Programming Applications
10 Non-Linear Programming
- Solution of a Non-linear Programming Problem
- Convex and Concave Functions
- Kuhn-Tucker Conditions for Constrained Optimisation
- Quadratic Programming
- Separable Programming
- NLP Models with Solver
11 Introduction to game theory and its Applications
- Important terms in Game Theory
- Saddle points
- Mixed strategies: Games without saddle points
- 2 x n games
- Exploiting an opponent’s mistakes
12 Monte Carlo Simulation
- Reasons for using simulation
- Monte Carlo simulation
- Limitations of simulation
- Steps in the simulation process
- Some practical applications of simulation
- Two typical examples of hand-computed simulation
- Computer simulation
13 Queueing Models
- Characteristics of a queueing model
- Notations and Symbols
- Statistical methods in queueing
- The M/M/I System
- The M/M/C System
- The M/Ek/I System
- Decision problems in queueing
Operations Research
191. The large negative opportunity cost value in an unused cell in a transportation table is chosen to improve the current solution because
- It represents per unit cost reduction
- It represents per unit cost improvement
- It ensure no rim requirement violation
- None of the above
Correct answer: (A) It represents per unit cost reduction
192. The method of finding an initial solution based upon opportunity costs is called __________.
- the northwest corner rule
- Vogel's approximation
- Johanson's theorem
- Flood's technique
- Hungarian method
Correct answer: (B) Vogel's approximation
193. The net cost of shipping one unit on a route not used in the current transportation problem solution is called the __________.
- change index
- Improvement index
Correct answer: (E) Improvement index
194. The objective function and constraints are functions of two types of variables, __________ variables and __________ variables.
- Positive and negative
- Controllable and uncontrollable
- Strong and weak
Correct answer: (B) Controllable and uncontrollable
195. The objective function for a minimization problem is given by z = 2 x1 - 5 x2 + 3 x3 The hyperplane for the objective function cuts a bounded feasible region in the space (x1,x2,x3). Find the direction vector d, where a finite optimal solution can be reached.
- d(-2,-5,-3)
Correct answer: (B) d(-2,5,-3)
196. The occurrence of degeneracy while solving a transportation problem means that
- Total supply equals total demand
- The solution so obtained is not feasible
- The few allocations become negative
Correct answer: (B) The solution so obtained is not feasible
197. The only restriction we place on the initial solution of a transportation problem is that: we must have nonzero quantities in a majority of the boxes.
- all constraints must be satisfied.
- demand must equal supply.
- we must have a number (equal to the number of rows plus the number of columns minus one) of boxes which contain nonzero quantities.
Correct answer: (A) all constraints must be satisfied.
198. The Operations research technique which helps in minimizing total waiting and service costs is
- Queuing Theory
- Decision Theory
- Both A and B
Correct answer: (A) Queuing Theory
199. The procedure used to solve assignment problems wherein one reduces the original assignment costs to a table of opportunity costs is called __________.
- stepping-stone method
- matrix reduction
- MODI method
- northwest reduction
- simplex reduction
Correct answer: (B) matrix reduction
200. The purpose of a dummy source or dummy destination in a transportation problem is to
- prevent the solution from becoming degenerate.
- obtain a balance between total supply and total demand.
- make certain that the total cost does not exceed some specified figure.
- provide a means of representing a dummy problem.
Correct answer: (B) obtain a balance between total supply and total demand.
Search MBA MCQ.com
Assignment Problem: Meaning, Methods and Variations | Operations Research
After reading this article you will learn about:- 1. Meaning of Assignment Problem 2. Definition of Assignment Problem 3. Mathematical Formulation 4. Hungarian Method 5. Variations.
Meaning of Assignment Problem:
An assignment problem is a particular case of transportation problem where the objective is to assign a number of resources to an equal number of activities so as to minimise total cost or maximize total profit of allocation.
The problem of assignment arises because available resources such as men, machines etc. have varying degrees of efficiency for performing different activities, therefore, cost, profit or loss of performing the different activities is different.
Thus, the problem is “How should the assignments be made so as to optimize the given objective”. Some of the problem where the assignment technique may be useful are assignment of workers to machines, salesman to different sales areas.
Definition of Assignment Problem:
ADVERTISEMENTS:
Suppose there are n jobs to be performed and n persons are available for doing these jobs. Assume that each person can do each job at a term, though with varying degree of efficiency, let c ij be the cost if the i-th person is assigned to the j-th job. The problem is to find an assignment (which job should be assigned to which person one on-one basis) So that the total cost of performing all jobs is minimum, problem of this kind are known as assignment problem.
The assignment problem can be stated in the form of n x n cost matrix C real members as given in the following table:
The method used for solving an assignment problemis called
A. reduced matrix method
B. MODI method
C. hungarian method
D. none of these
Answer: Option C
This Question Belongs to Management >> Operations Research
Join The Discussion
Related Questions on Operations Research
The use of decision models.
A. Is possible when the variables value is known
B. Reduces the scope of judgement & intuition known with certainty in decision-making
C. Require the use of computer software
D. None of the above
Every mathematical model.
A. Must be deterministic
B. Requires computer aid for its solution
C. Represents data in numerical form
D. All of the above
A physical model is example of.
A. An iconic model
B. An analogue model
C. A verbal model
D. A mathematical model
The qualitative approach to decision analysis relies on.
A. Experience
B. Judgement
C. Intuition
More Related Questions on Operations Research
Read More: MCQ Type Questions and Answers
- Arithmetic Ability
- Competitive Reasoning
- Competitive English
- Data Interpretation
- General Knowledge
- State GK
- History
- Geography
- Current Affairs
- Banking Awareness
- Computer Fundamentals
- Networking
- C Program
- Java Program
- Database
- HTML
- Javascript
- Computer Science
- Electronics and Communications Engineering
- Electrical Engineering
- Mechanical Engineering
- Civil Engineering
- Chemical Engineering
- Automobile Engineering
- Biotechnology Engineering
- Mining Engineering
- Commerce
- Management
- Philosophy
- Agriculture
- Sociology
- Political Science
- Pharmacy
- β Uncategorized topics
- β Decision Science
- β The Hungarian method for solving an assi...
View all MCQs in
No comments yet
Related MCQs
- The method used for solving an assignment problem is called
- While solving an assignment problem, an activity is assigned to a resource through a square with zero opportunity cost because the objective is to
- To proceed with the MODI algorithm for solving an assignment problem, the number of dummy allocations need to be added are
- An assignment problem is considered as a particular case of a transportation problem because
- Maximization assignment problem is transformed into a minimization problem by
- An assignment problem is a special case of transportation problem, where
- Which method usually gives a very good solution to the assignment problem?
- An assignment problem can be solved by
- An optimal solution of an assignment problem can be obtained only if
- Which of the following is used to come up with a solution to the assignment problem?
IMAGES
VIDEO
COMMENTS
For solving an assignment problem, which method is used? a) Hungarian b) American c) German d) Both are incorrect To make an unbalanced assignment problem balanced, what are added with all entries as zeroes? a) Dummy rows b) Dummy columns c) Both A and B d) Dummy entries
There are mainly four methods to solve assignment problems: Hungarian method Enumeration Method Simplex method Transportation method The most common method used for solving assignment is: Hungarian Method Hence, option B is the correct answer. India's #1 Learning Platform Start Complete Exam Preparation Daily Live MasterClasses
The Hungarian method for solving an assignment problem can also be used to solve. A. A transportation problem B. A travelling salesman problem C. A LP problem D. Both a & b. An optimal solution of an assignment problem can be obtained only if; A. Each row & column has only one zero element B. Each row & column has at least one zero element C.
The method used for solving an assignment problem is called method. If the number of rows and columns in an assignment problem are not equal than it is called problem. When a maximization assignment problem is converted in minimization problem, the resulting matrix is called matrix.
The assignment problem can be solved by the following four methods: a) Complete enumeration method b) Simplex Method c) Transportation method d) Hungarian method 9.2.1 Complete enumeration method In this method, a list of all possible assignments among the given resources and activities is prepared.
There are various methods for solving the assignment problem, including the Hungarian method, the brute force method, and the auction algorithm. Here, we will focus on the steps involved in solving the assignment problem using the Hungarian method, which is the most commonly used and efficient method. Step 1: Set up the cost matrix
116. If primal linear programming problem has a finite solution, then dual linear programming problem should ______________. have optimal solution. satisfy the Rim condition. have degenerate solution. have non-degenerate solution. View answer. 117. While solving an assignment problem, an activity is assigned to a resource through a square with ...
Multiple choice Questions on Operations Research. Practice for BBA or MBA exams using these MCQ. Page 20. ... The method of finding an initial solution based upon opportunity costs is called _____. ... The procedure used to solve assignment problems wherein one reduces the original assignment costs to a table of opportunity costs is called _____.
MCQ QUESTIONS WITH ANSWER K.BHARATHI,SCSVMV. ASSIGNMENT PROBLEM 2 / 55 ... PROBLEM 1: Solve the following assignment problem shown in Table using Hungarian method. The matrix entries are processing time of each man in hours. 2 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4 I II III IV V 1 20 15 18 20 25 2 18 20 12 14 15
Discussion No comments yet Login to comment Related MCQs The method used for solving an assignment problem is called method. If the number of rows and columns in an assignment problem are not equal than it is called problem. When a maximization assignment problem is converted in minimization problem, the resulting matrix is called matrix.
Variations. Meaning of Assignment Problem: An assignment problem is a particular case of transportation problem where the objective is to assign a number of resources to an equal number of activities so as to minimise total cost or maximize total profit of allocation.
For solving an assignment problem, which method is used? If the number of rows and columns in an assignment problem are not equal than it is called problem. When a maximization assignment problem is converted in minimization problem, the resulting matrix is called matrix.
Solution (By Examveda Team) The method used for solving an assignment problem is called Hungarian method. The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods. This Question Belongs to Management >> Operations Research Join The Discussion
Which of the following methods is used to solve an assignment problem: An assignment problem can be solved by ......................... The assignment problem is: In a maximisation assignment problem, the objective is to maximise ............................. While solving LP problem graphically, the area bounded by the constraints is called
Explanation: There are mainly four methods to solve assignment problems: Hungarian method. Enumeration Method. Simplex method. Transportation method. The most common method used for solving assignment is: Hungarian Method. Hence, option B is the correct answer. Download Solution PDF.
Operations Research or Qualitative Approach MCQ Questions and answers with easy and logical explanations. Management provides you all type of quantitative and competitive aptitude mcq questions with easy and logical explanations. Operations Research or Qualitative Approach MCQ is important for exams like MAT, CAT, CA, CS, CMA, CPA, CFA, UPSC, Banking and other Management department exam.
[Solved] The method used for solving an assignment problem is called β Uncategorized topics β Decision Science β The method used for solving an assignmen... View all MCQs in Decision Science Discussion No comments yet Login to comment Related MCQs The Hungarian method for solving an assignment problem can also be used to solve
The method used for solving an assignment problemis called a) reduced matrix method b) MODI method c) hungarian method d) none of these. ... Read More: MCQ Type Questions and Answers. Arithmetic Ability; Competitive Reasoning; Competitive English; Data Interpretation; General Knowledge; State GK; History
The method used for solving an assignment problem is called ________ (a) Reduced matrix method ( ... (c) Hungarian method (d) Graphical method
The method used for solving an assignment problem is: ........................... method is used to solve an assignment problem. .................... is the popular method for solving an assignment problem. Which of the following methods is used to solve an assignment problem: Hungarian method was developed by ........................
The method used for solving an assignment problem is called. While solving an assignment problem, an activity is assigned to a resource through a square with zero opportunity cost because the objective is to. To proceed with the MODI algorithm for solving an assignment problem, the number of dummy allocations need to be added are.