Ricerca Operativa I

Docente

Dario Pacciarelli

Orari

vedi orario ufficiale sul sito del Dipartimento di Ingegneria

 

Ricevimento

Giovedì dalle 11:30 alle 13:00, stanza DIA2.31

Esami & Esoneri

Calendario degli esami
Ricerca Operativa I - Ing. Informatica

Vedi calendario ufficiale del Collegio Didattico in Ingegneria Informatica

Ricerca Operativa - Ing. Civile/Elettronica/Meccanica

Vedi calendario ufficiale del Collegio Didattico di Ingegneria Civile

 

Modalità di Esame

Nel periodo di emergenza COVID-19 gli esami si svolgeranno secondo quanto previsto dai decreti rettorali di riferimento. Vedi sezione "Comunicazioni"

Ricerca Operativa I - Ing. Informatica

L'esame consiste in una prova scritta selettiva e una prova orale, secondo il calendario indicato. Accede all'orale chi ha conseguito una valutazione almeno "quasi sufficiente" allo scritto. Nel primo appello d'esame lo scritto include una domanda di teoria e pertanto la prova orale è facoltativa per chi ha conseguito una valutazione compresa nell'intervallo [18,26]. L'orale è obbligatorio per chi ha conseguito allo scritto una valutazione "quasi sufficiente" o compresa in [27,30]. Negli appelli successivi al primo lo scritto comprende solo esercizi e l'orale è obbligatorio per tutti gli ammessi all'orale.

Ricerca Operativa - Ing. Civile/Elettronica/Meccanica

L'esame consiste in una prova scritta selettiva e una prova orale, secondo il calendario indicato. Accede all'orale chi ha conseguito una valutazione almeno "quasi sufficiente" allo scritto. Lo scritto include una domanda di teoria e pertanto la prova orale è facoltativa per chi ha conseguito una valutazione compresa nell'intervallo [18,30]. L'orale è obbligatorio per chi ha conseguito allo scritto una valutazione "quasi sufficiente" o per chi aspira alla lode. 

Comunicazioni

 

- AVVISO - Risultati del 7/7/2021

Sono stati pubblicati su Moodle i risultati della prova del 7 luglio,  pubblicati anche su GOMP (solo sufficienti) in modalità silenzio/assenso. Gli studenti che hanno conseguito una valutazione sufficiente possono rifiutare il voto fino a una settimana dopo la pubblicazione (in questo caso si suggerisce di comunicare la decisione anche a dario.pacciarelli@uniroma3.it in quanto non sempre la rinuncia viene registrata correttamente da GOMP), il 29 luglio il voto diventerà definitivo e sarà verbalizzato. 

Gli studenti che hanno necessità di verbalizzare il voto prima del 29/7 (per esempio per partecipare a borse di studio con scadenza 28/7) possono verbalizzare il voto con la modalità “approvazione immediata”, che tuttavia richiede di concludere l’esame in presenza (anche telematica). Allo scopo, venerdì 23 luglio alle ore 15:00 attiverò una riunione nel canale Teams utilizzato per le lezioni. Chi desidera la verbalizzazione immediata (in data 23/7) può semplicemente collegarsi al canale alle 15:00. Potrete comunicarmi a voce l’accettazione del voto e procederò alla verbalizzazione immediata.

 

 

- AVVISO - procedura prove intermedie e appelli d'esame del 16/6/2021 e 7/7/2021

 

La prova sarà organizzata presso le sedi dell’Ateneo con una prova scritta in presenza. La data è a scelta dello studente in fase di prenotazione all'esame (su GOMP). La suddivisione in aule (N10, N11 e N1 o N14) e orario di inizio verrà pubblicata su Moodle (cartella "Assegnazione aule e turni") Lunedì 14/6. La prova sarà articolata in due esercizi e una domanda di teoria.

 

 

- AVVISO - procedura d'esame sessione di giugno/luglio 2021

 

