OPERATIONS RESEARCH

Lesson 9. solution of assignment problem.

Current course

MBA Notes

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

for solving an assignment problem which method is used mcq

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:

for solving an assignment problem which method is used mcq

The method used for solving an assignment problemis called

Examveda

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

Mcqmate logo

  • β†’ 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

  1. MCQ QT

    for solving an assignment problem which method is used mcq

  2. 5 step problem solving method

    for solving an assignment problem which method is used mcq

  3. 7 steps in problem solving

    for solving an assignment problem which method is used mcq

  4. Solution of Assignment Problems

    for solving an assignment problem which method is used mcq

  5. MCQ Assignment

    for solving an assignment problem which method is used mcq

  6. mckinsey problem solving ppt

    for solving an assignment problem which method is used mcq

VIDEO

  1. Rapid Revision and Question Solving

  2. NCERT NUMERICAL AND OBJECTIVE QUESTION PART 4

  3. NCERT NUMERICAL AND OBJECTIVE QUESTION PART 6 FOR 12TH

  4. NCERT NUMERICAL & OBJECTIVE QUESTION PART 15 FOR 12TH

  5. Assignment problems| Chapter-1st of part-2| Bsc 3rd year math-book Optimization Techniques Paper-3rd

  6. #Assignment_problem#OperationsResearch#Hungerian_Method

COMMENTS

  1. MCQ QT

    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

  2. Assignment MCQ [Free PDF]

    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

  3. OR MCQ ALL

    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.

  4. [Solved] ______method is used in Assignment Problem

    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.

  5. ES-3: Lesson 9. SOLUTION OF ASSIGNMENT PROBLEM

    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.

  6. How to Solve the Assignment Problem: A Complete Guide

    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

  7. Operations Research Multiple choice Questions and Answers. Page 12

    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 ...

  8. Operations Research Multiple choice Questions and Answers. Page 20

    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 _____.

  9. PDF ASSIGNMENT PROBLEM

    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

  10. For solving an assignment problem, which method is used?

    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.

  11. Assignment Problem: Meaning, Methods and Variations

    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.

  12. The method used for solving an assignment problem is called ...

    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.

  13. The method used for solving an assignment problem is called

    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

  14. The method used for solving an assignment problem is:

    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

  15. Which of the following methods is commonly used to solve assignment

    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.

  16. Operations Research or Qualitative Approach MCQ Questions ...

    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.

  17. The method used for solving an assignment problem is called

    [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

  18. The method used for solving an assignment problemis called

    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

  19. The method used for solving an assignment problem is called ________ (a

    The method used for solving an assignment problem is called ________ (a) Reduced matrix method ( ... (c) Hungarian method (d) Graphical method

  20. The Hungarian method for solving an assignment problem can also be used

    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 ........................

  21. The Hungarian method for solving an assignment problem can also be used

    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.