Metodi di ottimizzazione

Nome docente	Carta Fernando
Corso di laurea	Scienze e Gestione delle Attività Marittime
Anno accademico	2022/2023
Periodo di svolgimento	Secondo semestre
Crediti formativi universitari (CFU)	12
Settore scientifico disciplinare	MAT/05
Download Programma

Obiettivi del corso

Fornire agli studenti una buona base di competenze teoriche, metodologiche ed applicative nelle aree fondamentali della disciplina. Saranno sviluppate capacità di analisi e di sintesi, di apprendimento individuale, di soluzione di problemi, di comprensione ed utilizzazione di modelli matematici di interesse sia scientifico, sia applicativo.

Prerequisiti

Contenuti di base di analisi matematica.

Programma

1) Funzioni scalari di più variabili, dominio naturale, grafico. Lo spazio vettoriale n  . Intorno di un punto di n  , punto isolato e punto di accumulazione. Nozione di proprietà verificata definitivamente. Punti di estremo locale.

2) Limiti e continuità per funzioni di più variabili. Insiemi aperti, chiusi, limitati. Nozioni di punto interno, di insieme aperto, di punto esterno, di insieme chiuso. Punti di frontiera, insiemi limitati.

3) Derivate direzionali e parziali, gradiente. Nozione di punto critico, teorema di Fermat. Differenziabilità, migliore approssimazione lineare. Regolarità delle funzioni differenziabili, teorema del differenziale totale.

4) Derivate successive, teorema di Schwarz, matrice hessiana. Polinomio di Taylor per funzioni di più variabili. Estremi liberi di funzioni a valori scalari.

5) Segno delle matrici reali simmetriche, studio della natura dei punti critici.

6) Introduzione ai problemi di Ottimizzazione. Esempi: problemi di pianificazione delle risorse, problemi di scheduling. Esempi di  problemi non lineari. L’approccio modellistico ai problemi di ottimizzazione. Modelli deterministici e modelli stocastici. Problemi di ottimizzazione continua, discreta e mista.

7) Esempi di definizione di modelli di programmazione matematica. Programmazione lineare. Esempi classici di problemi di programmazione lineare: il problema della dieta. Problemi in forma standard. Regione ammissibile. Insiemi convessi. Soluzioni ammissibili e soluzione ottima. Il caso di una regione ammissibile illimitata. Soluzioni multiple. Il metodo grafico per problemi di programmazione lineare in due dimensioni. Problemi di programmazione lineare in forma standard. Variabili slack.

8) Il Problema aumentato. Il metodo del simplesso. Struttura tabellare del metodo del simplesso. Il caso delle funzioni illimitate. Il caso delle soluzioni multiple. Soluzioni degeneri. Regole anticiclo: La regola di Bland. Problemi in forma non standard. Minimizzazione di funzioni lineari. Il caso di variabili decisionali con valori negativi. Variabili decisionali limitate. Vincoli di uguaglianza. Vincoli tipo maggioreuguale. Variabili artificiali e variabili surplus. Definizione del
problema artificiale. Il metodo del simplesso a due fasi. Analisi Postottimale. Prezzi ombra.

9) Il problema del trasporto: il modello matematico. Condizione di ammissibilità per il problema del trasporto. Il problema della BFS iniziale. La Regola del Nord-Ovest. Il metodo di Vogel. Il metodo di Russell. Il caso dell BFS degeneri. Il metodo del simplesso per il problema del trasporto. Proprietà di interezza delle soluzioni. Il problema del trasporto con una sorgente o una destinazione fittizia. Il caso dei costi indefiniti.

10) Problemi di programmazione lineare binaria. Il problema dello zaino. Il problema di assegnamento. Il metodo ungherese per il problema di assegnamento.

11) Problemi di ottimizzazione su reti. Definizione di Grafo orientato e non orientato. Proprietà e terminologia dei grafi. Il problema di minimo albero ricoprente. L'algoritmo di Prim. L'algoritmo di Kruskal.
Il metodo Reverse-Delete. Lati di diminuazione. Condizione di ottimalità per un albero ricoprente. Il problema del cammino minimo. L’algoritmo di Dijkstra. Tecniche reticolari di gestione dei progetti. PERT e CPM. Tecniche AON e AOA. Definizione di cammino critico. Diagrammi di Gantt. Crash di un'attività. Trade-off dei tempicosti.

12) Problemi di programmazione lineare binaria e intera. Il metodo Branch-and-Bound per problemi binari. Definizione dei sottoproblemi. Soluzione incombente. Criteri di Fathoming. Test di ottimalità. Il metodo Branch-and-Bound per problemi interi o misti. Criteri di Fathoming per problemi di programmazione intera.

Testi di riferimento

1) Bertsch, Dell’Aglio, Giacomelli – Epsilon 1 Primo corso di Analisi Matematica - Mc Graw Hill;

2) F. Hillier, G. Lieberman, Ricerca Operativa, McGraw-Hill;

3) Un qualunque testo di esercitazioni di ricerca operativa.

Metodi didattici

Lezioni frontali nelle quali si espongono i contenuti disciplinari, con dimostrazioni dei teoremi ed esempi. Parte rilevante ha la presentazione della risoluzione di esercizi scelti in modo da esemplificare la teoria e fornire le basi per le applicazioni pratiche.

Risultati di apprendimento previsti

Conoscenza e capacità di comprensione:

- Conoscenza delle definizioni e dei teoremi previsti dal programma;

- Conoscenza dei metodi risolutivi degli esercizi;

- Comprensione dei contenuti e capacità di realizzare dimostrazioni in modo autonomo;

- Capacità di risolvere problemi utilizzando i contenuti del corso.

Conoscenza e capacità di comprensione applicate:

- Comprensione dei metodi di modellizzazione matematica in vari ambiti;

- Capacità di risolvere problemi applicativi relativi ai contenuti del corso;

- Saper analizzare i risultati ottenuti.

Competenze trasversali:

- Autonomia di giudizio

Al termine dell’insegnamento lo studente dovrà essere in grado di:

- Esporre i contenuti trattati nel corso dando prova di averne compreso l’approccio logico e le finalità.

- Dare prova di conoscere i metodi risolutivi per risolvere problemi applicativi;

- Saper modellizzare un problema utilizzando i metodi più appropriati, saper eseguire i relativi algoritmi risolutivi e interpretarne i risultati.

- Abilità comunicative

- Saper esporre in modo chiaro e rigoroso l’approccio risolutivo di un problema;

- Saper motivare la scelta del procedimento adottato nella risoluzione di un problema;

- Capacità di apprendere in modo autonomo

- Saper ricercare, comprendere ed applicare contenuti e metodi nuovi.

Valutazione

Modalità di verifica dell’apprendimento:

Prova scritta con eventuale prova orale

Criteri di valutazione:

Conoscenza e capacità di comprensione:

- Conoscenza consapevole delle definizioni, dei teoremi e delle dimostrazioni previste dal programma

Conoscenza e capacità di comprensione applicate:

- Comprensione dei metodi di modellizzazione matematica, capacità di utilizzarli autonomamente nella risoluzione di problemi

Autonomia di giudizio:

- Capacità di esposizione, sia scritta, sia orale dei contenuti del corso dimostrando di averli acquisiti consapevolmente.

Abilità comunicative:

- Saper esporre in modo chiaro e rigoroso i contenuti teorici e gli approcci adottati nella risoluzione di un problema.

Capacità di apprendere:

- Evidenza di comprensione attiva dei contenuti disciplinari, capacità di individuare con precisione approcci risolutivi appropriati.