NB: Se non interverranno provvedimenti d'emergenza nei prossimi giorni le modalità d'esame saranno le seguenti

 

La prova d'esame sarà organizzata come regolato dal Decreto Rettorale n. 1096 del 20 luglio 2020, che prescrive come modalità d'esame standard l'esame in presenza presso le sedi dell’Ateneo. In particolare, l'esame sarà organizzato con una prova solo scritta in presenza che si terrà, per ciascun appello, nel giorno e nell'aula indicati dal calendario degli esami. La prova sarà articolata in due esercizi e una domanda di teoria.

 

Per evitare assembramenti gli studenti verranno chiamati per gruppi in ordine alfabetico (del cognome), identificati e allocati ai posti a partire dall'orario previsto. Ogni studente dovrà tenere pronto un documento per l'identificazione all'ingresso in aula e dovrà accedere al proprio posto dalle scale laterali dell'aula.

 

Dentro e fuori dall'aula gli studenti dovranno sempre mantenere la distanza interpersonale di sicurezza e dovranno indossare la mascherina di protezione per tutta la durata della prova.

 

Durante tutta la prova gli studenti non potranno alzarsi dal posto e dovranno rimanere in aula fino al termine della stessa. Il sorvegliante d'aula riporterà presenze e assenze sull'elenco dei prenotati. Dopo il controllo dei documenti e l'avvio della prova rimarrà fermo alla cattedra per tutto il tempo. 

 

Al termine della prova gli studenti dovranno uscire dall'aula, utilizzando la scala centrale, uno per volta  seguendo un appello nominale e consegneranno il proprio elaborato in una scatola posta sulla cattedra.
 

Tutti gli studenti che avranno conseguito una valutazione tra 18 e 30 vedranno il voto pubblicato su GOMP con la modalità "silenzio/assenso e verbalizzazione posticipata", chi vuole rifiutare il voto dovrà farlo su GOMP rifiutando il voto pubblicato (in questo caso si suggerisce di comunicarlo anche a dario.pacciarelli@uniroma3.it in quanto non sempre la rinuncia viene registrata correttamente da GOMP). La verbalizzazione effettiva del voto avverrà una settimana dopo la pubblicazione.

 

- AVVISO - modalità d'esame sostitutiva a fronte di richieste motivate

 

Gli studenti che presentano una richiesta motivata entro il giorno della scadenza delle prenotazioni (per es. documentate esigenze di salute) possono sostenere l'esame secondo quanto previsto all’art.1 del Decreto Rettorale n°. 703 del 5 maggio 2020. Quindi, con esame esclusivamente orale in modalità telematica, utilizzando la piattaforma Teams, sul team "Ricerca Operativa I". La richiesta va presentata inderogabilmente entro il giorno della scadenza delle prenotazioni all'esame inviando un messaggio email a pacciarelli@ing.uniroma3.it, indicando le motivazioni dettagliate della richiesta e allegando l'eventuale documentazione comprovante l'esigenza. La richiesta potrà essere accolta o meno e la decisione sarà notificata al richiedente per email entro il giorno successivo alla scadenza delle prenotazioni. Se la richiesta non sarà accolta si dovrà sostenere lo scritto in presenza nella data prevista per lo scritto, altrimenti si dovrà sostenere la sola prova orale a distanza nella data indicata nell'email di notifica (tipicamente il giorno successivo a quello dello scritto).

 

- AVVISO - Risultati prove intermedie del 21 e 23 aprile  2021

 

