Pagina aggiornata il 13 ottobre 2014. La pagina è stata recentemente spostata qui su google. Prego tutti i lettori di segnalarmi malfunzionamenti e/o link errati. Grazie!
In questo anno accademico sono attivi tre corsi per l'insegnamento della ricerca operativa. Questo, denominato Ricerca Operativa (J-Z) 2013-14, è impartito da Gianpaolo Oriolo (nel primo emisemestre, su grafi e reti: vedi qui la pagina relativa) e da Andrea Pacifici (nel secondo emisemestre, sulla programmazione lineare). Devono seguire questo canale:
tutti gli studenti di Ingegneria Informatica indirizzo Automazione;
tutti gli studenti di Ingegneria Matematica;
gli studenti di Ingegneria Gestionale il cui cognome inizia con una lettera compresa nell'intervallo J-Z.
Avvisi
Qui leggi gli avvisi e le informazioni più urgenti. La pagina viene aggiornata spesso: ricorda di effettuare il "reload" per la versione più recente.
Verbalizzazioni : mercoledì 15 ottobre, ore 16 presso ufficio prof. Oriolo; venerdì 24 ottobre, ore 11.30 presso ufficio prof. Pacifici.
I risultati finali dell'appello d'esame del 26/09/14 sono disponibili qui.
I risultati per la parte II dell'appello d'esame del
26/09/14 sono disponibili qui (scheda "Autunnale"). Trovi qui il testo d'esame e una proposta di soluzione. I risultati finali dell'appello d'esame del 26/09/14 sono disponibili qui.
12/09/14 sono disponibili qui (scheda "Autunnale"). Qui potete trovare i risultati finali di Ricerca Operativa nel primo appello di settembre.
25/07/14 sono disponibili qui (scheda "Estiva")
I risultati della sessione invernale sono consultabili su questo documento.
Indice
Avvisi (annunci, calendario degli esami, valutazioni)
Esercizi prove assegnate agli appelli d'esame e tipologia degli esercizi per le prove in itinere
Calendario del corso (gli argomenti svolti nelle singole lezioni)
Qui la pagina dello scorso A.A. 2012-13 (esami, appelli, risultati ecc.)
Coordinate
Semestre: I, emisemestre II
Crediti: 12 (parti I e II).
Ricevimento: per appuntamento inviando mail all'indirizzo andrea.pacifici@uniroma2.it
Orari: sempre in Aula A1 (Nuovo Complesso della didattica, piano 0).
martedì ore 11:30-13:00 e ore 16:00-17:30;
giovedì ore 11:30-13:00;
venerdì ore 09:30-11:00.
Programma del corso
Obiettivi: II parte: Introdurre alla teoria della programmazione lineare e ad alcune loro applicazioni rilevanti.
Prerequisiti. È raccomandabile aver seguito i moduli di Analisi Matematica 1 e 2, di Geometria 1 e di Informatica 1.
Programma. Consulta qui gli argomenti per la II parte del corso di questo A.A. 2013-14.
Testi adottati e da consultare
Matteo Fischetti, Lezioni di Ricerca Operativa, 1995, Edizioni Libreria Progetto, Via Marzolo, 28, Padova.
Carlo Mannino, Laura Palagi, Massimo Roma, Complementi ed Esercizi di Ricerca Operativa, Edizioni Ingegneria 2000, Roma.
Una nota su "Introduzione alla Dualità"
Una nota su Minimi Alberi Ricoprenti.
Una nota sulla formulazione e interpretazione del duale del problema di massimo flusso
Una nota sulla soluzione del rilassamento lineare della formulazione PLI del knapsack binario.
Alcune utili chiare dispense con esempi del gruppo di ottimizzazione dell'Università di Pisa, in particolare per la parte sui modelli (cap. 1) e la geometria (cap. 3) della PL.
Alcune utili dispense con esercizi svolti, in particolare per la parte relativa al simplesso su reti.
Modalità d'esame
Le sessioni ufficiali d'esame (Ord. D.M. 270/2004) sono le seguenti:
Sessione invernale Due prove d'esonero più un appello d'esame alla fine del corso (a febbraio).
Sessione estiva Due appelli alla fine del II semestre (giugno-luglio). Nel primo appello non è consentito utilizzare materiale didattico.
Sessione autunnale Due appelli (a settembre). Nel primo appello non è consentito utilizzare materiale didattico.
Ci si prenota agli appelli d'esame utilizzando obbligatoriamente l'apposito modulo online sul sito delphi.uniroma2.it
Notate che esistono quindi due distinte modalità d'esame:
Due prove scritte d'esonero distinte, durante l'erogazione del corso di uno stesso anno accademico. Nel dettaglio, la prima prova, a inizio dicembre, verte sul programma svolto da Gianpaolo Oriolo (prima parte del corso), la seconda prova, a inizio febbraio, verte sul programma svolto da Andrea Pacifici (seconda parte del corso).
Prova scritta singola, che copre gli argomenti sia della prima parte che della seconda parte del corso. Tale modalità è obbligatoria negli appelli d'esame da marzo a settembre.
Si ricevono due voti distinti sulle due parti (indipendentemente dalla modalità). Il voto finale d'esame è la media in trentesimi dei voti conseguiti nelle due parti arrotondata all'intero più vicino.
È possibile richiedere di integrare il voto con un colloquio orale che verte su tutto il programma della prima e della seconda parte. Può richiedere il colloquio orale solo chi ha raggiunto la votazione di almeno 18/30 sulla prova scritta; in ogni caso il colloquio può variare il voto della prova scritta in un intorno di più o meno 4 voti (eventualmente pregiudicando la sufficienza).
Si ricorda che durante le prove d'esame:
È consentito utilizzare materiale didattico, come appunti e libri di testo solo in alcuni appelli d'esame (vedi sopra) e che la prova d'esame può prevedere domande di natura teorica.
Non è consentito utilizzare dispositivi capaci di qualsivoglia connessione wireless come PC, tablet, smartphone.
È necessario dotarsi di fogli su cui produrre l'elaborato e avere con sé un documento di identità o il libretto universitario.
Non è permesso in alcun caso sostenere prove d'esame su parti del programma allo scopo di migliorare un voto precedentemente acquisito.
Inoltre:
La partecipazione a un appello d'esame implica l'automatico decadimento di eventuali voti conseguiti in precedenza.
I voti conseguiti si conservano per tutto e solo l'anno accademico in corso (cioè fino alla sessione autunnale di settembre).
Gli studenti che devono sostenere gli esami da 5 CFU (Grafi e Reti di Flusso e Ricerca Operativa 1) e 10 cfu (Ricerca Operativa) previsti dal vecchio ordinamento (D.M. 509/1999) possono sostenere gli esami negli stessi appelli previsti per l'Ord. D.M. 270/2004.
Appelli d'esame straordinari. In casi di comprovata urgenza, per esempio se il mancato sostenimento dell'esame causa uno slittamento della sessione di laurea, uno studente, solo se è iscritto al terzo anno (o terzo ripetente), può chiedere al docente di indire un appello straordinario al di fuori delle sessioni ufficiali. Si ricordi che, secondo le regole attualmente in vigore in Facoltà, in uno stesso A.A. uno studente può sostenere al più un esame in un appello straordinario e che la convocazione di un appello straordinario è a discrezione del docente titolare del corso e del Consiglio di Corso di Studi.
Date d'esame
Sessione invernale
Esoneri: I parte il 2/12/13; II parte 28/1 (aule B1 e B4 ore 16:00, prenotazione su delphi).
Mer 19/02/14 (aule A2, A3 e A4 ore 11:30).
Sessione estiva
Ven 25/07/14, ore 14, aula 3.
Sessione autunnale
venerdì 12 settembre, aule 3 e 4, ore 14:00 (Nel I appello non è consentito utilizzare materiale didattico.)
venerdì 26 settembre, aule 3 e 4, ore 14:00
Esercizi
Per la parte del corso relativa alla teoria dei grafi, potete scaricare da qui i testi e le soluzioni di alcune prove degli scorsi A.A. per la I parte del corso di Ricerca Operativa (già Grafi e Reti di Flusso (Ord. D.M. 509)) tenuti dal prof. Oriolo presso questa Facoltà.
Per la II parte del corso relativa alla programmazione matematica (già Ricerca Operativa 1 (Ord. D.M. 509)), potete scaricare qui i testi di alcune prove in itinere e d'esame dei corsi di Ricerca Operativa tenuti negli scorsi AA.AA. per vari corsi di laurea.
Paolo Serafini, Ottimizzazione, Zanichelli
Antonio Sassano, Modelli e Algoritmi della Ricerca Operativa, 1999, Franco Angeli, Milano.
Trova qui alcune prove per il corso RO per la LM in Ing. Informatica (Prova del 16/07/14 con una proposta di soluzione, e una simulazione d'esame con testo e proposta di soluzione).
Prove in itinere e d'esame di RObis (Anni 2008-2013) nel repository file in fondo alla pagina del corso per la LM in Ing. Informatica.
Link utili
Questi link contengono dispense, esercizi, software freeware, curiosità relativi al mondo della ricerca operativa.
GUROBI - Software per l'ottimizzazione lineare, intera e quadratica.
IBM ILOG CPLEX - Altro software per l'ottimizzazione lineare, intera e quadratica.
A.I.R.O - l'associazione italiana di Ricerca Operativa
Michael Trick's Home Page - una quantità di informazioni e link orientati alla Ricerca Operativa.
INFORMS - la pagina della "International Federation of Operations Research and Management Science"
U.M.I. - Unione Matematica Italiana
La pagina didattica di Fabio Schoen - dispense, lucidi, esercizi, software e molte altre risorse per gli studenti di R.O.
La pagina didattica di Alessandro Agnetis - alcune chiare dispense ed utili esercizi su argomenti chiave di un corso di R.O.
La pagina didattica del gruppo di Ottimizzazione dell'Università di Pisa - altre utili risorse per gli studenti di R.O.
Punk Rock Operations Research (sic!) un'operazione di marketing per la Ricerca Operativa, con alcune discussioni su applicazioni interessanti dei modelli di ottimizzazione.
Agenda del corso
1. martedì 26/11/13 mattina.
Lezione sospesa.
2. martedì 26/11/13 pomeriggio.
Introduzione al corso di Ricerca Operativa: problemi di decisione e di programmazione matematica. Definizioni relative ai di problema di programmazione matematica: variabili decisionali, vincoli, funzione obiettivo. Problema vuoto, illimitato con ottimo finito (rif. Fischetti, Sez.1.1, Sez.2). Modelli e formulazione come problema di programmazione lineare del problema di allocazione di risorse Problemi di ottimizzazione combinatoria. (rif. Fischetti, Sez.6.1, 6.2, 6.3).
3. giovedì 28/11/13.
Esercitazione sulla prima parte del corso (a cura del dott. M. Senatore).
4. venerdì 29/11/13.
Forme alternative di un PL, forma canonica, forma standard. Geometria della PL: Definizioni di combinazione lineare e convessa, funzioni convesse, semispazio affine, poliedro, polìtopo. Esempi. (rif. Fischetti, Sez.3.1).
5. martedì 3/12/13 mattina.
Geometria della PL, definizioni: facce, vertici di un polítopo. Involucro (o inviluppo) convesso. Combinazione conica. Rappresentazione implicita di un poliedro. Cono di recessione di un poliedro. Teorema di Weyl-Minkowski. (rif. Fischetti, Sez.3.1. e dispense U. Pisa: cap. 3).
6. martedì 3/12/13 pomeriggio.
Teorema: In un problema di programmazione matematica con f.o. concava e regione ammissibile P, polìtopo non vuoto, esiste un ottimo su un vertice di P. (Dimostrazione.) Esercizi, modelli di PL: problema di miscelazione/dieta (a pagina 11 di questa dispensa trovi il riferimento).
7. giovedì 5/12/13.
Definizione di base, soluzione di base, soluzione di base ammissibile (SBA). Esempi in R2. Definizione di (sotto-)vettore dei costi ridotti: condizione di ottimo per una SBA.
8. venerdì 6/12/13.
La lezione di venerdì 6 dicembre è sospesa (Sospensione della didattica, decreto rettorale 3826 del 27/11/2013).
9. martedì 10/12/13 mattina.
Teorema vertice = SBA. (Dimostrazione.) Il metodo del simplesso: condizione di ottimo per una SBA, condizione di illimitatezza del PL. Esempi. Forma tableau. Esempi. (rif. Fischetti, Sez.3.2).
10. martedì 10/12/13 pomeriggio.
Esercitazione: formulazione di problemi di PL. Uso del foglio elettronico per la rappresentazione e la soluzione di un PL (trova qui due file che descrivono un esempio introduttivo). Un problema di PL nel mondo reale: produzione di computer in DEC alla fine degli anni '80 (esempio tratto dal testo Linear Optimization, cap. 1, pagg. 7-10: trova qui l'esempio e il corrispondente foglio elettronico).
11. giovedì 12/12/13.
Fase II del metodo del simplesso: cambiamento di base, definizione di una nuova SBA con valore migliore della f.o.
12. venerdì 13/12/13.
Convergenza e degenerazione. Regola di Bland. Fase I del metodo del simplesso. Definizione del problema artificiale. (rif. Fischetti, Sez.3). Esercizio: formulazione di problema di decisione come PL.
13. martedì 17/12/13 mattina.
Fase I del metodo del simplesso: determinazione di una SBA per il problema originale. Esercizi di ricapitolazione del metodo con il tableau.
14. martedì 17/12/13 pomeriggio.
Esercitazione: formulazione di problemi di PL (problema dei trasporti, problema di minimizzazione degli sfridi). Problema di matching su grafo bipartito come problema dei trasporti.
15. giovedì 19/12/13.
Lezione sospesa. La lezione sarà recuperata nel mese di gennaio (lun 13 e gio 16 dalle ore 16 alle ore 17.30).
16. venerdì 20/12/13.
Metodo del simplesso revised: fase II (rif. Fischetti, Sez.3.3). Esempio su problema di allocazione risorse. Definizione del problema di facility location (rif. Sassano slide della lezione 11.)
17. martedì 7/1/14 mattina.
Introduzione alla teoria della dualità per la PL: Rilassamento di un problema di ottimizzazione. Rilassamento lagrangiano di un PL e determinazione del duale di un PL (rif. Dispensa "Introduzione alla Dualità"). Dualità di PL in forma standard e "canonica". Dualità debole (rif. Fischetti, Sez.4.3).
18. martedì 7/1/14 pomeriggio.
Dualità forte per la PL (rif. Fischetti, Sez.4.3). Esercitazione: il duale del duale equivale al primale. Scrittura del duale di PL in formati diversi. Il problema dei trasporti come PL e il suo duale.
19. giovedì 9/1/14.
Teoria della dualità per la PL: Interpretazione economica del duale: problemi dei trasporti e della dieta. Condizioni di ortogonalità per una coppia di PL Primale/Duale. (rif. Fischetti, Sez.4.4).
20. venerdì 10/1/14.
Esercizi e applicazioni delle condizioni di ottimalità: rilassamento lineare del problema di knapsack {0,1} e sua soluzione ottima attraverso le condizioni di ortogonalità (rif. una nota su RL di KP-{0,1}). Altri esercizi d'esame.
21. lunedì 13/1/14 (recupero lez. 15).
Esercitazione a cura del Dr. M. Senatore. Formulazione PL e duale del problema di massimo flusso (rif. Agnetis una nota sul problema di massimo flusso).
22. martedì 14/1/14 mattina.
Dualità per la PL: Il metodo duale del simplesso (rif. Fischetti, Sez.4.7 e 4.8). Ricapitolazione ed esempi.
23. martedì 14/1/14 pomeriggio.
Dualità per la PL: Ricapitolazione ed esempi. Esempio di analisi di sensibilità (rif. Fischetti, Sez.4.8).
24. giovedì 16/1/14.
Dualità per la PL: Analisi di sensibilità (rif. Fischetti, Sez.4.8) Studio di esempi per via grafica e analitica.
25. giovedì 16/1/14 pomeriggio (recupero lez. 8)
Problemi di flusso a costo minimo. Introduzione al simplesso su reti (rif. Agnetis una nota su flusso a costo minimo e simplesso su reti).
26. venerdì 17/1/14.
Ancora sul simplesso su reti. Fase II (rif. Locatelli dispense con esercizi svolti.)
27. martedì 21/1/14 mattina.
Simplesso su reti: ricapitolazione e cenni su fase I. Esercizi d'esame: programmazione della produzione.
28. martedì 21/1/14 pomeriggio.
Esercitazione. Formulazione di problemi di programmazione della produzione.
29. giovedì 23/1/14 pomeriggio.
Esercizi di ricapitolazione su formulazioni PL(I), simplesso duale, dualità per la PL.
30. venerdì 24/1/14.
Esercitazione su simplesso su reti e formulazioni PL(I). Fine del corso.
31. martedì 28/1/14 ore 11:30-12:30.
Ricevimento studenti in aula A1.
32. martedì 28/1/14 ore 16:00-17:30.
Prova d'esonero.