Ricerca operativa

Finalità

Il corso si propone di illustrare le principali metodologie messe a disposizione dalla Ricerca Operativa per la soluzione dei problemi decisionali che si presentano nell'industria e nei servizi.

Programma

Simulazione di sistemi discreti
Generazione di variabili aleatorie, metodo della trasformazione inversa.
Descrizione statica e dinamica di un sistema, metodo della programmazione degli eventi, metodo della interazione dei processi, diagrammi di flusso per problemi di simulazione.
Linguaggio SIMSCRIPT II.
Complessita' computazionale e Problemi di ottimizzazione
Complessita' degli algoritmi e dei problemi.
Problemi polinomiali ed NP-completi.
Algoritmi enumerativi per problemi NP-completi.
Modelli matematici dei problemi di ottimizzazione. Algoritmi esatti ed euristici.
Problemi polinomiali su grafi
Definizioni relative a grafi orientati e non orientati.
Problemi di cammini: cammini minimi, cammini in grafi aciclici.
Problemi di alberi: alberi ricoprenti a costo minimo.
Problemi di flusso su rete: flusso massimo.
Cenni a problemi non polinomiali: Circuiti Hamiltoniani e Problema del Commesso Viaggiatore.
Programmazione lineare
Forme canonica e standard di un problema di programmazione lineare.
Soluzioni ammissibili e soluzioni base.
Algoritmo del simplesso: interpretazione geometrica, criterio di ottimalita', degenerazione, determinazione di una soluzione base iniziale.
Teoria della dualita': problema duale, algoritmo del simplesso duale.
Utilizzazione del package di programmazione lineare LINDO.
Programmazione lineare intera
Formulazioni di un problema PLI.
Totale unimodularità
Metodo dei piani di taglio e metodo branch and bound.
Algoritmi esatti per problemi NP-difficili
Metodo Branch and Bound: schemi di separazione, determinazione dei bound (rilassamento per eliminazione di vincoli, rilassamento surrogato, rilassamento lagrangiano, tecnica del subgradiente), procedure di riduzione.
Algoritmi per la soluzione ottima del problema del knapsack singolo.
Algoritmi euristici per problemi NP-difficili
Algoritmi per la determinazione di soluzioni ammissibili.
Algoritmi di postottimizzazione.
Algoritmi per la soluzione approssimata dei problemi del knapsack singolo e del commesso viaggiatore.

Attività d'esercitazione

Modalità d'esame

Propedeuticità

Testi consigliati

S. MARTELLO: " Lezioni di Ricerca Operativa " , III Edizione, Progetto Leonardo, Bologna, 1998.
S. MARTELLO, D. VIGO: " Esercizi di Ricerca Operativa " , IV Edizione, Progetto Leonardo, Bologna, 1997.
S. MARTELLO, D. VIGO:" Esercizi di Simulazione Numerica ", Progetto Leonardo, Bologna, 1996.
M. FISCHETTI: " Lezioni di Ricerca Operativa ", Edizioni Libreria Progetto, Padova, 1995.
M. DELL'AMICO: " 120 Esercizi di Ricerca Operativa ", Pitagora, Bologna, 1996.

Testi d'approfondimento

Aggiornato