RICERCA OPERATIVA 1

RICERCA OPERATIVA 1

_
iten
Codice
66274
ANNO ACCADEMICO
2019/2020
CFU
6 cfu al 3° anno di 9921 INGEGNERIA INDUSTRIALE E GESTIONALE (L-9) SAVONA
SETTORE SCIENTIFICO DISCIPLINARE
MAT/09
LINGUA
Italiano
SEDE
SAVONA (INGEGNERIA INDUSTRIALE E GESTIONALE )
periodo
1° Semestre
moduli
materiale didattico

PRESENTAZIONE

Il Corso introduce a modelli e metodi di ottimizzazione matematica utilizzabili per la soluzione di problemi decisionali.  Si articola nei temi  della modellazione di problemi, della loro trattabilità, dei metodi di soluzione tramite la programmazione lineare e non-lineare, l'ottimizzazione combinatoria, l'ottimizzazione su reti e grafi e la programmazione dinamica, fino ad arrivare ad algoritmi implementabili su un calcolatore. La materia viene presentata nei suoi aspetti metodologici, teorici ed applicativi.

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

Il corso fornisce le competenze per affrontare problemi applicativi sviluppando modelli e metodi che operino in modo efficiente in presenza di risorse limitate

OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

Scopo del Corso è far acquisire le competenze che consentano di affrontare problemi applicativi sviluppando modelli e metodi anche originali, che operino in modo efficiente in presenza di risorse limitate. Gli studenti impareranno a:

  • interpretare e modellare un processo decisionale (di progettazione, di gestione, ecc.) nei termini di un problema di ottimizzazione, individuando cioè le variabili decisionali da ottimizzare e la funzione di costo (o la cifra di merito) da minimizzare (o da massimizzare);
  • inquadrare il problema nella gamma dei problemi considerati “canonici” (lineari/non lineari, discreti/continui, statici/dinamici, deterministici/stocastici, ecc.);
  • realizzare il "matching" tra l’algoritmo risolutivo (da scegliere tra quelli esistenti o da progettare) e un adeguato supporto software di elaborazione.

Modalità didattiche

Lezioni frontali.

PROGRAMMA/CONTENUTO

INTRODUZIONE ALLA RICERCA OPERATIVA

Le origini della Ricerca Operativa.

Problemi reali e modelli matematici. Limiti dei modelli.

Obiettivi, variabili decisionali, vincoli.

Classificazioni dei problemi di ottimizzazione.

Dimensione dei problemi e inefficienza degli algoritmi “brute force”.

Un esempio numerico introduttivo.

PROGRAMMAZIONE LINEARE (PL)

Modelli di PL di importanza applicativa.

Esempio grafico introduttivo.

Algebra e geometria della PL.

Algoritmo del simplesso. Interpretazioni algebrica e geometrica. Simplesso sul tableau.

Analisi di post-ottimalità.

DUALITÀ

Problemi duali: modelli di PL di importanza applicativa.

Dualità debole e dualità forte.

Interpretazione economica della dualità (prezzi ombra).

Slackness complementare.

PROGRAMMAZIONE LINEARE A NUMERI INTERI (PLI)

Modelli di PLI di importanza applicativa (Matching, Sequencing, Fixed-Charge, Knapsack, Steiner Tree, Plant Location, Scheduling). 

Algebra e geometria della PLI. Matrici totalmente unimodulari.

Algoritmo di tipo branch-and-bound.

Algoritmo basati su piani di taglio. Tagli di Gomory.

Algoritmi di tipo branch-and-cut.

GRAFI E RETI

Definizioni e generalità sui grafi.

Rappresentazione dei grafi.

Il problema di Shortest Path (SP) e il suo modello di PLI. Algoritmo di Dijkstra. Algoritmo di Bellman-Ford.

Il problema di Shortest Spanning Tree (SST) e il suo modello di PLI. Algoritmo di Kruskal. Algoritmo di Primm-Dijkstra.

Algoritmi greedy.

Cenni al Travelling Salesman Problem (TSP) e al suo modello di PLI.

Problemi di flusso (Max-Flow, Min-Cost-Flow). Algoritmo di Ford-Fulkerson per il Max-Flow)

CENNI ALLA TEORIA DELLA COMPLESSITÀ

Concetto di istanza e dimensione di un'istanza.

Complessità computazionale di un algoritmo.

Problemi trattabili ed intrattabili. Problemi in forma decisionale.

Classi P, NP e co-NP. Concetto di algoritmo non-deterministico.

Il teorema di Cook. La classe dei problemi NP-completi.

Esempi di problemi NP-completi e rispettivi modelli di PLI: knapsack, Steiner tree, …

Problemi NP-hard.

PROGRAMMAZIONE DINAMICA (PD) 

Esempio introduttivo.

Problemi di ottimizzazione a stadi. Contesto deterministico.

Fase backward e fase forward.

Principio di ottimalità.

Le equazioni di Bellman.

Estensione al contesto stocastico.

La “maledizione della dimensionalità”.

CENNI ALLA PROGRAMMAZIONE NON LINEARE (PNL)

ESERCITAZIONI (facoltative; distribuite durante il Corso)

  • Esercizi sugli argomenti del Corso.
  • Strumenti software per la Ricerca Operativa (Lingo, Matlab Optimization Toolbox, ecc.).

TESTI/BIBLIOGRAFIA

Materiale didattico fornito a lezione.

Matteo Fischetti, “Lezioni di Ricerca Operativa”, 1999.

DOCENTI E COMMISSIONI

Ricevimento: Students may also take appointment via email sent to mauro.gaggero@cnr.it

Commissione d'esame

MAURO GAGGERO (Presidente)

SILVIA SIRI (Presidente)

SIMONA SACONE

LEZIONI

Modalità didattiche

Lezioni frontali.

INIZIO LEZIONI

19 settembre 2016

ESAMI

Modalità d'esame

Scritto e orale

Modalità di accertamento

Sia domande di teoria sia svolgimento di esercizi

Calendario appelli

Data Ora Luogo Tipologia Note
03/09/2020 09:00 SAVONA Scritto