| | | |  corso | | | |
Programmazione Matematica B
(Corso di Laurea in Informatica (quinquennale))
| Codice: | 4I016 | Crediti: | 6 | Semestre: | 1 | Sigla: | PM | |
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
risoluzione di problemi di ottimizzazione, con la relativa teoria.
Verranno utilizzati i fogli elettronici (spreadsheets) per la
modellizzazione e soluzione dei problemi.
English Description
The course is intended to provide basic knowledge of modelling,
Linear Programming techniques and network flow algorithms. The course
is focused on one hand over the construction of mathematical models
for possible applications, and on the other hand over the algorithms
and their theory. Spreadsheets are used to model and solve
optimization problems.
Programma
- Introduzione alla modellistica (6 ore)
- Problemi decisionali, problemi di ottimizzazione ed esistenza;
classi di problemi.
- Uso dei fogli elettronici 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 limitazione 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.
- Alberi di copertura ottimi.
- Flusso massimo.
- Flusso di costo minimo.
- Accoppiamenti su grafi bipartiti.
- Programmazione Lineare (11 ore)
- Modelli di Programmazione Lineare, coppie di problemi
Primale-Duale e teorema debole della dualità.
- Vincoli attivi e non attivi, 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.
(Le ore indicate non includono le esercitazioni)
| Ore lezione: | 25 | Ore esercitazione: | 15 | | | |
Bibliografia
-
HREF="http://www.di.unipi.it/di/groups/optimize/Courses/AppuntiPM.html"
Appunti
- F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa",
Franco Angeli, Milano (1999)
- A. Sassano, "Modelli e algoritmi della ricerca operativa", Franco Angeli, Milano (1999)
- C. Vercellis, "Modelli e decisioni", Progetto Leonardo, Bologna (1997)
Modalità di esame
Prova scritta seguita da una prova orale.
I contenuti dell'esame sono quelli del corso dell'Anno Accademico a cui si
riferisce l'appello, anche per gli studenti che avessero seguito il corso
in anni precedenti.
