RICERCA OPERATIVA

MAT/09 - 9 CFU - 2° semestre

Docente titolare dell'insegnamento

PATRIZIA DANIELE


Obiettivi formativi

Lo studente acquisirà la capacità di formulare in termini matematici problemi di massimizzazione dei profitti e minimizzazione dei costi, di ottimizzazione delle risorse, di equilibrio del traffico su reti e di giochi tra due persone a somma nulla.

In particolare, il corso di Ricerca Operativa si propone i seguenti obiettivi:

Conoscenza e capacità di comprensione (knowledge and understanding):

Alla fine del corso di Ricerca Operativa, lo studente, oltre ad aver acquisito le conoscenze e le capacità di base nell’ambito della programmazione e modellizzazione matematica, dimostrerà di:

Capacità di applicare conoscenza e comprensione (applying knowledge and understanding):

Le conoscenze teoriche e pratiche acquisite durante il corso permetteranno allo studente di:

Autonomia di giudizio (making judgements):

Lo studente, in virtù della formazione acquisita, anche di tipo analitico-quantitativo, sarà in grado di analizzare ed interpretare criticamente i dati forniti.

Abilità comunicative (communication skills):

Alla fine del corso di Ricerca Operativa lo studente sarà in grado di:

 

Capacità di apprendimento (learning skills):

Lo studente avrà acquisito capacità di apprendere, anche in modo autonomo, ulteriori conoscenze sui problemi di matematica applicata. Tali capacità di apprendimento gli consentiranno di proseguire gli studi matematici con maggiore autonomia.


Prerequisiti richiesti

Conoscenze di base di Analisi Matematica 1 (equazioni e disequazioni, spazi metrici) e Geometria 1 (spazi vettoriali, combinazioni lineari di vettori, basi, risoluzione di sistmi lineari, geometria nel piano)



Frequenza lezioni

La frequenza è fortemente consigliata



Contenuti del corso

Programmazione Lineare: metodo del simplesso, dualità, geometria della Programmazione Lineare, analisi di stabilità (circa 26 ore).

Programmazione Lineare Intera: il rilassamento continuo, il metodo del Branch & Bound (circa 4 ore).

Programmazione Lineare Intera 0-1: il problema dello zaino (circa 4 ore).

Disequazioni variazionali: esistenza, caratterizzazione e unicità della proiezione su un convesso, teoremi di esistenza e unicità della soluzione di disequazioni variazionali (circa 8 ore).

Reti di traffico: definizioni, principio di equilibrio di Wardrop, caratterizzazione mediante disequazione variazionale, metodo diretto per il calcolo della soluzione, metodo delle proiezioni (circa 14 ore).

Teoria dei giochi: strategie pure e miste, Teorema di Von Neumann (circa 8 ore).

Cenni di ottimizzazione nonlineare: teoria lagrangiana e moltiplicatori KKT (circa 9 ore).



Testi di riferimento

  1. L. Daboni, P. Malesani, P. Manca, G. Ottaviani, F. Ricci, G. Sommi, “Ricerca Operativa”, Zanichelli, Bologna, 1975.
  2. M.L. De Cesare, M.R. Maddalena, “Introduzione alla Programmazione Lineare”, Giappichelli Editore, 2001.
  3. Dispense su STUDIUM

Altro materiale didattico

Si consultino le dispense e i testi delle esercitazioni su STUDIUM



Programmazione del corso

 *ArgomentiRiferimenti testi
1*Il metodo del simplesso
2*La ricerca della base in due fasi
3*La geometria della PL
4*Dualità in PL
5*Calcolo della soluzione ottima del problema duale
6*Interpretazione duale dei problemi di PL
7*Analisi di sensitività
8*Il metodo del Branch & Bound
9*Il problema dello zaino
10*Teorema della proiezione su un convesso chiuso
11*Teoremi di esistenza e unicità delle soluzioni di una disequazione variazionale
12*Reti di traffico
13*Teorema di Smith
14*Metodo diretto per il calcolo della soluzione di una disequazione variazionale
15*Metodo delle proiezioni
16*Teoria Lagrangiana
17*Moltiplicatori KKT
18*Teorema di Von Neumann
19*Riduzione di un gioco ad una coppia di problemi duali
* Conoscenze minime irrinunciabili per il superamento dell'esame.

N.B. La conoscenza degli argomenti contrassegnati con l'asterisco è condizione necessaria ma non sufficiente per il superamento dell'esame. Rispondere in maniera sufficiente o anche più che sufficiente alle domande su tali argomenti non assicura, pertanto, il superamento dell'esame.


Verifica dell'apprendimento


MODALITÀ DI VERIFICA DELL'APPRENDIMENTO

A metà corso è prevista una prova di autovalutazione, che consiste nello svolgimento di alcuni esercizi relativi alla formulazione e alla risoluzione di problemi di Programmazione Lineare.

L'esame finale consiste in una prova orale durante la quale il candidato è invitato anche a risolvere un esercizio numerico. Il voto finale viene stabilito sulla base delle risposte scritte e orali date dal candidato durante il colloquio finale.


PROVE IN ITINERE

A metà corso è prevista una prova di autovalutazione, che consiste nello svolgimento di alcuni esercizi relativi alla formulazione e alla risoluzione di problemi di Programmazione Lineare.


PROVE DI FINE CORSO

L'esame finale consiste in una prova orale durante la quale il candidato è invitato anche a risolvere un esercizio numerico. Il voto finale viene stabilito sulla base delle risposte scritte e orali date dal candidato durante il colloquio finale.


ESEMPI DI DOMANDE E/O ESERCIZI FREQUENTI

Esempi di domande:

Si presentino i tre casi del metodo del simplesso.

Si dimostri il teorema fondamentale della dualità.

Si dimostri la caratterizzazione della proiezione su un convesso.

Si dimostri il primo teorema di esistenza delle soluzioni di una disequazione variazionale.

Si dimostri il teorema di Von Neumann.

Si presenti il metodo del Branch & Bound.

Si dimostri il teorema di Smith.

Si presenti il problema dello zaino.

Esercizi frequenti:

alcuni esercizi assegnati negli anni precedenti si possono torvare su STUDIUM.




Apri in formato Pdf English version