Calendario degli appelli d'esame per
l'a.a. 2009/10
|
FRO Prima Prova in Itinere lun. 16/11/09 |
|
|
FRO Seconda Prova in Itinere lun. 18/01/10 aula G12
ore 13.30 |
|
|
FRO I Appello mar. 26/01/10 |
|
|
FRO II Appello mar. 16/02/10 |
|
|
FRO III Appello mar. 15/06/10 |
|
|
FRO IV Appello mar. 27/07/10 |
|
|
FRO V Appello mar. 21/09/10 |
|
AVVISI
Orario
del corso Fondamenti di Ricerca Operativa
(FRO):
lunedì
13,30-15,30 aula G12 Via Golgi 19
martedì
16,30-18,30 aula G12 Via Golgi 19
Orario
del corso Complementi di Ricerca
Operativa (CRO):
lunedì
13,30-15,30 auletta 6 Via Comelico 39
giovedì
10,30-12,30 auletta 6 o aula Delta Via
Comelico 39
------------------------------------------------------------------------------------------------------
Gli studenti che hanno superato l'esame di FRO con le prove in itinere, per poter verbalizzare il voto devono comunque iscriversi ad un appello regolare.
Regole per la determinazione del voto di FRO.
Con una votazione nei compitini o in una prova scritta:
- compresa fra 18 e 26 (estremi inclusi) l'esame orale è facoltativo
- superiore a 26, senza sostenere la prova orale, il voto verbalizzato è 26
Programma dei corsi per l'a.a. 2009/10 e sommario
degli argomenti trattati
|
Fondamenti di Ricerca Operativa |
||
|
Ore di didattica: 48 |
Crediti: 6 |
Semestre: 1° |
|
Modalita’ d’esame: scritto, prova orale |
||
Obiettivi
del corso:
Il corso si propone di introdurre i fondamenti della programmazione matematica e le relative tecniche algoritmiche, con particolare attenzione ai modelli di programmazione lineare, a quelli di programmazione lineare intera e a quelli ottimizzazione su grafo. Esempi illustrano i numerosi ambiti di applicazione delle tecniche descritte.
1.
Introduzione
Programmazione matematica. Formulazione matematica di problemi di ottimizzazione: modelli di programmazione lineare (PL) e lineare intera (PLI).
2.
Programmazione Lineare
Programmazione Lineare : geometria della PL e soluzione grafica. Algoritmo del Simplesso in forma base e Tableau. Metodo delle due Fasi. Dualità in PL. Problema duale. Relazioni primale-duale. Proprietà fondamentali. Condizioni di ottimalità. Simplesso duale. Analisi di sensitività.
3.
Programmazione Lineare a Numeri Interi
Matrici unimodulari. Piani di taglio, Tagli di Gomory. Metodo "Branch and Bound". Tecniche per il calcolo dei bounds. Esempi di algoritmi Branch and Bound.
4.
Elementi Di Teoria Dei Grafi
Definizioni. Algoritmi per il calcolo dell’albero di supporto di costo minimo. Algoritmi per il calcolo di cammini minimi. Il problema del flusso massimo: Algoritmo di Ford-Fulkerson. Il problema del flusso massimo a costo minimo. Cenni alla teoria della complessità computazionale.
Bibliografia
di riferimento:
M. Fischetti: Lezioni di Ricerca Operativa, Edizioni Libreria Progetto Padova.
Bibliografia
consigliata:
M. Dell’Amico: 120 esercizi di ricerca operativa, Pitagora Editrice Bologna.
Bibliografia
per approfondimenti:
L.A. Wolsey: IntegerProgramming, Wiley, 1998.
C.H. Papadimitriou, K. Steiglitz: Combinatorial
Optimization: Alghorithms and Complexity, Prentice Hall, 1982.
R.K. Ahuja, T.L. Magnanti, J.B.
Orlin: Network Flows, Prentice Hall, 1993.
Prerequisiti:
Elementi di algebra delle matrici.
Materiale
integrativo
Programma dettagliato
Programmazione lineare. Introduzione ed esempi di modelli di Programmazione matematica. Definizioni di "insieme convesso" e "funzione convessa". Definizione di "ottimizzazione convessa". Proprietà Minimo locale=minimo globale (con dimostrazione). Disegno della regione ammissibile in R2. Soluzione geometrica di un problema di PL in due variabili. Trasformazione di un modello generico in modello in Forma Standard. Definizione di iperpiano, semispazio, poliedro, politopo e vertice. Teorema Minkowski-Weyl ristretto ai politopi (enunciato). Teorema Esistenza ottimo finito => esistenza vertice ottimo (con dimostrazione). Dalla geometria all’algebra: definizioni di: base, soluzione di base, soluzione di base ammissibile. Teorema x soluzione di base ammissibile se e solo se x vertice (con dimostrazione). Corollario Esistenza ottimo finito => esistenza soluzione di base ottima. Definizione di forma canonica rispetto ad una base. Stima del numero delle soluzioni di base. Teorema Condizioni di ottimalità di una base (con dimostrazione). Schema dell’algoritmo del simplesso. Individuazione di una variabile entrante e di quella uscente. Il cambio di base o operazione di pivot. Condizioni di illimitatezza. Forma Tableau dell'algoritmo del simplesso. Determinazione di una soluzione iniziale: metodo due fasi. Analisi di sensitività per via geometrica. Modifica di un termine noto. Modifica di un coefficiente di costo. Analisi di sensitività per via algebrica. Simplesso: convergenza e degenerazione: regola di Bland.
Dualità
nella PL. Introduzione. Lemma di Farkas (con dimostrazione). Relazioni
primali duali. Teorema di dualità debole (con dimostrazione). Teorema di
dualità forte. Teorema sulle condizioni di scarto complementare (con
dimostrazione). Rivisitazione del tableau in forma canonica (il simplesso primale mantiene l’ammissibilità
primale, le condizioni di scarto complementare e cerca l’ammissibilità duale).
Interpretazione economica della dualità: variabili duali e prezzi ombra. Regola
per determinare il verso di vincoli e variabili usando la nozione di prezzo
ombra. Introduzione alla
Programmazione Lineare Intera. Definizione di conv(S). Definizione di rilassamento continuo. Definizioni di matrice Unimodulare (UM) e Matrice Totalmente Unimodulare (TUM). Esempio: i modelli dei problemi di Assegnamento e Trasporto. Altre proprietà delle matrici TUM. Il metodo dei Piani di Taglio. I tagli di Chvatal. La chiusura di Chvatal. Il rango di Chvatal. I tagli di Gomory. Il metodo del simplesso duale. Introduzione al metodo del Branch & Bound. La fase di branching. Tecniche di "bounding": rilassamento continuo. Esempio numerico: un problema di PLI in due dimensioni. Tecniche di "bounding": rilassamento per eliminazione di vincoli, rilassamento lagrangiano, rilassamento surrogato. Esempi. Relazione fra rilassamento continuo e rilassamento lagrangiano: la proprietà di integralità. Esplorazione dell’albero di branching: a priorità di profondità (depth first), in base al valore dei bound (best bound first). Esempio numerico: un problema di “zaino”.
Ottimizzazione
su grafo. Problema dell’albero di
supporto di costo minimo (Minimum Spanning Tree). Modello di PLI per l’MST.
Teorema che caratterizza i lati appartenenti ad alberi di costo minimo.
Algoritmo di Prim-Dijkstra: versione O(n2). Esempio numerico.
L’algoritmo di Kruskal per l’MST. Il
problema dei cammini minimi su grafo orientato. Formulazione matematica.
Teorema che caratterizza gli archi appartenenti a cammini di costo minimo.
Algoritmo di Dijkstra. Esempio. Algoritmo O(n3)
di Flyd-Warshall. Il problema del flusso massimo in una rete. Formulazione
matematica. Algoritmo di Ford-Fulkerson. Esempio. Il problema di flusso a costo
minimo. Formulazione matematica. Algoritmo dei cicli di lunghezza negativa.
Esempio. Nozioni di
Complessità Computazionale. Richiami informali a: problemi di decisione, istanza, dimensione di un’istanza, modello di calcolo (macchina di Turing deterministica), modello di costo uniforme, complessità di un algoritmo nel caso peggiore. Definizione della classe di problemi P. La macchina di Turing Non-deterministica. Definizione della classe di problemi NP. Il concetto di certificato polinomiale. Altra definizione della classe NP. Nozione di riduzione polinomiale. Definizione della classe NP-c: i problemi NP completi. SAT come prototipo dei problemi NP-completi. Un esempio di riduzione.
Appelli
di Fondamenti di Ricerca Operativa
|
Appelli |
Testi |
Esiti |
|
Prima prova in itinere |
||
|
Seconda prova in itinere |
||
|
Primo appello 26/01/10 |
||
|
Secondo appello 16/02/10 |
||
|
Terzo appello 15/06/10 |
||
|
Quarto appello 27/07/10 |
||
|
Quinto appello 21/09/10 |
||
|
Sesto appello 12/01/11 |
Testi
di precedenti appelli di Fondamenti di Ricerca Operativa e di Ricerca Operativa
Argomenti trattati
Argomenti parte numerica: Risoluzione grafica, analisi di sensitività per via grafica, e per via algebrica. Simplesso primale I e II fase, formulazione modello duale, applicazione teorema scarti complementari.
Argomenti parte modellistica: tutti i modelli descritti nel documento ModPLePLI.
Argomenti parte
teorica Definizioni: insieme convesso, funzione
convessa, iperpiano, semispazio, poliedro, politopo, vertice, base, soluzione di base, soluzione
di base ammissibile, forma canonica
rispetto ad una base, prezzo ombra. Condizioni di ottimalità, di illimitatezza,
Teoremi Esistenza ottimo finito
=> esistenza vertice ottimo, Dualità
debole, Dualità forte, Condizioni di scarto complementare, Relazione soluzioni
di base ammissibili e vertici (solo enunciato), Lemma di Farkas (solo enunciato). Analisi
di sensitività per via algebrica.
Aula G12. Martedì 22/12/09,
16,30-18,30. Sospensione per nevicata.
Aula G12. Lunedì
18/01/10, 13,30-14,30. Seconda prova in itinere.
Argomenti parte numerica: Metodo dei tagli di Gomory e simplesso duale. Metodo di Branch and Bound per problemi di PLI e per problema di zaino. Costruire il rilassamento lagrangiano o surrogato di un modello di PLI. Ottimizzazione su grafo: algoritmi di Prim-Dijkstra, Kruskal, Dijkstra, Ford-Fulkerson, e per flusso a costo minimo.
Argomenti parte modellistica: modelli per problemi di ottimizzazione su grafo: albero di supporto di costo minimo, cammini minimi, flusso massimo e flusso massimo a costo minimo. Modello del commesso viaggiatore (TSP).
Argomenti parte
teorica Definizioni: conv(S),
matrici UM e TUM, taglio valido, taglio di Gomory. Rilassamento lagrangiano e
surrogato. Definizioni legate ai grafi: albero, cammino, flusso, taglio. Teoremi: Condizioni sufficienti
affinché una matrice sia TUM, validità dei tagli di Gomory. Correttezza
algoritmi di Prim-Dijkstra e Dijkstra. Proprietà per la quale il valore del
flusso in una rete è pari al lusso che attraversa un qualunque Taglio s-t della stessa.
La correttezza dell’algoritmo di Ford-Fulkerson e le
principali definizioni legate alle classi di complessità vengono richieste per
la sola prova orale.
|
Complementi di Ricerca Operativa |
||
|
Ore di didattica: 48 |
Crediti: 6 |
Semestre: 2° |
|
Modalità d’esame: progetto (per i frequentanti), prova orale |
||
Obiettivi
del corso:
Il corso si propone di ampliare i fondamenti della programmazione matematica introdotti nel corso di Fondamenti di Ricerca Operativa. In primo luogo vengono introdotte le principali tecniche disponibili per affrontare modelli di programmazione non lineare.
Vengono successivamente illustrate tecniche avanzate per la soluzione di problemi di programmazione lineare di grandi dimensioni: tecniche di decomposizione e tecniche di generazione di colonne (column generation). Vengono illustrati esempi di applicazione del metodo dei piani di taglio (cutting plane) e vengono descritti gli algoritmi esatti basati su tali tecniche: Branch & Price e Branch & Cut. Viene descritta e illustrata con esempi la principale tecnica per il calcolo dei valori ottimi dei moltiplicatori duali Lagrangiani (tecnica del sottogradiente).
Le tecniche introdotte vengono applicate con lezioni in laboratorio informatico dove, dopo aver appreso il linguaggio di modellazione AMPL, lo stesso linguaggio viene utilizzato per implementare la tecnica del sottogradiente e per risolvere problemi (di localizzazione, di taglio di pannelli, di decomposizione matriciale, zaino multidimensionale, ecc.) mediante le tecniche di column generation, cutting plane.
Bibliografia
di riferimento:
Dispense del docente: OttNonLineare
Bibliografia
per approfondimenti:
J. Nocedal, S.J. Wright. Numerical Optimization. Seconda Edizione. Ed. Springer, 2006.
Francesco
Maffioli. Elementi di Programmazione
matematica. Volume
secondo. Ed. Masson, 1991.
Jan A. Snyman. Practical Mathematical Optimization. Ed. Springer, 2005.
Materiale integrativo:
Linguaggio
Ampl: LabAMP01,
Esercizi, Esempi, Un articolo introduttivo
alla tecnica di column generation: primer.pdf.
Il materiale ampl per l’SSTDMA: sstdma. File
Ampl per cover inequalities MKP01.zip. Lavori
legati alle tecniche poliedrali con particolare enfasi all’approfondimento del
problema TSP: Articoli_di_Poliedrale. Proposte di progetti d’esame: Proposte.pdf .
Prerequisiti:
E' fortemente consigliato aver seguito il corso di Fondamenti di Ricerca Operativa.
Programma
dettagliato
Programmazione Non Lineare (PNL). Introduzione ed esempi. PLI come caso particolare di PNL. Definizioni di "insieme convesso", "funzione convessa", "ottimizzazione convessa". Proprietà di insiemi e funzione convesse. Definizione di “minimo globale”, “minimo locale”. Esempio di funzione con molti minimi locali.
Ottimizzazione non vincolata. Definizione di “funzione di classe Ck ”. Lo sviluppo in serie di Taylor in Rn, arrestato al secondo ordine.Definizione di "direzione di discesa", “derivata direzionale”. Legame fra vettore gradiente e derivata direzionale. Legame fra direzione di discesa e derivata direzionale. Condizioni necessarie di ottimalità del I° e del II° ordine. Condizioni sufficienti di ottimalità del II° ordine. Definizione di (semi)definita positività di una matrice, proprietà per determinare se una matrice è (semi)definita positiva. Convessità e gradiente, convessità e matrice hessiana. Condizioni di ottimalità per funzioni convesse. Condizioni empiriche di ottimalità. Programmazione quadratica. Q definita positiva, Q indefinita, Q semidefinita positiva. Esempi. Convergenza locale e convergenza globale. Rapidità di convergenza. Convergenza lineare, superlineare, quadratica. Introduzione ai metodi iterativi basati su ricerca lineare. Determinazione del passo alpha. Condizione di sufficiente riduzione della funzione f(x). Determinazione del passo alpha. Condizione di curvatura (Wolfe). Condizione di Wolfe in senso forte. Backtracking e metodo di Armijo. Proprietà di terminazione del metodo di Armijo. Metodo di ricerca esatto: interpretazione geometrica e caso di funzioni quadratiche. Metodo di interpolazione: funzione approssimante quadratica e cubica. Inizializzazione di alpha_0. Scelta della direzione. Condizione d’angolo. Proprietà: gli algoritmi iterativi che soddisfano alle condizioni di Wolfe ed alla condizione d’angolo (su funzioni limitate e a gradiente Lipschitziano) convergono globalmente. Metodo del gradiente. Proprietà: l’algoritmo del gradiente su funzioni quadratiche ha tasso di convergenza lineare. Proprietà: tasso di convergenza dell’algoritmo del gradiente su funzioni qualsiasi. Metodo di Newton. Proprietà: l’algoritmo di Newton su funzioni con hessiano Lipschitziano ha tasso di convergenza quadratico. Metodo di Newton modificato. Metodi quasi Newton. Metodi quasi-Newton. Formula di aggiornamento di rango 1. Formula di aggiornamento di rango 2 (DFP). Formula di aggiornamento di rango 2 inversa (BFGS). Famiglia di Broyden. Metodi alle direzioni coniugate. Metodo di gradiente coniugato. Formule di Fletcher-Reeves e formule di Polak-Ribiére. Metodo di Trust-Region. Introduzione alla tecnica. Il modello quadratico vincolato. Pseudo codice. Condizioni analitiche di ottimalità del modello quadratico vincolato. Il punto di Cauchy e la sua determinazione. Il metodo Dogleg. Problemi ai Minimi Quadrati. Introduzione. Il metodo di Gauss-Newton. Il metodo di Levenberg-Marquardt.
Ottimizzazione Vincolata. Introduzione. Esempi. Condizioni analitiche: soli vincoli di uguaglianza. Condizioni necessarie di Lagrange. Interpretazione geometrica delle condizioni di Lagrange. Condizioni di Qualificazione dei Vincoli. Punto Regolare. Funzione quadratica e vincoli di uguaglianza lineari. Da vincoli di disuguaglianza a vincoli di uguaglianza. Caso generale e condizioni KKT. Interpretazione geometrica delle condizioni KKT. Definizione di Cono delle direzioni critiche e condizioni necessarie del secondo ordine. Tecnica delle funzioni di penalità e metodi di barriera. Introduzione alle tecniche di Ottimizzazione Globale. Metodo del gradiente proiettivo per funzione qualsiasi e vincoli di uguaglianza. Cenni al metodo dei lagrangiani aumentati e al Sequential Quadratic Programmino (SQP).
Rilassamento
lagrangiano. Proprietà. Concavità e non differenziabilità della
funzione obiettivo duale. Definizione di sottogradiente, proprietà. Esistenza
del sottogradiente per funzioni concave. Il sottogradiente come direzione di
avvicinamento a l*.
Introduzione alla tecnica del sottogradiente. La
tecnica di sottogradiente applicata al TSP: l’esempio di Held e Karp (1971).
Column generation.
Introduzione. Applicazione della tecnica di column
generation al problema Cutting Stock.
Cutting Planes.
Introduzione al metodo dei piani di taglio e alla tecnica di Branch & Cut.
Esempio problema di knapsack: le Cover
inequalities con l’oracolo di separazione. Esempio del TSP: risoluzione del
problema di separazione per l’individuazione di vincoli di eliminazione di
sottocicli violati mediante la soluzione di un problema di Max Flow-Min Cut su
un grafo opportuno.
Laboratorio. Introduzione al linguaggio Ampl. Esempi. Script .run: esempio di generazione dinamica dei vincoli applicato al TSP, esempi di ottimizzazione globale. Esempio di tecnica di sottogradiente. Esempio di tecnica di sottogradiente per la determinazione del rilassamento lagrangiano ottimo di un problema di trasporto e localizzazione e per un problema di tipo BinPacking. La tecnica del sottogradiente modificato. Esempi: il Cutting Stock e la risoluzione del problema di pricing per l’individuazione di una colonna con coefficiente di costo ridotto negativo mediante la soluzione di un problema di Knapsack Intero. Il problema SSTDMA. Script .run: applicazione della tecnica di column generation. Esempio del problema di knapsack e di knapsack multidimensionale: le Cover inequalities con l’oracolo di separazione in ampl. Esempio del problema di SSTDMA. Le Cover inequalities estese e le Cover inequalities liftate. Un algoritmo euristico per “liftare” le cover inequalities. Le Comb inequalities per il TSP.
Argomenti trattati
-
Sospensione della
lezione di giovedì 8 ottobre 2009 per concomitante Career Day
Martedì
22/12/09, 13,30-15,30. Sospensione causa nevicata.