Funzione reale di variabili reali
Algebra delle matrici
Sistemi di equazioni lineari
Nel corso vengono introdotte metodologie di base della Ricerca Operativa, con particolare riferimento a modelli ed algoritmi per applicazioni ingegneristiche ed informatiche in ambito industriale e nella gestione di reti. Lo studio teorico dei principali algoritmi per il calcolo della soluzione ottima è completato dalla sperimentazione numerica di tali algoritmi mediante il linguaggio di modellazione GAMS.
Al termine del corso lo studente è in grado di
a. Formulare un problema decisionale in un contesto reale mediante un modello di programmazione matematica, individuando le variabili decisionali ed esprimendo in funzione di esse l’obiettivo da conseguire ed i vincoli che devono essere rispettati affinché la soluzione sia effettivamente utilizzabile nel contesto reale
b. Individuare il metodo (o i metodi) da utilizzare per la determinazione della soluzione ottima, conoscendone applicabilità e limiti
c. Analizzare la soluzione ottima determinata dal metodo risolutivo, in particolare la sua unicità e la sua sensibilità rispetto ai valori assegnati ai parametri del modello sulla base dei dati osservati disponibili.
d. Utilizzare l’ambiente di modellazione GAMS per la codifica dei modelli formulati e la loro risoluzione.
Formulazione di un modello di programmazione matematica: variabili decisionali, funzione obiettivo, vincoli. Tecniche di modellazione matematica.
Problemi su grafi e reti di flusso.
Alberi e grafi, algoritmi di ricerca su grafo. Cammini minimi, massimo flusso, flusso di costo minimo, assegnamento. Alcune strutture dati e algoritmi di soluzione.
Programmazione lineare.
Metodo grafico. Soluzioni di base e condizioni di ottimalità. Metodo del simplesso. Teoria della dualità, coppie di problemi duali, scarti complementari. Metodo del simplesso duale. Analisi di sensitività, analisi parametrica.
Programmazione lineare mista intera e ottimizzazione combinatoria.
Problemi di ottimizzazione discreta: formulazioni. Rilassamenti e algoritmo di Branch-and-Bound. Alcune applicazioni.
Algoritmi euristici voraci e ricerche locali.
Applicazioni reali in ambito industriale e in computer science.
Dispense fornite dal docente.
Libri di testo consigliati:
F.S. Hillier, G.J. Lieberman, Ricerca Operativa: Fondamenti, Nona edizione, McGraw-Hill, 2010
M. Fischetti, Lezioni di Ricerca Operativa, seconda edizione, Edizioni Libreria Progetto, Padova, 1999
S. Martello, Ricerca Operativa per la Laurea Magistrale, Esculapio, Bologna, 2011
F. Schoen, Modelli di ottimizzazione per le decisioni, Esculapio, Bologna, 2006
Il corso si compone di lezioni frontali, esercitazioni ed eventuale tutorato.
La prova d’esame vuole verificare il raggiungimento da parte dello studente degli obiettivi formativi sopra descritti.
La prova d’esame si divide in due parti: parte A e parte B.
La parte A consiste in 3 quesiti di natura teorica o pratica da svolgersi per iscritto. Lo studente è ammesso alla prova B se consegue un punteggio di almeno di 18/30 nella parte A.
La parte B consiste in una discussione orale relativa all’esposizione di argomenti teorici e alla risoluzione di esercizi di modellazione, con determinazione ed analisi della soluzione ottima. Il voto finale è la media dei voti conseguiti nella parte A e nella parte B.
Real function of real variables
Matrix algebra
Systems of linear equations
The course introduces basic Operations Research methodologies, in particular models and algorithms for engineering and IT applications in industry and in network management. The theoretical study of the main optimization algorithms is complemented by numerical experiments using the GAMS modeling language.
The course enables the student to
1) Formulate a real decision problem as a mathematical programming problem, identifying the relevant decision variables and expressing the problem objective and constraints as functions of these decision variables.
2) Identify the method(s) for computing the optimal solution, being aware of its (their) applicability and limits.
3) Analyze the computed optimal solution, in particular uniqueness and sensitivity to model parameters.
4) Use the modeling framework GAMS to code the mathematical model and obtain the optimal solution.
Optimization problems and their mathematical formulations; decision variables, objective function, constraints. Modeling techniques.
Graphs and network flows problems.
Trees and graphs, searching on a graph. Shortest paths, maximum flow, minimum cost flow, assignments. Some data structures and solution algorithms. Complexity analisys.
Linear programming.
Duality theory, pairs of dual problems, complementary slackness, the simplex method; geometrical and economical interpretation. Basic solutions and optimality conditions.
Integer linear programming and combinatorial optimization.
.Discrete optimization problems: formulations. Relaxations and branch and bound algorithm. Some applications.
Heuristic algorithms: greedy and local search.
Applications of OR in computer science and engineering.
Lecture notes.
Libri di testo consigliati:
F.S. Hillier, G.J. Lieberman, Ricerca Operativa: Fondamenti, Nona edizione, McGraw-Hill, 2010
M. Fischetti, Lezioni di Ricerca Operativa, seconda edizione, Edizioni Libreria Progetto, Padova, 1999
S. Martello, Ricerca Operativa per la Laurea Magistrale, Esculapio, Bologna, 2011
F. Schoen, Modelli di ottimizzazione per le decisioni, Esculapio, Bologna, 2006
The course is composed of lectures, exercises and tutoring.
The exam aims at assessing the achievement of the educational objective described above.
The exam consists of two parts: Part A and Part B.
Part A is a written exam consisting of 3 questions both theoretical and practical. To be admitted to Part B, the student must get a grade not less than 18/30 in Part A.
Part B is an oral discussion about both theoretical issues and practical problems. The final grade is the average of the marks obtained in Part A and in Part B.