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 088698 - FONDAMENTI DI RICERCA OPERATIVA
Docente Malucelli Federico
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 (355) INGEGNERIA DELL'AUTOMAZIONE*AZZZZ088698 - FONDAMENTI DI RICERCA OPERATIVA
Ing Ind - Inf (Mag.)(ord. 270) - MI (475) ELECTRICAL ENGINEERING - INGEGNERIA ELETTRICA*AZZZZ088698 - FONDAMENTI DI RICERCA OPERATIVA

Obiettivi dell'insegnamento

La Ricerca Operativa, è la disciplina che concerne l'utilizzazione del metodo scientifico nei processi decisionali. Essa è di importanza centrale nel trattamento di sistemi complessi con metodi quantitativi. La caratteristica tipica del suo approccio è l'analisi e la modellazione dei sistemi decisionali e lo sviluppo di algoritmi efficienti allo scopo di prevederne l'evoluzione e di individuare le scelte che li facciano evolvere verso gli obiettivi desiderati.

L'insegnamento affronterà alcuni problemi di ottimizzazione che sorgono nell’ambito industriale e informatico traendo spunto per introdurre alcune delle metodologie principali della Ricerca Operativa (RO), privilegiando gli aspetti modellistici e algoritmici. 

 

Obiettivi formativi metodologici: Affrontare i problemi di ottimizzazione che sorgono nell’ambito professionale; astrazione dei problemi e costruzione di modelli matematici di ottimizzazione; applicazione di algoritmi di ottimizzazione a semplici esempi. Sviluppo di algoritmi di soluzione; utilizzo di strumenti software di ottimizzazione.

Obiettivi formativi secondari: Capacità di analisi dei problemi, lavoro progettuale di gruppo, presentazione tecnica. Introduzione al “problem solving”.

 


Risultati di apprendimento attesi
Conoscenza e comprensione
 
Gli studenti impareranno:

- Il linguaggio matematico dei modelli di ottimizzazione e alcune classi di modelli

- Le pricipali proprietà e algoritmi (inlusa la valutazione della complessità nel caso pessimo) per seguenti classi di problemi di ottimizzazione su grafo: albero di copertura di costo minimo, cammino minimo, flusso massimo, flusso di costo minimo, assegnamento

- il metodo del cammino critico per la pianificazione di progetto

- gli aspetti algebrici e geometrici della programmazione lineare e un algoritmo di soluzione 

- le principali proprietà della dualità, come la dualità forte e debole e le condizioni degli scarti complementari

- L'interpretazione economica del duale

- le principali caratteristiche dei problemi di programmazione lineare intera

- il metodo dei piani di taglio e i tagli di Gomory
- il metodo del Branch and Bound per problemi di programmazione lineare intera e altri problemi di ottimizzazione combinatoria

- le defiizioni di base della complessità computazionale

-la struttura degli algoritmi euristici di tipo Greedy e Ricerca Locale

- alcuni cenni di ottimizzazione non lineare

Applicazione della conoscenza e comprensione

 

Gli studenti saranno in grado di:

- costruire modelli matematici di ottimizzazione a pratire dalla descrizione dei problemi di decisione

- risolvere i modelli con software di ottimizzazione e intepretare i risultati

- identificare appropriati algioritmi di ottimizzazione su grafo per affrontare particolari problemi di ottimizzazione

- applicare gli algoritmi di ottimizzazione su grafo a piccoli esempi

- appicare l'algoritmo di programmazione lineare a semplici esempi

- costruire il duale e le equazioni degli scarti complementari di problemi di programmazione lineare sia in forma numerica che in forma parametrica

- applicare i metodi di programmazione lineare intera studiati  (Branch-and-Bound, tagli di Gomory) a piccoli esempi

- costruire algoritmi euristici di tipo Greedy e di Ricerca Locale

Capacità di apprendimento

Gli studenti impareranno in modo attivo ad affrontare problemi decisionali complessi con un approccio matematico e algoritmico, che può venire adattato ed esteso a problemi reali.

 


Argomenti trattati

1. Introduzione alla Ricerca Operativa Introduzione all’ottimizzazione: panoramica di problemi con l’ottica dell’ottimizzazione. Introduzione ai problemi di ottimizzazione e loro formulazione. Variabili, Vincoli e Funzioni obiettivo, problemi multiobiettivo. Introduzione al linguaggio di modellazione AMPL e al software di ottimizzazione.

2. Ottimizzazione su reti I grafi e gli alberi; algoritmi di visita. Il problema dell'albero dei cammini minimi. Il problema di flusso massimo. Il problema del flusso di costo minimo. Il problema dell'assegnamento. Algoritmi di soluzione. Problemi di project planning, di vehicle scheduling e timetable design.

3. Programmazione Lineare Teoria matematica della dualità; coppie di problemi duali; teoremi della dualità e degli scarti complementari; il metodo del simplesso primale-duale; interpretazioni geometrica e economica. Cenni di programmazione non lineare. Problemi di mix produttivo, problemi di investimento, problemi multiperiodo.

4. Programmazione intera e combinatoria Problemi di ottimizzazione lineare discreta; variabili intere e decisionali. Metodi di piani di taglio. Albero delle decisioni; valutazioni per difetto e per eccesso; il metodo del Branch&Bound. Algoritmi euristici: greedy e ricerca locale. Problemi di carico, di assegnamento di incarichi.

5. Cenni di ottimizzazione non lineare. Ottimizzazione non vincolata, condizioni di ottimo, algoritmi. Ottimizzazione vincolata, condizioni di ottimo.


Prerequisiti

Notazione algoritmica di base

Concetti di base di algebra lineare e di geometria


Modalità di valutazione

La modalità di valutazione consta di una prova scritta e una prova di laboratorio facoltativa.

La prova scritta può essere sostituita da 2 prove in itinere. Una delle due prove in itinere che risultasse insufficiente o nella quale lo studente conseguisse un punteggio per lui insoddisfacente può essere recuperata (una sola volta) durante gli appelli regolari. Una prova si ritiene sostenuta all'atto della consegna. L'esame viene sostenuto a libri aperti.

Nella prova scritta si intende verificare le capacità di applicazione degli algoritmi di base di ottimizzazione su grafi e reti, di programmazione lineare e di programmazione intera visti durante l'insegnamento, e come sfruttare le principali proprietà dei problemi per ricavare le soluzioni.

Inoltre vi saranno esercizi di modellazione e di creazione di semplici algoritmi euristici il cui scopo è verificare le capacità interpretative e modellistiche e l'autonomia di visione dello studente.

Nella prova di laboratorio si intendono verificare le capacità di utilizzare lo strumento software visto in laboratorio per risolvere problemi realistici e interpretarne i risultati.


Bibliografia
Risorsa bibliografica obbligatoriaappunti del docente http://home.dei.polimi.it/malucell/didattica/appunti/materiale.html
Risorsa bibliografica facoltativaF. S. Hillier, G. J. Lieberman, Ricerca Operativa: Fondamenti, Editore: McGraw-Hill

Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
32:00
48:00
Esercitazione
14:00
21:00
Laboratorio Informatico
4:00
6: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 materiale didattico/slides in lingua inglese
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.6.4 / 1.6.4
Area Servizi ICT
10/07/2020