PRESENTAZIONE

L’insegnamento di Ricerca Operativa fornisce competenze relative alla costruzione di modelli e all'utilizzo di algoritmi per la soluzione di problemi decisionali formulati in termini di problemi di ottimizzazione.

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

L'insegnamento fornisce le nozioni di base dei metodi di ottimizzazione per risolvere problemi decisionali. In particolare, L'insegnamento fornisce conoscenza per modellare matematicamente un problema di decisione e risolverlo attraverso tecniche di programmazione lineare, programmazione lineare a numeri interi, programmazione non lineare, e ottimizzazione su grafi.

OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

L’insegnamento ha come obiettivo lo studio dei principali metodi di ottimizzazione per la soluzione di problemi decisionali. In particolare, si vuole fornire agli studenti le competenze di base per la formulazione in termini matematici di problemi decisionali nonché le conoscenze per poter risolvere tali problemi attraverso l'applicazione di algoritmi di ottimizzazione. L’insegnamento presenta i concetti di variabili decisionali, funzione obiettivo, e vincoli di un problema di ottimizzazione, nonché le nozioni di base della programmazione lineare a variabili reali, della programmazione lineare intera e dell’ottimizzazione sui grafi e reti.

Per tutti gli argomenti, sono presentati sia gli aspetti più metodologici, sia i risvolti maggiormente applicativi. I vari concetti sono esposti attraverso lezioni teoriche e mediante soluzione di esercizi. Durante le lezioni inoltre viene anche mostrato come utilizzare un solver per la programmazione matematica a numeri misti interi e un risolutore grafico per problemi di programmazione matematica a variabili continue.

Al termine dell’insegnamento, lo studente sarà in grado sia di formulare un modello matematico per alcune classi di problemi decisionali di tipo combinatorio, sia di scegliere e applicare gli algoritmi più adeguati per la soluzione di problemi di programmazione matematica lineare e di problemi su grafi e reti.

PREREQUISITI

Conoscenze di base di Analisi Matematica, Geometria e Informatica.

MODALITA' DIDATTICHE

Lezioni frontali.

Gli studenti che abbiano certificazioni in corso di validità per Disturbi Specifici dell’Apprendimento (DSA), per disabilità o altri bisogni educativi sono invitati a contattare il docente e il referente per la disabilità della Scuola Politecnica, Prof. Federico Scarpa (federico.scarpa@unige.it), all’inizio dell’insegnamento per concordare eventuali modalità didattiche che, nel rispetto degli obiettivi dell’insegnamento, tengano conto delle modalità di apprendimento individuali.

PROGRAMMA/CONTENUTO

• Concetti base della teoria della complessità 
• Introduzione alla programmazione matematica e ai problemi decisionali
• Programmazione lineare a variabili reali: la formulazione di problemi, l'algoritmo del simplesso, tecniche di post-ottimalità. teoria della dualità, il simplesso duale
• Programmazione lineare a variabili intere: l'uso delle variabili binarie, formulazione di problemi, la totale unimodularità, il metodo dei piani di taglio, il metodo del branch and bound
• Ottimizzazione su grafi: definizioni fondamentali, il problema del minimo albero ricoprente e gli algoritmi di Kruskal e Prim; il problema del percorso minimo e gli algoritmi di Dijkstra, Bellman-Ford e Floyd-Warshall
• Reti di flusso: esempi di formulazioni, il problema del max flow-min cut e l'algoritmo del cammino aumentante; il problema del min cost flow e gli algoritmi di eliminazione dei cicli ed il simplesso su rete
• Esempi di formulazione e soluzione di problemi di programmazione matematica a numeri reali e misti interi con il solver Cplex di IBM

TESTI/BIBLIOGRAFIA

Dispense fornite dal Docente e disponibili in formato elettronico su Aulaweb

Testi per eventuale approfindimento:

[1] Hillier, Lieberman – Introduction to operations research. McGraw-Hill, 2004.

[2] D. Bertsimas, J.N. Tsitsiklis – Introduction to linear optimization. Athena Scientific, 1999

Tutte le slides utilizzate durante le lezioni e altro materiale didattico saranno disponibili su Aulaweb. In generale, gli appunti presi durante le lezioni e il materiale su Aulaweb sono sufficienti per la preparazione dell'esame.

DOCENTI E COMMISSIONI

LEZIONI

INIZIO LEZIONI

https://corsi.unige.it/corsi/10716/studenti-orario

Orari delle lezioni

L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy

ESAMI

MODALITA' D'ESAME

Esame scritto eventualmente con domande che richiedono la soluzione di esercizi (applicazione di algoritmi) per le classi di problemi presentati al corso, che chiedono di esporre brevemente alcuni aspetti teorici insegnati e che chiedono di formulare semplici problemi decisionali di natura combinatoria.

MODALITA' DI ACCERTAMENTO

Al termine dell’insegnamento lo studente dovrà dimostrare di:

• aver compreso i concetti visti a lezione ed essere capace di esporli con un linguaggio adeguato;
• saper scegliere ed applicare l’algoritmo più opportuno per la soluzione dei problemi decisionali presentati durante l'insegnamento
• essere in grado di formulare un modello matematico di programmazione lineare per risolvere un problema decisionale di natura combinatori.

ALTRE INFORMAZIONI

Rivolgersi al docente per ulteriori informazioni non comprese nella scheda insegnamento.