Answer to Question #242476 in Operations Research for opr

Question

A company has 5 salesmen and 5 customers to attend to on a particular day. The company has estimated the savings in dollars associated with assigning a particular salesman to a specific client. These estimates are given in the table below.

clients

1 2 3 4 5

A 30 37 40 28 40

B 40 24 27 21 36

Salesmen C 40 32 33 30 35

D 25 38 40 36 36

E 29 62 41 34 39

Determine who should be assigned which client and the maximum savings the company can achieve from the allocations

Answer 1

using Hungarian method:

Here the problem is of Maximazition type and convert it into minimization by substracting it from maximum value 62

Here given problem is balanced.

Step-1: Find out the each row minimum element and subtract it from that row

Step-2: Find out the each column minimum element and subtract it from that column.

Iteration-1 of steps 3 to 6

Step-3: Make assignment in the opporunity cost table

a. Identify rows with exactly one unmarked 0. Make an assignmment to this single 0 by make 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 assignmment to this single 0 by make 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 arbitarily.

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

Step-3: Make assignment in the opporunity cost table

(1) Rowwise cell (B,1) is assigned, so columnwise cell (C,1) crossed off.

(2) Rowwise cell (E,2) is assigned

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

(4) Columnwise cell (A,3) is assigned, so rowwise cell (A,5) crossed off.

Rowwise & columnwise assignment shown in table

Step-4: Number of assignments = 4, number of rows = 5

Which is not equal, so solution is not optimal.

Step-5: Draw a set of horizontal and vertical lines to cover all the 0

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.

f. If the number of lines is equal to the number of rows then the current solution is the optimal, otherwise goto step-6

Step-5: Cover the 0 with minimum number of lines

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

(2) Mark(✓) column 1 since row C has 0 in this column

(3) Mark(✓) row B since column 1 has an assignment in this row B.

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

Tick mark not allocated rows and allocated columns

Step-6: Develop the new revised table by selecting the smallest element, among the cells not covered by any line (say k = 4)

Subtract k = 4 from every element in the cell not covered by a line.

Add k = 4 to every elment in the intersection cell of two lines.

Repeat steps 3 to 6 until an optimal solution is obtained.

Iteration : 1

Iteration-2 of steps 3 to 6

Step-3: Make assignment in the opporunity cost table

(1) Rowwise cell (C,1) is assigned, so columnwise cell (B,1) crossed off.

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

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

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

(5) Rowwise cell (E,2) is assigned

Rowwise & columnwise assignment shown in table

Step-4: Number of assignments = 5, number of rows = 5

Which is equal, so solution is optimal

Optimal assignments are

Optimal solution is