Obiettivi
Il corso descrive l'ottimizzazione da tre prospettive diverse, tra loro fortemente integrate: la teoria, i metodi e le applicazioni. L'estensione degli argomenti trattati è ampia: l'ottimizzazione lineare, con particolare riferimento all'algoritmo del simplesso; la teoria della dualità lineare; l'ottimizzazione intera e nei grafi; la gestione dei progetti; la teoria delle decisioni e i legami tra la teoria dei giochi e l'ottimizzazione. I riferimenti a problemi reali e il frequente ricorso a esemplificazioni si accompagnano al rigore nella descrizione della teoria dell'ottimizzazione, degli algoritmi risolutivi e dei modelli applicativi. Il corso si propone inoltre di fornire agli allievi una autonoma capacità di analizzare un problema reale, di formulare un modello di ottimizzazione che lo rappresenta, di individuare un algoritmo risolutivo e infine di interpretarne i risultati.

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

Programma

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

X

L'esame si svolge in forma scritta. Verranno tenuti gli appelli d'esame, inclusi preappelli o prove in itinere, previsti dai regolamenti didattici vigenti.