PRIVATE UNIVERSITY OF TACNA

FACULTY OF ENGINEERING
Professional School of Systems Engineering

ASSIGNMENT MODEL

Course: Operations Research

Teacher: Eng. Minelly Martinez Peñaloza

Members:

Mauricio Daniel Puma Chipana

Tacna–Peru
2017
 ASSIGNMENT MODEL

GENERAL INDEX

INTRODUCTION.
ASSIGNMENT MODEL........................................................................................................... 4
1. OBJECTIVES .......................................................................................................................... 4
2. DEVELOPMENT OF THE WORKO ......................................................................................... 4
2.1. DEFINITION.................................................................................................................. 4
2.2. METHOD HUNGARIAN5
CONCLUSIONES11
RECOMMENDATIONS.................................................................................................................. 12
BIBLIOGRAPHYA ............................................................................................................................... 13

2
 ASSIGNMENT MODEL

INTRODUCTION

The following work aims to present and apply the allocation model using the method
Hungarian as a tool that manages to solve problems that develop in the field of
engineering.

This assignment model is a special case of linear programming that deals with the following
Issue: there are "n" tasks to be performed and "n" workers available to execute them. Due to
to differences in the skills of the workers and therefore in their performance, as well as to
differences in salaries, preparation, experience, etc., the cost of assigning a job to a worker
it is different from the one incurred if assigned to another. (Cost in time, money, etc.).

The assignment model obtains the optimal (minimum) solution for distributing the jobs among the
workers. Theory will be complemented with examples using this method.

3
 ASSIGNMENT MODEL

ASSIGNMENT MODEL

1. OBJECTIVES

1.1. GENERAL:
- Apply the allocation model for solving optimization exercises.

SPECIFIC:
- Understand and analyze the allocation model.
- Identify the Hungarian method as a procedure to solve problems of
assignment.
- Solve exercises using the assignment model.

2. DEVELOPMENT OF THE WORK

2.1. DEFINITION

One of the most common activities in business is the assignment of the 'ideal' person for the
efficient execution of a particular task; however, the way to carry this out
assignment presents certain implicit difficulties, for example, who is the right person to
Each task?, is the cost of this assignment minimal?, as well as what type of information does it support?
assignment made? These questions find answers in the Allocation Model and its
solution.

In general, the allocation involves people, but it is also used to assign plants.
industrial, vehicles and even time periods with specific tasks. The importance of
presenting and solving the allocation model is based on optimizing some objective such as:

• Minimize production times.

Since the assignment model is a particular case of the transportation model; usually,
the first was resolved with the tools of the second, but given the characteristics of the model

4
 ASSIGNMENT MODEL

for assignment, the investment in calculations and computing time was too high. Consequently,
Two Hungarian mathematicians developed an algorithm to efficiently solve the
assignment model, known as the Hungarian Method.

2.2. HUNGARIAN METHOD

We will use examples to present the mechanics of the algorithm.

Example 1.

Joe Klyne's three children, John, Karen, and Terri, want to earn some money for their expenses.
personal. Mr. Klyne chose three tasks for his children: mowing the lawn, painting the door of the
garage and wash the family cars. To avoid early competition among the
Brothers, he asks you to submit individual (secret) bids for what you consider a payment.

TO GIVE PAINT TO WASH

JOHN $15 $10 $9

KAREN $9 $15 $10

TERRI $10 $12 $8

Table 1. Mr. Klyne's Assignment Problem

TO GIVE PAINTING LAVAR MIN. LINE

JOHN 15 10 9 =9
1

KAREN 9 15 10
2= 9

TERRI 10 12 8
3= 8

Table 2 Step 1.

Step 1. Determine , the minimum cost element in the row from the original cost matrix, and

subtract it from all the elements of the row , = 1, 2, 3.

5
 ASSIGNMENT MODEL

TO GIVE PAINT TO WASH

JOHN 6 1 0

KAREN 0 6 1

TERRI 2 4 0

COLUMN
1= 0 2= 1 3= 0
MAX.
Table 3 Step 2.

Step 2. For the matrix created in step 1, determine the minimum cost element of the column

, and subtract it from all elements in the column , = 1, 2, 3.

PODAR PAINT WASH

JOHN 6 0 0

KAREN 0 5 1

TERRI 2 3 0

Table 4 Step 3.

Step 3. Identify the assignment zeros, which are unique in their row and column (there may be
more zeros in the row or column, but only one is for assignment). The position of the zeros of
assignment indicates the task that corresponds to each assignment candidate. If the number of zeros
the assignment is equal to the number of tasks, finish and calculate the cost of the model. Otherwise,
continue.

