• Programma d'esame

• Libri di testo

• Modalità d'esame

• Date d'esame

• Link (alcuni dei quali utili)

• Esercizi

• Calendario del corso

• La pagina dello scorso anno.

Programma del corso

L'obiettivo del corso è quello di introdurre alla programmazione matematica con particolare riferimento alla teoria della programmazione lineare, lineare intera e ad alcune loro loro rilevanti applicazioni. È raccomandabile avere conoscenze di Fondamenti di Informatica, Analisi Matematica, Algebra Lineare, Strutture Dati. Il programma dettagliato è ricostruibile a partire dal Calendario del corso.

Testi consigliati e da consultare

1. Matteo Fischetti, Lezioni di Ricerca Operativa, 1995, Edizioni Libreria Progetto, Via Marzolo, 28, Padova.

2. Una nota su "Introduzione alla Dualità"

3. Una nota su Minimi Alberi Ricoprenti.

4. Una nota sulla formulazione e interpretazione del duale del problema di massimo flusso

5. Una nota sulla soluzione del rilassamento lineare della formulazione PLI del knapsack binario.

6. Una nota su problemi di decisione e ottimizzazione combinatoria.

1. Carlo Mannino, Laura Palagi, Massimo Roma, Complementi ed Esercizi di Ricerca Operativa, Edizioni Ingegneria 2000, Roma.

2. Alcune utili dispense con esercizi svolti, in particolare per la parte relativa al simplesso su reti.

3. Paolo Serafini, Ottimizzazione, Zanichelli

4. Antonio Sassano, Modelli e Algoritmi della Ricerca Operativa, 1999, Franco Angeli, Milano.

5. Sara Mattia, Metodo del Simplesso Dinamico, slides

Modalità d'esame

La prova di un appello d'esame consiste in uno scritto che verte sull'intero programma del corso. La prova può prevedere domande di natura teorica. Qualora non esplicitamente indicato il contrario, è possibile utilizzare materiale didattico, come appunti e libri di testo. Non è consentito utilizzare dispositivi capaci di connessioni alle reti, come telefoni, 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.

Come prenotarsi per gli appelli d'esame: Utilizzare l'apposito modulo online sul sito delphi.uniroma2.it

Si ricorda che sono previste tre sessioni ufficiali d'esame (Ord. D.M. 270/2004). Sessione Estiva Due appelli d'esame alla fine del corso (a luglio). Sessione Autunnale Due appelli d'esame (a settembre). Nel primo appello non è consentito utilizzare materiale didattico. Sessione Invernale Un appello d'esame (a febbraio). 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 secondo anno (o 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 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 estiva

• mercoledì 16 luglio, aula 2, ore 10:30 (risultati).

• venerdì 25 luglio, aula 3, ore 14:00 (risultati).

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

Sessione invernale

• 9 febbraio 2015, aule 3 e 4, ore 11:00

Esercizi

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.

1. Prova del 16/07/14 con una proposta di soluzione.

2. Simulazione prova d'esame: trova qui il testo e qui una proposta di soluzione.

3. Prove in itinere e d'esame di RObis (Anni 2008-2013) nel repository file in fondo alla pagina.

4. Prove in itinere e d'esame di RO1bis (Anno 2007).

5. Prove in itinere e d'esame di RO1bis (Anno 2006).

6. Prove in itinere e d'esame di RO1bis (Anno 2005).

7. Prove in itinere e d'esame di RO1bisdell'A.A. 2003-04.

8. Prove in itinere e d'esame di RO1bisdell'A.A. 2002-03.

Link

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.

• 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. lunedì 3/3/14

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).

2. martedì 4/3/14 (mattina).

Geometria della PL. Definizioni di combinazione lineare, conica e convessa, Definizione di semispazio affine, poliedro, polìtopo. Teorema di Weyl-Minkowski. Def. di vertici. 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.) Forme alternative di un PL, forma canonica, forma standard. Esempi (rif. Fischetti, Sez.3.1.)

3. martedì 4/3/14 (pomeriggio).

Programmazione lineare su polìtopo non vuoto. Esempi in R². Formulazione di problemi di decisione come PL: Allocazione di risorse scarse, Problemi di miscelazione/dieta (rif. prof. A. Frangioni dispensa p.11 e segg.). Esercizi d'esame.

4. lunedì 10/3/14

Ancora sulla geometria della PL. Rappresentazione implicita di un poliedro: involucro convesso e cono di recessione. Generalizzazione del Teorema di Weyl-Minkowski nel caso di poliedri non limitati: Decomposizione di poliedri (Motzkin). (rif. dispensa prof. A. Frangioni). Definizione di base, soluzione di base, soluzione di base ammissibile (SBA). Teorema vertice = SBA(rif. Fischetti, Sez.3.2).

