for assignment models hungarian method cannot be applied to solve

Hungarian Method

The Hungarian method is a computational optimization technique that addresses the assignment problem in polynomial time and foreshadows following primal-dual alternatives. In 1955, Harold Kuhn used the term “Hungarian method” to honour two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry. Let’s go through the steps of the Hungarian method with the help of a solved example.

Hungarian Method to Solve Assignment Problems

The Hungarian method is a simple way to solve assignment problems. Let us first discuss the assignment problems before moving on to learning the Hungarian method.

What is an Assignment Problem?

A transportation problem is a type of assignment problem. The goal is to allocate an equal amount of resources to the same number of activities. As a result, the overall cost of allocation is minimised or the total profit is maximised.

Because available resources such as workers, machines, and other resources have varying degrees of efficiency for executing different activities, and hence the cost, profit, or loss of conducting such activities varies.

Assume we have ‘n’ jobs to do on ‘m’ machines (i.e., one job to one machine). Our goal is to assign jobs to machines for the least amount of money possible (or maximum profit). Based on the notion that each machine can accomplish each task, but at variable levels of efficiency.

Hungarian Method Steps

Check to see if the number of rows and columns are equal; if they are, the assignment problem is considered to be balanced. Then go to step 1. If it is not balanced, it should be balanced before the algorithm is applied.

Step 1 – In the given cost matrix, subtract the least cost element of each row from all the entries in that row. Make sure that each row has at least one zero.

Step 2 – In the resultant cost matrix produced in step 1, subtract the least cost element in each column from all the components in that column, ensuring that each column contains at least one zero.

Step 3 – Assign zeros

• Analyse the rows one by one until you find a row with precisely one unmarked zero. Encircle this lonely unmarked zero and assign it a task. All other zeros in the column of this circular zero should be crossed out because they will not be used in any future assignments. Continue in this manner until you’ve gone through all of the rows.
• Examine the columns one by one until you find one with precisely one unmarked zero. Encircle this single unmarked zero and cross any other zero in its row to make an assignment to it. Continue until you’ve gone through all of the columns.

Step 4 – Perform the Optimal Test

• The present assignment is optimal if each row and column has exactly one encircled zero.
• The present assignment is not optimal if at least one row or column is missing an assignment (i.e., if at least one row or column is missing one encircled zero). Continue to step 5. Subtract the least cost element from all the entries in each column of the final cost matrix created in step 1 and ensure that each column has at least one zero.

Step 5 – Draw the least number of straight lines to cover all of the zeros as follows:

(a) Highlight the rows that aren’t assigned.

(b) Label the columns with zeros in marked rows (if they haven’t already been marked).

(c) Highlight the rows that have assignments in indicated columns (if they haven’t previously been marked).

(d) Continue with (b) and (c) until no further marking is needed.

(f) Simply draw the lines through all rows and columns that are not marked. If the number of these lines equals the order of the matrix, then the solution is optimal; otherwise, it is not.

Step 6 – Find the lowest cost factor that is not covered by the straight lines. Subtract this least-cost component from all the uncovered elements and add it to all the elements that are at the intersection of these straight lines, but leave the rest of the elements alone.

Step 7 – Continue with steps 1 – 6 until you’ve found the highest suitable assignment.

Hungarian Method Example

Use the Hungarian method to solve the given assignment problem stated in the table. The entries in the matrix represent each man’s processing time in hours.

\(\begin{array}{l}\begin{bmatrix} & I & II & III & IV & V \\1 & 20 & 15 & 18 & 20 & 25 \\2 & 18 & 20 & 12 & 14 & 15 \\3 & 21 & 23 & 25 & 27 & 25 \\4 & 17 & 18 & 21 & 23 & 20 \\5 & 18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} \)

With 5 jobs and 5 men, the stated problem is balanced.

