Quantitative Management-Assignment Model

QUANTITATIVE MANAGEMENT- ASSIGNMENT MODEL
INTRODUCTION:
Refers to the class linear programming problems that involve the determining of the most efficient assignment of
people to projects, sales people to territories, contracts to bidders, and jobs to machines, etc.
The objective is most often to minimize total costs or total time of performing the tasks at hand.
One important characteristic of assignment model is that only one job or worker is assigned to one machine or
project.
Each assignment problem has associated with it a table or matrix. Generally, the rows contain the object or
people we wish to assign and the columns comprise the tasks or things we want them assigned to. The numbers in the
table are the costs associated with each particular assignment.
THE HUNGARIAN METHOD

The Hungarian method of assignment provides us with an efficient means of finding the optimal solution without
having to make a direct comparison of every assignment option. It operates on a principle of matrix reduction, which
means that by subtracting and adding appropriate numbers in the cost table or matrix, we can reduce the problem to a
matrix of opportunity costs. Opportunity costs show the relative penalties associated with assigning any person to a
project as opposed to making the best or least-cost assignment. We would like to make assignments such that the
opportunity cost for each assignment is zero.
The steps involved in the Hungarian method are outlined below.
THE HUNGARIAN METHOD
1. Find the opportunity cost table by
a. Subtracting the smallest number in each row of the original cost table or matrix from every number in that row
b. Then subtracting the smallest number in each column of the table obtained in part (a) from every number in that column
2. Test the table resulting from step 1 to see whether an optimal assignment can be made. The procedure is to draw the
minimum number of vertical and horizontal straight lines necessary to cover all zeros in the table. If the number of lines
equals either the number of rows or columns, an optimal assignment can be made. If the number of lines is less than the
number of rows or columns, we proceed to step 3.
3. Revise the present opportunity cost table. This is done by subtracting the smallest number not covered by a line from
every other uncovered number. This same smallest number is also added to any number(s) lying at the intersection of the
horizontal and vertical lines. We then return to step 2 and continue the cycle until an optimal assignment is possible.
4. After getting the optimal assignment possible: Finally, we make the allocation. Note that only one assignment will be
made from each row or column. We use this fact to proceed to making the final allocation as follows:
(a) Find a row or column with only one zero cell.
(b) Make the assignment corresponding to that zero cell.
(c) Eliminate that row and column from the table.
(d) Continue until all the assignments have been made.
Examples:
Example Problem 1: Example Problem 2:
A construction company has four large bulldozers located
You work as a sales manager for a toy manufacturer, and at four different garages. The bulldozers are to be moved
you currently have three salespeople on the road meeting to four different construction sites. The distances in miles
buyers. Your salespeople are in Austin, TX; Boston, MA; between the bulldozers and the construction sites are
and Chicago, IL. You want them to fly to three other cities: given below.
Denver, CO; Edmonton, Alberta; and Fargo, ND. The table
below shows the cost of airplane tickets in dollars between
these cities.
How should the bulldozers be moved to the construction

Where should you send each of your salespeople in order sites in order to minimize the total distance traveled?
to minimize airfare?
MULTIPLE OPTIMAL SOLUTIONS

An Assignment problem can have more than one optimal solution, which is called multiple optimal solutions. The
meaning of multiple optimal solutions is – The total cost or total profit will remain same for different sets or combinations of
allocations. It means we have the flexibility of assigning different allocations while still maintaining Minimum (Optimal) cost
or Maximum (Optimal) profit.
QUANTITATIVE MANAGEMENT- ASSIGNMENT MODEL
Example Problem 3: Example Problem 4:
The Spicy Spoon restaurant has four payment counters.
Three air conditioners are needed to be installed in the There are four persons available for service. The cost of
same week by three different companies. Bids for each assigning each person to each counter is given in the
job are solicited from each company. To which company following table.
should each job be assigned?
SEATWORK:
SEATWORK PROBLEM 1 SEATWORK PROBLEM 2
Solve the following assignment problem. Show all
There are five machines and five jobs are to be assigned and the possible solutions
Associated cost matrix is as follows. Find the proper assignment.
UNBALANCED ASSIGNMENT MODEL

If the cost matrix of an assignment problem is not a square matrix (i.e. number of sources is not equal to the number of
destinations). The assignment problem is called an unbalanced assignment problem. In such cases, fictitious rows and
columns are added in the matrix so as to form a square matrix. Then the usual assignment algorithm can be applied to
this resulting balanced problem.
Example Problem 5:
A company has 4 machines on which to do 3 jobs. Each job can be assigned to one and only one machine. The cost of
each job on each machine is given in the following table
Assignment Problem: Maximization

There are problems where certain facilities have to be assigned to a number of jobs, so as to maximize the overall
performance of the assignment. The Hungarian Method can also solve such assignment problems, as it is easy to obtain
an equivalent minimization problem by converting every number in the matrix to an opportunity loss. The conversion is
accomplished by subtracting all the elements of the given matrix from the highest element. It turns out that minimizing
opportunity loss produces the same assignment solution as the original maximization problem.
Example Problem 6: A company has 5 jobs to be done. The following matrix shows the return in terms of thousand of
pesos on assigning ith ( i = 1, 2, 3, 4, 5 ) machine to the jth job (j = A, B, C, D, E). Assign the five jobs to the five machines
so as to maximize the total expected profit.

Quantitative Management-Assignment Model

Uploaded by

Copyright:

Available Formats

Quantitative Management-Assignment Model

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Quantitative Management-Assignment Model

Uploaded by

Copyright:

Available Formats

QUANTITATIVE MANAGEMENT- ASSIGNMENT MODEL

THE HUNGARIAN METHOD

How should the bulldozers be moved to the construction

MULTIPLE OPTIMAL SOLUTIONS

UNBALANCED ASSIGNMENT MODEL

Assignment Problem: Maximization

You might also like