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
- - -
