Ottimizzazione della ricerca operativa

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