Codice identificativo insegnamento: 098474
Programma
sintetico:
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à.