Politecnico di Milano
SchedaIncarico
 
Funzioni disponibili
Uscita

Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2008/2009
FacoltÓ Scuola di Ingegneria dell'Informazione
Insegnamento 070321 - FONDAMENTI DI RICERCA OPERATIVA D
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 (2 liv.)(ord. 509) - MI (187) INGEGNERIA INFORMATICA* HZZZZ070321 - FONDAMENTI DI RICERCA OPERATIVA D

Programma dettagliato e risultati di apprendimento previsti

Obiettivi

Il corso presenterà alcune metodologie di base della Ricerca Operativa (RO) ponendo particolare attenzione agli aspetti modellistici e algoritmici che emergono nella soluzione di problemi decisionali in ambito ingegneristico.


Programma delle lezioni e delle esercitazioni

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

2. Problemi di ottimizzazione su grafi e reti: Problema di raggiungibilità in un grafo. Algoritmi e ordine di complessità. Problema dell'albero di supporto di costo minimo, algoritmi di soluzione. Problema dei cammini minimi: algoritmi di soluzione, e metodo della programmazione dinamica per grafi senza circuiti. Pianificazione dei progetti: metodo del cammino critico. Problema del flusso di valore massimo: algoritmo di Ford-Fulkerson, teorema del flusso massimo e taglio minimo.

3. Cenni sulla teoria della complessità computazionale: problemi di riconoscimento, classi P e NP, problemi NP-completi e NP-difficili.

4. 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à. Algoritmi di soluzione per problemi in programmazione lineare.

5. 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.

 

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.

 

 


Bibliografia

Bibliografia consigliata

M. Fischetti, Lezioni di Ricerca Operativa, seconda edizione, Edizioni Libreria Progetto, Padova, 1999.

M. Dell'Amico, 120 Esercizi di Ricerca Operativa, Pitagora Editrice, Bologna, 1996.

Copie dei lucidi del prof. E. Amaldi scaricabili da http://home.dei.polimi.it/amaldi/FRO-DE-07-08.html

Dispense del prof. F. Malucelli scaricabili da http://home.dei.polimi.it/malucell

F.S. Hillier, G.J. Lieberman, Introduction to Operations Research, sixth edition, McGraw-Hill, 1995.

F. Maffioli, Elementi di Programmazione Matematica, seconda edizione, Casa Editrice Ambrosiana, 2000.

W.L. Winston, Operations Research, Applications and Algorithms, third edition, ITP, 1994.


Altro materiale didattico

Software AMPL scaricabile gratuitamente

 


Mix Forme Didattiche
Tipo Forma Didattica Ore didattiche
lezione
35.0
esercitazione
15.0
laboratorio informatico
10.0
laboratorio sperimentale
0.0
progetto
0.0
laboratorio di progetto
0.0

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Italiano
DisponibilitÓ di libri di testo/bibliografia in lingua inglese
PossibilitÓ di sostenere l'esame in lingua inglese
DisponibilitÓ di supporto didattico in lingua inglese

Note Sulla ModalitÓ di valutazione

Il corso non prevede prove in itinere. Una prova scritta e una prova facoltativa di laboratorio.

25/04/2014 v. 1.0.59 / 1.0.59