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

OPERATIONS RESEARCH

Lesson 9. solution of assignment problem.

Current course

solve the following assignment problem minimisation

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:

Hungarian Method

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

solve the following assignment problem minimisation

  • Share Share

Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

close

Procedure, Example Solved Problem | Operations Research - Solution of assignment problems (Hungarian Method) | 12th Business Maths and Statistics : Chapter 10 : Operations Research

Chapter: 12th business maths and statistics : chapter 10 : operations research.

Solution of assignment problems (Hungarian Method)

First check whether the number of rows is equal to the numbers of columns, if it is so, the assignment problem is said to be balanced.

Step :1 Choose the least element in each row and subtract it from all the elements of that row.

Step :2 Choose the least element in each column and subtract it from all the elements of that column. Step 2 has to be performed from the table obtained in step 1.

Step:3 Check whether there is atleast one zero in each row and each column and make an assignment as follows.

solve the following assignment problem minimisation

Step :4 If each row and each column contains exactly one assignment, then the solution is optimal.

Example 10.7

Solve the following assignment problem. Cell values represent cost of assigning job A, B, C and D to the machines I, II, III and IV.

solve the following assignment problem minimisation

Here the number of rows and columns are equal.

∴ The given assignment problem is balanced. Now let us find the solution.

Step 1: Select a smallest element in each row and subtract this from all the elements in its row.

solve the following assignment problem minimisation

Look for atleast one zero in each row and each column.Otherwise go to step 2.

Step 2: Select the smallest element in each column and subtract this from all the elements in its column.

solve the following assignment problem minimisation

Since each row and column contains atleast one zero, assignments can be made.

Step 3 (Assignment):

solve the following assignment problem minimisation

Thus all the four assignments have been made. The optimal assignment schedule and total cost is

solve the following assignment problem minimisation

The optimal assignment (minimum) cost

Example 10.8

Consider the problem of assigning five jobs to five persons. The assignment costs are given as follows. Determine the optimum assignment schedule.

solve the following assignment problem minimisation

∴ The given assignment problem is balanced.

Now let us find the solution.

The cost matrix of the given assignment problem is

solve the following assignment problem minimisation

Column 3 contains no zero. Go to Step 2.

solve the following assignment problem minimisation

Thus all the five assignments have been made. The Optimal assignment schedule and total cost is

solve the following assignment problem minimisation

