RICERCA OPERATIVA
cod. 00884

Anno accademico 2017/18
1° anno di corso - Primo semestre
Docente
Settore scientifico disciplinare
Ricerca operativa (MAT/09)
Field
Attività formative affini o integrative
Tipologia attività formativa
Affine/Integrativa
63 ore
di attività frontali
9 crediti
sede: PARMA
insegnamento
in ITALIANO

Obiettivi formativi

Lo studente al termine del corso dovrebbe avere familiarita' con le tecniche di modellizzazione e di risoluzione di problemi di programmazione matematica (in particolare, programmazione lineare continua e intera, e programmazione nonlineare). Dovrebbe inoltre essere a conoscenza dei risultati teorici che sono alla base delle tecniche risolutive.

Dal punto di vista pratico dovrebbe essere in grado di affrontare la risoluzione, tramite gli strumenti della programmazione matematica, di problemi di decisione reali. In particolare, dovrebbe essere in grado di costruire il modello matematico di un problema di decisione reale, individuare un opportuno algoritmo di risoluzione (applicabile eventualmente attraverso il linguaggio di modellizzazione proposto) e infine ricavare e interpretare le soluzioni del modello.

Prerequisiti

Nozioni di base di algebra lineare e analisi

Contenuti dell'insegnamento

Nella prima parte del corso si introduce la programmazione matematica e si illustrano alcuni concetti di base relativi alla creazione di modelli di programmazione matematica utilizzati per la rappresentazione di problemi di decisione reali. Si introduce anche il linguaggio AMPL, un linguaggio di modellizzazione che consente un uso molto semplificato
dei principali software per la risoluzione dei problemi.
Questa parte richiede 12 ore.

Nella seconda parte si introduce la Programmazione Lineare (PL). Dopo una prima parte, dedicata
alla teoria della PL, si usa la teoria stessa per definire un algoritmo di risoluzione (l'algoritmo del simplesso). Si affrontano inoltre i temi relativi alla dualita' e all'analisi di sensitivita' (sensibilita' di soluzioni ottime e valore ottimo rispetto a perturbazioni dei dati). Questa parte richiede 30 ore, cosi' suddivise:
-Teoria PL: 6 ore
- Algoritmo simplesso e sue varianti: 14 ore
- Dualita': 6 ore
- Analisi sensitivita': 4 ore

Nella terza parte si parla di Programmazione Lineare Intera (PLI). Anche qui si parte da aspetti teorici per arrivare alla definizione di algoritmi di risoluzione, in particolare algoritmi di taglio, algoritmi branch and bound. Questa parte richiede 12 ore.

Nella quarta e ultima parte si parla di Programmazione Non Lineare. Si introducono le condizioni di ottimalita' e si illustrano le principali componenti di alcune procedure di risoluzione.
Questa parte richiede 12 ore

Programma esteso

Nella prima parte del corso si introduce la programmazione matematica e si illustrano alcuni concetti di base relativi alla creazione di modelli di programmazione matematica utilizzati per la rappresentazione di problemi di decisione reali. Si introduce anche il linguaggio AMPL, un linguaggio di modellizzazione che consente un uso molto semplificato
dei principali software per la risoluzione dei problemi.

Nella seconda parte si introduce la Programmazione Lineare (PL). Dopo una prima parte, dedicata
alla teoria della PL, si usa la teoria stessa per definire un algoritmo di risoluzione (l'algoritmo del simplesso). Si affrontano inoltre i temi relativi alla dualita' e all'analisi di sensitivita' (sensibilita' di soulzioni ottime e valore ottimo rispetto a perturbazioni dei dati).

Nella terza parte si parla di Programmazione Lineare Intera (PLI). Anche qui si parte da aspetti teorici per arrivare alla definizione di algoritmi di risoluzione, in particolare algoritmi di taglio, algoritmi branch and bound.

Nella quarta e ultima parte si parla di Programmazione Non Lineare. Si introducono le condizioni di ottimalita' e si illustrano le principali componenti di alcune procedure di risoluzione.

Bibliografia

Dispense fornite dal docente e rese disponibili in rete.

Metodi didattici

La principale modalita' di trasmissione della conoscenza e' la lezione frontale, durante la quale si cerca di coinvolgere gli studenti per portarli da soli alle conclusioni. Sono previste anche esercitazioni per consolidare quanto visto nelle lezioni. Non sono previste attivita' di laboratorio ma e' previsto un progetto di ricerca da svolgere a casa, eventualmente insieme ad altri.

Modalità verifica apprendimento

L'esame scritto e' suddiviso in due parti che possono essere sostenute in appelli diversi
(e' prevista anche una prova in itinere relativamente alla prima parte).
L'esame scritto e' composto da esercizi e domande di teoria che incidono allo stesso modo sulla votazione finale. L'esame orale e' previsto solo su richiesta dello studente.

Viene anche richiesto allo studente di lavorare a casa su un progetto, proposto dal docente o suggerito dallo studente stesso, in cui deve sviluppare tutte le fasi di lavoro del ricercatore operativo: traduzione del problema reale in un modello matematico, traduzione del modello in linguaggio AMPL, scelta di un opportuno solver, analisi della soluzione restituita dal solver
e sensitivita' della soluzione ottenuta rispetto a perturbazioni dei dati. Il lavoro eseguito deve essere riporato in una relazione che viene poi discussa con il docente. Puo' essere fatto in gruppo e assegna un punteggio aggiuntivo dai 2 ai 4 punti a seconda della sua difficolta'.

Altre informazioni

Il materiale didattico e' disponibile al sito elly.dii.unipr.it