\(\begin{array}{l}A = \begin{bmatrix}20 & 15 & 18 & 20 & 25 \\18 & 20 & 12 & 14 & 15 \\21 & 23 & 25 & 27 & 25 \\17 & 18 & 21 & 23 & 20 \\18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} \)

Subtract the lowest cost element in each row from all of the elements in the given cost matrix’s row. Make sure that each row has at least one zero.

\(\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 5 & 10 \\6 & 8 & 0 & 2 & 3 \\0 & 2 & 4 & 6 & 4 \\0 & 1 & 4 & 6 & 3 \\2 & 2 & 0 & 3 & 4 \\\end{bmatrix}\end{array} \)

Subtract the least cost element in each Column from all of the components in the given cost matrix’s Column. Check to see if each column has at least one zero.

\(\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 3 & 7 \\6 & 8 & 0 & 0 & 0 \\0 & 2 & 4 & 4 & 1 \\0 & 1 & 4 & 4 & 0 \\2 & 2 & 0 & 1 & 1 \\\end{bmatrix}\end{array} \)

When the zeros are assigned, we get the following:

The present assignment is optimal because each row and column contain precisely one encircled zero.

Where 1 to II, 2 to IV, 3 to I, 4 to V, and 5 to III are the best assignments.

Hence, z = 15 + 14 + 21 + 20 + 16 = 86 hours is the optimal time.

Practice Question on Hungarian Method

Use the Hungarian method to solve the following assignment problem shown in table. The matrix entries represent the time it takes for each job to be processed by each machine in hours.

\(\begin{array}{l}\begin{bmatrix}J/M & I & II & III & IV & V \\1 & 9 & 22 & 58 & 11 & 19 \\2 & 43 & 78 & 72 & 50 & 63 \\3 & 41 & 28 & 91 & 37 & 45 \\4 & 74 & 42 & 27 & 49 & 39 \\5 & 36 & 11 & 57 & 22 & 25 \\\end{bmatrix}\end{array} \)

Stay tuned to BYJU’S – The Learning App and download the app to explore all Maths-related topics.

Frequently Asked Questions on Hungarian Method

What is hungarian method.

The Hungarian method is defined as a combinatorial optimization technique that solves the assignment problems in polynomial time and foreshadowed subsequent primal–dual approaches.

What are the steps involved in Hungarian method?

The following is a quick overview of the Hungarian method: Step 1: Subtract the row minima. Step 2: Subtract the column minimums. Step 3: Use a limited number of lines to cover all zeros. Step 4: Add some more zeros to the equation.

What is the purpose of the Hungarian method?

When workers are assigned to certain activities based on cost, the Hungarian method is beneficial for identifying minimum costs.

Leave a Comment Cancel reply

Your Mobile number and Email id will not be published. Required fields are marked *

Request OTP on Voice Call

Post My Comment

• Share Share

Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures
• Hungarian Algorithm for Assignment Problem | Set 1 (Introduction)
• Clustering Coefficient in Graph Theory
• Maximum number of edges in Bipartite graph
• Types of Graphs with Examples
• Count of nodes with maximum connection in an undirected graph
• Erdos Renyl Model (for generating Random Graphs)
• Program to find the number of region in Planar Graph
• Maximize count of nodes disconnected from all other nodes in a Graph
• Find node having maximum number of common nodes with a given node K
• Convert the undirected graph into directed graph such that there is no path of length greater than 1
• Ways to Remove Edges from a Complete Graph to make Odd Edges
• Cost of painting n * m grid
• Number of Simple Graph with N Vertices and M Edges
• Count of Disjoint Groups by grouping points that are at most K distance apart
• Program to check if N is a Concentric Hexagonal Number
• Program to check if N is a Octagonal Number
• Graph Data Structure And Algorithms
• Program to check if N is a Icosidigonal Number
• Program to check if N is a Octadecagon number

Hungarian Algorithm for Assignment Problem | Set 2 (Implementation)

