assignment problem in operation research mcq

270+ Operations Research Solved MCQs

Done Reading?

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

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:

Check it out now on O’Reilly

Dive in for free with a 10-day trial of the O’Reilly learning platform—then explore all the other resources our members count on to build skills and solve problems every day.

Operations Research Questions and Answers – MCQ Quiz

Operations Research  Online Quiz Following  quiz  provides Multiple Choice  Questions (MCQs) related to OS . You will have to read all the given answers and click on the view answer option.

These HTML online test quizzes on Operations Research have answers available with pdf, which is very useful in interviews and also in HTML subject exams.

Question 1: Operations Research approach is?

(A) multi-disciplinary

(B) scientific

(C) intuitive

(D) collect essential data

Question 2: Operation research approach is typically based on the use of ___________.

(A) physical model

(B) mathematical model

(C) iconic model

(D) descriptive model

Question 3: Mathematical model of linear programming problem is important because ___________.

(A) it helps in converting the verbal description and numerical data into a mathematical expression

(B) decision-makers prefer to work with formal models

(C) it captures the relevant relationship among decision factors

(D) it enables the use of algebraic technique

Question 4: In Program Evaluation Review Technique for an activity, the optimistic time 2, the pessimistic time is 12 and most likely time is 4. What is the expected time?

Question 5: Graphical method of linear programming is useful when the number of decision variable are __________.

(D) infinite

Question 6: A feasible solution to a linear programming problem _______________.

(A) must satisfy all the constraints of the problem simultaneously

(B) need not satisfy all of the constraints, only some of them

(C) must be a corner point of the feasible region.

(D) must optimize the value of the objective function

Question 7: Utilization factor is also known as ___________.

(A) Traffic intensity

(B) Kendals notation

(C) Row minima method

(D) Unbalanced assignment problem

Question 8: While solving a linear programming problem infeasibility may be removed by _________.

(A) adding another constraint

(B) adding another variable

(C) removing a constraint

(D) removing a variable

Question 9: In the optimal simplex table, Zj-Cj=0 value indicates _____________.

(A) alternative solution

(B) bounded solution

(C) infeasible solution

(D) unbounded solution

Question 10: If all aij values in the entering variable column of the simplex table are negative, then ___________.

(A) there are multiple solutions

(B) there exist no solution

(C) solution is degenerate

(D) solution is unbounded

Question 11: If an artificial variable is present in the basic variable column of optimal simplex table, then the solution is ___________.

(A) alternative

(B) bounded

(C) no solution

(D) infeasible

Question 12: For any primal problem and its dual ______________.

(A) optimal value of objective function is same

(B) primal will have an optimal solution if dual does too

(C) both primal and dual cannot be infeasible

(D) dual will have an optimal solution if primal does too

Question 13: Principle of complementary slackness states that ____________.

(A) primal slack*dual main=0

(B) primal main+dual slack=0

(C) primal main+dual surplus=0

(D) dual slack*primal main not equal to zero

Question 14: If primal linear programming problem has a finite solution, then dual linear programming problem should have ____________.

(A) finite solution

(B) infinite solution

(C) bounded solution

(D) alternative solution

Question 15: The initial solution of a transportation problem can be obtained by applying any known method. However, the only condition is that __________.

(A) the solution be optimal

(B) the rim conditions are satisfied

(C) the solution not be degenerate

(D) the few allocations become negative

Question 16: The dummy source or destination in a transportation problem is added to ______________.

(A) satisfy rim conditions

(B) prevent solution from becoming degenerate

(C) ensure that total cost does not exceed a limit

(D) the solution not be degenerate

Question 17: Which of the following methods is used to verify the optimality of the current solution of the transportation problem ____________.

(A) Modified Distribution Method

(B) Least Cost Method

(C) Vogels Approximation Method

(D) North West Corner Rule

Question 18: An optimal assignment requires that the maximum number of lines which can be drawn through squares with zero opportunity cost be equal to the number of ________.

(A) rows or coloumns

(B) rows and coloumns

(C) rows+columns- 1

(D) rows-columns

Question 19: Maximization assignment problem is transformed into a minimization problem by _____________.

(A) adding each entry in a column from the maximum value in that column

(B) subtracting each entry in a column from the maximum value in that column

(C) subtracting each entry in the table from the maximum value in that table

(D) adding each entry in the table from the maximum value in that table

Question 20: To proceed with the MODI algorithm for solving an assignment problem, the number of dummy allocations need to be added are ___________.

Question 21: An artificial variable leaves the basis means, there is no chance for the ________ variable to enter once again.

(B) surplus

(C) artificial

Question 22: Simplex method was designed by ___________.

(A) Dantzig

(B) A.Charnes

(D) Hungarian

Question 23: Dual Simplex Method was introduced by ____________.

Question 24: 4. The cell with allocation can be called ___________ .

(B) Empty cell

(C) Basic cell

(D) Non-basic cell

Question 25: The cell without allocation is called __________.

(A) Basic cell

(B) Non-basic cell

(C) Empty cell

(D) Basic solution

Question 26: Service mechanism in a queuing system is characterized by _____________.

(A) customers behavior

(B) servers behavior

(C) customers in the system

(D) server in the system

Question 27: . The problem of replacement is felt when job performing units fail _______________.

(A) suddenly and gradually

(B) gradually

(C) suddenly

(D) neither gradually nor suddenly

Question 28: Least Cost Method is also known as __________.

(A) North West Corner Method

(B) Matrix Minima Method

(C) Row Minima method

(D) Coloumn Minima method

Question 29: The objective of network analysis is to ___________.

(A) minimize total project duration

(B) minimize total project cost

(C) minimize production delays, interruption, and conflicts

(D) maximize total project duration

Question 30: A activity in a network diagram is said to be __________ if the delay in its start will further delay the project completion time.

(A) forward pass

(B) backward pass

(C) critical

(D) non critical

Operations Research

31. Using ______________ method, we can never have an unbounded solution

• Dual simplex

32. The customers of high priority are given service over the low priority customers is ______________.

• Pre emptive

33. A queuing system is said to be a ______________ when its operating characteristic are independent upon time

• pure birth model
• pure death model
• transient state
• steady state

34. An activity which does not consume neither any resource nor time is known as ______________.

• predecessor activity
• successor activity
• dummy activity

35. The difference between total and free float is ______________.

• independent
• interference

36. The number of time estimates involved in Program Evaluation Review Technique problem is ______________.

37. The assignment problem is always a ______________matrix.

38. The slack variables indicate ______________.

• excess resource available.
• shortage of resource
• nil resource
• idle resource

39. If the net evaluation corresponding to any non -basic variable is zero, it is an indication of the existence of an ______________.

• initial basic feasible solution
• optimum basic feasible solution
• optimum solution.
• alternate optimum solution.

40. Mathematical model of linear programming problem is important because ______________.

• it helps in converting the verbal description and numerical data into mathematical expression
• decision makers prefer to work with formal models
• it captures the relevant relationship among decision factors
• it enables the use of algebraic technique

Search MBA MCQ.com