maximization assignment problem example

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

Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

4.7 Applied Optimization Problems

Learning objectives.

• 4.7.1 Set up and solve optimization problems in several applied fields.

One common application of calculus is calculating the minimum or maximum value of a function. For example, companies often want to minimize production costs or maximize revenue. In manufacturing, it is often desirable to minimize the amount of material used to package a product with a certain volume. In this section, we show how to set up these types of minimization and maximization problems and solve them by using the tools developed in this chapter.

Solving Optimization Problems over a Closed, Bounded Interval

The basic idea of the optimization problems that follow is the same. We have a particular quantity that we are interested in maximizing or minimizing. However, we also have some auxiliary condition that needs to be satisfied. For example, in Example 4.32 , we are interested in maximizing the area of a rectangular garden. Certainly, if we keep making the side lengths of the garden larger, the area will continue to become larger. However, what if we have some restriction on how much fencing we can use for the perimeter? In this case, we cannot make the garden as large as we like. Let’s look at how we can maximize the area of a rectangle subject to some constraint on the perimeter.

Example 4.32

Maximizing the area of a garden.

A rectangular garden is to be constructed using a rock wall as one side of the garden and wire fencing for the other three sides ( Figure 4.62 ). Given 100 100 ft of wire fencing, determine the dimensions that would create a garden of maximum area. What is the maximum area?

Let x x denote the length of the side of the garden perpendicular to the rock wall and y y denote the length of the side parallel to the rock wall. Then the area of the garden is

We want to find the maximum possible area subject to the constraint that the total fencing is 100 ft . 100 ft . From Figure 4.62 , the total amount of fencing used will be 2 x + y . 2 x + y . Therefore, the constraint equation is

Solving this equation for y , y , we have y = 100 − 2 x . y = 100 − 2 x . Thus, we can write the area as

Before trying to maximize the area function A ( x ) = 100 x − 2 x 2 , A ( x ) = 100 x − 2 x 2 , we need to determine the domain under consideration. To construct a rectangular garden, we certainly need the lengths of both sides to be positive. Therefore, we need x > 0 x > 0 and y > 0 . y > 0 . Since y = 100 − 2 x , y = 100 − 2 x , if y > 0 , y > 0 , then x < 50 . x < 50 . Therefore, we are trying to determine the maximum value of A ( x ) A ( x ) for x x over the open interval ( 0 , 50 ) . ( 0 , 50 ) . We do not know that a function necessarily has a maximum value over an open interval. However, we do know that a continuous function has an absolute maximum (and absolute minimum) over a closed interval. Therefore, let’s consider the function A ( x ) = 100 x − 2 x 2 A ( x ) = 100 x − 2 x 2 over the closed interval [ 0 , 50 ] . [ 0 , 50 ] . If the maximum value occurs at an interior point, then we have found the value x x in the open interval ( 0 , 50 ) ( 0 , 50 ) that maximizes the area of the garden. Therefore, we consider the following problem:

Maximize A ( x ) = 100 x − 2 x 2 A ( x ) = 100 x − 2 x 2 over the interval [ 0 , 50 ] . [ 0 , 50 ] .

As mentioned earlier, since A A is a continuous function on a closed, bounded interval, by the extreme value theorem, it has a maximum and a minimum. These extreme values occur either at endpoints or critical points. At the endpoints, A ( x ) = 0 . A ( x ) = 0 . Since the area is positive for all x x in the open interval ( 0 , 50 ) , ( 0 , 50 ) , the maximum must occur at a critical point. Differentiating the function A ( x ) , A ( x ) , we obtain

Therefore, the only critical point is x = 25 x = 25 ( Figure 4.63 ). We conclude that the maximum area must occur when x = 25 . x = 25 . Then we have y = 100 − 2 x = 100 − 2 ( 25 ) = 50 . y = 100 − 2 x = 100 − 2 ( 25 ) = 50 . To maximize the area of the garden, let x = 25 x = 25 ft and y = 50 ft . y = 50 ft . The area of this garden is 1250 ft 2 . 1250 ft 2 .

Checkpoint 4.31

Determine the maximum area if we want to make the same rectangular garden as in Figure 4.63 , but we have 200 200 ft of fencing.

Now let’s look at a general strategy for solving optimization problems similar to Example 4.32 .

Problem-Solving Strategy

Problem-solving strategy: solving optimization problems.

• Introduce all variables. If applicable, draw a figure and label all variables.
• Determine which quantity is to be maximized or minimized, and for what range of values of the other variables (if this can be determined at this time).
• Write a formula for the quantity to be maximized or minimized in terms of the variables. This formula may involve more than one variable.
• Write any equations relating the independent variables in the formula from step 3 . 3 . Use these equations to write the quantity to be maximized or minimized as a function of one variable.
• Identify the domain of consideration for the function in step 4 4 based on the physical problem to be solved.
• Locate the maximum or minimum value of the function from step 4 . 4 . This step typically involves looking for critical points and evaluating a function at endpoints.

Now let’s apply this strategy to maximize the volume of an open-top box given a constraint on the amount of material to be used.

Example 4.33

Maximizing the volume of a box.

An open-top box is to be made from a 24 24 in. by 36 36 in. piece of cardboard by removing a square from each corner of the box and folding up the flaps on each side. What size square should be cut out of each corner to get a box with the maximum volume?

