Question

5. Use the assignment method (i.e., Hungarian method) to obtain a plan that will minimize the processing costs in the following table under the following condition (provide also the total cost of the plan):

The combination 4-A is undesirable. (15 points)

WORKER ABCDE

1 14 18

2 14 15 Job 3 12 16 4 11 13 5 10 16

20 17 18 19 16 17 15 14 17 14 12 14 15 14 13

  

5. Use the assignment method (i.e., Hungarian method) to obtain a plan that will minimize the processing costs in the following table under the following condition (provide also the total cost of the plan): The combination 4-A is undesirable (15 points) B A 14 14 12 11 10 1 2 3 4 5 WORKER с 20 19 15 14 15 18 15 16 13 16 D 17 16 14 12 14 Job E 18 17 17 14 13

Answer 1

Answer:

As specific information is mentioned in the question, we will solve the given assignment problem by following the steps of the Hungarian Method of Task (Job) Assignment as mentioned below:

We are given the following problem-table:

А B CD DE 1 14 18 20 17 18 2 14 15 1916 17 3 12 16 15 14 17 4 M 13 14 | 12 14 5 10 16 15 14 13

Where A to E = Workers and 1 to 5 = Jobs

As per the condition given in the question, Job 4 can not be assigned to Worker A, so, we have assigned M (i.e., a very high cost, say, 99999)

Step 1: Pick a minimum element from each row and subtract it from that row:

A 10 4 (-14) 2 B C D E 0 4 6 3 0 1 5 2 3 (-14) 3 0 4 3 2 5 (-12) 4 M 1 2 0 2 (-12) 5 0 6 5 4 3 (-10)

Step 2: Now, find out each column minimum element and subtract it from that column:

Hence, we get the following opportunity cost table:

A | B D E 1 2 1 в с 0 3 4 3 2 0 0 3 2 3.0 3 1 2 3 MOOO 5 0 5 3 4 (-0) (-1) (-2) (-0) (-2) 1 4 0 1

Step 3: Make the assignments by following the below-mentioned substeps:

a. Identify rows with exactly one unmarked 0. Make an assignment to this single 0 by making a square ( [0] ) around it and cross off all other 0 in the same column.

b. Identify columns with exactly one unmarked 0. Make an assignment to this single 0 by making a square ( [0] ) around it and cross off all other 0 in the same rows.

c. If a row and/or column has two or more unmarked 0 and one cannot be chosen by inspection, then choose the cell arbitrarily.

d. Continue this process until all 0 in rows/columns are either assigned or cross off( ).

Thus,

(1) Rowwise cell (1,A) is assigned, so columnwise cell (2,A),(3,A),(5,A) crossed off.

(2) Rowwise cell (2,B) is assigned, so columnwise cell (4,B) crossed off.

(3) Columnwise cell (4,C) is assigned, so rowwise cell (4,D),(4,E) crossed off.

A B C D E 1 [O] 3 4 3 2 2 3 2 1 1 [O] 0 3 1 2 3 [0] 5 0 5 3 4 4 MO 1

Here, Number of assignments = 3, number of rows = 5
Which is not equal, so solution is not optimal.

Step 4: Draw a set of horizontal and vertical lines to cover all the '0s' by following the substeps as mentioned below:

a. Tick(✓) mark all the rows in which no assigned 0.

b. Examine Tick(✓) marked rows, If any 0 cell occurs in that row, then tick(✓) mark that column.

c. Examine Tick(✓) marked columns, If any assigned 0 exists in that columns, then tick(✓) mark that row.

d. Repeat this process until no more rows or columns can be marked.

e. Draw a straight line for each unmarked rows and marked columns.

Thus,

(1) Mark(✓) row 3 since it has no assignment

(2) Mark(✓) row 5 since it has no assignment

(3) Mark(✓) column A since row 3 has 0 in this column

(4) Mark(✓) row 1 since column A has an assignment in this row 1.

(5) Since no other rows or columns can be marked, therefore draw straight lines through the unmarked rows 2,4 and marked columns A

Hence, we get:

A B C D E 1| []3 413 2 2 MH3 33+4 3 車」3 1|2|3 4 N1 中中中中 車」5 5 1 4

Step 5:

Develop the new revised table by selecting the smallest element, among the cells not covered by any line (say k = 1)
Subtract k = 1 from every element in the cell not covered by a line.
Add k = 1 to every element in the intersection cell of two lines.

A B D E 1 1 1 BC 0 2 3 2 2 1 0 3 2 3 0 2 0 1 2 4M 0 0 0 0 5 0 4 2 3 0

Step 6: Here, make the assignments by following step 3:

(1) Rowwise cell (1,A) is assigned, so columnwise cell (3,A),(5,A) crossed off.

(2) Rowwise cell (2,B) is assigned, so columnwise cell (4,B) crossed off.

(3) Rowwise cell (3,C) is assigned, so columnwise cell (4,C) crossed off.

(4) Rowwise cell (5,E) is assigned, so columnwise cell (4,E) crossed off.

(5) Rowwise cell (4,D) is assigned

Hence, we get:

B с DE 1 2 1 32 1 1 [O] 2 3 2 [O] *|2|0|1|2 M | 8 | 8 | rol 3 1 2 5 04 2 3 [0]

Here, Number of assignments = 5, number of rows = 5
Which is equal, so the solution is optimal

Hence, the optimal solution=

Worker Total Cost A 14 Job 1 2 3 B с 15 15 12 4 D 5 13 E Total Min Cost 69

(Kindly raise an upvote for this answer, if you found it useful)