logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2018/2019
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 098474 - METODI DI OTTIMIZZAZIONE DELLA RICERCA OPERATIVA
Docente Fumero Francesca
Cfu 10.00 Tipo insegnamento Monodisciplinare

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (1 liv.)(ord. 270) - BV (394) INGEGNERIA GESTIONALE*CIH098474 - METODI DI OTTIMIZZAZIONE DELLA RICERCA OPERATIVA

Obiettivi dell'insegnamento

L’insegnamento si inserisce all’interno del percorso degli studi perseguendo alcuni degli obiettivi generali di apprendimento dichiarati. In particolare, l’insegnamento contribuisce allo sviluppo delle capacità di:

  • Comprendere i principi scientifici ed ingegneristici fondamentali e la loro declinazione nelle principali tecnologie adottate in impresa

  • Progettare soluzioni applicando l’approccio scientifico ed ingegneristico (apprendimento, ragionamento e modellizzazione basati su una solida preparazione multidisciplinare) nell’affrontare problemi ed opportunità in ambito aziendale ed industriale

 

Nello specifico l’insegnamento si propone di portare lo studente a

  • Conoscere le teorie e i metodi dell’ottimizzazione e comprendere i principi fondamentali della modellizzazione matematica dei sistemi reali
  • Saper progettare e applicare con rigore scientifico modelli di ottimizzazione per risolvere problemi decisionali che si presentano in ambito aziendale e industriale.

Risultati di apprendimento attesi

Al termine della frequenza dell'insegnamento e del superamento dell'esame lo studente

- conosce i principi base della teoria dell'ottimizzazione lineare continua ed intera, dell'ottimizzazione su reti, e dell'ottimizzazione nei sistemi stocastici

- conosce le principali tecniche risolutive e gli algoritmi tradizionalmente utilizzati per risolvere i problemi nei contesti citati al punto precedente

- è in grado di comprendere e interpretare la formulazione di un modello di ottimizzazione matematica

- ha sviluppato un'autonoma capacità di analizzare un problema reale, riconducendolo ad una precisa tassonomia, ed è in grado di applicare le conoscenze teoriche acquisite per formulare specifici modelli adatti al contesto considerato

- è in grado di identificare metodi e algoritmi risolutivi per i problemi definiti e di applicarli utilizzando software opportuni per la loro soluzione

- è in grado di comprendere e interpretare le soluzioni ottenute per trasformarle in indicazioni operative efficaci per la risoluzione di problemi aziendali complessi

 


Argomenti trattati

   1. Modelli di ottimizzazione

Modelli matematici per le decisioni; fasi di sviluppo di un modello. Modelli di ottimizzazione; modelli di ottimizzazione matematica; ottimizzazione vincolata; ottimizzazione multi-obiettivo con e senza priorità; superfici di livello; algoritmi iterativi di ottimizzazione; cenni alla complessità degli algoritmi.

2. Modelli di ottimizzazione lineare

Applicazioni dell'ottimizzazione lineare: mix produttivo, dieta, miscelazione, trasporto, pianificazione produttiva multi-periodo, selezione del portafoglio, regressione, classificazione. Formulazioni di ottimizzazione lineare: forma generale, standard, mista; equivalenza tra formulazioni: variabili di scarto e variabili surplus; assunzioni dell'ottimizzazione lineare; ammissibilità, illimitatezza, ottimalità.

3. Geometria dell'ottimizzazione lineare

Geometria convessa: rappresentazione dei vincoli e della funzione obiettivo; poliedri, vertici, punti estremi, facce; soluzioni di base e loro numerosità; equivalenza tra punti estremi, vertici, e soluzioni di base ammissibili; degenerazione; soluzioni di base nello spazio dei vincoli; soluzioni di base per problemi in forma generale e per variabili limitate; caratterizzazione delle soluzioni ottimali; soluzioni ottimali multiple; problemi inammissibili e illimitati; vincoli attivi, inattivi e ridondanti; teorema fondamentale dell'ottimizzazione lineare.

4. Algoritmo del simplesso

Geometria del simplesso nello spazio delle variabili; condizioni di ottimalità; direzioni ammissibili e algoritmo del simplesso; generica iterazione dell'algoritmo (fase II): condizioni di illimitatezza e cambio di base; ricerca di una soluzione ammissibile iniziale (fase I). Tableau del simplesso; convergenza dell'algoritmo, degenerazione e regole anticiclaggio; estensione al caso di variabili limitate; complessità dell'algoritmo; simplesso nello spazio dei vincoli.

5. Dualità

Interpretazione economica della dualità: duali di mix produttivo, dieta e trasporto; problemi lineari duali e relative trasformazioni; mutue relazioni tra primale e duale: teoremi di dualità debole e di dualità forte; condizioni degli scarti complementari; motivazioni algoritmiche della teoria della dualità.

