logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2019/2020
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 085842 - FONDAMENTI DI RICERCA OPERATIVA D
Docente Bruglieri Maurizio
Cfu 5.00 Tipo insegnamento Monodisciplinare

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (1 liv.)(ord. 270) - MI (358) INGEGNERIA INFORMATICAIOAAZZZZ085842 - FONDAMENTI DI RICERCA OPERATIVA D
IOLAZZZZ085842 - FONDAMENTI DI RICERCA OPERATIVA D
IORAZZZZ085842 - FONDAMENTI DI RICERCA OPERATIVA D

Obiettivi dell'insegnamento

Si tratta di un corso di matematica applicata, in cui vengono analizzati modelli per formulare e tecniche per risolvere problemi di decisione.

Nello specifico il corso si propone i seguenti obiettivi:
- Insegnare la teoria e i metodi dell’ottimizzazione;

- Confrontare le prestazioni di algoritmi diversi per la risoluzione dello stesso problema decisionale;

- Fare conoscere i principi fondamentali della modellizzazione matematica dei sistemi reali;

- Insegnare a progettare e applicare con rigore scientifico specifici modelli di ottimizzazione per risolvere problemi decisionali.

 


Risultati di apprendimento attesi

- Conoscenza dei principi base della teoria dell'ottimizzazione lineare continua ed intera, e dell'ottimizzazione su grafi.
- Conoscenza delle principali tecniche risolutive e degli algoritmi tradizionalmente utilizzati per risolvere problemi di ottimizzazione.
- Capacità di comprendere e interpretare la formulazione di un modello matematico.
- Capacità di analizzare un problema reale di ottimizzazione e di formulare specifici modelli matematici di rappresentazione del problema.

- Capacità di identificare metodi e algoritmi risolutivi per problemi di ottimizzazione e di utilizzare software opportuni per la loro soluzione


Argomenti trattati

Il corso è diviso in 5 parti, per complessive 24 lezioni. La prima parte riguarda esempi di passaggio da problemi decisionali a modelli matematici, con una classificazione dei modelli stessi. La seconda riguarda l'ottimizzazione su grafo, con la presentazione dei principali problemi e dei relativi algoritmi. La terza riguarda la programmazione lineare, le caratteristiche dei modelli di questo tipo, l'algoritmo del simplesso, il concetto di dualità, la presentazione di applicazioni. La quarta riguarda la programmazione a numeri interi, l'uso di algoritmi esatti, la necessità di algoritmi euristici, la presentazione di applicazioni. L'ultima parte è dedicata alla programmazione a molti obiettivi e a molti criteri.

 

1. Introduzione ai problemi decisionali. Modelli matematici di decisione e loro caratteristiche: decisori, obiettivi, informazione, grado di incertezza.

2. Ottimizzazione su grafo: definizione. Cammini ottimi: algoritmi delle etichette (programmazione dinamica), di Dijkstra e Floyd-Warshall. Il Pert. Alberi di copertura: algoritmi di Prim e Kruskal. Flusso massimo (max flow- min cut).

3. Formulazione di un problema di programmazione lineare, proprietà generali, esempi. Forma standard, soluzioni di base, teorema fondamentale. Metodo del simplesso, forma canonica, soluzione ammissibile iniziale. Teoremi della dualità e dello scarto complementare. Interpretazione economica, post-ottimalità e analisi di sensitività.

4. Programmazione Lineare Intera (PLI). Metodi di “Branch and Bound" e applicazioni ai casi della PLI, del problema di zaino e del problema del commesso viaggiatore (TSP). Euristiche per il TSP. 

5. Modelli di programmazione a molti obiettivi. Dominanza e soluzioni paretiane. Analisi a molti criteri. Metodo della somma pesata e sensitività sui pesi.


Prerequisiti

Conoscenze di base di Algebra Lineare e di Geometria Analitica.


Modalità di valutazione

·         Durata.

Il corso si articola secondo l'agenda che viene inizialmente indicata. All'inizio del corso viene effettuata una “prova d'ingresso”, valutata al fine di fornire un feedback agli studenti ma non considerata ai fini del voto finale

·         Prove in itinere (PI).

Ciascuna delle 3 PI – collocate come indicato nell'agenda e relative prevalentemente alle parti 1° e 2°, alla parte 3°, alle parti 4° e 5° – ha a disposizione 10 punti. In genere le prove vengono messe sul sito il venerdì e lasciate fino al lunedì, ma sul forum viene indicato un ragionevole tempo di esecuzione (stimato dal docente) come raffronto.

·         Incrementi di punteggio.

Hanno l'obiettivo di premiare chi partecipa regolarmente e positivamente alle varie attività del corso. Vengono attribuiti in base a tre parametri: la partecipazione alle sessioni live (1/3 di punto per ogni presenza), la scoperta di errori non formali nei materiali didattici (1/4 di punto per ogni errore scoperto e segnalato sul sito, in una apposita cartella), la partecipazione consapevole al forum di materia (1/4 di punto per ogni intervento ritenuto significativo dai tutor e come tale indicato sul forum, non c'è alcuna penalizzazione legata a messaggi non significativi o sbagliati). Il massimo incremento ottenibile in questo modo è di 2 punti.

Inoltre verranno indicati alcuni progetti di approfondimento (ricerche bibliografiche, progetti da sviluppare come prototipo, ecc.) anche su proposta degli studenti. Attraverso il progetto di approfondimento è possibile ottenere un ulteriore incremento del voto fino a 2 punti.

·         Prova d’esame.

Viene svolta una prova scritta (di circa 3 ore) allo scopo di confrontare i punteggi ottenuti nelle PI con il lavoro svolto in presenza. La prova riguarda tutto il corso ed è costituita da 10 domande o problemi da risolvere, divise in 3 gruppi di 3 domande più una finale facoltativa. Se il voto complessivo della prova è migliore di quello ottenuto come somma delle 3 PI, viene considerato il voto della prova; se è peggiore ma entro un massimo di 5 punti in meno, viene considerata la media dei due voti; se lo scarto è maggiore di 5 punti bisogna sostenere un esame orale sui contenuti di tutto il corso (ciò è dichiaratamente fatto allo scopo di sconsigliare lo studente dal copiare nelle PI online, ottenendo in esse un voto molto migliore rispetto a quello che presumibilmente otterrà nella prova in presenza). Se lo scarto tra PI e prova in presenza è maggiore di 3 punti su una singola parte (cioè su una delle PI), l'esame orale riguarderà la sola parte su cui si è verificato lo scarto.

Se il voto totale della prova in presenza è inferiore a 15 essa deve essere ripetuta.


Bibliografia
Risorsa bibliografica facoltativaMaurizio Bruglieri, Alberto Colorni, Ricerca Operativa, Editore: Zanichelli, Anno edizione: 2012, ISBN: 978-88-08-16694-4 www.online.zanichelli.it/bruglieri

Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
32:30
48:45
Esercitazione
17:30
26:15
Laboratorio Informatico
0:00
0:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 50:00 75:00

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Italiano
Disponibilità di libri di testo/bibliografia in lingua inglese
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.6.1 / 1.6.1
Area Servizi ICT
04/04/2020