闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MAT021

Foundations of Operational Research and Analytics

Autumn 2020/21

1. (a) Solve the following linear programming problem by using the Simplex Method. Provide all the details and explanations.

Explicitly provide the optimal solution for the problem and the corresponding objective function value.

(b) Write the Dual problem for the problem in part (a).

(c) Write the Dual problem from part (b) in standard form, with non-negative right- hand side constants in the constraints.

(d) Suppose you need to ﬁnd a feasible basic solution for the problem in part (c) by using the Two-Phase Method. Write the problem you would have to solve in the ﬁrst phase of the Two-Phase Method. (Do not solve the problem.)

(e) Provide the solution of the Dual problem in part (b) by analysing the solution of the problem in part (a).

(f) A business executive has the option of investing money in two plans. Plan A guarantees that each pound invested will earn 70 pence in one year, and plan B guarantees that each pound invested will earn 戈2.00 in two years. Plan A al- lows yearly investments, while in plan B, only investments for periods that are multiples of two years are allowed. How should the executive invest 戈100,000 to maximise the earnings at the end of three years? Assume all the intermediate earnings are re-invested. Formulate this problem as a linear programming prob- lem. (Do not solve the problem.)

2. (a) A company is taking bids on four construction jobs. Three people have placed bids on the jobs. Their bids (in thousands of pounds) are given in the table below, where a * indicates that the person did not bid on the given job:

Person 1 can do only one job, but persons 2 and 3 can each do as many as two jobs. Formulate an LP/IP problem to minimise the cost of assigning persons to jobs. (Do not solve the problem.)

(b) Using the Branch-and-Bounds method, ﬁnd all the solutions to the following instance of the Knapsack Problem:

Use the ratio choice method to obtain solutions to the LP relaxations of the corresponding problems. Provide all the details and explanation, and draw a Branch-and-Bounds tree of sub-problems for the solution process.

3. (a) Consider the travelling salesman problem.

i. Explain how you would produce a solution using a greedy algorithm.

ii. Explain how you would produce a solution using random descent.

iii. Explain how you would produce a solution using tabu search.

(b) 4 towns are linked by the following road network.

Towns A and B are linked by a road of length 3.

Towns A and C are linked by a road of length 4.

Towns B and D are linked by a road of length 6

Towns C and D are linked by a road of length 4.

The council wish to locate a hospital along the road connecting B and D so that the maximum distance anyone has to travel from any of the four towns is minimised. Use Hakimi’s Algorithm to ﬁnd the optimal location.

4. (a) A manufacturing company has 4 jobs A, B, C, D that need to be each completed in turn on Machine 1 followed by Machine 2. The times each job takes on each machine are as follows:

(b) A company that make roadsweepers is planning its production for the next four months. Although it knows the demand for its product in months 3 and 4, it is uncertain about the demand for the ﬁrst two months. It believes the demand for its product is as follows:Use Johnsons Algorithm to ﬁnd the sequence that minimises the makespan. Find the makespan of your solution by drawing a suitable Gantt chart.

The company can make up to 4 roadsweepers per month and it costs f5, 000 to make one roadsweeper, f9, 500 to make two roadsweepers, f13, 000 to make three roadsweepers and f16, 000 to make four roadsweepers. Storing a roadsweeper costs f1, 000 per month and they can store up to three roadsweepers at any time.

Given the company starts this period with zero roadsweepers in stock and wishes to end the four months with zero in stock, use dynamic programming to ﬁnd the optimal production plan. Assume that the company will not allow the possibility of not being able to meet the demand or having more than three roadsweepers in stock.