Step 1: Let x x be the side length of the square to be removed from each corner ( Figure 4.64 ). Then, the remaining four flaps can be folded up to form an open-top box. Let V V be the volume of the resulting box.

Step 2: We are trying to maximize the volume of a box. Therefore, the problem is to maximize V . V .

Step 3: As mentioned in step 2 , 2 , we are trying to maximize the volume of a box. The volume of a box is V = L · W · H , V = L · W · H , where L , W , and H L , W , and H are the length, width, and height, respectively.

Step 4: From Figure 4.64 , we see that the height of the box is x x inches, the length is 36 − 2 x 36 − 2 x inches, and the width is 24 − 2 x 24 − 2 x inches. Therefore, the volume of the box is

Step 5: To determine the domain of consideration, let’s examine Figure 4.64 . Certainly, we need x > 0 . x > 0 . Furthermore, the side length of the square cannot be greater than or equal to half the length of the shorter side, 24 24 in.; otherwise, one of the flaps would be completely cut off. Therefore, we are trying to determine whether there is a maximum volume of the box for x x over the open interval ( 0 , 12 ) . ( 0 , 12 ) . Since V V is a continuous function over the closed interval [ 0 , 12 ] , [ 0 , 12 ] , we know V V will have an absolute maximum over the closed interval. Therefore, we consider V V over the closed interval [ 0 , 12 ] [ 0 , 12 ] and check whether the absolute maximum occurs at an interior point.

Step 6: Since V ( x ) V ( x ) is a continuous function over the closed, bounded interval [ 0 , 12 ] , [ 0 , 12 ] , V V must have an absolute maximum (and an absolute minimum). Since V ( x ) = 0 V ( x ) = 0 at the endpoints and V ( x ) > 0 V ( x ) > 0 for 0 < x < 12 , 0 < x < 12 , the maximum must occur at a critical point. The derivative is

To find the critical points, we need to solve the equation

Dividing both sides of this equation by 12 , 12 , the problem simplifies to solving the equation

Using the quadratic formula, we find that the critical points are

Since 10 + 2 7 10 + 2 7 is not in the domain of consideration, the only critical point we need to consider is 10 − 2 7 . 10 − 2 7 . Therefore, the volume is maximized if we let x = 10 − 2 7 in . x = 10 − 2 7 in . The maximum volume is V ( 10 − 2 7 ) = 640 + 448 7 ≈ 1825 in . 3 V ( 10 − 2 7 ) = 640 + 448 7 ≈ 1825 in . 3 as shown in the following graph.

Watch a video about optimizing the volume of a box.

Checkpoint 4.32

Suppose the dimensions of the cardboard in Example 4.33 are 20 in. by 30 in. Let x x be the side length of each square and write the volume of the open-top box as a function of x . x . Determine the domain of consideration for x . x .

Example 4.34

Minimizing travel time.

An island is 2 mi 2 mi due north of its closest point along a straight shoreline. A visitor is staying at a cabin on the shore that is 6 mi 6 mi west of that point. The visitor is planning to go from the cabin to the island. Suppose the visitor runs at a rate of 8 mph 8 mph and swims at a rate of 3 mph . 3 mph . How far should the visitor run before swimming to minimize the time it takes to reach the island?

Step 1: Let x x be the distance running and let y y be the distance swimming ( Figure 4.66 ). Let T T be the time it takes to get from the cabin to the island.

Step 2: The problem is to minimize T . T .

Step 3: To find the time spent traveling from the cabin to the island, add the time spent running and the time spent swimming. Since Distance = = Rate × × Time ( D = R × T ) , ( D = R × T ) , the time spent running is

and the time spent swimming is

Therefore, the total time spent traveling is

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

Step 5: From Figure 4.66 , we see that 0 ≤ x ≤ 6 . 0 ≤ x ≤ 6 . Therefore, [ 0 , 6 ] [ 0 , 6 ] is the domain of consideration.

Step 6: Since T ( x ) T ( x ) is a continuous function over a closed, bounded interval, it has a maximum and a minimum. Let’s begin by looking for any critical points of T T over the interval [ 0 , 6 ] . [ 0 , 6 ] . The derivative is

If T ′ ( x ) = 0 , T ′ ( x ) = 0 , then

Squaring both sides of this equation, we see that if x x satisfies this equation, then x x must satisfy

which implies

We conclude that if x x is a critical point, then x x satisfies

Therefore, the possibilities for critical points are

Since x = 6 + 6 / 55 x = 6 + 6 / 55 is not in the domain, it is not a possibility for a critical point. On the other hand, x = 6 − 6 / 55 x = 6 − 6 / 55 is in the domain. Since we squared both sides of Equation 4.6 to arrive at the possible critical points, it remains to verify that x = 6 − 6 / 55 x = 6 − 6 / 55 satisfies Equation 4.6 . Since x = 6 − 6 / 55 x = 6 − 6 / 55 does satisfy that equation, we conclude that x = 6 − 6 / 55 x = 6 − 6 / 55 is a critical point, and it is the only one. To justify that the time is minimized for this value of x , x , we just need to check the values of T ( x ) T ( x ) at the endpoints x = 0 x = 0 and x = 6 , x = 6 , and compare them with the value of T ( x ) T ( x ) at the critical point x = 6 − 6 / 55 . x = 6 − 6 / 55 . We find that T ( 0 ) ≈ 2.108 h T ( 0 ) ≈ 2.108 h and T ( 6 ) ≈ 1.417 h, T ( 6 ) ≈ 1.417 h, whereas T ( 6 − 6 / 55 ) ≈ 1.368 h . T ( 6 − 6 / 55 ) ≈ 1.368 h . Therefore, we conclude that T T has a local minimum at x ≈ 5.19 x ≈ 5.19 mi.

