| | | corso | | | | |
Ricerca Operativa A
(Corso di Laurea in Informatica (classe L-31))
Codice: | 029AA | Crediti: | 6 | Semestre: | 2 | Sigla: | RO | |
|
Settore disciplinare: | MAT/09 - Ricerca Operativa |
Docente
Prerequisiti
Propedeuticità obbligatorie: 006AA “Matematica Discreta” e 008AA “Algoritmica e Laboratorio”.
Inoltre, la conoscenza dei contenuti del corso 005AA “Analisi
Matematica” è altamente raccomandata.
Obiettivi di apprendimento
Il corso presenta gli strumenti necessari alla costruzione e alla
risoluzione di modelli analitici di ottimizzazione per problemi reali,
tipicamente di gestione, di allocazione delle risorse e di logistica.
Verranno illustrate le proprietà teoriche ed alcune delle principali
tecniche algoritmiche per la soluzione di due grandi classi di problemi
di ottimizzazione: problemi di flusso su reti e problemi di
programmazione lineare.
Conoscenze.
Lo studente acquisirà conoscenze sulle principali tecniche di
modellazione mediante strumenti logico/matematici, sulle proprietà
teoriche dei principali problemi di ottimizzazione su rete e dei
problemi programmazione lineare e sui relativi algoritmi risolutivi.
Capacità.
Lo studente saprà
analizzare problemi reali, individuandone le caratteristiche principali
per fornire una sua modellazione mediante strumenti logico/matematici;
studiare e risolvere problemi di ottimizzazione su rete e lineare.
Comportamenti.
Lo studente acquisirà uno spirito critico nell'analisi di problemi
decisionali, nella loro modellazione logico/matematica e nell'analisi
dei risultati.
Descrizione
Il corso si propone di fornire allo studente gli strumenti di base per:
analizzare problemi reali, tipicamente di gestione, di
allocazione delle risorse e di logistica, individuandone le
caratteristiche principali per fornire una sua modellazione mediante
strumenti logico/matematici; studiare le proprietà di alcuni problemi di
ottimizzazione su rete e descrivere ed utilizzare alcuni algoritmi
risolutivi; conoscere le proprietà teoriche della programmazione
lineare, derivando da esse gli schemi algoritmici del simplesso
primale e del simplesso duale.
English Description
This course presents the necessary tools for the construction and resolution of analytical models of
optimisation, management, allocation of resources and logistics.
Programma
Introduzione (2 ore)- Problemi decisionali, problemi di ottimizzazione ed esistenza;
- Classi di problemi; alcuni esempi.
Modelli e loro formulazione (8 ore)
- Tipi di variabili: logiche, continue, discrete;
- Formulazione di vincoli;
- Formulazione della funzione obiettivo.
Grafi e reti di flusso (20 ore)
- Modello generale dei problemi di flusso;
- Alberi, cammini e tagli, visite di grafi e alberi;
- Il problema dei cammini minimi;
- Il problema dell'albero di copertura di costo minimo;
- Il problema del flusso massimo;
- Il problema del flusso di costo minimo.
Programmazione Lineare (18 ore)
- Modelli di Programmazione Lineare, coppie di problemi duali e
teorema debole della dualità
- Vincoli attivi e non attivi, direzioni ammissibili e/o di
crescita, Lemma di Farkas;
- Teorema forte della dualità, scarti complementari e
interpretazione economica della dualità;
- Basi complementari, considerazioni geometriche; algoritmi del
Simplesso Primale e del Simplesso Duale;
- Analisi post-ottimale.
Ore lezione: | 32 | Ore esercitazione: | 16 | | | |
Bibliografia
Testo di riferimento
G. Bigi, A. Frangioni,
G. Gallo, S. Pallottino, M.G. Scutellà "Appunti di Ricerca Operativa",
Servizio
Editoriale Universitario www.di.unipi.it/~bigig/dida/roa/0910/Appunti.html
Esercizi (vecchio corso)www.di.unipi.it/~bigig/dida/roa/Esercizi/Indice.htmlwww.di.unipi.it/~bigig/dida/roa/soluzioni.html (soluzioni
dettagliate dei compiti d'esame)
Altri testiR.K. Ahuja, T.L. Magnnti, J. Orlin,
Network flows. Theory, algorithms and applications, Prentice Hall, 1993.
C. Vercellis,
Modelli e decisioni, Progetto Leonardo, 1999.
P. Serafini,
Ottimizzazione, Zanichelli,
2000.
C. Vercellis,
Ottimizzazione. Teoria, metodi, applicazioni, McGraw Hill, 2008.
Modalità di esame
La valutazione avverrà mediante una prova scritta ed un prova orale. Il
superamento della prova scritta costituisce un prerequisito per accedere
a quella orale. Il corso prevede due prove di verifica intermedia per
l’esonoro dalla prova scritta.