Unit – 6

Assignment Problem

Q1) 1      2       3       4 (Tasks)  

Column Reduction

Workers

A1)

Row reduction:

column reduction:

Q2) Three men are to be given 3 jobs and it is assumed that a person is fully capable of doing job independently. The following table gives an idea of that cost incurred to complete each job by each person

Formulate as linear programming problem

A2)

The given problem can easily be formulated as a linear programming (transportation) model as under.

Z = (20 +28+ 21) + (15 +35+ 17)+ (18 +32+ 20)

++ = 1

++ = 1       , where i =1, 2, 3, ……

++ = 1

Since each job can be assigned to only one person, therefore three equations for three different persons three different jobs.

The given problem is just a special case of the transportation problem.

Q 3: you work as a sales manager for a toy manufacturer, and you currently have three salespeople on the road meeting buyers. Your salespeople are in Austin, TX Boston, MA; and Chicago, IL. You want them to fly to three other cities: Denver, CO; Edmonton, Alberta; and Fargo, ND. The table below shows the cost of airplane tickets in dollars between these cities.

Where should you send each of your salespeople in order to minimize airfare?

A3)

Step 1: Subtract 250 from row 1, 350 from row2, and 200 from row 3.

Step 2: Subtract 0 from column 1, 150 from column 2, and 0 from column 3.

Step 3: Cover all the zeros of the matrix with the minimum number of horizontal or vertical lines.

Step 4: Since the minimal number of lines is 3, an optimal assignment of zeros is possible and we are finished. Since the total cost for this assignment is 0, it must be an optimal assignment.

Here is the same assignment made to the original cost matrix.

Q4) A construction company has four large bulldozers located at four different garages. The bulldozers are to be moved to four different construction sites are given below.

How should bulldozers be moved to the construction sites in order to minimize the total distance travelled?

A4)

Step 1: Subtract 75 from row 1, 35 from row 2, 90 from row 3, and 45 from row 4.

Step 2: Subtract 0 from colum 1, 0 from column 2, 0 from column 3, and 5 from column 4.

Step 3: Cover all the zeros of the matrix with the minimum number of horizontal or vertical lines.

Step 4: Since the minimal number of lines is less than 4, we have to proceed to step 5.

Step 5: Note that 5 is the smallest entry not covered by any line. Subtract from each uncovered row.

Now add 5 to each covered column.

Now return to step 3.

Step 3: Cover all the zeros of the matrix with the minimum number of horizontal or vertical lines.

step 4: Since the minimal number of lines is less than 4, we have to return to step 5.

Step 5: Note that 20 is the smallest entry not covered by a line. Subtract 20 from each uncovered row.

Then add 20 to each covered column.

Now return to step 3

Step 3: Cover all the zeros of the matrix with the minimum number of horizontal or vertical lines.

Step 4: Since the minimal number of lines is 4, an optimal assignment of zeros is possible and we are finished.

Since the total cost for assignment is 0, it must be an optimal assignment.

Here is the same assignment made to the original cost matrix.

So, we should send Bulldozer 1 to site D, Bulldozer 2 to site C, Bulldozer 3 to site B, and Bulldozer 4 to site A.

Q5) Using the following cost matrix, determine

(i)                Optimal job assignment.

(ii)             The cost of assignment.

A5)

Here, no.of rows = no.of columns, In other words, no.of workers = no.of jobs. So, it is a balanced assignment problem.

Step 1: Subtract the smallest element of each row from all the elements of that row.

step 2: Subtract the smallest element of each column from all the elements of that column.

Step 3: cover all zeros

(a)  Cover all zeros of the matrix with the minimum number of horizontal or vertical lines. If the number of lines drawn is equal to the order of the matrix then the solution is optimal.

The minimum number of lines that cover all the zeros = 3. And is not equal to the number of rows/columns. Proceed to next step.

(b) Select all smallest elements from the matrix which is not covered by  lines (here 2 is the smallest and uncovered elements
Subtract the elements from all the uncovered elements and add this smallest element to the element lying at the intersection of lines repeat step 3(a) and 3(b)

 As the minimum number of lines that cover all zeros =4. And equal to the number of rows/columns.

Therefore, the solution is optimal.

Step 4: Assign the zeros.

(a)  Examine the rows which contain only one ‘zero ‘element. Make an assignment to this single zero by encircling it. Cross all other zeros, as these will not be considered for any future assignment. Continue till all the rows have been examined.

(b) Now, examine the columns containing only one ‘zero’. Encircle this zero and make an assignment there. Then cross any other zero and continue till all the columns are eliminated

(c)  Repeat the step 4(A) and 4(b) until all the assignments have been made.

(d) While assigning, if there is no single zero exists in the row or column, then select any zero arbitrary and encircle it and cross all other zeros in the column and row in respect of which the assignment is made.

Therefore, the optimal job assignment is (1-c), (2-B), (3-D), (4-A)

Total cost = 9+4+11+4 = 28.

Q6) solve the balanced assignment problem.

