MAT021 Foundations of Operational Research and Analytics Autumn 2022/23
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Academic Year: 2022/23
Examination Period: Autumn
Module Code: MAT021
Examination Paper Title: Foundations of Operational Research and Analytics
Duration: 2 hours
1. (a) Betty plans to invest a total of ↔17, 000 in mutual funds, certificates of deposit, and a high yield savings account. She doesn’t want to invest more in mutual funds than the sum of her certificates of deposit and savings because of the risk involved in mutual funds. She also wants the amount in savings to be at least half the amount in certificates of deposit. Her expected returns are 8.5% on the mutual funds, 5% on the certificates of deposit, and 3.7% on savings. She is allowed to deposit nothing into the high yield savings account, or any amount from ↔3, 000 to ↔7, 000, and the deposit must be in ↔1, 000’s.
Help Betty decide how much money to invest in each area in order to have the maximum possible total return on her investments by formulating this as a lin- ear/integer programming problem. Clearly describe your decision variables, ob-
jective function, and constraints. Do not solve the LP/IP problem. [13 marks]
(b) Solve the following linear programming problem by using the Dual Simplex Method:
Clearly provide the optimal solution for the problem and the corresponding ob-jective function value. [12 marks]
2. (a) A farmer wishes to ensure he feeds his cows with sufficient nutrients of type A, B, and C, while minimising the cost of food he uses. There are three types of food available, denoted by X, Y, and Z, and they cost ↔10, ↔7, and ↔8 per bag, respectively. A bag of type X contains 1 unit of A, 2 units of B, and 1 of C. A bag of type Y contains 2 units of A, 1 of B, and 1 of C. Finally, a bag of type Z contains 3 units of A, 2 of B, and 1 of C. They have formulated the following linear programming problem to represent their problem:
where x, y, and z are the number of bags of food X, Y, and Z, respectively, that the farmer should purchase.
The optimal tableau to the problem, after it is solved using the Dual Simplex Method, is
i. State which constraints are tight and which have slack or excess. Justify your answer. Show that P = −58. [3 marks]
ii. Given the right-hand side values of the constraints change from 14, 10, 8 to 12, 10, 6, respectively, find the new optimal solution. What is the value of the objective function for your new solution? [4 marks]
(b) Using the Branch-and-Bounds method, solve the following instance of the Knap- sack Problem:
maximise 8x1 + 6x2 + 7x3 + 12x4 + 9x5
subject to 3x1 + 2x2 + 4x3 + 6x4 + 4x5 ≤ 10
x1 , x2 , x3 , x4 , x5 = 0 or 1
Use the ratio choice method to obtain solutions to the LP relaxations of the cor- responding problems. Provide all the necessary details and explanation, and draw a Branch-and-Bounds tree of sub-problems for the solution process. [18 marks]
3. (a) Describe how you would solve the travelling salesman problem using:
i. A greedy algorithm [3 marks]
ii. Steepest descent. Your answer should include the cost function, the starting solution, the neighbourhood and the stopping condition. [5 marks]
iii. A memetic algorithm. Your answer should include the fitness function, the starting population, the parent selection mechanism, the crossover, the mu- tation and the stopping condition. [7 marks]
(b) A company wish to produce the optimal ordering of five jobs on two machines where each job has to be processed on Machine 1 and then on Machine 2. The times of processing each job on each machine are as follows:
i. Find the optimal ordering using Johnson’s Algorithm and state the corre- sponding makespan. [7 marks]
ii. Explain how you would apply Johnson’s Algorithm if a set of jobs have to be processed on four machines. [3 marks]
4. A company have five lorries to assign to three warehouses. Up to three lorries can be assigned to any one warehouse. The following table shows the financial profit that will be achieved by the company in hundreds of pounds according to the number of lorries allocated to each warehouse:
Use dynamic programming to find the allocation of lorries to warehouses that max- imises the profit. No marks will be awarded if a method other than Dynamic Pro- gramming is used. Assume that all lorries are allocated to a warehouse. Include all definitions in your answer. [25 marks].
2023-08-09