Ricerca Operativa

Crediti

Propedeuticità

Nessuna.

Settore scientifico-disciplinare

MAT/09 Ricerca Operativa.

Modalità dell’esame

Prova scritta (esercizi e problemi numerici eventualmente a risposta multipla) e orale.

Obiettivi
formativi

L’insegnamento si prefigge quale obiettivo principale l’introduzione degli studenti all’uso dei modelli di programmazione matematica ed in particolare sia ai modelli di ottimizzazione lineare (sia continui che a variabili intere) che ai modelli di ottimizzazione non lineare.

Programma

Definizione e classificazione dei problemi di ottimizzazione e dei problemi di decisione e classificazione dei relativi metodi risolutivi. Programmazione Lineare (PL): il Metodo del Simplesso. Problemi di Programmazione Lineare Intera. Metodi esatti per la risoluzione dei problemi di Programmazione Lineare Intera. Esempi di problemi di PLI con matrice dei vincoli uni-modulare. Problemi dello Zaino e algoritmi risolutivi. Problemi di Ottimizzazione su grafi ed alberi: Vertex Cover ed Albero di Copertura Minimo. Il problema del Vertex Cover: un algoritmo 2-approssimato per il problema del Vertex Cover. Il problema dell’albero di copertura di un grafo a costo minimo (MST): l’algoritmo di Kruskal. Problemi di Ottimizzazione su grafi ed alberi: Problemi di Cammino Minimo. Cammini in un grafo orientato: il problema della raggiungibilità (visita in ampiezza; visita in profondità). Il problema dei cammini minimi: l’algoritmo di Dijkstra; l’algoritmo di Floyd e Warshall. Problemi di Ottimizzazione su grafi ed alberi: Pianificazione di un Progetto e Problema del Massimo Flusso. Pianificazione di un progetto: il Metodo CPM. Problemi di flusso su reti: il problema del massimo flusso; teorema max-flow min-cut; algoritmo di Ford-Fulkerson. Ottimizzazione Non Lineare Non Vincolata: Metodi del Gradiente, Metodo di Newton, Metodi delle direzioni coniugate. Metodi basati sui Moltiplicatori di Lagrange.

Risultati dell’apprendimento
attesi

Al termine dell’insegnamento, lo studente deve dimostrare di

comprendere e conoscere le tecniche di formalizzazione dei modelli di ottimizzazione (lineare e nonlineare) per problemi di logistica, organizzazione, pianificazione, scheduling, trasporto, flusso su reti e problemi su grafi ed alberi;
saper applicare le conoscenze acquisite sviluppando e risolvendo modelli matematici dei classici problemi di ottimizzazione (lineare e nonlineare) e dei relativi algoritmi di risoluzione nei campi della Pianificazione della Produzione, della Localizzazione, della Gestione delle Scorte e della Logistica;
saper comunicare in maniera chiara, rigorosa ed efficace idee e soluzioni a interlocutori specialisti e non specialisti;
saper individuare i metodi più appropriati per analizzare e risolvere un problema inerente gli argomenti del corso e interpretare correttamente i risultati.

Risultati di apprendimento
che si intende verificare

Verifica della abilità nella risoluzione di esercizi di varia difficoltà; chiarezza, correttezza e completezza nell’esposizione scritta e orale degli argomenti inerenti l’insegnamento.

Ricerca Operativa