Ricerca Operativa - A.A. 2012/2013 - Corso
di Laurea Triennale in Ingegneria Gestionale, Classe L8 - L9 Ricerca Operativa - A.A. 2012/2013 - Corso
di Laurea Triennale in Ingegneria Gestionale, Classe L8 - L9
invia un suggerimento al docente
Obiettivi Formativi:
Il corso introduce alla modellazione matematica e fornisce gli elementi fondamentali,
gli approcci metodologici e le tecniche risolutive per problemi di programmazione
lineare e lineare intera.
Orario delle lezioni
e di ricevimento
Programma
Testi di riferimento e materiale didattico integrativo
Modalità e temi di esame
Appelli
Orario delle lezioni e ricevimento
- Orario delle lezioni
Lunedì dalle ore 14.30 alle ore 17.30.
Giovedì dalle ore 14.30 alle ore 17.30.
- Orario di ricevimento
a Ancona: mercoledì dalle ore 10.30 alle ore 13.30.
a Fermo: lunedì dopo la lezione.In ogni caso contattare il docente al numero 071-2204823 oppure via posta elettronica.
Programma
- Programma generale
Sistemi organizzati e problemi decisionali. Modelli di programmazione lineare e lineare intera. Soluzione di problemi di ottimizzazione con un foglio di calcolo. Applicazioni. Richiami di analisi convessa e algebra lineare. Teoria della programmazione lineare, risoluzione geometrica e algoritmo del simplesso. Teoria della dualità: motivazioni, risultati principali, significato economico delle variabili duali. Algoritmo del simplesso duale e revisionato. Analisi di sensitività. Problemi di ottimizzazione dei tagli: formulazioni in termini di programmazione lineare intera e metodi di generazione di colonne.
- Programma dettagliato
Cosa significa Ricerca Operativa
Origini storiche e evoluzione
Settori applicativi; un esempio di mix produttivo
Le tre parole chiave: metodi quantitativi, problemi decisionali, sistemi organizzati
Metodi per lo studio dei sistemi: modelli matematici e di simulazione
I modelli matematici come paradigma dichiarativo
Tassonomia dei problemi decisionali: problemi multi-obiettivo, teoria delle decisioni, teoria dei giochi
Programmazione matematica: definizioni preliminari e tassonomia
Programmazione Lineare: ipotesi di applicabilità
Dal problema al modello: esempio con il problema dello zaino 0-1
Dal modello alla soluzione: metodi esatti, approssimati, euristici; metodi per la PL e per la PLI
Cenni di complessità computazionale: problemi facili e difficili; algoritmi polinomiali e esponenziali
Notazione e definizioni di base
Richiami di algebra lineare: vettori, combinazioni lineari, spazi lineari, indipendenza lineare, basi, trasformazioni lineari e matrici, operazioni su matrici, matrici particolari, determinante di una matrice, proprietà del determinante
Esempi: un problema di PL in R^2 e un modello di mix-produttivo
Algoritmo geometrico del Simplesso
Combinazione affine, conica e convessa; funzioni convesse e insiemi convessi; involucro convesso, ottimizzazione convessa.
Soluzioni di un problema di PL: ottimo finito, problema inammissibile, problema illimitato
Equivalenza tra problemi di PL e regole di trasformazione; forma Generale e forma Standard
Geometria della PL: iperpiani, semispazi, poliedri e politopi, disuguaglianze valide, vertici, spigoli, facce
Teorema di rappresentazione interna: caso limitato
Direzioni di un poliedro e cono di recessione; rette di un poliedro
Teorema di rappresentazione interna: caso generale
Teorema fondamentale della PL
Richiami sui sistemi di equazioni lineari: compatibilità, teorema di Rouché-Capelli, regola di Cramer, operazioni elementari, metodo di Gauss-Jordan, esempi.
Matrice di base, variabili di base e fuori base, soluzioni di base e soluzioni di base ammissibili (SBA)
Caratterizzazione analitica dei vertici, vertici e SBA, SBA degeneri: esempi e interpretazione geometrica
Algoritmi iterativi di ottimizzazione
Direzione ammissibile e migliorante
Ricerca iterativa e algoritmo del simplesso (perchè funziona?)
Descrizione geometrica: determinazione di una direzione migliorante, scelta di una direzione ammissibile, calcolo della nuova soluzione
Descrizione analitica: problema ridotto, forma canonica e vettore dei costi ridotti, tabella canonica, criterio di ottimalità, criterio di illimitatezza, cambiamento di base, operazione di pivot (esempi), scelta della colonna di pivot, scelta della riga di pivot, significato geometrico, ciclaggio e regola di Bland
Fase II dell'algoritmo del simplesso, esempio. Complessità e congettura di Hirsch. Fase I dell'algoritmo del simplesso
Simplesso revisionato: motivazione, matrice carry, esempi.
Software di ottimizzazione, ambienti integrati general purpose e software verticalizzati
Funzionalità dei software general purpose
Problema della Dieta: soluzione con Excel
Combinazioni coniche e disuguaglianze valide
Limitazioni inferiori e superiori, bound primali e duali
Rilassamento di un problema: definizione e proprietà
Dualità: motivazione, stima dell'errore, calcolo di un bound duale utilizzando combinazioni coniche dei vincoli
Problema duale e metodo dei moltiplicatori di Lagrange nella PL
Regole generali per la costruzione del duale
Alcuni problemi duali notevoli: problema della dieta, problema di mix di produzione, problema di trasporto
Teoria della dualità: reciprocità, dualità debole e corollari, dualità forte e corollari, condizioni di ortogonalità
gap di dualità nei modelli di PLI: esempio di insieme stabile e copertura con archi
Informazioni duali sul tableau del simplesso
Dualità per stabilire condizioni di ottimalità: problema dello zaino 0-1, bound di Dantzig, dimostrazione di correttezza
Il simplesso duale: motivazione, idea generale, tabella canonica, criterio di ottimalità, scelta della riga e della colonna di pivot, criterio di illimitatezza, esempio di esecuzione.
Analisi post-ottimale: motivazione
variazione dei coeff. della f.o.: interpretazione geometrica, calcolo analitico e interpretazione; coefficienti critici e non
variazione dei termini noti: interpretazione geometrica, calcolo analitico e interpretazione. Esempi
Interpretazione economica: variabili duali come costi marginali, il caso del mix produttivo
Livelli di pianificazione: strategico, tattico e operativo.
problema della dieta e di miscelazione
problema di trasporto
pianificazione degli investimenti
mix produttivo
assegnamento di risorse
Testi di riferimento e
materiale didattico integrativo
Libri di testo e esercizi:
C. Vercellis, Ottimizzazione. Teoria, metodi, applicazioni, Mc Graw-Hill, 2008
S. Martello, D. Vigo, Esercizi di Ricerca Operativa, Progetto Leonardo, Bologna, 2001Approfondimento:
D. Bertsimas and J.N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, Belmont, MassachusettsMateriale didattico integrativo
Gli appunti e le slide utilizzate a lezione sono disponibili in una cartella condivisa su DropBox. Iscriviti (specificando nome e corso).
Si può partecipare a discussioni sugli argomenti del corso iscrivendosi alla community Ricerca Operativa Fermo su Google+.
Modalità e temi di esame
L'esame consiste in una prova scritta costituita da una prima parte con 7 domande a risposta chiusa (da -7 a 14 punti) e una seconda parte con uno o due esercizi (16 punti), e in una prova orale sui contenuti del corso.
Gli studenti possono guadagnare l'esonero dalla seconda parte dello scritto risolvendo (individualmente o in coppia) uno dei problemi proposti. Saranno esonerati gli studenti che ottengono il miglior risultato e che presentano adeguatamente i risultati a lezione (con data da concordare).
Appelli
Importante: l'iscrizione all'appello dovrà essere fatta inserendo nome cognome e matricola nell'elenco appelloggmmaa.txt presente nella cartella DropBox (accessibile previa iscrizione). Le iscrizioni si chiudono una settimana prima della data di appello.16 gennaio 2013 - Prova scritta 09:30 - Prova orale a seguire
10 aprile 2013 -Prova scritta 09:30 - Prova orale a seguire
18 giugno 2013 -Prova scritta 09:30 - Prova orale a seguire
16 luglio 2013 -Prova scritta 09:30 - Prova orale a seguire
02 ottobre 2013 - Prova scritta 09:30 - Prova orale a seguire
19 novembre 2013 - Prova scritta 09:30 - Prova orale a seguire
Bacheca
Link
utili