Leo Liberti - lix.polytechnique.fr

1 Ecole PolytechniqueProblems and exercises in operations ResearchLeo Liberti1 Last update: November 29, 20061 Some exercises have been proposed by other authors, as detailed in the text. All the solutions, however, are by theauthor, who takes full responsibility for their accuracy (or lack thereof).ExercisesOperations ResearchL. Liberti2 Contents1 Optimization on Dijkstra s algorithm .. Bellman-Ford s algorithm .. Maximum flow .. Minimum cut .. Renewal plan .. Connected subgraphs .. Strong connection .. 112 Linear Graphical solution .. Geometry of LP .. Simplex method .. Duality .. Geometrical interpretation of the simplex algorithm .. Complementary slackness.

2 Sensitivity analysis .. Dual simplex method .. 163 Integer Piecewise linear objective .. Gomory cuts .. Branch and Bound I .. Branch and Bound II .. Knapsack Branch and Bound .. 183 ExercisesOperations ResearchL. Liberti4 Easy modelling Compact storage of similar sequences .. Communication of secret messages .. Mixed production .. Production planning .. Transportation .. Project planning with precedences .. Museum guards .. Inheritance .. Carelland .. CPU Scheduling .. Dyeing plant .. Parking .. 245 Difficult modelling Checksum .. Eight queens .. Production management .. The travelling salesman problem .. Optimal rocket control 1.

3 Double monopoly .. 286 Telecommunication Packet routing .. Network Design .. Network Routing .. 327 Nonlinear Error correcting codes .. Airplane maintenance .. Pooling problem .. Optimal rocket control 2 .. 378 Optimization on graphs: Solutions39 CONTENTS4 ExercisesOperations ResearchL. Dijkstra s algorithm: Solution .. Bellman-Ford algorithm: Solution .. Maximum flow: Solution .. Minimum cut: Solution .. Renewal plan: Solution .. Connected subgraphs: Solution .. Strong connection: Solution .. 449 Linear programming: Graphical solution: Solution .. Geometry of LP: Solution .. Simplex method: Solution .. Duality: Solution .. Geometrical interpretation of the simplex algorithm: Solution.

4 Iteration 1: Finding the initial vertex .. Iteration 2: Finding a better vertex .. Iterazione 3: Algorithm termination .. Complementary slackness: Solution .. Sensitivity analysis: Solution .. Dual simplex method: Solution .. 5810 Integer programming: Piecewise linear objective: Solution .. Gomory Cuts: Solution .. Branch and Bound I: Solution .. Branch and Bound II: Solution .. Knapsack Branch and Bound: Solution .. 6711 Easy modelling problems: Compact storage of similar sequences: Solution .. Communication of secret messages: Solution .. Mixed production: Solution .. Formulation .. 72 CONTENTS5 ExercisesOperations ResearchL. AMPL model, data, run .. CPLEX solution.

5 Production planning: Solution .. Formulation .. AMPL model, data, run .. CPLEX solution .. Transportation: Solution .. Formulation .. AMPL model, data, run .. CPLEX solution .. Project planning with precedences: Solution .. Museum guards: Solution .. Formulation .. AMPL model, data, run .. CPLEX solution .. Inheritance: Solution .. AMPL model, data, run .. CPLEX solution .. Carelland: Solution .. Formulation .. AMPL model, data, run .. CPLEX solution .. Scheduling: Solution .. model, data, run .. solution .. plant: Solution .. model, data, run .. solution .. : Solution .. model, data, run .. solution .. 92 CONTENTS6 ExercisesOperations ResearchL.