Checkpoint 4.33

Suppose the island is 1 1 mi from shore, and the distance from the cabin to the point on the shore closest to the island is 15 mi . 15 mi . Suppose a visitor swims at the rate of 2.5 mph 2.5 mph and runs at a rate of 6 mph . 6 mph . Let x x denote the distance the visitor will run before swimming, and find a function for the time it takes the visitor to get from the cabin to the island.

In business, companies are interested in maximizing revenue . In the following example, we consider a scenario in which a company has collected data on how many cars it is able to lease, depending on the price it charges its customers to rent a car. Let’s use these data to determine the price the company should charge to maximize the amount of money it brings in.

Example 4.35

Maximizing revenue.

Owners of a car rental company have determined that if they charge customers p p dollars per day to rent a car, where 50 ≤ p ≤ 200 , 50 ≤ p ≤ 200 , the number of cars n n they rent per day can be modeled by the linear function n ( p ) = 1000 − 5 p . n ( p ) = 1000 − 5 p . If they charge $ 50 $ 50 per day or less, they will rent all their cars. If they charge $ 200 $ 200 per day or more, they will not rent any cars. Assuming the owners plan to charge customers between $50 per day and $ 200 $ 200 per day to rent a car, how much should they charge to maximize their revenue?

Step 1: Let p p be the price charged per car per day and let n n be the number of cars rented per day. Let R R be the revenue per day.

Step 2: The problem is to maximize R . R .

Step 3: The revenue (per day) is equal to the number of cars rented per day times the price charged per car per day—that is, R = n × p . R = n × p .

Step 4: Since the number of cars rented per day is modeled by the linear function n ( p ) = 1000 − 5 p , n ( p ) = 1000 − 5 p , the revenue R R can be represented by the function

Step 5: Since the owners plan to charge between $ 50 $ 50 per car per day and $ 200 $ 200 per car per day, the problem is to find the maximum revenue R ( p ) R ( p ) for p p in the closed interval [ 50 , 200 ] . [ 50 , 200 ] .

Step 6: Since R R is a continuous function over the closed, bounded interval [ 50 , 200 ] , [ 50 , 200 ] , it has an absolute maximum (and an absolute minimum) in that interval. To find the maximum value, look for critical points. The derivative is R ′ ( p ) = −10 p + 1000 . R ′ ( p ) = −10 p + 1000 . Therefore, the critical point is p = 100 p = 100 When p = 100 , p = 100 , R ( 100 ) = $ 50,000 . R ( 100 ) = $ 50,000 . When p = 50 , p = 50 , R ( p ) = $ 37,500 . R ( p ) = $ 37,500 . When p = 200 , p = 200 , R ( p ) = $ 0 . R ( p ) = $ 0 . Therefore, the absolute maximum occurs at p = $ 100 . p = $ 100 . The car rental company should charge $ 100 $ 100 per day per car to maximize revenue as shown in the following figure.

Checkpoint 4.34

A car rental company charges its customers p p dollars per day, where 60 ≤ p ≤ 150 . 60 ≤ p ≤ 150 . It has found that the number of cars rented per day can be modeled by the linear function n ( p ) = 750 − 5 p . n ( p ) = 750 − 5 p . How much should the company charge each customer to maximize revenue?

Example 4.36

Maximizing the area of an inscribed rectangle.

A rectangle is to be inscribed in the ellipse

What should the dimensions of the rectangle be to maximize its area? What is the maximum area?

Step 1: For a rectangle to be inscribed in the ellipse, the sides of the rectangle must be parallel to the axes. Let L L be the length of the rectangle and W W be its width. Let A A be the area of the rectangle.

Step 2: The problem is to maximize A . A .

Step 3: The area of the rectangle is A = L W . A = L W .

Step 4: Let ( x , y ) ( x , y ) be the corner of the rectangle that lies in the first quadrant, as shown in Figure 4.68 . We can write length L = 2 x L = 2 x and width W = 2 y . W = 2 y . Since x 2 4 + y 2 = 1 x 2 4 + y 2 = 1 and y > 0 , y > 0 , we have y = 1 − x 2 4 . y = 1 − x 2 4 . Therefore, the area is

Step 5: From Figure 4.68 , we see that to inscribe a rectangle in the ellipse, the x x -coordinate of the corner in the first quadrant must satisfy 0 < x < 2 . 0 < x < 2 . Therefore, the problem reduces to looking for the maximum value of A ( x ) A ( x ) over the open interval ( 0 , 2 ) . ( 0 , 2 ) . Since A ( x ) A ( x ) will have an absolute maximum (and absolute minimum) over the closed interval [ 0 , 2 ] , [ 0 , 2 ] , we consider A ( x ) = 2 x 4 − x 2 A ( x ) = 2 x 4 − x 2 over the interval [ 0 , 2 ] . [ 0 , 2 ] . If the absolute maximum occurs at an interior point, then we have found an absolute maximum in the open interval.

