• Italiano
  • English

Department of Mathematics and Applications
"Renato Caccioppoli"


Operations Research

Home > Exams > Operations Research

Operations Research

Credits

6

Prerequisites

None.

Scientific-disciplinary sector (SSD)

MAT/09 Operations Research.

Examination method

Written exam (exercises and numerical problems, possibly multiple-choice) and oral exam.

Learning
objectives

The main objective of the course is to introduce students to the use of mathematical programming models, in particular both linear optimisation models (both continuous and integer-variable) and nonlinear optimisation models.

Syllabus

Definition and classification of optimisation problems and decision problems, and classification of the related solution methods. Linear Programming (LP): the Simplex Method. Integer Linear Programming problems. Exact methods for solving Integer Linear Programming problems. Examples of ILP problems with a unimodular constraint matrix. Knapsack problems and solution algorithms. Optimisation problems on graphs and trees: Vertex Cover and Minimum Spanning Tree. The Vertex Cover problem: a 2-approximation algorithm for the Vertex Cover problem. The minimum-cost spanning tree problem for a graph (MST): Kruskal’s algorithm. Optimisation problems on graphs and trees: Shortest Path problems. Paths in a directed graph: the reachability problem (breadth-first search; depth-first search). The shortest path problem: Dijkstra’s algorithm; the Floyd-Warshall algorithm. Optimisation problems on graphs and trees: Project Scheduling and the Maximum Flow Problem. Project scheduling: the CPM method. Network flow problems: the maximum flow problem; the max-flow min-cut theorem; the Ford-Fulkerson algorithm. Unconstrained Nonlinear Optimisation: Gradient Methods, Newton’s Method, Conjugate Direction Methods. Methods based on Lagrange Multipliers.

Expected learning
outcomes

By the end of the course, students must demonstrate that they

  • understand and know the techniques for formalising (linear and nonlinear) optimisation models for problems of logistics, organisation, planning, scheduling, transport, network flow and problems on graphs and trees;
  • are able to apply the knowledge acquired by developing and solving mathematical models of classical (linear and nonlinear) optimisation problems, and the related solution algorithms, in the fields of Production Planning, Location, Inventory Management and Logistics;
  • are able to communicate ideas and solutions clearly, rigorously and effectively to both specialist and non-specialist audiences;
  • are able to identify the most appropriate methods to analyse and solve a problem relating to the course topics and to interpret the results correctly.

Learning outcomes
to be assessed

Assessment of the ability to solve exercises of varying difficulty; clarity, correctness and completeness in the written and oral presentation of the course topics.