Exam January 2013, questions and answers - Exam with solutions PDF

Preview

Summary

Exam with solutions ...

Description

PAPER CODE NO. MATH 261

EXAMINER: Dr. A.Piunovskiy, TEL.NO. 44737 DEPARTMENT: Mathematical Sciences

JANUARY 2013 EXAMINATIONS

Introduction to methods of operational research

Time allowed: Two and a half hours

INSTRUCTIONS TO CANDIDATES: Full marks will be given for complete answers to five questions. Only the best five answers will be taken into account.

Paper Code MATH 261

Page 1 of 5

CONTINUED

1. Consider the Main Convex Program: minimise f (x, y) = y 2 − ln(x + 1) subject to g(x, y ) = x + y ≤ 5,

x, y ≥ 0.

Construct the Lagrangean L for this problem and write down all the necessary and sufficient conditions for a point (x, y, λ) to be a saddle point of the Lagrangean. [6 marks] Find the saddle point of the Lagrangean. (You must consider all cases λ = 0, λ > 0 etc.) Hence give the solution to the original Convex Program. [7 marks] (b) For the problem minimise f (x, y) = x1 + y2 + x + y carry out one iteration of the Newton-Raphson method, starting from the initial point (x0 , y0 ) = (0.5, 1). [7 marks]

2. (a) A company manufactures two types of computer, type A and type B. Manufacturing a type A computer requires 4 hours of labour and 2 computer chips. Each type B computer requires 2 hours of labour and 1 computer chip. There are 800 hours of labour and 700 chips available per month. The company is able to sell up to 100 type A computers and up to 400 type B computers per month. For each type A computer sold the company makes a profit of £150, while the profit on each type B computer is £50. The company’s aim is to maximise monthly profits. Formulate this problem as a linear program. Sketch the feasible region of the problem, and find the optimal solution. Which, if any, of the constraints are redundant and which are binding at optimality? [14 marks] (b) Sketch the feasible region for the linear program maximise x0 = x1 + 2x2 subject to 3x1 + 2x2 ≤ 6 2x1 + 3x2 ≤ 6 x1 , x2 ≥ 0 Use your sketch to solve this problem graphically, i.e. find the optimal solution. [6 marks]

Paper Code MATH 261

Page 2 of 5

CONTINUED

3. (a) Solve the following Transportation Problem starting from the initial basic feasible solution given.

Q

P 2

R 8

A 8

B

2

5

C

10

6

10 13

5

S 6

5

8

4

6

5

5

5

[12 marks] (b) Three orchards supply crates of oranges to four retailers. The daily demands from retailers 1, 2, 3 and 4 are 150, 150, 400 and 100 crates respectively. Supply at the orchards is dictated by available labour, the daily supply available from orchards A, B, C being 300, 300 and 200 crates respectively. The transportation costs (£) per crate from the orchards to the retailers are given in the table below. Retailer 1 2 3 4 A 1 2 3 2.5 Orchard B 2 4 2.8 2.7 C 1.5 3 5 3 Formulate this problem as a transportation problem in tableau form and give an initial feasible solution using the Least-Cost method. [4 marks] Suppose now that the demand from retailer 1 increases to 250 crates per day. It is possible for Orchard A to supply more crates by using overtime labour, at an additional cost of £1.50 per crate; orchards B and C do not offer this option. Explain how the formulation of the original problem may be modified for this new situation, writing down an appropriate modified tableau. [4 marks]

Paper Code MATH 261

Page 3 of 5

CONTINUED

4. (a) For a maximisation bicriterion problem with objectives Z1 and Z2 define what it means for a point y to be inferior to a point x. Sketch in objective space the set of points inferior to a given point (Z1 (x) , Z2 (x)). [3 marks] (b) Consider the bicriterion problem maximise {Z1 , Z2} subject to x+y ≥ 2 x + 3y ≤ 9 3x + y ≤ 9 x, y ≥ 0 (i) Sketch the feasible region for this problem.

[4 marks]

(ii) If Z1 = x + 5y and Z2 = 7x + y, state the values of x, y, Z1, Z2 at each vertex of the feasible region. Identify which of these vertices are inferior solutions and hence find the Non-Inferior Set (NIS). [4 marks] (iii) Let Z(w) = (1 − w)Z1 + wZ2, where 0 ≤ w ≤ 1. Determine, as a function of w, the set of points of the feasible region for which Z(w) is maximised. [5 marks] (iv) Suppose the goals for Z1 and Z2 are G1 = 15 and G2 = 21 respectively. Formulate a goal program in which the penalties for undershooting goals G1 and G2 are 2 and 1 per unit, respectively, and where there is no penalty for overshooting. [4 marks] 5. (a) Using the primal simplex method, solve the linear program maximise x0 = 3x1 + Cx2 subject to 2x1 + 3x2 ≤ 60 2x1 + x2 ≤ 30 x1 ≤ x2 + 3 x2 ≤ 18 x1 , x2 ≥ 0 for C = 1.

[12 marks]

(b) For what range of C does the optimal solution remain the same? [4 marks] (c) Formulate the dual linear program for C = 1. [4 marks] Paper Code MATH 261

Page 4 of 5

CONTINUED

6. Consider the following linear program: minimise y0 = 30y1 + 20y2 + 18y3 + 4y4 subject to

y1 + y2 + y3 − y4 ≥ 1 3y1 + y2 − y3 + y4 ≥ 5 y 1 , y2 , y3 , y4 ≥ 0 (a) Formulate the dual to it using variables x1 , x2 and solve the dual graphically. [10 marks] (b) Write down all the complementary slackness conditions and use them to find the optimal solution y1∗, y2∗, y ∗3 , y4∗ to the original linear program. [10 marks]

7. (a) Consider a single-item static continuous review model in which the setup cost is K per order, the demand rate is D units per unit time and the holding cost is h per unit per unit time. If the order size is y units, then the Total Cost per Unit time is given by T CU (y) =

KD hy + y 2

p and the Economic Order Quantity y ∗ is given by y ∗ = 2KD/h. Calculate the values of y ∗ and T CU(y ∗ ) if K = £140 per order, D = 100 units per day and h = 10 pence per unit per day. If it is learned that orders must be in multiples of 50 units, determine the order size which would lead to minimal cost. If the company’s working week is 5 days long, then considering the time between orders, what order size would you finally suggest, and why? [6 marks] (b) Consider now a single-item static continuous review model in which shortages are permitted. Suppose the set-up cost is K per order, the demand rate is D units per unit time, the holding cost is h per unit per unit time, and the shortage cost is p per unit per unit time. Sketch a graph of stock level against time, and produce the formula for T CU(y, w), where the order size is y units and shortages of up to w units are permitted to occur. [6 marks] Find expressions in terms of h, p, K and D for the optimal values of y and w. [8 marks]

Paper Code MATH 261

Page 5 of 5

END...