Lo scopo del corso è quello di fornire una panoramica (per
quanto necessariamente ristretta) sui principali aspetti teorici e
pratici inerenti alla costruzione di modelli matematici di sistemi
reali, con particolare riferimento ai modelli di ottimizzazione, ed
alla loro soluzione algoritmica.
Verranno presentate le proprietà matematiche alla base di alcune
delle principali tecniche algoritmiche per la soluzione di tre grandi
classi di problemi di ottimizzazione, in ordine cresciente di
difficoltà: problemi di cammino e flusso su reti, problemi di
programmazione lineare, e problemi di ottimizzazione combinatoria.
Verranno discusse le proprietà che rendono alcuni di questi
problemi "facili" ed altri "difficili", e l'impatto che esse hanno sugli
algoritmi risolutivi disponibili. Verranno inoltre discusse le
problematiche relative alla costruzione di modelli matematici che
coniughino (per quanto più possibile) la rispondenza del modello
alla situazione reale rappresentata con la risolubilità
computazionale dello stesso, fornendo tecniche ed esempi applicativi che
consentano allo studente di acquisire la capacità di modellare
autonomamente i problemi con gli strumenti che attualmente sono
considerati tra i migliori in pratica.
Problemi e Modelli (4 ore)
Grafi e Reti di flusso (18 ore)
Programmazione Lineare (18 ore)
Ottimizzazione Combinatoria (20 ore)
(Le ore indicate includono le esercitazioni)
I seguenti argomenti presenti negli appunti non fanno parte del programma del corso per l'anno corrente:
2.3.2: dimostrazione del Lemma 2.3
2.3.4: Algoritmo basato su preflussi
2.4.1: dimostrazione del Teorema 2.9
2.4.3: Algoritmo basato su cammini minimi successivi
2.5.2: algoritmo basato sui cammini minimi successivi per il problema dell'assegnamento di costo minimo
2.5.3: Accoppiamento di massima cardinalità a bottleneck
3.1.1: dimostrazioni dei teoremi tranne quella del Corollario 3.1
3.2.3: dimostrazione del Lemma di Farkas (Teorema 3.10)
5: tutto il capitolo tranne 5.1.1.1, 5.1.1.3 e 5.1.2.1
6: tutto il capitolo tranne 6.2.1.2 e 6.2.1.4
7.2.3: Regole di dominanza
7.2.5: Preprocessing
A.3.3: Complessità ed approssimazione
B.2.4: Livello dei nodi di un albero
B.4: tutto il paragrafo tranne la definizione del problema e lo pseudo-codice dell'Algoritmo di Kruskal
Massimo Pappalardo, Mauro Passacantando "Ricerca Operativa", Plus, 2010
F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa", Franco Angeli, Milano (1999)
Per iscriversi all'esame (comprese le prove scritte) è necessario aver verbalizzato gli esami di Algebra Lineare ed Analisi Matematica II. Come richiesto dal CCS, il controllo su queste propedeuticità sarà stretto e senza eccezioni.