Maximization Assignment Problem

Maximization Assignment Problem

In assignment problems, you need to assign resources to tasks in such a way as to maximize or minimize an objective, like total profit or cost. For maximization problems, the Hungarian method can be adapted by converting the problem into a minimization problem. Here’s a step-by-step breakdown of how to handle a maximization assignment problem using this approach:

Steps to Convert and Solve a Maximization Assignment Problem:

1. Convert to Minimization Problem:

To apply the Hungarian method, you first need to transform a maximization problem into a minimization problem. Here’s how:

• Identify the Maximum Value: Find the highest value in the matrix. This value represents the highest possible performance or cost.
• Subtract from the Maximum Value: Subtract each value in the matrix from this maximum value. This converts the problem into a minimization problem where the objective is to minimize the "cost" of assignments, which corresponds to maximizing the original performance measure.

Example Conversion: 

Suppose the sales data matrix is:

$$\begin{array}{cccc}10& 20& 30& 40\\ 15& 25& 35& 45\\ 20& 30& 40& 50\\ 25& 35& 45& 55\end{array}$$

The maximum value is 55. The converted minimization matrix will be:

$$\begin{array}{cccc}\mathrm{<span\; style="font-size:\; large;">45</span>}& \mathrm{<span\; style="font-size:\; large;">35</span>}& \mathrm{<span\; style="font-size:\; large;">25</span>}& \mathrm{<span\; style="font-size:\; large;">15</span>}\\ \mathrm{<span\; style="font-size:\; large;">40</span>}& \mathrm{<span\; style="font-size:\; large;">30</span>}& \mathrm{<span\; style="font-size:\; large;">20</span>}& \mathrm{<span\; style="font-size:\; large;">10</span>}\\ \mathrm{<span\; style="font-size:\; large;">35</span>}& \mathrm{<span\; style="font-size:\; large;">25</span>}& \mathrm{<span\; style="font-size:\; large;">15</span>}& \mathrm{<span\; style="font-size:\; large;">5</span>}\\ \mathrm{<span\; style="font-size:\; large;">30</span>}& \mathrm{<span\; style="font-size:\; large;">20</span>}& \mathrm{<span\; style="font-size:\; large;">10</span>}& \mathrm{<span\; style="font-size:\; large;">0</span>}\end{array}$$​

2. Row Reduction:

• Subtract Row Minimums: For each row, subtract the smallest value in that row from every element in that row. This step simplifies the matrix and ensures that at least one zero is present in each row.

Example Row Reduction: 

Applying row reduction to the converted matrix:

$$\begin{array}{cccc}30& 20& 10& 0\\ 30& 20& 10& 0\\ 30& 20& 10& 0\\ 30& 20& 10& 0\end{array}$$

3. Column Reduction:

• Subtract Column Minimums: After row reduction, perform column reduction by subtracting the smallest value in each column from every element in that column. This ensures that at least one zero is present in each column.

Example Column Reduction: 

Applying column reduction to the matrix obtained after row reduction:

$$\begin{array}{cccc}\mathrm{<span\; style="font-size:\; large;">0</span>}& \mathrm{<span\; style="font-size:\; large;">0</span>}& \mathrm{<span\; style="font-size:\; large;">0</span>}& \mathrm{<span\; style="font-size:\; large;">0</span>}\\ \mathrm{<span\; style="font-size:\; large;">0</span>}& \mathrm{<span\; style="font-size:\; large;">0</span>}& \mathrm{<span\; style="font-size:\; large;">0</span>}& \mathrm{<span\; style="font-size:\; large;">0</span>}\\ \mathrm{<span\; style="font-size:\; large;">0</span>}& \mathrm{<span\; style="font-size:\; large;">0</span>}& \mathrm{<span\; style="font-size:\; large;">0</span>}& \mathrm{<span\; style="font-size:\; large;">0</span>}\\ \mathrm{<span\; style="font-size:\; large;">0</span>}& \mathrm{<span\; style="font-size:\; large;">0</span>}& \mathrm{<span\; style="font-size:\; large;">0</span>}& \mathrm{<span\; style="font-size:\; large;">0</span>}\end{array}$$

4. Cover Zeros with Minimum Lines:

• Draw Lines to Cover All Zeros: Use the minimum number of horizontal and vertical lines to cover all zeros in the matrix. If the number of lines is equal to the order of the matrix (number of rows or columns), then an optimal assignment is possible with the current matrix.

Example Line Covering: 

Draw lines to cover all zeros in the matrix. If the number of lines is less than the order of the matrix, you need to adjust the matrix.

5. Adjust the Matrix:

• Find the Smallest Uncovered Element: Identify the smallest element that is not covered by any line.
• Update Matrix Values: Subtract this smallest value from all uncovered elements, and add it to the elements covered by two lines (intersection points). Elements covered by only one line remain unchanged.

Example Adjustment: 

Update the matrix using the smallest uncovered value and adjust accordingly to ensure optimal coverage.

6. Determine the Optimal Solution:

• Repeat the Process: Continue adjusting and covering zeros until the number of lines equals the order of the matrix. At this point, the solution is optimal.

Example Solution: 

After adjustments, you will have an optimal assignment that maximizes the original performance measure.

Summary:

1. Convert the maximization matrix to a minimization matrix by subtracting each value from the maximum value in the matrix.
2. Reduce the matrix row-wise and column-wise to ensure zeros in each row and column.
3. Cover all zeros with the minimum number of lines.
4. Adjust the matrix if necessary by updating uncovered elements until the number of lines equals the matrix order.
5. Find the optimal assignment from the final adjusted matrix.

By following these steps, you transform a maximization problem into a form suitable for the Hungarian method, allowing for an efficient solution to the assignment problem.