Corso di Metodi di Ottimizzazione

Corso di Laurea in Ingegneria Gestionale

Ultimo Aggiornamento 10/04/2014


Avvisi

Prossimi appelli:
28 Aprile 2014 ore 10.30 Aula 2 (prenotazioni entro il 19 Aprile 2014 su Esse3 oppure via mail per gli studenti che non possono verbalizzare o appartenenti a corsi dell'ordinamento 509).
Appelli successivi:

12 Maggio 2014 ore 15.00 studio del docente
16 Giugno 2014 ore 15.00 studio del docente
1 Luglio 2014 ore 15.00 studio del docente
14 Luglio 2014 ore 15.00 studio del docente
1 Settembre 2014 ore 15.00 studio del docente
15 Settembre 2014 ore 15.00 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 40 ore) 1 credito di esercitazioni (pari a 16 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 (Provvisorio)

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.
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à di 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 (Definitive)

Al seguente link sono disponibili alcuni esercizi svolti e da svolgere:
Tracce di Esercizi (ed alcuni esercizi svolti).

File prestampato per impostare la risoluzione del problema del trasporto.

Modalità di svolgimento dell'esame

L'esame consiste in una prova orale. La prenotazione deve avvenire sul portale Esse3. Gli studenti appartenenti all'ordinamento 270/04 cui non è stato inserito ancora l'esame nella carriera elettronica possono prenotarsi via mail entro la data riportata. Ovviamente tali studenti potranno sostenere l'esame ma non verbalizzarlo.
Gli studenti iscritti al CdL Ingegneria Gestionale DM 509 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 entro la data prevista anche per gli altri studenti.

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 di Ricerca Operativa (LS Ing. Informatica/Automazione/Telecomunicazioni), il cui programma è parzialmente in comune.
Tracce


Date degli appelli

12 Maggio 2014 ore 15.00
16 Giugno 2014 ore 15.00 studio del docente
1 Luglio 2014 ore 15.00 studio del docente
14 Luglio 2014 ore 15.00 studio del docente
1 Settembre 2014 ore 15.00 studio del docente
15 Settembre 2014 ore 15.00 studio del docente.