Corso di Metodi di
Ottimizzazione (Corso A-K)
Corso di Laurea in Ingegneria Gestionale
Ultimo Aggiornamento 08/04/2019
Avvisi
Calendario esame del 9 Aprile 2019.
Il primo appello di settembre, già previsto a partire dalla mattina del 6 settembre, si svolgerà
regolarmente. Poichè è prevedibile che a causa della legittima astensione di molti colleghi
docenti l'appello sarà molto affollato il docente invita gli studenti a presentarsi solo se
in possesso di una preparazione adeguata.
L'astensione dagli esami riguarda il primo appello quindi il secondo appello di settembre
sarà garantito comunque.
La prova si svolge in diversi giorni (solitamente due/tre, in funzione della numerosità degli
studenti prenotati). Il calendario delle prove sarà reso noto il giorno prima della data d'esame.
Gli studenti sono invitati a segnalare eventuali esigenze legate alla data d'esame (soprattutto
eventuale coincidenza con altre prove d'esame) inviando una mail al
docente entro la data di scadenza delle prenotazioni. Il docente cercherà, nei limiti
del possibile, di tenere conto di tali problemi nella stesura del calendario.
Calendario appelli:
19 Giugno 2017 ore 8.30 Aula 5
10 Luglio 2018 ore 8.30 Aula 10
4 Settembre 2018 ore 8.30 Aula Q
18 Settembre 2018 ore 8.30 Aula Q
6 Novembre 2018 ore 8.30 Aula Q
15 Gennaio 2019 ore 8.30 Aula Q
12 Febbraio 2019 ore 8.30 Aula Q
9 Aprile 2019 ore 8.30 Aula 23.
Organizzazione del Corso
Il Corso di Metodi di Ottimizzazione ha il valore 6 crediti suddivisi secondo la seguente
tipologia didattica:
4.5 crediti di lezioni teoriche (pari a 36 ore)
1.5 crediti di esercitazioni (pari a 12 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.
L’approccio modellistico ai problemi di ottimizzazione.
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.
Modelli di miscelzione. Modelli logistici e di assegnamento. 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.
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.
M. Caramia, S. Giordani, F. Guerriero, R. Musmanno, D. Pacciarelli, Ricerca Operativa, Isedi.
Materiale didattico
File prestampato per impostare la risoluzione del problema del trasporto.
Modalità di prentazione e svolgimento dell'esame
L'esame consiste in una prova scritta che prevederà sia esercizi che quesiti teorici (2 esercizi e 2
domande teoriche) riguardanti tutto il programma
del corso.
Il calendario delle prove sarà pubblicato il giorno successivo la scadenza dei termini per la
prenotazione su Esse3.
Gli studenti che, per problemi vari, non potessero
presentarsi il giorno dell'appello o in uno giorni successivi ono pregati di inviare
una mail al docente prima della scadenza delle prenotazioni in modo tale da essere
inseriti in un turno per il quale possano essere presenti.
La prenotazione deve avvenire obbligatoriamente sul portale Esse3.
Richeste di deroga a tale regola non
saranno prese in considerazione.
Tracce di esame
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
Appelli anno accademico 2016/2017:
19 Giugno 2017 ore 8.30
10 Luglio 2018 ore 8.30
4 Settembre 2018 ore 8.30
18 Settembre 2018 ore 8.30
6 Novembre 2018 ore 8.30
15 Gennaio 2019 ore 8.30
12 Febbraio 2019 ore 8.30
9 Aprile 2019 ore 8.30.