1. **Problem Statement:** A car hire company has one car at each of five depots a, b, c, d, and e. A customer in each of five cities A, B, C, D, and E requires a car. The distances (in km) between depots and cities are given. We need to assign cars to cities to minimize total distance traveled. 2. **Method:** This is an assignment problem, solved using the Hungarian Algorithm which finds the minimum cost matching in a cost matrix. 3. **Distance matrix:** $$\begin{bmatrix} 200 & 150 & 180 & 200 & 250 \\ 180 & 200 & 120 & 140 & 150 \\ 210 & 230 & 250 & 270 & 250 \\ 170 & 180 & 210 & 230 & 200 \\ 180 & 180 & 160 & 190 & 200 \end{bmatrix}$$ 4. **Step 1: Row reduction** (subtract minimum of each row from all elements in that row): - Row A min = 150, new row A: $[200-150, 150-150, 180-150, 200-150, 250-150] = [50, 0, 30, 50, 100]$ - Row B min = 120, new row B: $[180-120, 200-120, 120-120, 140-120, 150-120] = [60, 80, 0, 20, 30]$ - Row C min = 210, new row C: $[210-210, 230-210, 250-210, 270-210, 250-210] = [0, 20, 40, 60, 40]$ - Row D min = 170, new row D: $[170-170, 180-170, 210-170, 230-170, 200-170] = [0, 10, 40, 60, 30]$ - Row E min = 160, new row E: $[180-160, 180-160, 160-160, 190-160, 200-160] = [20, 20, 0, 30, 40]$ 5. **Step 2: Column reduction** (subtract minimum of each column from all elements in that column): - Column 1 min = 0, no change - Column 2 min = 0, no change - Column 3 min = 0, no change - Column 4 min = 20, new column 4: $[50-20, 20-20, 60-20, 60-20, 30-20] = [30, 0, 40, 40, 10]$ - Column 5 min = 30, new column 5: $[100-30, 30-30, 40-30, 30-30, 40-30] = [70, 0, 10, 0, 10]$ 6. **Reduced matrix:** $$\begin{bmatrix} 50 & 0 & 30 & 30 & 70 \\ 60 & 80 & 0 & 0 & 0 \\ 0 & 20 & 40 & 40 & 10 \\ 0 & 10 & 40 & 40 & 0 \\ 20 & 20 & 0 & 10 & 10 \end{bmatrix}$$ 7. **Step 3: Assignment** - Assign city A to depot b (0 cost) - Assign city B to depot d or e (both 0 cost), choose depot d - Assign city C to depot a (0 cost) - Assign city D to depot e (0 cost) - Assign city E to depot c (0 cost) 8. **Final assignment:** - A → b (distance 150) - B → d (distance 140) - C → a (distance 210) - D → e (distance 200) - E → c (distance 160) 9. **Total minimum distance:** $$150 + 140 + 210 + 200 + 160 = 860$$ **Answer:** Assign cars as above to minimize total distance traveled to 860 km.