Ricerca Operativa 2011/2012

Ricerca Operativa: programma A.A. 2010/11   Problemi di decisione e di programmazione matematica ----------------------------------------------- [corrisponde ai contenuti del corso "Ricerca Operativa 1" (5 cfu) e Ricerca Operativa 1-2 parte II] 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 ------------- [corrisponde ai contenuti del corso "Grafi e Reti di Flusso" (5 cfu) e Ricerca Operativa 1-2 parte I] 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].