A6)

Step 1: row reduction                  step 2: column reduction

  Therefore, the optimum cost is Rs.38 (12+7+11+8 =38).

Q7) Recently, Yadaiah and haragopal published in the American journal of operations Research a new approach to solving the unbalanced assignment problem. They also provide a numerical example which they solve with their approach and get a cost of 1550 which they claim is optimum. This approach might be of interest; however, their approach does not guarantee the optimal solution. In this short paper, we will show that solving this sample textbook formulation to balance the problem and then solve it with the classic Hungarian method Of Kuhn yields the true optimal solution with a cost of 1520.

A7)

first sub-problem:

870 + 680 = 1550. It can easily be checked using the Hungarian method, that these sub-problems were solved optimally. In their paper,

Yadaiah and Haragopal have a minor typo.

We will now solve the original problem of assigning these eight jobs to five machines such that machine is used at least once, but not more than twice.

Second sub-problem

Final Hungarian method cost matrix

For a total minimum cost of 1520 (not 1550).

Q8) Let us consider a problem with 8worker and 4 tasks. Its worker-task assignment cost matrix is shown in table

A8)

Step 1: Create an unbalanced matrix problem for worker task assignment cost matrix.

Step 2: Obtain table 2 by adding duplicate or one dummy task with all 1 assignment cost to given table

Step 3: Calculate a reduced cost matrix by dividing each row by minimum cost of its column. Reduced cost matrix obtained from table 2.

Step 4: Look for the row with one reduced cost excluding 1 from dummy column. Assign worker to task according to position of the choosen 1 and mark entire row to avoid later redundant assignment as shown in above table.

Step 5: Look for the column with one reduced cost excluding 1 from dummy row. Assign worker to task according to position of the chosen 1 and mark entire column to avoid later redundant assignment as shown in above table.

Step 6: Choose one of remaining 1 in the reduced cost matrix as a position to assign worker to task. Mark row and colum of chosen 1 to avoid later redundant assignment. After applying step 6 to the matrix in table 4, we get the new matrix as shown in table 5.

Step 7: Assign dummy task to the first n-m agent from table 5, we assign dummy task to 8-4 workers as shown in table 6

Step 8: Count the number of assigned text excluding dummy task. If it is equal to the number of tasks then go to step 11(5)

Step 9: Mark row assignment excluding dummy task assignment and mark dummy column. The marked rows/column from our examples are shown in table 7.

Step 10: Look for the minimum cost among remaining (unmarked) costs. Recalculate the reduced cost table by dividing each remaining cost by the minimum cost and replace 0 at intersection with the minimum cost. And go to step 4. Table 8 shows the modified reduced matrix.

Step 11: Calculate total assignment cost.

Suppose B - >1, D - >2, E – >3 and H - >4. The total cost for this assignment is calculated as follows.

Min(T) =

Q9) A travelling salesman has to visit five cities. He wishes to start from a particular city, visit each city and then return to his starting point. The travelling cost (in Rs.) of each city from a particular city is given below.

Travelling salesman problem:

What should be the sequence of the salesman’s visit, so that the cost is minimum?

A9)

The optimal solution is reached using Hungarian method.

The assignment shown in the above table gives the route sequence

AB, BC, CD, DE, EA

The travelling cost to this solution is 2000 + 3000 + 4000 + 5000 + 1000 = 15,000.

Therefore, the sequence feasible for this assignment is

A with the travelling cost of Rs. 15,000.

Q10) A sales man has to visit five cities A, B, C, D AND E.the intercity distances are tabulated below

The above distances in km between two cities need not be same both ways. Which route would you advise the salesman to take so that the total distance travelled by him is minimum, if the salesman starts from city A and has to come back to city ‘A’.

A10)

step 1: Select smallest element in each row and subtract it from every element of that row. Row reduction results in the following table.

Step 2: Select the minimum element in each column and subtract this element from every element in that column, we get

Step 3: Cover all zeros and get the final minimum solution

Optimal schedule is B C, C D, D E, E A

Involving distance 12 + 17 + 19 + 12 = 77 km.

This route satisfies the travelling salesman problem.