Answer to Question #218803 in Operations Research for Jyoti

Question

Estimated sales revenue (in 000 Rs) of 5 salesmen in 5 districts is as given below:

District

C

65

66

57

60

56

Salesman

P

Q

R

S

T

A

55 85

90

75

80

76

B

75

78

66

72

64

D

125

132

114

120

112

E

75

78

69

72

68

- 414

Find an optimal solution for maximising the total revenue.

Answer 1

$\text{We want to find an optimal solution for maximising total revenue. We can do this }\\\text{using the Hungarian method, we first tabularize the given data:}\\\begin{matrix} & A & B &C&D&E \\\hline P& 55&75&65&125&75\\Q&90&78&66&132&78\\R&75&66&57&114&69\\S&80&72&60&120&72\\T&76&64&56&112&68 \end{matrix}$

$\text{The given problem is a balanced maximisation problem, so at first we need to }\\\text{convert the matrix into cost/loss matrix. By subtracting all the values in the}\\\text{matrix from the largest value in the matrix(132). we have:}$

$\begin{matrix} & A & B &C&D&E \\\hline P& 77&57&67&7&57\\Q&42&54&66&0&54\\R&57&66&75&18&63\\S&52&60&72&12&60\\T&56&68&76&20&64 \end{matrix}$

$\text{By subtracting the smallest vlaue in the row from all elements in the row }\\\text{and subtracting the smallest value in the column from all elements in the }\\\text{column,we obtain the matrix below, we then cover the zeros using the }\\\text{using the lines below:}$

$\begin{matrix} & A & B &C&D&E \\\hline P& 34&2&4&0&6\\Q&6&6&10&0&10\\R&3&0&1&0&1\\S&4&0&4&0&4\\T&0&0&0&0&0 \end{matrix}$

$\text{The solution is not optimal. The minimum uncovered element is 1 that is}\\\text{ subtracted from all elements and added to all elements at intersections.}\\\text{This yields the following matrix }$

$\begin{matrix} & A & B &C&D&E \\\hline P& 33&2&3&0&5\\Q&5&6&9&0&9\\R&2&0&0&0&0\\S&3&0&3&0&3\\T&0&1&0&1&0 \end{matrix}$

$\text{By repeating the steps above we get the matrix below: }$

$\begin{matrix} & A & B &C&D&E \\\hline P& 31&0&1&0&3\\Q&3&4&7&0&7\\R&2&0&0&2&0\\S&3&0&3&2&3\\T&0&1&0&3&0 \end{matrix}$

$\text{We repeat the steps above to get the matrix below: }$

$\begin{matrix} & A & B &C&D&E \\\hline P& 30&0&0&0&2 \\\hline Q&2&4&6&0&6 \\\hline R&2&1&0&3&0\\\hline S&2&0&3&2&2\\\hline T&0&2&0&4&0\\\hline \end{matrix}$

$\text{Since the no. of lines = No. of row/column=5, optimal solution is possible. }\\\text{Here by following the steps we first allot at cell13 [12 means 1st Row 3rd}\\\text{ Column] now tie appears as there are more than one zeros in remaining rows}\\\text{/columns. So, we arbitrarily allot assignment in Cell24, then we allot }\\\text{assignment in cell35, cell42 and cell 51. Therefore our final answer is:}$

$\begin{matrix} Salesperson & Districts&Sales Revenue\\\hline P&A&65\\Q&B&132\\R&C&69\\S&D&72\\T&E&76\\& Total Revenue&414 \end{matrix}$