Fundamentals of Operations Research

Introduction to mathematical programming and, in particular, to linear optimization (both with continuous and discrete variables). Theory and main algorithms for the solution of linear optimization problems, of network flows, of integer linear optimization problems.

Textbook:  Fabio Schoen, Fondamenti di Ricerca Operativa, seconda edizione ISBN-10: 1542342023 ISBN-13: 978-1542342025, 2017

CourseObjectives:

Knowledge of the theory and methods of linear optimization, integer optimization, network flows. To be able to solve small dimensional linear optimization problems. Knowledge and usage of duality theory. Capability of solving shortest path and maximum flow problems.

Prerequisites:

Linear Algebra: vectors, matrices, determinant, linear systems of equations

Front teaching

Oral exam including two numerical exercises. The exam can be substituted by an equivalent written one

Syllabus

1. Linear Optimization Examples: blending problems, product mix, transportation; introduction to graph theory; network flows Introduction to Linear Porgramming (LP). Forms of an LP problem: solution, bases, feasible solutions; Introduzione alla Programmazione Lineare (PL). Forma di un problema di PL; soluzioni, basi, soluzioni ammissibili; basic feasible solutions; fundamental theorem of LP; geometry of LP Simplex methods – matrix formulation Duality theory; definition of dual problems; duality theorems; interpretation; complementary slackness; duality and game theory (introduction); dual simplex method. Sensitivity analysis; sensitivity on the right hand side; sensitivity on cost coefficients; adding a variable or a constraint.
2. Integer Linear Programming (ILP) Examples of ILP problems and models Links between LP and ILP General purpose methods for ILP: cutting plane methods (Gomory), Branch and Bound.
3. Network Flows Bases and basic solutions in network flow problems. Shortest paths: Disjkstra algorithm Maximum flow problem; method of Ford and Fulkerson. Maximum flow / minimum cut theorem Network simplex methods

 

---

 

FONDAMENTI DI RICERCA OPERATIVA

Corso di studio: B047 – INGEGNERIA INFORMATICA

CFU: 6
Settore: MAT/09
Anno corso: 2 Periodo: Primo Semestre

Contenuti (Dipl.Sup.)

Introduzione alla programmazione matematica, in particolare all’ottimizzazione lineare (sia continua che a variabili intere). Teoria ed principali algoritmi di risoluzione per problemi di ottimizzazione lineare, per problemi di flusso ottimo su reti, per problemi lineari con variabili discrete.

Testi di riferimento:

Fabio Schoen, Fondamenti di Ricerca Operativa, seconda edizione ISBN-10: 1542342023 ISBN-13: 978-1542342025, 2017

Obiettivi formativi:

Conoscere la teoria ed i metodi di ottimizzazione lineare, di ottimizzazione lineare intera, di ottimizzazione lineare su grafi; saper risolvere piccoli problemi di programazione lineare, sapere utilizzare la dualità, saper risolvere problemi di cammino di costo minimo e di flusso massimo su reti. Prerequisiti Algebra lineare: matrici, vettori, determinanti, sistemi lineari

Metodi didattici: Didattica frontale
Modalità di verifica dell’apprendimento: Esame orale, comprendente due esercizi numerici. L’esame orale puo’ essere sostenuto anche mediante prove scritte

 

Programma esteso

1. Programmazione Lineare esempi: il problema della dieta, problema di miscelazione ottimale, problema del trasporto, introduzione alla teoria dei grafi, problemi di flusso su reti. Introduzione alla Programmazione Lineare (PL). Forma di un problema di PL; soluzioni, basi, soluzioni ammissibili; interpretazione del concetto di base; teorema fondamentale della PL; geometria della PL. Il metodo del simplesso; formulazione matriciale Teoria della dualità Introduzione; definizione del problema duale; teoremi di dualità; interpretazione di problemi duali; teorema di “complementary slackness”; dualità e teoria dei giochi (cenni introduttivi); il metodo del simplesso duale. Analisi di sensitività. Introduzione; sensitività sul termine noto; sensitività sul vettore dei costi; aggiunta di una nuova variabile; aggiunta di un nuovo vincolo
2. Programmazione Lineare Intera Esempi di problemi e modelli di programmazione intera. Connessioni tra PL e programmazione lineare intera. Algoritmi generali per la programmazione intera: il metodo di Gomory, il metodo Branch & Bound.
3. Reti di flusso Basi e soluzioni di base nei problemi di flusso; Il problema del cammino di costo minimo: algoritmo di Dijkstra Il problema del flusso massimo: algoritmo di Ford & FUlkerson. Teorema massimo flusso/sezione di capacita’ minima Il metodo del simplesso su reti