assignment problem maximization

Assignment Problem: Maximization

There are problems where certain facilities have to be assigned to a number of jobs, so as to maximize the overall performance of the assignment.

The Hungarian Method can also solve such assignment problems , as it is easy to obtain an equivalent minimization problem by converting every number in the matrix to an opportunity loss.

The conversion is accomplished by subtracting all the elements of the given matrix from the highest element. It turns out that minimizing opportunity loss produces the same assignment solution as the original maximization problem.

• Unbalanced Assignment Problem
• Multiple Optimal Solutions

Example: Maximization In An Assignment Problem

At the head office of www.universalteacherpublications.com there are five registration counters. Five persons are available for service.

How should the counters be assigned to persons so as to maximize the profit ?

Here, the highest value is 62. So we subtract each value from 62. The conversion is shown in the following table.

On small screens, scroll horizontally to view full calculation

Now the above problem can be easily solved by Hungarian method . After applying steps 1 to 3 of the Hungarian method, we get the following matrix.

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

Select the smallest element from all the uncovered elements, i.e., 4. Subtract this element from all the uncovered elements and add it to the elements, which lie at the intersection of two lines. Thus, we obtain another reduced matrix for fresh assignment. Repeating step 3, we obtain a solution which is shown in the following table.

Final Table: Maximization Problem

Use Horizontal Scrollbar to View Full Table Calculation

The total cost of assignment = 1C + 2E + 3A + 4D + 5B

Substituting values from original table: 40 + 36 + 40 + 36 + 62 = 214.

Share This Article

Operations Research Simplified Back Next

Goal programming Linear programming Simplex Method Transportation Problem

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures

Hungarian Algorithm for Assignment Problem | Set 1 (Introduction)

• Hungarian Algorithm for Assignment Problem | Set 2 (Implementation)
• Introduction to Exact Cover Problem and Algorithm X
• Greedy Approximate Algorithm for Set Cover Problem
• Job Assignment Problem using Branch And Bound
• Implementation of Exhaustive Search Algorithm for Set Packing
• Channel Assignment Problem
• Chocolate Distribution Problem | Set 2
• Transportation Problem | Set 1 (Introduction)
• OLA Interview Experience | Set 11 ( For Internship)
• Top 20 Greedy Algorithms Interview Questions
• Job Sequencing Problem - Loss Minimization
• Prim's Algorithm (Simple Implementation for Adjacency Matrix Representation)
• Data Structures and Algorithms | Set 21
• Adobe Interview Experience | Set 55 (On-Campus Full Time for MTS profile)
• Amazon Interview Experience | Set 211 (On-Campus for Internship)
• OYO Rooms Interview Experience | Set 3 (For SDE-II, Gurgaon)
• C# Program for Dijkstra's shortest path algorithm | Greedy Algo-7
• Algorithms | Dynamic Programming | Question 7
• Amazon Interview | Set 46 (On-campus for Internship)

• For each row of the matrix, find the smallest element and subtract it from every element in its row.
• Do the same (as step 1) for all columns.
• Cover all zeros in the matrix using minimum number of horizontal and vertical lines.
• Test for Optimality: If the minimum number of covering lines is n, an optimal assignment is possible and we are finished. Else if lines are lesser than n, we haven’t found the optimal assignment, and must proceed to step 5.
• Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column. Return to step 3.

Try it before moving to see the solution

Explanation for above simple example:

  An example that doesn’t lead to optimal value in first attempt: In the above example, the first check for optimality did give us solution. What if we the number covering lines is less than n.

Time complexity : O(n^3), where n is the number of workers and jobs. This is because the algorithm implements the Hungarian algorithm, which is known to have a time complexity of O(n^3).

Space complexity :   O(n^2), where n is the number of workers and jobs. This is because the algorithm uses a 2D cost matrix of size n x n to store the costs of assigning each worker to a job, and additional arrays of size n to store the labels, matches, and auxiliary information needed for the algorithm.

In the next post, we will be discussing implementation of the above algorithm. The implementation requires more steps as we need to find minimum number of lines to cover all 0’s using a program. References: http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf https://www.youtube.com/watch?v=dQDZNHwuuOY

Please Login to comment...

Similar reads.

• Mathematical

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Hungarian Method

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.

What is an Assignment Problem?

A transportation problem is a type of assignment problem. The goal is to allocate an equal amount of resources to the same number of activities. As a result, the overall cost of allocation is minimised or the total profit is maximised.

Because available resources such as workers, machines, and other resources have varying degrees of efficiency for executing different activities, and hence the cost, profit, or loss of conducting such activities varies.

Assume we have ‘n’ jobs to do on ‘m’ machines (i.e., one job to one machine). Our goal is to assign jobs to machines for the least amount of money possible (or maximum profit). Based on the notion that each machine can accomplish each task, but at variable levels of efficiency.

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 Test

• The 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.

