Ricerca Operativa (Informatica, Matematica)

(Prof. Claudio Arbib)

Orario

Lezioni

Orario di Ricevimento

Appelli

Programma

Testi di Riferimento

Materiale Didattico Integrativo

Temi di Esame ed Esercizi Proposti

Bacheca

Orario

Martedí dalle ore 15:00 alle ore 17:00
Mercoledí dalle ore 15:00 alle ore 17:00
Giovedí dalle ore 11:30 alle ore 13:30

Top

Lezioni

X settimana

Scarica qui il materiale integrativo di questa settimana

Martedì 23 marzo 2004
Esercitazione.

IX settimana

Martedì 16 marzo 2004
Gestione ottima di un portafoglio di titoli come gioco a somma zero. Problema max-min e formulazione come PL. Fase I del metodo del simplesso: calcolo della prima base tramite problema ausiliario. Esercitazione.

Mercoledì 17 marzo 2004 
Giochi a somma zero. Esercitazione.

Giovedì 18 marzo 2004
Esercitazione: ottimizzazione di un palinsesto televisivo. Programmazione lineare intera: rilassamento lineare, calcolo di limitazioni inferiori/superiori tramite simplesso, cenni sui metodi di branch-and-bound, esempi.

VIII settimana

Scarica qui il materiale integrativo di questa settimana

Martedì 9 marzo 2004
Il metodo del simplesso: basi e soluzioni (ammissibili) di base; problemi equivalenti; forma e tabella canonica; criteri di ottimalità e illimitatezza.

Mercoledì 10 marzo 2004
Metodo del simplesso: tabella canonica e operazione di pivot. Esempi.

Giovedì 11 marzo 2004
Metodo del simplesso: miglioramento della base corrente, esercitazione.

VII settimana

Scarica qui il materiale integrativo di questa settimana

Martedì 2 marzo 2004
Formulazione del duale di un problema di PL: esempi. Ottimizzazione di un processo di produzione. Interpretazione del problema duale. Prezzo implicito delle risorse.

Mercoledì 3 marzo 2004
Aspetti geometrici della programmazione lineare. Direzioni di un poliedro: cono di recessione e sue proprietà. Teorema di Weyl (enunciato). Esempi.

Giovedì 4 marzo 2004
Teorema fondamentale della programmazione lineare.

VI settimana

Scarica qui il materiale integrativo di questa settimana

Martedì 24 febbraio 2004
Teoremi dell'alternativa: Teorema di Gale, Lemma di Fàrkas, esempi.

Mercoledì 25 febbraio 2004
Teorema di dualità forte.

Giovedì 26 febbraio 2004
Duale di un problema di PL in forma standard. Proprietà del problema duale: reciprocità e dominanza. Condizioni di ottimalità primale e duale, ortogonalità. Costruzione del duale di un problema di PL generico.

V settimana

Scarica qui il materiale integrativo di questa settimana

Martedì 10 febbraio 2004
Semispazi chiusi, poliedri e loro rappresentazione algebrica. Sistemi di disequazioni lineari e loro soluzione. Teorema (enunciato) e metodo di Fourier-Motzkin. Esempi.

Mercoledì 11 febbraio 2004
Basi per un insieme di vettori. Teorema di rappresentazione. Teorema di sostituzione (Steinitz). Matroide vettoriale. Programmazione lineare: il problema della dieta.

Giovedì 12 febbraio 2004
Esercitazione.

Martedì 3 febbraio 2004
Vettori, scalari e operazioni elementari. Prodotto scalare, combinazione lineare, affine, conica e convessa. Chiusura rispetto alle operazioni di combinazione. Dipendenza e indipendenza lineare e affine. Esempi.

Mercoledì 4 febbraio 2004
Problemi di programmazione matematica, programmazione lineare e a numeri interi. Riformulazione di problemi di ottimizzazione combinatoria in termini di programmazione lineare 0-1. Esempi: clique, insieme stabile, node-cover, colorazione.

Giovedì 5 febbraio 2004
Problemi dell’(s, t)-cammino minimo e del commesso viaggiatore: riformulazione in termini di programmazione lineare 0-1.

III settimana

Scarica qui il materiale integrativo aggiornato di questa settimana

Martedì 27 gennaio 2004
Esempi di problemi di ottimizzazione combinatoria: zaino, edge-cover, insieme stabile, albero ricoprente, matching (perfetto). Algoritmo universale e sua complessità. Problemi subclusivi, superclusivi, né subclusivi né superclusivi: esempi. Algoritmo ingordo: pseudocodifica per problemi subclusivi e superclusivi. Ammissibilità della soluzione.

Mercoledì 28 gennaio 2004
Proprietà di scambio e sue implicazioni sulla cardinalità degli insiemi massimali. Convergenza dell'algoritmo ingordo a una soluzione ottima. Teorema di Rado (enunciato).

Giovedì 29 gennaio 2004
Dimostrazione del Teorema di Rado, matroidi. Esempi: matroide banale, matroide grafico (teorema); assegnamenti e matroide partizione.

II settimana

Martedì 20 gennaio 2004
Insieme stabile e clique. Numero di clique e numero di stabilità. Diametro di un grafo simmetrico. Colorazione di un grafo simmetrico. Numero cromatico. Grafi k-colorabili. Grafi bipartiti e loro caratterizzazione. Matching. Esempi.

Mercoledì 21 gennaio 2004
Grafi bipartiti completi. Grafi privi di cicli: alberi e foreste. Grafi d-regolari: matching e grafi cubici. Grafi intersezione: grafi intervallo e loro proprietà. Grafi cordali. Colorazione e numero di clique di un grafo intervallo.

