Ricerca Operativa - Corso A
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 tre grandi
classi di problemi di ottimizzazione: problemi di flusso su reti,
di programmazione lineare e di programmazione lineare intera.
PROGRAMMA DEL CORSO
- Problemi decisionali e problemi di ottimizzazione
- Classi di problemi ed esempi
-
Modelli e loro formulazione (6 ore)
- Tipi di variabili: quantitative, 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 del flusso massimo
- Il problema del flusso di costo minimo
- Il problema dell'albero di copertura di costo minimo
Programmazione Lineare (16 ore)
- Geometria della programmazione lineare e teorema fondamentale
- Dualità e scarti complementari
- Basi: complementarità, degenericità ed ottimalità
- Algoritmi del simplesso primale e duale
- Introduzione all'algoritmo del simplesso su reti
Programmazione Lineare Intera (8 ore)
- Metodi poliedrali: tagli ed algoritmo di Gomory
- Metodi enumerativi: l'algoritmo "Branch&Bound"
- Implementazioni ad-hoc per i problemi dello zaino e del commesso viaggiatore
(Le ore indicate includono le esercitazioni)