Step 6: As mentioned earlier, A ( x ) A ( x ) is a continuous function over the closed, bounded interval [ 0 , 2 ] . [ 0 , 2 ] . Therefore, it has an absolute maximum (and absolute minimum). At the endpoints x = 0 x = 0 and x = 2 , x = 2 , A ( x ) = 0 . A ( x ) = 0 . For 0 < x < 2 , 0 < x < 2 , A ( x ) > 0 . A ( x ) > 0 . Therefore, the maximum must occur at a critical point. Taking the derivative of A ( x ) , A ( x ) , we obtain

To find critical points, we need to find where A ′ ( x ) = 0 . A ′ ( x ) = 0 . We can see that if x x is a solution of

then x x must satisfy

Therefore, x 2 = 2 . x 2 = 2 . Thus, x = ± 2 x = ± 2 are the possible solutions of Equation 4.7 . Since we are considering x x over the interval [ 0 , 2 ] , [ 0 , 2 ] , x = 2 x = 2 is a possibility for a critical point, but x = − 2 x = − 2 is not. Therefore, we check whether 2 2 is a solution of Equation 4.7 . Since x = 2 x = 2 is a solution of Equation 4.7 , we conclude that 2 2 is the only critical point of A ( x ) A ( x ) in the interval [ 0 , 2 ] . [ 0 , 2 ] . Therefore, A ( x ) A ( x ) must have an absolute maximum at the critical point x = 2 . x = 2 . To determine the dimensions of the rectangle, we need to find the length L L and the width W . W . If x = 2 x = 2 then

Therefore, the dimensions of the rectangle are L = 2 x = 2 2 L = 2 x = 2 2 and W = 2 y = 2 2 = 2 . W = 2 y = 2 2 = 2 . The area of this rectangle is A = L W = ( 2 2 ) ( 2 ) = 4 . A = L W = ( 2 2 ) ( 2 ) = 4 .

Checkpoint 4.35

Modify the area function A A if the rectangle is to be inscribed in the unit circle x 2 + y 2 = 1 . x 2 + y 2 = 1 . What is the domain of consideration?

Solving Optimization Problems when the Interval Is Not Closed or Is Unbounded

In the previous examples, we considered functions on closed, bounded domains. Consequently, by the extreme value theorem, we were guaranteed that the functions had absolute extrema. Let’s now consider functions for which the domain is neither closed nor bounded.

Many functions still have at least one absolute extrema, even if the domain is not closed or the domain is unbounded. For example, the function f ( x ) = x 2 + 4 f ( x ) = x 2 + 4 over ( − ∞ , ∞ ) ( − ∞ , ∞ ) has an absolute minimum of 4 4 at x = 0 . x = 0 . Therefore, we can still consider functions over unbounded domains or open intervals and determine whether they have any absolute extrema. In the next example, we try to minimize a function over an unbounded domain. We will see that, although the domain of consideration is ( 0 , ∞ ) , ( 0 , ∞ ) , the function has an absolute minimum.

In the following example, we look at constructing a box of least surface area with a prescribed volume. It is not difficult to show that for a closed-top box, by symmetry, among all boxes with a specified volume, a cube will have the smallest surface area. Consequently, we consider the modified problem of determining which open-topped box with a specified volume has the smallest surface area.

Example 4.37

Minimizing surface area.

A rectangular box with a square base, an open top, and a volume of 216 216 in. 3 is to be constructed. What should the dimensions of the box be to minimize the surface area of the box? What is the minimum surface area?

Step 1: Draw a rectangular box and introduce the variable x x to represent the length of each side of the square base; let y y represent the height of the box. Let S S denote the surface area of the open-top box.

Step 2: We need to minimize the surface area. Therefore, we need to minimize S . S .

Step 3: Since the box has an open top, we need only determine the area of the four vertical sides and the base. The area of each of the four vertical sides is x · y . x · y . The area of the base is x 2 . x 2 . Therefore, the surface area of the box is

Step 4: Since the volume of this box is x 2 y x 2 y and the volume is given as 216 in . 3 , 216 in . 3 , the constraint equation is

Solving the constraint equation for y , y , we have y = 216 x 2 . y = 216 x 2 . Therefore, we can write the surface area as a function of x x only:

Therefore, S ( x ) = 864 x + x 2 . S ( x ) = 864 x + x 2 .

Step 5: Since we are requiring that x 2 y = 216 , x 2 y = 216 , we cannot have x = 0 . x = 0 . Therefore, we need x > 0 . x > 0 . On the other hand, x x is allowed to have any positive value. Note that as x x becomes large, the height of the box y y becomes correspondingly small so that x 2 y = 216 . x 2 y = 216 . Similarly, as x x becomes small, the height of the box becomes correspondingly large. We conclude that the domain is the open, unbounded interval ( 0 , ∞ ) . ( 0 , ∞ ) . Note that, unlike the previous examples, we cannot reduce our problem to looking for an absolute maximum or absolute minimum over a closed, bounded interval. However, in the next step, we discover why this function must have an absolute minimum over the interval ( 0 , ∞ ) . ( 0 , ∞ ) .

Step 6: Note that as x → 0 + , x → 0 + , S ( x ) → ∞ . S ( x ) → ∞ . Also, as x → ∞ , x → ∞ , S ( x ) → ∞ . S ( x ) → ∞ . Since S S is a continuous function that approaches infinity at the ends, it must have an absolute minimum at some x ∈ ( 0 , ∞ ) . x ∈ ( 0 , ∞ ) . This minimum must occur at a critical point of S . S . The derivative is

