define balanced and unbalanced assignment problem

Assignment Problem: Meaning, Methods and Variations | Operations Research

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

Meaning of Assignment Problem:

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

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

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

Definition of Assignment Problem:

ADVERTISEMENTS:

Suppose there are n jobs to be performed and n persons are available for doing these jobs. Assume that each person can do each job at a term, though with varying degree of efficiency, let c ij be the cost if the i-th person is assigned to the j-th job. The problem is to find an assignment (which job should be assigned to which person one on-one basis) So that the total cost of performing all jobs is minimum, problem of this kind are known as assignment problem.

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

Thus, one can obtain the contraints for the Linear Programming Problem by considering each agent/task in turn:

As each agent is assigned to exactly one job, we can deduce:

Similarly, since each job is assigned to exactly one agent, one can deduce:

The obtain the objective function for this example, we must consider the total costs.

The means, therefore, that the objection function, Z , for this example is to minimise Z where:

Finally, this means that one can conclude the LPP to be:

Minimise Z, where Z = 15 x {\displaystyle x} A1 + {\displaystyle +} 10 x {\displaystyle x} A2 + {\displaystyle +} 12 x {\displaystyle x} A3 + {\displaystyle +} 10 x {\displaystyle x} B1 + {\displaystyle +} 7 x {\displaystyle x} B2 + {\displaystyle +} 11 x {\displaystyle x} B3 + {\displaystyle +} 15 x {\displaystyle x} C1 + {\displaystyle +} 6 x {\displaystyle x} C2 + {\displaystyle +} 9 x {\displaystyle x} C3 , subject to: x {\displaystyle x} A1 + x {\displaystyle x} A2 + x {\displaystyle x} A3 = 1 x {\displaystyle x} B1 + x {\displaystyle x} B2 + x {\displaystyle x} B3 = 1 x {\displaystyle x} C1 + x {\displaystyle x} C2 + x {\displaystyle x} C3 = 1 x {\displaystyle x} A1 + x {\displaystyle x} B1 + x {\displaystyle x} C1 = 1 x {\displaystyle x} A2 + x {\displaystyle x} B2 + x {\displaystyle x} C2 = 1 x {\displaystyle x} A3 + x {\displaystyle x} B3 + x {\displaystyle x} C3 = 1

Solution of the Balanced Assignment Problem [ edit | edit source ]

An algorithm was developed by Harold Kuhn in the 1950s, and was named the Hungarian Algorithm. Its name is a reference to Dénes Kőnig and Jenő Egerváry, a pair of prominent Hungarian Mathematicians whose techniques are applied in this algorithm.

The Hungarian Algorithm [ edit | edit source ]

For the Hungarian Algorithm to work, the assignment problem must meet the following criteria:

• Each worker must be assigned, as we previously saw, to exactly one job.
• Each job must be assigned to exactly one worker.
• In the cost matrix, a constant can be added or subtracted from all cost values in any row or column without having any effect on the optimal assignments.

There are three stages in the implementation of the Hungarian Algorithm:

• Find the opportunity cost matrix
• Test for an optimal assignment. If one can be made, use it and stop.
• If an optimal assignment cannot be made, revise the opportunity cost matrix and return to the previous step.

To demonstrate these three steps, let us consider again the lorry example:

Finding the Opportunity Cost Matrix [ edit | edit source ]

The Opportunity Cost Matrix (OCM) is essentially a modified version of our initial Cost Matrix. In order to change the Cost Matrix into the OCM, one must carry out two stages.

• Carry out row reduction
• Carry out column reduction

Row reduction is the operation in which the smallest number in each row is subtracted from every number in that row. With our earlier example:

Next, one completes the column reduction. This is the same as row reduction, only with the smallest number in each column being subtracted from each value within that column. Thus:

Thus, the completed Opportunity Cost Matrix is:

Interpreting The Opportunity Cost Matrix [ edit | edit source ]

Since the aim of an assignment problem is to assign exactly one agent to exactly one task, one must match each agent up to the task which best minimises overall cost. After completing the row reduction and column reduction, it is logical to assume that the values that remain in the table are the minimum possible. Similarly, since the values in the table are the cost-values, the lowest values in the table are, surely, those of lowest cost. In order to find a solution, one must select one zero from each row and one zero from each column. However, one cannot select more than one value from any row or column, as it will result in one agent/task being assigned twice, which cannot occur in an Assignment Problem.

Again, let's consider the earlier example. If we were to select one zero from each column/row without any doubles occurring, the only possible solution is (with selected costs marked by asterices):

If we then assign this solution to our original cost matrix, one can see the following:

Thus, the final assignment is:

It is interesting to see that, despite this being the cheapest solution, it doesn't actually utilise all of the lowest values within the table.

Optimality of a Solution [ edit | edit source ]

An important issue with AP is the optimality of solution - when one obtains a solution, how can one be sure it truly is the best solution available? With the Hungarian algorithm, there is a fairly straightforward test for optimality that concerns drawing lines through the zeros in the Opportunity Cost Matrix. If the number of lines (horizontal and vertical only) is equal to the number of rows/columns, the solution obtained is optimal. If, however, the number of lines needed does not equal the number of rows/columns, the solution is not optimal, and can be improved. This is a somewhat perplexing technique, but one that is straightforward to implement and clear to interpret.

Consider the following OCM:

It is fairly easy to see that it would require only two lines to draw through all of the zeros - one could use a horizontal line through row B, and a vertical line through column 2, for instance. 2≠3 (the number of rows/columns), thus an optimal solution cannot be made.

Consider, on the other hand, our lorry example. Is the solution that we obtained optimal?

One can see that, in order to strike through each zero, one would need three lines (for instance, one through column 2, one through row B and one through row A). 3 = 3, thus we have an optimal solution that cannot be improved upon.

Revision of the Opportunity Cost Matrix [ edit | edit source ]

In the event of achieving a non-optimal assignment, one must revise the OCM. There are several steps in this process:

• Check the costs uncovered by the drawn lines
• Identify the smallest uncovered value
• Subtract this value from all of the uncovered costs
• Add this value to any costs that are at the intersection of any two drawn lines

Take our non-optimal solution from earlier. The smallest uncovered value was one. Subtracting one from each uncovered value gives:

Adding one to the point of intersection of the two lines (in this example, one could have drawn them through row B and column 2, therefore the point of intersection is cell B2) gives:

Again, only two lines (this time, they must be through row A and column 3) are needed. They intersect at cell A3. The smallest uncovered value is, again, 1. So, subtracting one from each uncovered cell and adding one to cell A3 gives:

Finally, the minimum number of lines needed to draw through all of the zeros is 3, which is the number of rows/columns. This means any assignment made will be optimal.

Solutions of Unbalanced Assignment Problems [ edit | edit source ]

The definition of a balanced AP was one in which the number of agents was the same as the number of tasks. In reality, this is unlikely to be the case - that is, it is unlikely that one would have the same number of taxi drivers to the number of customers, for example. In the event of an unbalanced problem, one must add a dummy , which is a blank/empty row, added to the Cost Matrix, in order to 'balance' the rows, for the sake of the algorithm. If one had, for instance, three agents and four tasks, one would add a dummy row . On the other hand, if one had four agents and three tasks, one would add a dummy task . This helps as it means that one agent or task will be left without a 'real' assignment, as using them would increase the total cost of the assignment.

Consider the following example:

A taxi company has four drivers (A, B, C, D), each currently at different locations. Three customers (1, 2, 3) have called the taxi company and need to be driven to their destinations. The total distance that would be travelled, by the driver, is represented in the cost matrix below:

The Taxi Company wishes to minimise the total distance travelled by its drivers. Find an optimal solution to this Assignment Problem.

Solution: Initially, one must add a dummy column, in order to make this a 'balanced' problem. Let this column be called "Row 4". Since there isn't actually a fourth customer, all of the costs in this matrix will be zero. This will mean that the otherwise most expensive taxi in the matrix will result in being assigned the dummy - in other words, it won't be used in the problem. First, let's carry out row and column reduction: Cost Matrix with Row Minima 1 2 3 4 Row Minimum A 11 19 17 0 0 C 15 18 21 0 0 D 18 15 17 0 0 ... with Column Minima 1 2 3 4 A 11 19 17 0 B 21 15 13 0 C 15 18 21 0 D 18 15 17 0 Column Minimum 11 15 13 0 Opportunity Cost Matrix 1 2 3 4 A 0 4 4 0 B 10 0 0 0 C 4 3 8 0 D 7 4 0 0 As one can see, all of the zeros in the Opportunity Cost Matrix can only be struck through using 4 lines (for instance, 1 line vertically through Column 4, 3 lines horizontally through Rows A, B & D). Thus, we've already arrived at the optimal solution because 4 lines can be used to mark through the entire matrix. The only possible solution is: A → 1 B → 3 C → 2 D → 4* Z = 11 + 13 + 18 = 42

• Of course, customer 4 is in fact a 'dummy' - i.e., D doesn't actually transport any customer. Thus, the only three drivers needed are drivers A, B and C. Driver A will transport Passenger 1, Driver B will transport Passenger 3 and Driver C will transport Passenger 2.

Maximisation Problems [ edit | edit source ]

All of the examples that have been considered so far have been Minimisation problems - in other words, they've been ones in which the aim of the problem was to minimise a cost. Assignment problems can, however, be used for the opposite reason - to maximise a gain or a profit. Consider the example of ice-cream seller. They know that, in certain towns, they will sell more icecream than others. The day, too, changes how much ice-cream s/he sells - they only drive the van on Monday, Wednesday and Saturday (M, W and S respectively). Taking into account that the ice-cream van can only visit one town at a time, which town should the ice-cream van visit on which day, in order to maximise his/her profit.

The following cost-matrix represents the earnings (in £100s) for each town (A, B, C) on each day (M, W, S):

After completing this process for the whole matrix, we achieve the following:

We can now carry out row and column reduction, as we usually would. This, eventually, results in the following Opportunity Cost Matrix:

Since the smallest number of lines that can be used to strike-through each of the zeros in this matrix is 3 (which is equal to the number of rows/columns), an optimal assignment can be made. The only possible assignment is:

On the cost matrix, this gives us:

This means that:

The total profit gives:

Thus the maximum total profit of the ice-cream van is £3500.

• Book:A-level Mathematics

Navigation menu

Unbalanced Assignment Problem

In the previous section, the number of persons and the number of jobs were assumed to be the same. In this section, we remove this assumption and consider a situation where the number of persons is not equal to the number of jobs . In all such cases, fictitious rows and/or columns are added in the matrix to make it a square matrix.

• Maximization Problem
• Multiple Optimal Solutions

Example: Unbalanced Assignment Problem

Since the number of persons is less than the number of jobs, we introduce a dummy person (D) with zero values. The revised assignment problem is given below:

Use Horizontal Scrollbar to View Full Table Calculation.

Now use the Hungarian method to obtain the optimal solution yourself. Ans. = 20 + 17 + 17 + 0 = 54.

Share and Recommend

Operations Research Simplified Back Next

Goal programming Linear programming Simplex Method Transportation Problem

Nash Balanced Assignment Problem

• Conference paper
• First Online: 21 November 2022
• Cite this conference paper

• Minh Hieu Nguyen 11 ,
• Mourad Baiou 11 &
• Viet Hung Nguyen 11  

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13526))

Included in the following conference series:

• International Symposium on Combinatorial Optimization

349 Accesses

2 Citations

In this paper, we consider a variant of the classic Assignment Problem (AP), called the Balanced Assignment Problem (BAP) [ 2 ]. The BAP seeks to find an assignment solution which has the smallest value of max-min distance : the difference between the maximum assignment cost and the minimum one. However, by minimizing only the max-min distance, the total cost of the BAP solution is neglected and it may lead to an inefficient solution in terms of total cost. Hence, we propose a fair way based on Nash equilibrium [ 1 , 3 , 4 ] to inject the total cost into the objective function of the BAP for finding assignment solutions having a better trade-off between the two objectives: the first aims at minimizing the total cost and the second aims at minimizing the max-min distance. For this purpose, we introduce the concept of Nash Fairness (NF) solutions based on the definition of proportional-fair scheduling adapted in the context of the AP: a transfer of utilities between the total cost and the max-min distance is considered to be fair if the percentage increase in the total cost is smaller than the percentage decrease in the max-min distance and vice versa.

We first show the existence of a NF solution for the AP which is exactly the optimal solution minimizing the product of the total cost and the max-min distance. However, finding such a solution may be difficult as it requires to minimize a concave function. The main result of this paper is to show that finding all NF solutions can be done in polynomial time. For that, we propose a Newton-based iterative algorithm converging to NF solutions in polynomial time. It consists in optimizing a sequence of linear combinations of the two objective based on Weighted Sum Method [ 5 ]. Computational results on various instances of the AP are presented and commented.

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

Access this chapter

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

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Bertsimas, D., Farias, V.F., Trichakis, N.: The price of fairness. Oper. Res. January–February 59 (1), 17–31 (2011)

MathSciNet   MATH   Google Scholar  

Martello, S., Pulleyblank, W.R., Toth, P., De Werra, D.: Balanced optimization problems. Oper. Res. Lett. 3 (5), 275–278 (1984)

Article   MathSciNet   MATH   Google Scholar  

Kelly, F.P., Maullo, A.K., Tan, D.K.H.: Rate control for communication networks: shadow prices, proportional fairness and stability. J. Oper. Res. Soc. 49 (3), 237–252 (1997). https://doi.org/10.1057/palgrave.jors.2600523

Article   Google Scholar  

Ogryczak, W., Luss, H., Pioro, M., Nace, D., Tomaszewski, A.: Fair optimization and networks: a survey. J. Appl. Math. 2014 , 1–26 (2014)

Marler, R.T., Arora, J.S.: The weighted sum method for multi-objective optimization: new insights. Struct. Multi. Optim. 41 (6), 853–862 (2010)

Heller, I., Tompkins, C.B.: An extension of a theorem of Dantzig’s. Ann. Math. Stud. (38), 247–254 (1956)

Google Scholar  

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

Martello, S.: Most and least uniform spanning trees. Discrete Appl. Math. 15 (2), 181–197 (1986)

Beasley, J.E.: Linear programming on Clay supercomputer. J. Oper. Res. Soc. 41 , 133–139 (1990)

Nguyen, M.H, Baiou, M., Nguyen, V.H., Vo, T.Q.T.: Nash fairness solutions for balanced TSP. In: International Network Optimization Conference (INOC2022) (2022)

Download references

Author information

Authors and affiliations.

INP Clermont Auvergne, Univ Clermont Auvergne, Mines Saint-Etienne, CNRS, UMR 6158 LIMOS, 1 Rue de la Chebarde, Aubiere Cedex, France