Note: The cells with zero entries underlined in step 3 give the optimal solution.
(feasible): John gets the job of painting, Karen gets the job of mowing the lawn, and Terri gets the
to wash the family cars.

The total cost for Mr. Klyne is9 + 8 + 8 = $27

6
 ASSIGNMENT MODEL

Step 4. When it is not possible to obtain all assignment zeros, proceed to:

4a. Cover all the zeros in the table with the least number of vertical and horizontal lines.

4b. Select the lowest uncovered cost by any line and subtract it from all uncovered costs.
Cutlery. Add to the costs where there is an intersection of the lines, the lower cost
selected.

4c. The costs covered by a single line remain the same.

[Link] back to step 3.

Example 2.

Assume that the three people A, B, and C are to be assigned the tasks TI, TII, and TIII, but with
significant changes in costs, which are for person A in tasks TI, TII and
TIII, $21, $18 and $23, respectively; likewise, for B the costs are $33, $28 and $43, for TI.
TII and TIII, while for C the costs are $21, $25, and $24 for the same tasks. Determine
the assignment to obtain the minimum cost of the assignment model.

IT TII TII

A 21 18 23

B 33 28 43

C 21 25 24

Step 1. Identify the smallest cost in the row and subtract it from all elements of the row.
corresponding.

TI TII TII LOWER COST

A 21 18 23 18

B 33 28 43 28

C 21 25 24 21

7
 ASSIGNMENT MODEL

The result of subtracting the lowest cost per row is shown in the following table:

TI TII TIII

A 3 0 5

B 5 0 15

C 0 4 3

In the table resulting from the previous point, identify the lowest cost by column and
subtract it from all the elements of the corresponding column.

TI TII TIII

A 3 0 5

B 5 0 15

C 0 4 3

COST 0 0 3
MINOR

Note that the lowest cost per column for TI and TII is zero. The result of the cost subtraction
the smallest by column is:

IT TII TIII

A 3 0 2

B 5 0 12

C 0 4 0

Identify the assignment zeros that are unique in their row and column (there may be more)
zeros in the row or column, but only one is for assignment.
For this table, it can be observed that the number of allocated zeros cannot be matched to the number of
tasks, three for this case, so we continue with Step 5 of the general algorithm.

8
 ASSIGNMENT MODEL

When it is not possible to obtain all the assignment zeros, the following steps are taken:

a) Cover all the zeros in the table with the smallest number of vertical and horizontal lines.

IT TII TII

A 3 0 2

B 5 0 12

C 0 4 0

The least number of vertical and horizontal lines for this case were drawn on the table.

b) Select the lowest uncovered cost and subtract it from all uncovered costs.
Add to the costs where there is an intersection of the lines the selected lowest cost.

The lowest cost not covered by any line is $2, so subtracting $2 from the other costs does not
cutlery generates the following table:

TI TI TII

A 1 0

B 3 10

The sum of $2 to the elements where there is an intersection is:

A 1 0

B 3 10

C 6

9
 ASSIGNMENT MODEL

c) The costs covered by a single line remain the same.

IT TII TII

A 1 0 0

B 3 0 10

C 0 6 0

Find the assignment zeros, this is shown below, I exchange column TI for the
column TIII.
TIII TII TI

A 0 0 1

B 10 0 3

C 0 6 0

Thus, it is observed that the position of the assignment zeros indicates the task that corresponds to each.
assignment candidate. For this case:

Person A is assigned to task TIII, person B is assigned to task TII, and person C is assigned to
the IT task.

As the number of assignment zeros is equal to the number of tasks, three in this case, it ends the
method; to calculate the cost of the model, we retrieve from the original table the associated costs
the proposed allocation and we add to obtain the total cost, that is, for A in TIII $23, for
For B in TII $28 and for C in TI $21, then the minimum total cost is $23 + $28 + $21 = 72.

10
ASSIGNMENT MODEL

conclusions

- As we have seen, it is easy to apply this method; at the same time, it is a great
alternative to solve optimization problems, these can be minimization
of the total cost, the maximization of profits or the minimization of total time
involved.

11
ASSIGNMENT MODEL

RECOMMENDATIONS

- It is important to strictly follow the steps to find a feasible solution.

12
ASSIGNMENT MODEL

BIBLIOGRAPHY

- Carvajal G., J. A. (2003). Class notes 'Operational Research'. University

- Cuellar Romo, N. H. (n.d.). Mathematics for Business. ED BANKING AND COMMERCE.

- Taha, H. (2011). Operations Research. Pearson.

13