Hungarian Method Example

Use the Hungarian method to solve the given assignment problem stated in the table. The entries in the matrix represent each man’s processing time in hours.

\(\begin{array}{l}\begin{bmatrix} & I & II & III & IV & V \\1 & 20 & 15 & 18 & 20 & 25 \\2 & 18 & 20 & 12 & 14 & 15 \\3 & 21 & 23 & 25 & 27 & 25 \\4 & 17 & 18 & 21 & 23 & 20 \\5 & 18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} \)

With 5 jobs and 5 men, the stated problem is balanced.

\(\begin{array}{l}A = \begin{bmatrix}20 & 15 & 18 & 20 & 25 \\18 & 20 & 12 & 14 & 15 \\21 & 23 & 25 & 27 & 25 \\17 & 18 & 21 & 23 & 20 \\18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} \)

Subtract the lowest cost element in each row from all of the elements in the given cost matrix’s row. Make sure that each row has at least one zero.

\(\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 5 & 10 \\6 & 8 & 0 & 2 & 3 \\0 & 2 & 4 & 6 & 4 \\0 & 1 & 4 & 6 & 3 \\2 & 2 & 0 & 3 & 4 \\\end{bmatrix}\end{array} \)

Subtract the least cost element in each Column from all of the components in the given cost matrix’s Column. Check to see if each column has at least one zero.

\(\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 3 & 7 \\6 & 8 & 0 & 0 & 0 \\0 & 2 & 4 & 4 & 1 \\0 & 1 & 4 & 4 & 0 \\2 & 2 & 0 & 1 & 1 \\\end{bmatrix}\end{array} \)

When the zeros are assigned, we get the following:

The present assignment is optimal because each row and column contain precisely one encircled zero.

Where 1 to II, 2 to IV, 3 to I, 4 to V, and 5 to III are the best assignments.

Hence, z = 15 + 14 + 21 + 20 + 16 = 86 hours is the optimal time.

Practice Question on Hungarian Method

Use the Hungarian method to solve the following assignment problem shown in table. The matrix entries represent the time it takes for each job to be processed by each machine in hours.

\(\begin{array}{l}\begin{bmatrix}J/M & I & II & III & IV & V \\1 & 9 & 22 & 58 & 11 & 19 \\2 & 43 & 78 & 72 & 50 & 63 \\3 & 41 & 28 & 91 & 37 & 45 \\4 & 74 & 42 & 27 & 49 & 39 \\5 & 36 & 11 & 57 & 22 & 25 \\\end{bmatrix}\end{array} \)

Stay tuned to BYJU’S – The Learning App and download the app to explore all Maths-related topics.

Frequently Asked Questions on Hungarian Method

What is hungarian method.

The Hungarian method is defined as a combinatorial optimization technique that solves the assignment problems in polynomial time and foreshadowed subsequent primal–dual approaches.

What are the steps involved in Hungarian method?

The following is a quick overview of the Hungarian method: Step 1: Subtract the row minima. Step 2: Subtract the column minimums. Step 3: Use a limited number of lines to cover all zeros. Step 4: Add some more zeros to the equation.

What is the purpose of the Hungarian method?

When workers are assigned to certain activities based on cost, the Hungarian method is beneficial for identifying minimum costs.

Leave a Comment Cancel reply

Your Mobile number and Email id will not be published. Required fields are marked *

Request OTP on Voice Call

Post My Comment

• Share Share

Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

Maximisation in an Assignment Problem: Optimizing Assignments for Maximum Benefit

Table of Contents

This blog will explain how to solve assignment problems using optimization techniques to achieve maximum results. Learn the basics, step-by-step approach, and real-world applications of maximizing assignment problems.

In an assignment problem, the goal is to assign n tasks to n agents in such a way that the overall cost or benefit is minimized or maximized. The maximization problem arises when the objective is to maximize the overall benefit rather than minimize the cost.

Understanding Maximisation in an Assignment Problem

The maximization problem can be solved using the Hungarian algorithm, which is a special case of the transportation problem. The algorithm involves converting the assignment problem into a matrix, finding the minimum value in each row, and subtracting it from all the elements in that row. Similarly, we find the minimum value in each column and subtract it from all the elements in that column. This is known as matrix reduction.

Next, we cover all zeros in the matrix using the minimum number of lines. A line covers a row or column that contains a zero. If the minimum number of lines is n, an optimal solution has been found. Otherwise, we continue with the next step.

In step three, we add the minimum uncovered value to each element covered by two lines, and subtract it from each uncovered element. Then, we return to step two and repeat until an optimal solution is found.

Solving Maximisation in an Assignment Problem

The above approach provides a step-by-step process to maximize an assignment problem. Here are the steps in summary:

• Convert the assignment problem into a matrix.
• Reduce the matrix by subtracting the minimum value in each row and column.
• Cover all zeros in the matrix with the minimum number of lines.
• Add the minimum uncovered value to each element covered by two lines and subtract it from each uncovered element.
• Repeat from step two until an optimal solution is found.

Real-World Applications

Maximization in an Assignment Problem has numerous real-world applications. For example, it can be used to optimize employee allocation to projects, to allocate tasks in a manufacturing process, or to assign jobs to machines for maximum productivity. By using optimization techniques to maximize the benefits of an assignment problem, businesses can save time, money, and resources.

This blog has provided an overview of Maximisation in an Assignment Problem, explained how to solve it using the Hungarian algorithm, and discussed real-world applications. By following the step-by-step approach, you can optimize your assignments for maximum benefit.

How useful was this post?

Click on a star to rate it!

Average rating 5 / 5. Vote count: 2

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you! 😔

Let us improve this post!

Tell us how we can improve this post?

Operations Research

1 Operations Research-An Overview

• History of O.R.
• Approach, Techniques and Tools
• Phases and Processes of O.R. Study
• Typical Applications of O.R
• Limitations of Operations Research
• Models in Operations Research
• O.R. in real world

2 Linear Programming: Formulation and Graphical Method

• General formulation of Linear Programming Problem
• Optimisation Models
• Basics of Graphic Method
• Important steps to draw graph
• Multiple, Unbounded Solution and Infeasible Problems
• Solving Linear Programming Graphically Using Computer
• Application of Linear Programming in Business and Industry

3 Linear Programming-Simplex Method

• Principle of Simplex Method
• Computational aspect of Simplex Method
• Simplex Method with several Decision Variables
• Two Phase and M-method
• Multiple Solution, Unbounded Solution and Infeasible Problem
• Sensitivity Analysis
• Dual Linear Programming Problem

4 Transportation Problem

• Basic Feasible Solution of a Transportation Problem
• Modified Distribution Method
• Stepping Stone Method
• Unbalanced Transportation Problem
• Degenerate Transportation Problem
• Transhipment Problem
• Maximisation in a Transportation Problem

5 Assignment Problem

• Solution of the Assignment Problem
• Unbalanced Assignment Problem
• Problem with some Infeasible Assignments
• Maximisation in an Assignment Problem
• Crew Assignment Problem

6 Application of Excel Solver to Solve LPP

• Building Excel model for solving LP: An Illustrative Example

7 Goal Programming

• Concepts of goal programming
• Goal programming model formulation
• Graphical method of goal programming
• The simplex method of goal programming
• Using Excel Solver to Solve Goal Programming Models
• Application areas of goal programming

8 Integer Programming

• Some Integer Programming Formulation Techniques
• Binary Representation of General Integer Variables
• Unimodularity
• Cutting Plane Method
• Branch and Bound Method
• Solver Solution

9 Dynamic Programming

• Dynamic Programming Methodology: An Example
• Definitions and Notations
• Dynamic Programming Applications

10 Non-Linear Programming

• Solution of a Non-linear Programming Problem
• Convex and Concave Functions
• Kuhn-Tucker Conditions for Constrained Optimisation
• Quadratic Programming
• Separable Programming
• NLP Models with Solver

11 Introduction to game theory and its Applications

• Important terms in Game Theory
• Saddle points
• Mixed strategies: Games without saddle points
• 2 x n games
• Exploiting an opponent’s mistakes

12 Monte Carlo Simulation

• Reasons for using simulation
• Monte Carlo simulation
• Limitations of simulation
• Steps in the simulation process
• Some practical applications of simulation
• Two typical examples of hand-computed simulation
• Computer simulation

13 Queueing Models

• Characteristics of a queueing model
• Notations and Symbols
• Statistical methods in queueing
• The M/M/I System
• The M/M/C System
• The M/Ek/I System
• Decision problems in queueing

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons
• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

3.1: Maximization Applications

• Last updated
• Save as PDF
• Page ID 37861

• Rupinder Sekhon and Roberta Bloom
• De Anza College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

Learning Objectives

In this section, you will learn to:

• Recognize the typical form of a linear programing problem
• Formulate maximization linear programming problems
• Graph feasibility regions for maximization linear programming problems
• Determine optimal solutions for maximization linear programming problems.

Application problems in business, economics, and social and life sciences often ask us to make decisions on the basis of certain conditions. The conditions or constraints often take the form of inequalities. In this section, we will begin to formulate, analyze, and solve such problems, at a simple level, to understand the many components of such a problem.

A typical linear programming problem consists of finding an extreme value of a linear function subject to certain constraints. We are either trying to maximize or minimize the value of this linear function, such as to maximize profit or revenue, or to minimize cost. That is why these linear programming problems are classified as maximization or minimization problems , or just optimization problems . The function we are trying to optimize is called an objective function , and the conditions that must be satisfied are called constraints .

