TalentJR apps
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.
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.
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.
Three workers W1, W2, W3 and jobs J1, J2, J3 with costs W1: 9, 2, 7; W2: 6, 4, 3; W3: 5, 8, 1. Without the Hungarian method, find the cheapest assignment.
Answer: W1→J2, W2→J1, W3→J3; cost 9
Solve the 3 × 3 cost table above (9, 2, 7 / 6, 4, 3 / 5, 8, 1) by the Hungarian method.
Answer: Minimum cost 9
Salesmen A, B and districts 1, 2 with daily profits A: 10, 7; B: 8, 9. Maximise total profit.
Answer: A→1, B→2; maximum profit Rs 19
Machines X, Y and places P, Q, R with costs X: 5, 8, 4; Y: 6, —, 3 (Y cannot go to Q). Find the cheapest placement.
Answer: X→P, Y→R; cost 8
| What | Formula | Symbols |
|---|---|---|
| Model | Min Σ Σ cᵢⱼxᵢⱼ, each row and column sums to 1 | xᵢⱼ = 1 if worker i gets job j |
| Row reduction | cᵢⱼ − (row minimum) | 9, 2, 7 → 7, 0, 5 |
| Column reduction | cᵢⱼ − (column minimum) | column 1: 7, 3, 4 → 4, 0, 1 |
| Optimality test | minimum lines covering zeros = n | 3 lines for a 3 × 3 table |
| Improvement | − least uncovered; + at intersections | Creates new zeros |
| Maximisation | regret = largest entry − entry | 10 − 7 = 3 |
| Unbalanced | add dummy row/column of zeros | 4 machines, 5 places |
| Restricted | put M (very large) in forbidden cells | Y cannot go to Q |
Solve each one in your notebook first. Then open the solution and compare every step.
1. Q1. Jobs P, Q, R, S on machines I–IV; costs P: 31, 25, 33, 29; Q: 25, 24, 23, 21; R: 19, 21, 23, 24; S: 38, 36, 34, 40. Minimise total cost.
Answer: P→II, Q→IV, R→I, S→III; minimum cost Rs 99
2. Q2. Wagons at stations 1–5 to stations I–V; mileages 1: 10, 5, 9, 18, 11; 2: 13, 9, 6, 12, 14; 3: 3, 2, 4, 4, 5; 4: 18, 9, 12, 17, 15; 5: 11, 6, 14, 19, 10. Minimise mileage.
Answer: 1→I, 2→III, 3→IV, 4→II, 5→V; minimum 39 miles
3. Q3. Jobs 1–5 on machines A–E with profits 1: 30, 37, 40, 28, 40; 2: 40, 24, 27, 21, 36; 3: 40, 32, 33, 30, 35; 4: 25, 38, 40, 36, 36; 5: 29, 62, 41, 34, 39. Maximise profit.
Answer: 1→C, 2→E, 3→A, 4→D, 5→B; maximum profit Rs 214
4. Q4. Machines M1–M4 to places A–E; M2 cannot go to C, M3 cannot go to A. Costs M1: 4, 6, 10, 5, 6; M2: 7, 4, —, 5, 4; M3: —, 6, 9, 6, 2; M4: 9, 3, 7, 2, 3. Minimise cost.
Answer: M1→A, M2→B, M3→E, M4→D (C vacant); minimum cost 12
5. Q5. Salesmen A–D in districts 1–4; profits A: 16, 10, 12, 11; B: 12, 13, 15, 15; C: 15, 15, 11, 14; D: 13, 14, 14, 15. Maximise profit.
Answer: A→1, B→3, C→2, D→4; maximum profit Rs 61 per day
6. Q6. Machines M1–M4 at locations A–E (hundred rupees); M2 not at C, M3 not at A. Costs M1: 9, 11, 15, 10, 11; M2: 12, 9, —, 10, 9; M3: —, 11, 14, 11, 7; M4: 14, 8, 12, 7, 8. Minimise cost.
Answer: M1→A, M2→B, M3→E, M4→D; minimum cost Rs 3,200 (32 hundred)
Read the question, answer it in your head, then tap the card to check. 20 cards.
15 questions. Tap an option — you will see at once if it is right and why.
1. An assignment problem requires
Answer: A. Balanced, one-to-one.
2. The first step of the Hungarian method is
Answer: B. Subtract row minima.
3. The table is ready for assignment when
Answer: A. Optimality test.
4. For a maximisation problem you first
Answer: A. Convert to regret.
5. A 4 × 5 cost table needs
Answer: A. Four rows, five columns.
6. A machine that cannot go to a place gets a cost of
Answer: B. So it is never chosen.
7. Row 9, 2, 7 after row reduction is
Answer: A. Subtract 2.
8. If lines < n, the least uncovered number is
Answer: D. Standard improvement step.
9. The total minimum cost is read from
Answer: B. Reduced entries are not costs.
10. How many ways can 5 jobs be assigned to 5 machines?
Answer: B. 5!
11. Assigning to a dummy column means
Answer: C. Dummy = no job.
12. Adding 5 to every entry of a row
Answer: A. Property of assignment problems.
13. Optimal cost in Ex 7.1 Q1 (jobs P–S on machines I–IV) is
Answer: A. P→II, Q→IV, R→I, S→III.
14. Maximum profit in Ex 7.1 Q3 is
Answer: D. 1→C, 2→E, 3→A, 4→D, 5→B.
15. An assignment problem is a special case of
Answer: B. 0–1 variables.
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.
Done with the notes? Revise Exercise 7.1 – Assignment problems by the Hungarian method the fun way: match key terms, beat the 60-second lightning round and spot true or false facts. Every game uses only this lesson, so each round is real exam revision.
⭐ 0 XP⏱ About 55 minutes
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.
Sign in free to see the answers to the textbook exercise of Exercise 7.1 – Assignment problems by the Hungarian method.
Sign in to see solutionsStuck on a question? Type it, 🎤 speak it or 📷 snap a photo of it and get simple, step-by-step help with “Assignment Problem and Sequencing Ex 7.1” — important questions, a quick quiz, revision notes — in English, मराठी or हिंदी.
Sign in with Google to ask the AI tutor. It's free — 20 questions a day, one TalentJR account.
Sign in to askPrefer 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.