corso

Ricerca Operativa A

Codice:	029AA	Crediti:	6	Semestre:	2	Sigla:	RO

Settore disciplinare:		MAT/09 - Ricerca Operativa

Docente

Giancarlo Bigi

Tel. 0502213124

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:

Ore esercitazione:

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.html
www.di.unipi.it/~bigig/dida/roa/soluzioni.html (soluzioni dettagliate dei compiti d'esame)

Altri testi
R.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.