Given a 2D array , arr of size N*N where arr[i][j] denotes the cost to complete the j th job by the i th worker. Any worker can be assigned to perform any job. The task is to assign the jobs such that exactly one worker can perform exactly one job in such a way that the total cost of the assignment is minimized.

Input: arr[][] = {{3, 5}, {10, 1}} Output: 4 Explanation: The optimal assignment is to assign job 1 to the 1st worker, job 2 to the 2nd worker. Hence, the optimal cost is 3 + 1 = 4. Input: arr[][] = {{2500, 4000, 3500}, {4000, 6000, 3500}, {2000, 4000, 2500}} Output: 4 Explanation: The optimal assignment is to assign job 2 to the 1st worker, job 3 to the 2nd worker and job 1 to the 3rd worker. Hence, the optimal cost is 4000 + 3500 + 2000 = 9500.

Different approaches to solve this problem are discussed in this article .

Approach: The idea is to use the Hungarian Algorithm to solve this problem. The algorithm is as follows:

• For each row of the matrix, find the smallest element and subtract it from every element in its row.
• Repeat the step 1 for all columns.
• Cover all zeros in the matrix using the minimum number of horizontal and vertical lines.
• Test for Optimality : If the minimum number of covering lines is N , an optimal assignment is possible. Else if lines are lesser than N , an optimal assignment is not found and must proceed to step 5.
• Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column. Return to step 3.

Consider an example to understand the approach:

Let the 2D array be: 2500 4000 3500 4000 6000 3500 2000 4000 2500 Step 1: Subtract minimum of every row. 2500, 3500 and 2000 are subtracted from rows 1, 2 and 3 respectively. 0   1500  1000 500  2500   0 0   2000  500 Step 2: Subtract minimum of every column. 0, 1500 and 0 are subtracted from columns 1, 2 and 3 respectively. 0    0   1000 500  1000   0 0   500  500 Step 3: Cover all zeroes with minimum number of horizontal and vertical lines. Step 4: Since we need 3 lines to cover all zeroes, the optimal assignment is found.   2500   4000  3500  4000  6000   3500   2000  4000  2500 So the optimal cost is 4000 + 3500 + 2000 = 9500

For implementing the above algorithm, the idea is to use the max_cost_assignment() function defined in the dlib library . This function is an implementation of the Hungarian algorithm (also known as the Kuhn-Munkres algorithm) which runs in O(N 3 ) time. It solves the optimal assignment problem. 

Below is the implementation of the above approach:

Time Complexity: O(N 3 ) Auxiliary Space: O(N 2 )

Please Login to comment...

Similar reads.

• Mathematical

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Hungarian Method: Assignment Problem

Hungarian Method is an efficient method for solving assignment problems .

This method is based on the following principle:

• If a constant is added to, or subtracted from, every element of a row and/or a column of the given cost matrix of an assignment problem, the resulting assignment problem has the same optimal solution as the original problem.

Hungarian Algorithm

The objective of this section is to examine a computational method - an algorithm - for deriving solutions to the assignment problems. The following steps summarize the approach:

Steps in Hungarian Method

1. Identify the minimum element in each row and subtract it from every element of that row.

2. Identify the minimum element in each column and subtract it from every element of that column.

3. Make the assignments for the reduced matrix obtained from steps 1 and 2 in the following way:

• For every zero that becomes assigned, cross out (X) all other zeros in the same row and the same column.
• If for a row and a column, there are two or more zeros and one cannot be chosen by inspection, then you are at liberty to choose the cell arbitrarily for assignment.

4. An optimal assignment is found, if the number of assigned cells equals the number of rows (and columns). In case you have chosen a zero cell arbitrarily, there may be alternate optimal solutions. If no optimal solution is found, go to step 5.

5. Draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix obtained from step 3 by adopting the following procedure:

• Mark all the rows that do not have assignments.
• Mark all the columns (not already marked) which have zeros in the marked rows.
• Mark all the rows (not already marked) that have assignments in marked columns.
• Repeat steps 5 (i) to (iii) until no more rows or columns can be marked.
• Draw straight lines through all unmarked rows and marked columns.

