Operations Research

Programma dell'insegnamento - Corso di laurea in Informatica Magistrale internazionale

Docente/Lecturer

Prof. Paolo serafini

Indirizzo e-mail
paolo.serafini@uniud.it

Indirizzo Pagina Web Personale

http://users.dimi.uniud.it/~paolo.serafini/ROINF****.html

Crediti

6 CFU

The course is held in English

Aims

Operations Research deals with efficient management problems via a mathematical and algorithmic approach. The course aims at giving the student both the basic tools to design a viable mathematical model of a real problem and the necessary understanding of the mathematical and algorithmic properties of the models, with a special emphasis to linear programming. Several examples will be provided toward this goal. Most models will be solved by using Excel or other linear programming packages.

Program

- Introduction to linear programming
- General modelling issues: constraint identification, soft and hard constraints; objective identification; objectives and constraints. Explicit objectives. Pareto optima.
Example of the diet problem: modelling via linear programming. Sensitivity analysis. Identification of further objectives. Efficient frontier identification. Integrality constraints. Model refinement.

- Linear programming properties . Geometric structure. Vertices and basis solutions. Dual problem. Complementarity. Overview of simplex method. Overview of branch-and-bound methods for integer variables.

- Routing models . Dynamic programming. Optimality principle. Recursive equation. Shortest paths (Bellman-Ford, Dijkstra, Floyd-Warshall).

- Routing models with capacities. Capacitated shortest paths: network flow problems. Minimum cost flows. Max Flow. Minimum cuts. Examples of applications to electoral seat assignment.

- Routing models with constraints on nodes or arcs. Travelling salesman problem (cutting plane formulation). Eulerian circuits. Minimal spanning trees (Kruskal and Prim algorithms).

- Allocation models . Assignment. Matching. Example of applications to sport events. Knapsack. Bin packing. Staffing models. LP with column generation: cutting stock, max flow, crew scheduling. Vehicle routing problems. Staffing problems.

- Scheduling . Infinite resource scheduling: PERT. Finite resource scheduling: one machine problems, parallel machine problems, flow-shop, job-shop and open-shop. Periodic scheduling.

The detailed lecture plan is available at http://www.dimi.uniud.it/~paolo.serafini/ROINF****.html

References

Paolo Serafini, Ricerca Operativa, Springer, 2009.
Paolo Serafini, Ottimizzazione, Zanichelli, Bologna 2000.
L. Schrage, LINDO: An optimization modeling system, Palo Alto Scientific Press, 1991

************************************************************************************

Finalità

La Ricerca Operativa si occupa di problemi di gestione efficiente affrontati con modelli matematici e algoritmici. Il corso vuole fornire allo studente gli strumenti principali per progettare un modello a partire da un problema reale e la necessaria comprensione delle strutture matematiche e algoritmiche dei modelli, con particolare riguardo alla programmazione lineare. A questo fine vengono presentati doversi modelli e per la maggior parte i modelli sono risolti usando Excel o pacchetti di programmazione lineare.

Programma

- Introduzione alla programmazione lineare
Modellizzazione: identificazione delle grandezze, dei vincoli e degli obiettivi. Ottimi di Pareto.
Esempio della dieta: modello di programmazione lineare. Analisi di sensibilità. Identificazione di ulteriori obiettivi. Frontiera efficiente. Vincoli di interezza.

- Proprietà della programmazione lineare
Struttura geometrica. Vertici e soluzioni di base. Problema duale. Complementarità. Cenni del metodo del simplesso. Metodo branch-and-bound per variabili intere.

- Modelli di percorsi
Programmazione Dinamica. Principio di ottimalità. Equazione ricorsiva. Cammini minimi (Bellman-Ford, Dijkstra, Floyd-Warshall).

- Modelli di percorsi con capacità
Cammini minimi con capacità: reti di flusso. Flussi di costo minimo. Massimo flusso. Minimi tagli. Esempi di applicazione dei flussi: assegnazione seggi elettorali.

- Modelli di percorsi con vincoli sui nodi o sugli archi
Problema del commesso viaggiatore (formulazione con piani di taglio). Circuiti Euleriani. Minimi alberi di supporto (Kruskal e Prim).

- Modelli di allocazione
Assegnamento. Accoppiamento. Esempi di applicazioni ad eventi sportivi. Knapsack. Bin packing. Modelli di turnazione. Generazione di colonne: cutting stock, massimo flusso. Vehicle routing problems.

- Schedulazione
Schedulazione a risorsa infinita: PERT. Schedulazione a risorsa finita: problemi a una macchina, macchine parallele, flow-shop, job-shop e open-shop. Schedulazione periodica.

Il piano dettagliato delle lezioni si trova al sito http://users.dimi.uniud.it/~paolo.serafini/ROINF****.html

Bibliografia