A typical example is to maximize profit from producing several products, subject to limitations on materials or resources needed for producing these items; the problem requires us to determine the amount of each item produced. Another type of problem involves scheduling; we need to determine how much time to devote to each of several activities in order to maximize income from (or minimize cost of) these activities, subject to limitations on time and other resources available for each activity.

In this chapter, we will work with problems that involve only two variables, and therefore, can be solved by graphing. In the next chapter, we’ll learn an algorithm to find a solution numerically. That will provide us with a tool to solve problems with more than two variables. At that time, with a little more knowledge about linear programming, we’ll also explore the many ways these techniques are used in business and wide variety of other fields.

We begin by solving a maximization problem.

Example \(\PageIndex{1}\)

Niki holds two part-time jobs, Job I and Job II. She never wants to work more than a total of 12 hours a week. She has determined that for every hour she works at Job I, she needs 2 hours of preparation time, and for every hour she works at Job II, she needs one hour of preparation time, and she cannot spend more than 16 hours for preparation.

If Nikki makes $40 an hour at Job I, and $30 an hour at Job II, how many hours should she work per week at each job to maximize her income?

We start by choosing our variables.

• Let \(x\) = The number of hours per week Niki will work at Job I.
• Let \(y\) = The number of hours per week Niki will work at Job II.

Now we write the objective function. Since Niki gets paid $40 an hour at Job I, and $30 an hour at Job II, her total income I is given by the following equation.

\[I = 40x + 30y \nonumber \]

Our next task is to find the constraints. The second sentence in the problem states, "She never wants to work more than a total of 12 hours a week." This translates into the following constraint:

\[x + y \leq 12 \nonumber \]

The third sentence states, "For every hour she works at Job I, she needs 2 hours of preparation time, and for every hour she works at Job II, she needs one hour of preparation time, and she cannot spend more than 16 hours for preparation." The translation follows.

\[2x + y \leq 16 \nonumber \]

The fact that \(x\) and \(y\) can never be negative is represented by the following two constraints:

\[x \geq 0 \text{, and } y \geq 0 \nonumber. \nonumber \]

Well, good news! We have formulated the problem. We restate it as

\begin{array}{ll} \textbf { Maximize } & \mathrm{I}=40 \mathrm{x}+30 \mathrm{y} \\ \textbf { Subject to: } & \mathrm{x}+\mathrm{y} \leq 12 \\ & 2 \mathrm{x}+\mathrm{y} \leq 16 \\ & \mathrm{x} \geq 0 ; \mathrm{y} \geq 0 \end{array}

In order to solve the problem, we graph the constraints and shade the region that satisfies all the inequality constraints.

Any appropriate method can be used to graph the lines for the constraints. However often the easiest method is to graph the line by plotting the x-intercept and y-intercept.

The line for a constraint will divide the plane into two region, one of which satisfies the inequality part of the constraint. A test point is used to determine which portion of the plane to shade to satisfy the inequality. Any point on the plane that is not on the line can be used as a test point.

• If the test point satisfies the inequality, then the region of the plane that satisfies the inequality is the region that contains the test point.
• If the test point does not satisfy the inequality, then the region that satisfies the inequality lies on the opposite side of the line from the test point.

In the graph below, after the lines representing the constraints were graphed using an appropriate method from Chapter 1, the point (0,0) was used as a test point to determine that

• (0,0) satisfies the constraint \(x + y \leq 12\) because \(0 + 0 < 12\)
• (0,0) satisfies the constraint \(2x + y \leq 16\) because \(2(0) + 0 < 16\)

Therefore, in this example, we shade the region that is below and to the left of both constraint lines, but also above the x axis and to the right of the y axis, in order to further satisfy the constraints \(x \geq 0\) and \(y \geq 0\).

The shaded region where all conditions are satisfied is called the feasibility region or the feasibility polygon.

The Fundamental Theorem of Linear Programming states that the maximum (or minimum) value of the objective function always takes place at the vertices of the feasibility region.

Therefore, we will identify all the vertices (corner points) of the feasibility region. We call these points critical points. They are listed as (0, 0), (0, 12), (4, 8), (8, 0). To maximize Niki's income, we will substitute these points in the objective function to see which point gives us the highest income per week. We list the results below.

Clearly, the point (4, 8) gives the most profit: $400.

Therefore, we conclude that Niki should work 4 hours at Job I, and 8 hours at Job II.

Example \(\PageIndex{2}\)

A factory manufactures two types of gadgets, regular and premium. Each gadget requires the use of two operations, assembly and finishing, and there are at most 12 hours available for each operation. A regular gadget requires 1 hour of assembly and 2 hours of finishing, while a premium gadget needs 2 hours of assembly and 1 hour of finishing. Due to other restrictions, the company can make at most 7 gadgets a day. If a profit of $20 is realized for each regular gadget and $30 for a premium gadget, how many of each should be manufactured to maximize profit?

We choose our variables.

