INGLESE

Richiami ad elementi di algebra lineare e geometria nello spazio e cenni alla risoluzione di sistemi lineari; introduzione all'ottimizzazione e ai problemi di decisione; programmazione lineare; programmazione lineare intera: modelli e definizioni; introduzione alla teoria dei giochi.

[1] Fundamental Methods of Mathematical Economics, Alpha C. Chiang, New York, Mc Graw-Hill
[2] Advanced Optimization and Operations Research, Asoke Kumar Bhunia, Laxminarayan Sahoo, Ali Akbar Shaikh, Springer
[3] Materiale del corso e appunti rilasciati dalla docente.

Conoscenze: gli studenti devono acquisire conoscenze di base su metodi ed algoritmi per ottimizzazione, problemi di decisione e teoria dei giochi.

Applicazioni delle conoscenze e competenze: gli studenti dovrebbero essere in grado di selezionare e applicare correttamente i metodi di base e gli strumenti software per l'analisi dei dati nel contesto della ricerca operativa.

Abilità comunicative: gli studenti dovrebbero essere in grado di illustrare i metodi e gli strumenti appresi durante il corso e di comunicare i risultati ottenuti, utilizzando un linguaggio tecnico e scientifico adeguato.

Si raccomanda la conoscenza dei contenuti del corso di Algebra lineare e di Analisi.

Capacità di scrivere codici in Matlab e/o Python.

Il corso prevede lezioni frontali e sessioni di laboratorio.

La frequenza ai corsi non è obbligatoria, ma è fortemente consigliata.

Lo scopo della prova d’esame consiste nel verificare il livello di raggiungimento degli obiettivi formativi precedentemente indicati. L’esame è costituito da una prova scritta seguita da una prova orale. Non si possono consultare testi o appunti durante lo scritto.

I voti sono espressi in trentesimi. Il punteggio minimo richiesto è 18/30. Il voto massimo è 30/30 con lode.
Si accede alla prova orale dopo aver conseguito almeno 18/30 nella prova scritta. Il voto finale è basato per 1/3 sulla prova scritta e per 2/3 su quella orale.
Il voto della prova scritta rimane valido per l'anno accademico in cui è stata sostenuta la prova.

Per essere ammessi alla valutazione, gli studenti devono presentare un documento d'identità valido.

Le attività di laboratorio sono parte integrante del programma.

1. Argomenti

1.1 Preliminari
Elementi di algebra lineare e geometria nello spazio e cenni alla risoluzione di sistemi lineari.

1.2 Introduzione all'ottimizzazione e ai problemi di decisione
Modelli, esempi, come si passa da un problema concreto, al modello astratto alla scelta dell'algoritmo, implementazione e analisi dei risultati.

1.3 La programmazione lineare
- La risoluzione grafica
- Geometria della PL (Vertici, faccette e facce del poliedro)
- Teorema fondamentale della PL
- Dualità
- Analisi di sensitività e interpretazione economica dei prezzi ombra

1.4 La programmazione lineare intera: modelli e definizioni
- Possibili approcci che non funzionano: rounding
- Matrici totalmente unimodulari e problemi polinomiali su grafo
- Algoritmi di risoluzione:
- il branch and bound
- il cutting plane

1.5 Introduzione alla teoria dei giochi
- Definizione di soluzioni dominate e di punti equilibrio
- Giochi a due giocatori a somma nulla (min max)
- Correlazione con la PL
- Metodi per trovare i punti di equilibrio.

2. Attività di laboratorio
Le attività di laboratorio sono parte integrante del programma. Per ciascuno degli algoritmi affrontati, è prevista l'esecuzione su una serie di problemi test, che evidenzino gli aspetti implementativi, le prestazioni dei codici implementati e l'analisi dei risultati ottenuti.

Gli algoritmi potranno essere implementati in Matlab o Python.

English

Recalls of elements of linear algebra and geometry in space and hints to the solution of linear systems; introduction to optimization and decision problems; linear programming; integer linear programming: models and definitions; introduction to game theory.

[1] Fundamental Methods of Mathematical Economics, Alpha C. Chiang, New York, Mc Graw-Hill
[2] Advanced Optimization and Operations Research, Asoke Kumar Bhunia, Laxminarayan Sahoo, Ali Akbar Shaikh, Springer
[3] Lecture notes from the teacher.

Knowledge: students must acquire basic knowledge on methods and algorithms for optimization, decision problems and game theory.

Knowledge Applications and Skills: Students should be able to select and correctly apply basic methods and software tools for data analysis in the context of operations research.

Communication skills: students should be able to illustrate the methods and tools learned during the course and to communicate the results obtained, using appropriate technical and scientific language.

The knowledge of the contents of the Linear Algebra course and of the basics of the Analysis course is recommended.

Ability to write codes in Matlab and / or Python.

The course consists of lectures and laboratory sessions.

Course attendance is not mandatory, but it is strongly recommended.

Written and oral exam. Students are not allowed to bring textbooks or notes during the written exam.

Marks are expressed in a scale ranging from 0 to 30. The minimum passing mark is 18/30. Outstanding performance is marked 30/30 cum laude.
To access the oral exam, students must have achieved at least 18/30 in the written exam. The final grade is based on the written mark (1/3) and on the oral mark (2/3).
The mark of the written exam expires at the end of the academic year.

In order to be admitted to the evaluation, students must show a valid id card.

The laboratory activities are an integral part of the program.

1. Topics

1.1 Preliminaries
Basics of linear algebra and geometry in space and methods for solving linear systems.

1.2 Introduction to optimization and decision problems
Models, examples, how to move from a concrete problem, to the abstract model and the choice of algorithm, implementation and analysis of results.

1.3 Linear programming
- The graphic resolution
- Geometry of the LP (vertices, facets and faces of the polyhedron)
- Fundamental theorem of LP
- Duality
- Sensitivity analysis and economic interpretation of shadow prices

1.4 Integer linear programming: models and definitions
- Possible approaches that don't work: rounding
- Totally unimodular matrices and polynomial problems on graphs
- Resolution algorithms:
- the branch and bound
- the cutting plane

1.5 Introduction to game theory
- Definition of dominated solutions and equilibrium points
- Two-player games with zero sum (min max)
- Correlation with the PL
- Methods for finding the balance points.

2. Laboratory activities
Laboratory activities are an integral part of the program. For each of the algorithms addressed, the execution on a series of test problems is foreseen, which highlight the implementation aspects, the performance of the implemented codes and the analysis of the results obtained.

The algorithms can be implemented in Matlab or Python.