Exercise 7.1 – Assignment problems by the Hungarian methodClass 12 Commerce Maths · Chapter 7 Assignment Problem and Sequencing · Exercise 7.1 – Maharashtra Board

Textbook: Mathematics and Statistics (Commerce) Part II – Class 12 (Balbharati, official free PDF) · pages 108–119

An assignment problem asks how to give n jobs to n workers (or machines, salesmen, routes), one each, so that the total cost or time is least or the total profit is greatest. Trying all n! arrangements is slow, so we use the Hungarian method, which keeps subtracting numbers from rows and columns until a full set of zero-cost assignments appears. This exercise also covers the special cases: maximisation, unbalanced tables that need a dummy row or column, and forbidden (restricted) assignments.

🎧 Listen to the summary

Summary: Exercise 7.1 – Assignment problems by the Hungarian method

An assignment problem pairs n workers with n jobs one-to-one to minimise total cost (or maximise total profit).

Adding or subtracting a constant to every entry of a row or column does not change the optimal assignment.

Hungarian method: reduce rows, reduce columns, cover zeros with the fewest lines; if lines = n, assign; otherwise create more zeros and repeat.

Maximisation: subtract every entry from the largest entry (or change signs) and then minimise.

Unbalanced problems get a dummy row or column of zeros; forbidden cells get a very large cost M.

Key points to remember

  • Conditions: equal numbers of workers and jobs, one job each, any worker can do any job, a clear objective.
  • In symbols: minimise Σ Σ cᵢⱼxᵢⱼ with each row and each column containing exactly one xᵢⱼ = 1.
  • Step 1: subtract the smallest entry of each row from that row.
  • Step 2: subtract the smallest entry of each column from that column.
  • Step 3: cover all zeros with the minimum number of horizontal and vertical lines.
  • If the number of lines equals the order n, an optimal assignment exists among the zeros.
  • Otherwise subtract the smallest uncovered number from all uncovered cells and add it at line intersections.
  • Assign first in rows or columns with a single zero; cross out the other zeros in that row and column.
  • Read the total cost or profit from the ORIGINAL table, not the reduced one.
  • If more than one set of zeros gives a full assignment, the problem has alternative optimal solutions.
Want a teacher to explain Exercise 7.1 – Assignment problems by the Hungarian method?

Get a ✓ Verified tutor for “Exercise 7.1 – Assignment problems by the Hungarian method” — live online or at home. We aim to suggest up to 3 tutors within 24 hours.

Get a tutor for this chapter →

👩‍🏫 Class 12 Commerce Maths Book classes — live online, request a call back

Prefer a real teacher? TalentJR teachers take live online classes anywhere in India. Tell us what you need and our team will call you with timings and fees.

Live online classesSmall groups or 1:1 with a teacher, from home, any city.
We call you backOur team asks what your child needs, then shares timings and fees.
Home tutor?We are still building our list of home tutors — ask on the call if there is one near you.

Keep learning