You can also draw the minimum number of lines by inspection.

6. Select the smallest element from all the uncovered elements. Subtract this smallest element from all the uncovered elements and add it to the elements, which lie at the intersection of two lines. Thus, we obtain another reduced matrix for fresh assignment.

7. Go to step 3 and repeat the procedure until you arrive at an optimal assignment.

For the time being we assume that number of jobs is equal to number of machines or persons. Later in the chapter, we will remove this restrictive assumption and consider a special case where no. of facilities and tasks are not equal.

Share This Article

Operations Research Simplified Back Next

Goal programming Linear programming Simplex Method Transportation Problem

• MapReduce Algorithm
• Linear Programming using Pyomo
• Networking and Professional Development for Machine Learning Careers in the USA
• Predicting Employee Churn in Python
• Airflow Operators

Solving Assignment Problem using Linear Programming in Python

Learn how to use Python PuLP to solve Assignment problems using Linear Programming.

In earlier articles, we have seen various applications of Linear programming such as transportation, transshipment problem, Cargo Loading problem, and shift-scheduling problem. Now In this tutorial, we will focus on another model that comes under the class of linear programming model known as the Assignment problem. Its objective function is similar to transportation problems. Here we minimize the objective function time or cost of manufacturing the products by allocating one job to one machine.

If we want to solve the maximization problem assignment problem then we subtract all the elements of the matrix from the highest element in the matrix or multiply the entire matrix by –1 and continue with the procedure. For solving the assignment problem, we use the Assignment technique or Hungarian method, or Flood’s technique.

The transportation problem is a special case of the linear programming model and the assignment problem is a special case of transportation problem, therefore it is also a special case of the linear programming problem.

In this tutorial, we are going to cover the following topics:

Assignment Problem

A problem that requires pairing two sets of items given a set of paired costs or profit in such a way that the total cost of the pairings is minimized or maximized. The assignment problem is a special case of linear programming.

For example, an operation manager needs to assign four jobs to four machines. The project manager needs to assign four projects to four staff members. Similarly, the marketing manager needs to assign the 4 salespersons to 4 territories. The manager’s goal is to minimize the total time or cost.

Problem Formulation

A manager has prepared a table that shows the cost of performing each of four jobs by each of four employees. The manager has stated his goal is to develop a set of job assignments that will minimize the total cost of getting all 4 jobs.  

Initialize LP Model

In this step, we will import all the classes and functions of pulp module and create a Minimization LP problem using LpProblem class.

Define Decision Variable

In this step, we will define the decision variables. In our problem, we have two variable lists: workers and jobs. Let’s create them using  LpVariable.dicts()  class.  LpVariable.dicts()  used with Python’s list comprehension.  LpVariable.dicts()  will take the following four values:

• First, prefix name of what this variable represents.
• Second is the list of all the variables.
• Third is the lower bound on this variable.
• Fourth variable is the upper bound.
• Fourth is essentially the type of data (discrete or continuous). The options for the fourth parameter are  LpContinuous  or  LpInteger .

Let’s first create a list route for the route between warehouse and project site and create the decision variables using LpVariable.dicts() the method.

Define Objective Function

In this step, we will define the minimum objective function by adding it to the LpProblem  object. lpSum(vector)is used here to define multiple linear expressions. It also used list comprehension to add multiple variables.

Define the Constraints

Here, we are adding two types of constraints: Each job can be assigned to only one employee constraint and Each employee can be assigned to only one job. We have added the 2 constraints defined in the problem by adding them to the LpProblem  object.

Solve Model

In this step, we will solve the LP problem by calling solve() method. We can print the final value by using the following for loop.

From the above results, we can infer that Worker-1 will be assigned to Job-1, Worker-2 will be assigned to job-3, Worker-3 will be assigned to Job-2, and Worker-4 will assign with job-4.

