RICERCA OPERATIVA
cod. 00884

Anno accademico 2011/12
1° anno di corso - Primo semestre
Docente
Settore scientifico disciplinare
Ricerca operativa (MAT/09)
Field
Attività formative affini o integrative
Tipologia attività formativa
Affine/Integrativa
72 ore
di attività frontali
9 crediti
sede:
insegnamento
in - - -

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

- - -