• Let \(x\) = The number of regular gadgets manufactured each day.
• and \(y\) = The number of premium gadgets manufactured each day.

The objective function is

\[P = 20x + 30y \nonumber \]

We now write the constraints. The fourth sentence states that the company can make at most 7 gadgets a day. This translates as

\[x + y \leq 7 \nonumber \]

Since the regular gadget requires one hour of assembly and the premium gadget requires two hours of assembly, and there are at most 12 hours available for this operation, we get

\[x + 2y \leq 12 \nonumber \]

Similarly, the regular gadget requires two hours of finishing and the premium gadget one hour. Again, there are at most 12 hours available for finishing. This gives us the following constraint.

\[2x + y \leq 12 \nonumber \]

We have formulated the problem as follows:

\[\begin{array}{ll} \textbf { Maximize } & \mathrm{P}=20 \mathrm{x}+30 \mathrm{y} \\ \textbf { Subject to: } & \mathrm{x}+\mathrm{y} \leq 7 \\ & \mathrm{x}+2\mathrm{y} \leq 12 \\ & 2\mathrm{x} +\mathrm{y} \leq 12 \\ & \mathrm{x} \geq 0 ; \mathrm{y} \geq 0 \end{array} \nonumber \]

In order to solve the problem, we next graph the constraints and feasibility region.

Again, we have shaded the feasibility region, where all constraints are satisfied.

Since the extreme value of the objective function always takes place at the vertices of the feasibility region, we identify all the critical points. They are listed as (0, 0), (0, 6), (2, 5), (5, 2), and (6, 0). To maximize profit, we will substitute these points in the objective function to see which point gives us the maximum profit each day. The results are listed below.

The point (2, 5) gives the most profit, and that profit is $190. Therefore, we conclude that we should manufacture 2 regular gadgets and 5 premium gadgets daily to obtain the maximum profit of $190.

So far we have focused on “ standard maximization problems ” in which

• The objective function is to be maximized
• All constraints are of the form \(ax + by \leq c\)
• All variables are constrained to by non-negative (\(x ≥ 0\), \(y ≥ 0\))

We will next consider an example where that is not the case. Our next problem is said to have “ mixed constraints ”, since some of the inequality constraints are of the form \(ax + by ≤ c\) and some are of the form \(ax + by ≥ c\). The non-negativity constraints are still an important requirement in any linear program.

Example \(\PageIndex{3}\)

Solve the following maximization problem graphically.

\[\begin{array}{ll} \textbf { Maximize } & \mathrm{P}=10 \mathrm{x}+15 \mathrm{y} \\ \textbf { Subject to: } & \mathrm{x}+\mathrm{y} \geq 1 \\ & \mathrm{x}+2\mathrm{y} \leq 6 \\ & 2\mathrm{x} +\mathrm{y} \leq 6 \\ & \mathrm{x} \geq 0 ; \mathrm{y} \geq 0 \end{array} \nonumber \]

The graph is shown below.

The five critical points are listed in the above figure. The reader should observe that the first constraint \(x + y ≥ 1\) requires that the feasibility region must be bounded below by the line \(x + y =1\); the test point (0,0) does not satisfy \(x + y ≥ 1\), so we shade the region on the opposite side of the line from test point (0,0).

Clearly, the point (2, 2) maximizes the objective function to a maximum value of 50.

It is important to observe that that if the point (0,0) lies on the line for a constraint, then (0,0) could not be used as a test point. We would need to select any other point we want that does not lie on the line to use as a test point in that situation.

Finally, we address an important question. Is it possible to determine the point that gives the maximum value without calculating the value at each critical point?

The answer is yes.

For example \(\PageIndex{2}\), we substituted the points (0, 0), (0, 6), (2, 5), (5, 2), and (6, 0), in the objective function \(P = 20x + 30y\), and we got the values $0, $180, $190, $160, $120, respectively.

Sometimes that is not the most efficient way of finding the optimum solution. Instead we could find the optimal value by also graphing the objective function.

To determine the largest \(P\), we graph \(P = 20x + 30y\) for any value \(P\) of our choice. Let us say, we choose \(P = 60\). We graph \(20x + 30y = 60\).

Now we move the line parallel to itself, that is, keeping the same slope at all times. Since we are moving the line parallel to itself, the slope is kept the same, and the only thing that is changing is the P. As we move away from the origin, the value of P increases. The largest possible value of P is realized when the line touches the last corner point of the feasibility region.

The figure below shows the movements of the line, and the optimum solution is achieved at the point (2, 5). In maximization problems, as the line is being moved away from the origin, this optimum point is the farthest critical point.

We summarize:

The Maximization Linear Programming Problems

• Write the objective function.
• For the standard maximization linear programming problems, constraints are of the form: \(ax + by ≤ c\)
• Since the variables are non-negative, we include the constraints: \(x ≥ 0\); \(y ≥ 0\).
• Graph the constraints.
• Shade the feasibility region.
• Find the corner points.
• This is done by finding the value of the objective function at each corner point.
• This can also be done by moving the line associated with the objective function.

