Worked Examples · Example 6
Q.
A shop must complete four jobs but has only three machines (each machine can take one job). The cost (in ) is:
| Machine | ||||
|---|---|---|---|---|
| 4 | 6 | 8 | 2 | |
| 6 | 3 | 5 | 9 | |
| 5 | 7 | 4 | 8 |
Assign the jobs to minimise total cost, and state which job is left undone.
Maharashtra MsbshseTextbookSubjectiveImportance★★★★★
31% · 10/32 Questions
You're viewing a preview — the full solution, concept, methods & PYQ mapping are locked.
Start your 14-day free trial to unlock the full solution →Step 0 — Balance the problem. There are jobs but only machines, so add a dummy machine with all costs :
| Machine | ||||
|---|---|---|---|---|
| 4 | 6 | 8 | 2 | |
| 6 | 3 | 5 | 9 | |
| 5 | 7 | 4 | 8 | |
| 0 | 0 | 0 | 0 |
Step 1 — Row reduction. Row minima :
| Machine | ||||
|---|---|---|---|---|
| 2 | 4 | 6 | 0 | |
| 3 | 0 | 2 | 6 | |
| 1 | 3 | 0 | 4 | |
| 0 | 0 | 0 | 0 |
Step 2 — Column reduction. Column minima are — no change.
Step 3 — Assign the zeros.
- single zero at assign .
- single zero at assign .
- single zero at assign .
- (dummy) takes the only column left, (a zero) .
Four independent zeros — optimal. …
Unlock everything free for 14 days
- Full step-by-step solutions
- Concept-first explanations
- Methods, shortcuts & mistakes
- PYQ mapping + timed mock tests
Full access for 14 days. No credit card required.