Muzammil irshad.pptxhdududududiufufufufu

Hehdhdhdhdhdhdhhdh

1. Submitted by: MUZAMMIL IRSHAD Enrollment no.: 72215601723 Branch/Sem: BBA 2 nd Sem Section: B ASSIGNMENT PROBLEM

2. What is Assignment problem? It involves assignment of people to pro jobs to machines, workers to jobs and teachers to classes etc., while minimizing the total assignment costs. One of the important characteristics of assignment problem is that only one job (or worker) is assigned to one machine (or project). An assignment problem is a special type of linear programming problem where the objective is to minimize the cost or time of completing a number of jobs by a number of persons. This method was developed by D. Kon Hungarian mathematician and is there known as the Hungarian method of assignment problem. In order to use this method, one needs to know only the cost of making all the possible assignments. Each assignment problem has a matrix (table) associated with it. Normally, the objects (or people) one wishes to assign are expressed in rows, whereas the columns represent the tasks (or things) assigned to them. The number in the table would then be the costs associated with each particular assignment.

3. Hungarian Method Top Banner The Hungarian method is a computational optimization technique that addresses the assignment problem in polynomial time and foreshadows following primal-dual alternatives. In 1955, Harold Kuhn used the term “Hungarian method” to honour two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry . Let’s go through the steps of the Hungarian method with the help of a solved example.. Hungarian Method to Solve Assignment Problems The Hungarian method is a simple way to solve assignment problems. Let us first discuss the assignment problems before moving on to learning the Hungarian method

4. Hungarian Method Steps Check to see if the number of rows and columns are equal; if they are, the assignment problem is considered to be balanced. Then go to step 1. If it is not balanced, it should be balanced before the algorithm is applied. Step 1 – In the given cost matrix, subtract the least cost element of each row from all the entries in that row. Make sure that each row has at least one zero. Step 2 – In the resultant cost matrix produced in step 1, subtract the least cost element in each column from all the components in that column, ensuring that each column contains at least one zero. Step 3 – Assign zeros Analyse the rows one by one until you find a row with precisely one unmarked zero. Encircle this lonely unmarked zero and assign it a task. All other zeros in the column of this circular zero should be crossed out because they will not be used in any future assignments. Continue in this manner until you’ve gone through all of the rows.Examine the columns one by one until you find one with precisely one unmarked zero. Encircle this single unmarked zero and cross any other zero in its row to make an assignment to it. Continue until you’ve gone through all of the columns. Step 4 – Perform the Optimal TestThe present assignment is optimal if each row and column has exactly one encircled zero.The present assignment is not optimal if at least one row or column is missing an assignment (i.e., if at least one row or column is missing one encircled zero). Continue to step 5. Subtract the least cost element from all the entries in each column of the final cost matrix created in step 1 and ensure that each column has at least one zero. Step 5 – Draw the least number of straight lines to cover all of the zeros as follows:(a) Highlight the rows that aren’t assigned.(b) Label the columns with zeros in marked rows (if they haven’t already been marked).(c) Highlight the rows that have assignments in indicated columns (if they haven’t previously been marked). (d) Continue with (b) and (c) until no further marking is needed.(f) Simply draw the lines through all rows and columns that are not marked. If the number of these lines equals the order of the matrix, then the solution is optimal; otherwise, it is not.. Step 6 – Find the lowest cost factor that is not covered by the straight lines. Subtract this least-cost component from all the uncovered elements and add it to all the elements that are at the intersection of these straight lines, but leave the rest of the elements alone. Step 7 – Continue with steps 1 – 6 until you’ve found the highest suitable assignment

5. Type of assignment problem Balanced Assignment Problem: Balanced Assignment Problem is an assignment problem where the number of facilities is equal to the number of jobs. Unbalanced Assignment Problem : Unbalanced Assignment problem is an assignment problem where the number of facilities is not equal to the number of jobs. To make unbalanced assignment problem, a balanced one, a dummy facility(s) or a dummy job(s) (as the case may be) is introduced with zero cost or time. Dummy Job/Facility: A dummy job or facility is an imaginary job/facility with zero cost or time introduced to make an unbalanced assignment problem balanced. Infeasible Assignment: An Infeasible Assignment occurs in the cell ( i , j) of the assignment cost matrix if ith person is unable to perform jth job. It is sometimes possible that a particular person is incapable of doing certain work or a specific job cannot be performed on a particular machine. The solution of the assignment problem should take into account these restrictions so that the infeasible assignments can be avoided. This can be achieved by assigning a very high cost to the cells where assignments are prohibited.

6. Unbalanced Assignment Problems Whenever the cost matrix of an assignment problem is not a square matrix, that is, whenever the number of sources is not equal to the number of destinations, the assignment problem is called an unbalanced assignment problem. In such problems, dummy rows (or columns) are added in the matrix so as to complete it to form a square matrix. The dummy rows or columns will contain all costs elements as zeroes. The Hungarian method may be used to solve the problem.

7. Restriction in Assignment It is sometimes possible that a particular person is incapable of doing certain work or a specific job cannot be performed on a particular machine. The solution of the assignment problem should take into account these restrictions so that the restricted (infeasible) assignment can be avoided. This can be achieved by assigning a very high cost (say ∞ or M)to the cells where assignments are prohibited, thereby restricting the entry of this pair of job-machine or resource-activity into the final solution.

8. Travelling salesman model Given a set of cities and distances between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.  Note the difference between  Hamiltonian Cycle  and TSP. The Hamiltonian cycle problem is to find if there exists a tour that visits every city exactly once. Here we know that Hamiltonian Tour exists (because the graph is complete) and in fact, many such tours exist, the problem is to find a minimum weight Hamiltonian Cycle.