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 8-35. Game Sites c 30 15 60 35 40 55 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, which 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 our teams can be uniquely assigned to a different game. Table B-36 The Tableau with Column Reductions D 25 5 75 10 page 8-23 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. Table B-37 The Opportunity Cost Table with the Line Test 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. A test to determine whether 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.
If the number of unique assignments is less than the number of rows (or columns), a line test must be used. 0 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 loud 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 3-38. Table B-38 The Second Iteration 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. 8-23 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. 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 as 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: Assignment Team B Team C Team D Distance Atlanta Raleigh Durham Clemson 450 miles B_24 1/9/09 page 8-24 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: Assign meet Team A When supply exceeds demands, a dummy column is added to the assignment tableau. Table B-39 An Unbalanced Assignment Tableau with a Dummy Column 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. A prohibited assignment is given large relative cost of M so that it will never be selected.
