1. A marathon runner wishes to make her own sport drink.   She intends to use three main ingredients: apple juice, carrot juice, and pineapple juice, plus some water and salt.   The following table shows, for each ingredient, the amount of carbohydrate and protein content, and the cost:

The runner’s nutritionist recommends that each litre of the drink should contain at least 20 grams of carbohydrate, at least 4 grams of protein, and at most 0.9 litres of fruit juice. In order to make one litre at minimum cost, the runner solves the following linear program with A, C, P as decision variables defined as number of litres of Apple Juice, Carrot Juice and Pineapple Juice respectively:

min 0.75 A + 0.9 C + 1.3 P

st

3  A    +    4    C  +  5  P      4                       (2)

A    +          C  +      P      0.9                   (3)

A, C, P  0.

The optimal simplex tableau for this problem is:

(a) This tableau is optimal.   Explain how you know it is optimal and explain the optimal solution in words.

(10% marks)

(b) From the information in the simplex tableau, deduce the slack and shadow price of each of the three constraints.  Also state which of the three constraints, if any, are binding.

(30% marks)

(c) Suppose the price of A were uncertain.   Using the information in the simplex tableau, compute the range of values of the price of A for which the current optimal solution remains optimal.

(20% marks)

(d) Would the optimal solution change if actually only 3.9 grams of protein were needed per litre?  What about the optimal cost?  Explain your answer using the simplex tableau.

(20% marks)

(e) The nutritionist is concerned that the proposed mixture contains too much carotene (a chemical present in carrot juice).  She now recommends that the drink contain at most 0.4 litres of carrot juice.  Explain how you could find the new optimal solution without starting again from the beginning. (You are not required to actually compute that solution.)

(20% marks)

Question 2

Suppose you are faced with the following problem: your company is thinking of opening new depots to supply wood to sofa manufacturers in Lancashire. Six locations have been                identified which are suitable to open a depot which can store wood. However, there is a          constraint that you can only open at most 4 out of the possible 6 depots. There are 7 clients     (sofa manufacturers) in Lancashire and each of these clients should be supplied from exactly  one depot. There is no restriction on the number of clients that can be supplied from each        depot. The problem is to decide which depots to open and how to assign each client to exactly one opened depot such that total profits are maximized. The profit matrix is given below:

(a) Devise a local search heuristic and comment on the size of the neighbourhood.          (35% of marks)

(b) Find the local optimum in the neighbourhood proposed in part (a). Explain if this      local optimum is also the global optimum by clearly giving the reasoning. Is this true in general for any profit matrix?

(30% of marks)

(c) Give an integer programming formulation for the problem.                  (35% of marks)

Question 3

The Skein Haulage Company (SHA) has one surplus truck at each of four of its depots at Atown, Beeville, Caster and Deeport.  Four customer companies, JJ, KK, LL and MM have each requested one additional truck. SHA reckon that the profit they will make (in hundreds of pounds) from supplying an additional truck to each customer from each location is given in the following table:

Customer

(a) Use the assignment algorithm to find which depot should be used to provide the truck for each customer.  Explain the optimal allocation and profit in words.  Describe any alternative optimal solutions.

(40% of marks)

(b) Would the optimal solution change if the profit of supplying a truck to JJ from Deeport increased from £300 to £400?  What about the optimal profit?

(20% of marks)

(c) Would the optimal solution change if the profit of supplying a truck to JJ from Atown increased from £900 to £1000?  What about the optimal profit?

(20% of marks)

(d)  Suppose a new constraint arose: if the Atown truck is assigned to either JJ or LL, then the Beeville truck must be assigned to MM.  Formulate the resulting problem as a 0- 1 integer      program.

(20% of marks)