09 01 19 1

Page 1

Nome: Cognome: Matricola : Exam 9/1/2019 First part : Closed book Total score: 21 pts. Minimum score to pass: 11 pts. Tentative scores: 1) 4 pts, 2) 5 pts, 3) 5 pts, 4) 3 pts. 5) 4 pts. 1. Determine the maximum flow in the following graph starting from the given flow (x). Report the intermediate steps and the final minimum capacity cut. What is the worst case complexity of the used algorithm? 3 5 2 1 4 6 s t 5, 9 10, 10 4, 4 6, 6 4, 8 5, 5 3, 6 4, 4 6,8 0, 2 0, 5 4, 4 2, 2 2, 22, 2 i jxij, uij 2. Consider the following linear programming problem: max −x1 + 2x2 −5x1 + 3x2 ≤ 15 x1 + 3x2 ≤ 6 −x1−x2 ≤ 0 Write the dual and the complementary slackness equations. For each of the solutions the solutions x′ = [ −3 3 ] and x′′ = [ −3/2 5/2 ] derive the corresponding complementary dual solutions and discuss their primal and dual feasibility arguing their optimality. 3. Consider the following Integer Linear Programming problem max −x1−x2 x1− 2x2 ≤− 2 −3x1− 2x2 ≤− 6 x1,x 2∈ Z+ After adding the slack variables, consider the optimal base B ={1, 2} and generate the Gomory cuts associated with the fractional components of the solution. Justify your answer and give the geometric representation of the feasible region and of the cuts. 4. Given a LP problem of the form max {cx,Ax ≤ b,x ∈R n} and a feasible solution ¯x, give the conditions for the existence of a growing feasible direction ξ∈R n in ¯x. Justify the answer. 5. Answer to this question on the rear of this paper Write the definition in the AMPL modelling language of the following: • a set I of all the integers between 1 and 10. • a positive variable xi with i∈{I∪ 0}. • a parameter bi,j with i∈I and j∈{I∪ 0}. Then using the defined variables and parameters write in the AMPL modelling language the following constraint: ∑ i∈I ∑ j∈I…