Therefore, S ′ ( x ) = 0 S ′ ( x ) = 0 when 2 x = 864 x 2 . 2 x = 864 x 2 . Solving this equation for x , x , we obtain x 3 = 432 , x 3 = 432 , so x = 432 3 = 6 2 3 . x = 432 3 = 6 2 3 . Since this is the only critical point of S , S , the absolute minimum must occur at x = 6 2 3 x = 6 2 3 (see Figure 4.70 ). When x = 6 2 3 , x = 6 2 3 , y = 216 ( 6 2 3 ) 2 = 3 2 3 in . y = 216 ( 6 2 3 ) 2 = 3 2 3 in . Therefore, the dimensions of the box should be x = 6 2 3 in . x = 6 2 3 in . and y = 3 2 3 in . y = 3 2 3 in . With these dimensions, the surface area is

Checkpoint 4.36

Consider the same open-top box, which is to have volume 216 in . 3 . 216 in . 3 . Suppose the cost of the material for the base is 20 ¢ / in . 2 20 ¢ / in . 2 and the cost of the material for the sides is 30 ¢ / in . 2 30 ¢ / in . 2 and we are trying to minimize the cost of this box. Write the cost as a function of the side lengths of the base. (Let x x be the side length of the base and y y be the height of the box.)

Section 4.7 Exercises

For the following exercises, answer by proof, counterexample, or explanation.

When you find the maximum for an optimization problem, why do you need to check the sign of the derivative around the critical points?

Why do you need to check the endpoints for optimization problems?

True or False . For every continuous nonlinear function, you can find the value x x that maximizes the function.

True or False . For every continuous nonconstant function on a closed, finite domain, there exists at least one x x that minimizes or maximizes the function.

For the following exercises, set up and evaluate each optimization problem.

To carry a suitcase on an airplane, the length + width + + width + height of the box must be less than or equal to 62 in . 62 in . Assuming the base of the suitcase is square, show that the volume is V = h ( 31 − ( 1 2 ) h ) 2 . V = h ( 31 − ( 1 2 ) h ) 2 . What height allows you to have the largest volume?

You are constructing a cardboard box with the dimensions 2 m by 4 m . 2 m by 4 m . You then cut equal-size squares from each corner so you may fold the edges. What are the dimensions of the box with the largest volume?

Find the positive integer that minimizes the sum of the number and its reciprocal.

Find two positive integers such that their sum is 10 , 10 , and minimize and maximize the sum of their squares.

For the following exercises, consider the construction of a pen to enclose an area.

You have 400 ft 400 ft of fencing to construct a rectangular pen for cattle. What are the dimensions of the pen that maximize the area?

You have 800 ft 800 ft of fencing to make a pen for hogs. If you have a river on one side of your property, what is the dimension of the rectangular pen that maximizes the area?

You need to construct a fence around an area of 1600 ft 2 . 1600 ft 2 . What are the dimensions of the rectangular pen to minimize the amount of material needed?

Two poles are connected by a wire that is also connected to the ground. The first pole is 20 ft 20 ft tall and the second pole is 10 ft 10 ft tall. There is a distance of 30 ft 30 ft between the two poles. Where should the wire be anchored to the ground to minimize the amount of wire needed?

[T] You are moving into a new apartment and notice there is a corner where the hallway narrows from 8 ft to 6 ft . 8 ft to 6 ft . What is the length of the longest item that can be carried horizontally around the corner?

A patient’s pulse measures 70 bpm, 80 bpm, then 120 bpm . 70 bpm, 80 bpm, then 120 bpm . To determine an accurate measurement of pulse, the doctor wants to know what value minimizes the expression ( x − 70 ) 2 + ( x − 80 ) 2 + ( x − 120 ) 2 ? ( x − 70 ) 2 + ( x − 80 ) 2 + ( x − 120 ) 2 ? What value minimizes it?

In the previous problem, assume the patient was nervous during the third measurement, so we only weight that value half as much as the others. What is the value that minimizes ( x − 70 ) 2 + ( x − 80 ) 2 + 1 2 ( x − 120 ) 2 ? ( x − 70 ) 2 + ( x − 80 ) 2 + 1 2 ( x − 120 ) 2 ?

You can run at a speed of 6 6 mph and swim at a speed of 3 3 mph and are located on the shore, 4 4 miles east of an island that is 1 1 mile north of the shoreline. How far should you run west to minimize the time needed to reach the island?

For the following problems, consider a lifeguard at a circular pool with diameter 40 m . 40 m . He must reach someone who is drowning on the exact opposite side of the pool, at position C . C . The lifeguard swims with a speed v v and runs around the pool at speed w = 3 v . w = 3 v .

Find a function that measures the total amount of time it takes to reach the drowning person as a function of the swim angle, θ . θ .

Find at what angle θ θ the lifeguard should swim to reach the drowning person in the least amount of time.

A truck uses gas as g ( v ) = a v + b v , g ( v ) = a v + b v , where v v represents the speed of the truck and g g represents the gallons of fuel per mile. Assuming a a and b b are positive, at what speed is fuel consumption minimized?