In this article, we have learned about Assignment problems, Problem Formulation, and implementation using the python PuLp library. We have solved the Assignment problem using a Linear programming problem in Python. Of course, this is just a simple case study, we can add more constraints to it and make it more complicated. You can also run other case studies on Cargo Loading problems , Staff scheduling problems . In upcoming articles, we will write more on different optimization problems such as transshipment problem, balanced diet problem. You can revise the basics of mathematical concepts in  this article  and learn about Linear Programming  in this article .

• Solving Blending Problem in Python using Gurobi
• Transshipment Problem in Python Using PuLP

You May Also Like

DBSCAN Clustering

Measures of Central Tendency

Understanding Random Forest Classification and Building a Model in Python

Chapter: Operations Research: An Introduction : Transportation Model and Its Variants

The assignment model and the hungarian method.

THE ASSIGNMENT MODEL

"The best person for the job" is an apt description of the assignment model. The situation can be illustrated by the assignment of workers with varying degrees of skill to jobs. A job that happens to match a worker's skill costs less than one in which the operator is not as skillful. The objective of the model is to determine the minimum-cost assignment of workers to jobs. .

The general assignment model with n workers and n jobs is represented in Table 5.31.

The element c ij represents the cost of assigning worker i to job j (i, j = 1, 2, ... , n). There is no loss of generality in assuming that the number of workers always

equals the number of jobs, because we can always add fictitious workers or fictitious jobs to satisfy this assumption.

The assignment model is actually a special case of the transportation model in which the workers represent the sources, and the jobs represent the destinations. The supply (demand) amount at each source (destination) exactly equals 1. The cost of "transporting" worker i to job j is c ij . In effect, the assignment model can be solved directly as a regular transportation model. Nevertheless, the fact that all the supply and demand amounts equal 1 has led to the development of a simple solution algorithm called the Hungarian method. Although the new solution method appears totally un-related to the transportation model, the algorithm is actually rooted in the simplex method, just as the transportation model is.

1. The Hungarian Method

We will use two examples to present the mechanics of the new algorithm. The next section provides a simplex-based explanation of the procedure.

Example 5.4-1

Joe Klyne's three children, John, Karen, and Terri, want to earn some money to take care of personal expenses during a school trip to the local zoo. Mr. Klyne has chosen three chores for his children: mowing the lawn, painting the garage door, and washing the family cars. To avoid antic-ipated sibling competition, he asks them to submit (secret) bids for what they feel is fair pay for each of the three chores. The understanding is that aU three children will abide by their father's decision as to who gets which chore. Table 5.32 summarizes the bids received. Based on this information, how should Mr. Klyne assign the chores?

The assignment problem will be solved by the Hungarian method.

Step 1. For the original cost matrix, identify each row's minimum, and subtract it from all the entries of the row. .

Step 2. For the matrix resulting from step 1, identify each column's minimum, and subtract it from all the entries of the column.

Step 3. Identify the optimal solution as the feasible assignment associated with the zero ele-ments of the matrix obtained in step 2.

Let p i and q j be the minimum costs associated with row i and column j as defined in steps 1 and 2, respectively. The row minimums of step 1 are computed from the original cost matrix as shown in Table 5.33.

Next, subtract the row minimum from each respective row to obtain the reduced matrix in Table 5.34.

The application of step 2 yields the column minimums in Table 5.34. Subtracting these values from the respective columns, we get the reduced matrix in Table 5.35.

The cells with underscored zero entries provide the optimum solution. This means that John gets to paint the garage door, Karen gets to mow the lawn, and Terri gets to wash the family cars. The total cost to Mr. Klyne is 9 + 10 + 8 = $27. This amount also will always equal (p 1 + p 2 + p 3 ) + (q 1 + q 2 + q 3 ) = (9 + 9 + 8)+(0 + 1 + 0) = $27. (A justification of this result is given in the next section.)

