Introduction to Management Science (10th Edition)

The assignment model is a special form of a linear programming model that is similar to the transportation model. There are differences, however. In the assignment model, the supply at each source and the demand at each destination are each limited to one unit.

An assignment problem is a special form of transportation problem where all supply and demand values equal one .

The following example from the text will be used to demonstrate the assignment model and its special solution method. The Atlantic Coast Conference has four basketball games on a particular night. The conference office wants to assign four teams of officials to the four games in a way that will minimize the total distance traveled by the officials. The distances in miles for each team of officials to each game location are shown in Table B-34.

Table B-34. The Travel Distances to Each Game for Each Team of Officials

The supply is always one team of officials, and the demand is for only one team of officials at each game. Table B-34 is already in the proper form for the assignment.

An opportunity cost table is developed by first substracting the minimum value in each row from all other row values and then repeating this process for each column .

The first step in the assignment method of solution is to develop an opportunity cost table . We accomplish this by first subtracting the minimum value in each row from every value in the row. These computations are referred to as row reductions . We applied a similar principle in the VAM method when we determined penalty costs. In other words, the best course of action is determined for each row, and the penalty or "lost opportunity" is developed for all other row values. The row reductions for this example are shown in Table B-35.

Table B-35. The Assignment Tableau with Row Reductions

Next, the minimum value in each column is subtracted from all column values. These computations are called column reductions and are shown in Table B-36. It represents the completed opportunity cost table for our example. Assignments can be made in this table wherever a zero is present. For example, team A can be assigned to Atlanta. An optimal solution results when each of the four teams can be uniquely assigned to a different game.

Table B-36. The Tableau with Column Reductions

Notice in Table B-36 that the assignment of team A to Atlanta means that no other team can be assigned to that game. Once this assignment is made, the zero in row B is infeasible, which indicates that there is not a unique optimal assignment for team B. Therefore, Table B-36 does not contain an optimal solution.

Assignments are made to locations with zeros in the opportunity cost table .

An optimal solution occurs when the number of independent unique assignments equals the number of rows or columns .

A test to determine if four unique assignments exist in Table B-36 is to draw the minimum number of horizontal or vertical lines necessary to cross out all zeros through the rows and columns of the table. For example, Table B-37 shows that three lines are required to cross out all zeros.

Table B-37. The Opportunity Cost Table with the Line Test

The three lines indicate that there are only three unique assignments, whereas four are required for an optimal solution. (Note that even if the three lines could have been drawn differently, the subsequent solution method would not be affected.) Next, subtract the minimum value that is not crossed out from all values not crossed out. Then add this minimum value to those cells where two lines intersect. The minimum value not crossed out in Table B-37 is 15. The second iteration for this model with the appropriate changes is shown in Table B-38.

Table B-38. The Second Iteration

If the number of unique assignments is less than the number of rows (or columns), a line test must be used .

No matter how the lines are drawn in Table B-38, at least four are required to cross out all the zeros. This indicates that four unique assignments can be made and that an optimal solution has been reached. Now let us make the assignments from Table B-38.

In a line test, all zeros are crossed out by horizontal and vertical lines; the minimum uncrossed value is subtracted from all uncrossed values and added to cell values where two lines cross .

First, team A can be assigned to either the Atlanta game or the Clemson game. We will assign team A to Atlanta first. This means that team A cannot be assigned to any other game, and no other team can be assigned to Atlanta. Therefore, row A and the Atlanta column can be eliminated. Next, team B is assigned to Raleigh. (Team B cannot be assigned to Atlanta, which has already been eliminated.) The third assignment is of team C to the Durham game. This leaves team D for the Clemson game. These assignments and their respective distances (from Table B-34) are summarized as follows .

Now let us go back and make the initial assignment of team A to Clemson (the alternative assignment we did not initially make). This will result in the following set of assignments.

These two assignments represent multiple optimal solutions for our example problem. Both assignments will result in the officials traveling a minimum total distance of 450 miles.

Like a transportation problem, an assignment model can be unbalanced when supply exceeds demand or demand exceeds supply. For example, assume that, instead of four teams of officials, there are five teams to be assigned to the four games. In this case a dummy column is added to the assignment tableau to balance the model, as shown in Table B-39.

Table B-39. An Unbalanced Assignment Tableau with a Dummy Column

When supply exceeds demands, a dummy column is added to the assignment tableau .

In solving this model, one team of officials would be assigned to the dummy column. If there were five games and only four teams of officials, a dummy row would be added instead of a dummy column. The addition of a dummy row or column does not affect the solution method.

When demand exceeds supply, a dummy row is added to the assignment tableau .

Prohibited assignments are also possible in an assignment problem, just as prohibited routes can occur in a transportation model. In the transportation model, an M value was assigned as a large cost for the cell representing the prohibited route. This same method is used for a prohibited assignment. A value of M is placed in the cell that represents the prohibited assignment.

A prohibited assignment is given a large relative cost of M so that it will never be selected .

The steps of the assignment solution method are summarized here.

1. Perform row reductions by subtracting the minimum value in each row from all row values.

2. Perform column reductions by subtracting the minimum value in each column from all column values.

3. In the completed opportunity cost table, cross out all zeros, using the minimum number of horizontal or vertical lines.

4. If fewer than m lines are required (where m = the number of rows or columns), subtract the minimum uncrossed value from all uncrossed values, and add this same minimum value to all cells where two lines intersect. Leave all other values unchanged, and repeat step 3.

5. If m lines are required, the tableau contains the optimal solution and m unique assignments can be made. If fewer than m lines are required, repeat step 4.