For the following exercises, consider a limousine that gets m ( v ) = ( 120 − 2 v ) 5 mi/gal m ( v ) = ( 120 − 2 v ) 5 mi/gal at speed v , v , the chauffeur costs $15/h , $15/h , and gas is $ 3.5 / gal . $ 3.5 / gal .

Find the cost per mile at speed v . v .

Find the cheapest driving speed.

For the following exercises, consider a pizzeria that sell pizzas for a revenue of R ( x ) = a x R ( x ) = a x and costs C ( x ) = b + c x + d x 2 , C ( x ) = b + c x + d x 2 , where x x represents the number of pizzas ;   a   >   c ;   a   >   c .

Find the profit function for the number of pizzas. How many pizzas gives the largest profit per pizza?

Assume that R ( x ) = 10 x R ( x ) = 10 x and C ( x ) = 2 x + x 2 . C ( x ) = 2 x + x 2 . How many pizzas sold maximizes the profit?

Assume that R ( x ) = 15 x , R ( x ) = 15 x , and C ( x ) = 60 + 3 x + 1 2 x 2 . C ( x ) = 60 + 3 x + 1 2 x 2 . How many pizzas sold maximizes the profit?

For the following exercises, consider a wire 4 ft 4 ft long cut into two pieces. One piece forms a circle with radius r r and the other forms a square of side x . x .

Choose x x to maximize the sum of their areas.

Choose x x to minimize the sum of their areas.

For the following exercises, consider two nonnegative numbers x x and y y such that x + y = 10 . x + y = 10 . Maximize and minimize the quantities.

x 2 y 2 x 2 y 2

y − 1 x y − 1 x

x 2 − y x 2 − y

For the following exercises, draw the given optimization problem and solve.

Find the volume of the largest right circular cylinder that fits in a sphere of radius 1 . 1 .

Find the volume of the largest right cone that fits in a sphere of radius 1 . 1 .

Find the area of the largest rectangle that fits into the triangle with sides x = 0 , y = 0 x = 0 , y = 0 and x 4 + y 6 = 1 . x 4 + y 6 = 1 .

Find the largest volume of a cylinder that fits into a cone that has base radius R R and height h . h .

Find the dimensions of the closed cylinder volume V = 16 π V = 16 π that has the least amount of surface area.

Find the dimensions of a right cone with surface area S = 4 π S = 4 π that has the largest volume.

For the following exercises, consider the points on the given graphs. Use a calculator to graph the functions.

[T] Where is the line y = 5 − 2 x y = 5 − 2 x closest to the origin?

[T] Where is the line y = 5 − 2 x y = 5 − 2 x closest to point ( 1 , 1 ) ? ( 1 , 1 ) ?

[T] Where is the parabola y = x 2 y = x 2 closest to point ( 2 , 0 ) ? ( 2 , 0 ) ?

[T] Where is the parabola y = x 2 y = x 2 closest to point ( 0 , 3 ) ? ( 0 , 3 ) ?

For the following exercises, set up, but do not evaluate, each optimization problem.

A window is composed of a semicircle placed on top of a rectangle. If you have 20 ft 20 ft of window-framing materials for the outer frame, what is the maximum size of the window you can create? Use r r to represent the radius of the semicircle.

You have a garden row of 20 20 watermelon plants that produce an average of 30 30 watermelons apiece. For any additional watermelon plants planted, the output per watermelon plant drops by one watermelon. How many extra watermelon plants should you plant?

You are constructing a box for your cat to sleep in. The plush material for the square bottom of the box costs $ 5 / ft 2 $ 5 / ft 2 and the material for the sides costs $ 2 / ft 2 . $ 2 / ft 2 . You need a box with volume 4 ft 3 . 4 ft 3 . Find the dimensions of the box that minimize cost. Use x x to represent the length of the side of the box.

You are building five identical pens adjacent to each other with a total area of 1000 m 2 , 1000 m 2 , as shown in the following figure. What dimensions should you use to minimize the amount of fencing?

You are the manager of an apartment complex with 50 50 units. When you set rent at $ 800 / month, $ 800 / month, all apartments are rented. As you increase rent by $ 25 / month, $ 25 / month, one fewer apartment is rented. Maintenance costs run $ 50 / month $ 50 / month for each occupied unit. What is the rent that maximizes the total amount of profit?

As an Amazon Associate we earn from qualifying purchases.

This book may not be used in the training of large language models or otherwise be ingested into large language models or generative AI offerings without OpenStax's permission.

Want to cite, share, or modify this book? This book uses the Creative Commons Attribution-NonCommercial-ShareAlike License and you must attribute OpenStax.

Access for free at https://openstax.org/books/calculus-volume-1/pages/1-introduction

• Authors: Gilbert Strang, Edwin “Jed” Herman
• Publisher/website: OpenStax
• Book title: Calculus Volume 1
• Publication date: Mar 30, 2016
• Location: Houston, Texas
• Book URL: https://openstax.org/books/calculus-volume-1/pages/1-introduction
• Section URL: https://openstax.org/books/calculus-volume-1/pages/4-7-applied-optimization-problems

© Feb 5, 2024 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike License . The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.

Assignment problem: Hungarian method 3

Assignment problem: Hungarian Method Nui Ruppert (Mtk_Nr.: 373224) David Lenh (Mtk_Nr.: 368343) Amir Farshchi Tabrizi (Mtk-Nr.: 372894)