Cari studenti, è terminata la correzione delle prime prove intermedie. Dei 214 presenti nelle due date, oltre l’80% sono stati ammessi alla seconda prova (voto da 16 a 30) e quasi il 30% con voto maggiore di 26. Trovate i risultati individuali su GOMP tra le prove intermedie. Per tutti risulta come data della prova il 23/4, anche per chi ha sostenuto la prova il 21/4. Gli ammessi alla seconda prova potranno decidere in quale data effettuare la seconda prova intermedia (una sola volta: 16/6 o 7/7). Allo scopo è necessario prenotarsi all’esame in una delle due date, il giorno dello scritto sarà possibile scegliere se sostenere l’esame o la seconda prova intermedia. Tutti (ammessi e non) potranno sostenere l’esame in una sola delle due date, e consegnando l’elaborato dell’esame rinunciano all’eventuale voto della prima prova intermedia. E’ possibile sostenere la seconda prova intermedia il 16/6 e l’esame il 7/7, allo scopo è necessario consegnare l’elaborato della seconda prova intermedia il 16/6.

 

- AVVISO - Risultati del 3/2/2021

Sono stati pubblicati su GOMP (solo sufficienti) i risultati della prova del 3 febbraio in modalità silenzio/assenso. Gli studenti che hanno conseguito una valutazione sufficiente possono rifiutare il voto fino al 16 febbraio (in questo caso si suggerisce di comunicare la decisione anche a dario.pacciarelli@uniroma3.it in quanto non sempre la rinuncia viene registrata correttamente da GOMP), dal 17 il voto diventerà definitivo. I risultati sono pubblicati anche sulla pagina Moodle del corso https://moodle1.ing.uniroma3.it/.

 

Test di inizio corso

Con questo test (file.pdf) puoi verificare il possesso dei prerequisiti minimi per seguire il corso di Ricerca Operativa I.

 

 

Materiale Didattico

Libro di testo per il corso di Ricerca Operativa I del collegio di Ing. Informatica

 

Dispense per il corso di Ricerca Operativa dei collegi di Ing. Civile/Elettronica/Meccanica

 

Esercizi Ing. Informatica (Dowload Acrobat Reader)

Nota: gli esercizi presenti in questa sezione fino a giugno 2013 utilizzano la notazione adottata negli anni passati, simile a quella utilizzata nel libro di testo per la prima parte del corso ma non uguale. Per gli esercizi di formulazione la notazione  è equivalente. Da aprile 2014 viene adottata la nuova notazione.

Nota: dal 2018/19 il simplesso su reti non è più in programma

Esercizi Ing. Civile/Elettronica/Meccanica (Dowload Acrobat Reader)

 

 