Minh Hieu Nguyen, Mourad Baiou & Viet Hung Nguyen

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Viet Hung Nguyen .

Editor information

Editors and affiliations.

ESSEC Business School of Paris, Cergy Pontoise Cedex, France

Ivana Ljubić

IBM TJ Watson Research Center, Yorktown Heights, NY, USA

Francisco Barahona

Georgia Institute of Technology, Atlanta, GA, USA

Santanu S. Dey

Université Paris-Dauphine, Paris, France

A. Ridha Mahjoub

Proposition 1 . There may be more than one NF solution for the AP.

Let us illustrate this by an instance of the AP having the following cost matrix

By verifying all feasible assignment solutions in this instance, we obtain easily three assignment solutions \((1-1, 2-2, 3-3), (1-2, 2-3, 3-1)\) , \((1-3, 2-2, 3-1)\) and \((1-3, 2-1, 3-2)\) corresponding to 4 NF solutions (280, 36), (320, 32), (340, 30) and (364, 28). Note that \(i-j\) where \(1 \le i,j \le 3\) represents the assignment between worker i and job j in the solution of this instance.     \(\square \)

We recall below the proofs of some recent results that we have published in [ 10 ]. They are needed to prove the new results presented in this paper.

Theorem 2 [ 10 ] . \((P^{*},Q^{*}) = {{\,\mathrm{arg\,min}\,}}_{(P,Q) \in \mathcal {S}} PQ\) is a NF solution.

Obviously, there always exists a solution \((P^{*},Q^{*}) \in \mathcal {S}\) such that

Now \(\forall (P',Q') \in \mathcal {S}\) we have \(P'Q' \ge P^{*}Q^{*}\) . Then

The first inequality holds by the Cauchy-Schwarz inequality.

Hence, \((P^{*},Q^{*})\) is a NF solution.     \(\square \)

Theorem 3 [ 10 ] . \((P^{*},Q^{*}) \in \mathcal {S}\) is a NF solution if and only if \((P^{*},Q^{*})\) is an optimal solution of \(\mathcal {P(\alpha ^{*})}\) where \(\alpha ^{*} = \frac{Q^{*}}{P^{*}}\) .

Firstly, let \((P^{*},Q^{*})\) be a NF solution and \(\alpha ^{*} = \frac{Q^{*}}{P^{*}}\) . We will show that \((P^{*},Q^{*})\) is an optimal solution of \(\mathcal {P(\alpha ^{*})}\) .

Since \((P^{*},Q^{*})\) is a NF solution, we have

Since \(\alpha ^{*} = \frac{Q^{*}}{P^{*}}\) , we have \(\alpha ^{*}P^{*}+Q^{*} = 2Q^{*}\) .

Dividing two sides of ( 6 ) by \(P^{*} > 0\) we obtain

So we deduce from ( 7 )

Hence, \((P^{*},Q^{*})\) is an optimal solution of \(\mathcal {P}(\alpha ^{*})\) .

Now suppose \(\alpha ^{*} = \frac{Q^{*}}{P^{*}}\) and \((P^{*},Q^{*})\) is an optimal solution of \(\mathcal {P}(\alpha ^{*})\) , we show that \((P^{*},Q^{*})\) is a NF solution.

If \((P^{*},Q^{*})\) is not a NF solution, there exists a solution \((P',Q') \in \mathcal {S}\) such that

We have then

which contradicts the optimality of \((P^{*},Q^{*})\) .     \(\square \)

Lemma 3 [ 10 ] . Let \(\alpha , \alpha ' \in \mathbb {R}_+\) and \((P_{\alpha }, Q_{\alpha })\) , \((P_{\alpha '}, Q_{\alpha '})\) be the optimal solutions of \(\mathcal {P(\alpha )}\) and \(\mathcal {P(\alpha ')}\) respectively, if \(\alpha \le \alpha '\) then \(P_{\alpha } \ge P_{\alpha '}\) and \(Q_{\alpha } \le Q_{\alpha '}\) .

The optimality of \((P_{\alpha }, Q_{\alpha })\) and \((P_{\alpha '}, Q_{\alpha '})\) gives

By adding both sides of ( 8a ) and ( 8b ), we obtain \((\alpha - \alpha ') (P_{\alpha } - P_{\alpha '}) \le 0\) . Since \(\alpha \le \alpha '\) , it follows that \(P_{\alpha } \ge P_{\alpha '}\) .

