Part D: 6 marks A factory has five workers, Anne, Bob, Carol, Dave and Ethan. It also has 5 tasks which must be done. Each worker does the tasks with a different efficiency. Apply the branch and bound strategy to allocate the tasks with minimum overall cost, when each task must be completed by a different worker. The cost for each worker to do the tasks is given in the following table: Task 1 Task 2 Task 3 Task 4 Task 5 Anne $4.00 $8.00 $8.00 $3.00 $4.00 Bob $9.00 $5.00 $5.00 $2.00 $7.00 Carol $4.00 $2.00 $4.00 $1.00 $3.00 Dave $7.00 $9.00 $6.00 $5.00 $8.00 Ethan $3.00 $6.00 $4.00 $4.00 $5.00 a) Describe a suitable method to calculate the lower bound value for all similar problems, where the total number of workers and the total number of tasks are equal? (1 mark) b) Describe a method to calculate a suitable upper bound for similar problems? (1 mark) c) Use the branch and bound strategy to find the most cost-efficient allocation of tasks to workers. Show the details of the expansion and pruning (branch and bound) of the decision tree along with reasons. (4 marks) Part D: 6 marks A factory has five workers, Anne, Bob, Carol, Dave and Ethan. It also has 5 tasks which must be done. Each worker does the tasks with a different efficiency. Apply the branch and bound strategy to allocate the tasks with minimum overall cost, when each task must be completed by a different worker. The cost for each worker to do the tasks is given in the following table: Task 1 Task 2 Task 3 Task 4 Task 5 Anne $4.00 $8.00 $8.00 $3.00 $4.00 Bob $9.00 $5.00 $5.00 $2.00 $7.00 Carol $4.00 $2.00 $4.00 $1.00 $3.00 Dave $7.00 $9.00 $6.00 $5.00 $8.00 Ethan $3.00 $6.00 $4.00 $4.00 $5.00 a) Describe a suitable method to calculate the lower bound value for all similar problems, where the total number of workers and the total number of tasks are equal? (1 mark) b) Describe a method to calculate a suitable upper bound for similar problems? (1 mark) c) Use the branch and bound strategy to find the most cost-efficient allocation of tasks to workers. Show the details of the expansion and pruning (branch and bound) of the decision tree along with reasons. (4 marks)