MANAGEMENT SCIENCE

Manuel S. Enverga University Foundation

College of Business and Accountancy
Lucena City

Special Purpose
Algorithm LP:
Assignment Method

Prepared by
RALYN E BERMUDEZ
MANAGEMENT SCIENCE

Learning Outcomes
1. identify the special features of transportation and assignment
problems

2. Set up the transportation and assignment problem in matrix

form

3. determine the best method in establishing the initial feasible

solution and method in manipulating towards the optimal
solution

4. Solve transportation and assignment problems, both for

balanced and unbalanced cases .
MANAGEMENT SCIENCE

Assignment Method

✳ The assignment problem is the problem of assigning m workers

n jobs, in such a way that a worker is assigned to only one job.
The workers assigned to it and the costs of completing all of the
jobs will be minimized

✳ It is concerned in matching jobs to each of the workers for

minimum costs or maximum revenues
MANAGEMENT SCIENCE

Hungarian method or Flood

Technique
• It is an algorithm used to determine an optimal solution to an
assignment problem.

• It is based on mathematically proven algorithm for determining

optimal solutions.

• Based on the concept of opportunity losses, related on the

opportunity losses in the Vogel’s Approximation Method of the
transportation problems.
MANAGEMENT SCIENCE

Hungarian Method: Minimization

Steps
1. Set up the initial table and determine the BFS

2. Determine the opportunity cost table.

a) Subtract the lowest entry in each 1) row & 2) 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.
MANAGEMENT SCIENCE
Steps in Solving Assignment
Problems using Hungarian
Method
3. Determine whether an optimal assignment can be made. The
procedure is to draw straight lines (vertically or horizontally)
using the least number of lines possible.

An optimal assignment can be made when the number of lines

equals the numbers of rows/columns. If the number of lines
drawn is fewer than the number of rows/columns, an optimal
assignment cannot be made and the problem is not solved.
MANAGEMENT SCIENCE

Description
4. If the optimal solution is not yet obtained, revise the total
opportunity-cost table.

a) Look for (and select) the smallest value among the

uncovered entries and subtract it from all the uncovered
numbers.

But, you are to add this same number to the numbers lying
at the intersection of any two lines.

a) Copy the entries covered by a single line, then return to

step 3.
MANAGEMENT SCIENCE

Assignment: Balanced Case

The manager of a company wishes to assign the 4 operators to four
machines on a one-to-one basis. Their work test performance (in
minutes) in utilizing different machines is shown below.

Machine
Operator A B C D
1 11 12 10 9
2 8 10 5 7
3 11 14 12 13
4 9 15 8 11

What could be the best assignment to ensure work efficiency?

MANAGEMENT SCIENCE

Iteration
Table 1 Table 2

Machine Machine

Operator A B C D Operator A B C D

1 11 12 10 9 1 2 3 1 0

2 8 10 5 7 2 3 5 0 2

3 11 14 12 13 3 0 3 1 2

4 9 15 8 11 4 1 7 0 3
MANAGEMENT SCIENCE

Iteration
Table 2 Table 3

Machine Machine

Operator A B C D Operator A B C D

1 2 3 1 0 1 2 0 1 0

2 3 5 0 2 2 3 2 0 2

3 0 3 1 2 3 0 0 1 2

4 1 7 0 3 4 1 4 0 3
MANAGEMENT SCIENCE

Iteration
Table 3 Table 4

Machine Machine

Operator A B C D Operator A B C D

1 2 0 1 0 1 2 0 2 0

2 3 2 0 2 2 2 1 0 1

3 0 0 1 2 3 0 0 2 2

4 1 4 0 3 4 0 3 0 2
MANAGEMENT SCIENCE

.
Machine
Operator Machine Time
Operator A B C D

1 2 0 2 0 1 B or D
❎
2 2 1 0 1 2 C ✅
3 0 0 2 2 3 A or B
❎
4 0 3 0 2 4 A or ❎
C
MANAGEMENT SCIENCE

Decision

Time
Operator Machine
(Minutes)

1 D 9

2 C 5

3 B 14

4 A 9

Total 37
MANAGEMENT SCIENCE

Assignment: Unbalanced Case

A dispatcher for the Metro Manila Taxi Company presently has five taxi
cabs at different locations and six customers who have called for service.
The distance (in kilometers) from each taxi’s present location to each
customer is shown in the table.

Customer
Cab
A B C D E F
1 7 5 8 2 3 6
2 2 1 7 5 3 2
3 4 5 6 2 5 4
4 10 6 5 4 8 3
5 7 6 5 5 4 4
MANAGEMENT SCIENCE

Assignment: Unbalanced Case

Table 1

Customer
Cab
A B C D E F
1 7 5 8 2 3 6
2 2 1 7 5 3 2
3 4 5 6 2 5 4
4 10 6 5 4 8 3
5 7 6 5 5 4 4

6 (D) 0 0 0 0 0 0
MANAGEMENT SCIENCE

Table 2

Customer
Cab
A B C D E F
1 5 3 6 0 1 4
2 1 0 6 4 2 1
3 2 3 4 0 3 2
4 7 3 2 1 5 0
5 3 2 1 1 0 0
6 (D) 0 0 0 0 0 0
MANAGEMENT SCIENCE

Table 3

Customer
Cab
A B C D E F
1 5 3 6 0 1 4
2 1 0 6 4 2 1
3 2 3 4 0 3 2
4 7 3 2 1 5 0
5 3 2 1 1 0 0
6 (D) 0 0 0 0 0 0
MANAGEMENT SCIENCE

Table 4

Customer
Cab
A B C D E F
1 4 3 5 0 1 4
2 0 0 5 4 2 1
3 1 3 3 0 3 2
4 6 3 1 1 5 0
5 2 2 0 1 0 0
6 (D) 0 1 0 1 1 1
MANAGEMENT SCIENCE

Table 5

Customer
Cab
A B C D E F
1 3 2 4 0 0 4
2 0 0 5 5 2 2
3 0 2 2 0 2 2
4 5 2 0 1 4 0
5 2 2 0 2 0 1
6 (D) 0 1 0 2 1 2
MANAGEMENT SCIENCE

Prepare the decision and submit your output

MANAGEMENT SCIENCE

Hungarian Method: Maximization

Steps
1. Set up the initial table and determine the BFS

2. Determine the opportunity cost table.

a) Look for the row reducer (Highest entry ) and subtract it from the
row entries
b) Then identify the column reducer, that is the lowest entry, and
subtract it from the column entries
c) Cover the row or column having the most number of zeros with
minimum number of lines.

3. When the optimal solution is not yet obtained.

a) Identify the minimum (lowest) value among the uncovered
entries and subtract it to each value; retain the value of the
covered entries and add the number to the intersectional entries).
b) Repeat the process starting from 2c.
MANAGEMENT SCIENCE

Practice:

Tsikot Car Rental Agency plans to purchase five new automobiles to replace
five older vehicles. The older vehicles are to be sold at auction. The agency has
solicited from five individuals, each whom wishes to buy only one vehicle but
has agreed to make sealed bid to each of the five. The bids are as follows in
terms of (P10, 000):

BUYER TOYOTA MITSUBISHI FORD NISSAN MAZDA

1 12 20 10 8 7
2 10 13 1 9 14
3 5 6 10 7 5
4 9 7 10 9 11
5 10 14 12 10 6

The agency wishes to determine which bid to accept from each of the five bidders so
that each of them can buy one vehicle while the total of the five accepted bids is a
maximum. Provide a sound suggestions backed up with evidence (solution).