Question 1

A steel company must decide how to allocate its weekly time on a rolling mill. The mill takes unfinished slabs of steel as input and can produce two semi-finished products: bands and       coils. The mill's two products come off the rolling line at different rates and have different     profitabilities. To further complicate matters, weekly production amounts must be limited to  not exceed maximum demands. The following data is available.

The question now facing the company is as follows: If 40 hours of production time are   available each week, how many tons of bands and coils should be produced to maximise profit?

a)  Formulate this problem as a linear programme. Clearly define your decision variables (15 marks)

b)   Solve the problem using the graphical method. (15 marks)

c)  Write the simplex tableau for the optimal solution obtained in part b. (20 marks)

d)  By how much can each of the profitabilities change for the optimal solution to stay the same? (20 marks)

e)  Every ton of bands produced results in 90 kg of waste and every ton of coils gives 200 kg of waste. A new policy is adopted to restrict waste to 810000 kg. Add this new       constraint and using your solution in part c resolve the resulting linear programme      using dual simplex.  (30 marks)

Question 2

Consider an integer programme of the form:

Maximize  ux + vy

s.t. 5x + 6y <= 33

x + 3y <= 10

x, y: >=0, integer

where u and v are non-negative rational parameters.

a)   Give an example of u and v for which the optimal solution to the linear relaxation of this problem is fractional. (10 marks)

b)  Give a valid inequality that cuts off the linear relaxation in part a. (10 marks)

c)   Give an equivalent formulation for this problem whose linear relaxation has an optimal solution that has integer value for x and y for all u and v. (50 marks)

d)  Suppose you are interested in solving integer programmes in this family by Branch and Bound algorithm. Would the value of u and v affect the performance of Branch and Bound? Please explain clearly with examples.  (30 marks)

Question 3

Consider the following transportation problem with three factories A, B and C supplying to four dealers 1, 2, 3 and 4. Supplies available from factories A, B and C is 1000, 700 and 900 respectively. Demands of dealers 1, 2, 3 and 4 are X, Y, Z and W respectively. The transportation costs are given as follows:

A feasible solution for this cost minimizing transportation problem is given as follows:

a)   Is the problem degenerate? Clearly justify your answer and explain the similarity with degeneracy in linear programming in general. (15 marks)

b)   Starting from the given solution solve the problem to optimality. (60 marks)

c)   Suppose that the cost of supplying from factory C to dealer 4 goes up by 1 unit will  the optimal solution change? If yes, give the new optimal solution. Clearly give your reasoning for your answer. (5 marks)

d)  Suppose that the cost of supplying from factory A to dealer 1 goes down by 1 unit   will the optimal solution change? If yes, give the new optimal solution. Clearly give your reasoning for your answer.  (10 marks)

e)  Explain the relationship between part costs in the transportation method and dual formulation of transportation linear programme. (10 marks)