In this OR-Wiki entry we're going to explain the Hungarian method with 3 examples. In the first example you'll find the optimal solution after a few steps with the help of the reduced matrix. The second example illustrates a complex case where you need to proceed all the steps of the algorithm to get to an optimal solution. Finally in the third example we will show how to solve a maximization problem with the Hungarian method.

Inhaltsverzeichnis

• 1 Introduction
• 2 Example 1 – Minimization problem
• 3 Example 2 – Minimazation problem
• 4 Example 3 – Maximization problem
• 6 References

Introduction

The Hungarian method is a combinatorial optimization algorithm which was developed and published by Harold Kuhn in 1955. This method was originally invented for the best assignment of a set of persons to a set of jobs. It is a special case of the transportation problem. The algorithm finds an optimal assignment for a given “n x n” cost matrix. “Assignment problems deal with the question how to assign n items (e.g. jobs) to n machines (or workers) in the best possible way. […] Mathematically an assignment is nothing else than a bijective mapping of a finite set into itself […]” [1]

The assignment constraints are mathematically defined as:

To make clear how to solve an assignment problem with the Hungarian algorithm we will show you the different cases with several examples which can occur .

Example 1 – Minimization problem

In this example we have to assign 4 workers to 4 machines. Each worker causes different costs for the machines. Your goal is to minimize the total cost to the condition that each machine goes to exactly 1 person and each person works at exactly 1 machine. For comprehension: Worker 1 causes a cost of 6 for machine 1 and so on …

To solve the problem we have to perform the following steps:

Step 1 – Subtract the row minimum from each row.

Step 2 – Subtract the column minimum from each column from the reduced matrix.

The idea behind these 2 steps is to simplify the matrix since the solution of the reduced matrix will be exactly the same as of the original matrix.

Step 3 – Assign one “0” to each row & column.

Now that we have simplified the matrix we can assign each worker with the minimal cost to each machine which is represented by a “0”.

- In the first row we have one assignable “0” therefore we assign it to worker 3 .

- In the second row we also only have one assignable “0” therefore we assign it to worker 4 .

- In the third row we have two assignable “0”. We leave it as it is for now.

- In the fourth row we have one assignable “0” therefore we assign it. Consider that we can only assign each worker to each machine hence we can’t allocate any other “0” in the first column.

- Now we go back to the third row which now only has one assignable “0” for worker 2 .

As soon as we can assign each worker to one machine, we have the optimal solution . In this case there is no need to proceed any further steps. Remember also, if we decide on an arbitrary order in which we start allocating the “0”s then we may get into a situation where we have 3 assignments as against the possible 4. If we assign a “0” in the third row to worker 1 we wouldn’t be able to allocate any “0”s in column one and row two.

The rule to assign the “0”:

- If there is an assignable “0”, only 1 assignable “0” in any row or any column, assign it.

- If there are more than 1, leave it and proceed.

This rule would try to give us as many assignments as possible.

Now there are also cases where you won’t get an optimal solution for a reduced matrix after one iteration. The following example will explain it.

Example 2 – Minimazation problem

In this example we have the fastest taxi company that has to assign each taxi to each passenger as fast as possible. The numbers in the matrix represent the time to reach the passenger.

We proceed as in the first example.

Iteration 1:

Now we have to assign the “0”s for every row respectively to the rule that we described earlier in example 1.

- In the first row we have one assignable “0” therefore we assign it and no other allocation in column 2 is possible.

- In the second row we have one assignable “0” therefore we assign it.

- In the third row we have several assignable “0”s. We leave it as it is for now and proceed.

- In the fourth and fifth row we have no assignable “0”s.

Now we proceed with the allocations of the “0”s for each column .

- In the first column we have one assignable “0” therefore we assign it. No other “0”s in row 3 are assignable anymore.

Now we are unable to proceed because all the “0”s either been assigned or crossed. The crosses indicate that they are not fit for assignments because assignments are already made.

We realize that we have 3 assignments for this 5x5 matrix. In the earlier example we were able to get 4 assignments for a 4x4 matrix. Now we have to follow another procedure to get the remaining 2 assignments (“0”).

Step 4 – Tick all unassigned rows.

Step 5 – If a row is ticked and has a “0”, then tick the corresponding column (if the column is not yet ticked).

Step 6 – If a column is ticked and has an assignment, then tick the corresponding row (if the row is not yet ticked).

Step 7 - Repeat step 5 and 6 till no more ticking is possible.

In this case there is no more ticking possible and we proceed with the next step.

Step 8 – Draw lines through unticked rows and ticked columns. The number of lines represents the maximum number of assignments possible.

Step 9 – Find out the smallest number which does not have any line passing through it. We call it Theta. Subtract theta from all the numbers that do not have any lines passing through them and add theta to all those numbers that have two lines passing through them. Keep the rest of them the same.

(With this step we create a new “0”)

With the new assignment matrix we start to assign the “0”s after the explained rules. Nevertheless we have 4 assignments against the required 5 for an optimal solution. Therefore we have to repeat step 4 – 9.

Iteration 2:

Step 4 – Tick all unassigned row.

Note: The indices of the ticks show you the order we added them.

Iteration 3:

Iteration 4:

After the fourth iteration we assign the “0”s again and now we have an optimal solution with 5 assignments.

The solution:

- Taxi1 => Passenger1 - duration 12

- Taxi2 => Passenger4 - duration 11

- Taxi3 => Passenger2 - duration 8

