Let's solve the **assignment problem** where 5 trucks (A, B, C, D, E) need to be assigned to 5 routes (1, 2, 3, 4, 5) such that the total cost is minimized. We will use the **Hungarian Method** (also called the Assignment Method) step by step. --- ### Step 1: Write the Cost Matrix | | 1 | 2 | 3 | 4 | 5 | |------|---|---|---|---|---| | **A**| 4 | 6 | 7 | 5 | 8 | | **B**| 5 | 4 | 3 | 2 | 5 | | **C**| 9 | 8 |10 | 5 | 6 | | **D**| 8 | 3 | 4 | 6 | 5 | | **E**| 7 | 5 | 6 | 5 | 9 | --- ### Step 2: Row Reduction Subtract the smallest value in each row from all elements in that row. - Row A min = 4; subtract 4 from row A - Row B min = 2; subtract 2 from row B - Row C min = 5; subtract 5 from row C - Row D min = 3; subtract 3 from row D - Row E min = 5; subtract 5 from row E | | 1 | 2 | 3 | 4 | 5 | |------|---|---|---|---|---| | **A**| 0 | 2 | 3 | 1 | 4 | | **B**| 3 | 2 | 1 | 0 | 3 | | **C**| 4 | 3 | 5 | 0 | 1 | | **D**| 5 | 0 | 1 | 3 | 2 | | **E**| 2 | 0 | 1 | 0 | 4 | --- ### Step 3: Column Reduction Find the minimum value in each column and subtract it from the column. - Col 1 min = 0; subtract 0 from column 1 - Col 2 min = 0; subtract 0 from column 2 - Col 3 min = 1; subtract 1 from column 3 - Col 4 min = 0; subtract 0 from column 4 - Col 5 min = 1; subtract 1 from column 5 | | 1 | 2 | 3 | 4 | 5 | |------|---|---|---|---|---| | **A**| 0 | 2 | 2 | 1 | 3 | | **B**| 3 | 2 | 0 | 0 | 2 | | **C**| 4 | 3 | 4 | 0 | 0 | | **D**| 5 | 0 | 0 | 3 | 1 | | **E**| 2 | 0 | 0 | 0 | 3 | --- ### Step 4: Assign Zeros (Hungarian Method) We need to cover all zeros with a minimum number of lines and check if we can make assignments. #### **First, mark independent zeros (no row/col has more than one assigned zero):** - **Row A:** 1 zero (col 1) - **Row B:** 2 zeros (col 3, 4) - **Row C:** 2 zeros (col 4, 5) - **Row D:** 2 zeros (col 2, 3) - **Row E:** 3 zeros (col 2, 3, 4) Let's proceed to assign zeros: 1. **Row A** has only one zero (col 1). Assign A-1. 2. **Row D** now has only one remaining zero (col 2). Assign D-2. 3. **Row B** now has only one zero left (col 3). Assign B-3. 4. **Row C** now has two zeros (col 4, 5). Let's pick col 5 for C (arbitrary, will check if better assignment possible later). 5. **Row E** now has one zero left (col 4). Assign E-4. Let's see if this is a valid assignment: - **A-1** - **D-2** - **B-3** - **E-4** - **C-5** Check if any two assignments are in the same column: all are unique, so this is a valid assignment. --- ### Step 5: Calculate the Total Cost Now substitute back to the **original cost matrix**: - **A-1:** 4 - **D-2:** 3 - **B-3:** 3 - **E-4:** 5 - **C-5:** 6 **Total cost = 4 + 3 + 3 + 5 + 6 = 21 (in N000) = N21,000** --- ### Step 6: Conclusion **Assignments:** - Truck A → Route 1 - Truck B → Route 3 - Truck C → Route 5 - Truck D → Route 2 - Truck E → Route 4 **Minimum Total Cost:** **N21,000** --- #### **Summary Table** | Truck | Route | Cost (N000) | |-------|-------|-------------| | A | 1 | 4 | | B | 3 | 3 | | C | 5 | 6 | | D | 2 | 3 | | E | 4 | 5 | |**Total**| | **21** | --- **Therefore, the minimum total cost is N21,000, and the assignments are as above.**

Let's carefully solve the assignment problem to minimize total costs for assigning trucks to routes. --- ### Given Data: | Truck | Route 1 | Route 2 | Route 3 | Route 4 | Route 5 | |--------|---------|---------|---------|---------|---------| | **A** | 4 | 6 | 7 | 5 | 8 | | **B** | 5 | 4 | 3 | 2 | 5 | | **C** | 9 | 8 | 10 | 5 | 6 | | **D** | 8 | 3 | 4 | 6 | 5 | | **E** | 7 | 5 | 6 | 5 | 9 | --- ### Step 1: Row Reduction Subtract the minimum value in each row from all entries in that row: - Row A min = 4 → subtract 4: - A: 0, 2, 3, 1, 4 - Row B min = 2 → subtract 2: - B: 3, 2, 1, 0, 3 - Row C min = 5 → subtract 5: - C: 4, 3, 5, 0, 1 - Row D min = 3 → subtract 3: - D: 5, 0, 1, 3, 2 - Row E min = 5 → subtract 5: - E: 2, 0, 1, 0, 4 **Updated matrix:** | | 1 | 2 | 3 | 4 | 5 | |------|---|---|---|---|---| | **A**| 0 | 2 | 3 | 1 | 4 | | **B**| 3 | 2 | 1 | 0 | 3 | | **C**| 4 | 3 | 5 | 0 | 1 | | **D**| 5 | 0 | 1 | 3 | 2 | | **E**| 2 | 0 | 1 | 0 | 4 | --- ### Step 2: Column Reduction Subtract the minimum value in each column from all entries in that column: - Column 1 min = 0 → no change - Column 2 min = 0 → no change - Column 3 min = 1 → subtract 1: - C: 4→3, D: 1→0, others unchanged - Column 4 min = 0 → no change - Column 5 min = 1 → subtract 1: - A: 4→3, others unchanged **Updated matrix after column reduction:** | | 1 | 2 | 3 | 4 | 5 | |------|---|---|---|---|---| | **A**| 0 | 2 | 3 | 1 | 3 | | **B**| 3 | 2 | 1 | 0 | 2 | | **C**| 4 | 3 | 3 | 0 | 0 | | **D**| 5 | 0 | 0 | 3 | 1 | | **E**| 2 | 0 | 0 | 0 | 3 | --- ### Step 3: Cover Zeros Identify the minimum number of lines needed to cover all zeros: Zeros are at positions: - A: col 1 - B: col 4 - C: cols 4, 5 - D: cols 2, 3 - E: cols 2, 3, 4 Possible assignment: - Assign A to Route 1 (zero at A-1) - Assign D to Route 2 (zero at D-2) - Assign B to Route 4 (zero at B-4) - Assign C to Route 5 (zero at C-5) - Assign E to Route 3 (zero at E-3) Check if all zeros are covered with 5 lines: yes, since each zero is in a unique row/column combination. --- ### Step 4: Final Assignments and Cost Calculation Now, map these assignments back to the original costs: | Truck | Route | Original Cost | |--------|--------|---------------| | A | 1 | 4 | | D | 2 | 3 | | B | 4 |