elenco     
        corso     

Ricerca Operativa A

Codice: 029AACrediti: 6Semestre: 2Sigla: RO 
 
Settore disciplinare: MAT/09 - Ricerca Operativa

Docente

Maria Grazia Scutellà   scut@di.unipi.it  Stanza 363  Tel. 0502212771

Prerequisiti

Per sostenere l'esame e' necessario aver superato gli esami di Algoritmica e Laboratorio (008AA) e Matematica Discreta (006AA). Sarebbe opportuno, inoltre, aver superato l'esame di Analisi Matematica (005AA).

Obiettivi di apprendimento

Il corso si prefigge l'obiettivo di guidare lo studente nella formulazione di modelli matematici per rilevanti problemi applicativi, e di illustrare tecniche algoritmiche, per alcune famiglie base di problemi di ottimizzazione, a partire da proprietà teoriche caratterizzanti tali famiglie (i problemi di flusso su rete ed i problemi di programmazione lineare).

Conoscenze.

Lo studente acquisirà competenze che gli permetteranno di formulare significativi modelli di ottimizzazione, prevalentemente modelli di flusso su rete e modelli di ottimizzazione, ma anche modelli di programmazione lineare intera. Apprenderà inoltre proprietà matematiche che lo condurranno alla progettazione di approcci algoritmici di base per due importanti classi di problemi di ottimizzazione: problemi di flusso su rete e programmazione lineare.

Capacità.

Lo studente sarà in grado di formulare modelli matematici per rilevanti problemi applicativi, e risolvere problemi di flusso su rete e problemi di programmazione lineare.

Comportamenti.

Lo studente acquisirà non solo competenze ma anche capacità critiche che, sia a livello modellistico che algoritmico, risulteranno rilevanti in svariati ambiti lavorativi, sia a livello progettuale che implementativo.

Descrizione

Il corso presenta gli strumenti necessari alla definizione e alla risoluzione di modelli analitici di ottimizzazione per problemi reali, tipicamente di gestione, di allocazione delle risorse e di logistica. Verranno introdotte proprietà teoriche ed alcune delle principali tecniche algoritmiche per la risoluzione di due grandi famiglie di problemi di ottimizzazione: i problemi di flusso su rete ed i problemi di programmazione lineare.

English Description

This course presents the necessary tools for the construction and resolution of analytical models of optimisation, management, allocation of resources and logistics.

Programma

  1. Introduzione (2 ore)

    • Problemi decisionali, problemi di ottimizzazione ed esistenza
    • Classi di problemi: alcuni esempi.
  2. Grafi e Reti di flusso (18 ore)

    • Un modello generale per i problemi di flusso su rete
    • Alberi, cammini e tagli, visite di grafi e alberi
    • Il problema dei cammini minimi
    • Il problema dell'albero di copertura di costo minimo
    • Il problema del flusso massimo
    • Il problema di accoppiamento di massima cardinalitt&agrave.
  3. Programmazione Lineare (18 ore)

    • Modelli di Programmazione Lineare e coppie di problemi duali
    • Teoria della dualit&agrave: teorema debole della dualit&agrave, direzioni ammissibili e/o di crescita, Lemma di Farkas; teorema forte della dualit&agrave
    • Algoritmo del Simplesso Primale e sua interpretazione geometrica;
    • Teorema degli scarti complementari
    • Algoritmo del Simplesso Duale e sua interpretazione geometrica.
  4. Modelli per problemi di ottimizzazione pi&ugrave generali (10 ore)

    • Tipi di variabili: logiche, continue, discrete
    • Formulazioni di vincoli
    • Formulazioni della funzione obiettivo
    • Esempi di problemi reali.
     

Bibliografia

Modalità di esame

Prova scritta seguita da una prova orale. Sono ammessi alla prova orale solamente gli studenti che hanno superato la prova scritta (con votazione pari almeno a "quasi sufficiente"). Sono esonerati dalla prova scritta gli studenti che hanno superato entrambe le verifiche intermedie.


Ulteriore pagina web del corso: http://www.di.unipi.it/di/groups/optimize/ORGroup.html


home


email