Ricerca Operativa - Corso B
a.a. 2021/2022
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 dell'albero di copertura di costo minimo
- Il problema del flusso massimo
- Il problema del flusso 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
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)
Testo di riferimento
- G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G.
Scutellą, Appunti di Ricerca Operativa, SEU - Servizio Editoriale Universitario di Pisa (PDF)
Parti degli appunti non incluse nel programma del corso
Sezione aggiornata periodicamente durante lo svolgimento del corso (ultimo aggiornamento: 7/9/2021)
- - -
1.2.3
1.2.10.1
1.2.11
1.2.12
- - -
- - -
2.3.7
2.4.3
2.5.3
2.5.4
2.6.3
2.6.4
- - -
- - -
- - -
3.3.3
|
Algoritmi approssimati (pp. 6)
Relazioni logiche
Minima distanza
Funzioni lineari a tratti
Vincoli disgiuntivi
Algoritmi a coda di prioritą: Heap binario (pp. 79-80)
Algoritmi a selezione su lista: Liste a doppio ingresso (pp. 81-83)
Cammini minimi con radici multiple
Albero di copertura bottleneck
Algoritmo basato su preflussi
Flusso massimo con pił sorgenti/pozzi
Algoritmo basato su cancellazione di cicli
Basi di cicli
Interpretazione economica degli scarti complementari (pp. 160-163)
Individuazione di una base primale ammissibile (pp. 179-182)
Individuazione di una base duale ammissibile (pp. 188-189)
Analisi post-ottimale
|
|---|
Altri testi di consultazione
- R.K. Ahuja, T.L. Magnanti, J. Orlin, Network flows. Theory, algorithms and applications, Prentice Hall, 1993
- M. Pappalardo, M. Passacantando, Ricerca operativa, Pisa University Press, 2012
- P. Serafini, Ottimizzazione, Zanichelli, 2000
- C. Vercellis, Modelli e decisioni, Progetto Leonardo, 1999
- C. Vercellis, Ottimizzazione. Teoria, metodi, applicazioni, McGraw Hill, 2008