Informazioni generali
Nome insegnamento Ricerca operativa
Anno 2011/2012
Propedeuticità Analisi Matematica I; Algebra Lineare e Analisi Matematica II
Carico didattico
CFU 9
Ore totali lezione 60
Ore totali esercitazione 30
Ore totali laboratorio 0
Obiettivi
Conoscenze: L’insegnamento ha l’obiettivo di fornire le conoscenze di base di Ricerca Operativa.
Capacità: L’insegnamento ha l’obiettivo di fornire gli strumenti per costruire modelli matematici di ottimizzazione, l’analisi  di tali modelli e i metodi risolutivi e la costruzione di algoritmi per la soluzione.
Comportamenti: L’insegnamento ha l’obiettivo di fornire strumenti rigorosi di tipo matematico per problemi di decisioni ottime in presenza di risorse limitate.
Programma

PROGRAMMAZIONE LINEARE (PL). Problemi e modelli di PL. Produzione, dieta, miscelazione. Geometria della PL: poliedri e loro rappresentazione. Condizioni di ottimalità. Teoria della dualità. Algebra della PL: soluzioni di base e vertici primali e duali. Teorema degli scarti complementari. Algoritmo del simplesso primale ed algoritmo del simplesso duale. Interpretazione geometrica. Il caso degenere e le regole anticiclo. . Il problema ausiliario per la ricerca della prima base ammissibile. (L: 15-E:5)

PROGRAMMAZIONE LINEARE SU RETI. Problemi e modelli di PL su reti. Flusso di costo minimo, trasporto, cammini minimi, flusso massimo, assegnamento di costo minimo, accoppiamento di cardinalità massima. Grafi. Proprietà della matrice di incidenza. Flussi e potenziali di base. Condizioni di Bellman. Algoritmo del simplesso per flussi. Cammini minimi. Algoritmo del simplesso per cammini. Algoritmo di Dijkstra. Flusso massimo. Taglio di capacità minima. Algoritmo di Ford–Fulkerson. (L: 15-E: 5)

PROGRAMMAZIONE LINEARE INTERA (PLI). Problemi e modelli di PLI. Turni, carico fisso, produzione, distribuzione di lavori, scheduling, selezione di sottoinsiemi, localizzazione, caricamento, commesso viaggiatore. Relazioni tra PL e PLI. Matrici totalmente unimodulari. Disuguaglianze valide. Piani di taglio di Gomory. Metodo del Branch and Bound. Valutazioni superiori ed inferiori. Regole di taglio. Risoluzione del problema dello zaino. Algoritmo di Kruskal. Risoluzione del problema del commesso viaggiatore asimmetrico e simmetrico. Rilassamento lagrangiano. (L: 15-E: 5)

PROGRAMMAZIONE NON LINEARE (PNL). Funzioni convesse, funzioni quadratiche, funzioni coercive. Metodi di minimizzazione per funzioni di più variabili non vincolate. Metodi di discesa. Metodo del gradiente con ricerca esatta ed inesatta. Metodo di Newton. Problemi di ottimizzazione vincolata. Moltiplicatori di Lagrange-Karush-Kuhn-Tucker. Analisi locale per lo studio dei punti stazionari. Metodo di Frank-Wolfe su poliedri. Metodo del gradiente proiettato su poliedri. (L: 20-E: 10)
Materiale didattico
M.Pappalardo-M.Passacantando: Ricerca Operativa, PLUS editore, anno 2010
Modalità di Esame
L'ammissione alla prova orale è subordinata al superamento della prova scritta.
Link utili
Ultime modifiche: mercoledì, 8 febbraio 2012, 13:16