MODELLI E ALGORITMI DI OTTIMIZZAZIONE | Università degli studi di Bergamo

MODELLI E ALGORITMI DI OTTIMIZZAZIONE

Attività formativa monodisciplinare
Codice dell'attività formativa: 
38010

Scheda dell'insegnamento

Per studenti immatricolati al 1° anno a.a.: 
2020/2021
Insegnamento (nome in italiano): 
MODELLI E ALGORITMI DI OTTIMIZZAZIONE
Insegnamento (nome in inglese): 
OPTIMIZATION MODELS AND ALGORITHMS
Tipo di attività formativa: 
Attività formativa Affine/Integrativa
Tipo di insegnamento: 
Opzionale
Settore disciplinare: 
RICERCA OPERATIVA (MAT/09)
Anno di corso: 
1
Anno accademico di offerta: 
2020/2021
Crediti: 
9
Responsabile della didattica: 
Mutuazioni

Altre informazioni sull'insegnamento

Modalità di erogazione: 
Didattica Convenzionale
Lingua: 
Italiano
Ciclo: 
Primo Semestre
Obbligo di frequenza: 
No
Ore di attività frontale: 
72
Ambito: 
Attività formative affini o integrative
Prerequisiti

Funzione reale di variabili reali
Algebra delle matrici
Sistemi di equazioni lineari

Obiettivi formativi

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.

Contenuti dell'insegnamento

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.

Metodi didattici

Il corso si compone di lezioni frontali, esercitazioni ed eventuale tutorato.

Modalità verifica profitto e valutazione

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.

Prerequisites

Real function of real variables
Matrix algebra
Systems of linear equations

Educational goals

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.

Course content

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.

Teaching methods

The course is composed of lectures, exercises and tutoring.

Assessment and Evaluation

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.