6 Liberti12 Difficult modelling problems: Checksum: Solution .. Formulation .. AMPL model, data, run .. CPLEX solution .. Eight queens: Solution .. Formulation .. AMPL model, run .. CPLEX solution .. Production management .. Formulation .. AMPL model, data, run .. The travelling salesman problem: Solution .. Formulation .. AMPL model, data .. Algorithm .. CPLEX solution .. Heuristic solution .. Optimal rocket control 1: Solution .. AMPL: model, run .. CPLEX solution .. Double monopoly: Solution .. 10813 Telecommunication networks: Packet routing: Solution .. Formulation for 2 links .. Formulation formlinks .. AMPL model, data, run .. CPLEX solution.

7 Network Design: Solution .. Formulation and linearization .. AMPL model, data, run .. 114 CONTENTS7 ExercisesOperations ResearchL. CPLEX solution .. Network Routing: Solution .. AMPL model, data, run .. Soluzione di CPLEX .. 12214 Nonlinear programming: Error correcting codes: Solution .. Airplane maintenance: Solution .. Pooling problem: Solution .. AMPL: model, data, run .. CPLEX solution .. Optimal rocket control 2: Solution .. 127 CONTENTS8 Chapter 1 Optimization on Dijkstra s algorithmUse Dijkstra s algorithm to find the shortest path tree in the graph below using vertex 1 as Bellman-Ford s algorithmCheck whether the graph below has negative cycles using Bellman-Ford s algorithm and 1as a 13 Maximum flowDetermine a maximum flow from node 1 to node 7 in the networkG= (V, A) below (the values on thearcs (i, j) are the arc capacitieskij).

8 Also find a cut having minimum ResearchL. Minimum cutFind the mimum cut in the graph below (arc capacities are marked on the arcs). What algorithm didyou use? Renewal planA small firm buys a new production machinery costing 12000 euros. In order to decrease maintenancecosts, it is possible to sell the machinery second-hand and buy a new one. The maintenance costs andpossible gains derived from selling the machinery second-hand are given below (forthe next 5 years):age (years)costs (keuro)gain (keuro)02-1472563924121 Determine a renewal plan for the machinery which minimizes the total operation cost over a 5-year period.[E. Amaldi, Politecnico di Milano] Connected subgraphsConsider the complete undirected graphKn= (V, E) whereV={0.}

9 , n 1}andE={{u, v}|u, v V}. LetU={imodn|i 0}andF={{imodn,(i+2) modn}|i 0}. Show that (a)H= (U, F)is a subgraph ofGand that (b)His connected if and only ifnis subgraphs10 ExercisesOperations ResearchL. Strong connectionConsider the complete undirected graphKn= (V, E) and orient the edges arbitrarily into an arc setAso that for each vertexv V,| +(v)| 1 and| (v)| 1. Show that the resulting directed graphG= (V, A) is strongly connection11 ExercisesOperations ResearchL. LibertiStrong connection12 Chapter 2 Linear Graphical solutionConsider the problemminxcxAx bx 0wherex= (x1, x2)T,c= (16,25),b= (4,5,9)T, andA= 1 71 52 3 .1. Solve the problem Write the problem in standard form. IdentifyBandNfor the optimal vertex of the feasiblepolyhedron.

10 [E. Amaldi, Politecnico di Milano] Geometry of LPConsider the following LP = 3x1+ 2x2( )2x1+x2 4( ) 2x1+x2 2( )x1 x2 1( )x1, x2 Solve the problem graphically, specifying the variable values andz at the Determine the bases associated to all the vertices of the feasible ResearchL. Liberti3. Specify the sequence of the bases visited by the simplex algorithm to reach the solution (choosex1as the first variable entering the basis).4. Determine the value of the reduced costs relative to the basic solutions associated to the followingvertices, expressed as intersections of lines inR2: (a) (Eq. ) (Eq. ); (b) ((Eq. ) (Eq. ),where ( ) is the equation obtained by inequality (i) replacing with =.5. Verify geometrically that the objective function gradient can be expressed asa non-negative linearcombination of the active constraint gradients only in the optimal vertex (keep in mind that theconstraints must all be cast in the form, since the optimization direction is maximization 0 should be written as x1 0).)