- Taxi4 => Passenger3 - duration 14

- Taxi5 => Passenger5 - duration 11

If we define the needed duration as costs, the minimal cost for this problem is 56.

Example 3 – Maximization problem

Furthermore the Hungarian algorithm can also be used for a maximization problem in which case we first have to transform the matrix. For example a company wants to assign different workers to different machines. Each worker is more or less efficient with each machine. The efficiency can be defined as profit. The higher the number, the higher the profit.

As you can see, the maximal profit of the matrix is 13. The simple twist that we do is rather than try to maximize the profit, we’re going to try to minimize the profit that you don’t get. If every value is taken away from 13, then we can minimize the amount of profit lost. We receive the following matrix:

From now on we proceed as usual with the steps to get to an optimal solution.

With the determined optimal solution we can compute the maximal profit:

- Worker1 => Machine2 - 9

- Worker2 => Machine4 - 11

- Worker3 => Machine3 - 13

- Worker4 => Machine1 - 7

Maximal profit is 40.

The optimal solution is found if there is one assigned “0” for each row and each column.

[1] Linear Assignment Problems and Extensions, Rainer E. Burkard, Eranda Cela

[2] Operations Research Skript TU Kaiserslautern, Prof. Dr. Oliver Wendt

[3] The Hungarian method for the assignment problem, H. W. Kuhn, Bryn Mawr College

Fundamental of Operations Research, Lec. 16, Prof. G. Srinivasan

Navigationsmenü

• Quelltext anzeigen
• Versionsgeschichte

Meine Werkzeuge

• Gemeinschaftsportal
• Operations Research
• Studentenbeiträge zum Thema Operations Research
• Wirtschaftsinformatik
• Aktuelle Ereignisse
• Letzte Änderungen
• Zufällige Seite
• Links auf diese Seite
• Änderungen an verlinkten Seiten
• Spezialseiten
• Druckversion
• Permanenter Link
• Seiten­informationen

• Diese Seite wurde zuletzt am 1. Juli 2013 um 11:03 Uhr geändert.
• Datenschutz
• Über Operations-Research-Wiki

2. Algorithm & Example-1

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

• MapReduce Algorithm
• Linear Programming using Pyomo
• Networking and Professional Development for Machine Learning Careers in the USA
• Predicting Employee Churn in Python
• Airflow Operators

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

Understanding Random Forest Classification and Building a Model in Python

Pandas map() and reduce() Operations

Data Visualization using Matplotlib

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons

Margin Size

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

7.1.1: Maximization (Exercises)

• Last updated
• Save as PDF
• Page ID 82135

• 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}}}} \)

For the following maximization problems, choose your variables, write the objective function and the constraints, graph the constraints, shade the feasibility region, label all critical points, and determine the solution that optimizes the objective function.

1) A farmer has 100 acres of land on which she plans to grow wheat and corn. Each acre of wheat requires 4 hours of labor and $20 of capital, and each acre of corn requires 16 hours of labor and $40 of capital. The farmer has at most 800 hours of labor and $2400 of capital available. If the profit from an acre of wheat is $80 and from an acre of corn is $100, how many acres of each crop should she plant to maximize her profit?

2) Mr. Tran has $24,000 to invest, some in bonds and the rest in stocks. He has decided that the money invested in bonds must be at least twice as much as that in stocks. But the money invested in bonds must not be greater than $18,000. If the bonds earn 6%, and the stocks earn 8%, how much money should he invest in each to maximize profit?

3) A factory manufactures chairs and tables, each requiring the use of three operations: Cutting, Assembly, and Finishing. The first operation can be used at most 40 hours; the second at most 42 hours; and the third at most 25 hours. A chair requires 1 hour of cutting, 2 hours of assembly, and 1 hour of finishing; a table needs 2 hours of cutting, 1 hour of assembly, and 1 hour of finishing. If the profit is $20 per unit for a chair and $30 for a table, how many units of each should be manufactured to maximize revenue?

4) The Silly Nut Company makes two mixtures of nuts: Mixture A and Mixture B. A pound of Mixture A contains 12 oz of peanuts, 3 oz of almonds and 1 oz of cashews and sells for $4. A pound of Mixture B contains 12 oz of peanuts, 2 oz of almonds and 2 oz of cashews and sells for $5. The company has 1080 lb. of peanuts, 240 lb. of almonds, 160 lb. of cashews. How many pounds of each of mixtures A and B should the company make to maximize profit? (Hint: Use consistent units. Work the entire problem in pounds by converting all values given in ounces into fractions of pounds).

5) \[\begin{array}{lc} \text { Maximize: } &Z=4 x+10 y \\ \text { Subject to: } & x+y \leq 5 \\ & 2 x+y \leq 8 \\ & x+2 y \leq 8 \\ & x \geq 0, y \geq 0 \end{array}\nonumber \]

6) This maximization linear programming problem is not in “standard” form. It has mixed constraints, some involving ≤ inequalities and some involving ≥ inequalities. However with careful graphing, we can solve this using the techniques we have learned in this section.

\[\begin{array}{ll} \text { Maximize: } &Z=5 x+7 y \\ \text { Subject to: } & x+y \leq 30 \\ & 2 x+y \leq 50 \\ & 4 x+3 y \geq 60 \\ & 2 x \geq y \\ & x \geq 0, y \geq 0 \end{array} \nonumber \]