72935 - RICERCA OPERATIVA M

Anno Accademico 2022/2023

  • Docente: Silvano Martello
  • Crediti formativi: 8
  • SSD: MAT/09
  • Lingua di insegnamento: Italiano
  • Moduli: Silvano Martello (Modulo 1) Andrea Lodi (Modulo 2)
  • Modalità didattica: In presenza e a distanza - Blended Learning (Modulo 1) Convenzionale - Lezioni in presenza (Modulo 2)
  • Campus: Bologna
  • Corso: Laurea Magistrale in Ingegneria informatica (cod. 5826)

Conoscenze e abilità da conseguire

Modelli matematici, programmazione lineare, algoritmo del simplesso, dualità. Programmazione lineare intera, piani di taglio, branch-and-bound. Complessità. Programmazione dinamica. Simulazione discreta.

Contenuti

Prerequisiti:
È necessario che l'allievo comprenda la lingua inglese scritta per poter seguire le slide di lezione.

MODULO 1 (Ottimizzazione Matematica): Silvano Martello

1. Il metodo scientifico: sistemi, modelli, metodologie

2. Programmazione Matematica

2.1 Problemi di ottimizzazione
2.2 Insiemi e funzioni convesse
2.3 Programmazione convessa

3. Programmazione Lineare
3.1 Forma generale, canonica e standard
3.2 Basi e soluzioni base
3.3 Politopi convessi

4. Algoritmo del Simplesso
4.1 Spostamento tra soluzioni base
4.2 Il tableau e il pivoting
4.3 Criterio di ottimalità
4.4 Algoritmo del simplesso
4.5 Metodo delle due fasi
4.6 Aspetti geometrici dell'ottimizzazione

5. Dualità
5.1 Duale di un problema di programmazione lineare
5.2 Proprietà della dualità
5.3 Lemma di Farkas
5.4 Scarti complementari
5.5 Algoritmo del simplesso duale
5.6 Analisi di sensitività

6. Programmazione Lineare Intera
6.1 Unimodularità
6.2 Algoritmi cutting-plane e tagli di Gomory
6.3 Algoritmi branch-and-bound
6.4 Strategie di esplorazione
6.5 Problema knapsack 0-1
6.6 Algoritmi branch-and-cut

6.7 Software e freeware

7. Complessità
7.1 Versione riconoscimento di un problema
7.2 Classi P ed NP
7.3 Problemi NP-completi
7.4 Programmazione dinamica
7.5 Problemi fortemente NP-completi

 

MODULO 2 (Simulazione Discreta): Andrea Lodi

Introduzione alla simulazione discreta

Descrizione statica e dinamica di un sistema

Entità temporanee e permanenti

Eventi ed event notice.

Esercitazioni per la modellazione di sistemi realistici.

Testi/Bibliografia

MODULO 1

Libro di testo: S. Martello, Ricerca Operativa, Esculapio (progetto Leonardo), Bologna, 2021.

Slide (in Inglese)

Il libro di testo contiene numerosi esercizi svolti. Per ulteriori esercizi:

S. Martello, D. Vigo, Esercizi di Ricerca Operativa, Esculapio (progetto Leonardo), Bologna, 2003.

Per eventuali approfondimenti:

C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.

S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990 (download gratuito)

R. Burkard, M. Dell'Amico, S. Martello, Assignment Problems - Revised reprint, SIAM, Philadelphia, 2012.

 

MODULO 2

Libro di testo: S. Martello, Ricerca Operativa, Esculapio (progetto Leonardo), Bologna, 2021.


Slide ed esercizi risolti disponibili su virtuale.unibo.it.

Per ulteriori esercizi di simulazione:

S. Martello, D. Vigo, Esercizi di Simulazione Numerica, Esculapio (progetto Leonardo), Bologna, 2001.

Metodi didattici

Il corso e` strutturato in lezioni ed esercitazioni in aula.
Durante le lezioni vengono discusse le problematiche teoriche e gli aspetti algoritmici degli argomenti trattati.
Durante le esercitazioni vengono proposti casi industriali in cui si presentano problemi di ottimizzazione e vengono derivati i corrispondenti modelli matematici o di simulazione numerica.
Per i modelli matematici la soluzione viene determinata mediante gli algoritmi illustrati nelle lezioni.

Modalità di verifica e valutazione dell'apprendimento

L'apprendimento viene verificato mediante una prova scritta (comprensiva dei due moduli, con unica votazione) ed una prova orale.

La prova scritta ha durata di circa due ore ed e` composta da un esercizio relativo al MODULO 1 (modellizzazione di un sistema mediante modelli matematici e soluzione, mediante gli opportuni algoritmi, di semplici problemi di ottimizzazione), cui sono attribuiti 15 punti, e da un esercizio relativo al MODULO 2 (modellizzazione di un sistema mediante simulazione discreta), cui sono attribuiti 15 punti. I due esercizi devono essere svolti nella stessa prova scritta. La prima volta che vengono consegnati i due elaborati, viene aggiunto al punteggio un bonus di 3 punti. Il voto della prova scritta e` quindi dato da:

voto prova scritta modulo 1 + voto prova scritta modulo 2 + bonus (se e` la prima consegna).

La visione degli elaborati corretti e` possibile unicamente nella data prefissata (normalmente in modalità online).

I candidati che riportano voto positivo nella prova scritta devono sostenere una prova orale sulla conoscenza teorica relativa al solo MODULO 1 (proprietà, dimostrazioni, ecc.), valutata in trentesimi. Detto k l'appello in cui si è superata la prova scritta, la prova orale va sostenuta entro l'appello k + 2.

Il voto finale è dato dalla media pesata:
2/3 (voto prova scritta) + 1/3 (voto prova orale)
arrotondata per eccesso.

I candidati respinti alla prova orale conservano il voto della prova scritta (nell'ambito della sua validità).

I candidati che rifiutano il voto finale ottenuto devono ripetere la prova scritta e la prova orale.

ESAMI ONLINE

Nel caso in cui gli esami vengano svolti in modalità online, verificare le istruzioni su virtuale.unibo.it.

Strumenti a supporto della didattica

Application, applet e freeware

Link ad altre eventuali informazioni

http://www.or.deis.unibo.it/staff_pages/martello/cvitae.html

Orario di ricevimento

Consulta il sito web di Silvano Martello

Consulta il sito web di Andrea Lodi