| | | corso | | | | |
Ricerca operativa B
Codice: | AA014 | Crediti: | 6 | Semestre: | 2 | Sigla: | RO | |
|
Settore disciplinare: | MAT/09 - Ricerca Operativa |
Docente
Stefano Pallottino
Prerequisiti
- AA001 Analisi Matematica
- AA005 Algebra
- AA006 Algoritmica
Obiettivi di apprendimento
Fornire allo studente le conoscenze di base relative alla
modellistica, ai problemi di flusso su rete e alla Programmazione
Lineare.
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
The aim of the course is to provide basic knowledge to model real
life management, resource allocation and logistics problems, and to
formulate and solve network flow and linear programming problems.
Specifically, problem analysis and mathematical formulation, network
flow algorithms and linear programming simplex approaches will be
presented.
Programma
- Problemi e modelli (12 ore)
- La Ricerca Operativa: formulazione e risoluzione di problemi.
- Problemi decisionali, problemi di ottimizzazione e di esistenza.
- Uso di variabili (logiche, discrete, continue, a valori prefissati, ...).
- Formalizzazione di relazioni e vincoli (relazioni logiche,
assegnazione di elementi, selezione di sottoinsiemi, vincoli di
soglia, ...).
- Rappresentazione di funzioni (funzioni con carico fisso,
funzioni lineari a tratti, funzioni di soglia, ...).
- Grafi e reti di flusso (12 ore)
- Introduzione ai problemi di flusso su rete.
- Algoritmi di visita di un grafo.
- Il problema dell'albero dei cammini minimi: proprietà e algoritmi.
- Il problema dell'albero di copertura ottimo: proprietà e algoritmi.
- Il problema del flusso massimo: proprietà e algoritmi.
- Programmazione Lineare (18 ore)
- Coppie di problemi duali e relazioni tra problema primale e
problema duale.
- Geometria della programmazione lineare.
- Vincoli attivi e non attivi, direzioni, direzioni ammissibili e/o
di crescita; lemma di Farkas.
- Teoria matematica della dualità; teorema forte della
dualità e teorema degli scarti complementari.
- Basi complementari, considerazioni geometriche; algoritmi del
simplesso primale e del simplesso duale.
- Tecniche della programmazione lineare per problemi di flusso.
- Riottimizzazione ed analisi parametrica.
Bibliografia
- G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M.G. Scutellà, Appunti del corso.
- F.S. Hillier, G.J. Lieberman, "Introduction to Operations
Research", McGraw Hill (1990).
- R.K. Ahuja, T.L. Magnanti, J.B. Orlin, "Network Flows: theory,
algorithms, and applications", Prentice-Hall (1993).
Modalità di esame
Scritto e orale.