The optimal assignment (minimum) cost = ` 9

Example 10.9

Solve the following assignment problem.

solve the following assignment problem minimisation

Since the number of columns is less than the number of rows, given assignment problem is unbalanced one. To balance it , introduce a dummy column with all the entries zero. The revised assignment problem is

solve the following assignment problem minimisation

Here only 3 tasks can be assigned to 3 men.

Step 1: is not necessary, since each row contains zero entry. Go to Step 2.

solve the following assignment problem minimisation

Step 3 (Assignment) :

solve the following assignment problem minimisation

Since each row and each columncontains exactly one assignment,all the three men have been assigned a task. But task S is not assigned to any Man. The optimal assignment schedule and total cost is

solve the following assignment problem minimisation

The optimal assignment (minimum) cost = ₹ 35

Related Topics

Privacy Policy , Terms and Conditions , DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.

The assignment problem revisited

  • Original Paper
  • Published: 16 August 2021
  • Volume 16 , pages 1531–1548, ( 2022 )

Cite this article

  • Carlos A. Alfaro   ORCID: orcid.org/0000-0001-9783-8587 1 ,
  • Sergio L. Perez 2 ,
  • Carlos E. Valencia 3 &
  • Marcos C. Vargas 1  

911 Accesses

4 Citations

4 Altmetric

Explore all metrics

First, we give a detailed review of two algorithms that solve the minimization case of the assignment problem, the Bertsekas auction algorithm and the Goldberg & Kennedy algorithm. It was previously alluded that both algorithms are equivalent. We give a detailed proof that these algorithms are equivalent. Also, we perform experimental results comparing the performance of three algorithms for the assignment problem: the \(\epsilon \) - scaling auction algorithm , the Hungarian algorithm and the FlowAssign algorithm . The experiment shows that the auction algorithm still performs and scales better in practice than the other algorithms which are harder to implement and have better theoretical time complexity.

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

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

solve the following assignment problem minimisation

Bertsekas, D.P.: The auction algorithm: a distributed relaxation method for the assignment problem. Annal Op. Res. 14 , 105–123 (1988)

Article   MathSciNet   Google Scholar  

Bertsekas, D.P., Castañon, D.A.: Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Comput. 17 , 707–732 (1991)

Article   Google Scholar  

Bertsekas, D.P.: Linear network optimization: algorithms and codes. MIT Press, Cambridge, MA (1991)

MATH   Google Scholar  

Bertsekas, D.P.: The auction algorithm for shortest paths. SIAM J. Optim. 1 , 425–477 (1991)

Bertsekas, D.P.: Auction algorithms for network flow problems: a tutorial introduction. Comput. Optim. Appl. 1 , 7–66 (1992)

Bertsekas, D.P., Castañon, D.A., Tsaknakis, H.: Reverse auction and the solution of inequality constrained assignment problems. SIAM J. Optim. 3 , 268–299 (1993)

Bertsekas, D.P., Eckstein, J.: Dual coordinate step methods for linear network flow problems. Math. Progr., Ser. B 42 , 203–243 (1988)

Bertsimas, D., Tsitsiklis, J.N.: Introduction to linear optimization. Athena Scientific, Belmont, MA (1997)

Google Scholar  

Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems. Revised reprint. SIAM, Philadelphia, PA (2011)

Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for network problems. SIAM J. Comput. 18 (5), 1013–1036 (1989)

Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum flow problem. J. Assoc. Comput. Mach. 35 , 921–940 (1988)

Goldberg, A.V., Tarjan, R.E.: Finding minimum-cost circulations by successive approximation. Math. Op. Res. 15 , 430–466 (1990)

Goldberg, A.V., Kennedy, R.: An efficient cost scaling algorithm for the assignment problem. Math. Programm. 71 , 153–177 (1995)

MathSciNet   MATH   Google Scholar  

Goldberg, A.V., Kennedy, R.: Global price updates help. SIAM J. Discr. Math. 10 (4), 551–572 (1997)

Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2 , 83–97 (1955)

Kuhn, H.W.: Variants of the Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2 , 253–258 (1956)

Lawler, E.L.: Combinatorial optimization: networks and matroids, Holt. Rinehart & Winston, New York (1976)

Orlin, J.B., Ahuja, R.K.: New scaling algorithms for the assignment ad minimum mean cycle problems. Math. Programm. 54 , 41–56 (1992)

Ramshaw, L., Tarjan, R.E., Weight-Scaling Algorithm, A., for Min-Cost Imperfect Matchings in Bipartite Graphs, : IEEE 53rd Annual Symposium on Foundations of Computer Science. New Brunswick, NJ 2012 , 581–590 (2012)

Zaki, H.: A comparison of two algorithms for the assignment problem. Comput. Optim. Appl. 4 , 23–45 (1995)

Download references

Acknowledgements

This research was partially supported by SNI and CONACyT.

Author information

Authors and affiliations.

Banco de México, Mexico City, Mexico

Carlos A. Alfaro & Marcos C. Vargas

Mountain View, CA, 94043, USA

Sergio L. Perez

Departamento de Matemáticas, CINVESTAV del IPN, Apartado postal 14-740, 07000, Mexico City, Mexico

Carlos E. Valencia

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Carlos A. Alfaro .

Ethics declarations

Conflict of interest.

There is no conflict of interest.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The authors were partially supported by SNI and CONACyT.

Rights and permissions

Reprints and permissions

About this article

Alfaro, C.A., Perez, S.L., Valencia, C.E. et al. The assignment problem revisited. Optim Lett 16 , 1531–1548 (2022). https://doi.org/10.1007/s11590-021-01791-4

Download citation

Received : 26 March 2020

Accepted : 03 August 2021

Published : 16 August 2021

Issue Date : June 2022

DOI : https://doi.org/10.1007/s11590-021-01791-4

Share this article

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

  • Assignment problem
  • Bertsekas auction algorithm
  • Combinatorial optimization and matching
  • Find a journal
  • Publish with us
  • Track your research
  • Linear Programming using Pyomo
  • Networking and Professional Development for Machine Learning Careers in the USA
  • Predicting Employee Churn in Python
  • Airflow Operators
  • MLOps Tutorial

Machine Learning Geek

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.  

Assignment Problem

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

solve the following assignment problem minimisation

Data Visualization using Matplotlib

solve the following assignment problem minimisation

Spectral Clustering

solve the following assignment problem minimisation

Pandas map() and reduce() Operations

Library homepage

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

Mathematics LibreTexts

3.1: Maximization Applications

  • Last updated
  • Save as PDF
  • Page ID 37861

  • Rupinder Sekhon and Roberta Bloom
  • De Anza College

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\).

Example3.1.1.png

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.

Example3.1.2.png

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.

Example3.1.3.png

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.

Section3.1.png

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.

IMAGES

  1. Solved Question 2 Solve the following minimisation problem

    solve the following assignment problem minimisation

  2. Solved 1.1 (a) Solve the following minimization problem by

    solve the following assignment problem minimisation

  3. Balanced Assignment Problem [ Minimization Type] #AssignmentProblem #HungarianMethod

    solve the following assignment problem minimisation

  4. Solved Q1: Consider the minimisation of the following

    solve the following assignment problem minimisation

  5. Solved Instructions: Solve all the Assignment Problems with

    solve the following assignment problem minimisation

  6. Unit 1 Lesson 20 :Solving Assignment problem

    solve the following assignment problem minimisation

VIDEO

  1. Assignment Problem Part

  2. Operation Management

  3. Assignment Model

  4. Assignment Problem (Balanced)

  5. Assignment Model

  6. Assignment Model

COMMENTS

  1. Solve the Following Assignment Problem to Minimize the Cost

    ∴ Given problem is unbalanced . Step 1: For making it balanced, we add dummy job(iv) with cost zero. Step 2: Minimum elements of each row is subtracted from every element of that row. Resultant matrix is same. Step 3: Minimum element in each column is subtracted from every element in that column.

  2. Hungarian Method Examples, Assignment Problem

    Solution. This is a minimization example of assignment problem.We will use the Hungarian Algorithm to solve this problem.. Step 1. Identify the minimum element in each row and subtract it from every element of that row. The result is shown in the following table.

  3. Assignment Problem, Maximization Example, Hungarian Method

    Here, the highest value is 62. So we subtract each value from 62. The conversion is shown in the following table. 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 ...

  4. ES-3: Lesson 9. SOLUTION OF ASSIGNMENT PROBLEM

    For an assignment problem of order n x n there would be only n basic variables in the solution because here n assignments are required to be made. This degeneracy problem of solution makes the transportation method computationally inefficient for solving the assignment problem. 9.2.4 Hungarian assignment method

  5. Assignment Problem using Hungarian Method (Minimization Problem

    In this video you will be able to understand how to solve an assignment problem (Minimization) using Hungarian method. The step by step procedure is provided...

  6. Hungarian method calculator

    Hungarian method calculator. 1. A computer centre has 3expert programmers. The centre wants 3 application programmes to be developed. The head of thecomputer centre, after studying carefully the programmes to be developed, estimates the computer time in minutes required by the experts for the application programmes as follows. Programmers.

  7. 4.7: Optimization Problems

    Step 4: From Figure 4.7.5, the line segment of y miles forms the hypotenuse of a right triangle with legs of length 2 mi and 6 − x mi. Therefore, by the Pythagorean theorem, 22 + (6 − x)2 = y2, and we obtain y = √(6 − x)2 + 4. Thus, the total time spent traveling is given by the function. T(x) = x 8 + √(6 − x)2 + 4 3.

  8. 4.3: Minimization By The Simplex Method

    To do this, we solve the dual by the simplex method. Example 4.3.3. Find the solution to the minimization problem in Example 4.3.1 by solving its dual using the simplex method. We rewrite our problem. Minimize Z = 12x1 + 16x2 Subject to: x1 + 2x2 ≥ 40 x1 + x2 ≥ 30 x1 ≥ 0; x2 ≥ 0.

  9. 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.

  10. PROBLEM II: Solve the following Assignment Problem

    Question: PROBLEM II: Solve the following Assignment Problem with the Minimization Objective. Answer the following questions. Job 1 Job 2 Job 3 Job 4 Person A 8 3 8 9 Person B 1 0 3 3 Person C 0 -2 2 3 Person D 2 -3 3 4 Do not write any thing adjacent to the table above. Use the space on the next page to create all the tables needed to solve ...

  11. Solving Minimization Assignment Problem with Python

    This video tutorial illustrates how you can solve the Assignment Problem (AP) using the Hungarian Method in Python

  12. PDF Unit 1 Lesson 20 :Solving Assignment problem

    Lesson 20 :Solving Assignment problem Learning objectives: • Solve the assignment problem using Hungarian method. • Analyze special cases in assignment problems. Writing of an assignment problem as a Linear programming problem Example 1. Three men are to to be given 3 jobs and it is assumed that a person is fully capable of doing a job ...

  13. Solution of assignment problems (Hungarian Method)

    Step :4 If each row and each column contains exactly one assignment, then the solution is optimal. Example 10.7. Solve the following assignment problem. Cell values represent cost of assigning job A, B, C and D to the machines I, II, III and IV. Solution: Here the number of rows and columns are equal. ∴ The given assignment problem is ...

  14. 7.5.1: Minimization By The Simplex Method (Exercises)

    SECTION 7.5 PROBLEM SET: MINIMIZATION BY THE SIMPLEX METHOD. In problems 1-2, convert each minimization problem into a maximization problem, the dual, and then solve by the simplex method. 1) Minimize subject to z = 6x1 + 8x2 2x1 + 3x2 ≥ 7 4x1 + 5x2 ≥ 9 x1,x2 ≥ 0 Minimize z = 6 x 1 + 8 x 2 subject to 2 x 1 + 3 x 2 ≥ 7 4 x 1 + 5 x 2 ≥ ...

  15. The assignment problem revisited

    First, we give a detailed review of two algorithms that solve the minimization case of the assignment problem, the Bertsekas auction algorithm and the Goldberg & Kennedy algorithm. It was previously alluded that both algorithms are equivalent. We give a detailed proof that these algorithms are equivalent. Also, we perform experimental results comparing the performance of three algorithms for ...

  16. 4: Linear Programming

    4.3: Minimization By The Simplex Method. In this section, we will solve the standard linear programming minimization problems using the simplex method. The procedure to solve these problems involves solving an associated problem called the dual problem. The solution of the dual problem is used to find the solution of the original problem.

  17. Solving Assignment Problem using Linear Programming in Python

    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.

  18. Assignment problem

    Worked example of assigning tasks to an unequal number of workers using the Hungarian method. The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows: The problem instance has a number of agents and a number of tasks.Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent ...

  19. Solved 2. Solve the following minimization problem by

    Question: 2. Solve the following minimization problem by applying the simplex method to its dual problem (see examples 1 and 2 in section 4.5). Minimize the objective function 3r +5y+ z subject to the constraints , y, z 2 0 Provide the detailed solutions for both problems. There are 2 steps to solve this one.

  20. PDF Solving The Assignment Problems Directly Without Any Iterations

    (Minimization and balanced [2] assignment problem) Consider a minimization assignment problem with the following 3×3 cost matrix which represents 3 employees and 3 jobs. 25 40 35 40 60 35 20 40 25 ªº «» «» «»¬¼ First: we add an additional row and column for the matrix as follows: Job1 Job2 Job3 Row Sum Emp.1 25 40 35 R 1 = 100

  21. 4.4: Linear Programming

    Minimization linear programming problems are solved in much the same way as the maximization problems. For the standard minimization linear program, the constraints are of the form \(ax + by ≥ c\), as opposed to the form \(ax + by ≤ c\) for the standard maximization problem.As a result, the feasible solution extends indefinitely to the upper right of the first quadrant, and is unbounded.

  22. 3.1: Maximization Applications

    For the standard maximization linear programming problems, constraints are of the form: a x + b y ≤ 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. Determine the corner point that gives the maximum value.