Scheda programma d'esame
RICERCA OPERATIVA
MAURO PASSACANTANDO
Anno accademico2021/22
CdSINFORMATICA
Codice029AA
CFU6
PeriodoPrimo semestre
LinguaItaliano

ModuliSettoreTipoOreDocente/i
RICERCA OPERATIVAMAT/09LEZIONI48
MAURO PASSACANTANDO unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

Il corso presenta gli strumenti necessari alla costruzione e alla risoluzione di modelli analitici di ottimizzazione per problemi reali, tipicamente di gestione, di allocazione delle risorse e di logistica. Verranno illustrate le proprietà teoriche ed alcune delle principali tecniche algoritmiche per la soluzione di tre grandi classi di problemi di ottimizzazione: problemi di flusso su reti, di programmazione lineare e di programmazione lineare intera.

Knowledge

The course presents the necessary tools for the construction and resolution of optimization models for real problems (management, resource allocation and logistics problems, etc.). The theoretical properties and some of the main algorithmic techniques for the solution of three classes of optimization problems will be illustrated: network flow problems, linear programming problems and integer linear programming problems.

Modalità di verifica delle conoscenze

Per l'accertamento delle conoscenze saranno svolte delle prove in itinere.

Assessment criteria of knowledge

Ongoing assessment to monitor academic progress will be carried out.

Capacità

Lo studente sarà in grado di analizzare, modellizzare e sviluppare algoritmi risolutivi per problemi di flusso su reti, problemi di programmazione lineare e di programmazione lineare intera.

Skills

The student will be able to analyse, model and develop solving algorithms for netwrok flow problems, linear programming problems and integer linear programming problems.

Modalità di verifica delle capacità

Durante le sessioni di esercitazioni saranno svolti esercizi per modellizzare e risolvere problemi di flusso su reti, di programmazione lineare e di programmazione lineare intera.

Assessment criteria of skills

Exercises to model and solve network flow problems, linear programming problems and integer linear programming problems will be conducted during the tutorial sessions.

Comportamenti

Lo studente potrà sviluppare capacità critiche, sia a livello modellistico che algoritmico, per affrontare problemi di ottimizzazione del mondo reale, che risulteranno rilevanti in svariati ambiti lavorativi, sia a livello progettuale che implementativo.

Behaviors

The student will be able to develop critical modelling and algorithmic skills on real-world optimization problems, which will be relevant to several work areas, both at design and implementation level.

Modalità di verifica dei comportamenti

Durante le sessioni di esercitazioni saranno valutate le capacità critiche dello studente per affrontare problemi di ottimizzazione del mondo reale.

Assessment criteria of behaviors

During the tutorial sessions, the student's critical skills in dealing with real-world optimization problems will be assessed.

Prerequisiti (conoscenze iniziali)
  • Logica elementare: connettivi logici, proposizioni, principio di induzione, metodi di dimostrazione

  • Spazi vettoriali: spazi, semispazi, vettori, combinazioni lineari, indipendenza lineare, basi, coordinate

  • Geometria del piano e dello spazio tridimensionale: sottospazi affini, equazione di rette, piani e semispazi

  • Prodotto scalare euclideo, ortogonalità

  • Matrici: operazioni con le matrici, determinante, invertibilità

  • Concetto di funzione, funzioni lineari (ed affini)

  • Sistemi lineari di equazioni e loro risoluzione

  • Cosa è un algoritmo

  • Complessità di un algoritmo

  • Classi P e NP

  • Strutture dati: fila, pila, deque, code di priorità, heap

  • Grafi: nodi, archi, alberi, cammini, cicli

  • Grafi: rappresentazione e visite (DFS e BFS)

  • Alberi: rappresentazioni e visite

  • Ricerca dei punti di massimo e minimo di funzioni di una variabile
Prerequisites
  • Boolean logic: operators, propositions, induction principle, proof methods
  • Vector spaces: spaces, semi-spaces, vectors, linear combinations, linear independence, bases, coordinates  
  • Geometry of the two and three-dimensional spaces: affine subspaces, equations of lines, planes and half-spaces  
  • Euclidean product, orthogonality   
  • Matrices: operations with the matrices, determinant, invertibility
  • Affine and linear functions
  • Linear systems of equations and their resolution
  • What is an Algorithm
  • Complexity of an algorithm
  • Classes P and NP
  • Data structures: row, stack, deque, priority queues, heap
  • Graphs: nodes, arcs, trees, paths, cycles
  • Graphs: representation and visits (DFS and BFS)
  • Trees: representations and visits
  • Maximum and minimum points for functions of one variable
Indicazioni metodologiche

Modalità: lezioni frontali, con l'aiuto di slide, e sessioni di esercitazioni.

Sito di elearning del corso: download di materiali didattici, pubblicazione di test per esercizi a casa (con relative soluzioni).

Attività di apprendimento: partecipazione alle lezioni e studio individuale.

Frequenza: consigliata

Teaching methods

Delivery: Frontal lessons, with the help of transparencies, exercise sessions.

Course elearning site: download teaching materials, publication of tests for home exercises.

Learning activities: attending lectures, individual study.

Attendance: Advised

