Corso di Metodi di Ottimizzazione

Corso di Laurea in Ingegneria Gestionale

Ultimo Aggiornamento 08/04/2015


Avvisi

A partire dall'appello di Febbraio 2015 la prenotazione su Esse3 è obbligatoria anche per gli studenti appertenenti a corsi dell'ordinamento 509/99.

Calendario esame del 13 Aprile 2015.
A causa di alcuni problemi che si sono verificati con la verbalizzazione posticipata degli esami a partire dall'appello di Giugno saranno ammesse prenotazioni solo attraverso il portale Esse3 per gli studenti appartenenti ai corsi di studio degli ordinamenti 270/04 e 509/99 e via e-mail entro 7 giorni dalla data dell'esame per gli appartenenti a corsi di studio dell'ordinamento pre-riforma.

Prossimi appelli:
2 Febbraio 2015 ore 8.30 studio del docente
13 Aprile 2015 ore 8.30 studio del docente.

Organizzazione del Corso

Il Corso di Metodi di Ottimizzazione ha il valore 6 crediti suddivisi secondo la seguente tipologia didattica:
5 crediti di lezioni teoriche (pari a 50 ore) 1 credito di esercitazioni (pari a 10 ore)

Finalità del Corso

Obiettivo del corso è quello di fornire agli studenti del corso di Laurea in Ingegneria Gestionale gli strumenti per la descrizione matematica in termini modellistici di problemi di ottimizzazione, nonchè gli algoritmi per la risoluzione di problemi di programmazione lineari e su reti.

Programma del Corso

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. 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. 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 maggiore-uguale. Variabili artificiali e variabili surplus. Definizione del problema artificiale. Il metodo del simplesso a due fasi. Analisi Postottimale. Prezzi ombra.
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.
Problemi di programmazione lineare binaria. Il problema dello zaino. Il problema di assegnamento. Il metodo ungherese per il problema di assegnamento.
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.
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.

Libri di riferimento:

F. Hillier, G. Lieberman, Ricerca Operativa, McGraw-Hill
M. Bruglieri, A. Colorni, Ricerca Operativa, Zanichelli.

Materiale didattico

Le dispense finali del corso (in formato PDF) sono disponibili al seguente link:
Dispense

File prestampato per impostare la risoluzione del problema del trasporto.

Modalità di svolgimento dell'esame

L'esame consiste in una prova orale/scritta durante la quale dovranno essere risolti (per iscritto) esercizi riguardanti tutti gli argomenti del corso e da un esame orale contestuale riguardante tutto il programma del corso. La prenotazione deve avvenire sul portale Esse3per gli studenti appartenenti agli ordinamenti 509/99 e 270/04.
Gli studenti iscritti al CdL Ingegneria Gestionale ordinamento pre-riforma che devono sostenere l'esame di Ricerca Operativa (equivalente nel N.O. all'esame di Metodi di Ottimizzazione) possono iscriversi mandando un e-mail al docente almeno 7 giorni prima della data dell'esame.

Tracce di esame

L'esame si svolge oralmente quindi non sono disponibili tracce d'esame.

Per esercitarsi al seguente link si trovano le tracce dell'esame scritto del corso (disattivato) di Ricerca Operativa (LS Ing. Informatica/Automazione/Telecomunicazioni), il cui programma era simile.
Tracce

Date degli appelli

2 Febbraio 2015 ore 8.30 studio del docente
13 Aprile 2015 ore 8.30 studio del docente.