Giovedì 22 gennaio 2004
Grafi intersezione: grafi intervallo d-dimensionali. Grafo di adiacenza (edge-graph) di un grafo simmetrico. Numero di clique e di stabilità di un grafo di adiacenza. Problemi combinatorici e di ottimizzazione combinatoria.

I settimana

Scarica qui il materiale integrativo di questa settimana

Martedì 13 gennaio 2004
Introduzione al corso. Origine della Ricerca Operativa. Riferimenti bibliografici e materiale didattico.

Mercoledì 14 gennaio 2004
Ruolo di grafi, vettori e matrici nella definizione di modelli di simulazione e ottimizzazione. Un problema di ottimizzazione: riduzione dell'area di una matrice logica programmabile. Elementi di teoria dei grafi: definizioni di base, grafi simmetrici, asimmetrici e antisimmetrci, grafo complemento, grafo completo e grafo vuoto, isomorfismo.

Giovedì 15 gennaio 2004
Elementi di teoria dei grafi: sottografi (indotti), cammini, catene e percorsi, connessione debole e forte, componenti connesse, grado, teorema del grado, numero di nodi con grado dispari in un grafo simmetrico.

 

Top

Orario di Ricevimento

Mercoledì dalle 17:00 alle 18:30

Top

Appelli

 

Top

Programma

Top

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"

Top

Materiale Didattico Integrativo

Combinatoria*, presentazione

Basi*, presentazione

Dualità*, presentazione

GeometriaPL*, presentazione

Simplesso*, presentazione

Appunti delle lezioni, dispense in distribuzione.

* i file sono in formato .pps (presentazione Microsoft PowerPoint) e compressi con WinZip

Top

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

Esercizio 1

Soluzione Esercizio 1

Esercizio 2

Soluzione Esercizio 2

Esercizio 3

Soluzione Esercizio 3

Esercizio 4

Soluzione Esercizio 4

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

Risultati prova scritta finale del 25 Marzo 2003

Top

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

Risultati prova scritta del 23 Settembre 2003

Risposte prova scritta intermedia del 19 febbraio 2004 GRUPPO A

Risposte prova scritta intermedia del 19 febbraio 2004 GRUPPO B

Risposte prova scritta intermedia del 19 febbraio 2004 GRUPPO C

Risposte prova scritta intermedia del 19 febbraio 2004 GRUPPO D

Esiti finali delle prove scritte 2003-2004

Risultati prova scritta del 31 marzo 2004 Compito A I parte

Risultati prova scritta del 31 marzo 2004 Compito A II parte

Risultati prova scritta del 31 marzo 2004 Compito B I parte  

Matricola	Giudizio
138954	insuff
140713	insuff
140454	21
146444	insuff
146591	insuff
143620	insuff
147186	19
131306	22
148800	20
151913	insuff
146496	insuff
150850	insuff
148783	insuff
146882	insuff
152540	insuff
142204	30 lode
144149	insuff
148832	insuff
139995	insuff
145381	insuff
146999	insuff
143790	insuff
147502	insuff
141081	insuff
151307	insuff
146493	20
150457	30
151737	insuff
140438	insuff
145413	insuff
144173	insuff
144797	insuff
142847	18
139459	insuff
146471	insuff
150221	insuff
147311	23
147429	insuff
144048	insuff
139000	insuff
144636	28
140584	insuff
114973	insuff
140609	23
150169	insuff
148679	23
139642	18
146493	insuff
146335	insuff
147847	insuff
146792	20
153709	27
146633	26
140900	insuff
126407	insuff
152342	insuff
149476	26
151693	18
141579	20
147172	24
150149	26
147114	insuff
143994	insuff
146767	18
150581	insuff
135448	20
146666	18
147348	20
142340	insuff
143796	24
146734	18
144311	insuff
146595	insuff
146630	30
140918	insuff
143401	insuff
139639	20
144162	insuff
152005	21
147009	19
140429	insuff
146913	insuff
147674	19
130427	21
136730	20
150199	insuff
146751	insuff
140431	insuff
146891	22
143735	21
146772	21
151474	insuff
144584	insuff
143463	insuff
140956	insuff
135036	insuff
143700	insuff
144036	insuff
158589	insuff
141908	insuff
151536	insuff
142351	21
144005	30 lode
145587	insuff
145769	insuff
151932	insuff
142914	18
146099	insuff
152726	insuff
146809	insuff
158080	27
146715	insuff
130116	insuff
151638	insuff
144041	24
143202	insuff
144694	insuff
141623	20
154097	insuff
141735	23
151379	27
141468	insuff
138225	18
151054	insuff
146191	insuff
141124	insuff
141191	insuff
140809	24
151705	30 lode
147845	insuff
143763	23
135520	21
151652	insuff
139747	insuff
141928	insuff
150992	insuff
147568	insuff
144928	insuff
140945	30
139221	insuff
147628	insuff
132372	21
131170	24
144621	30 lode
124450	30
146523	30
153377	insuff
143631	insuff
144564	insuff
139628	21
150099	insuff
150285	insuff
135029	insuff
146724	18
144269	18
147433	27
141183	20
151516	20
142289	20
144566	26
141730	insuff
144629	insuff
141866	insuff
138827	insuff
136071	21
143378	insuff
137876	insuff
144219	18
143538	18
143837	insuff
143834	23
142612	20
150455	21
141552	18
152913	insuff
142341	insuff
150989	insuff
146652	insuff
143456	insuff
146127	insuff
141835	insuff
150538	insuff
146066	21
144226	18
136206	26
148858	insuff
136920	insuff
151330	29
141659	23
141140	insuff