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 083220 - FONDAMENTI DI RICERCA OPERATIVA
Docente Carello Giuliana
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 (365) INGEGNERIA MATEMATICA*AZZZZ083220 - FONDAMENTI DI RICERCA OPERATIVA

Obiettivi dell'insegnamento

Il corso presenterà alcune metodologie di base della Ricerca Operativa, la disciplina che studia come applicare il metodo scientifico e gli strumenti e i metodi quantitativi alla soluzione dei problemi decisionali. Il corso porrà particolare attenzione agli aspetti modellistici ed algoritmici che emergono nella soluzione di problemi decisionali in ambito ingegneristico.


Risultati di apprendimento attesi

A seguito del superamento dell'esame lo studente deve:

- conoscere le principali tipologie di variabili decisionali, vincoli e funzione obiettivo usati nella programmazione lineare

- conoscere le proprietà fondamentali della programmazione lineare e della dualità

- conoscere alcuni metodi di soluzione di problemi di programmazione lineare e le loro proprietà

- conoscere i problemi su grafo trattati nel corso, le loro proprietà e i relativi algoritmi di risoluzione

- conoscere alcune metodologie (tagli di Gomory e branch and bound) per la soluzione di problemi di programmazione lineare a variabili intere

- conoscere i principi di base della complessità computazionale

 

- essere in grado di riconoscere le decisioni, i vincoli e l'obiettivo che descrivono un problema decisionale e di rappresentarli con un modello di programmazione lineare

- essere in grado di applicare i metodi di soluzione per problemi di programmazione lineare a piccoli esempi

- essere in grado di riconoscere i diversi problemi su grafo e di individuare e applicare l'algoritmo più adatto alla loro soluzione

- essere in grado di applicare i metodi studiati per la programmazione lineare a variabili intere (tagli di Gomory e branch and bound) a piccoli esempi

- essere in grado di applicare le conoscenze teoriche acquisite per rispondere a semplici quesiti


Argomenti trattati

1. Introduzione: Problemi decisionali, esempi e caratteristiche. Tipologia dei modelli di ottimizzazione (programmazione matematica). Modelli di programmazione lineare e lineare intera: variabili, vincoli e funzione obiettivo.

2. Programmazione lineare: Forme equivalenti, aspetti geometrici e algebrici. Proprietà fondamentali della programmazione lineare. Teoria della dualità: dualità debole e forte, condizioni degli scarti complementari. Condizioni di ottimalità. L'algoritmo del simplesso per problemi in programmazione lineare.

3. Problemi di ottimizzazione su grafi e reti.  Problema dell'albero di supporto di costo minimo, algoritmi di soluzione. Problema dei cammini minimi: algoritmi di soluzione.  Problema del flusso di valore massimo: algoritmo di Ford-Fulkerson, teorema del flusso massimo e taglio minimo.


4. Programmazione lineare intera:  Metodi di risoluzione esatti. Metodo dei piani di taglio con tagli di Gomory. Metodo di Branch & Bound e tecniche per ottenere le stime dell'ottimo. Cenni sulla teoria della complessità computazionale.

Attività di laboratorio

Si prevede lo svolgimento di esercitazioni in Laboratorio di Informatica con l'introduzione di software per la modellizzazione e la risoluzione dei problemi di programmazione matematica.


Prerequisiti

Conoscenze elementari di algebra lineare.


Modalità di valutazione

Prova scritta che include:

- esercizi sulla risoluzione di problemi allo scopo di verificare la capacità di applicare correttamente i metodi studiati

- domande di carattere teorico sugli argomenti del corso allo scopo di verificare la conoscenza delle proprietà e dei principi studiati


Bibliografia
Risorsa bibliografica obbligatoriaappunti del docente (disponibili sulla pagina Beep del corso)
Risorsa bibliografica facoltativaF. S. Hillier, G. J. Lieberman, Ricerca Operativa: Fondamenti, Editore: McGraw-Hill
Risorsa bibliografica obbligatoriaR.Tadei, F.Della Croce, Elementi di Ricerca Operativa, Editore: Esculapio

Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
30:00
45:00
Esercitazione
12:00
18:00
Laboratorio Informatico
8:00
12: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
schedaincarico v. 1.6.1 / 1.6.1
Area Servizi ICT
20/01/2020