The given steps of the Hungarian method work well in the preceding example because the zero entries in the final matrix happen to produce a feasible assignment (in the sense that each child is assigned a distinct chore). In some cases, the zeros created by steps 1 and 2 may not yield a feasible solution directly, and further steps are needed to find the optimal (feasible) assignment. The following example demonstrates this situation.

Example 5.4-2

Suppose that the situation discussed in Example 5.4-1 is extended to four children and four chores. Table 5.36 summarizes the cost elements of the problem.

The application of steps 1 and 2 to the matrix in Table 5.36 (using p 1 = 1, p 2 = 7, p 3 = 4, p 4 = 5, q 1 = 0, q 2 = 0, q 3 = 3, and q 4 = 0) yields the reduced matrix in Table 5.37 (verify!).

The locations of the zero entries do not allow assigning unique chores to all the children. For example, if we assign child 1 to chore 1, then column 1 will be eliminated, and child 3 will not have a zero entry in the remaining three columns. This obstacle can be accounted for by adding the following step to the procedure outlined in Example 5.4-1:

Step 2a. If no feasible assignment (with all zero entries) can be secured from steps 1 and 2,

(i) Draw the minimum number of horizontal and vertical lines in the last reduced matrix that will cover all the zero entries.

(ii) Select the smallest uncovered entry, subtract it from every uncovered entry, then add it to every entry at the intersection of two lines.

(iii) If no feasible assignment can be found among the resulting zero entries, repeat step 2a. Otherwise, go to step 3 to determine the optimal assignment.

The application of step 2a to the last matrix produces the shaded cells in Table 5.38. The smallest unshaded entry (shown in italics) equals 1. 111is entry is added to the bold intersection cells and subtracted from the remaining shaded cells to produce the matrix in Table 5.39.

The optimum solution (shown by the underscored zeros) calls for assigning child 1 to chore 1, child 2 to chore 3, child 3 to chore 2, and child 4 to chore 4. The associated optimal cost is 1 + 10 + 5 + 5 = $21. The same cost is also determined by summing the p i s, the q i s, and the entry that was subtracted after the shaded cells were determined-that is, (1 + 7 + 4 + 5) + (0 + 0 + 3 + 0) + (1) = $21.

AMPL Moment.

File amplEx5.4-2.txt provides the AMPL model for the assignment model. The model is very similar to that of the transportation model.

PROBLEM SET 5.4A

1. Solve the assignment models in Table 5.40.

a. Solve by the Hungarian method.

b. TORA Experiment. Express the problem as an LP and solve it with TORA.

c. TORA Experiment. Use TORA to solve the problem as a transportation model.

d. Solver Experiment. Modify Excel file solverEx5.3-l.xls to solve the problem.

e. AMPL Experiment. Modify ampIEx5.3-1b.txt to solve the problem.

2. JoShop needs to assign 4 jobs to 4 workers. The cost of performing a job is a function of the skills of the workers. Table 5.41 summarizes the cost of the assignments. Worker 1 cannot do job 3 and worker 3 cannot do job 4. Determine the optimal assignment using the Hungarian method.

3. In the JoShop model of Problem 2, suppose that an additional (fifth) worker becomes available for performing the four jobs at the respective costs of $60, $45, $30, and $80. Is it economical to replace one of the current four workers with the new one?

4.In the model of Problem 2, suppose that JoShop has just received a fifth job and that the respective costs of performing it by the four current workers are $20, $10, $20, and $80. Should the new job take priority over any of the four jobs JoShop already has?

*5. A business executive must make the four round trips listed in Table 5.42 between the head office in Dallas and a branch office in Atlanta.

The price of a round-trip ticket from Dallas is $400. A discount of 25% is granted if the dates of arrival and departure of a ticket span a weekend (Saturday and Sunday). If the stay in Atlanta lasts more than 21 days, the discount is increased to 30%. A one-way

ticket between Dallas and Atlanta (either direction) costs $250. How should the execu-tive purchase the tickets?

