Assignment Problems

Assignment problems in linear programming involve assigning a number of tasks or jobs to a number of individuals, machines, or resources in the most optimal way possible. These problems are usually solved using the Hungarian algorithm, which is a popular algorithm for solving assignment problems. The goal is to minimize the total cost or time required to complete all the tasks. The video lecture above would further explain and apply these concepts in solving problem of assignments problems. 

There are two types of problems in the assignment problems - Minimization and Maximization. The following steps of each are as follows:

Steps of the Hungarian method for solving a minimization problem:

1. Create a matrix representing the cost of assigning each job to each worker.

2. Subtract the smallest value in each row from all the values in that row.

3. Subtract the smallest value in each column from all the values in that column.

4. Draw the minimum number of horizontal and vertical lines to cover all the zeros in the matrix. 

5. If the number of lines equals the number of rows (or columns), an optimal solution has been found. If not, proceed to step 6.

6. Determine the smallest uncovered value in the matrix.

7. Subtract that value from all uncovered values, and add it to all values at the intersection of two lines.

8. Repeat steps 4-7 until an optimal solution is found.

Steps of the Hungarian method for solving a maximization problem:

1. Subtract the smallest number in each row from all the numbers in that row.

2. Subtract the smallest number in each column from all the numbers in that column.

3. Draw the minimum number of horizontal and vertical lines to cover all the zeros in the matrix.

4. If the number of lines drawn equals the number of rows, then an optimal solution has been found. If not, continue to step 5.

5. Determine the smallest uncovered number in the matrix and subtract it from every uncovered number. Then add it to every number that is covered by two lines. Go back to step 3.

6. Create a matrix representing the cost of assigning each job to each worker.

7. Subtract the smallest value in each row from all the values in that row.

8. Subtract the smallest value in each column from all the values in that column.

9. Draw the minimum number of horizontal and vertical lines to cover all the zeros in the matrix. 

10. If the number of lines equals the number of rows (or columns), an optimal solution has been found. If not, proceed to step 6.

11. Determine the smallest uncovered value in the matrix.

12. Subtract that value from all uncovered values, and add it to all values at the intersection of two lines.

13. Repeat steps 4-7 until an optimal solution is found.