Ricerca Operativa 2012/2013

I PARTE:

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. Cammini su grafo, walk, trail, path. Circuiti e cicli. Grafi complemento, insiemi indipendenti, 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. Problemi di flusso massimo su rete: reti residue, tagli e flussi, algoritmo di Ford e Fulkerson, teorema del massimo flusso e minimo taglio.

II PARTE:

Modelli di programmazione lineare: pianificazione della produzione, miscelazione,...; Cenni ai modelli di programmazione intera. Teoria della programmazione lineare: introduzione, condizioni geometriche di ottimalità e illimitatezza, condizioni algebriche di ottimalità. Teoria della dualità nella programmazione lineare: introduzione, proprietà della coppia primale- duale, analisi di sensitività, interpretazione economica della dualità. Algoritmo del simplesso per la programmazione lineare: introduzione, la matrice di pivot, inizializzazione dell’algoritmo, convergenza dell’algoritmo, algoritmo del simplesso rivisto. Altri algoritmi per la programmazione lineare: algoritmo del simplesso duale; algoritmo primale- duale. Cenni ai problemi e alle tecniche per la programmazione intera.