Multi-objective Assignment Problems and Their Solutions by Genetic Algorithm

• First Online: 30 May 2021

Cite this chapter

• Anita R. Tailor 19 &
• Jayesh M. Dhodiya 20  

Part of the book series: Modeling and Optimization in Science and Technologies ((MOST,volume 18))

1096 Accesses

1 Citations

Assignment problem (AP) has been usually used to solve decision-making problems in the industrial organization, manufacturing system, developing service system, etc., is to optimally resolve the problem of n-activities to n-devices such that total cost/time can be minimized or total profit/sales can be maximized. In today’s optimization problems, the single objective optimization problems (SOOPs) are not more sufficient to hold the problem facts, hence multi-objective optimization problems (MOOPs) are considered. The purpose of MOOPs in the mathematical programming (MP) structure is to optimize several objective functions under some constraints. In research, the multi-objective field does not give a single optimal solution, but a set of efficient solutions because there are frequently conflicts between the various objectives. In the multi-objective assignment problem (MOAP), significant research concerns related to the study of effective solutions. The current chapter focuses on a genetic algorithm (GA) based approach to find a solution to MOAP. In order to achieve an effective allocation plan, the decision-maker (DM) must specify different aspiration levels (ALs) according to his/her preferences and different shape parameters (SPs) in the exponential membership function (EMF) to show the effect of integration on the effective solution of MOAP. Numerical illustrations are provided to express the usefulness of a specific approach related to the data set from realistic circumstances. This research turned out to be a GA based approach provides effective output based on analysis to take the decision regarding the situation.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Bufardi A (2008) On the efficiency of feasible solutions of a multicriteria assignment problem. Open Oper Res J 2:25–28

Google Scholar  

White DJ (1984) A special multi-objective assignment problem. J Oper Res Soc 759–767.

Tsai C-H, Wei C-C, Cheng C-L et al (1999) Multi-objective fuzzy deployment of manpower. Int J Comput Internet Manag 7(2):1–7

Tuyttens D, Teghem J, Fortemps P, Nieuwenhuyze KV (2000) Performance of the mosa method for the bicriteria assignment problem. J Heuristics 6(3):295–310

Gungor I, Gunes M (2000) Fuzzy multiple criteria assignment problems for fusion: the case of Hungarian algorithm. In: Proceedings of the third international conference on information fusion, 2000. FUSION 2000, vol 1, IEEE, pp TUD4–8

Przybylski A, Gandibleux X, Ehrgott M (2005) The biobjective assignment problem. Technical report. Research report

Bao C-P, Tsai M, Tsai M-I (2007) A new approach to study the multi-objective assignment problem. WHAMPOA Interdisc J 53:123–132

Kagade K, Bajaj V (2009) Fuzzy approach with linear and some non-linear membership functions for solving multi-objective assignment problems. J Adv Comput Res 1:14–17

Odior A, Charles-Owaba O, Oyawale F (2010) Determining feasible solutions of a multicriteria assignment problem. J Appl Sci Environ Manag 14:1

Przybylski A, Gandibleux X, Ehrgott M (2010) A two phase method for multi-objective integer programming and its application to the assignment problem with three objectives. Discrete Optim 7(3):149–165

Li C, Park C, Pattipati KR, Kleinman DL (2011) Distributed algorithms for biobjective assignment problems. In: 2011 50th IEEE conference on decision and control and European control conference (CDC-ECC). IEEE, pp 5893–5898

Adiche C, Aïder M (2010) A hybrid method for solving the multi-objective assignment problem. J Math Modell Algorithms 9(2):149–164

Article   MathSciNet   Google Scholar  

Ozlen M, Burton BA, Macrae CA (2014) Multi-objective integer programming: an improved recursive algorithm. J Optim Theory Appl 160(2):470–482

De P, Yadav B (2011) An algorithm to solve multi-objective assignment problem using interactive fuzzy goal programming approach. Int J Contemp Math Sci 6(34):1651–1662

MathSciNet   MATH   Google Scholar  

Ratli M, Eddaly M, Jarboui B, Lecomte S, Hanafi S (2013) Hybrid genetic algorithm for bi-objective assignment problem. In: Proceedings of 2013 international conference on industrial engineering and systems management (IESM). IEEE, pp 1–6

Gupta P, Mehlawat MK, Mittal G (2013) A fuzzy approach to multicriteria assignment problem using exponential membership functions. Int J Mach Learn Cybern 4(6):647–657

Basirzadeh H, Morovati V, Sayadi A (2014) A quick method to calculate the super-efficient point in multi-objective assignment problems. J Math Comput Sci 10:157–162

