| | | corso | | | | |
Ricerca operativa B
Codice: | AA014 | Crediti: | 6 | Semestre: | 2 | Sigla: | RO | |
|
Settore disciplinare: | MAT/09 - Ricerca Operativa |
Docente
Stefano Pallottino
Prerequisiti
- Matematica Discreta
- Analisi Matematica I
- Algoritmi e Strutture Dati I
Obiettivi di apprendimento
Fornire allo/a studente/essa le conoscenze di base relative alla
modellistica, ai problemi di flusso su reti e alla Programmazione
Lineare e introdurre all'uso di software per il trattamento di dati e
la risoluzione di problemi di ottimizzazione.
Descrizione
Il corso si propone di fornire allo/a studente/essa le conoscenze di
base relative alla modellistica, ai problemi di flusso su reti e alla
Programmazione Lineare. Il corso presenterà principalmente gli aspetti
relativi alla modellazione di problemi di ottimizzazione ed alle
possibili applicazioni, e le classi di algoritmi per la soluzione dei
diversi problemi di ottimizzazione affrontati, con la relativa teoria.
VERRÀ PRESENTATO L'USO DEI FOGLI ELETTRONICI (SPREADSHEETS) COME
STRUMENTO PER LA MODELLAZIONE E LA SOLUZIONE DI PROBLEMI
DECISIONALI.
English Description
The course is intended to provide basic knowledge of modelling and
Linear Programming techniques and network flow algorithms. The course
is mainly focused over the construction of mathematical models and to
possible applications and over the algorithms and their theory.
The use of spreadsheets to model and solve decision problems will
be presented.
Programma
- Introduzione alla modellistica
- Problemi decisionali, problemi di ottimizzazione ed esistenza;
classi di problemi.
- Uso DI UN TABELLONE ELETTRONICO per la formulazione e risoluzione
di problemi di ottimizzazione.
- Uso delle variabili (continue, discrete, decisionali,...);
formulazione di vincoli (restrizioni, vincoli classici, vincoli per il
trattamento di variabili complesse, vincoli per il trattamento di
insiemi disgiunti, vincoli per il trattamento di limtazione di
valori,...), formalizzazione della funzione obiettivo (obiettivi
lineari, in valore assoluto, lineari a tratti, di tipo
``bottleneck'',...).
- Classi di algoritmi (algoritmi greedy, algoritmi di ricerca
locale ed algoritmi enumerativi).
- Grafi e Reti di flusso (8 ore)
- Introduzione: alberi, cammini e tagli, visite di grafi e alberi.
- Cammini minimi e alberi di copertura ottimi.
- Flusso massimo e flusso di costo minimo.
- Accoppiamenti su grafi bipartiti.
- Programmazione lineare
- Modelli di Programmazione Lineare, coppie di problemi
Primale-Duale e teorema debole della dualità.
- Vincoli attivi e non attivi, direzioni, direzioni ammissibili e/o
di miglioramento; teorema forte della dualità scarti
complementari e interpretazione economica della dualità.
- Basi complementari, considerazioni geometriche; algoritmi del
simplesso primale e duale.
- Riottimizzazione ed analisi parametrica.
- Presenza di più obiettivi (Goal Programming).
Bibliografia
Modalità di esame
Scritto e orale