Programma Ricerca Operativa I - Ing. Informatica (dall'A.A. 2018-19 a oggi)

Programma delle Lezioni  (tra parentesi i riferimenti ai capitoli del libro di testo)

    1. Introduzione alla Ricerca Operativa

Formulazioni, il metodo delle 5 fasi (cap 1)
Richiami di Algebra Lineare (cap 5)

    1. Formulazione di tipici problemi di ottimizzazione (cap 2)

Miscelazione
Allocazione di risorse
Gestione delle scorte
Taglio ottimo
Assegnazione
Pianificazione di attività 

    1. Soluzione di problemi di Programmazione Lineare

Geometria della Programmazione lineare (cap 6)
Algoritmo del simplesso  (cap 8)

Algoritmo di Fourier-Motzkin (cap 9.3)
Interpretazione geometrica del simplesso  (cap 6)

    1. Teoria della dualità (cap 7)

Costruzione del problema duale
Teorema fondamentale della PL
Condizioni di complementarità
Interpretazione economica del duale
Analisi di sensitività

    1. Ottimizzazione su grafi  (cap 12, 14, 15, 16)

Massimo flusso
Cammino minimo
Minimo albero ricoprente

 

 

Programma Ricerca Operativa - Ing. Civile/Elettronica/Meccanica (dall'A.A. 2014-15 a oggi)

Programma delle Lezioni del primo modulo  

    1. Elementi di programmazione matematica

Programmazione convessa
Programmazione lineare

    1. Formulazione di tipici problemi di ottimizzazione

Miscelazione
Allocazione di risorse
Gestione delle scorte
Taglio ottimo
Pianificazione di attività 

    1. Soluzione di problemi di Programmazione Lineare

Geometria della Programmazione lineare
Algoritmo del simplesso
Interpretazione geometrica del simplesso 

    1. Teoria della dualità

Costruzione del problema duale
Teorema fondamentale della PL
Condizioni di complementarità
Interpretazione economica del duale
Analisi di sensitività

    1. Ottimizzazione non vincolata 

Gradiente e matrice Hessiana
Condizioni necessarie di minimo del primo e del secondo ordine
Condizioni sufficienti di minimo locale
Condizioni sufficienti di minimo globale nel caso convesso
Metodo del gradiente
line search esatta, metodo di Armijo e di interpolazione
Convergenza sublineare, lineare, superlineare
Metodo di Newton
Limiti dei metodi per funzioni non differenziabili 

    1. Ottimizzazione vincolata 

Matrice Jacobiana e vincoli attivi
Funzione Lagrangiana
Condizioni di Karush Kuhn Tucker
Cenni sulle funzioni di penalità e sui metodi di barriera

Elenco delle dimostrazioni in programma 

condizioni sufficienti di ottimo di una SBA nella PL
vertice di un poliedro = SBA 
dualità debole
dualità forte
condizioni di ortogonalità
Teorema 2  dispensa PNL non vincolata
 condizioni di ottimalità (1 e 2 ordine) nella PNL non vincolata
programmazione covessa, min locale=min globale

 

Calendario delle lezioni 2020/21 (Ing. Informatica) in rosso sono riportate le modifiche recenti

 

DATA

ARGOMENTO

2/3/2021

 Introduzione al corso.

4/3/2021

 Ripasso di Algebra, operazioni tra vettori e matrici. Operazione di pivot, metodo di Gauss. Esempi

9/3/2021

Formulazione di un problema di PL. Metodo delle 5 fasi.  

Soluzione di un problema di PL: il metodo grafico. Esempi.

11/3/2021

Soluzione di un problema di PL: metodo di Fourier-Motzkin. Formulazioni: il problema di miscelazione. Esempi.

16/3/2021

 Geometria poliedrale: poliedri, vertici e direzioni. Teorema di Weyl-Minkowski.

18/3/2021

 Condizioni geometriche di ottimalità e illimitatezza nella PL. Forme equivalenti di un problema di PL: la forma standard. 

23/3/2021

 Geometria e algebra della PL: Soluzioni base ammissibili e relazione tra vertici e soluzioni di base ammissibili.

25/3/2021

Soluzione di un problema di PL: condizioni algebriche di ottimalità e illimitatezza.

30/3/2021

Algoritmo del simplesso: la Fase 2. Interpretazione geometrica del Simplesso e cambiamento di base.
1/4/2021 Algoritmo del simplesso: aggiornamento della matrice inversa, il metodo rivisto. 
8/4/2021 Algoritmo del simplesso: Fase 1 e fase 2. Il problema artificiale. Convergenza e degenerazione nell’algoritmo del simplesso. Regola di Bland.

13/4/2021

 Passaggio dalla fase 1 alla fase 2 nel metodo rivisto.
15/4/2021 Esercizi di ripasso

19-23 /4/2021

 

PRIMA PROVA INTERMEDIA 

aule N1, N10, N11 ore 16:00-19:00

 

27/4/2021

Introduzione alla teoria dei grafi: definizioni e notazioni. Albero ricoprente di peso minimo: algoritmo di Kruskal, algoritmo di Prim
29/4/2021

Albero ricoprente di peso minimo: algoritmo di Prim-Dijkstra

4/5/2021

 Problema di percorso minimo: algoritmo di Dijkstra. Implementazione efficiente dell’algoritmo di Dijkstra.

6/5/2021

 Problema di cammino minimo: algoritmo di Floyd-Warshall

11/5/2021

 Problema di massimo flusso: definizioni e proprietà. Teorema di Ford-Fulkerson. Algoritmo di Ford-Fulkerson per il problema di massimo flusso

13/5/2021

 Ottimizzazione su grafi: esercizi di ripasso

18/5/2021

 Formulazioni: allocazione di risorse, il problema del trasporto, il problema di taglio ottimo.

20/5/2021

 Formulazioni: esempi
25/5/2021 Dualità nella PL: definizione del problema duale teorema debole della dualità.

27/5/2021

 Teorema forte della dualità.
1/6/2021 Condizioni di ortogonalità.
3/6/2021 Analisi di sensitività nella PL. Interpretazione economica del duale.

8/6/2021

Esercizi di ripasso

10/6/2021

Esercizi di ripasso
16/6/2021

 

ESAME (SCRITTO)  o seconda prova intermedia

aule N14, N10, N11 ore 15:00

 
7/7/2021

 

ESAME (SCRITTO) o seconda prova intermedia

aule N1, N10, N11 ore pomeriggio (da confermare)

 

 

Calendario delle lezioni dal 2018/19 (Ing. Civile/Elettronica/Meccanica) in rosso sono riportate le modifiche recenti

 

Lezione #

ARGOMENTO

1

Introduzione al corso. Ripasso di Algebra, operazioni tra vettori e matrici, metodo grafico.

2

Operazione di pivot, metodo di Gauss. Metodo delle 5 fasi, esempi introduttivi. Storia della programmazione matematica.

3

Programmazione matematica, programmazione convessa, programmazione lineare (PL).

4

Geometria della PL: poliedri, vertici. Condizioni di ottimo nella PL. Forme equivalenti di un problema di PL. Soluzioni base e relazione tra vertici e soluzioni base ammissibili.

5

Metodo del Simplesso: condizioni di ottimo e cambiamento di base. Interpretazione geometrica.

6

Cambiamento di base, Aggiornamento della matrice inversa, metodo rivisto. Fase 1, passaggio dalla fase 1 alla fase 2 nel metodo rivisto. Convergenza e degenerazione nell’algoritmo del simplesso.  Regola di Bland.

7

Formulazione e soluzione di tipici problemi di PL: problema di miscelazione, allocazione di risorse, gestione delle scorte. I Solutori esistenti.

8

Problema di assegnazione, problema di trasporti, pianificazione di attività. Problema di taglio ottimo.

9

Dualità nella PL: teorema debole e teorema forte

10

Teorema fondamentale della PL, condizioni di ortogonalità. Analisi di sensibilità.

11

Interpretazione economica del duale.

12

Cenni di Programmazione lineare a numeri interi.

13

Esercizi di ripasso

14

Prima prova intermedia.

15

Programmazione non lineare. Gradiente, matrice Hessiana. Formulazioni. Serie di Taylor, condizioni necessarie di minimo locale del primo ordine, condizioni necessarie e sufficienti di minimo globale per funzioni convesse.

16

matrici definite e semidefinite positive, condizioni necessarie e condizioni sufficienti di minimo locale del 2 ordine. Algoritmi di programmazione non lineare, metodo di discesa.

17

Esistenza minimo globale. Metodo del gradiente,  Line search esatta. Convergenza globale e locale. Metodo del gradiente con  backtracking: Armijo

18

Rapidità di convergenza. Metodo del gradiente con  Interpolazione. Metodo di Newton, Newton modificato.

19

Metodo del gradiente coniugato.

20

Cenni sui metodi di soluzione di problemi di ottimizzazione non lineare vincolata

21

Esercitazione.

22

Metodo del gradiente per una funzione non ovunque differenziabile.

23

Ottimizzazione non lineare vincolata. La funzione Lagrangiana. Condizioni KKT.

24

Esercizi di ripasso

25

Esercizi di ripasso

26

Esercizi di ripasso

27

Seconda prova intermedia

 

ESAME (SCRITTO)

 

ESAME (ORALE)