Calendario Ricerca Operativa 2015-16
Consulta questa pagina per sapere quali argomenti sono stati (e saranno) trattati lezione per lezione e i riferimenti necessari.
58. venerdì 22/1/16. Seconda prova d'esonero (ore 14.30, aule 1 e 4). Fine del corso.
57. venerdì 22/1/16. Lezione sospesa.
56. giovedì 21/1/16. Esercizi di ricapitolazione.
55. martedì 19/1/16 pomeriggio. Esercizi di ricapitolazione.
54. martedì 19/1/16 mattina. Ancora sui cammini minimi. Esempi ed esercizi di ricapitolazione.
53. venerdì 14/1/16. Albero dei cammini minimi su digrafo: Algoritmi di Dijkstra e per grafi aciclici. Esempi (rif. Oriolo Sinossi 6).
52. giovedì 14/1/16. Condizioni di esistenza di un albero dei cammini minimi. Potenziale come soluzione duale del PL formulazione del problema di determinare un albero dei cammini minimi (rif. dispensa in preparazione). Algoritmo di Ford-Bellman (rif. Oriolo Sinossi 6).
51. martedì 12/1/16 pomeriggio. Cammino minimo s-t su grafo orientato. Formulazione come problema di flusso a costo minimo. Albero dei cammini minimi (singola sorgente) su grafi orientati (connessi) pesati. Concetto di potenziale, potenziale come stima per difetto delle distanze dalla sorgente. (rif. Oriolo Sinossi 6).
50. martedì 12/1/16 mattina. Algoritmo di Ford e Fulkerson per il problema di massimo flusso: definizione di rete residuale e cammino aumentante, dualità forte: il valore del massimo flusso (s,t) è pari alla capacità minima di un taglio (s,t). Esempi, esercizi d'esame. (rif. Oriolo Sinossi 7, Fischetti Sez. 7.7).
49. venerdì 8/1/16. Algoritmo di Ford e Fulkerson per il problema di massimo flusso: definizioni, flusso attraverso (e capacità di) un (s,t)-taglio (rif. Oriolo Sinossi 7, Fischetti Sez. 7.7).
48. giovedì 7/1/16. Problemi di flusso a costo minimo e di massimo flusso: definizione, proprietà e formulazione PL (rif. Fischetti Se. 7.7, dispense del prof. Iovanella, Cap. 6, Sez. 6.2).
Festività
47. venerdì 18/12/15. Elementi di conteggio (rif. Sinossi 2 Oriolo). Esempi ed esercizi d'esame.
46. giovedì 17/12/15. Elementi di conteggio: pigeonhole principle (rif. slides Peng Shi), r-permutazioni, r-combinazioni (rif. Sinossi 2 Oriolo).
45. martedì 15/12/15 pomeriggio. Algoritmi di Prim e di Kruskal per la determinazione di un MST. Correttezza e complessità computazionale (rif. testo g. Cormen et. al., cap. 23). Esempi. Esercizi d'esame su MST, scrittura duale e formulazioni di PLI.
44. martedì 15/12/15 mattina. Algoritmi di visita di grafi in profondità DFS e in ampiezza BFS (rif. dispense del prof. Iovanella, Cap. 5, Sez. 5.1, oppure ). Matching su grafo bipartito: determinare cammini aumentanti alternanti o provare che non esistono: algoritmo su digrafo. Thm. di König (rif. note su Bipartite matching di M. Goemans)
43. lunedì 14/12/15. Prima prova d'esonero (ore 16, aule 2 e 4). Testi con soluzione.
42. venerdì 11/12/15. Grafi bipartiti: thm.: grafo è bipartito se e solo se non contiene cicli dispari. Matching su grafo bipartito: cammini alternanti rispetto a un matching. Thm.: un matching M è massimo se e solo se non esistono cammini alternanti aumentanti rispetto a M (rif. note su Bipartite matching di M. Goemans) .
41. giovedì 10/12/15. Esercizi (d'esame e non): formulazione di problemi di PL, simplesso duale.
40. venerdì 4/12/15. (la lezione comincia alle ore 10). Ancora esercizi su formulazioni PL e duale. Il problema del cutting stock (problema degli sfridi).
39. giovedì 3/12/15. Esercizi (d'esame e non): formulazione di problemi di PL, scrittura del duale.
38. martedì 1/12/15 pomeriggio. Algoritmi di Prim e di Kruskal per la determinazione di un MST. Correttezza e complessità computazionale (rif. testo g. Cormen et. al., cap. 23). Esempi. Esercizi d'esame su MST, scrittura duale e formulazioni di PLI.
37. martedì 1/12/15 mattina. Alberi ricoprenti di peso minimo (MST) per grafi non orientati e connessi. Thm.2 Un albero T ricoprente di G è un MST di G se e solo se, per ogni taglio su G indotto da un lato e di T, il lato e è un arco "leggero" rispetto a S (dispensa su MST).
35. giovedì 26/11/15. Ancora esercizi (d'esame e non) su cicli e trail euleriani: qui un'implementazione dell'algoritmo di Hierholzer.
34. martedì 24/11/15 pomeriggio. Esercizi: un'euristica ("del collega") per il problema del Max Cut. Esercizi d'esame: disegno di grafi semplici non orientati, applicazioni dell'handshaking lemma, grafi complemento.
33. martedì 24/11/15 mattina. Ancora su alberi e foreste. Cicli e Trail Euleriani: caratterizzazione, algoritmo di Hierholzer (rif. Sinossi 1 Oriolo ma anche, perché no, wikipedia).
31. giovedì 19/11/15 . Max Cut formulazione PLI (rif. dispensa MiniMaxGraphRelat.pdf nel Repository). Rappresentazione di grafi: matrici di incidenza e adiacenza, liste di successori (rif. Fischetti Sez. 7.3).
36. venerdì 27/11/15. Alberi ricoprenti di peso minimo (MST) per grafi non orientati e connessi. Formulazione PLI. Thm.1 Se un albero T ricoprente di G è un MST di G allora, per ogni taglio S di G, T contiene almeno un arco "leggero" rispetto a S (rif. Fischetti Sez. 7.5; dispensa su MST).
32. venerdì 20/11/15. Connessione su grafi n.o. semplici: componenti connesse e aciclicità, alberi, procedura "Growing Tree". Raggiungibilità e connessione forte su digrafi (rif. Fischetti Sez. 7.1,7.2; e Sinossi 1 Oriolo).
30. martedì 17/11/15 pomeriggio. Esercitazioni: Definizione del problema di Max Cut; Minimum Vertex-Cover e Maximum Matching: formulazione come PLI e relazioni di dualità (rif. dispensa MiniMaxGraphRelat.pdf nel Repository).
29. martedì 17/11/15 mattina. Grafi orientati e non: definizioni. semplici/multigrafi/pseudografi (loop). Taglio, lati di un taglio. Grado di un nodo. Handshaking Lemma. (rif. Fischetti, Sez.7.1, 7.2, 7.3 e Sinossi 1 Oriolo). Cammini su grafi non orientati (gnos) e su digrafi: walk, trail, path, circuiti, cicli. Connessione su gnos: componenti connesse.
28. venerdì 13/11/15. Esercitazione: Esercizi d'esame su formulazione di problemi di decisione come PL(I).
27. giovedì 12/11/15 . Esercitazione: Esercizi d'esame su formulazione di problemi di decisione come PL(I).
26. martedì 10/11/15 pomeriggio. Esercitazione: Esercizi d'esame su formulazione di problemi di decisione come PL(I).
25. martedì 10/11/15 mattina. Teoria della dualità per la PL: analisi di sensibilità (rif. Fischetti, Sez.5.8). Esercizi di ricapitolazione sulla dualità per la PL.
24. venerdì 6/11/14. Problemi di localizzazione: p-median e p-center.
23. giovedì 5/11/15 . Esempi e applicazioni delle condizioni di ottimalità: rilassamento lineare del problema di knapsack {0,1} e sua soluzione ottima attraverso le condizioni di ortogonalità.
22. martedì 3/11/15 pomeriggio. Esercizi d'esame su formulazione, soluzione e dualità PL. Metodo del simplesso duale (rif. Fischetti, Sez 5.7).
21. martedì 3/11/15 mattina. Teoria della dualità per la PL: Condizioni di ortogonalità per una coppia di PL Primale/Duale. Esempi e applicazioni delle condizioni di ottimalità (rif. Fischetti, Sez. 5.5)
20. venerdì 30/10/15. La lezione è rinviata a: Lunedì 2/11 ore 11.30 aula C11. Dualità forte per la PL (dimostrazione) (rif. Fischetti, Sez. 5.4). Esercizi su soluzione di un PL e del suo duale.
19. giovedì 29/10/15. Dualità per la PL: Formulazione del duale del problema dei trasporti. Definizione e formulazione del problema di knapsack binario KP-{0,1} (rif. Fischetti, Sez. 3.0.2). Duale del rilassamento di KP-{0,1}. Interpretazione economica del duale (esempi: problema della dieta/miscelazione; problema dei trasporti), definizione dei "prezzi ombra".
18. martedì 27/10/15 pomeriggio. Duale di un PL con obiettivo max. (rif. Fischetti, Sez. 5.2 e 5.3). Dualità per la PL: scrittura del duale di PL in formati diversi - due approcci: trasformazione di formato e rilassamento lagrangiano (rif. Fischetti, Sez. 5.2).
17. martedì 27/10/15 mattina. Rilassamento di un problema di ottimizzazione, rilassamento lineare di un PLI, rilassamento lagrangiano di un PL. Introduzione alla teoria della dualità: determinazione del duale di un PL. Dualità debole. Duale del duale equivale al Primale. (rif. Dispensa "Introduzione alla dualità nella PL").
Lunedì 26/10/15 Aula C11 ore 11.30. (recupero Lezione 3): (A cura del dott. T. Bacci). sempi ed esercizi di modelli di PL e PL(I): allocazione di risorse scarse; cutting stock (min. degli sfridi); Problemi di ottimizzazione combinatoria (CO): set covering (rif. Fischetti, Sez.6.1, 6.2, 6.3).
16. venerdì 23/10/15. Esercitazione: formulazione e risoluzione di problemi di PL su foglio elettronico (altri esempi problema di programmazione della produzione e magazzino, trasporti, costi fissi). Qui il link al file Excel relativo al problema di produzione e magazzino. Vedi anche le esercitazioni ROG_class141028 nel repository.
15. giovedì 22/10/15. Formulazione di problemi di decisione come PL(I): supply-demand flow (problema dei trasporti) (rif. Fischetti, Sez. 6.2.1 e "costi fissi" Fischetti Sez. 3.0.1, pag. 23).
14. martedì 20/10/15 pomeriggio. Esercitazione: formulazione e risoluzione di problemi di PL su foglio elettronico (problema della dieta, problema di programmazione della produzione e magazzino).
13. martedì 20/10/15 mattina. Metodo del simplesso revised: condizione di ottimo per una SBA, cambiamento di base, definizione di una nuova SBA ottima (rif. Fischetti, Sez. 4.3).
12. venerdì 16/10/15. Fase I del metodo del simplesso: Esempio su modello di PL.
11. giovedì 15/10/15. Degenerazione e Regola di Bland. Fase I del metodo del simplesso: definizione del problema artificiale. Determinazione di una SBA/condizioni di "vuotezza" di un PL. (rif. Fischetti, Sez. 4.2.5 e 4.2.6). Esempi.
10. martedì 13/10/15 pomeriggio. Lezione sospesa (partecipazione riunione commissione paritetica studenti-docenti)
9. martedì 13/10/15 mattina. Fase II metodo del simplesso: Forma tableau. Esempi. (rif. Fischetti, Sez. 4.2.4).
8. venerdì 9/10/15. Fase II metodo del simplesso: soluzioni di base ammissibili e "dizionari". (rif. Fischetti, Sez. 4.1.1.) Esempio su modello di allocazione di risorse scarse (modello di PL).
7. giovedì 8/10/15. Ancora sul concetto di soluzione di base ammissibile (SBA). Teorema: SBA = vertice. Dimostrazione. Fase II del metodo del simplesso: condizione di ottimo per una SBA, condizione di illimitatezza del PL. Esempi. (rif. Fischetti, Sez. 4.1.1.)
6. martedì 6/10/15 pomeriggio. Problema di PL in forma standard. Base. Soluzione di base (ammissibile). (rif. Fischetti, Sez. 4.1.1.) Esempi.
5. martedì 6/10/15 mattina. Dimostrazione del teorema fondamentale della PL (rif. dispense U. Pisa: cap. 3.) Esempi. Problema di PL in forma standard. (rif. Fischetti, Sez. 1.2)
4. venerdì 2/10/15. Geometria della PL, definizioni: vertici di un polítopo. Rappresentazione implicita di un poliedro. Cono di recessione di un poliedro. Teorema di Weyl-Minkowski. (rif. Fischetti, Sez.4.1. e dispense U. Pisa: cap. 3). Teorema fondamentale: condizioni di illimitatezza per un PL con regione ammissibile P, poliedro non vuoto o esistenza di un ottimo su un vertice di P.
3. giovedì 1/10/15. Lezione sospesa
2. martedì 29/9/15 pomeriggio. Geometria della PL: Definizioni di combinazione lineare e convessa, funzioni convesse. Involucro (o inviluppo) convesso. Combinazione conica. Semispazio affine, iperpiano, poliedro, polìtopo. Facce e vertici di un polítopo. Esempi. (rif. dispense U. Pisa: cap. 3).
1. martedì 29/9/15 mattina. Introduzione al corso di Ricerca Operativa: problemi di decisione e di programmazione matematica. Definizioni relative ai di problema di programmazione matematica: variabili decisionali, vincoli, funzione obiettivo. Problema vuoto, illimitato con ottimo finito(rif. Fischetti, Sez.1). Modelli e formulazione come problema di programmazione lineare del problema di allocazione di risorse (rif. Fischetti, Sez.2).