Ricerca Operativa 2012/2013

PRIMA PARTE: DOCENTE G. ORIOLO

Introduzione. Definizioni fondamentali. Handshaking lemma. Primo e secondo principio di induzione. Connessione e aciclicita'. Alberi. Cicuiti euleriani.  Elementi di conteggio. Pigeonhole principle. Combinazioni, permutazioni e coefficiente binomiale.  

Crescita della funzioni. Complessita' degli algoritmi e analisi di alcuni algoritmi di ricerca e ordinamento. Strutture dati per la rappresentazione di grafi e reti.  

Grafi aciclici e ordinamento topologico. Grafi bipartiti e cicli dispari. Numero cromatico. Edge  coloring number  

Il problema dell'albero ricoprente di peso minimo. Condizioni di ottimalita' algoritmi di Prim e Kruskal. La codifica di Huffman  

Il problema del massimo flusso. Capacita' di un taglio. Algoritmo dei cammini aumentanti. Il caso di piu' sorgenti e destinazioni. Il problema del massimo matching su grafo bipartito e il teorema di Hall.  

Il problema del cammino minimo. Algoritmo di Ford. Algoritmo di Ford-Bellman via node-scanning. Algoritmo per reti acicliche. Algoritmo di Dijkstra.

SECONDA PARTE: DOCENTE A. PACIFICI

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.

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")