07 02 17

Pagina 1

Foundations of Operations Research Exam 7/2/2017 First part : Closed book Total score: 17 pts. Minimum score to pass: 10 pts. Tentative scores: 1) 3+1 pts, 2) 4 pts, 3) 5 pts, 4) 4 pts. 1. Consider the undirected graph in the figure below, with costs reported on the arcs. Compute the minimum cost spanning tree illustrating the intermediate steps. 6 32 5 1 4 7 3 21 47 8 9 1327 22 30 29 31 Additional question Once the solution has been found, determine for arcs (5, 7) and (3, 6), separately, what is the cost coe cient interval that guarantees that the optimal solution remains unchanged. Justify the answer. 2. Consider the maximum flow problem instance represented in the figure below. Compute the maximum flow starting from the given flow, illustrating the intermediate steps. 3 4 5 1 i j 2 xij, uij ts 6,6 1,7 3,3 2,8 2,2 2,2 0,5 3,3 5,10 0,4 5,5 0,3 3. Consider the following Linear Programming problem: min 6 x1 + 18x2 +6 x3 x1 + x2 + x3 =1 2x1 +3 x2 =2 x1,x 2,x 3 0 Write the dual and complementary slackness equations. For each of the following solutions verify the optimality by applying complementary slackness (i.e., discuss their primal and dual feasibility): x0 = 2 4 1 0 2 3 5 x00 = 2 4 0 2/3 1/3 3 5 4. Consider the following Integer linear programming problem: min 2 x1 x2 x1 +3 x2  21/2 x1 +2 x2  19/2 x1,x 2 0 integer After adding slack variables, consider the optimal basic solution B = {2, 4} of the linear relaxation. Derive the Gomory cut(s) with respect to the optimal solution of the linear relaxation. Give the geometrical representation of the cut(s). 1 Foundations of Operations Research Exam 7/2/2017 Second part: Open book Total score: 10 pts. 1. The soap opera “A place in the fog” director has to plan the shooting of the next D episodes. The shooting of an episode…