Scribd
Upload
6 views1 page

Understanding the Assignment Problem in Linear Programming

The document discusses the Assignment Problem, a type of linear programming that optimally allocates resources like people to tasks while minimizing costs or time. It describes the structure of assignment problems using a cost table and outlines the Hungarian Method as the most common algorithm for solving these problems, which involves creating an opportunity cost table and revising it to find an optimal assignment. For maximization problems, it suggests transforming them into minimization problems to achieve the same assignment outcomes.

Uploaded by

Yvan Mav
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views1 page

Understanding the Assignment Problem in Linear Programming

The document discusses the Assignment Problem, a type of linear programming that optimally allocates resources like people to tasks while minimizing costs or time. It describes the structure of assignment problems using a cost table and outlines the Hungarian Method as the most common algorithm for solving these problems, which involves creating an opportunity cost table and revising it to find an optimal assignment. For maximization problems, it suggests transforming them into minimization problems to achieve the same assignment outcomes.

Uploaded by

Yvan Mav
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

The following materials are helpful in your study of this special linear programming problem

called THE ASSIGNMENT PROBLEM. Work with your groupmates to come up with a summary
of important concepts taught in these materials.
 Chapter 5, Section 5.2 (Textbook, pp. 299-304)

Assignment problems are linear programming problems that involve allocating resources
optimally. It focuses on finding the best allocation of resources, such as people to tasks, jobs to
machines, or vehicles to routes. It typically aims to minimize costs or time in assigning tasks to
individuals or resources.
An assignment problem represents a table where rows represent the assignees and columns
represent the tasks. The number of assignees and tasks are equal. Meanwhile, the numbers inside
the cells indicate the costs associated with each assignment.
Several algorithms exist to solve assignment problems, such as the enumeration method,
simplex method, transportation method, and Hungarian method. Among these, the Hungarian
Method is the most commonly used. It relies on matrix reduction and opportunity costs.
To do the Hungarian Method, first, create an opportunity cost table by subtracting the
smallest number in each row and column from the original cost table. Next, test the resulting table
to determine if an optimal assignment is possible. An optimal assignment is possible if the number
of lines equals the number of rows or columns. If it is not equal, the table will undergo revision by
subtracting the smallest uncovered number and then adding it at the intersection of the horizontal
and vertical lines. The process will continue until an optimal solution is found.
For maximization assignment problems, the approach is to transform the problem into an
equivalent minimization problem by subtracting every entry from the largest number in the table.
The minimized opportunity costs yield the same assignment as the original maximization problem.
Calculate the total payoff by summing the original payoffs of the assigned cells.

You might also like