Ricerca Operativa (Informatica, Matematica)
Ricerca Operativa (Informatica, Matematica)
(Prof. Claudio Arbib)
Materiale Didattico Integrativo
Temi di Esame ed Esercizi Proposti
Orario
Martedí dalle ore 15:00 alle ore 17:00, Aula Magna
Mercoledí dalle ore 15:00 alle ore 17:00, Aula Magna
Giovedí dalle ore 11:30 alle ore 13:30, Aula Magna
Lezioni
XI settimana
Martedì 18 Marzo 2003
Pianificazione della produzione di un impianto. Formulazione generale ed esempi. Metodo del simplesso: determinazione di una base ammissibile tramite problema ausiliario.
X settimana
Martedì 11 Marzo 2003
Problemi di PL in forma standard. Trasformazione in forma standard. Teorema di dualità forte: condizione necessaria.
Mercoledì 12 Marzo 2003
Teorema di dualità forte: condizione sufficiente. Problema duale e problema primale. Esempio. Costruzione del duale di un problema di PL.
Giovedì 13 Marzo 2003 (mattina)
Teorema di dualità debole. Corollari ed esempi. Problemi in forma standard: basi e soluzioni (ammissibili) di base.Giovedì 13 Marzo 2003 (pomeriggio)
Metodo del Simplesso. Criterio di ottimalità della base corrente. Forma canonica e operazione di pivot. Miglioramento della base corrente. Criterio di illimitatezza. Esempi.
IX settimana
Mercoledì 05 Marzo 2003
Applicazione del Metodo di Fourier-Motzkin alla risoluzione di un problema di programmazione lineare.
Giovedì 06 Marzo 2003
Teoremi dell'alternativa: Teorema di Gale, Lemma di Farkas. Esercitazione: un problema di palinsesto televisivo.
VIII settimana
Martedì 25 Febbraio 2003
Problema: decidere se un poliedro è vuoto oppure no. Proiezione di un poliedro. Teorema di Fourier-Motzkin (enunciato).Mercoledì 26 Febbraio 2003
Teorema di Fourier-Motzkin (dimostrazione). Esempi.Giovedì 27 Febbraio 2003
Metodo di Fourier-Motzkin. Esercitazione. Forma algebrica dell'involucro convesso di un insieme finito di punti.
VII settimana
Martedì 18 Febbraio 2003
Esercitazione: risoluzione e discussione dei problemi proposti alla prova d'esonero, prima parteMercoledì 19 Febbraio 2003
Esercitazione: risoluzione e discussione dei problemi proposti alla prova d'esonero, seconda parteGiovedì 20 Febbraio 2003
Problemi multicriterio. Ottimizzazione secondo Pareto: soluzioni dominate e non dominate. Curve di regressione: calcolo della retta di regressione tramite programmazione lineare. Esercitazione: uso di un foglio di calcolo per la formulazione e risoluzione di un problema di programmazione lineare
VI settimana
Mercoledì 12 Febbraio 2003
Prima prova di esonero
V settimana
Martedì 04 Febbraio 2003
Spazi vettoriali a dimensione finita, combinazione lineare, dipendenza e indipendenza lineare.Combinazione conica, convessa e affine. Involucro convesso di un insieme di punti. Poliedri.Mercoledì 05 Febbraio 2003
Teorema di Steinitz. Un problema di programmazione lineare: la dieta ottima.Giovedì 06 Febbraio 2003
Esercitazione: sistemi di indipendenza e matroidi, formulazione di problemi di ottimizzazione combinatoria, combinazione lineare, affine, conica e convessa
IV settimana
Martedì 28 Gennaio 2003
Formulazione analitica di problemi di ottimizzazione combinatoria: knapsack, insieme stabile, clique, edge cover.Mercoledì 29 Gennaio 2003
Teorema di Rado: condizione sufficiente.Giovedì 30 Gennaio 2003
Teorema di Rado: condizione necessaria. Esempi di matroide: matroide grafico, matroide partizione.
III settimana
Martedì 21 Gennaio 2003
Algoritmo greedy: pseudocodifica incrementale ed esempi.Mercoledì 22 Gennaio 2003
Proprietà di subclusione, sistemi di indipendenza, esempi. Applicazione del metodo greedy a problemi subclusivi e non. Proprietà di scambio, matroidi. Una condizione sufficiente perché un sistema di indipendenza non sia un matroide. Esempi di matroidi.
II settimana
Martedì 14 Gennaio 2003
Colorazione dei vertici di un grafo. Grafi planari, contraibilità e Teorema di Kuratowski (enunciato). Grafi bipartiti e loro colorazione. Esercizio: verifica di planarità di un grafo hamiltoniano.Mercoledì 15 Gennaio 2003
Caratterizzazione dei grafi bipartiti. Alberi, arborescenze e foreste. Numero di clique e di stabilità. Problemi combinatorici, alcuni esempi: abbinamento, edge-cover, abbinamento perfetto.Giovedì 16 Gennaio 2003
Problemi di ottimizzazione combinatoria: definizione ed esempi. Algoritmo universale. Complessità dell'algoritmo universale.
I settimana
Martedì 07 Gennaio 2003
Introduzione al corso: origini della Ricerca Operativa, esempi di applicazioni militari e civili, date fondamentali, ruolo della Ricerca Operativa nel panorama scientifico e tecnologico odierno, riferimenti.Mercoledì 08 Gennaio 2003
Elementi di teoria dei grafi: definizioni fondamentali; grafo complementare, completo e vuoto; grado e Teorema del grado; Teorema di Ramsey per grafi finiti (enunciato); isomorfismo; esempi.Giovedì 09 Gennaio 2003
Elementi di teoria dei grafi: sottografi di un grafo dato; alcuni grafi notevoli; connessione debole e forte: esempi.
Orario di Ricevimento
Martedì dalle ore 17.00 alle ore 18.00
Mercoledì dalle ore 17.00 alle ore 18.00
Appelli
sessione di recupero 2003
17 dicembre 2003 ore 10:30 aula 2.4
Programma
Testi di Riferimento
A. Sassano, Modelli e Algoritmi della Ricerca Operativa, Franco Angeli Ed.(1999)
A. Agnetis, C. Arbib, M. Lucertini, S. Nicoloso, Il Processo Decisionale, Nuova Italia Scientifica (1992)
C.H. Papadimitriou, K.E. Steiglitz, Combinatorial optimization: algorithms and complexity, Dover Publications (1999), cap. 12 "Spanning Trees and Matroids"
Materiale Didattico Integrativo
Un problema di palinsesto televisivo*, presentazione
Soluzione del problema di palinsesto televisivo*, presentazione
Teoria della Dualità*, presentazione
Combinatoria*, presentazione
Esercitazioni*, presentazione
Branch-and-Bound*, presentazione
Metodo di Fourier Motzkin *, presentazione
Problemi combinatorici ed Esempi*, presentazione
Il problema della dieta*, formato .xls
Il metodo di Fourier Motzkin*, presentazione
Esempio sul metodo di Fourier Motzkin*, presentazione
L'auto ideale*, presentazione
Il metodo del Simplesso*, presentazione
Poliedri*, presentazione
Branch&Bound, Stabile, Zaino *, slide delle lezioni del 6 e 12 marzo 2002
Appunti delle lezioni, dispense in distribuzione.
* i file sono in formato .pps (presentazione Microsoft PowerPoint) e compressi con WinZip
Temi di Esame ed Esercizi Proposti
04 febbraio 2002
18 settembre 2001
26 giugno 2001
21 febbraio 2001
05 febbraio 2001
16 gennaio 2001
22 giugno 2000
01 giugno 2000
24 febbraio 2000
20 gennaio 2000
15 settembre 1999
12 luglio 1999
04 giugno 1999
18 febbraio 1999
27 gennaio 1999
16 settembre 1998
21 luglio 1998
30 giugno 19998
02 giugno 1998
25 febbraio 1998
Risposte prova scritta intermedia del 12 febbraio 2003 GRUPPO A
Risposte prova scritta intermedia del 12 febbraio 2003 GRUPPO B
Risposte prova scritta intermedia del 12 febbraio 2003 GRUPPO C
Risposte prova scritta intermedia del 12 febbraio 2003 GRUPPO D
Risposte prova scritta finale del 25 Marzo 2003 GRUPPO A
Risposte prova scritta finale del 25 Marzo 2003 GRUPPO B
Risposte prova scritta finale del 25 Marzo 2003 GRUPPO C
Risposte prova scritta finale del 25 Marzo 2003 GRUPPO D
Risposte prova scritta finale del 22 Luglio 2003 GRUPPO A
Risposte prova scritta finale del 22 Luglio 2003 GRUPPO B
Risposte prova scritta finale del 22 Luglio 2003 GRUPPO C
Risposte prova scritta finale del 22 Luglio 2003 GRUPPO D
Risultati prova scritta finale del 22 Luglio 2003
Bacheca
Avviso 14
L'appello della sessione di recupero 2003 si terrà il 17 dicembre 2003 ore 10:30 aula 2.4
Avviso 13
L'esame orale di Ricerca Operativa si terrà il giorno Martedì 30 Settembre ore 15.00 in aula da definire. Gli esiti dell'esame scritto saranno pubblicati nella mattinata dello stesso giorno
Avviso 12
L'esame orale di Ricerca Operativa si terrà nel giorno Giovedì 24 Luglio alle ore 10.30 presso lo studio del Prof. Claudio Arbib
Avviso 11
Coloro che hanno riportato una votazione insufficiente nella prova scritta dell'esame di Ricerca Operativa potranno prendere visione del compito nell'orario di ricevimento del Prof. Claudio Arbib (a partire dalla settimana successiva alle vacanze di Pasqua)
Avviso 10
L'esame orale di Ricerca Operativa si terrà nei giorni Martedì 15 Aprile e Mercoledì 16 Aprile secondo la seguente suddivisione (aggiornata in seguito alla pubblicazione dei risultati finali della prova scritta):
Martedì 15 Aprile, Ore:10.00, Aula C 3.5 (in ordine alfabetico) da Angelone Francesco a Del Matto Massimiliano;
Martedì 15 Aprile, Ore:16.00, Aula C 2.4 (in ordine alfabetico) da Di Bastiano Enrica a Giordano Luca;
Mercoledì 16 Aprile, Ore 10.00 (in ordine alfabetico) da Gregorj Alessio a Pellicciotta Elena;
Mercoledì 16 Aprile, Ore 15.00 (in ordine alfabetico) da Pescatore Eduardo a Villani Federico
Avviso 9
I risultati della seconda prova di esonero di Ricerca Operativa saranno resi pubblici dopo l'8 aprile 2003.
Avviso 8
Sono disponibili le soluzioni delle prove scritte di ricerca operativa (vedi sezione "Temi d'esame ed esercizi proposti"). Il colloquio si terrà in data da destinarsi, comunque non prima del 1 aprile 2003.
Avviso 7
La seconda prova scritta di Ricerca Operativa si terrà il 25 marzo 2003 alle ore 10.00 in aule da definire.
Avviso 6
A seguito dell'attacco americano in Iraq, la lezione straordinaria di Ricerca Operativa ed il ricevimento studenti del giorno giovedì 20 marzo sono annullati.
Avviso 5
Il docente terrrà un'ulteriore esercitazione facoltativa giovedì 20 marzo. La lezione non avrà tuttavia luogo in caso di invasione dell'Iraq da parte americana, come forma di protesta.
Avviso 4
Una lezione integrativa a scopo di esercitazione (facoltativa) verrà tenuta in Aula Magna martedì 18 marzo dalle ore 9.30 alle 11.30. Su richiesta di un numero sufficiente di studenti, il docente è disponibile per ulteriori lezioni ed esercitazioni.Avviso 3
NON E' UNO SCHERZO! Martedì 4 marzo 2003 (martedì grasso) non si va a lezione. Buon carnevale.Avviso 2
Le dispense elettroniche di ottimizzazione combinatoria sono in fase di revisione. L'uscita della nuova versione sarà tempestivamente segnalata con avviso in bacheca.
Avviso 1
Giovedì 23 gennaio 2003 la lezione di Ricerca Operativa sarà sostituita da Interfacce Uomo Macchina. Le lezioni di Ricerca Operativa riprenderanno regolarmente martedì 28 gennaio.