On the other hand, inequality ( 8a ) implies \(Q_{\alpha '} - Q_{\alpha } \ge \alpha (P_{\alpha } - P_{\alpha '}) \ge 0\) that leads to \(Q_{\alpha } \le Q_{\alpha '}\) .     \(\square \)

Lemma 4 [ 10 ] . During the execution of Procedure Find ( \(\alpha _{0})\) in Algorithm 1 , \(\alpha _{i} \in [0,1], \, \forall i \ge 1\) . Moreover, if \(T_{0} \ge 0\) then the sequence \(\{\alpha _i\}\) is non-increasing and \(T_{i} \ge 0, \, \forall i \ge 0\) . Otherwise, if \(T_{0} \le 0\) then the sequence \(\{\alpha _i\}\) is non-decreasing and \(T_{i} \le 0, \, \forall i \ge 0\) .

Since \(P \ge Q \ge 0, \, \forall (P, Q) \in \mathcal {S}\) , it follows that \(\alpha _{i+1} = \frac{Q_i}{P_i} \in [0,1], \, \forall i \ge 0\) .

We first consider \(T_{0} \ge 0\) . We proof \(\alpha _i \ge \alpha _{i+1}, \, \forall i \ge 0\) by induction on i . For \(i = 0\) , we have \(T_{0} = \alpha _{0} P_{0} - Q_{0} = P_{0}(\alpha _{0}-\alpha _{1}) \ge 0\) , it follows that \(\alpha _{0} \ge \alpha _{1}\) . Suppose that our hypothesis is true until \(i = k \ge 0\) , we will prove that it is also true with \(i = k+1\) .

Indeed, we have

The inductive hypothesis gives \(\alpha _k \ge \alpha _{k+1}\) that implies \(P_{k+1} \ge P_k > 0\) and \(Q_{k} \ge Q_{k+1} \ge 0\) according to Lemma 3 . It leads to \(Q_{k}P_{k+1} - P_{k}Q_{k+1} \ge 0\) and then \(\alpha _{k+1} - \alpha _{k+2} \ge 0\) .

Hence, we have \(\alpha _{i} \ge \alpha _{i+1}, \, \forall i \ge 0\) .

Consequently, \(T_{i} = \alpha _{i}P_{i} - Q_{i} = P_{i}(\alpha _{i}-\alpha _{i+1}) \ge 0, \, \forall i \ge 0\) .

Similarly, if \(T_{0} \le 0\) we obtain that the sequence \(\{\alpha _i\}\) is non-decreasing and \(T_{i} \le 0, \, \forall i \ge 0\) . That concludes the proof.     \(\square \)

Lemma 5 [ 10 ] . From each \(\alpha _{0} \in [0,1]\) , Procedure Find \((\alpha _{0})\) converges to a coefficient \(\alpha _{k} \in \mathcal {C}_{0}\) satisfying \(\alpha _{k}\) is the unique element \(\in \mathcal {C}_{0}\) between \(\alpha _{0}\) and \(\alpha _{k}\) .

As a consequence of Lemma 4 , Procedure \(\textit{Find}(\alpha _{0})\) converges to a coefficient \(\alpha _{k} \in [0,1], \forall \alpha _{0} \in [0,1]\) .

By the stopping criteria of Procedure Find \((\alpha _{0})\) , when \(T_{k} = \alpha _{k} P_{k} - Q_{k} = 0\) we obtain \(\alpha _{k} \in C_{0}\) and \((P_{k},Q_{k})\) is a NF solution. (Theorem 3 )

If \(T_{0} = 0\) then obviously \(\alpha _{k} = \alpha _{0}\) . We consider \(T_{0} > 0\) and the sequence \(\{\alpha _i\}\) is now non-negative, non-increasing. We will show that \([\alpha _{k},\alpha _{0}] \cap \mathcal {C}_{0} = \alpha _{k}\) .

Suppose that we have \(\alpha \in (\alpha _{k},\alpha _{0}]\) and \(\alpha \in \mathcal {C}_{0}\) corresponding to a NF solution ( P ,  Q ). Then there exists \(1 \le i \le k\) such that \(\alpha \in (\alpha _{i}, \alpha _{i-1}]\) . Since \(\alpha \le \alpha _{i-1}\) , \(P \ge P_{i-1}\) and \(Q \le Q_{i-1}\) due to Lemma 3 . Thus, we get

By the definitions of \(\alpha \) and \(\alpha _{i}\) , inequality ( 9 ) is equivalent to \(\alpha \le \alpha _{i}\) which leads to a contradiction.

By repeating the same argument for \(T_{0} < 0\) , we also have a contradiction.     \(\square \)

Rights and permissions

Reprints and permissions

Copyright information

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

About this paper

Cite this paper.

Nguyen, M.H., Baiou, M., Nguyen, V.H. (2022). Nash Balanced Assignment Problem. In: Ljubić, I., Barahona, F., Dey, S.S., Mahjoub, A.R. (eds) Combinatorial Optimization. ISCO 2022. Lecture Notes in Computer Science, vol 13526. Springer, Cham. https://doi.org/10.1007/978-3-031-18530-4_13

Download citation

DOI : https://doi.org/10.1007/978-3-031-18530-4_13

Published : 21 November 2022

Publisher Name : Springer, Cham

Print ISBN : 978-3-031-18529-8

Online ISBN : 978-3-031-18530-4

eBook Packages : Computer Science Computer Science (R0)

Share this paper

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

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

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

Solving the Unbalanced Assignment Problem: Simpler Is Better

American Journal of Operations Research

Related Papers

Dr Avanish Kumar

Bhausaheb G Kore

In this paper I have proposed a new approach to solve an unbalanced assignment problem (UBAP). This approach includes two parts. First is to obtain an initial basic feasible solution (IBFS) and second part is to test optimality of an IBFS. I have proposed two new methods Row Penalty Assignment Method (RPAM) and Column Penalty Assignment Method (CPAM) to obtain an IBFS of an UBAP. Also I have proposed a new method Non-basic Smallest Effectiveness Method (NBSEM) to test optimality of an IBFS. We can solve an assignment problem of maximization type using this new approach in opposite sense. By this new approach, we achieve the goal with less number of computations and steps. Further we illustrate the new approach by suitable examples. INTRODUCTION The assignment problem is a special case of the transportation problem where the resources are being allocated to the activities on a one-to-one basis. Thus, each resource (e.g. an employee, machine or time slot) is to be assigned uniquely to a particular activity (e.g. a task, site or event). In assignment problems, supply in each row represents the availability of a resource such as a man, machine, vehicle, product, salesman, etc. and demand in each column represents different activities to be performed such as jobs, routes, factories, areas, etc. for each of which only one man or vehicle or product or salesman respectively is required. Entries in the square being costs, times or distances. The assignment method is a special linear programming technique for solving problems like choosing the right man for the right job when more than one choice is possible and when each man can perform all of the jobs. The ultimate objective is to assign a number of tasks to an equal number of facilities at minimum cost (or maximum profit) or some other specific goal. Let there be 'm' resources and 'n' activities. Let c ij be the effectiveness (in terms of cost, profit, time, etc.) of assigning resource i to activity j (i = 1, 2, …., m; j = 1, 2,…., n). Let x ij = 0, if resource i is not assigned to activity j and x ij = 1, if resource i is assigned to activity j. Then the objective is to determine x ij 's that will optimize the total effectiveness (Z) satisfying all the resource constraints and activity constraints. 1. Mathematical Formulation Let number of rows = m and number of columns = n. If m = n then an AP is said to be BAP otherwise it is said to be UBAP. A) Case 1: If m < n then mathematically the UBAP can be stated as follows:

Malaya Journal of Matematik

DR ANJU KHANDELWAL

International Journal for Research in Applied Science & Engineering Technology (IJRASET)

IJRASET Publication

In this paper a new method is proposed for finding an optimal solution of a wide range of assignment problems, directly. A numerical illustration is established and the optimality of the result yielded by this method is also checked. The most attractive feature of this method is that it requires very simple arithmetical and logical calculations. The method is illustrated through an example.

Hussein Ali Hussein Al-Dallal Al-Saeedi

archana pandey

Assignment problems arise in different situation where we have to find an optimal way to assign n-objects to mother objects in an injective fashion. The assignment problems are a well studied topic in combinatorial optimization. These problems find numerous application in production planning, telecommunication VLSI design, economic etc. The assignment problems is a special case of Transportation problem. Depending on the objective we want to optimize, we obtain the typical assignment problems. Assignment problem is an important subject discussed in real physical world we endeavor in this paper to introduce a new approach to assignment problem namely, matrix ones assignment method or MOA-method for solving wide range of problem. An example using matrix ones assignment methods and the existing Hungarian method have been solved and compared it graphically. Also some of the variations and some special cases in assignment problem and its applications have been discussed in the paper.

Sultana Rafi

The assignment problem is a particular type of linear programming problem. In this paper, we analyzed the standard and existing proposed methods. After studying these methods, we proposed a new alternative method for solving the assignment problem. We examined the newly proposed method by a couple of numerical examples and compare this result with the standard method. The main characteristic of this newly proposed method is that it constructed a very easy logical and arithmetical algorithm. Here we point out some advantages and limitations of the new proposed method. Programming code for the newly proposed method has been added in this paper.

Ranjan Kumar Mondal

Thecloudcomputingpresentsatypeofassignmentsandsystemswhichoccupydistributedresources toexecutearoleinadistributedway.Cloudcomputingmakeuseoftheonlinesystemsonthewebto assisttheimplementationofcomplicatedassignments;thatneedhuge-scalecomputation.Itwassaid withtheintentionofinourlivingworld;wecanfinditchallengingtobalanceworkloadsofcloud computingamongassignments(jobsortasks)andsystems(machinesornodes),sothemajorityofthe timewehavetopromoteaconditiontounbalancedassignmentproblems(unequaltaskallocations). The present article submits a new technique to solve the unequal task allocation problems. The techniqueisofferedinanalgorithmicmodelandputintopracticeontheseveralgroupsofinputto investigatethepresentationandusefulnessoftheworks.Anevaluationispreparedwiththepresented approach.Itmakessurethattheproposedapproachprovidesabetteroutcomebycomparingwith someotherexistingalgorithms.

Industrial Engineering Journal

Shridhar Mhalsekar

Journal of Advances in Mathematics and Computer Science

Hudu Mohammed

Assignment problem is an important area in Operation Research and is also discussed in real physical world. In this paper an attempt has been made to solve the assignment problem using a new Method called the Penalty method. We discuss a numerical example by using the new Method and compare it with standard existing method which is the Hungarian method. We compare the optimal solution of the new Method and the Hungarian method. The new method is a simple procedure, easy to apply for solving assignment problem.

RELATED TOPICS

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

Quantitative Techniques: Theory and Problems by P. C. Tulsian, Vishal Pandey

Get full access to Quantitative Techniques: Theory and Problems and 60K+ other titles, with a free 10-day trial of O'Reilly.

There are also live events, courses curated by job role, and more.

BALANCED ASSIGNMENT PROBLEM

Balanced Assignment Problem is an assignment problem where the number of facilities is equal to the number of jobs.

Get Quantitative Techniques: Theory and Problems now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Don’t leave empty-handed

Get Mark Richards’s Software Architecture Patterns ebook to better understand how to design components—and how they should interact.

It’s yours, free.

Check it out now on O’Reilly

Dive in for free with a 10-day trial of the O’Reilly learning platform—then explore all the other resources our members count on to build skills and solve problems every day.

How to Solve the Assignment Problem: A Complete Guide

Table of Contents

Assignment problem is a special type of linear programming problem that deals with assigning a number of resources to an equal number of tasks in the most efficient way. The goal is to minimize the total cost of assignments while ensuring that each task is assigned to only one resource and each resource is assigned to only one task. In this blog, we will discuss the solution of the assignment problem using the Hungarian method, which is a popular algorithm for solving the problem.

Understanding the Assignment Problem

Before we dive into the solution, it is important to understand the problem itself. In the assignment problem, we have a matrix of costs, where each row represents a resource and each column represents a task. The objective is to assign each resource to a task in such a way that the total cost of assignments is minimized. However, there are certain constraints that need to be satisfied – each resource can be assigned to only one task and each task can be assigned to only one resource.

Solving the Assignment Problem

There are various methods for solving the assignment problem, including the Hungarian method, the brute force method, and the auction algorithm. Here, we will focus on the steps involved in solving the assignment problem using the Hungarian method, which is the most commonly used and efficient method.

Step 1: Set up the cost matrix

The first step in solving the assignment problem is to set up the cost matrix, which represents the cost of assigning a task to an agent. The matrix should be square and have the same number of rows and columns as the number of tasks and agents, respectively.

Step 2: Subtract the smallest element from each row and column

To simplify the calculations, we need to reduce the size of the cost matrix by subtracting the smallest element from each row and column. This step is called matrix reduction.

Step 3: Cover all zeros with the minimum number of lines

The next step is to cover all zeros in the matrix with the minimum number of horizontal and vertical lines. This step is called matrix covering.

Step 4: Test for optimality and adjust the matrix

To test for optimality, we need to calculate the minimum number of lines required to cover all zeros in the matrix. If the number of lines equals the number of rows or columns, the solution is optimal. If not, we need to adjust the matrix and repeat steps 3 and 4 until we get an optimal solution.

Step 5: Assign the tasks to the agents

The final step is to assign the tasks to the agents based on the optimal solution obtained in step 4. This will give us the most cost-effective or profit-maximizing assignment.

Solution of the Assignment Problem using the Hungarian Method

The Hungarian method is an algorithm that uses a step-by-step approach to find the optimal assignment. The algorithm consists of the following steps:

• Subtract the smallest entry in each row from all the entries of the row.
• Subtract the smallest entry in each column from all the entries of the column.
• Draw the minimum number of lines to cover all zeros in the matrix. If the number of lines drawn is equal to the number of rows, we have an optimal solution. If not, go to step 4.
• Determine the smallest entry not covered by any line. Subtract it from all uncovered entries and add it to all entries covered by two lines. Go to step 3.

The above steps are repeated until an optimal solution is obtained. The optimal solution will have all zeros covered by the minimum number of lines. The assignments can be made by selecting the rows and columns with a single zero in the final matrix.

Applications of the Assignment Problem

The assignment problem has various applications in different fields, including computer science, economics, logistics, and management. In this section, we will provide some examples of how the assignment problem is used in real-life situations.

Applications in Computer Science

The assignment problem can be used in computer science to allocate resources to different tasks, such as allocating memory to processes or assigning threads to processors.

Applications in Economics

The assignment problem can be used in economics to allocate resources to different agents, such as allocating workers to jobs or assigning projects to contractors.

Applications in Logistics

The assignment problem can be used in logistics to allocate resources to different activities, such as allocating vehicles to routes or assigning warehouses to customers.

Applications in Management

The assignment problem can be used in management to allocate resources to different projects, such as allocating employees to tasks or assigning budgets to departments.

Let’s consider the following scenario: a manager needs to assign three employees to three different tasks. Each employee has different skills, and each task requires specific skills. The manager wants to minimize the total time it takes to complete all the tasks. The skills and the time required for each task are given in the table below:

The assignment problem is to determine which employee should be assigned to which task to minimize the total time required. To solve this problem, we can use the Hungarian method, which we discussed in the previous blog.

Using the Hungarian method, we first subtract the smallest entry in each row from all the entries of the row:

Next, we subtract the smallest entry in each column from all the entries of the column:

We draw the minimum number of lines to cover all the zeros in the matrix, which in this case is three:

Since the number of lines is equal to the number of rows, we have an optimal solution. The assignments can be made by selecting the rows and columns with a single zero in the final matrix. In this case, the optimal assignments are:

• Emp 1 to Task 3
• Emp 2 to Task 2
• Emp 3 to Task 1

This assignment results in a total time of 9 units.

I hope this example helps you better understand the assignment problem and how to solve it using the Hungarian method.

Solving the assignment problem may seem daunting, but with the right approach, it can be a straightforward process. By following the steps outlined in this guide, you can confidently tackle any assignment problem that comes your way.

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

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

• TPC and eLearning
• Read Watch Interact
• What's NEW at TPC?
• Practice Review Test
• Teacher-Tools
• Subscription Selection
• Seat Calculator
• Ad Free Account
• Edit Profile Settings
• Classes (Version 2)
• Student Progress Edit
• Task Properties
• Export Student Progress
• Task, Activities, and Scores
• Metric Conversions Questions
• Metric System Questions
• Metric Estimation Questions
• Significant Digits Questions
• Proportional Reasoning
• Acceleration
• Distance-Displacement
• Dots and Graphs
• Graph That Motion
• Match That Graph
• Name That Motion
• Motion Diagrams
• Pos'n Time Graphs Numerical
• Pos'n Time Graphs Conceptual
• Up And Down - Questions
• Balanced vs. Unbalanced Forces
• Change of State
• Force and Motion
• Mass and Weight
• Match That Free-Body Diagram
• Net Force (and Acceleration) Ranking Tasks
• Newton's Second Law
• Normal Force Card Sort
• Recognizing Forces
• Air Resistance and Skydiving
• Solve It! with Newton's Second Law
• Which One Doesn't Belong?
• Component Addition Questions
• Head-to-Tail Vector Addition
• Projectile Mathematics
• Trajectory - Angle Launched Projectiles
• Trajectory - Horizontally Launched Projectiles
• Vector Addition
• Vector Direction
• Which One Doesn't Belong? Projectile Motion
• Forces in 2-Dimensions
• Being Impulsive About Momentum
• Explosions - Law Breakers
• Hit and Stick Collisions - Law Breakers
• Case Studies: Impulse and Force
• Impulse-Momentum Change Table
• Keeping Track of Momentum - Hit and Stick
• Keeping Track of Momentum - Hit and Bounce
• What's Up (and Down) with KE and PE?
• Energy Conservation Questions
• Energy Dissipation Questions
• Energy Ranking Tasks
• LOL Charts (a.k.a., Energy Bar Charts)
• Match That Bar Chart
• Words and Charts Questions
• Name That Energy
• Stepping Up with PE and KE Questions
• Case Studies - Circular Motion
• Circular Logic
• Forces and Free-Body Diagrams in Circular Motion
• Gravitational Field Strength
• Universal Gravitation
• Angular Position and Displacement
• Linear and Angular Velocity
• Angular Acceleration
• Rotational Inertia
• Balanced vs. Unbalanced Torques
• Getting a Handle on Torque
• Torque-ing About Rotation
• Properties of Matter
• Fluid Pressure
• Buoyant Force
• Sinking, Floating, and Hanging
• Pascal's Principle
• Flow Velocity
• Bernoulli's Principle
• Balloon Interactions
• Charge and Charging
• Charge Interactions
• Charging by Induction
• Conductors and Insulators
• Coulombs Law
• Electric Field
• Electric Field Intensity
• Polarization
• Case Studies: Electric Power
• Know Your Potential
• Light Bulb Anatomy
• I = ∆V/R Equations as a Guide to Thinking
• Parallel Circuits - ∆V = I•R Calculations
• Resistance Ranking Tasks
• Series Circuits - ∆V = I•R Calculations
• Series vs. Parallel Circuits
• Equivalent Resistance
• Period and Frequency of a Pendulum
• Pendulum Motion: Velocity and Force
• Energy of a Pendulum
• Period and Frequency of a Mass on a Spring
• Horizontal Springs: Velocity and Force
• Vertical Springs: Velocity and Force
• Energy of a Mass on a Spring
• Decibel Scale
• Frequency and Period
• Closed-End Air Columns
• Name That Harmonic: Strings
• Rocking the Boat
• Wave Basics
• Matching Pairs: Wave Characteristics
• Wave Interference
• Waves - Case Studies
• Color Addition and Subtraction
• Color Filters
• If This, Then That: Color Subtraction
• Light Intensity
• Color Pigments
• Converging Lenses
• Curved Mirror Images
• Law of Reflection
• Refraction and Lenses
• Total Internal Reflection
• Who Can See Who?
• Formulas and Atom Counting
• Atomic Models
• Bond Polarity
• Entropy Questions
• Cell Voltage Questions
• Heat of Formation Questions
• Reduction Potential Questions
• Oxidation States Questions
• Measuring the Quantity of Heat
• Hess's Law
• Oxidation-Reduction Questions
• Galvanic Cells Questions
• Thermal Stoichiometry
• Molecular Polarity
• Quantum Mechanics
• Balancing Chemical Equations
• Bronsted-Lowry Model of Acids and Bases
• Classification of Matter
• Collision Model of Reaction Rates
• Density Ranking Tasks
• Dissociation Reactions
• Complete Electron Configurations
• Elemental Measures
• Enthalpy Change Questions
• Equilibrium Concept
• Equilibrium Constant Expression
• Equilibrium Calculations - Questions
• Equilibrium ICE Table
• Intermolecular Forces Questions
• Ionic Bonding
• Lewis Electron Dot Structures
• Limiting Reactants
• Line Spectra Questions
• Mass Stoichiometry
• Measurement and Numbers
• Metals, Nonmetals, and Metalloids
• Metric Estimations
• Metric System
• Molarity Ranking Tasks
• Mole Conversions
• Name That Element
• Names to Formulas
• Names to Formulas 2
• Nuclear Decay
• Particles, Words, and Formulas
• Periodic Trends
• Precipitation Reactions and Net Ionic Equations
• Pressure Concepts
• Pressure-Temperature Gas Law
• Pressure-Volume Gas Law
• Chemical Reaction Types
• Significant Digits and Measurement
• States Of Matter Exercise
• Stoichiometry Law Breakers
• Stoichiometry - Math Relationships
• Subatomic Particles
• Spontaneity and Driving Forces
• Gibbs Free Energy
• Volume-Temperature Gas Law
• Acid-Base Properties
• Energy and Chemical Reactions
• Chemical and Physical Properties
• Valence Shell Electron Pair Repulsion Theory
• Writing Balanced Chemical Equations
• Mission CG1
• Mission CG10
• Mission CG2
• Mission CG3
• Mission CG4
• Mission CG5
• Mission CG6
• Mission CG7
• Mission CG8
• Mission CG9
• Mission EC1
• Mission EC10
• Mission EC11
• Mission EC12
• Mission EC2
• Mission EC3
• Mission EC4
• Mission EC5
• Mission EC6
• Mission EC7
• Mission EC8
• Mission EC9
• Mission RL1
• Mission RL2
• Mission RL3
• Mission RL4
• Mission RL5
• Mission RL6
• Mission KG7
• Mission RL8
• Mission KG9
• Mission RL10
• Mission RL11
• Mission RM1
• Mission RM2
• Mission RM3
• Mission RM4
• Mission RM5
• Mission RM6
• Mission RM8
• Mission RM10
• Mission LC1
• Mission RM11
• Mission LC2
• Mission LC3
• Mission LC4
• Mission LC5
• Mission LC6
• Mission LC8
• Mission SM1
• Mission SM2
• Mission SM3
• Mission SM4
• Mission SM5
• Mission SM6
• Mission SM8
• Mission SM10
• Mission KG10
• Mission SM11
• Mission KG2
• Mission KG3
• Mission KG4
• Mission KG5
• Mission KG6
• Mission KG8
• Mission KG11
• Mission F2D1
• Mission F2D2
• Mission F2D3
• Mission F2D4
• Mission F2D5
• Mission F2D6
• Mission KC1
• Mission KC2
• Mission KC3
• Mission KC4
• Mission KC5
• Mission KC6
• Mission KC7
• Mission KC8
• Mission AAA
• Mission SM9
• Mission LC7
• Mission LC9
• Mission NL1
• Mission NL2
• Mission NL3
• Mission NL4
• Mission NL5
• Mission NL6
• Mission NL7
• Mission NL8
• Mission NL9
• Mission NL10
• Mission NL11
• Mission NL12
• Mission MC1
• Mission MC10
• Mission MC2
• Mission MC3
• Mission MC4
• Mission MC5
• Mission MC6
• Mission MC7
• Mission MC8
• Mission MC9
• Mission RM7
• Mission RM9
• Mission RL7
• Mission RL9
• Mission SM7
• Mission SE1
• Mission SE10
• Mission SE11
• Mission SE12
• Mission SE2
• Mission SE3
• Mission SE4
• Mission SE5
• Mission SE6
• Mission SE7
• Mission SE8
• Mission SE9
• Mission VP1
• Mission VP10
• Mission VP2
• Mission VP3
• Mission VP4
• Mission VP5
• Mission VP6
• Mission VP7
• Mission VP8
• Mission VP9
• Mission WM1
• Mission WM2
• Mission WM3
• Mission WM4
• Mission WM5
• Mission WM6
• Mission WM7
• Mission WM8
• Mission WE1
• Mission WE10
• Mission WE2
• Mission WE3
• Mission WE4
• Mission WE5
• Mission WE6
• Mission WE7
• Mission WE8
• Mission WE9
• Vector Walk Interactive
• Name That Motion Interactive
• Kinematic Graphing 1 Concept Checker
• Kinematic Graphing 2 Concept Checker
• Graph That Motion Interactive
• Two Stage Rocket Interactive
• Rocket Sled Concept Checker
• Force Concept Checker
• Free-Body Diagrams Concept Checker
• Free-Body Diagrams The Sequel Concept Checker
• Skydiving Concept Checker
• Elevator Ride Concept Checker
• Vector Addition Concept Checker
• Vector Walk in Two Dimensions Interactive
• Name That Vector Interactive
• River Boat Simulator Concept Checker
• Projectile Simulator 2 Concept Checker
• Projectile Simulator 3 Concept Checker
• Hit the Target Interactive
• Turd the Target 1 Interactive
• Turd the Target 2 Interactive
• Balance It Interactive
• Go For The Gold Interactive
• Egg Drop Concept Checker
• Fish Catch Concept Checker
• Exploding Carts Concept Checker
• Collision Carts - Inelastic Collisions Concept Checker
• Its All Uphill Concept Checker
• Stopping Distance Concept Checker
• Chart That Motion Interactive
• Roller Coaster Model Concept Checker
• Uniform Circular Motion Concept Checker
• Horizontal Circle Simulation Concept Checker
• Vertical Circle Simulation Concept Checker
• Race Track Concept Checker
• Gravitational Fields Concept Checker
• Orbital Motion Concept Checker
• Angular Acceleration Concept Checker
• Balance Beam Concept Checker
• Torque Balancer Concept Checker
• Aluminum Can Polarization Concept Checker
• Charging Concept Checker
• Name That Charge Simulation
• Coulomb's Law Concept Checker
• Electric Field Lines Concept Checker
• Put the Charge in the Goal Concept Checker
• Circuit Builder Concept Checker (Series Circuits)
• Circuit Builder Concept Checker (Parallel Circuits)
• Circuit Builder Concept Checker (∆V-I-R)
• Circuit Builder Concept Checker (Voltage Drop)
• Equivalent Resistance Interactive
• Pendulum Motion Simulation Concept Checker
• Mass on a Spring Simulation Concept Checker
• Particle Wave Simulation Concept Checker
• Boundary Behavior Simulation Concept Checker
• Slinky Wave Simulator Concept Checker
• Simple Wave Simulator Concept Checker
• Wave Addition Simulation Concept Checker
• Standing Wave Maker Simulation Concept Checker
• Color Addition Concept Checker
• Painting With CMY Concept Checker
• Stage Lighting Concept Checker
• Filtering Away Concept Checker
• InterferencePatterns Concept Checker
• Young's Experiment Interactive
• Plane Mirror Images Interactive
• Who Can See Who Concept Checker
• Optics Bench (Mirrors) Concept Checker
• Name That Image (Mirrors) Interactive
• Refraction Concept Checker
• Total Internal Reflection Concept Checker
• Optics Bench (Lenses) Concept Checker
• Kinematics Preview
• Velocity Time Graphs Preview
• Moving Cart on an Inclined Plane Preview
• Stopping Distance Preview
• Cart, Bricks, and Bands Preview
• Fan Cart Study Preview
• Friction Preview
• Coffee Filter Lab Preview
• Friction, Speed, and Stopping Distance Preview
• Up and Down Preview
• Projectile Range Preview
• Ballistics Preview
• Juggling Preview
• Marshmallow Launcher Preview
• Air Bag Safety Preview
• Colliding Carts Preview
• Collisions Preview
• Engineering Safer Helmets Preview
• Push the Plow Preview
• Its All Uphill Preview
• Energy on an Incline Preview
• Modeling Roller Coasters Preview
• Hot Wheels Stopping Distance Preview
• Ball Bat Collision Preview
• Energy in Fields Preview
• Weightlessness Training Preview
• Roller Coaster Loops Preview
• Universal Gravitation Preview
• Keplers Laws Preview
• Kepler's Third Law Preview
• Charge Interactions Preview
• Sticky Tape Experiments Preview
• Wire Gauge Preview
• Voltage, Current, and Resistance Preview
• Light Bulb Resistance Preview
• Series and Parallel Circuits Preview
• Thermal Equilibrium Preview
• Linear Expansion Preview
• Heating Curves Preview
• Electricity and Magnetism - Part 1 Preview
• Electricity and Magnetism - Part 2 Preview
• Vibrating Mass on a Spring Preview
• Period of a Pendulum Preview
• Wave Speed Preview
• Slinky-Experiments Preview
• Standing Waves in a Rope Preview
• Sound as a Pressure Wave Preview
• DeciBel Scale Preview
• DeciBels, Phons, and Sones Preview
• Sound of Music Preview
• Shedding Light on Light Bulbs Preview
• Models of Light Preview
• Electromagnetic Radiation Preview
• Electromagnetic Spectrum Preview
• EM Wave Communication Preview
• Digitized Data Preview
• Light Intensity Preview
• Concave Mirrors Preview
• Object Image Relations Preview
• Snells Law Preview
• Reflection vs. Transmission Preview
• Magnification Lab Preview
• Reactivity Preview
• Ions and the Periodic Table Preview
• Periodic Trends Preview
• Intermolecular Forces Preview
• Melting Points and Boiling Points Preview
• Reaction Rates Preview
• Ammonia Factory Preview
• Stoichiometry Preview
• Nuclear Chemistry Preview
• Gaining Teacher Access
• Tasks and Classes
• Tasks - Classic
• Subscription
• Subscription Locator
• 1-D Kinematics
• Newton's Laws
• Vectors - Motion and Forces in Two Dimensions
• Momentum and Its Conservation
• Work and Energy
• Circular Motion and Satellite Motion
• Thermal Physics
• Static Electricity
• Electric Circuits
• Vibrations and Waves
• Sound Waves and Music
• Light and Color
• Reflection and Mirrors
• About the Physics Interactives
• Task Tracker
• Usage Policy
• Newtons Laws
• Vectors and Projectiles
• Forces in 2D
• Momentum and Collisions
• Circular and Satellite Motion
• Balance and Rotation
• Electromagnetism
• Waves and Sound
• Atomic Physics
• Forces in Two Dimensions
• Work, Energy, and Power
• Circular Motion and Gravitation
• Sound Waves
• 1-Dimensional Kinematics
• Circular, Satellite, and Rotational Motion
• Einstein's Theory of Special Relativity
• Waves, Sound and Light
• QuickTime Movies
• About the Concept Builders
• Pricing For Schools
• Directions for Version 2
• Measurement and Units
• Relationships and Graphs
• Rotation and Balance
• Vibrational Motion
• Reflection and Refraction
• Teacher Accounts
• Task Tracker Directions
• Kinematic Concepts
• Kinematic Graphing
• Wave Motion
• Sound and Music
• About CalcPad
• 1D Kinematics
• Vectors and Forces in 2D
• Simple Harmonic Motion
• Rotational Kinematics
• Rotation and Torque
• Rotational Dynamics
• Electric Fields, Potential, and Capacitance
• Transient RC Circuits
• Light Waves
• Units and Measurement
• Stoichiometry
• Molarity and Solutions
• Thermal Chemistry
• Acids and Bases
• Kinetics and Equilibrium
• Solution Equilibria
• Oxidation-Reduction
• Nuclear Chemistry
• NGSS Alignments
• 1D-Kinematics
• Projectiles
• Circular Motion
• Magnetism and Electromagnetism
• Graphing Practice
• About the ACT
• ACT Preparation
• For Teachers
• Other Resources
• Newton's Laws of Motion
• Work and Energy Packet
• Static Electricity Review
• Solutions Guide
• Solutions Guide Digital Download
• Motion in One Dimension
• Work, Energy and Power
• Frequently Asked Questions
• Purchasing the Download
• Purchasing the CD
• Purchasing the Digital Download
• About the NGSS Corner
• NGSS Search
• Force and Motion DCIs - High School
• Energy DCIs - High School
• Wave Applications DCIs - High School
• Force and Motion PEs - High School
• Energy PEs - High School
• Wave Applications PEs - High School
• Crosscutting Concepts
• The Practices
• Physics Topics
• NGSS Corner: Activity List
• NGSS Corner: Infographics
• About the Toolkits
• Position-Velocity-Acceleration
• Position-Time Graphs
• Velocity-Time Graphs
• Newton's First Law
• Newton's Second Law
• Newton's Third Law
• Terminal Velocity
• Projectile Motion
• Forces in 2 Dimensions
• Impulse and Momentum Change
• Momentum Conservation
• Work-Energy Fundamentals
• Work-Energy Relationship
• Roller Coaster Physics
• Satellite Motion
• Electric Fields
• Circuit Concepts
• Series Circuits
• Parallel Circuits
• Describing-Waves
• Wave Behavior Toolkit
• Standing Wave Patterns
• Resonating Air Columns
• Wave Model of Light
• Plane Mirrors
• Curved Mirrors
• Teacher Guide
• Using Lab Notebooks
• Current Electricity
• Light Waves and Color
• Reflection and Ray Model of Light
• Refraction and Ray Model of Light
• Classes (Legacy Version)
• Teacher Resources
• Subscriptions

• Newton's Laws
• Einstein's Theory of Special Relativity
• About Concept Checkers
• School Pricing
• Newton's Laws of Motion
• Newton's First Law
• Newton's Third Law

Balanced and Unbalanced Forces

• Inertia and Mass
• State of Motion

Newton's first law of motion has been frequently stated throughout this lesson.

An object at rest stays at rest and an object in motion stays in motion with the same speed and in the same direction unless acted upon by an unbalanced force.

Balanced Forces

But what exactly is meant by the phrase unbalanced force ? What is an unbalanced force? In pursuit of an answer, we will first consider a physics book at rest on a tabletop. There are two forces acting upon the book. One force - the Earth's gravitational pull - exerts a downward force. The other force - the push of the table on the book (sometimes referred to as a normal force ) - pushes upward on the book.  

Since these two forces are of equal magnitude and in opposite directions, they balance each other. The book is said to be at equilibrium . There is no unbalanced force acting upon the book and thus the book maintains its state of motion . When all the forces acting upon an object balance each other, the object will be at equilibrium; it will not accelerate. (Note: diagrams such as the one above are known as free-body diagrams and will be discussed in detail in Lesson 2 .)

Consider another example involving balanced forces - a person standing on the floor. There are two forces acting upon the person. The force of gravity exerts a downward force. The floor exerts an upward force.

Since these two forces are of equal magnitude and in opposite directions, they balance each other. The person is at equilibrium. There is no unbalanced force acting upon the person and thus the person maintains its state of motion . (Note: diagrams such as the one above are known as free-body diagrams and will be discussed in detail in Lesson 2 .)  

Unbalanced Forces

Now consider a book sliding from left to right across a tabletop. Sometime in the prior history of the book , it may have been given a shove and set in motion from a rest position. Or perhaps it acquired its motion by sliding down an incline from an elevated position. Whatever the case, our focus is not upon the history of the book but rather upon the current situation of a book sliding to the right across a tabletop. The book is in motion and at the moment there is no one pushing it to the right. (Remember: a force is not needed to keep a moving object moving to the right .) The forces acting upon the book are shown below.  

The force of gravity pulling downward and the force of the table pushing upwards on the book are of equal magnitude and opposite directions. These two forces balance each other. Yet there is no force present to balance the force of friction. As the book moves to the right, friction acts to the left to slow the book down. There is an unbalanced force; and as such, the book changes its state of motion. The book is not at equilibrium and subsequently accelerates. Unbalanced forces cause accelerations . In this case, the unbalanced force is directed opposite the book's motion and will cause it to slow down. (Note: diagrams such as the one above are known as free-body diagrams and will be discussed in detail in Lesson 2 .)

To determine if the forces acting upon an object are balanced or unbalanced, an analysis must first be conducted to determine what forces are acting upon the object and in what direction. If two individual forces are of equal magnitude and opposite direction, then the forces are said to be balanced. An object is said to be acted upon by an unbalanced force only when there is an individual force that is not being balanced by a force of equal magnitude and in the opposite direction. Such analyses are discussed in Lesson 2 of this unit and applied in Lesson 3 .

We Would Like to Suggest ...

Check Your Understanding

Luke Autbeloe drops an approximately 5.0 kg box of shingles (weight = 50.0 N) off the roof of his house into the swimming pool below. Upon encountering the pool, the box encounters a 50.0 N upward resistance force (assumed to be constant). Use this description to answer the following questions. Click the button to view the correct answers.

1. Which one of the velocity-time graphs best describes the motion of the box? Support your answer with sound reasoning.

Graph B is correct. The box first accelerates with a negative (downward) acceleration until it hits the water. Upon hitting the water, the box experiences a balance of forces (50 N downwards due to gravity and 50 N upwards due to the water). Thus, the box will finish its motion moving with a constant velocity. Graph B depicts both the initial negative acceleration and the final constant velocity.

2. Which one of the following dot diagrams best describes the motion of the falling box from the time that they are dropped to the time that they hit the bottom of the pool? The arrows on the diagram represent the point at which the box hits the water. Support your answer with sound reasoning.

Tape A is correct.

The box first accelerates with a negative (downward) acceleration until it hits the water. Upon hitting the water, the box experience a balance of forces (50 N downwards due to gravity and 50 N upwards due to the water). Thus, the box will finish its motion moving with a constant velocity. Diagram A depicts both the initial downward acceleration and the final constant velocity.

3. Several of Luke's friends were watching the motion of the falling box. Being "physics types", they began discussing the motion and made the following comments. Indicate whether each of the comments is correct or incorrect? Support your answers.

a. Once the box hits the water, the forces are balanced and the box will stop.

Once the box hits the water, the forces are balanced (50 N down and 50 N up). However, an object in motion (such as the box) will continue in motion at the same speed and in the same direction. When the box strikes the water, it stops accelerating; yet it does not stop moving.

b. Upon hitting the water, the box will accelerate upwards because the water applies an upward force.

Once the box hit the water, the forces are balanced (50 N down and 50 N up). The upward force of the water on the box is balanced by the downward pull of gravity. The box will continue in motion at constant speed.

 c. Upon hitting the water, the box will bounce upwards due to the upward force.

Once the box hits the water, the forces are balanced (50 N down and 50 N up). The box would only bounce upwards if the water applied an upward force greater than 50 N. As stated in the problem, the water applies only 50 N of upward force. Furthermore, the upward force would first contribute to slowing the box down (an upward acceleration) before it could begin to actually move it upward.

4. If the forces acting upon an object are balanced, then the object

a. must not be moving. b. must be moving with a constant velocity. c. must not be accelerating. d. none of these

The answer could be A (but does not have to be A) and it could be B (but does not have to be B). An object having balanced forces definitely cannot be accelerating. This means that it could be at rest and staying at rest (one option) or could be in motion at constant velocity (a second option). Either way, it definitely is not accelerating - choice C of your four choices.

• Meaning of Force