RICERCA OPERATIVA | Università degli studi di Bergamo

RICERCA OPERATIVA

Modulo Generico
Codice dell'attività formativa: 
22015-2

Scheda dell'insegnamento

Per studenti immatricolati al 1° anno a.a.: 
2020/2021
Insegnamento (nome in italiano): 
RICERCA OPERATIVA
Tipo di attività formativa: 
Attività formativa di Base
Tipo di insegnamento: 
Obbligatoria
Settore disciplinare: 
RICERCA OPERATIVA (MAT/09)
Anno di corso: 
2
Anno accademico di offerta: 
2021/2022
Crediti: 
6
Responsabile della didattica: 
Altri docenti: 

Altre informazioni sull'insegnamento

Modalità di erogazione: 
Didattica Convenzionale
Lingua: 
Italiano
Ciclo: 
Primo Semestre
Obbligo di frequenza: 
No
Ore di attività frontale: 
48
Ambito: 
Matematica, informatica e statistica
Prerequisiti

Funzioni reali di variabili reali. Algebra delle matrici. Sistemi di equazioni lineari

Obiettivi formativi

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.

Contenuti dell'insegnamento

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.

Metodi didattici

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

Modalità verifica profitto e valutazione

L'esame si svolge in due parti entrambe obbligatorie per tutti gli studenti: una prova scritta e una prova orale. La prova scritta prevede la risoluzione di 4 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.
Le domande della prova scritta saranno valutate con un punteggio da 0 (in caso di mancata risposta) a 7 (in caso di risposta ineccepibile) ad eccezione dell’esercizio di modellizzazione e implementazione in linguaggio GAMS che verrà valutato con un punteggio da 0 a 9. Lo studente è ammesso alla prova orale se consegue un punteggio di almeno di 15/30 nella prova scritta. Il voto finale è unico e tiene conto per il 60% della valutazione della prova scritta per il 40% del colloquio orale.

Altre informazioni

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

Prerequisites

Real functions of real variables. Matrix algebra. Systems of linear equations.

Educational goals

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.

Course content

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

Teaching methods

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.

Assessment and Evaluation

The final exam is based on a written test followed by an oral interview. The written test is composed of 4 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. The questions of the written test will be evaluated with a score from 0 to 7 with exception of the exercise in GAMS (from 0 to 9). To be admitted to the oral exam, the student must get a grade not less than 15/30 in the written test. The final mark takes into account both the parts of the exam (60% of the written and 40% of the oral).

Further information

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