Maximization Assignment Problem Example

7

Step-3: Starting with row 1, enrectangle the single zero if any, and cross out all the zero above the enrectangle zero. Then we get

∞ 1 3 0 1

1 ∞ 2 ⊗ 1

2 1 ∞ 2 0

0 0 3 ∞ 4

0 ⊗ ⊗ 3 ∞

Step-4: Applying the line operation:

1. Tick () the row which does not have any assignment i.e row 2. 2. There is a zero in the 4th column of the ticked row so we ticked the column 4. 3. further there is an assignment in the 1st row of the ticked column. So we tick

the row 1. 4. draw the lines through all the unmarked rows and marked column, we get the

following reduced matrix:-

∞ 1 3 0 1 ()

1 ∞ 2 ⊗ 1 ()

2 1 ∞ 2 0

0 0 3 ∞ 4

0 ⊗ ⊗ 3 ∞

()

Step5: In step 4, we observe that the minimum number of lines drawn is 4 which is less than the order of the matrix 5, which indicates that the current assignment is not optimal. To increase the minimum number of lines we generate new zeros in the modified matrix. Step 6: Here in the last reduced matrix the smallest element not covered by lines is 1, subtracting this smallest element 1 from all the uncovered elements and adding the same to the elements lying at the junction of the lines, rest of the elements remains the same, we get the following reduced matrix :

∞ ⊗ 2 0 ⊗

0 ∞ 1 ⊗ ⊗

2 1 ∞ 3 0

0 0 3 ∞ 4

⊗ ⊗ 0 4 ∞

The optimum assignment is A→D, B→A, C→E, D→B and E→C with the minimum cost of 20.

Docsity.com

There are problems where certain facilities have to be assigned to a number of jobs, so as to maximize the overall performance of the assignment.

The Hungarian Method can also solve such assignment problems, as it is easy to obtain an equivalent minimization problem by converting every number in the matrix to an opportunity loss.

The conversion is accomplished by subtracting all the elements of the given matrix from the highest element. It turns out that minimizing opportunity loss produces the same assignment solution as the original maximization problem.

Example: Maximization In An Assignment Problem

At the head office of www.universalteacherpublications.com there are five registration counters. Five persons are available for service.

Person
Counter A B C D E
1 30 37 40 28 40
2 40 24 27 21 36
3 40 32 33 30 35
4 25 38 40 36 36
5 29 62 41 34 39

How should the counters be assigned to persons so as to maximize the profit?

Solution.

Here, the highest value is 62. So we subtract each value from 62. The conversion is shown in the following table.

Table

On small screens, scroll horizontally to view full calculation

Person
Counter A B C D E
1 32 25 22 34 22
2 22 38 35 41 26
3 22 30 29 32 27
4 37 24 22 26 26
5 33 0 21 28 23

Now the above problem can be easily solved by Hungarian method. After applying steps 1 to 3 of the Hungarian method, we get the following matrix.

Table

Draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix.

Table

Select the smallest element from all the uncovered elements, i.e., 4. Subtract this element from all the uncovered elements and add it to the elements, which lie at the intersection of two lines. Thus, we obtain another reduced matrix for fresh assignment. Repeating step 3, we obtain a solution which is shown in the following table.

Final Table: Maximization Problem

Use Horizontal Scrollbar to View Full Table Calculation

The total cost of assignment = 1C + 2E + 3A + 4D + 5B

Substituting values from original table:
40 + 36 + 40 + 36 + 62 = 214.

0 Replies to “Maximization Assignment Problem Example”

Lascia un Commento

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *