| | | corso | | | | |
Ricerca operativa A
Codice: | AA014 | Crediti: | 6 | Semestre: | 2 | Sigla: | RO | |
|
Settore disciplinare: | MAT/09 - Ricerca Operativa |
Docente
Prerequisiti
La conoscenza dei contenuti dei corsi AA001 “Analisi Matematica”, AA005 “Algebra” e AA006
“Algoritmica” è 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.
Programma
Introduzione (2 ore)
- Problemi decisionali, problemi di ottimizzazione ed esistenza;
- Classi di problemi; alcuni esempi.
Modelli e loro formulazione (12 ore)
- Tipi di variabili: logiche, continue, discrete;
- Formulazione di vincoli;
- Formulazione della funzione obiettivo.
Grafi e reti di flusso (16 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.
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
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.