Scheda programma d'esame
OPERATIONS RESEARCH 1
GIANDOMENICO MASTROENI
Academic year2022/23
CourseENGINEERING MANAGEMENT
Code162AA
Credits6
PeriodSemester 1
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
RICERCA OPERATIVA IMAT/09LEZIONI60
GIANDOMENICO MASTROENI unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

Formulazione di modelli matematici mediante problemi di programmazione lineare.

Algoritmi risolutivi per problemi di programmazione lineare astratta e su grafi.

Knowledge

Mathematical formulations of mathematical models by means of linear programming.

Modalità di verifica delle conoscenze

Esame scritto e orale

Assessment criteria of knowledge

Oral and written exam.

Capacità

Lo studente deve essere in grado di formulare e risolvere opportuni problemi reali di carattere gestionale mediante modelli matematici dati da problemi di programmazione lineare.

Skills

Formulations of management real problems by means of linear programming.

Modalità di verifica delle capacità

Esercitazioni in presenza ed in modalità telematica.

Assessment criteria of skills

Online and classroom exercitations.

Prerequisiti (conoscenze iniziali)

Algebra lineare e nozioni di analisi di funzioni di una variabile.

Prerequisites

Linear algebra and basic mathematical analysis notions.

Programma (contenuti dell'insegnamento)

1. Introduzione ai problemi di Ricerca Operativa. Formulazioni matematiche di alcune situazioni reali. Un problema di programmazione dei trasporti. Problemi di produzione. Problemi di miscelazione ottimale. Problemi di flusso su reti. Il problema del cammino minimo. Problemi di flusso di costo minimo.

 2. Programmazione lineare. Elementi di analisi convessa: insiemi convessi, involucro convesso, combinazioni convesse, coni. Geometria della programmazione lineare (PL). Proprieta' dei poliedri. Vertici e direzioni di recessione di un poliedro. Teorema di rappresentazione dei poliedri (senza dimostrazione). Risoluzione geometrica della PL. Metodo delle curve di livello.
Teorema fondamentale della PL. Teoria della dualita'. Dualita' debole, dualita' forte. Teorema degli scarti complementari.
Soluzioni di base degeneri, non degeneri e complementari. Algoritmo del simplesso primale e duale.
Il problema ausiliario per la determinazione di una prima base duale ammissibile. Interpretazione economica del problema duale associato ad un problema di produzione. 


3. Programmazione lineare su grafi. Alcuni elementi di teoria dei grafi: cammini, cicli, alberi di copertura, matrici associate ad un grafo: la matrice di incidenza.
Il problema del flusso di costo minimo, principali proprieta': esistenza di una soluzione ottima, teorema dell'interezza delle soluzioni di base.
L'algoritmo del simplesso su reti per il problema del flusso di costo minimo senza capacita' superiori sugli archi. 
L'algoritmo del simplesso su reti per il problema del flusso di costo minimo con capacita' superiori sugli archi. 
Il problema della ricerca dell'albero dei cammini di costo minimo. Formulazione come problema di flusso di costo minimo, condizioni di esistenza di una soluzione ottima, algoritmo SPT. L'algoritmo di Dijkstra per il problema dell'albero dei cammini minimi con costi positivi sugli archi. Convergenza e complessita'. Il duale del problema dell'albero dei cammini minimi: connessioni con le condizioni di esistenza della soluzione ottima del problema e con l' algoritmo SPT.
Problema del flusso massimo: formulazione, teorema max-flow-min-cut, algoritmo di Ford-Fulkerson, algoritmo di Edmons-Karp per la ricerca del cammino aumentante. Problema duale del problema del flusso massimo: relazioni con il problema della ricerca del taglio di capacit\'a minima. Teorema max flow-min cut.

4. Laboratorio. Risoluzione di un problema di programmazione lineare tramite i programma Matlab. I comandi 'linprog' e 'intlinprog'. Analisi dei risultati.

Syllabus

1. Introduction to Operations Research.   Mathematial formulations of real problems. Transportation problems. Production problems.Minimum cost flow problems.  

 2. Linear Programming. Elements of  convex analysis:  convex sets, convex hull, convex combinations, cones. Polyhedra. Vertexes  and recession directions. Theorem of repesetation of polyhedra.
Existence of solutions for a linear programming (LP). Duality theory: weak and strong duality. Theorem of complementarity slackness. Basic solutions, primal and dual simplex algorithm.   

3. Linear Programming on graphs. Elements of graph theory: paths, cycles, trees and spanning trees,  matrices associated with graphs.
The minimum cost flow problem, symplex algorithm for the minimum cost flow problem.The Shortest-path tree problem: Dijkstra algorithm. The maximum flow problem: Edmonds-Karp and Ford-Fulkerson algorithms, cuts, theorem max flow-min cut.

4. Laboratory.  Matlab solution of a linear programming problem. Use of the commands 'linprog' and 'intlinprog'. 

Bibliografia e materiale didattico

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

Modalità d'esame

Prova scritta e orale

Updated: 03/08/2022 10:01