Hassan Shirdel G, Mortezaee A (2015) A dea-based approach for the multicriteria assignment problem. Croatian Oper Res Rev 6(1):145–154

Tiwari AK, Tiwari A, Samuel C, Pandey SK (2013) Flexibility in assignment problem using fuzzy numbers with nonlinear membership functions. Int J Ind Eng Technol 3(2):1–10

Jayalakshmi M, Sujatha V (2018) A new algorithm to solve multi-objective assignment problem. Int J Pure Appl Math 119(16):719–724

Medvedeva OA, Medvedev SN (2018) A dual approach to solving a multiobjective assignment problem. IOP Conf Ser J Phys Conf Ser (973)

Hammadi AMK (2017) Solving multi objective assignment problem using Tabu search algorithm. Global J Pure Appl Math 13(9):4747–4764

Belhoul L, Lucie G, Daniel V (2014) An efficient procedure for finding best compromise solutions to the multi-objective assignment problem. Comput Oper Res 49:97–106

Huang G, Lim A (2006) A hybrid genetic algorithm for the three-index assignment problem. Eur J Oper Res 172(1):249–257

Toroslu IH, Arslanoglu Y (2007) Genetic algorithm for the personnel assignment problem with multiple objectives. Inf Sci 177(3):787–803

Nakayama H (1995) Aspiration level approach to interactive multi-objective programming and its applications. In: Advances in multicriteria analysis. Springer, Berlin, pp 147–174

Nakayama H, Yun Y, Yoon M (2009) Interactive programming methods for multi-objective optimization. In: Sequential approximate multiobjective optimization using computational intelligence, pp 17–43

Dhodiya JM, Tailor AR (2016) Genetic algorithm based hybrid approach to solve fuzzy multi-objective assignment problem using exponential membership function. Springerplus 5(1):2028

Article   Google Scholar  

Dhodiya JM, Tailor AR (2018) Genetic algorithm based hybrid approach to solve uncertain multi-objective COTS selection problem for modular software system. J Intell Fuzzy Syst 34(4):2103–2120

Tailor AR, Dhodiya JM (2016) Genetic algorithm based hybrid approach to solve optimistic, most-likely and pessimistic scenarios of fuzzy multi-objective assignment problem using exponential membership function. J Adv Math Comput Sci 1–19

Rajan K (2013) Adaptive techniques in genetic algorithm and its applications. Ph.D. thesis, Kottayam

Sahu A, Tapadar R (2006) Solving the assignment problem using genetic algorithm and simulated annealing. In: IMECS, pp 762–765

Sani H, Yabo M (2016) Solving timetabling problems using genetic algorithm technique. Int J Comput Appl 134:15

Sivanandam S, Deepa S (2007) Introduction to genetic algorithms. Springer Science & Business Media, Berlin

Tosun U (2014) A new recombination operator for the genetic algorithm solution of the quadratic assignment problem. Procedia Comput Sci 32:29–36

Wu B, Tu X, Wu J (2000) Generalized self-adaptive genetic algorithms. J Univ Sci Technol Beijing Eng Ed 7(1):72–75

Younas I (2014) Using genetic algorithms for large scale optimization of assignment, planning and rescheduling problems. Ph.D. thesis, KTH Royal Institute of Technology

Tailor AR, Dhodiya JM (2016) A genetic algorithm based hybrid approach to solve multi-objective interval assignment problem by estimation theory. Indian J Sci Technol 9(35):0974–5645

Tailor AR, Dhodiya JM (2016) Genetic algorithm based hybrid approach to solve multi-objective assignment problem. Int J Innov Res Sci Eng Technol 5(1):524–535

Download references

Author information

Authors and affiliations.

Navyug Science College, Surat, India

Anita R. Tailor

S. V. National Institute of Technology, Surat, India

Jayesh M. Dhodiya

You can also search for this author in PubMed   Google Scholar

Editor information

Editors and affiliations.

Department of Computer Science and Engineering, Faculty of Engineering, SOA University, Bhubaneswar, Odisha, India

Srikanta Patnaik

Strategic Management and International Business, Tokyo Institute of Technology, Tokyo, Japan

Kayhan Tajeddini

School of Management, Victoria University of Wellington, Wellington, New Zealand

Rights and permissions

Reprints and permissions

Copyright information

© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this chapter

Tailor, A.R., Dhodiya, J.M. (2021). Multi-objective Assignment Problems and Their Solutions by Genetic Algorithm. In: Patnaik, S., Tajeddini, K., Jain, V. (eds) Computational Management. Modeling and Optimization in Science and Technologies, vol 18. Springer, Cham. https://doi.org/10.1007/978-3-030-72929-5_19

Download citation

DOI : https://doi.org/10.1007/978-3-030-72929-5_19

Published : 30 May 2021

Publisher Name : Springer, Cham

Print ISBN : 978-3-030-72928-8

Online ISBN : 978-3-030-72929-5

