![operational research problems operational research problems](https://studychacha.com/img/l/Applied-operations-research-semester-question-papers-1.jpg)
The flow chart of steps in the Hungarian method for solving an assignment problem is shown in following figures:ġ. Step 7: Repeat Step 3 to 6 Unlit an Optimal Solution is Obtained: (d) Elements in cells covered by one line remain unchanged. (c) Add K to very element in the cell covered by the two lines, i.e., intersection of two lines. (b) Subtract K from every element in the cell not covered by line. (a) From among the cells not covered by any line, choose the smallest element, call this value K Step 6: Develop the New Revised Opportunity Cost Table: 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. (d) Draw a straight line through each marked column and each unmarked row. (c) Repeat this process until no more rows or columns can be marked. If any zero occurs in those columns, tick the respective rows that contain those assigned zeros. (a) For each row in which no assignment was made, mark a tick (√) Step 5: Revise the Opportunity Cost Table:ĭraw 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: But if no optimal solution is found, then go to step (5). If a zero cell was chosen arbitrarily in step (3), there exists an alternative optimal solution. The total cost associated with this solution is obtained by adding original cost figures in the occupied cells. If the member of assigned cells is equal to the numbers of rows column then it is optimal solution. (e) Continue this process until all zeros in row column are either enclosed (Assigned) or struck off (x) (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. (c) Repeat step 3 (a) and 3 (b) for each column also with exactly single zero value all that has not been assigned. Step 1: Develop the Cost Table from the given Problem: The Hungarian method can be summarized in the following steps:
![operational research problems operational research problems](https://static.docsity.com/media/avatar/documents/2010/03/29/e142e558157ce42515f4f2fa364e68a1.jpeg)
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. Opportunity cost show the relative penalties associated with assigning resources to an activity as opposed to making the best or least cost assignment. It works on the principle of reducing the given cost matrix to a matrix of opportunity costs. 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. Hungarian Method for Solving Assignment Problem: Mathematical Formulation of the Assignment Problem:
![operational research problems operational research problems](https://management.ind.in/img/h/Applied-Operations-Research-PTU-Question-Papers-1.jpg)
The assignment problem can be stated in the form of n x n cost matrix C real members as given in the following table: The problem is to find an assignment (which job should be assigned to which person one on-one basis) So that the total cost of performing all jobs is minimum, problem of this kind are known as assignment problem. Assume that each person can do each job at a term, though with varying degree of efficiency, let c ij be the cost if the i-th person is assigned to the j-th job. Suppose there are n jobs to be performed and n persons are available for doing these jobs. Some of the problem where the assignment technique may be useful are assignment of workers to machines, salesman to different sales areas. Thus, the problem is “How should the assignments be made so as to optimize the given objective”.