An assignment problem is a particular case of transportation problem where the objective is to assign a number of resources to an equal number of activities so as to minimise total cost or maximize total profit of allocation. The problem of assignment arises because available resources such as men, machines etc. have varying degrees of efficiency for performing different activities, therefore, cost, profit or loss of performing the different activities is different. Thus, the problem is “How should the assignments be made so as to optimize the given objective”. Some of the problem where the assignment technique may be useful are assignment of workers to machines, salesman to different sales areas.
An assignment problem can be mathematically formulated as follows: Minimise the total cost \[Z= \sum_{i=1}^n\sum_{j=1}^n c_{ij}.x_{ij}\]where \(x_{ij} =1\), if \(i^{th}\) person is assigned to the \(j^{th}\) job subject to the constraints i) \(\sum_{i=1}^n x_{ij} = 1, j=1, 2, \cdots n\) which means that only one job is done by the \(i^{th}\) person, \(i= 1, 2, \cdots, n\) ii) \(\sum_{i=1}^n x_{ij} = 1, j=1, 2, \cdots n\) which means that only one person should be assigned to the \(j^{th}\) person, \(j= 1, 2, \cdots, n\)
The Hungarian method of assignment provides us with an efficient method of finding the optimal solution without having to make a-direct comparison of every solution. It works on the principle of reducing the given cost matrix to a matrix of opportunity costs. Opportunity cost show the relative penalties associated with assigning resources to an activity as opposed to making the best or least cost assignment. If we can reduce the cost matrix to the extent of having at least one zero in each row and column, it will be possible to make optimal assignment. The Hungarian method can be summarized in the following steps: Step 1: Develop the Cost Table from the given Problem If the no of rows are not equal to the no of columns and vice versa, a dummy row or dummy column must be added. The assignment cost for dummy cells are always zero. Step 2: Find the Opportunity Cost Table (a) Locate the smallest element in each row of the given cost table and then subtract that from each element of that row, and (b) In the reduced matrix obtained from 2 (a) locate the smallest element in each column and then subtract that from each element. Each row and column now have at least one zero value. Step 3: Make Assignment in the Opportunity Cost Matrix The procedure of making assignment is as follows: (a) Examine rows successively until a row with exactly one unmarked zero is obtained. Make an assignment single zero by making a square around it. (b) For each zero value that becomes assigned, eliminate (Strike off) all other zeros in the same row and/ or column (c) Repeat step 3 (a) and 3 (b) for each column also with exactly single zero value all that has not been assigned. (d) If a row and/or column has two or more unmarked zeros and one cannot be chosen by inspection, then choose the assigned zero cell arbitrarily. (e) Continue this process until all zeros in row column are either enclosed (Assigned) or struck off (x) Step 4: Optimality Criterion If the member of assigned cells is equal to the numbers of rows column then it is optimal solution. The total cost associated with this solution is obtained by adding original cost figures in the occupied cells. If a zero cell was chosen arbitrarily in step (3), there exists an alternative optimal solution. But if no optimal solution is found, then go to step (5). Step 5: Revise the Opportunity Cost Table Draw a set of horizontal and vertical lines to cover all the zeros in the revised cost table obtained from step (3), by using the following procedure: (a) For each row in which no assignment was made, mark a tick (√) (b) Examine the marked rows. If any zero occurs in those columns, tick the respective rows that contain those assigned zeros. (c) Repeat this process until no more rows or columns can be marked. If a no of lines drawn is equal to the no of (or columns) the current solution is the optimal solution, otherwise go to step 6. Step 6: Develop the New Revised Opportunity Cost Table (a) From among the cells not covered by any line, choose the smallest element, call this value K (b) Subtract K from every element in the cell not covered by line. (c) Add K to very element in the cell covered by the two lines, i.e., intersection of two lines. (d) Elements in cells covered by one line remain unchanged. Step 7: Repeat Step 3 to 6 Unlit an Optimal Solution is Obtained
An assignment problem can be easily solved by applying Hungarian method which consists of two phases. In the first phase, row reductions and column reductions are carried out. In the second phase, the solution is optimized on iterative basis. Phase 1 Step 0: Consider the given matrix. Phase 2: Step 3: Reduce the new matrix column-wise using the same method as given in step 2. Note: While assigning, if there is no single zero exists in the row or column, choose any one zero and assign it. Strike off the remaining zeros in that column or row, and repeat the same for other assignments also. If there is no single zero allocation, it means multiple numbers of solutions exist. But the cost will remain the same for different sets of allocations. Example : Assign the four tasks to four operators. The assigning costs are given in Table. Assignment Problem  Solution: Step 1: The given matrix is a square matrix and it is not necessary to add a dummy row/column Row-wise Reduction Step 3: Reduce the new matrix given in the following table by selecting the smallest value in Column-wise Reduction Matrix Step 4: Draw minimum number of lines possible to cover all the zeros in the matrix given in Table Matrix with all Zeros Covered The first line is drawn crossing row C covering three zeros, second line is drawn crossing column 4 covering two zeros and third line is drawn crossing column 1 (or row B) covering a single zero. Subtracted or Added to Uncovered Values and Intersection Lines Respectively Step 7: Now, draw minimum number of lines to cover all the zeros and check for optimality. Here in table minimum number of lines drawn is 4 which are equal to the order of matrix. Hence optimality is reached. Optimality Matrix Step 8: Assign the tasks to the operators. Select a row that has a single zero and assign by squaring it. Strike off remaining zeros if any in that row or column. Repeat the assignment for other tasks. The final assignment is shown in table below. Final Assignment Therefore, optimal assignment is: Example : Solve the following assignment problem shown in Table using Hungarian method. The matrix entries are processing time of each man in hours. Assignment Problem Solution: The row-wise reductions are shown in Table Row-wise Reduction Matrix The column wise reductions are shown in Table. Column-wise Reduction Matrix Matrix with minimum number of lines drawn to cover all zeros is shown in Table. Matrix will all Zeros Covered The number of lines drawn is 5, which is equal to the order of matrix. Hence optimality is reached. The optimal assignments are shown in Table. Optimal Assignment Therefore, the optimal solution is: |
In Hungarian method of solving assignment problem the opportunity cost matrix is obtained by
Pos Terkait
Copyright © 2024 ketajaman Inc.