6. Analisi di sensitività e parametrica

Analisi di sensitività: significato geometrico; variazioni nella funzione obiettivo; variazioni nel termine noto. Analisi parametrica rispetto al termine noto: andamento locale e globale della curva del valore ottimo, analisi grafica e interpretazione economica; analisi parametrica rispetto ai coefficienti di costo: andamento globale della curva del valore ottimo. Prezzi ombra: definizione, interpretazione economica e loro legame con i coefficienti di costo ridotto; aggiunta di una nuova variabile; nozione di costo opportunità; interpretazione del report del simplesso.

7. Ottimizzazione intera

Applicazioni dell'ottimizzazione intera: knapsack e capital budgeting, pianificazione produttiva con lotti minimi e con costi fissi, localizzazione di impianti, scheduling, vincoli either-or e disgiuntivi, covering, packing e partitioning, assegnazione. Proprietà dell'ottimizzazione intera: rilasciamenti, geometria dell'ottimizzazione intera, formulazioni alternative e formulazione ideale, unimodularità. Metodi dei piani di taglio: taglio di Gomory. Metodi enumerativi: algoritmo di branch and bound.

8. Ottimizzazione nei grafi

Grafi; alberi di supporto di costo minimo: modelli di ottimizzazione matematica, algoritmo di Kruskal, algoritmo di Prim; problemi di cammino minimo: modelli di ottimizzazione matematica, algoritmo di Dijkstra, algoritmo di Floyd-Warshall; problemi di flusso: problema di taglio minimo, algoritmo di Ford-Fulkerson; problema del commesso viaggiatore: modelli di ottimizzazione matematica.

9. Ottimizzazione di progetti

Rappresentazione di progetti mediante digrafi: scomposizione di un progetto in attività elementari, digrafi con le attività sui nodi e con le attività sugli archi, identificazione di un cammino critico, diagrammi di Gantt; modelli probabilistici per l'analisi PERT: distribuzione del tempo di completamento: analisi dei costi; modelli di ottimizzazione matematica: progetti a risorse illimitate, bilanciamento di tempi e costi, progetti a risorse limitate.

10. Ottimizzazione nei sistemi stocastici

Decisioni ottimali in condizioni di rischio: valore atteso monetario, valore atteso della perdita di opportunità; equivalenza tra i due criteri; valore atteso della perfetta informazione. Decisioni sequenziali e alberi di decisione; valore atteso dell'informazioni campionaria, efficienza dell'informazione campionaria. Teoria dell'utilità e calcolo della funzione di utilità. Decisioni ottimali in condizioni di incertezza: criterio maximax, maximin, del realismo, di equiprobabilità, minimax. Teoria dei giochi: giochi in forma normale; tipi di giochi; strategie dominanti; equilibrio di Nash per strategie pure e miste; esempi: dilemma del prigioniero, battaglia dei sessi, controllo dell'inquinamento, assenza di equilibrio di Nash; strategie miste a due giocatori e dualità; giochi differenziali e dualità.

 

 


Prerequisiti

Conoscenze matematiche di base di analisi, geometria, algebra lineare e statistica.


Modalità di valutazione

L'esame si svolge in forma scritta, con domande aperte e chiuse (risposta multipla), sotto forma di quesiti teorici e/o esercizi applicativi.

Le domande di tipo teorico intendono verificare la conoscenza da parte dello studente dei presupposti e dei risultati matematici fondamentali nel campo dell'ottimizzazione e del funzionamento dei metodi e degli algoritmi proposti per la risoluzione di tali problemi.

Gli esercizi applicativi verificano invece la sua capacità di comprendere un modello assegnato, di descrivere una situazione reale attraverso un opportuno modello autonomamente sviluppato, di applicare i metodi e gli algoritmi illustrati nel corso dell'insegnamento per risolverlo e di interpretare efficacemente e consapevolmente i risultati ottenuti.

Verranno tenuti gli appelli d'esame previsti dai regolamenti didattici vigenti.

 


Bibliografia
Risorsa bibliografica obbligatoriaCarlo Vercellis, Ottimizzazione - Teoria, metodi, applicazioni, Editore: MGraw-Hill, Anno edizione: 2009, ISBN: 9788838664427 http://www.catalogo.mcgraw-hill.it/catLibro.asp?item_id=2318
Risorsa bibliografica facoltativaF.V. Fumero, Metodi di ottimizzazione: esercizi e applicazioni, Editore: Esculapio, Anno edizione: 2013, ISBN: 9788874886463

Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
60:00
90:00
Esercitazione
40:00
60:00
Laboratorio Informatico
0:00
0:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 100:00 150:00

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Italiano
Possibilità di sostenere l'esame in lingua inglese
schedaincarico v. 1.6.5 / 1.6.5
Area Servizi ICT
25/02/2021