03 02 16

Page 1

Foundations of Operations Research Exam 3/2/2016 First part : Closed book Total score: 17 pts. Minimum score to pass: 12 pts. 1. Consider the following directed graph. Find the shortest path with root in node 5. Apply the most e cient algorithm, after a possible preprocessing phase. Justify your choice and illustrate the intermediate steps. What is the complexity of the algorithm? 6 3 7 5 1 4 2 1 2 4 -3 6 7 7 -2 9 -3 5 11 5 2. Consider the following LP problem: min 5 x1 +2 x2 +7 x3 +3 x4 2x1 +4 x2 x4 =3 2x1 +2 x2 2x3 2x4 = 1 xi 0 i =1 ,..., 4 Write the dual and complementary slackness equations. Check the optimality for the following solutions x0 =[ 0, 7/6, 0, 10/6] x00 =[ 0, 3/4, 5/4, 0] 3. Consider the following ILP problem: min x1 +4 x2 4x1 +6 x2  27 2x1 6x2  9 x1,x 2 0 After adding suitable slack variables, consider the optimal base B = {1, 3} of the LP relaxation. Compute the Gomory cut(s) with respect to the corresponding solution. Give the geometrical representation of the found cut(s). 4. Consider the minimum spanning tree problem. Write the decision version of the problem. 1 Foundations of Operations Research Exam 3/2/2016 Second part: Open book Total score: 10 pts. 1. Consider a telecommunication network represented by a directed graph G =( N, A). Root node r has to broadcast a message to every other node in N . At any one unit interval of time t a node can either receive or send a message to ONLY ONE of its neighboring nodes. Sending (or receiving) the message along an arc ( i, j) 2 A takes 1 unit of time. A node can send the message only after it has received it. Find the routing operations during the time that minimize the time for broadcasting the message to all the nodes. Write a suitable linear optimization model. Explain the meaning of variables and…