5. martedì 11/3/14 (mattina).

Teorema vertice = SBA: Dimostrazione. Esempi in R². Fase II del metodo del simplesso: condizione di ottimo per una SBA (costi ridotti), cambiamento di base, definizione di una nuova SBA con valore migliore della f.o. Esempi.(rif. Fischetti, Sez.3.2).

6. martedì 11/3/14 (pomeriggio).

Fase II del metodo del simplesso: Forma tableau. Esercizi. (rif. Fischetti, Sez.3.2).

6. lunedì 17/3/14

Metodo del simplesso: Forma tableau. Esempi. Fase I del metodo: definizione del problema artificiale. Determinazione di una SBA/condizioni di "vuotezza" di un PL. (rif. Fischetti, Sez.3.2).

7. martedì 18/3/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à per un PL in forma standard e "canonica". Dualità debole e forte per la PL (rif. Fischetti, Sez.4.3). Esempi.

8. martedì 18/3/14 (pomeriggio).

Esercitazione. Metodo del simplesso e formulazioni PL(I): problema di minimizzazione degli sfridi.

9. lunedì 24/3/14

Duale del problema della dieta. Problema dei trasporti (supply-demand flow): definizione, formulazione e duale. Interpretazione dei problemi duali. Dualità forte per la PL: dimostrazione.

10. martedì 25/3/14 (mattina).

Condizioni di ottimalità (ammissibilità + ortogonalità) per una coppia di PL Primale/Duale. (rif. Fischetti, Sez.4.4). Esempi. Duale del duale equivale al Primale. Scrittura del duale di PL in formati diversi. Definizione del problema di knapsack {0,1} e suo rilassamento e lineare (rif. una nota su RL di KP-{0,1}).

11. martedì 25/3/14 (pomeriggio).

Esercizi. Applicazioni delle condizioni di ottimalità al rilassamento lineare del problema di knapsack {0,1} (rif. una nota su RL di KP-{0,1}). Formulazioni PLI-{0,1}: Assegnamento (matching di peso massimo su grafo bipartito) come problema dei trasporti. (A pagina 3 di questa dispensa trovi una definizione di istanza di problema di ottimizzazione).

12. lunedì 31/3/14

Esercitazione su formulazioni PLI. A cura del dott. T.Bacci.

13. martedì 18/3/14 (mattina).

Problemi di Project Scheduling (CPM). A cura del dott. M. Senatore.

14. martedì 18/3/14 (pomeriggio).

Lezione sospesa.

15. lunedì 7/4/14

Problemi di flusso su reti: massimo flusso-minimo taglio: Formulazione PL. (rif. Ci sono una quantità di ottimi riferimenti in rete. Per esempio puoi cominciare da qui).

16. martedì 8/4/14 (mattina).

Lezione sospesa (FORUM).

17. martedì 8/4/14 (pomeriggio).

Formulazione PL e duale del problema di massimo flusso (rif. Agnetis una nota sul problema di massimo flusso).

18. lunedì 14/4/14

Problemi di flusso a costo minimo. Il simplesso su reti (rif. Agnetis una nota su flusso a costo minimo e simplesso su reti). Soluzioni di base e alberi ricoprenti.

19. martedì 15/4/14 (mattina).

Simplesso su reti: condizione di ottimo e di illimitatezza. Cambiamento di base (rif. Agnetis una nota su flusso a costo minimo e simplesso su reti). Esercizi (rif. Locatelli dispense con esercizi svolti).

20. martedì 15/4/14 (pomeriggio).

Applicazioni della dualità nella PL: analisi di sensibilità (rif. Fischetti, Sez.4.8). Esempi ed esercizi.

21. lunedì 28/4/14

Ricapitolazione ed esempi sulla PL e sulla dualità per la PL: Metodo del simplesso revised (rif. Fischetti, Sez.3.3); il metodo duale del simplesso (rif. Fischetti, Sez.4.7 e 4.8). Regola di Bland.

22. martedì 29/4/14 (mattina).

Ancora sul metodo del simplesso duale: introduzione di vincoli aggiuntivi. Esercitazione: formulazione di problemi come PL: la programmazione della produzione.

23. martedì 29/4/14 (pomeriggio).

Esercitazione: tableau iniziale per il simplesso duale. Analisi di sensibilità. Introduzione alla PL intera. Unimodularità Esempi (rif. Fischetti, Sez.5.2).

