CdSINGEGNERIA INFORMATICA
Codice170AA
CFU9
PeriodoSecondo semestre
LinguaItaliano
| Moduli | Settore/i | Tipo | Ore | Docente/i | |
| RICERCA OPERATIVA | MAT/09 | LEZIONI | 90 |
|
Il corso si prefigge l'obiettivo di guidare lo studente nella formulazione di modelli matematici per problemi di ottimizzazione lineare (discreta e continua) e non lineare a risorse limitate (vincoli), e di illustrare tecniche algoritmiche per la loro risoluzione.
Lo studente acquisirà competenze che gli permetteranno di formulare modelli di ottimizzazione lineare continua e discreta, compresi quelli di flusso su reti, e non lineare. Apprenderà inoltre proprietà matematiche che lo condurranno alla progettazione di approcci algoritmici di base per importanti classi di problemi di ottimizzazione: problemi di flusso su rete, programmazione lineare, ottimizzazione non lineare non vincolata e vincolata.
The student who successfully completes the course will be able to demonstrate a solid knowledge of the methodologies and algorithms concerning solution of basic optimization problems. He/she will acquire ability in formulation of mathematical models of decisional problems. The student will also be aware of the basic theory of optimization.
La verifica consiste di una prova scritta e prova orale.
Durante la prova scritta lo studente deve risolvere esercizi che mostreranno l'abilità acquisita nell'eseguire correttamente alcuni passi degli algoritmi proposti a lezione e nel saper formulare matematicamente un problema di decisione ottima.
Durante la prova orale lo studente deve mostrare di conoscere la base teorica con cui sono costruiti gli algoritmi presentati e mostrare di aver capito le idee alla base dei medesimi algoritmi.
During the written exam (2.5 hours) the student is asked to solve exercises in order to demonstrate the ability to put into practice the basic algorithms of linear and non linear optimization. During the oral exam the student will be assessed on his/her ability to approach problems and to know theory about the described optimization models.
Methods:
- Final oral exam
- Final written exam
Further information:
The final test is composed by a written exam followed by an oral exam. Both each part contributes 50% to the definition of the final grade.
Lo studente sarà in grado di formulare modelli matematici per alcuni problemi applicativi, risolvere problemi di flusso su rete, problemi di programmazione lineare continua e discreta e di programmazione non lineare. Una parte del corso è dedicata alla programmazione lineare intera ed ai suoi metodi risolutivi. La parte finale coprirà l'ottimizzazione continua e i suoi principali metodi risolutivi.
The student will be able to formulate mathematical models of linear optimization both continuous and discrete. Particula emphasis will be devoted to symplex methods in classical format or in neworks variant. A part of the course will be dedicated to integer linear programming while the final part will cover continuous optimization both unconstrained and constrained.
Tramite l'esame finale.
L'insegnamento ha l'obiettivo di rendere consapevoli gli studenti del corretto utilizzo dei metodi edegli algoritmi di ottimizzazione.
The course aims to make students aware of the correct use oth optimization methods.
La verifica avviene con l'esame finale.
Verificaton takes place with the final exam.
Elementi di algebra lineare: operazioni tra matrici, rango, determinante ed inversa di una matrice. Indipendenza lineare, sistemi lineari e loro risoluzione.
Calcolo per funzioni reali di più variabili: gradiente, derivata direzionale, hessiana, massimi e minimi liberi.
Fundamentals of linear algebra, algorithmics and calculus in several variables
Lezioni frontali. Periodiche verifiche in classe per la valutazione dell'apprendimento raggiunto.
La frequenza, seppur non obbligatoria, è fortemente raccomandata.
Delivery: face to face
Learning activities:
- attending lectures
- individual study
Attendance: Advised
Teaching methods:
- Lectures
Formulazione di problemi di ottimizzazione: dati, variabili, vincoli. Problemi di produzione, di trasporto, di assegnamento. Variabili discrete e continue. Modelli standard per software matlab. Programmazione Lineare. Soluzioni ammissibili ed ottime. Poledri e loro rappresentazione geometrica e matriciale. Teorema fondamentale della PL. Soluzioni di base e vertici. Teoria della dualità e test di ottimalità. Algoritmo del simplesso primale. Algoritmo del simplesso duale. Il problema ausiliario. Il caso delle variabili intere e binarie. Le valutazioni superiori ed inferiori. Algoritmi "greedy". Il metodo dei piani di taglio. Piani di taglio di Gomory.
Problemi su reti. Cammini minimi, flusso massimo, flusso di costo minimo. Matrici di incidenza, capacità, costi, bilanci. Alberi di copertura e basi. Poliedro dei flussi. Flussi di base su reti non capacitate e capacitate. La tecnica della tripartizione degli archi. Problema dei potenziali. Potenziali di base. Teorema di Bellman. Algoritmo del simplesso su reti non capacitate; algoritmo del simplesso su reti capacitate. L'algoritmo di Ford-Fulkerson. L'algoritmo di Dijkstra.
Il metodo del "Branch and Bound". Il problema dello zaino, il problema del "bin-packing", il problema del "commesso viaggiatore" ed i problemi di "copertura".
Metodi di ottimizzazione continua non vincolata: discesa e gradiente. La teoria di Lagrange-Kuhn-Tucker per l'ottimizzazione vincolata. Il caso convesso. Metodi di ottimizzazione vincolata: metodo del gradiente proiettato e metodo di Frank-Wolfe.
Mathematical models for optimization decisional problems. Linear Programming and simplex algorithm. Network flow problems, solution methods and algorithms: minimum cost, shortest path, maximum flow. Discrete optimization: "branch and bound", cutting planes. Traveling salesman problem and knapsack problem. Unconstrained continuous optimization: gradient and descent methods. Theory and methods of continuous constrained optimization.
- M.Pappalardo-M.Passacantando, Ricerca Operativa, Casa Editrice Pisa University Press.
- Slides del docente disponibili in rete
Si può anche consultare proficuamente:
- F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa", Franco Angeli.
Pappalardo M., Passacantando M., “Ricerca Operativa”, Pisa University Press.
Slides provided by the teacher.
F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa", Franco Angeli.
Consultare il registro delle lezioni, il materiale didattico caricato sulla pagina teams del corso, il testo suggerito ed il ricevimento studenti.
Prova scritta della durata di due ore composta da 4 esercizi/problemi, seguita da una prova orale. E' fortemente consigliato aver superato la prova scritta prima di accedere alla prova orale.
Written and oral exam.
Non previsti