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. Tons per hour Profit per
ton Maximum tons Bands 200 £25 6000 Coils 140 £30 4000 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: Dealer Factory 1 2 3 4 Supply A 2 2 2 4 1000 B 4 6 4 3 700 C 3 2 1 0 900 Demand X Y Z W A feasible solution for this cost minimizing transportation problem is given as follows: Dealer Factory 1 2 3 4 Supply A 900 100 1000 B 700 700 C 500 400 900 Demand X Y Z W 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)

Question 4

Kevin is required to transport blood urgently to a hospital located at t in the below network.
He is currently situated at s. Assume he can only travel on the roads given in the below
network and has only one mode of transportation. The travel times on roads are indicated just
above each road. For example, travel time from A to B is 12 minutes.
a) Assume Kevin aims to take the quickest route and travel is possible only in direction
of the arrow. Formulate this problem as an integer program. Clearly explain your
decision variables and constraints. (20 marks)
b) Explain the basic structure of a local search algorithm and comment on two strategies
to overcome its limitation. Give a local search heuristic to solve the problem in part a
and illustrate two iterations of your heuristic on the given network. (35 marks)
c) Explain briefly the basic components and the principle behind genetic algorithms.
Explain how you would construct a genetic algorithm for the problem in part a. (45
marks