23. martedì 29/4/14 (pomeriggio).

Esercitazione: tableau iniziale per il simplesso duale. Analisi di sensibilità. Introduzione alla PL intera. Unimodularità Esempi (rif. Fischetti, Sez.5.2).

24. lunedì 5/5/14

PL intera: totale unimodularità. Condizioni sufficienti di totale unimodularità di una matrice. Conseguenze nella PLI. Problemi di flusso a costo minimo.

25. martedì 6/5/14 (mattina).

Ancora sulla PL intera e totale unimodularità. Problemi di flusso massimo, matching e assegnamento, massimo insieme stabile: formulazioni PLI e casi particolari.

26. martedì 6/5/14 (pomeriggio).

La lezione non si è tenuta.

27. lunedì 12/5/14.

Metodi per la PL intera. Introduzione a tecniche di enumerazione implicita: Branch and Bound. Esempi. Applicazione a problemi di knapsack {0,1}.

28. martedì 13/5/14 (mattina).

Ancora su branch and bound e sulla sua applicazione a problemi di knapsack {0,1}. Metodi dei piani di taglio. Diseguaglianze di Chavatál, tagli di Gomory.

29. martedì 13/5/14 (pomeriggio).

Tagli di Gomory: applicazione su tableau con il metodo duale del simplesso.

(FINE DELLA PARTE DI CORSO RELATIVA ALL'ESAME DA 6 CREDITI)

Modelli di PL intera: Uniform Facility Location.

30. lunedì 19/5/14.

Uniform Facility location: formulazioni forte e debole. Soluzione ottima del rilassamento continuo fornito dalla formulazione debole. Capacitated Facility Location: formulazione derivata dalla formulazione debole.

31. martedì 20/5/14 (mattina).

Metodo del simplesso dinamico "primale": applicazione a un problema di cammino di costo minimo su reti (rif. Sara Mattia Una presentazione del metodo del simplesso dinamico ).

32. martedì 20/5/14 (pomeriggio).

Metodo del simplesso dinamico duale: applicazione al problema di Cutting Stock. (rif. A. Agnetis Una nota sui metodi di generazione colonne).

33. lunedì 26/5/14 (pomeriggio).

Il problema di Uniform Facility Location. Determinazione di lower bound con il metodo di ascesa duale (rif. A. Agnetis Una nota sull'algoritmo di ascesa duale per il problema di localizzazione degli impianti). A. Sassano Ascesa Duale: Idea base ed Esempio.

34. martedì 27/5/14 (mattina).

Tecniche di rilassamento lagrangiano per la determinazione di bound duali (lower bound) per problemi di programmazione lineare {0,1}. Definizione di rilassamento lagrangiano, problema duale lagrangiano, relazioni tra rilassamento continuo e duale lagrangiano. (rif. P. Detti Note sul R.L. nei problemi di ottimizzazione combinatoria.

35. martedì 27/5/14 (pomeriggio).

Metodo del subgradiente per il duale lagrangiano: definizione di subgradiente e schema dell'algoritmo. (rif. P. Detti Note sul R.L. nei problemi di ottimizzazione combinatoria). Esercizi: formulazione di problemi di decisione come PL - Prova d'esame del 19/2/14.

36. martedì 3/6/14 (mattina).

Lezione sospesa.

37. martedì 27/5/14 (pomeriggio).

Formulazione di problemi di ottimizzazione combinatoria (rif. dispensa su Problemi di decisione e ottimizzazione combinatoria OC.pdf).

38. lunedì 9/6/14.

Formulazione di problemi di ottimizzazione combinatoria e intera mista (MIP). Relazioni logiche (implicazioni) e corrispondenti modelli di ottimizzazione lineare intera. Formulazione di vincoli disgiuntivi: problemi di sequencing e scheduling (rif. dispensa su Problemi di decisione e ottimizzazione combinatoria OC.pdf).

39. martedì 10/6/14 (mattina).

Ancora sulla formulazione come MIP di problemi di scheduling. Uso dei vincoli disgiuntivi per modellare funzioni di costo con costi fissi, lineari a tratti etc. (rif. dispensa su Problemi di decisione e ottimizzazione combinatoria OC.pdf).

40. martedì 10/6/14 (pomeriggio).

Esercitazione: prove d'esame.

41. lunedì 16/6/14.

Ricevimento collettivo.

42. martedì 17/6/14 (mattina).

lezione sospesa.

40. martedì 17/6/14 (pomeriggio).

Ricevimento collettivo. Soluzioni prova simulazione d'esame (vedi file allegato exam_sim.pdf). Fine del corso.