RICERCA OPERATIVA
cod. 1008094

Anno accademico 2021/22
1° anno di corso - Primo semestre
Docente
Marco LOCATELLI
Settore scientifico disciplinare
Ricerca operativa (MAT/09)
Ambito
A scelta dello studente
Tipologia attività formativa
A scelta dello studente
72 ore
di attività frontali
9 crediti
sede:
insegnamento
in ITALIANO

Obiettivi formativi

Proporre un percorso che, partendo dalla semplice analisi dei reali problemi applicativi fornisca allo studente la capacità di applicare le tecniche di modellizzazione e di risoluzione di problemi di programmazione matematica (in particolare, programmazione lineare continua e intera) per definire ed individuare appropriate soluzioni la risoluzione, tramite gli strumenti della programmazione matematica,per realizzare applicazioni che li risolvano progettando modelli e appropriate tecniche risolutive.

Il corso prevede, oltre a lezioni teoriche, che esercitazioni, queste ultime saranno arricchite da casi di studio con programmi sviluppati in classe con l’ausilio del docente.

Con riferimento agli Indicatori di Dublino:
Conoscenza e capacità di comprensione

Il corso si focalizza sulla conoscenza delle tecniche di modellizzazione fondamentali con particolare enfasi allo studio di appropriate soluzioni per realizzare applicazioni e progettazioni di metodi risolutivi. Il testo di riferimento è in lingua inglese, che facilità l’avviamento alla consultazione di letteratura scientifica internazionale.

Capacità di applicare conoscenza e comprensione

Le conoscenze teoriche presentate vengono sempre applicate alla risoluzione di problemi specifici. Le esercitazioni che affiancano il corso sono incentrate sulla risoluzione di esercizi e problemi. Spesso i metodi risolutivi vengono presentati sotto forma algoritmica e talvolta anche mediante un linguaggio naturale come lo pseudocodice, sviluppando negli studenti la capacità di strutturare procedure utili in numerose per la definizione di tecniche risolutive.
Autonomia di giudizio
Gli esercizi, che vengono proposti relativamente alla parte teorica svolta a lezione, possono venire risolti individualmente o in gruppo. Il confronto con i compagni di corso, nel lavoro a casa o durante gli svolgimenti in aula, favorisce lo sviluppo di capacità specifiche per poter a chiarire ai compagni o ai docenti le proprie argomentazioni. Spesso gli esercizi proposti possono venire risolti in modi molto diversi e l'ascolto delle soluzioni proposte da altri permette di sviluppare la capacità di individuare strutture comuni, al di là delle apparenti differenze superficiali.

Abilità comunicative
Le numerose discussioni sui diversi metodi per risolvere i problemi proposti consentono di migliorare le capacità di comunicazione. Vengono inoltre abitualmente utilizzate durante le spiegazioni (ed esplicitamente evidenziate in classe) alcune modalità di comunicazione specifiche dell’analisi algoritmica.

Capacità di apprendimento

Lo studio delle origini delle soluzioni matematiche e la loro introduzione motivata da considerazioni quantitative contribuisce a realizzare negli studenti la capacità di apprendere in modo profondo e non soltanto superficiale e ripetitivo. Le conoscenze così acquisite non sono mai rigide e definitive, ma sono perfettamente adattabili ad ogni evoluzione e cambiamento di prospettiva e di contesto.

Prerequisiti

Nozioni di base di algebra lineare e analisi

Contenuti dell'insegnamento

I. Programmazione Matematica

II. Classi di Complessità Computazionale

III. Programmazione Lineare (PL)

IV. Duale di un problema di programmazione lineare

V. Programmazione Lineare Intera (PLI)

VI. Formulazione e risoluzione di problemi di PL con AMPL

VII. Problemi di Flusso su Reti e Problemi su Grafi

VIII. Metodi di soluzione: Metodi Esatti e non.

Programma esteso

Programmazione matematica, esempi applicativi.
Definizione Programmazione Lineare e non Lineare

Classi di Complessità Computazionale: classe P e sue proprietà; classe NP e sue proprietà; classe NP-hard e sue proprietà; classe NP-complete e sue proprietà; classe fortemente NP-complete e sue proprietà.

Programmazione Lineare (PL):
Introduzione alla PL e formulazione di un problema di PL;Geometria di un problema di PL continuo; Metodo del Simplesso. Metodo delle due Fasi e metodo del Big-M.


Duale di un problema di programmazione lineare :
Proprietà della dualità; Scarti complementari; Algoritmo del simplesso duale; Analisi di Sensitività



Programmazione Lineare Intera (PLI): Introduzione alla PLI; Rilassamento Lineare; Speciali problemi di PLI con matrice dei vincoli unimodulare: il Problema del Trasporto, metodo dell’angolo Nord Ovest e Regola del Ciclo; il Problema dell’Assegnamento;

Formulazione e risoluzione di problemi di PL con AMPL

Problemi di Flusso su Reti e Problemi su Grafi: Massimo Flusso; Flusso a costo minimo; Ford-Fulkerson e cammini aumentanti; Definizione di Taglio; Taglio minimo; il Problema del Vertex Cover Minimo; il Problema dell’Albero di Copertura Minimo; Algoritmo di Kruskal e Prim; Problemi di Cammino Minimo; Algoritmo di Dijkstra;


Metodi di soluzione: Metodi Esatti: Branch & Bound; Column Generation, Piani di Taglio, Programmazione Dinamica; Metodi di Approssimazione; Metodi Euristici e Metaeuristici; il Problema dello Zaino 0/1e il Problema dello Zaino Frazionario.

Bibliografia

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008

Metodi didattici

La principale modalita' di trasmissione della conoscenza e' la lezione frontale, durante la quale si cerca di coinvolgere gli studenti per portarli da soli alle conclusioni. Sono previste anche esercitazioni per consolidare quanto visto nelle lezioni. Non sono previste attivita' di laboratorio ma e' previsto un progetto di ricerca da svolgere a casa, eventualmente insieme ad altri.

Modalità verifica apprendimento

L'esame scritto è composto da esercizi e domande di teoria che incidono allo stesso modo sulla votazione finale. L'esame orale è previsto solo su richiesta dello studente.

Viene anche richiesto allo studente di lavorare a casa su un progetto, proposto dal docente o suggerito dallo studente stesso, in cui deve sviluppare tutte le fasi di lavoro del ricercatore operativo: traduzione del problema reale in un modello matematico, traduzione del modello in linguaggio AMPL, scelta di un opportuno solver, analisi della soluzione restituita dal solver
e sensitivita' della soluzione ottenuta rispetto a perturbazioni dei dati. Il lavoro eseguito deve essere riportato in una relazione che viene poi discussa con il docente.

Altre informazioni

- - -

Obiettivi agenda 2030 per lo sviluppo sostenibile

- - -