Obiettivi formativi
Lo studente dovrebbe essere in grado di eseguire i passi tipici di un aproccio analitico alla risoluzione di problemi decisionali, ovvero:
1) creazione del modello matematico per un problema reale
2) individuazione di un opportuno algoritmo di risoluzione
3) analisi dell'output dell'algoritmo di risoluzione
Prerequisiti
Nozioni di algebra lineare di base.
Nozioni di analisi.
Contenuti dell'insegnamento
Introduzione alla Ricerca Operativa: dal problema reale agli algoritmi di risoluzione
Modelli matematici. Componenti principali e loro traduzione in linguaggio matematico.
Il linguaggio di modellizzazione AMPL
Esempi di modelli matematici: problemi di flusso a costo minimo e massimo, problemi di flusso multicommodity, problema del commesso viaggiatore, problemi di instradamento dei veicoli
I problemi di Programmazione Lineare (PL). Forma canonica. Regione ammissibile e insieme delle soluzioni ottime.
Proprietà della regione ammissibile. Vertici e raggi estremi. Il teorema di rappresentazione della regione ammissibile.
Il metodo di risoluzione per via grafica e il riconoscimento delle diverse forme possibili dell’insieme delle soluzioni ottime.
Il teorema fondamentale della PL e le sue implicazioni algoritmiche.
Prime nozioni per l’introduzione dell’algoritmo del simplesso. Basi e soluzioni di base.
Coefficienti di costo ridotto.
L’operazione di cardine. I passi dell’algoritmo del simplesso.
Finitezza dell’algoritmo e commenti sulla sua complessità.
Soluzione ottima unica e soluzioni ottime multiple.
Individuazione di una base ammissibile iniziale: il metodo due fasi.
Problemi di Programmazione Lineare Intera (PLI). Aspetti teorici. Chiusure convesse. Matrici totalmente unimodulari. Problemi di PLI “semplici”
Algoritmi branch-and-bound.
Algoritmi di taglio
Introduzione alla complessità. Complessità degli algoritmi.
Esempi di algoritmi per il problema di cammino a costo minimo.
Esempi di algoritmi per il problema di albero di supporto a peso minimo.
La classe P dei problemi risolvibili in tempo polinomiale.
La classe NP e i problemi NP-completi
Riduzioni polinomiali. Esempi di problemi NP-completi.
I problemi di approssimazione. FPTAS, PTAS e risultati di inapprossimabilità.
Algoritmo di approssimazione per il problema del TSP metrico.
FPTAS per il problema KNAPSACK.
La programmazione dinamica. Componenti essenziali dei problemi risolvibili attraverso di essa.
Un algoritmo di programmazione dinamica per il problema KNAPSACK.
I problemi nonlineari. Ottimi locali e globali. Difficoltà dei problemi. Problemi convessi.
Problemi non vincolati: condizioni di ottimalità necessarie del primo e secondo ordine e sufficienti del secondo ordine.
Problemi non vincolati: metodi line search e trust region.
Problemi vincolati. Funzione Lagrangiana. Condizioni di ottimalità (condizioni KKT). Duale di Wolf.
Programma esteso
- - -
Bibliografia
Note pubblicate online dal docente.
Metodi didattici
Lezioni di teoria e di pratica.
Modalità verifica apprendimento
Esame scritto con domande sulla teoria.
Risoluzione a casa di un piccolo progetto con discussione finale.
Altre informazioni
- - -