Oct.
11, 2021
ASSIGNMENT
MODEL
Prepared by: Prof. Irah Dianne Nicolas
Assignment Model
Assignment Model Hungarian
Dénes König
It is a problem that requires Method/Floods
pairing two sets of items given The method is named after a
Technique Hungarian mathematician.
a set of paired costs/profits in
is an algorithm used to
such a way that the total
determine an optimal solution
cost/profit of the pairings
to an assignment model.
minimized or maximized.
• It yields optimal solutions to the
assignment model. The method is
Hungarian based on mathematically proven
algorithm for determining the optimal
solution.
Method • The basic idea in this method is to
avoid opportunity losses.
• Opportunity cost show the relative
penalties associated with assigning
resources to an activity as opposed to
making the best or least cost
assignment. If we can reduce the cost
matrix to the extent of having at least
one zero in each row and column, it
will be possible to make optimal
assignment.
AM AM
The objective is to assign a It involves assignment of people
number of origins to the equal to projects, jobs to machines,
number of destinations at the workers to jobs and teachers to
minimum cost or maximize classes etc.
profit
AM AM
One of the important Hence, the number of sources
characteristics of assignment are equal to the number of
problem is that only one job (or destinations and each
worker) is assigned to one requirement and capacity value
machine (or project). is exactly one unit.
Some applications of AM are:
Sales/Marketing
people to sales Teachers to
territories classes and more...
1 2 3 4 5 6
Contracts to Accountants to
Machines to bidders by clients accounts
factory orders systematic bid-
evaluation
Steps in Solving Model using Hungarian Method:
Determine the opportunity cost table
A. Subtract the lowest entry in each row/column of the
given cost table from all entries in that row/column for
minimization problem. For maximization problem subtract
each entry in the row/column from the highest entry in
each row/column.
B. Subtract the lowest entry in each column/row of the
table obtained in part from all numbers in that
column/row.
Determine whether an optimal
assignment can be made.
The procedure is to draw straight lines (vertically and
horizontally, using the least number of lines possible. This
can be done by covering the first row/column with most
number of zeros. An optimal assignment can be made with
the number of lines equals the number of rows/column.
Steps in Solving Model using Hungarian Method:
Revised the total opportunity cost table
A. Select the smallest value of the uncovered line
row/column and subtract this number from all numbers not
covered by straight line.
B. Add this same number to the number lying at the
intersection of any two lines.
C. Copy entries covered by a single line, then return to step 2.
Assignment Model: Minimization
Problem
A plant has 4 operators to be assigned
to 4 machines. The time (in minutes)
required by each operator to produce a
product on each machine is shown
below.
Operator Machine
A B C D
1 11 12 10 9
2 8 10 5 7
3 11 14 12 13
4 9 15 8 11
Assignment Model:
Maximization Problem
MSS Car Rental Agency plans to purchase 5 new
automobiles to replace 5 older vehicles. The
older vehicles are to be sold at auction. The
agency has solicited from 5 individuals, each of
whom wishes to buy only one vehicle but has
agreed to make a sealed bid on each of the 5.
The bids are as follows in terms of Php 10,000.
Automobile
Buyer
Toyota Mitsubishi Ford Nissan Mazda
1 12 20 10 8 7
2 10 13 11 9 14
3 5 6 10 7 5
4 9 7 10 9 11
5 10 14 12 10 6
Thank You!!
