Scheda programma d'esame
RICERCA OPERATIVA
MARIA GRAZIA SCUTELLA'
Anno accademico2021/22
CdSMATEMATICA
Codice072AA
CFU6
PeriodoPrimo semestre
LinguaItaliano

ModuliSettore/iTipoOreDocente/i
RICERCA OPERATIVAMAT/09LEZIONI60
MARIA GRAZIA SCUTELLA' unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

Il corso presenta i principali aspetti teorici e pratici relativi alla definizione e alla risoluzione di modelli matematici di ottimizzazione per problemi reali. In particolare, vengono introdotte proprietà matematiche di base e alcune delle principali tecniche algoritmiche per la risoluzione di tre grandi famiglie di problemi di ottimizzazione: i problemi di Programmazione Lineare, i Problemi di flusso su rete e i problemi di Programmazione Lineare Intera.

 

Knowledge

The course will introduce the student to the main mathematical properties and algorithmic approaches of Operations Research, the discipline aiming at formulating and solving mathematical models for decision problems stated in an optimization form. At the end of the course the student will know the mathematical foundations and some relevant solution algorithms for two important classes of "easy" problems, that is Network Flow problems and Linear Programming. Furthermore, she/he will be able to formulate "hard" optimization problems via Integer Linear Programming, and to solve them by exploiting some relevant mathematical properties of this class of problems.

 

Modalità di verifica delle conoscenze

La verifica delle conoscenze avverrà attraverso la valutazione dell'elaborato scritto e attraverso la valutazione delle risposte fornite in sede di prova orale. Verranno inoltre stimolate domande da parte degli studenti nel corso delle lezioni, per una verifica in itinere. 

 

Assessment criteria of knowledge

Through the written and the oral examination. Moreover, a discussion with the students will be stimulated during the lessons, to assess the acquired knowledge also in real time.

 

 

Capacità

Al termine del corso lo studente sarà in grado di formulare e risolvere problemi di ottimizzazione appartenenti alle classi studiate nel corso, ovvero Programmazione Lineare, Problemi di flusso su rete e Programmazione Lineare Intera.

 

Skills

At the end of the course the student will be able to formulate and solve optimization problems belonging to the classes studied in the course, i.e. Linear Programming, Network flow problems and Integer Linear Programming.

 

 

Modalità di verifica delle capacità

La verifica delle capacità acquisite avverrà attraverso l'analisi delle risposte fornite in sede di elaborato scritto e in sede di prova orale.

 

Assessment criteria of skills

All the skills will be assessed during the written and the oral examination.

Comportamenti

Saranno acquisite abilità di modellazione matematica e di risoluzione algoritmica di problemi di ottimizzazione.

 

Behaviors

Capabilities of mathematical modelling and solving optimization problems via efficient algorithmic approaches will be achieved.

 

 

Modalità di verifica dei comportamenti

Le abilità di modellazione matematica e di risoluzione algoritmica verranno verificate, oltre che in sede d'esame, nel corso delle esercitazioni in classe.

 

Assessment criteria of behaviors

All the behaviors will be assessed during the written and the oral examination, and through class exercises.

Prerequisiti (conoscenze iniziali)

Sono consigliate conoscenze di base di analisi matematica, geometria e algebra lineare.

Si assume inoltre una conoscenza di base dei concetti di algoritmo e di analisi della sua complessità computazionale.

Prerequisites

A basic knowledge of analysis, geometry and linear algebra is recommended.

Moreover, a basic knowledge of the concepts of algorithm and computational complexity is assumed.

 

 

Indicazioni metodologiche

Gli argomenti del corso verranno presentati tramite lezioni, con il supporto di esercitazioni. 

Teaching methods

Teaching methods:

  • Lectures
  • Exercises

 

 

 

Programma (contenuti dell'insegnamento)
  1. Problemi e modelli (4 ore)

    • Problemi decisionali, di ottimizzazione e di esistenza
    • Esempi di problemi di ottimizzazione

    Programmazione Lineare (PL) (20 ore)

    • Problemi e modelli di PL
    • Geometria della PL: poliedri e loro rappresentazione
    • Teoria matematica della dualità
    • Algoritmo del simplesso primale e sua interpretazione geometrica
    • Teorema degli scarti complementari
    • Algoritmo del simplesso duale e sua interpretazione geometrica

    Problemi di flusso su rete (16 ore)

    • Problemi e modelli di PL su reti
    • Cammini minimi
    • Flusso massimo
    • Flusso di costo minimo

    Programmazione Lineare Intera (PLI) (20 ore)

    • Problemi e modelli di Ottimizzazione Combinatoria e di PLI
    • Tecniche di modellazione
    • Tecniche di dimostrazione di ottimalità
    • Algoritmi euristici
    • Tecniche di rilassamento
    • Algoritmi enumerativi  

     

Syllabus

Problems and models (4 hours)

  • Decision problems, optimization problems, feasibility problems
  • Examples of optimization problems

Linear Programming (LP) (20 hours)

  • LP problems and models
  • Geometry of LP: polyhedra and their representation
  • Duality theory in LP
  • Primal Simplex algorithm with related geometrical interpretation
  • Complementary Slackness Theorem
  • Dual Simplex algorithm with related geometrical interpretation

Network flow problems (16 hours)

  • LP problems and models on networks
  • Shortest paths
  • Maximum flow
  • Minimum cost flow

Integer Linear Programming (ILP) (20 hours)

  • Combinatorial Optimization and ILP: problems and models
  • Modelling techniques
  • Proof of optimality
  • Heuristic algorithms
  • Relaxations
  • Enumerative algorithms  

 

 

Bibliografia e materiale didattico

Appunti di Ricerca Operativa e prove d'esame (con e senza svolgimento) sono disponibili sulla pagina web del corso:

http://didawiki.di.unipi.it/doku.php/matematica/ro/start

 

Testi di consultazione consigliati:

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

  2. Massimo Pappalardo, Mauro Passacantando "Ricerca Operativa", Plus, 2010

Bibliography

Appunti di Ricerca Operativa, exam exercises (with and without solution): available on the web page of the course.

 

Suggested:

  1. F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa", Franco Angeli, Milano (1999)

  2. Massimo Pappalardo, Mauro Passacantando "Ricerca Operativa", Plus, 2010

Indicazioni per non frequentanti

Si consiglia di contattare il docente.

Non-attending students info

Please contact the teacher.

Modalità d'esame

Prova scritta seguita da una prova orale. La prova scritta dura tre ore, consta di sei esercizi, e copre tutti gli argomenti trattati durante il corso. Durante la prova scritta non è possibile consultare libri o appunti. 

I contenuti della prova d'esame sono quelli presentati durante l'anno accademico a cui si riferisce l'appello, anche per gli studenti che avessero seguito il corso in anni precedenti.

La prova orale viene effettuata nello stesso appello della prova scritta, normalmente nei giorni immediatamente successivi a quelli di pubblicazione dell'esito della prova scritta.

 

Assessment methods

Written exam followed by an oral exam. The written exam, of 3 hours, consists of 6 exercises, and covers all of the topics of the course. Textbooks and student notes are forbidden during the written exam.

Both the written and the oral exams refer to the topics of the current academic year, also for those students who attended the course in previous years.

The oral exam is performed jointly with the written exam, usually a few days later the date of publication of the results of the written exam.

 

Ultimo aggiornamento 19/07/2021 09:12