Optimisation Techniques

Optimisation Techniques
2020/21
Coursework 2

Question 1 [20 marks]
Consider the integer linear programming problem

max x + 2y
s.t. x + y 10
2x + 5y 25 + z
x; y 0 and integer

Here z = 0 if the last digit of your registration number is odd; otherwise
z = 5.
(a) Relax the integrality constraint. Assume that it is known that in
the optimal solution of the obtained LP problem both main constraints hold
as equalities. Derive the …nal simplex tableau using the transformation matrix
technique. Is the obtained optimal solution feasible for the original integer
programming problem?

[9 marks]

(b) Starting with the tableau found in (a), apply the Gomory fractional
algorithm to obtain two di¤erent optimal integer solution. Clearly explain how
the cut equations are derived.

[11 marks]

Question 2 [20 marks]
By formulating and solving an appropriate optimisation problem by the
Lagrangian technique …nd the shortest distance between the line 2x = y + 4 and
the parabola y = x2 2:

[20 marks]

Question 3 [15 marks]
Consider the non-linear programming problem

maximise 3x + 2y
(x 2)2 + (y 1)2 9;
s.t.
x 0

(a) Draw a feasible region and …nd the coordinates of its vertices.

[2 marks]

(b) Write out the Lagrangian function and …nd its derivatives.

[3 marks]


1