Schema della sezione
-
Ricerca Operativa (corsi A e B), 029AA, 2025/26
Corso da 6 CFU, Primo Semestre. Orario:
- Mercoledì, 9:00 - 11:00, Aula E (B)
- Mercoledì, 11:00 - 13:00, Aula E (A)
- Giovedì, 16:00 - 18:00, Aule D5 (A) e D2 (B)
Docenti:
- Stefano Novellani (corso A), ricevimento studenti Giovedì 14:00 - 16:00 (eventualmente anche per appuntamento)
- Luca Mencarelli (corso B), ricevimento studenti Giovedì 11:00 - 13:00 (eventualmente anche per appuntamento)
Ancorché i corsi sono formalmente separati, il programma e gli esami scritti ed orali sono identici tra i due corsi. Ciascuno studente potrà quindi essere valutato da uno qualunque dei due docenti.
Registri delle lezioni:
-
Il corso presenta gli strumenti necessari alla costruzione e alla risoluzione di modelli analitici di ottimizzazione per problemi reali di gestione ed allocazione delle risorse, con applicaizioni in moltissimi campi della scienza e dell'ingegneria ed attività economiche (logistica, trasporti, telecomunicazioni, finanza, energia, salute, ...). Verrà innanzi tutto introdotto il concetto di modellazione matematica per due classi particolarmente rilevanti di problemi di ottimizzazione, la Programmazione Lineare e la Programmazione Lineare Intera, mostrando come sia possibile attraverso di esse costruire modelli di moltissime situazioni reali (o realistiche, o anche completamente immaginarie). Verranno poi 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.
PROGRAMMA DEL CORSO
-
-
Introduzione (4 ore)
- Il processo decisionale
-
Problemi decisionali e problemi di ottimizzazione
-
Modelli e loro formulazione (6 ore)
- Tecniche di formulazione in Programmazione Lineare Intera
- Cenni all'utilizzo pratico (linguaggi di modellazione)
-
Grafi e Reti di flusso (14 ore)
- Modello generale dei problemi di flusso
- Il problema dei cammini minimi
- l problema dell'albero di copertura di costo minimo
- Il problema del flusso massimo
- Il problema del flusso di costo minimo
- Problemi di accoppiamento (cenni)
-
Programmazione Lineare (16 ore)
- Geometria della programmazione lineare
- Algoritmo del simplesso primale
- Dualità e scarti complementari
- Algoritmo del simplesso duale
-
Programmazione Lineare Intera (8 ore)
- Ottimizzazione combinatoria e sua complessità
- Metodi enumerativi: l'algoritmo "Branch & Bound"
- Implementazioni ad-hoc per zaino, commesso viaggiatore, cammino minimo vincolato
- Tecniche poliedrali (tagli di Chvátal e Gomory) ed il "Branch & Cut"
-
(Le ore indicate includono le esercitazioni)
-
-
Prova scritta seguita da una prova orale.
Sono ammessi alla prova orale solo gli studenti che hanno superato la prova scritta con un voto numerico o "quasi sufficiente". La prova orale deve essere sostenuta nello stesso appello della prova scritta, tranne in caso di gravi impedimenti e previo esplicito permesso dei docenti.
Sono previste tre prove in itinere (opzionali, al di fuori dell'orario di lezione). Sono esonerati dalla prova scritta coloro che hanno superato le tre prove in itinere con un voto finale numerico o "quasi sufficiente", che assume quindi il ruolo di voto della prova scritta. Sono ammessi alla terza prova in itinere solamente gli studenti che hanno svolto le prime due con un giudizio complessivo tale da rendere possibile che il giudizio finale sia almeno "quasi sufficiente"; coloro che al termine della seconda prova non soddisfano tale requisito verranno esplicitamente informati dai docenti.In parziale deroga alla regola generale, gli studenti esonerati dalla prova scritta a seguito del superamento delle prove in itinere possono svolgere la prova orale negli appelli di Dicembre o Gennaio. Dopo l'appello di Gennaio il voto delle prove in itinere non è più valido e la prova scritta deve essere necessariamente sostenuta. Gli studenti che intendano avvalersi delle prove in itinere per essere esonerati dalla prova scritta di Gennaio devono iscriversi all'appello con la dicitura "solo orale" tra le note; questo non deve essere fatto per coloro che svolgano l'orale con i compitini nel pre-appello di Dicembre.Coloro che abbiano superato le prove in itinere e consegnino una prova scritta negli appelli di Dicembre o Gennaio (senza, ovviamente, aver prima sostenuto la prova orale) perdono con ciò irrevocabilmente il voto delle prove in itinere.Il voto della prova scritta (o di quelle in itinere) contribuisce in modo sostanziale al voto finale, che di norma si discosta da esso per non più di 5 punti in aumento o diminuzione. Sono comunque possibili eccezioni sia in aumento (prova orale particolarmente brillante) che in diminuzione; pertanto, un voto superiore a 23 allo scritto non garantisce automaticamente il superamento dell'esame in caso di prova orale particolarmente insoddisfacente. Gli studenti che accedono all'orale con un voto "quasi sufficiente" allo scritto devono essere ben consci che l'orale dovrà mostrare un buon livello di preparazione affinché l'esame risulti superato, e che anche qualora questo accada il voto finale sarà quasi sicuramente basso.
Durante le prove scritte, comprese quelle in itinere, non è concesso (ed è probabilmente inutile) l'uso di alcun tipo di appunto, libro o similia, in formato cartaceo e/o digitale. È concesso l'uso di una semplice calcolatrice elettronica non programmabile. Qualsiasi accesso a smartphone o dispositivi connessi ad Internet sarà motivo dell'immediata ed irrevocabile esclusione dalla prova scritta.
Il non superamento della prova orale comporta la perdita del voto della prova scritta (o di quelle in itinere) e di conseguenza rende necessario ripeterla.I due corsi procederanno strettamente in parallelo. Gli esami scritti e le verifiche intermedie saranno identiche, svolte nelle stesse aule ed orari. Gli studenti verranno suddivisi casualmente tra le aule, indipendentemente dal corso di appartenenza formale. Analogamente, per gli esami orali gli studenti verranno divisi casualmente tra i due docenti, indipendentemente dal corso di appartenenza formale.
-
La prima prova in itinere prevede due esercizi con risposte vero/falso. In particolare, per ogni esercizio verrà fornito un testo con la descrizione di un problema e un modello parziale. Verrano proposti una serie di vincoli, funzioni obiettivo ed eventualmente variabili e per ciascuno di esso verrà richiesto se deve essere aggiunto o meno al modello parziale per completare la formulazione. Inoltre per ogni esercizio sarà presente una domanda a risposta aperta.
Alla seconda prova in itinere sono iscritti di default tutti coloro che hanno ricevuto un risultato diverso da "non ammesso" nella prima prova in itinere.La seconda prova in itinere consiste di 4 esercizi sulle tematiche dei problemi di flusso e di cammino (albero dei cammini minimi, albero di copertura di costo minimo, flusso massmo e flusso di costo minimo) analoghi a quelli illustrati durante la lezione di preparazione e disponibili sulla pagina web. Ciascun esercizio ha test a risposta multipla ed una domanda finale a risposta aperta.Alla terza prova in itinere sono iscritti di default tutti coloro che hanno ricevuto un risultato diverso da "non ammesso" nel complessivo delle due prime prove in itinere.La terza prova in itinere consiste di 4 esercizi sulle tematiche della Programmazione Lineare (condizioni di ottimalità, simplesso primale e duale algebrico o geometrico) e sugli algoritmi Branch&Bound per problemi combinatori (zaino, TSP, CSP) analoghi a quelli illustrati durante la lezione di preparazione e disponibili sulla pagina web. Ciascun esercizio ha test a risposta multipla ed una domanda finale a risposta aperta. -
Appunti di Ricerca Operativa
Indice:
- 1. Problemi e Modelli
- 1.1 Modelli e Problemi
- 1.2 Tecniche di Modellazione
- 2. Grafi e reti di flusso
- 2.1 Flussi su reti
- 2.3 Cammini di costo minimo
- 2.4 Albero di copertura di costo minimo
- 2.5 Il problema di flusso massimo
- 2.6 Il problema di flusso di costo minimo
- 2.7. Problemi di accoppiamento
- 3. Programmazione Lineare
- 3.1 Problemi di Programmazione Lineare
- 3.2 Teoria della Dualità
- 3.3 Algoritmi del Simplesso
- 4. Ottimizzazione Combinatoria
- 4.1 Introduzione
- 4.2 Programmazione Lineare Intera (Mista)
- 4.3 Dimostrazioni di Ottimalità
- 5. Algoritmi enumerativi
- 5.1 Algoritmi di enumerazione implicita
- 5.2 Implementare un algoritmo enumerativo
- 5.3 Esempi di algoritmi enumerativi
- 5.4 Tecniche poliedrali
- Appendice A: Algoritmi e Complessità
- A.1 Modelli computazionali
- A.2 Misure di complessità
- A.3 Problemi trattabili e problemi intrattabili
- Appendice B: Grafi e Reti
- B.1 I grafi: notazione e nomenclatura
- B.2 Rappresentazione di grafi ed alberi
- B.3 Visita di un grafo
Gli Appunti di Ricerca Operativa distribuiti in questa pagina sono tagliati esattamente sul contenuto del corso, e non devono essere distribuiti ad altri che non agli studenti del corso. Gli studenti interessati ad approfondire gli argomenti, comprese molte delle dimostrazioni che non vengono riportare in questi, possono consultare la versione più completa liberamente disponibile qui.Altro possibile materiale didattico:- Jon Lee A First Course in Linear Optimization Reex Press, 2013
- Fabio Schoen Optimization Models, free e-book version, 2022
- D. Simchi-Levi, X. Chen and J. Bramel Logic of Logistics: Theory, algorithms, and applications for logistics and supply chain Springer-Verlag, 2004
- M.S.Bazaraa, J.J.Jarvis, H.D.Sherali Linear programming and network flows John Wiley & Sons
- L.A. Wolsey Integer programming John Wiley & Sons
- G. Ghiani, R. Musmanno Modelli e Metodi per l'Organizzazione dei Sistemi Logistici Pitagora, 2000
- R.K. Ahuja, T.L. Magnanti, J. Orlin Network flows. Theory, algorithms and applications Prentice Hall, 1993
- F.S. Hillier, G.J. Lieberman Ricerca Operativa - Fondamenti McGraw-Hill, 2010
- C. Vercellis Ottimizzazione. Teoria, metodi, applicazioni McGraw Hill, 2008
Alcune utili risorse web (software):- Il sistema di modellazione open-source COLIOP / CMPL
- La suite di programmi LibreOffice
- The Computational Infrastructure for Operations Research (COIN-OR)
- Il solver open-source SCIP (Solver Constraint Integer Programs)
- Il sistema di modellazione Pyomo (python)
- Il sistema di modellazione PuLP (python)
- Il sistema di modellazione JuMP (Julia)
- Il sistema di modellazione YALMIP (Matlab)
- Il solver commerciale IBM/ILOG CPLEX
- Il solver commerciale Gurobi
- Il solver commerciale Mosek
- The MCFClass project
- The SMS++ Structured Modelling System
-
L'archivio contiene quattro files che illustrano dei semplici modi per risolvere effettivamente modelli di ottimizzazione utilizzando software open-source e facilmente disponibile:
- MilanNet.ods è uno spreadsheet predisposto con i dati e le formule per risolvere un'istanza del problema della MilanNet da 15 uffici e 50 clienti attraverso il Solver disponibile all'interno di LibreOffice;
- MilanNet.cmpl è uno script nel linguaggio di modellazione open-source CMPL / Coliop che modella il problema della MilanNet;
- MilanNet.cdat è il file di dati che rappresenta la stessa istanza dello spreadsheet MilanNet.ods;
- MilanNetBig.cdat è un file di dati che rappresenta un'istanza molto più grande (100 uffici e 1000 clienti) e quindi molto più difficile da risolvere.
- 1. Problemi e Modelli
-
-
-