eBook Packages : Business and Management Business and Management (R0)

Share this chapter

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

Assignment Problem: Meaning, Methods and Variations | Operations Research

After reading this article you will learn about:- 1. Meaning of Assignment Problem 2. Definition of Assignment Problem 3. Mathematical Formulation 4. Hungarian Method 5. Variations.

Meaning of Assignment Problem:

An assignment problem is a particular case of transportation problem where the objective is to assign a number of resources to an equal number of activities so as to minimise total cost or maximize total profit of allocation.

The problem of assignment arises because available resources such as men, machines etc. have varying degrees of efficiency for performing different activities, therefore, cost, profit or loss of performing the different activities is different.

Thus, the problem is “How should the assignments be made so as to optimize the given objective”. Some of the problem where the assignment technique may be useful are assignment of workers to machines, salesman to different sales areas.

Definition of Assignment Problem:

ADVERTISEMENTS:

Suppose there are n jobs to be performed and n persons are available for doing these jobs. 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. 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.

The assignment problem can be stated in the form of n x n cost matrix C real members as given in the following table:

Solving Assignment Problem using Linear Programming in Python

Learn how to use Python PuLP to solve Assignment problems using Linear Programming.

In earlier articles, we have seen various applications of Linear programming such as transportation, transshipment problem, Cargo Loading problem, and shift-scheduling problem. Now In this tutorial, we will focus on another model that comes under the class of linear programming model known as the Assignment problem. Its objective function is similar to transportation problems. Here we minimize the objective function time or cost of manufacturing the products by allocating one job to one machine.

If we want to solve the maximization problem assignment problem then we subtract all the elements of the matrix from the highest element in the matrix or multiply the entire matrix by –1 and continue with the procedure. For solving the assignment problem, we use the Assignment technique or Hungarian method, or Flood’s technique.

The transportation problem is a special case of the linear programming model and the assignment problem is a special case of transportation problem, therefore it is also a special case of the linear programming problem.

In this tutorial, we are going to cover the following topics:

Assignment Problem

A problem that requires pairing two sets of items given a set of paired costs or profit in such a way that the total cost of the pairings is minimized or maximized. The assignment problem is a special case of linear programming.

For example, an operation manager needs to assign four jobs to four machines. The project manager needs to assign four projects to four staff members. Similarly, the marketing manager needs to assign the 4 salespersons to 4 territories. The manager’s goal is to minimize the total time or cost.

Problem Formulation

A manager has prepared a table that shows the cost of performing each of four jobs by each of four employees. The manager has stated his goal is to develop a set of job assignments that will minimize the total cost of getting all 4 jobs.  

Initialize LP Model

In this step, we will import all the classes and functions of pulp module and create a Minimization LP problem using LpProblem class.

Define Decision Variable

In this step, we will define the decision variables. In our problem, we have two variable lists: workers and jobs. Let’s create them using  LpVariable.dicts()  class.  LpVariable.dicts()  used with Python’s list comprehension.  LpVariable.dicts()  will take the following four values:

• First, prefix name of what this variable represents.
• Second is the list of all the variables.
• Third is the lower bound on this variable.
• Fourth variable is the upper bound.
• Fourth is essentially the type of data (discrete or continuous). The options for the fourth parameter are  LpContinuous  or  LpInteger .

Let’s first create a list route for the route between warehouse and project site and create the decision variables using LpVariable.dicts() the method.

Define Objective Function

In this step, we will define the minimum objective function by adding it to the LpProblem  object. lpSum(vector)is used here to define multiple linear expressions. It also used list comprehension to add multiple variables.

Define the Constraints

Here, we are adding two types of constraints: Each job can be assigned to only one employee constraint and Each employee can be assigned to only one job. We have added the 2 constraints defined in the problem by adding them to the LpProblem  object.

Solve Model

In this step, we will solve the LP problem by calling solve() method. We can print the final value by using the following for loop.

From the above results, we can infer that Worker-1 will be assigned to Job-1, Worker-2 will be assigned to job-3, Worker-3 will be assigned to Job-2, and Worker-4 will assign with job-4.

In this article, we have learned about Assignment problems, Problem Formulation, and implementation using the python PuLp library. We have solved the Assignment problem using a Linear programming problem in Python. Of course, this is just a simple case study, we can add more constraints to it and make it more complicated. You can also run other case studies on Cargo Loading problems , Staff scheduling problems . In upcoming articles, we will write more on different optimization problems such as transshipment problem, balanced diet problem. You can revise the basics of mathematical concepts in  this article  and learn about Linear Programming  in this article .

• Solving Blending Problem in Python using Gurobi
• Transshipment Problem in Python Using PuLP

You May Also Like

Working with crosstab, pivot_tables, and melt functions in Pandas

Solving Staff Scheduling Problem using Linear Programming

Solving Cargo Loading Problem using Integer Programming in Python