Full exam for Foundations of Operations Research in the Computer Engineering degree programme at Politecnico di Milano. The document covers: 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
Full exam for Foundations of Operations Research in the Computer Engineering degree programme at Politecnico di Milano. The document covers: 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
Import quality: text was extracted directly from the original document.
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
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…
First page of the document.
