Ricerca Operativa D

(Corso di Diploma in Informatica)

Codice:

5I003

Crediti:

Semestre:

Sigla:

Docente

Maria Grazia Scutellà

Tel. 0502212771

Prerequisiti

Obiettivi di apprendimento

Fornire le conoscenze di base della Programmazione lineare e dei problemi di flusso.

Descrizione

Il corso si propone di fornire allo/a studente/essa le conoscenze di base della Programmazione lineare e dei problemi di flusso. Un rilevante spazio sarà dedicato alla presentazione di esempi di modellizzazione e soluzione di problemi.

English Description

The course is intended to provide basic knowledge of Linear programming and Network Flow techniques. Stress is given to examples of modeling and solution of problems.

Programma

Introduzione (2 ore)
- Problemi decisionali, problemi di ottimizzazione ed esistenza; classi di problemi.
- Classi di algoritmi (algoritmi greedy, algoritmi di ricerca locale ed algoritmi enumerativi).
Programmazione lineare (15 ore)
- Modelli di Programmazione Lineare, coppie di problemi Primale-Duale e teorema debole della dualità.
- Programmazione lineare su coni; teorema forte della dualità e sue conseguenze.
- Algoritmo del Simplesso Primale-Duale.
- Scarti complementari e interpretazione economica della dualità.
- Basi complementari e considerazioni geometriche.
- Algoritmo del simplesso primale ed algoritmo duale.
- Riottimizzazione ed analisi parametrica.
- Caso delle variabili limitate.
- Presenza di più obiettivi (Goal Programming).
Problemi di flusso su reti (8 ore)
- Problema di flusso di costo minimo
- Strutture-dati ed algoritmi di visita su grafi
- Algoritmi del simplesso (primale e duale) su rete
- Problema dei cammini minimi
- Problema del flusso massimo
- Albero di copertura minimo (MST)
- Problema del commesso viaggiatore (TSP)

(Le ore indicate non includono le esercitazioni)

Ore lezione:

Ore esercitazione: