Scheda programma d'esame
OPERATIONAL RESEARCH
MASSIMO PAPPALARDO
Academic year2020/21
CourseCOMPUTER ENGINEERING
Code170AA
Credits9
PeriodSemester 2
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
RICERCA OPERATIVAMAT/09LEZIONI90
MASSIMO PAPPALARDO unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

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.

Knowledge

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.

Modalità di verifica delle conoscenze

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.

Assessment criteria of knowledge

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.

Capacità

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.

Skills

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.

Modalità di verifica delle capacità

Tramite l'esame finale.

Prerequisiti (conoscenze iniziali)

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.

Prerequisites

Fundamentals of linear algebra, algorithmics and calculus in several variables

Indicazioni metodologiche

Lezioni frontali o virtuali alla lavagna. Periodiche verifiche per la valutazione dell'apprendimento raggiunto. 

La frequenza, seppur non obbligatoria, è fortemente raccomandata.

Teaching methods

Delivery: face to face

Learning activities:

  • attending lectures
  • individual study

Attendance: Advised

Teaching methods:

  • Lectures
Programma (contenuti dell'insegnamento)

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.

Syllabus

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.

Bibliografia e materiale didattico
  • 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.
Bibliography

Pappalardo M., Passacantando M., “Ricerca Operativa”, Pisa University Press.

F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa", Franco Angeli.

Indicazioni per non frequentanti

Usare il registro delle lezioni, il materiale didattico caricato sulla pagina web del docente, il testo suggerito ed il ricevimento studenti.

Modalità d'esame

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

Assessment methods

Written and oral exam.

Altri riferimenti web

Non previsti

Updated: 31/07/2020 15:51