Funzioni reali di variabili reali. Algebra delle matrici. Sistemi di equazioni lineari
La Ricerca Operativa è un settore della matematica applicata che si occupa di modellare quantitativamente problemi complessi per supportare le decisioni strategiche, tattiche e operative in vari ambiti applicativi. Scopo del corso è fornire le principali metodologie della Ricerca Operativa per la soluzione di problemi decisionali: ottimizzazione lineare e intera e algoritmi risolutivi, teoria della dualità, analisi di sensitività, ottimizzazione su reti, introduzione alla programmazione stocastica e alla programmazione dinamica. I problemi oggetto di studio comprendono i sistemi di produzione, trasporto, distribuzione e supporto logistico di beni e servizi, la pianificazione, organizzazione e gestione di attività. Il corso si propone inoltre di fornire conoscenze relative all’utilizzo di GAMS, linguaggio di modellizzazione matematica per la soluzione di modelli di ottimizzazione.
Al termine del corso lo studente sarà in grado di:
• Comprendere l’impostazione concettuale della Ricerca Operativa quale strumento per formulare, risolvere e valutare problemi di decisione relativi a sistemi complessi;
• Conoscere le metodologie di formalizzazione dei modelli quantitativi e di soluzione algoritmica dei problemi;
• Comprendere gli aspetti teorici alla base delle tecniche di soluzione, le loro giustificazioni matematiche, le loro implicazioni e potenzialità applicative;
• Applicare in concreto le tecniche di soluzione e gli algoritmi, eseguendo le procedure necessarie per ottenere la soluzione di problemi decisionali in ambito ingegneristico e manageriale;
• Analizzare criticamente le soluzioni ottenute fornendone un’interpretazione economica;
• Applicare le conoscenze acquisite per arrivare autonomamente a formulare modelli quantitativi e successivamente a risolvere i relativi problemi di ottimizzazione utilizzando gli opportuni algoritmi risolutivi;
• Utilizzare l’ambiente di modellazione GAMS per la codifica dei modelli formulati e la loro risoluzione.
Introduzione alla ricerca operativa
o Problemi di decisione. Esempi.
o Ambiti di applicazione: manifatturiero, logistica, trasporti, localizzazione. Esempi.
o Altri ambiti di applicazione: economia, finanza, servizi sanitari, pubblica amministrazione. Esempi.
• Programmazione lineare (PL)
o Formulazione di problemi di PL.
o Geometria della PL: definizione di politopo, vertici e soluzioni di base ammissibile.
o Algoritmo del simplesso.
o Teoria della dualità e interpretazione economica.
o Algoritmo del simplesso duale.
o Analisi di sensitività e post-ottimalità nella PL.
• Ottimizzazione intera
o Teoria della Programmazione Intera.
o Proprietà di Interezza e Unimodularità di Matrici (UM e TUM).
o Alberi di ricerca e algoritmo del Branch-and-Bound.
o Tagli di Gomory.
o Problema dello zaino e algoritmi risolutivi.
o Problemi di assegnamento e trasporto.
• Ottimizzazione su grafi
o Mimino albero ricoprente e algoritmo di Prim.
o Problema del Percorso minimo e Algoritmo di Dijkstra.
o Problema del flusso massimo e Algoritmo di Ford-Fulkerson.
o Il problema del commesso viaggiatore
• Introduzione alla programmazione dinamica.
• Cenni alla programmazione stocastica e sue applicazioni.
Il corso sarà organizzato in lezioni frontali, esercitazioni e tutorato comprensive dello svolgimento di esempi e della risoluzione degli esercizi assegnati. Alcune lezioni si svolgeranno presso il laboratorio informatico in cui verranno implementati modelli di ottimizzazione tramite linguaggi di programmazione matematica (GAMS).
L'esame si svolge in due parti: una prova scritta e una prova orale. La prova scritta prevede la risoluzione di esercizi inerenti il programma uno dei quali consiste nella modellizzazione e implementazione in linguaggio GAMS di un problema di ottimizzazione. L’esame orale è volto a valutare capacità di ragionamento e proprietà di linguaggio sui temi oggetto del corso.
Lo studente è ammesso alla prova orale se consegue un punteggio di almeno 18/30 nella prova scritta. La prova orale è facoltativa.
Materiale relativo al corso verrà inserito dal docente tramite la piattaforma "e-learning" dell'Università degli studi di Bergamo.
Qualora l'insegnamento venisse impartito in modalità mista o a distanza potranno essere introdotte modifiche rispetto a quanto dichiarato nel syllabus per rendere il corso e gli esami fruibili anche secondo
queste modalità.
Per maggiori informazioni scrivere a: francesca.maggioni@unibg.it
Real functions of real variables. Matrix algebra. Systems of linear equations.
This course provides a rigorous introduction to the theory and applications of linear, discrete and stochastic programming to engineering. In terms of theory, the student will learn the structural properties and state-of-the-art solution algorithms to solve decision problems. From a practical viewpoint, the student will learn how to model real- world problems as optimization models and how to interpret their solutions computed via commercial package programs.
Topics covered include the simplex method, duality in linear programming, sensitivity analysis, network-type problems, integer programming, stochastic programming and dynamic programming.
In terms of applications, decision problems from widely different contexts are considered: manufacturing industry, transportation, finance, health, energy, network models. At the end of the course the student will be also able to realize simple GAMS coding for solving the considered decision problems.
At the end of the course the student will be able to:
• Understand the conceptual approach of Operations Research as a tool to formulate, solve and evaluate decision problems relating to complex systems.
• Understand the structural properties and state-of-the-art solution algorithms to solve decision problems.
• Model real-world problems as optimization models.
• Interpret the solution computed via commercial package programs and provide its economic interpretation.
• Implement a mathematical model in the GAMS environment.
• Introduction to Operational Research
o Linear (integer) programming models for real case applications
Blending of products, assignment of machining operations, the transportation problem, the diet problem, the assignment problem, the scheduling problem. Examples.
• Linear programming (LP)
o Formulations and equivalent forms.
o Geometry of linear programming: vertices and basic solutions.
o Simplex method.
o Duality in linear programming and economic interpretation.
o The dual simplex method.
o Sensitivity analysis and post-optimality in linear programming.
• Integer linear programming
o Theory of linear integer programming.
o Total unimodularity (UM and TUM).
o Branch and bound algorithm.
o Gomory cuts.
o The knapsack problem and algorithms.
o The transportation and assignment problems.
• Graph theory
o Minimum spanning trees and Prim’s algorithm.
o Shortest path problem and Dijkstra’s algorithm.
o Max flow problem and Ford-Fulckerson’s algorithm.
o The traveling salesman problem.
• Introduction to dynamic programming.
• Introduction to stochastic programming and applications.
The course will consist of lectures based on traditional teaching including theory, exercises and tutoring. Some of the lectures will be based on exercise sessions in GAMS using PC-labs.
The final exam is based on a written test followed by an oral interview. The written test is composed of exercises, one of which based on modeling and implementing under GAMS environment a real case problem. The oral exam is aimed at assessing the knowledge of the theory covered by the course. To be admitted to the oral exam, the student must get a grade not less than 18/30 in the written test. The oral test is optional.
The course material will be provided by means of the e-learning platform of the University of Bergamo.
If the teaching activity will be mixed or in remote mode, changes can be done compared to what stated in the syllabus, to make the course and the exams available also in these modalities.
For more details write to: francesca.maggioni@unibg.it