Samacheer Kalvi Class 12 Business Maths Solutions Chapter 10 Operations Research Exercise 10.2

 

Question 1. What is the Assignment problem?
Answer: The Assignment Problem is a type of optimization problem where we need to assign 'm' number of jobs to 'n' number of machines. The main goal is to do this assignment in a way that minimizes the total cost. This means each job is given to only one machine, and each machine handles only one job, aiming for the lowest possible overall cost.
In simple words: It's about matching jobs to machines to find the cheapest way to get all the work done.

🎯 Exam Tip: Clearly define the variables (jobs, machines, costs) and state the objective (minimize total cost) when explaining the assignment problem.

 

Question 2. Give mathematical form of assignment problem.
Answer: The assignment problem can be written using mathematical terms. We use \( C_{ij} \) to represent the cost of assigning job 'i' to machine 'j'. We also use a variable \( x_{ij} \) which is either 1 (if job 'i' is assigned to machine 'j') or 0 (if it's not). The aim is to find an assignment that keeps the total cost as low as possible. This formulation helps in solving complex assignment scenarios systematically.

Then, \( x_{ij} = \begin{cases} 1, & \text{if } i^{th} \text{ job is assigned to } j^{th} \text{ machine} \\ 0, & \text{if } i^{th} \text{ job is assigned to } j^{th} \text{ machine} \end{cases} \)

\( x_{ij} \) missing in any cell means no assignment is made, so \( x_{ij} = 0 \). If \( x_{ij} \) is present, an assignment is made, so \( x_{ij} = 1 \).

The assignment model can be written in Linear Programming Problem (LPP) as follows:

Minimize \( Z = \sum_{i=1}^{m} \sum_{j=1}^{n} C_{ij} X_{ij} \)
Subject to the constraints:
\( \sum_{i=1}^{n} X_{ij} = 1, j = 1, 2, ..., n \)
\( \sum_{j=1}^{n} X_{ij} = 1, i = 1, 2, ..., n \)
and \( X_{ij} = 0 \text{ (or) } 1 \text{ for all } i, j \)

In simple words: This problem is about matching jobs to machines. We use numbers (0 or 1) to show if a job is assigned to a machine. The main goal is to find the lowest total cost while making sure each job gets one machine and each machine gets one job.

🎯 Exam Tip: Remember to clearly define the decision variables (\( x_{ij} \)) and the objective function (minimize cost) along with the row and column constraints for a complete mathematical formulation.

 

Question 3. What is the difference between Assignment Problem and Transportation
Answer: The Assignment Problem and Transportation Problem are both types of optimization problems, but they have key differences. The assignment problem focuses on a one-to-one matching where resources are assigned to tasks, while the transportation problem deals with distributing goods from various sources to multiple destinations to minimize shipping costs. Understanding these distinctions helps in applying the correct solving methods for each.

In simple words: The assignment problem needs an equal number of jobs and workers, focusing on who does what. The transportation problem moves things from many places to many other places, trying to find the cheapest route.

🎯 Exam Tip: When comparing, always highlight the 'one-to-one' nature of assignments versus the 'many-to-many' flow in transportation problems, and mention the balance condition for each.

 

Question 4. Three jobs A, B and C one to be assigned to three machines U, V and W. The processing cost for each job machine combination is shown in the matrix given below. Determine the allocation that minimizes the overall processing cost. (cost is in Rs per unit)
Answer: We need to assign three jobs (A, B, C) to three machines (U, V, W) to find the lowest possible total cost. First, we ensure the problem is balanced (equal rows and columns), which it is. We then use the Hungarian method steps to find the optimal assignment.

Initial Cost Matrix:

The given assignment problem is balanced.

Step 1. Row Reduction: Select the smallest element in each row and subtract this from all elements in that row.

Now, look for at least one zero in each row and each column. If every row and column has exactly one zero, we can proceed to Step 3, skipping Step 2 (Column Reduction) if it's not needed.

Step 3. Assignment: Mark zeros to make assignments. If a row has only one zero, mark it with a square (an assignment) and cross out other zeros in its column. If a column has only one zero, mark it and cross out other zeros in its row.

Since each row and each column now contains exactly one assignment, all three machines have been assigned a job.

Final Assignment and Cost:

The optimal total processing cost is Rs 46.
In simple words: First, we made numbers smaller in each row. Then we found the best matches for jobs to machines. We assigned Job A to Machine V (cost 15), Job B to Machine U (cost 10), and Job C to Machine W (cost 11). Adding these up gives us the lowest total cost of Rs 46.

🎯 Exam Tip: Always recheck the original cost matrix with your final assignments to ensure you pick the costs from the original table, not the reduced one, and verify all assignments are one-to-one.

 

Question 5. A computer centre has got three expert programmers. The centre needs three application programmes to be developed. The head of the computer centre, after studying carefully the programmes to be developed, estimates the computer time in minitues required by the experts to the application programme as follows. Assign the programmers to the programme in such a way that the total computer time is least.
Answer: We need to assign three programmers to three programs to minimize the total computer time. The number of rows (programmers) equals the number of columns (programs), so the problem is balanced. We will use the Hungarian method.

Initial Time Matrix:

The given assignment problem is balanced.

Step 1. Row Reduction: Select the smallest element in each row and subtract this from all elements in its row.

Step 2. Column Reduction: Select the smallest element in each column and subtract this from all elements in its column.

Step 3. Assignment: Examine rows with exactly one zero, mark it, and cross out other zeros in its column.

Step 4. Examine columns with exactly one zero, mark it, and cross out other zeros in its row.

All three assignments have now been made. The optimal assignment schedule and total cost are:

The optimal assignment (minimum) cost = Rs 280.
In simple words: We reduced the numbers in rows and columns to find the best spots (zeros). Then we picked one zero in each row and column without overlap. Programmer 1 gets Program R (80 min), Programmer 2 gets Program Q (90 min), and Programmer 3 gets Program P (110 min). This makes the total time 280 minutes, which is the lowest possible.

🎯 Exam Tip: When doing row and column reductions, ensure you subtract the smallest element correctly from *all* elements in that row or column. Double-check your final assignments against the *original* cost matrix.

 

Question 6. A departmental head has four subordinates and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulty. His estimates of the time man would take to perform each task is given below. How should the tasks to allocated to subordinates so as to minimize the total man-hours?
Answer: We need to assign four tasks to four subordinates to minimize the total man-hours. The number of rows (subordinates) equals the number of columns (tasks), so the problem is balanced. We will use the Hungarian method.

Initial Time Matrix (in hours):

The given assignment problem is balanced.

Step 1. Row Reduction: Select the smallest element in each row and subtract this from all elements in its row.

Step 2. Column Reduction: Select the smallest element in each column and subtract this from all elements in its column.

Step 3. Assignment: Examine the rows with exactly one zero, mark the zero with a square, and mark other zeros in its column with an 'X'.

Step 4. Mark other zeros in its row by 'X'.

Step 5. Cover all zeros with the minimum number of lines. Since we only have three assignments but four tasks, we need to draw lines. We can cover all zeros with three lines. Row S has no assignment, so it's not yet optimized.

Step 6. Develop a new revised tableau. Find the smallest element among those not covered by any line (which is 1 in this case). Subtract this smallest element from all uncovered cells. Add this smallest element to cells at the intersection of two lines. Covered cells not at an intersection remain unchanged.

Step 7. Repeat Step 3 (Assignment) until an optimal assignment is found (i.e., the number of assignments equals the number of rows/columns).

Step 8. Determine an assignment.

All four assignments have been made. The optimal assignment schedule and total time are:

The optimum time (minimum) = 41 Hrs.
In simple words: We used steps to reduce the time numbers and find zeros. Then we marked zeros to assign each subordinate to one task. P gets Task 1 (8 hrs), Q gets Task 3 (4 hrs), R gets Task 2 (19 hrs), and S gets Task 4 (10 hrs). The total minimum time is 41 hours.

🎯 Exam Tip: When covering zeros with lines, ensure you draw the minimum number of lines possible. If the number of lines is less than the number of rows/columns, further matrix reduction is needed.

 

Question 7. Find the optimal solution for the assignment problem with the following cost matrix.
Answer: We need to find the optimal assignment for salespersons to areas to minimize the total cost. The problem has an equal number of rows (salesmen) and columns (areas), so it is a balanced assignment problem. We will use the Hungarian method.

Initial Cost Matrix:

The given assignment problem is balanced.

Step 1. Row Reduction: Select the smallest element in each row and subtract this from all elements in its row.

Step 2. Column Reduction: Select the smallest element in each column and subtract this from all elements in its column.

Step 3. Assignment: Examine the rows with exactly one zero, mark the zero with a square, and mark other zeros in its column with an 'X'.

All four assignments have been made. The optimal assignment schedule and total cost are:

The Optimum cost (minimum) = Rs 37.
In simple words: We reduced the costs in each row and column. Then we picked the best matches for each salesman to an area. Salesman P goes to Area 3 (cost 8), Q to Area 4 (cost 6), R to Area 1 (cost 13), and S to Area 2 (cost 10). The smallest total cost for all assignments is Rs 37.

🎯 Exam Tip: Always double-check that after all reductions and assignments, each row and column has exactly one assigned zero. Also, remember to calculate the total cost using the *original* cost matrix values.

 

Question 8. Assign four trucks 1, 2, 3 and 4 to vacant spaces A, B, C, D, E and F so that distance travelled is minimized. The matrix below shows the distance.
Answer: We need to assign four trucks to six vacant spaces to minimize the total distance. Since the number of columns (trucks, 4) is less than the number of rows (vacant spaces, 6), this is an unbalanced assignment problem. To balance it, we introduce two dummy columns (\( d_1, d_2 \)) with zero entries.

Initial Distance Matrix:

The number of columns (4) is less than the number of rows (6), so it's unbalanced. To balance, we introduce two dummy columns \( d_1 \) and \( d_2 \) with 0 entries.

The revised assignment problem is:

Step 1. Row Reduction: It is not necessary since each row already contains a zero entry due to the dummy columns. So, we can go to Step 2.

Step 2. Column Reduction: Select the smallest element in each column and subtract this from all elements in its column.

Step 3. (Assignment) Examine each row for a single zero, mark it, and cross out other zeros in its column. Then, examine each column for a single zero, mark it, and cross out other zeros in its row.

Here, all four assignments have been made. We can assign \( d_1 \) to D and \( d_2 \) to E. This means truck D and E are not assigned a real truck. The optimal assignment schedule and total distance are:

The Optimum Distance (minimum) = 12 units.
In simple words: Since there are more spaces than trucks, we added fake (dummy) trucks with zero distance. Then, we found the best matches to minimize distance. A gets Truck 3 (3 units), B gets Truck 2 (2 units), C gets Truck 1 (4 units), and F gets Truck 4 (3 units). Spaces D and E are assigned to dummy trucks, meaning they don't get a real truck. The lowest total distance is 12 units.

🎯 Exam Tip: Remember to balance unbalanced assignment problems by adding dummy rows or columns with zero costs/distances. This ensures the matrix is square before applying the Hungarian method.

 

Question 8. Assign four trucks 1, 2, 3 and 4 to vacant spaces A, B, C, D, E and F so that distance travelled is minimized. The matrix below shows the distance.

Answer: The problem is unbalanced because there are more rows (vacant spaces) than columns (trucks). To balance it, we add two extra 'dummy' columns, d\(_{1}\) and d\(_{2}\), filling them with zeros. This makes the matrix square and ready for the assignment method. This method helps to ensure that all tasks or resources are considered even when quantities don't match initially.
The revised assignment problem is:

**Step 1:** Select the smallest element in each row and subtract this from all the elements in its row. (Since each row already contains a zero entry, this step is not necessary. We can proceed to Step 2.)
**Step 2:** Select the smallest element in each column and subtract this from all the elements in its column.

**Step 3 (Assignment):** We look at each row. If a row has only one zero, we mark it (assign it) and cross out any other zeros in its column. If there are multiple zeros, we move to Step 4. (In this case, since there are multiple zeros in some rows and columns, we proceed to Step 4).
**Step 4:** Examine the columns with exactly one zero. Mark that zero (assign it) and cross out any other zeros in its row.

**Step 5:** We continue the process of marking zeros and crossing out other zeros until all possible assignments are made. At this point, we can assign dummy column d\(_{1}\) to D and dummy column d\(_{2}\) to E to complete the assignments.

The optimal assignment schedule and total distance is:

The optimum total distance (minimum) is Rs 12 units.
In simple words: We need to match trucks to parking spots in a way that minimizes the total distance traveled. Since there are more spots than trucks, we added 'fake' trucks (dummy columns) to balance the problem. Using a step-by-step assignment method, we find the best matches to achieve the lowest total distance, which comes out to be 12 units.

🎯 Exam Tip: Remember to always check if the assignment matrix is balanced (number of rows equals number of columns) first. If it's not, add dummy rows or columns with zero costs to make it balanced before starting the Hungarian algorithm steps.