B024345 - OTTIMIZZAZIONE SU RETI DI FLUSSO

Italiano

Introduzione ai modelli di ottimizzazione su grafo. Modelli e algoritmi per problemi di flusso su grafo, progettazione di reti, problemi di trasporto e instradamento dei veicoli. Robustezza.

Network flows: theory, algorithms, and applications
Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, Prentice Hall, 1993

Spreadsheet Modeling and Decision Analysis
Cliff T. Ragsdale, Fourth Edition, International Student Edition, 2004


Integer Programming
Laurence A. Wolsey, John Wiley & Sons, 1998

1) Conoscenza di modelli e algoritmi per problemi di ottimizzazione su grafo.
2) Capacità di formulare problemi di ottimizzazione su grafo.
3) Capacità di riconoscere la struttura di un problema.
4) Capacità di applicare e adattare, a specifici contesti applicativi, algoritmi standard di ottimizzazione su grafo.

Conoscenze di base di algebra lineare

Didattica frontale

Prova orale attraverso la quale si verifica mediante quesiti e domande teoriche:
- la capacità di formulare problemi di ottimizzazione su rete;
- la capacità di descrivere e utilizzare algoritmi di ottimizzazione su rete;
- la capacità di adattare modelli e algoritmi di ottimizzazione su rete per la soluzione di problemi complessi previa identificazione della loro struttura di rete.

Programma del corso di Ottimizzazione su reti di flusso

Introduzione (2h)
• Struttura e funzionamento dei sistemi di produzione e distribuzione: la catena logistica (cenni), obiettivi di gestione

Logistica distributiva: problemi di trasporto (routing) (32 h)
• il problema del percorso ottimo singola origine – singola destinazione (cammino minimo): costi non negativi e costi arbitrari
• il problema di instradamento dei flussi a costo minimo (origini e destinazioni multiple, vincoli di capacità, flussi multipli)
• il problema dell’albero di copertura di costo minimo
• il problema del commesso viaggiatore o sequenziamento ottimo
• il problema di instradamento di una flotta di veicoli (Vehicle Routing Problem)

Progetto di reti (4h)
• Dimensionamento di capacità
• Problemi congiunti di localizzazione e trasporto

Gestione dei progetti (4h)
• Il caso di attività con durata deterministica: il metodo del cammino critico (CPM)
• Gestione della variabilità delle durate: PERT

Problemi di schedulazione e sequenziamento (12h)
• Il problema su singola macchina: minimizzazione del tempo di completamento, minimizzazione del massimo ritardo
• Il problema di flow shop (le macchine sono visitate nello stesso ordine da tutti i job)
• Il problema di job shop (arbitrarietà dell’ordine di visita delle macchine per i job)

Le reti come strumento metodologico per la risoluzione di problemi complessi (18 h)
• Euristiche di ricerca locale: tabu-search, simulated annealing, algoritmi genetici, multi-exchange
• Rilassamento Lagrangiano come metodo di decomposizione: applicazione al caso del problema del commesso viaggiatore e all’instradamento di diverse tipologie di flussi (problema di flusso multicommodity)
• Alberi decisonali ed approcci enumerativi
• Gestione della robustezza (cenni)