Ricerca Operativa I

Docente

Dario Pacciarelli


Orari

Lezioni ed Esercitazioni Ing. Informatica

vedi orario ufficiale sul sito del Collegio Didattico in Ingegneria Informatica o del Dipartimento di Ingegneria

Lezioni ed Esercitazioni Ing. Civile/Elettronica

Vedi sito del Collegio Didattico di Ingegneria Civile o Collegio Didattico di Ingegneria Elettronica o del Dipartimento di Ingegneria Meccanica

Ricevimento

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


Esami & Esoneri

Calendario degli esami
Ing. Informatica

Vedi calendario ufficiale del Collegio Didattico in Ingegneria Informatica

Ing. Civile/Elettronica/Meccanica

Vedi calendario ufficiale del Collegio Didattico di Ingegneria Civile o Collegio Didattico di Ingegneria Elettronica o Collegio Didattico di Ingegneria Meccanica

Modalità di Esame: L'esame consiste in una prova scritta e una prova orale, secondo il calendario indicato.  


Comunicazioni

 

 

 

Sulla pagina Moodle3 del corso trovate i risultati della prova scritta di settembre, limitatamente agli studenti che hanno espresso come preferenza per l'orale il 18 settembre.  

Gli studenti ammessi all'orale dovranno sostenere la prova orale il 18 settembre, ore 9:00 aula N14.

Gli studenti non ammessi all'orale potranno consultare il compito esclusivamente il 18/9 al termine delle prove orali.

 

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.

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

 

 

Programma Ing. Informatica (dall'A.A. 2013-14)

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. Il simplesso su reti  (cap 13)

Flusso di costo minimo
Basi e alberi ricoprenti

cambiamento di base
fase 1 e fase 2

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

Massimo flusso
Cammino minimo
Albero ricoprente

 

 

Programma Ing. Civile/Elettronica/Meccanica (dall'A.A. 2014-15)

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 2016/17 (Ing. Informatica) in rosso sono riportate le modifiche recenti

DATA

ARGOMENTO

3/3/2017

Introduzione al corso.

7/3/2017

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

10/3/2017

Geometria poliedrale: poliedri, vertici e direzioni. Teorema di Weyl-Minkowski. Soluzione di un problema di PL: il metodo grafico. Esempi.

14/3/2017

Soluzione di un problema di PL: metodo di Fourier-Motzkin. Condizioni geometriche di ottimalità e illimitatezza nella PL.

15/3/2017

ore 14-18

Recupero

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

Forme equivalenti di un problema di PL.

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

17/3/2017

Condizioni algebriche di ottimalità. Interpretazione geometrica del cambiamento di base.

21/3/2017

Condizioni algebriche di illimitatezza nella PL. Metodo del Simplesso, Fase 2.

24/3/2017

lezione cancellata (Codemotion)

28/3/2017

Algoritmo del simplesso: Aggiornamento della matrice inversa, metodo rivisto.

29/3/2017

ore 14-18

Recupero

Algoritmo del simplesso: Fase 1 e fase 2. Il problema artificiale. Passaggio dalla fase 1 alla fase 2 nel metodo rivisto.

Formulazioni: Allocazione di risorse, miscelazione.

31/3/2017

Convergenza e degenerazione nell’algoritmo del simplesso. Regola di Bland. 

4/4/2017

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

7/4/2017 Albero ricoprente di peso minimo: algoritmo di Prim-Dijkstra

11/4/2017

Esercizi di ripasso.

21/04/2017

PRIMA PROVA INTERMEDIA 

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

28/4/2017

Dualità nella PL: definizione del problema duale teorema debole della dualità.

2/5/2017

lezione cancellata

5/5/2017

Teorema forte della dualità.

9/5/2017

Condizioni di ortogonalità.

10/5/2017

ore 14-18

Recupero

Analisi di sensitività nella PL. Interpretazione economica del duale.

Formulazioni: problema del trasporto, problema di taglio ottimo.

12/5/2017

Problema di flusso di costo minimo. Il simplesso su reti: equivalente su rete di una base.

16/5/2017

Il simplesso su reti: fase 2.

19/5/2017

Simplesso su reti, fase 1 e passaggio alla fase 2. Esercitazione sul problema di flusso di costo minimo

23/5/2017

Formulazioni su grafi/reti: flusso di costo minimo, massimo flusso, percorso minimo

26/5/2017

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

30/5/2017

Problema di cammino minimo: algoritmo di Floyd-Warshall

2/6/2017

Festa della Repubblica

6/6/2017

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

9/6/2017

lezione cancellata

13/6/2017

Esercizi di ripasso

20/6/2017

ESAME (SCRITTO)  + seconda prova intermedia

aule N1, N10, N11 ore 9:00

23/6/2017

ESAME (ORALE) e verbalizzazione

aula N14 ore 9:00

 

13/7/2017

ESAME (ORALE) e verbalizzazione

aula N14 ore 14:00

 

 

Calendario delle lezioni 2013/14 (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)