10 09 19

Page 1

Nome: Cognome: Matricola : Exam 10/9/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 from s to t in the following graph, starting from the given flow . Illustrate the intermediate steps and report the minimum capacity cut. Does the solution change (maximum flow or minimum cut) if the capacity of arc (1, 4) increases of one unit? Justify your answer. 2 31 4 s t 4, 11 6, 6 i jxij, uij 3, 3 7, 10 2, 4 1, 4 3, 3 4, 9 2. Consider the following linear programming problem: min −5x1 + 7x2 + 10x3 + 10x4 −x1 + x2− 2x3 + 2x4≥ 3 −x1 + 3x3− x4≥ 3 x1, x2, x3, x4≥ 0 Write the dual and the complementary slackness equations. For each of the following solutionsx′ = [0, 0, 9/4, 15/4], x′′ = [0, 5, 1, 0] derive the complementary dual solutions and discuss the primal and dual feasibility. 3. Consider the following Integer Linear Programming problem: max x1− 5x2 4x1− 12x2≤ 15 4x1 + 12x2≤ 23 x1, x2∈Z + Add the slack variables (x3 and x4) to the first and the second constraints, and consider the optimal base B ={1, 4} of the LP relaxation. 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 cut(s). 4. Consider the following linear programming problem min {cx : Ax≥ b, x≥ 0, x∈R n}, where A is an m× n matrix, b an m component column vector and c an n component row vector. Write the dual. Given two solutions ¯x and ¯y, feasible for the primal and the dual, respectively, prove that c¯x≥ ¯yb. APML question in the rear 1 Nome: Cognome: Matricola : Exam 10/9/2019 Write the definition in the ampl modelling language of the following: • a set I. • a set J…