INFORMAZIONI SU

Ricerca operativa (insegnamento mutuato dal cdl magistrale in Informatica)

Programma dell'insegnamento di Ricerca operativa - cdl magistrale in Ingegneria Gestionale (mutuato dal cdl magistrale in Informatica)

Docente

prof. Paolo SERAFINI

Crediti

6 CFU

Lingua

Italiano

Obiettivi formativi specifici

Il Corso presenta ed approfondisce tecniche matematiche di base all'analisi di problemi. Si fa richiamo a competenze precedenti di programmazione (i ragazzi conoscono il C), si introducono alcune nozioni di informatica, e si adotta ed indica un approccio algoritmico ed operativo. Il Corso illustra le principali tecniche di problem solving mentre propone e studia diversi modelli matematici adatti ad ospitare problematiche di tipo gestionale delle risorse. Ci si pone come obbiettivo il ravvivare ed il rafforzare la consuetudine ad un'analisi di tipo matematico dei problemi, la conoscenza di alcuni modelli e strumenti offerti dalla Ricerca Operativa, e la consapevolezza dei punti di forza e di debolezza in merito alle soluzioni offerte da un modello o da un software, e/o di fatto ottenibili in linea di principio.

Competenze acquisite

Non evidenziate

Programma
(48 ore complessive)

Introduzione alla programmazione lineare: modellizzazione, identificazione delle grandezze, dei vincoli e degli obiettivi; ottimi di Pareto; esempio della dieta, modello di programmazione lineare; analisi di sensibilità; identificazione di ulteriori obiettivi; frontiera efficiente;  vincoli di interezza.
Proprietà della programmazione lineare: struttura geometrica; vertici e soluzioni di base; problema duale; complementarità; cenni del metodo del simplesso; metodo branch-and-bound per variabili intere.
Modelli di percorsi: programmazione Dinamica; principio di ottimalità; equazione ricorsiva; cammini minimi (Bellman-Ford, Dijkstra, Floyd-Warshall).
Modelli di percorsi con capacità: cammini minimi con capacità, reti di flusso; flussi di costo minimo; massimo flusso; minimi tagli; esempi di applicazione dei flussi, assegnazione seggi elettorali.
Modelli di percorsi con vincoli sui nodi o sugli archi: problema del commesso viaggiatore (formulazione con piani di taglio); circuiti Euleriani; minimi alberi di supporto (Kruskal e Prim).
Modelli di allocazione: assegnamento; accoppiamento; esempi di applicazioni ad eventi sportivi; knapsack; bin packing; modelli di turnazione; generazione di colonne, cutting stock, massimo flusso; vehicle routing problems.
Schedulazione: schedulazione a risorsa infinita, PERT; schedulazione a risorsa finita, problemi a una macchina, macchine parallele, flow-shop, job-shop e open-shop; schedulazione periodica.

Bibliografia

- Paolo Serafini, Ricerca Operativa, Springer, 2009.
- Paolo Serafini, Ottimizzazione, Zanichelli, Bologna 2000.
- L. Schrage, LINDO: An optimization modeling system, Palo Alto Scientific Press, 1991

Modalità d'esame

prova orale, con la possibilità di presentare e discutere un progetto

Il piano dettagliato delle lezioni si trova alla pagina