RICERCA OPERATIVA
Anno accademico 2018/2019 - 1° anno - Curriculum APPLICATIVO- METODI E MODELLI DI OTTIMIZZAZIONE: Patrizia DANIELE
- OTTIMIZZAZIONE SU RETI: Patrizia DANIELE
Organizzazione didattica: 300 ore d'impegno totale, 206 di studio individuale, 70 di lezione frontale, 24 di esercitazione
Semestre: 1° e 2°
Obiettivi formativi
- METODI E MODELLI DI OTTIMIZZAZIONE
Gli obiettivi del corso di Metodi e Modelli di Ottimizzazione sono i seguenti:
- determinare cammini di lunghezza minima e massima a partire da un nodo radice;
- applicare i concetti di derivate generalizzate alle funzioni;
- applicare la teoria lagrangiana ai problemi di ottimizzazione vincolata;
- affrontare la teoria della dualità.
Conoscenza e capacità di comprensione (knowledge and understanding):
Alla fine del corso di Metodi e Modelli di Ottimizzazione, lo studente, avrà acquisito le conoscenze e le capacità di base nell’ambito dell'ottimizzazione e della modellizzazione matematica e dimostrerà di:
- riconoscere problemi di ottimizzazione vincolata
- essere in grado di formulare poroblemi concreti in termini matematici
- possedere conoscenze e capacità di comprensione di testi.
Capacità di applicare conoscenza e comprensione (applying knowledge and understanding):
Le conoscenze teoriche e pratiche acquisite durante il corso permetteranno allo studente di:
- individuare le caratteristiche funzionali dei dati forniti;
- analizzare criticamente varie situazioni aziendali;
- proporre soluzioni ottimali a problemi complessi;
- identificare l'essenza di un problema e applicare principi generali a casi specifici.
Autonomia di giudizio (making judgements):
Lo studente, in virtù della formazione acquisita, anche di tipo analitico-quantitativo, sarà in grado di analizzare ed interpretare criticamente i dati forniti.
Abilità comunicative (communication skills):
Alla fine del corso di Metodi e Modelli di Ottimizzazione lo studente sarà in grado di:
- trasmettere la propria esperienza e conoscenza ad altri;
- confrontarsi con gli altri, specialmente nell'elaborazione di progetti in cui si lavora in gruppo.
Capacità di apprendimento (learning skills):
- Lo studente avrà acquisito capacità di apprendere, anche in modo autonomo, ulteriori conoscenze sui problemi di ottimizzazione. Tali capacità gli consentiranno di affrontare e risolvere problemi concreti.
- OTTIMIZZAZIONE SU RETI
Gli obiettivi del corso di Network e Supernetwork sono i seguenti:
- determinare cammini di lunghezza minima e massima a partire da un nodo radice;
- formulare problemi di equilibrio del traffico nel caso dinamico in termini di reti, introducendo anche vincoli di capacità, vincoli aggiuntivi e termini di ritardo;
- valutare l'importanza delle singole componenti di una rete;
- costruire una rete a più livelli per problemi di produzione e distribuzione merci, per reti elettriche e nel caso di fusione tra aziende;
- applicare i modelli teorici a realtà aziendali.
Conoscenza e capacità di comprensione (knowledge and understanding):
Alla fine del corso di Network e Supernetwork, lo studente, oltre ad aver acquisito le conoscenze e le capacità di base nell’ambito dell'ottimizzazione e della modellizzazione matematica, dimostrerà di:
- saper trasformare situazioni reali di massimizzazione di profitti, minimizzazione di costi e di rischi,... in modelli matematici;
- possedere conoscenze e capacità di comprensione di testi.
Capacità di applicare conoscenza e comprensione (applying knowledge and understanding):
Le conoscenze teoriche e pratiche acquisite durante il corso permetteranno allo studente di:
- analizzare criticamente varie situazioni aziendali;
- proporre soluzioni ottimali a problemi complessi;
- identificare l'essenza di un problema e applicare principi generali a casi specifici.
Autonomia di giudizio (making judgements):
Lo studente, in virtù della formazione acquisita, anche di tipo analitico-quantitativo, sarà in grado di analizzare ed interpretare criticamente i dati forniti.
Abilità comunicative (communication skills):
Alla fine del corso di Network e Supernetwork lo studente sarà in grado di:
- trasmettere la propria esperienza e conoscenza ad altri;
- confrontarsi con gli altri, specialmente nell'elaborazione di progetti in cui si lavora in gruppo.
Capacità di apprendimento (learning skills):
-
Lo studente avrà acquisito capacità di apprendere, anche in modo autonomo, ulteriori conoscenze sui problemi di matematica applicata. Tali capacità gli consentiranno di affrontare e risolvere problemi concreti di ottimizzazione.
Modalità di svolgimento dell'insegnamento
- METODI E MODELLI DI OTTIMIZZAZIONE
L'insegnamento verrà svolto mediante lezioni frontali, esercitazioni in aula e presso i laboratori informatici e seminari.
- OTTIMIZZAZIONE SU RETI
L'insegnamento verrà svolto mediante lezioni frontali, esercitazioni in aula e presso i laboratori informatici e seminari.
Prerequisiti richiesti
- METODI E MODELLI DI OTTIMIZZAZIONE
Sono richiesti i concetti di base dell'Analisi Matematica I e II (differenziabilità, convessità di insiemi e funzioni, topologia, ...), della Ricerca Operativa (concetto di rete e di disequazione variazionale) e dell'Ottimizzazione (problemi di minimo, sottodifferenziali,...)
- OTTIMIZZAZIONE SU RETI
Sono richiesti i concetti di base dell'Algebra Lineare (vettori e matrici), dell'Analisi Matematica I e II (differenziabilità, convessità di insiemi e funzioni, topologia, ...) e della Ricerca Operativa (concetto di rete e di disequazione variazionale).
Frequenza lezioni
- METODI E MODELLI DI OTTIMIZZAZIONE
La frequenza è fortemente consigliata
- OTTIMIZZAZIONE SU RETI
La frequenza è fortemente consigliata
Contenuti del corso
- METODI E MODELLI DI OTTIMIZZAZIONE
Teoria dei grafi (circa 12 ore):
Digrafi e grafi: definizioni e nozioni preliminari. Rappresentazione mediante matrici. Algoritmo di Kruskal e sua variante. Algoritmo di Dijkstra e sua variante. Algoritmo di Ford. Ordinamento in livelli dei nodi in un digrafo privo di circuiti. Algoritmo di Bellmann-Kalaba. Il problema del commesso viaggiatore.
Derivate generalizzate (circa 10 ore)
Derivate direzionali. Derivate di Gâteaux e di Fréchet. Sottodifferenziali
Metodi risolutivi (circa 8 ore)
Metodo del sottogradiente, metodo di discretizzazione.
Condizioni di ottimalità (circa 10 ore)
Lemma di Farkas. Problemi di ottimo vincolato. Condizioni di Karush-Kuhn-Tucker. Teoria della dualità.
Applicazioni (circa 7 ore):
Esempi di problemi concreti formulati in termini di ottimo vincolato.
- OTTIMIZZAZIONE SU RETI
Teoria dei grafi (circa 12 ore):
Digrafi e grafi: definizioni e nozioni preliminari. Rappresentazione mediante matrici. Algoritmo di Kruskal e sua variante. Algoritmo di Dijkstra e sua variante. Algoritmo di Ford. Ordinamento in livelli dei nodi in un digrafo privo di circuiti. Algoritmo di Bellmann-Kalaba. Il problema del commesso viaggiatore.
Networks (circa 25 ore):
- Traffico su reti nel caso statico: presentazione del modello; principio di Wardrop; vincoli di capacità. Traffico su reti nel caso dinamico: presentazione del modello; condizioni di equilibrio; formulazione variazionale; teoremi di esistenza; modello con vincoli aggiuntivi. Modello di traffico su reti con termini di ritardo. Derivata direzionale: definizione e proprietà. Sottodifferenziale di una funzione convessa: definizione e proprietà. Metodo del sottogradiente, metodo di discretizzazione. Il paradosso di Braess nel caso statico: modello con costi di percorrenza. Il paradosso di Braess nel caso dinamico: modello con costi di percorrenza. Misura dell'efficienza di una rete di traffico: la misura secondo Latora-Marchiori e la misura secondo Nagurney-Qiang. Importanza delle singole componenti di una rete. Applicazioni alla rete di Braess e alla rete di Braess doppia. Individuazione di elementi critici nelle reti.
- Reti di mercati economici spazialmente distribuiti nel caso statico in presenza di eccessi di produzione e di richiesta. Formulazione variazionale. Teoria Lagrangiana.
- Reti di catene di offerte: la fusione orizzontale di aziende. Presentazione dei modelli prima e dopo le fusioni; problemi di ottimizzazione associati; misura del vantaggio strategico associato alle fusioni orizzontali. Modelli di reti di catene di offerte con interessi ambientali.
- Disequazioni variazionali per problemi di vendita all’asta: presentazione del modello, condizione di equilibrio e caratterizzazione mediante formulazione variazionale.
Supernetworks (circa 35 ore):
- Reti a strati con tre livelli di decisionisti: modello economico in presenza di produttori, dettaglianti e consumatori con commercio elettronico; condizioni di ottimalità e caratterizzazione mediante disequazione variazionale per i rappresentanti di ogni livello; stato di equilibrio e formulazione variazionale per l’intera catena di offerte. Caso dinamico: modello con eccessi di produzione e di richiesta.
- Reti di catene di offerte nel caso di bisogni critici con sorgenti esterne: modello con sanzioni per la carenza o l’eccesso di offerta ai punti di domanda. Problema di ottimizzazione e formulazione variazionale.
- Catene di offerte per alimenti: condizioni di ottimalità e formulazione variazionale.
- Reti di catene di fornitura di energia elettrica: presentazione del modello con produttori di energia elettrica, fornitori di energia, fornitori di servizi di trasmissione e mercati di domanda; condizioni di ottimalità e caratterizzazione mediante disequazione variazionale per i rappresentanti di ogni livello; stato di equilibrio e formulazione variazionale per l'intera rete. Presentazione del modello con fornitori di combustibile non rinnovabile e condizioni di ottimalità.
- Reti di catene di offerte a ciclo chiuso con riciclo di materiali: catena diretta e catena inversa. Comportamento dei fornitori di materiale grezzo, dei produttori, dei dettaglianti, dei mercati di domanda, dei centri di recupero. Formulazione variazionale.
- Il modello del crimine informatico nei servizi finanziari.
Testi di riferimento
- METODI E MODELLI DI OTTIMIZZAZIONE
- L. Daboni, P. Malesani, P. Manca, G. Ottaviani, F. Ricci, G. Sommi, “Ricerca Operativa”, Zanichelli, Bologna, 1975.
- P. Daniele, “Dynamic Networks and Evolutionary Variational Inequalities", Edward Elgar Publishing, 2006.
- J. Jahn, "Introduction to the Theory of Nonlinear Optimization", Springer, 1996.
- Dispense su STUDIUM
- OTTIMIZZAZIONE SU RETI
- L. Daboni, P. Malesani, P. Manca, G. Ottaviani, F. Ricci, G. Sommi, “Ricerca Operativa”, Zanichelli, Bologna, 1975.
- P. Daniele, “Dynamic Networks and Evolutionary Variational Inequalities", Edward Elgar Publishing, 2006.
- A. Nagurney, J. Dong, "Supernetworks", Edward Elgar Publishing, 2002.
- Dispense su STUDIUM
Programmazione del corso
METODI E MODELLI DI OTTIMIZZAZIONE | |||
Argomenti | Riferimenti testi | ||
---|---|---|---|
1 | Cammini di lunghezza minima e massima | 1 | |
2 | Proprietà delle derivate generalizzate | 3 | |
3 | Il sottodifferenziale di una funzione e sue proprietà | 3 | |
4 | Il lemma di Farkas | 4 | |
5 | I moltiplicatori di Lagrange | 3 | |
6 | Le condizioni KKT | 3 | |
7 | Dualità debole e forte | 3 | |
8 | Alcune applicazioni | 2 | |
OTTIMIZZAZIONE SU RETI | |||
Argomenti | Riferimenti testi | ||
1 | Algoritmi su grafi o digrafi | 1 | |
2 | Il problema del commesso viaggiatore | 4 | |
3 | Reti di traffico nel caso statico in presenza di vincoli di capacità | 2 | |
4 | Reti di traffico nel caso dinamico | 2 | |
5 | Il modello del traffico con vincoli aggiuntivi | 2 | |
6 | Il modello del traffico con termini di ritardo | 2 | |
7 | Il metodo del sottogradiente | 2 | |
8 | Il metodo di discretizzazione | 2 | |
9 | La misura dell'efficienza di una rete di traffico e l'importanza delle singole componenti | 4 | |
10 | La fusione tra due aziende con e senza interessi ambientali | 4 | |
11 | Il modello matematico della vendita all'asta | 4 | |
12 | Supernetwork con tre livelli di decisionisti | 3 | |
13 | Reti di catene di offerte nel caso di bisogni critici con sorgenti esterne | 4 | |
14 | Reti di catene di fornitura di energia elettrica con e senza i fornitori di combustibile non rinnovabile | 4 | |
15 | Reti di catene di offerte a ciclo chiuso con riciclo di materiali | 4 |
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
- METODI E MODELLI DI OTTIMIZZAZIONE
Alla fine del modulo di Metodi e Modelli di Ottimizzazione è prevista una prova in itinere, che si svolgerà nel mese di febbraio. Superata tale prova, lo studente acquisisce 6CFU.
Se lo studente non supera la prova in itinere, allora dovrà sostenere l'esame finale.
Durante il corso sono anche previsti dei seminari di approfondimento tenuti dagli studenti stessi.
L'esame finale consiste in una prova orale durante la quale il candidato dimostra di aver assimilato gli argomenti trattati nel corso.
- OTTIMIZZAZIONE SU RETI
Non sono previste prove in itinere. Durante il corso sono anche previsti dei seminari di approfondimento tenuti dagli studenti stessi.
L'esame finale consiste in una prova orale durante la quale il candidato dimostra di aver assimilato gli argomenti trattati nel corso.
Esempi di domande e/o esercizi frequenti
- METODI E MODELLI DI OTTIMIZZAZIONE
Esempi di domande:
Presentare l'algoritmo per il cammino di lunghezza minima in un grafo.
Presentare il metodo del sottogradiente.
Presentare il metodo di discretizzazione.
Dimostrare le proprietà delle derivate generalizzate.
Dimostrare il lemma di Farkas.
Dimopstrare le condizioni KKT.
Dimostrare il teorema di dualità debole.
- OTTIMIZZAZIONE SU RETI
Esempi di domande:
Presentare un algoritmo su grafi o digrafi
Presentare il problema del commesso viaggiatore.
Caratterizzare il principio di Wardrop in presenza di vincoli di capacità.
Presentare le condizioni di equilibrio di una rete dinamica del traffico.
Presentare il modello del traffico con vincoli aggiuntivi.
Presentare il modello del traffico con termini di ritardo.
Presentare il metodo del sottogradiente.
Presentare il metodo di discretizzazione.
Definire la misura dell'efficienza di una rete di traffico.
Presentare il modello di fusione tra due aziende con e senza interessi ambientali.
Presentare il modello matematico della vendita all'asta.
Presentare le reti a strati con tre livelli di decisionisti.
Esaminare il comportamento dei produttori.
Presentare le reti di catene di offerte nel caso di bisogni critici con sorgenti esterne.
Presentare le reti di catene di fornitura di energia elettrica con e senza i fornitori di combustibile non rinnovabile.
Presentare le reti di catene di offerte a ciclo chiuso con riciclo di materiali ed esaminare il comportamento dei centri di recupero.