Servizi per la didattica
PORTALE DELLA DIDATTICA

Ricerca operativa

07CESMQ

A.A. 2020/21

Lingua dell'insegnamento

Italiano

Corsi di studio

Corso di Laurea in Matematica Per L'Ingegneria - Torino

Organizzazione dell'insegnamento
Didattica Ore
Lezioni 50
Esercitazioni in aula 30
Docenti
Docente Qualifica Settore h.Lez h.Es h.Lab h.Tut Anni incarico
Brandimarte Paolo Professore Ordinario MAT/09 50 30 0 0 1
Collaboratori
Espandi

Didattica
SSD CFU Attivita' formative Ambiti disciplinari
MAT/09
MAT/09
4
4
C - Affini o integrative
F - Altre (art. 10, comma 1, lettera f)
Attività formative affini o integrative
Altre conoscenze utili per l'inserimento nel mondo del lavoro
2020/21
Ricerca operativa è un insegnamento di matematica applicata che fa da ponte tra gli insegnamenti di base dei primi tre semestri della laurea e quelli applicativi della laurea magistrale in Ingegneria Matematica. Come tale, esso è un insegnamento di sintesi di contenuti diversi, che spaziano dall’analisi matematica all’algebra lineare, dall’analisi numerica alla teoria delle probabilità, e si articola sia su concetti teorici che su applicazioni a problemi concreti. La ricerca operativa, come suggerisce il nome stesso, mira a ricercare il modo ottimale di operare, ovvero trovare una soluzione che ottimizzi un criterio di valutazione, nel rispetto dei vincoli del problema. A titolo di esempio possiamo cercare il piano di trasporto che minimizza il consumo di carburante, o ricavare i prezzi di un prodotto che massimizzano il profitto dalle vendite. In contesti più complessi, occorre trovare una soluzione di compromesso tenendo conto di molteplici criteri in conflitto tra di loro. Tutto ciò richiede di costruire un modello matematico del problema reale, per poi applicare un algoritmo numerico di soluzione. Parte integrante del processo decisionale sono la raccolta dei dati, l’implementazione in software, l’analisi dei risultati e la validazione del modello. Inoltre, l’insegnamento fornisce concetti di ottimizzazione essenziali negli insegnamenti di statistica e machine learning della laurea magistrale.
Operations research is a bridge between the foundational mathematics courses of the first three semesters and the application-oriented courses of the masters’ degree. As such, it merges content from calculus and linear algebra with numerical analysis and probability theory, integrating theoretical concepts and real-life problems. As the name itself suggests, we search the best way to operate a system, optimizing a performance criterion subject to constraints. For instance, we may look for an optimal transportation plan in order to minimize fuel consumption, or the optimal retail prices to boost profit from sales. In a more complicated setting, we have to find a suitable compromise solution accounting for confilcting requirements. To this aim, we need to build a mathematical model of the problem, which is then solved by a numerical procedure. The decision process also includes data collection, software implementation, output analysis and model validation. Furthermore, we will also introduce optimization concepts that play a key role in statistical and machine learning courses at the masters’ level.
• Capacità di razionalizzazione di un problema decisionale: formulazione di criteri di valutazione e vincoli. • Costruzione di modelli matematici di ottimizzazione. • Scelta di un algoritmo esatto o approssimato di soluzione. • Capacità di implementare algoritmi di decisione in MATLAB.
Ability to: • Formalize a decision problem in terms of evaluation criteria and constraints. • Build an optimization model for a real-life problem. • Choose an exact or approximate solution method. • Implement a decision algorithm in MATLAB.
Sono prerequisiti essenziali gli insegnamenti di matematica del primo e secondo anno, con particolare riferimento ai contenuti seguenti: • Algebra lineare e geometria: spazi vettoriali, matrici, indipendenza lineare, forme quadratiche; programmazione in MATLAB, approssimazione di funzioni, algebra lineare numerica. • Analisi II: gradiente, matrice Hessiana, polinomio di Taylor, massimi e minimi liberi. Verranno anche usati alcuni concetti elementari di teoria delle probabilità introdotti nell’insegnamento parallelo di Metodi matematici per l’ingegneria.
The essential prerequisites are given in the basic mathematics courses of the first two years, in particular: • Linear algebra and geometry: vector spaces, matrices, linear independence, quadratic forms; MATLAB programming, function approximation, numerical linear algebra. • Calculus II: gradient, Hessian matrix, Taylor polynomial, unconstrained maxima and minima. We will also use some basic concepts in probability theory, which are introduced in the parallel course Mathematical methods in engineering.
Costruzione di modelli di ottimizzazione: • Classificazione dei modelli di ottimizzazione. • Esempi in logistica, finanza, statistica e machine learning, ingegneria, marketing. • Modelli con obiettivi multipli: concetto di soluzione efficiente, goal programming. Concetti geometrici in ottimizzazione: • Convessità di insiemi e funzioni. • Gradienti e subgradienti. • Coni e poliedri. Programmazione nonlineare: • Condizioni di ottimalità per problemi di ottimizzazione vincolata e loro interpretazione economica. • Teoria della dualità. • Metodi locali di soluzione: funzioni di penalità; metodi basati sul gradiente e sue varianti (trust region; quasi-Newton); metodi per punti interni; metodi derivative-free. Programmazione lineare: • Algoritmo del simplesso. • Dualità nella programmazione lineare. • Metodi per punti interni. • Analisi di sensitività e suoi limiti. Elementi di complessità computazionale: classi P e NP; problemi NP-completi e NP-hard. Ottimizzazione non convessa: • Programmazione mista intera; algoritmi branch and cut; formulazioni forti e deboli. • Cenni di ottimizzazione globale: metodi deterministici e stocastici; metaeuristiche. • Applicazioni al problema di routing di veicoli (VRP). Esercitazioni su MATLAB: Optimization toolbox e Global optimization toolbox.
Optimization model building: • Classification of optimization models. • Examples in logistics, finance, statistical and machine learning, engineering, marketing. • Multiobjective models: efficient solutions, goal programming. Geometric concepts in optimization: • Convex sets and functions. • Gradients and subgradients. • Cones and polyhedra. Nonlinear programming: • Optimality conditions for constrained optimization and economic interpretation. • Duality theory. • Local solution methods: Penalty functions, gradient-based methods (trust region; quasi-Newton); interior point methods; derivative-free methods. Linear programming: • Simplex methods. • Duality in linear programming. • Interior point methods. • Sensitivity analysis and its limitations. Computational complexity: classes P and NP; NP-complete and NP-hard problems. Nonconvex optimization: • Mixed-integer programming; branch and cut algorithms; strong model formulations. • Global optimization: deterministic and stochastic methods; metaheuristics. • Applications to vehicle routing problems. EMATLAB laboratories: Optimization toolbox and Global optimization toolbox.
L’organizzazione dell'insegnamento dipenderà in parte dalla possibilità o meno di erogare didattica in presenza. Sono previste lezioni frontali ed esercitazioni numeriche, anche supportate da MATLAB. L’implementazione di procedure di soluzione in MATLAB è oggetto di elaborati di gruppo ed è parte integrante dell’esame.
The course structure will be affected by the possibility of onsite teaching or the lack thereof. Classical lectures are integrated by numerical experiments, also based on MATLAB. Implementing numerical solution methods as group homework is part of the exam.
Verranno forniti slide ed elementi di dispense didattiche preparati dal docente. Il materiale si basa sui riferimenti seguenti: • M.Z. Bazaraa, H.D. Sherali, G.M. Shetty. Nonlinear Programming: Theory and Algorithms, (3rd ed.). Wiley, 2006. • P. Brandimarte. Quantitative methods: An introduction for business management. Wiley, 2011. • D.-S. Chen, R.G. Batson, Y. Dang. Applied Integer Programming: Modeling and Solution. Wiley, 2011 • P. Toth D. Vigo. Vehicle Routing: Problems, Methods, and Applications (2nd ed.). SIAM, 2016 • P. Williams. Model Building in Mathematical Programming (5th ed.). Wiley, 2013.
Slides and lecture notes will be distributed, based on the following texts: • M.Z. Bazaraa, H.D. Sherali, G.M. Shetty. Nonlinear Programming: Theory and Algorithms, (3rd ed.). Wiley, 2006. • P. Brandimarte. Quantitative methods: An introduction for business management. Wiley, 2011. • D.-S. Chen, R.G. Batson, Y. Dang. Applied Integer Programming: Modeling and Solution. Wiley, 2011 • P. Toth D. Vigo. Vehicle Routing: Problems, Methods, and Applications (2nd ed.). SIAM, 2016 • P. Williams. Model Building in Mathematical Programming (5th ed.). Wiley, 2013.
Modalità di esame: Prova orale obbligatoria; Elaborato progettuale in gruppo;
CRITERI DI VALUTAZIONE Per l'orale: capacità di formulare modelli di ottimizzazione; comprensione profonda della teoria e degli algoritmi di soluzione; capacità di dimostrare semplici teoremi e di strutturare e analizzare algoritmi di soluzione; valutazione critica delle assunzioni semplificative necessarie. Per gli elaborati di gruppo: documentazione del software prodotto; completezza degli esperimenti computazionali; analisi del tradeoff tempo/prestazioni. PUNTEGGI Per la valutazione, 18 punti sono assegnati sulla base dell'orale, 12 sulla base degli elaborati di gruppo.
Exam: Compulsory oral exam; Group project;
EVALUATION CRITERIA For the oral part: ability to formulate an optimization model; deep knowledge of theory underlying solution methods; ability to prove simple theorems and properties; ability to specify and analyze a solution method; ability to assess the necessary simplifying assumptions. For the group homework: documentation of the developed software; ability to perform critical computational experiments and to assess the tradeoff between performance and computational effort. EXAM MARKS: 18 points oral, 12 group homework.
Modalità di esame: Prova scritta (in aula); Prova orale obbligatoria; Elaborato progettuale in gruppo;
CRITERI DI VALUTAZIONE Per l'esame scritto: capacità di formulare modelli di ottimizzazione; capacità di strutturare e analizzare algoritmi di soluzione; valutazione critica delle assunzioni semplificative necessarie. Per l'esame orale (facoltativo): comprensione profonda della teoria e degli algoritmi di soluzione; capacità di dimostrare semplici teoremi. Per gli elaborati di gruppo: documentazione del software prodotto; completezza degli esperimenti computazionali; analisi del tradeoff tempo/prestazioni. PUNTEGGI 16 punti sono assegnati sulla base dello scritto (90 minuti, closed book), 10 sulla base degli elaborati di gruppo. L'orale è opzionale e ha un range di valutazione da -2 a +4 (NB: non necessariamente positivo). L'orale è riservato a chi ha acquisito un punteggio di almeno 22 tra scritto e elaborati. Lo scritto in aula è sostituito da una prima parte di orale obbligatorio per gli esami a distanza.
Exam: Written test; Compulsory oral exam; Group project;
EVALUATION CRITERIA For the oral part: ability to formulate an optimization model; ability to specify and analyze a solution method; ability to assess the necessary simplifying assumptions. For the oral part (optional): deep knowledge of theory underlying solution methods; ability to prove simple theorems. For the group homework: documentation of the developed software; ability to perform critical computational experiments and to assess the tradeoff between performance and computational effort. EXAM MARKS: 16 points written exam (90 minutes, closed book), 10 group homework. Oral is optional, with range from -2 to +4 (Note: this is not necessarily positive). The optional oral is reserved to students who have achieved a minimum of 22 based on written exam and homework. The written exam is replaced by a first oral (compulsory) in the case of an onlne exam.


© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
m@il