MODELLI E ALGORITMI DI OTTIMIZZAZIONE | Università degli studi di Bergamo - Didattica e Rubrica

MODELLI E ALGORITMI DI OTTIMIZZAZIONE

Modulo Generico
Codice dell'attività formativa: 
38089-MOD2

Scheda dell'insegnamento

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

Altre informazioni sull'insegnamento

Ciclo: 
Annualità Singola
Obbligo di frequenza: 
No
Ore di attività frontale: 
48
Ore di studio individuale: 
90
Ambito: 
Attività formative affini o integrative
Prerequisiti

Funzioni reali di variabili reali. Algebra delle matrici. Sistemi di equazioni lineari.

Obiettivi formativi

Nel corso sono presentati modelli di programmazione matematica ed algoritmi risolutivi per lo sviluppo di strumenti di analisi e di supporto alle decisioni, con particolare riferimento ad applicazioni in ambito industriale, gestionale ed informatico. Lo studio teorico è completato dalla sperimentazione numerica in ambiente GAMS.
Al termine del corso lo studente è in grado di
a. formulare il modello di programmazione matematica che rappresenta il problema oggetto di analisi o di processo decisionale;
b. individuare il metodo risolutivo appropriato per il calcolo della soluzione ottima del modello, conoscendone applicabilità, limiti e costi computazionali;
c. analizzare la soluzione ottima determinata dal metodo risolutivo, in particolare la sua unicità e la sua sensitività rispetto ai valori assegnati ai parametri del modello in base ai dati osservati disponibili;
d. utilizzare l’ambiente di modellazione GAMS per la codifica dei modelli formulati e la loro risoluzione.

Contenuti dell'insegnamento

Il corso si articola in due parti.
Nella prima parte (3 CFU) sono introdotti i concetti di base per lo sviluppo e la risoluzione dei modelli di programmazione matematica:
• tecniche di modellazione.
• modelli di programmazione lineare: condizioni di ammissibilità e di ottimalità; soluzione unica e soluzioni ottime alternative; metodo del simplesso; analisi di sensitività; analisi parametrica.
• teoria della dualità nella programmazione lineare: problema duale; scarti complementari; metodo del simplesso duale.
• modelli di programmazione lineare mista intera: algoritmi Branch-and-Bound; algoritmi a piani di taglio.
Nella seconda parte (3 CFU) si discutono modelli ed algoritmi di ottimizzazione su reti di flusso e loro applicazione in ambito industriale, gestionale ed informatico:
• alberi di supporto di costo minimo; cammini minimi; massimo flusso; flusso di costo minimo; problemi di assegnamento e di abbinamento; flussi generalizzati; flussi multi-commodity.
• algoritmi esatti; algoritmi euristici.
• applicazioni in ambito industriale e gestionale

Metodi didattici

Il corso si compone di lezioni frontali, esercitazioni e tutorati, nel cui ambito problemi decisionali in vari contesti applicativi saranno modellati e risolti in ambiente GAMS.

Modalità verifica profitto e valutazione

La prova d’esame verifica 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 con esposizione di argomenti teorici e risoluzione di esercizi di modellazione, calcolo ed analisi della soluzione ottima.
Il voto finale è la media dei voti conseguiti nella parte A e nella parte B.

Prerequisites

Real functions of real variables. Matrix algebra. Systems of linear equations.

Educational goals

The course is concerned with mathematical programming models and solution algorithms for developing analysis and decision support tools, with particular reference to applications in industrial, management and computer science. The theoretical study is completed by numerical experiments in the GAMS environment.
At the end of the course the student is able to
a. formulate mathematical programming models to represent decision-making problems in the industrial, management and computer science fields: identify decision variables; express objective to be achieved and constraints that the solution must meet to be effectively usable in the real context;
b. identify the appropriate algorithm to compute the model optimal solution (applicability, limits and computational costs);
c. analyze the computed optimal solution (uniqueness, sensitivity with respect to the values assigned to the model parameters on the basis of available observed data);
d. use the GAMS modeling environment to solve the formulated models.

Course content

The course is divided into two parts.
The first part (3 CFU) introduces the basic concepts of developing and solving mathematical programming models:
- modeling techniques.
- linear programming models: feasibility and optimality conditions; unique solution and alternative optimal solutions; simplex method; sensitivity analysis; parametric analysis.
- duality theory in linear programming: dual problem; complementary slackness; dual simplex method.
- mixed integer linear programming models: Branch-and-Bound algorithms; cutting plane algorithms.
The second part (3 CFU) presents network optimization models and algorithms for problems in industrial, management and computer science:
- minimum cost support trees; minimum paths; maximum flow; minimum cost flow; assignment and matching problems; generalized flows; multi-commodity flows.
- exact algorithms; heuristic algorithms.
- applications in industrial and management fields

Teaching methods

The course consists of lectures, exercises and tutorials, in which decision problems in various application contexts will be modeled and solved in the GAMS environment.

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.