Ricerca Operativa 2017/2018

Introduzione alla Ricerca Operativa: generalità sui problemi di ottimizzazione. Cenni ed applicazioni sull'analisi combinatoria: permutazioni, combinazioni, coefficienti binomiali e proprietà. Algoritmi: proprietà, algoritmi di ricerca lineare e ricerca binaria. Crescita di funzioni, notazione Big-O. Complessità degli algoritmi. Grafi: introduzione e definizioni di base. Sottografi, ordine e dimensione di un grafo. Vicinati e grado di un nodo, k-regolarità di un grafo, fattorizzazioni. Percorsi, sentieri e cammini. Circuiti e cicli. Grafo complemento. Cricche, insiemi indipendenti, dominanti e ricoprenti. Numero cromatico di un grafo. Strutture dati per grafi: matrice di incidenza, matrice di adiacenza, lista di adiacenza. Isomorfismo tra grafi. Componenti connesse. Proprietà dei grafi connessi e/o aciclici. Alberi. Grafi bipartiti. Circuiti e cammini Euleriani e Teorema di Eulero. Cicli e cammini Hamiltoniani. Grafi planari, definizioni e proprietà, grafi duali. Algoritmi di ricerca su grafo, ricerca in ampiezza e ricerca in profondità. Ordinamenti topologici su digrafo, algoritmo di ordinamento topologico su digrafo. Problema del minimo albero ricoprente: introduzione, teoremi di ottimalità sui tagli e sui path, algoritmo di Kruskal, algoritmo di Prim. Problemi di flusso su rete, generalità sui problemi di flusso a costo minimo. Problema dei cammini minimi su grafo: condizioni di Bellman, algoritmo primale generico, algoritmo di Dijkstra, algoritmo su digrafi aciclici, algoritmo di Bellman-Ford, algoritmo di FLoyd-Warshall.Problema del flusso massimo su rete: reti residue, tagli e flussi, algoritmo di Ford e Fulkerson, teorema del massimo flusso e minimo taglio. Problema dell'abbinamento massimo su grafo bipartito: algoritmo cammini alternanti aumentanti, teorema di Hall, teorema di Konig.

La formulazione di problemi decisionali in termini di programmazione matematica. La programmazione lineare: richiami di geometria e algebra lineare, poliedri, vertici di un poliedro e soluzioni di base. Algoritmi per la programmazione lineare: il metodo del simplesso, il metodo del simplesso in due fasi, il metodo del simplesso con la funzione big-M. La dualità nella programmazione lineare. Algoritmi per la programmazione lineare basati sulla coppia primale-duale: il duale del simplesso, il metodo primale duale.