ECTS - University of Pisa
| Modules | Area | Type | Hours | Teacher(s) | |
| 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.
Ad oggi non si sa se l'emergenza covid terminerà nei prossimi mesi. Qualora si tornasse alla piena normalità la verifica consiste di prova scritta e prova orale. Qualora ciò non fosse possibile la prova scritta verrà inglobata nella prova orale a distanza.
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:
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.
Elementi di algebra lineare: operazioni tra matrici. rango, determinante ed inversa di una matrice.
Indipendenza lineare, sistemi lineari e loro risoluzione.
Calculo 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 o virtuali alla lavagna. Periodiche verifiche per la valutazione dell'apprendimento raggiunto.
La frequenza, seppur non obbligatoria, è fortemente raccomandata.
Delivery: face to face
Learning activities:
Attendance: Advised
Teaching methods:
Formulazione di problemi di ottimizzazione: dati, variabili, vincoli. Problemi di produzione, di trasporto, di assegnamento. Variabili discrete e continue. Modelli standard per software esistenti. 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 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.
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. 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.
Si può anche consultare proficuamente:
Pappalardo M., Passacantando M., “Ricerca Operativa”, Pisa University Press.
F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa", Franco Angeli.
Usare il registro delle lezioni, il materiale didattico caricato sulla pagina web del docente, 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.
Qualora proseguissel'emergenza sanitaria COVID-19, gli esami si svolgeranno a distanza e saranno formati dalla sola prova orale (durante la quale potrà essere richiesto lo svolgimento di esercizi).
Written and oral exam.
Non previsti
