闪电代写 -代写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

2020/21

1. (a) The linear programming problem

maximise z = subject to:

5x1 + 8x2

x1 + x2

5x1 + 9x2

x1 , x2

< 6

< 45

> 0

has the following solution (in the ﬁnal Simplex tableau):

x1 x2 s1 s2

Solution

0 0 5/4 3/4

165/4

1 0 9/4 -1/4 0 1 -5/4 1/4

9/4

15/4

i. Perform sensitivity analysis on the right-hand side value of the ﬁrst constraint of the LP problem.

[5 marks]

ii. Find a solution to the following linear programming problem, without re- solving it from scratch: [8 marks]

maximise z = 5x1 + 8x2 + 2x3

subject to: x1 + x2 + x3 < 6

5x1 + 9x2 + 2x3 < 45

x1 , x2 , x3 > 0.

Provide all necessary details and explanation.

(b) Find the optimal value of the objective function of the following LP problem by directly solving its dual problem:

maximise z = 3x1 · 14x2 · 2x3

subject to: ·3x1 + 2x2 · 2x3 > ·20

x1 , x2 , x3 > 0

Provide all the details.

[12 marks]

2. (a) A coach company has two attractive contracts lined up for a particular date. One contract is to provide coaches for a train replacement service. The train com- pany would need at most 6 coaches. The other contract is to provide additional coaches for a service to France, for which no more than 5 coaches are required. The company has 8 coaches and 12 drivers. Trips to France require 2 drivers per coach, whereas train replacement coaches require only one driver. The company feels that for goodwill, at least one coach should be contracted to each client. The proﬁt is E150 for each coach going to France and E100 for each coach operating as part of the train replacement service.

i. Formulate the problem of proﬁt maximisation subject to constraints as a lin-

ear programming problem to help the company to maximise their total proﬁt. [8 marks]

ii. Find an optimal solution to the LP problem graphically and state how many coaches should be provided for each of the two contracts. [5 marks]

(b) A brewer sells three types of beer, denoted by A, B, and C . They can make a proﬁt of E10 on a vat of beer of type A, E5 on each vat of beer of type A, but have a loss of E2 on each vat of type C beer. They have a limited amount of two ingredients, yeast and hops.

They would like to maximise their proﬁt while ensuring they do not use too much yeast or hops. Also, they are committed to a contract to supply a certain amount of type C beer. They have formulated the following linear programming problem to represent their problem:

maximise z = subject to:

10xA + 5xB · 2xC

3xA + 2xB + xC

4xA + 2xB + 2xC

xA , xB , xC

< 80 (constraint on yeast) < 100 (constraint on hops) > 20 (constraint on contract) > 0, integer,

where xA , xB , xC are respectively the number of vats of beer A, B, and C that the brewer should produce.

The ﬁnal tableau providing an optimal solution to the problem looks as follows:

xA xB xC s1 s2 s3

Solution

0 0 0 0 5/2 7

1/2

-3/4

1/4

-1/2

1/2

-1

i. State which constraints are tight and which are slack for this solution. What

is the value of P? Provide all the details and explanation. [5 marks]

ii. How would the formulation of the LP/IP problem change if there was an additional requirement that the value of xA should be either 0 or between 10 and 25? Provide all the necessary details and explanation. [7 marks]

3. (a) Provide an Integer Programming formulation of the Travelling Salesman Prob- lem (TSP). Explain the meaning of all parameters, variables, and constraints and show how the formulation prevents subtours. [9 marks]

(b) Demonstrate whether the Travelling Salesman problem is unimodular. State the signiﬁcance of your answer. [5 marks]

(c) Explain how you would use a greedy heuristic to produce a solution to the TSP. State one advantage and one disadvantage of a greedy heuristic. [4 marks]

(d) Explain how you would use simulated annealing to produce a solution to the TSP. Include in your answer a deﬁnition of the cost function, neighbourhood and start- ing solution and state any parameters that are required. State one advantage and one disadvantage of simulated annealing. [7 marks]

4. (a) A company wish to produce the optimal ordering of 5 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:

Job

Time on Machine 1 Time on Machine 2

Find the optimal ordering using Johnson’s Algorithm. Draw a Gantt chart of the jobs and state the corresponding makespan. [8 marks]

(b) A company that make generators must plan its production schedule for the next ﬁve months. They estimate the demand is as follows:

Month 1: 4

Month 2: 3

Month 3: 7

Month 4: 5

Month 5: 2

They will start month 1 with 1 generator in stock. It costs f1,000 to store a generator for one month. Each generator costs f5,000 to manufacture though the company saves f1,000 if they make more than 3 generators in a month (so for example making 3 generators costs f15,000 whereas making 4 generators costs f19,000). They can make a maximum of 5 generators per month. They wish to end Month 5 with 0 generators in stock. Use dynamic programming to determine how many generators the company should manufacture each month. Include all deﬁnitions in your answer. No marks will be awarded if a method other than dynamic programming is used. [17 marks]