**ASSIGNMENT MODEL**

design by Dóri Sirály for Prezi

Assignment Model

a problem that requires pairing two sets of items given a set of paired costs/profits in such a way that the total cost/profit of the pairings is minimized or maximized

Steps in solving assignment model using hungarian method

Subtract the lowest entry in such row/column of the given cost table from all entries in that row/column.

Subtract the lowest entry in each column/row of the table obtained in part from all numbers in that column/row.

STEP 3

**Minimization problem**

Hungarian method or

Flood's technique

an algorithm used to determine an optimal solution to an assignment problem

Dénes Kőnig

named after a Hungarian mathematician

hungarian method

- yields optimal solutions to the assignment model

- based on mathematically proven algorithm for determining the optimal solution

- related on the opportunity losses in Vogel's Approximation Method of the transportation problem

- it gives zero opportunity losses

THE BASIC IDEA IN THIS METHOD IS TO AVOID OPPORTUNITY LOSSES.

The assignment problem is a special case of transportation problem in which the objective is to assign a number of origins to the equal number of destinations at the minimum cost (or maximum profit).

Step 1

Determine the opportunity cost table

for maximization problem

Subtract each entry in the row/column from the highest entry in each row/column.

step 2

Determine whether an optimal assignment can be made.

Draw straight lines vertically and horizontally, using the least number of lines possible.

An optimal assignment can be made when the number of lines equals the number of rows/columns.

IF THE NUMBER OF LINES DRAWN ID FEWER THAN THE NUMBER OF ROWS/COLUMNS, AN OPTIMAL ASSIGNMENT CANNOT BE MADE AND THE PROBLEM IS NOT SOLVED!

REVISE THE TOTAL OPPORTUNITY-COST TABLE

Select the smallest value of the uncovered line row/column.

Subtract the number from all numbers not covered by a straight line

Add this same number to the numbers lying at the intersection of any two lines.

for minimization problem

THE MINIMUM MUST BE ONE!

Copy the entries covered by a single line, then return to step 2.

unbalanced assignment model:

Maximization Problem

A dummy row/column is being added to satisfy the one-to-one relationship for an assignment model.

example:

A high school department head has five teachers to be assigned to four different year levels. All of the teachers have taught the different year levels in the past and have been evaluated by the students. the ratings for each teacher for each year level is given in the following table.