Programma (contenuti dell'insegnamento)

Introduzione (2 ore)

  • Problemi decisionali e problemi di ottimizzazione
  • Classi di problemi ed esempi

Modelli e loro formulazione (6 ore)

  • Tipi di variabili: quantitative, logiche, continue, discrete
  • Formulazione di vincoli
  • Formulazione della funzione obiettivo

Grafi e Reti di flusso (16 ore)

  • Modello generale dei problemi di flusso
  • Alberi, cammini e tagli, visite di grafi e alberi
  • Il problema dei cammini minimi
  • Il problema del flusso massimo
  • Il problema del flusso di costo minimo
  • Il problema dell'albero di copertura di costo minimo

Programmazione Lineare (16 ore)

  • Geometria della programmazione lineare e teorema fondamentale
  • Dualità e scarti complementari
  • Basi: complementarità, degenericità ed ottimalità
  • Algoritmi del simplesso primale e duale

Programmazione Lineare Intera (8 ore)

  • Metodi poliedrali: tagli ed algoritmo di Gomory
  • Metodi enumerativi: l'algoritmo "Branch&Bound"
  • Implementazioni ad-hoc per i problemi dello zaino e del commesso viaggiatore
Syllabus

Introduction (2 hours)

  • Decision-making and optimization problems
  • Classes of problems and examples

Optimization models (6 hours)

  • Variables: quantitative, logical, continuous, discrete
  • Constraints formulation
  • Objective function formulation

Graphs and network flows (16 hours)

  • General model for network flow problems
  • Trees, paths and cuts, graph search
  • Shortest path problem
  • Maximum flow problem
  • Minimum cost flow problem
  • Minimum spanning tree problem

Linear Programming (16 hours)

  • Geometry and fundamental theorem of LP
  • Duality and complementary slackness conditions
  • Bases: complementarity, degeneracy and optimality
  • Primal and dual simplex algorithms

Integer Linear Programming (8 hours)

  • Polyhedral methods: Gomory cuts
  • Enumeration methods: the "Branch & Bound" method
  • Ad-hoc implementations of the "Branch & Bound" method for the knapsack problem and the travelling salesman problem
Bibliografia e materiale didattico

Testo di riferimento:

Altri testi consigliati:

  • R.K. Ahuja, T.L. Magnanti, J. Orlin, Network flows. Theory, algorithms and applications, Prentice Hall, 1993
  • G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G. Scutellà, Appunti di Ricerca Operativa, SEU - Servizio Editoriale Universitario di Pisa
  • F.S. Hillier, G.J. Lieberman, Ricerca Operativa - Fondamenti, McGraw-Hill, 2010
  • F. Schoen, Modelli di ottimizzazione per le decisioni, Esculapio, 2006
  • C. Vercellis, Ottimizzazione. Teoria, metodi, applicazioni, McGraw Hill, 2008
Bibliography

Main textbook:

Further textbooks:

  • R.K. Ahuja, T.L. Magnanti, J. Orlin, Network flows. Theory, algorithms and applications, Prentice Hall, 1993
  • G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G. Scutellà, Appunti di Ricerca Operativa, SEU - Servizio Editoriale Universitario di Pisa
  • F.S. Hillier, G.J. Lieberman, Ricerca Operativa - Fondamenti, McGraw-Hill, 2010
  • F. Schoen, Modelli di ottimizzazione per le decisioni, Esculapio, 2006
  • C. Vercellis, Ottimizzazione. Teoria, metodi, applicazioni, McGraw Hill, 2008
Modalità d'esame

Prova scritta seguita da una prova orale. Sono ammessi alla prova orale solo gli studenti che hanno superato la prova scritta. Sono esonerati dalla prova scritta coloro che hanno superato le due prove in itinere/prove di verifica intermedia (nel seguito denominate "compitini"). Sono ammessi al secondo compitino soltanto gli studenti che hanno superato il primo.

Per sostenere la prova scritta dell'esame, inclusi i compitini, è necessario iscriversi entro le date indicate su esami.unipi.it. In genere la scadenza per le iscrizioni è fissata 48 ore prima della prova. In caso di mancata iscrizione da parte di uno o più studenti non è possibile garantire la loro partecipazione alla prova.

Durante la prova scritta non è possibile consultare libri o appunti.

La prova orale viene effettuata nella stessa sessione (Gennaio-Febbraio, Giugno-Luglio, Settembre) della prova scritta secondo un calendario di possibili date comunicato durante il compito e pubblicato contemporaneamente sulla pagina web. La consegna di una prova scritta successiva a quella già superata comporta la rinuncia alla prova precedentemente sostenuta con esito positivo.

Gli studenti che sono stati esonerati dalla prova scritta a seguito di valutazione positiva dei compitini possono svolgere la prova orale in uno dei primi due appelli. La consegna di una prova scritta successiva ai compitini comporta la rinuncia all'esonoro eventualmente già ottenuto.

Assessment methods

The exam is made up of one written test and one oral test. Only students who have passed the written test are admitted to the oral test. Exempted from the written test are those who have passed the two intermediate tests. Only those students who have passed the first intermediate test are admitted to the second intermediate test.

In order to partecipate to the written tests it is necessary to register by the deadlines indicated on exams.unipi.it. If one or more students do not register, it is not possible to guarantee their participation in the test.

During the written test it is not possible to consult books or notes.

The oral test is carried out in the same session (January-February, June-July, September) of the written test according to a calendar of possible dates communicated during the test and published simultaneously on the web page. The delivery of a written test after the one already passed involves the renunciation of the test previously passed with positive results.

Students who have been exempted from the written test following a positive evaluation of the tasks can take the oral test in one of the first two appeals. The delivery of a written test after the tasks involves the waiver of any exemption already obtained.

Ultimo aggiornamento 18/11/2021 07:51