Programma Ricerca Operativa A.A. 2015-16
L'obiettivo del corso è quello di introdurre alla teoria dei grafi e alla programmazione lineare e ad alcune loro applicazioni rilevanti. Incidentalmente, si discuteranno elementi di complessità degli algoritmi e dei problemi.
Problemi di decisione e di programmazione matematica
Definizioni relative ai problemi di programmazione matematica: variabili decisionali, vincoli, funzione obiettivo. Problema vuoto, illimitato con ottimo finito. Problemi di ottimizzazione combinatoria. Problemi di programmazione lineare e lineare intera. Problemi di Ottimizzazione Combinatoria e relazione con la PLI.
Problemi di programmazione matematica vuoti, illimitati, con ottimo finito. Teoremi. (1) In un problema di programmazione matematica con f.o. concava e regione ammissibile P, polìtopo non vuoto, esiste un ottimo su un vertice di P. (2) L'ottimo locale di un problema di programmazione convessa è anche ottimo globale. Elementi di geometria di R^n.
Problemi di PL in forma standard. Definizioni di base, matrice di base, soluzione base (ammissibile). Thm. x è SBA di un PL in forma standard se e solo se è un vertice del poliedro regione ammissibile del PL: dimostrazione. Fase I del metodo del simplesso: condizione di ottimo per una SBA, cambiamento di base, definizione di una nuova SBA con valore migliore della f.o. Forma tableau del metodo del simplesso. Fase I del metodo del simplesso: definizione del problema artificiale. Determinazione di una SBA/condizioni di "vuotezza" di un PL. Metodo delle due fasi.
Metodo del simplesso revised: condizione di ottimo per una SBA, cambiamento di base, definizione di una nuova SBA ottima.
Teoria della dualità per la PL: introduzione. Rilassamento lagrangiano di un PL e determinazione del duale di un PL. Calcolo del duale di PL in formati diversi. Proprietà di dualità forte. Condizioni di ortogonalità per una coppia di PL Primale/Duale. Teoria della dualità per la PL: esempi sull'applicazione delle condizioni di ortogonalità. Analisi di sensibilità. Interpretazione economica del problema della dieta e del problema dei trasporti.
Il metodo del simplesso duale. Introduzione di vincoli aggiuntivi.
Formulazione di problemi di PL: Problema dei trasporti, minimizzazione di funzioni modulo e massimo di pi funzioni lineari come PL. Scheduling su macchina singola. Composizione di portfolio titoli. Problema di cutting stock unidimensionale (o minimizzazione degli "sfridi").
Teoria dei Grafi
Grafi non orientati: definizioni. Relazioni binarie e grafi. Ipergrafi. Grafi semplici/multigrafi; loop. Grado di un nodo (Handshaking Lemma). Lati e vertici adiacenti. Cammini. Sottografi. Insiemi indipendenti. Grafi euleriani: C.N.e S. perché un grafo (anche con lati multipli) sia euleriano. Grafi complemento e relazioni di conoscenza. Primo e secondo principio di induzione. Esempi. Connessione e aciclicità: numero delle componenti connesse di sottografi (G\e, G\v); minimo numero di lati di un grafo connesso, massimo numero di lati di un grafo aciclico. Teoremi e dimostrazioni. Alberi. Procedura "Growing-tree". Alberi ricoprenti. Grafi bipartiti. Thm. Un grafo è bipartito se e solo se non ha cicli dispari.
Conteggio. Princìpi della somma e del prodotto. Pidgeon principle. r-permutazioni, r-combinazioni. Esempi (rif. Sinossi 2).
Conteggio. Generalized Pidgeon Principle. Identità di Pascal. Algoritmi, definizioni, caratteristiche. Line Search. Notazioni asintotiche ("Big-O", Omega, Theta). Complessità computazionale di un algoritmo. Binary search. Algoritmi di visita di un albero.
Grafi orientati. Definizioni di walk, trail, path. Algoritmi di ricerca o visita di un grafo orientato: visite in ampiezza e in profondità. Numerazione topologica: thm. grafo connesso aciclico se e solo se ammette numerazione topologica.
Alberi ricoprenti di peso minimo (MST) per grafi non orientati e connessi. Thm. Un albero ricoprente T è un MST se e solo se ogni arco di T è "leggero". Algoritmi di Kruskal e Prim per la determinazione di un MST: correttezza e complessità computazionale.
Albero dei cammini minimi (singola sorgente) su grafi orientati (connessi) pesati. Proprietà: un sottocammino da x a y di un cammino minimo da s a v è un cammino minimo da x a y. Conseguenza: l'unione dei cammini minimi da s a tutti gli altri nodi è un albero (arborescenza) con radice s. Distanza d(v) di un nodo v da s. Un cammino da s a v è minimo se e solo se, per ogni arco (u,v) del cammino, d(v)=d(u) + cuv. Algoritmo di Dijkstra per il calcolo di un albero dei cammini minimi su grafo orientato: correttezza, complessità.
Algoritmo di Floyd-Warshall per il calcolo dei cammini minimi su grafo orientato, fra tutte le coppie di nodi: correttezza, complessità.
Problemi di flusso su reti: il problema di massimo flusso. Definizioni: flusso e suo valore, sezione e sua capacità, flusso attraverso una sezione. Algoritmo di Ford e Fulkerson per il problema di massimo flusso: correttezza, complessità. Problemi di flusso a costo minimo: relazione con i problemi di massimo flusso.
Matching su grafo bipartito. Vertex cover. Cammini alternanti [aumentanti].
Consulta anche il Calendario del corso per sapere quali argomenti sono stati (e saranno) trattati lezione per lezione e i relativi riferimenti ai testi.