*6. Figure 5.6 gives a schematic layout of a machine shop with its existing work centers des-ignated by squares 1,2,3, and 4. Four new work centers, I, II, III, and IV, are to be added to the shop at the locations designated by circles a, b, c, and d. The objective is to assign the new centers to the proposed locations to minimize the total materials handling traf-fic between the existing centers and the proposed ones. Table 5.43 summarizes the frequency of trips between the new centers and the old ones. Materials handling equip-ment travels along the rectangular aisles intersecting at the locations of the centers. For example, the one-way travel distance (in meters) between center 1 and location b is 30 + 20 = 50 m.

7. In the Industrial Engineering Department at the University of Arkansas, INEG 4904 is a capstone design course intended to allow teams of students to apply the knowledge and skills learned .in the undergraduate curriculum to a practical problem. The members of each team select a project manager, identify an appropriate scope for their project, write and present a proposal, perform necessary tasks for meeting the project objectives, and write and present a final report. The course instructor identifies potential projects and provides appropriate information sheets for each, including contact at the sponsoring or-ganization, project summary, and potential skills needed to complete the project. Each design team is required to submit a report justifying the selection of team members and the team manager. The report also provides a ranking for each project in order of prefer-ence, including justification regarding proper matching of the team's skills with the pro-ject objectives. In a specific semester, the following projects were identified: Boeing F-lS, Boeing F-18, Boeing Simulation, Cargil, Cobb-Vantress, ConAgra, Cooper, DaySpring (layout), DaySpring (material handling), IB. Hunt, Raytheon, Tyson South, Tyson East, Wal-Mart, and Yellow Transportation. The projects for Boeing and Raytheon require U.S. citizenship of all team members. Of the eleven design teams available for this semester, four do not meet this requirement.

Devise a procedure for assigning projects to teams and justify the arguments you use to reach a decision.

2. Simplex Explanation of the Hungarian Method

The assignment problem in which n workers are assigned to n jobs can be represented as an LP model in the following manner: Let c ij be the cost of assigning worker i to job j, and define

The optimal solution of the preceding LP model remains unchanged if a constant is added to or subtracted from any row or column of the cost matrix (c ij ). To prove this point, let p i and q j be constants subtracted from row i and column j. Thus, the cost element c ij is changed to

Because the new objective function differs from the original one by a constant, the optimum values of x ij must be the same in both cases. The development thus shows that steps 1 and 2 of the Hungarian method, which call for subtracting p i from row i and then subtracting q j from column j, produce an equivalent assignment model. In this regard, if a feasible solution can be found among the zero entries of the cost matrix created by steps 1 and 2, then it must be optimum because the cost in the modified matrix cannot be less than zero.

If the created zero entries cannot yield a feasible solution (as Example 5.4-2 demonstrates), then step 2a (dealing with the covering of the zero entries) must be ap-plied. The validity of this procedure is again rooted in the simplex method of linear programming and can be explained by duality theory (Chapter 4) and the complementary slackness theorem (Chapter 7). We will not present the details of the proof here because they are somewhat involved.

The reason (p 1 + p 2 + ... + p n ) + (q 1 + q 2 + ... + q n ) gives the optimal objective value is that it represents the dual objective function of the assignment model. This result can be seen through comparison with the dual objective function of the transportation model given in Section 5.3.4. [See Bazaraa and Associates (1990, pp. 499-508) for the details.]

Related Topics

Privacy Policy , Terms and Conditions , DMCA Policy and Compliant

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

Index     Assignment problem     Hungarian algorithm     Solve online    

Solve an assignment problem online

Fill in the cost matrix of an assignment problem and click on 'Solve'. The optimal assignment will be determined and a step by step explanation of the hungarian algorithm will be given.

Fill in the cost matrix ( random cost matrix ):

Don't show the steps of the Hungarian algorithm Maximize the total cost

HungarianAlgorithm.com © 2013-2024

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: