Programmazione Matematica B

(Corso di Laurea in Informatica (quinquennale))

Codice:

4I016

Crediti:

Semestre:

Sigla:

Docente

Antonio Frangioni

Tel. 0502212789

Prerequisiti

Matematica Discreta
Analisi Matematica I
Algoritmi e Strutture Dati I

Obiettivi di apprendimento

Fornire allo/a studente/essa le conoscenze di base relative alla Programmazione Lineare e ai problemi di flusso su rete.

Descrizione

Il corso si propone di fornire allo/a studente/essa le conoscenze di base relative alla Programmazione Lineare e ai problemi di flusso su rete. Il corso presenterà principalmente classi di algoritmi per la soluzione dei diversi problemi di ottimizzazione affrontati, con la relativa teoria; saranno comunque discussi alcuni aspetti relativi alla modellazione di problemi di ottimizzazione ed alle possibili applicazioni.

English Description

The course is intended to provide basic knowledge of Linear Programming techniques and network flow algorithms. The course is mainly focused over algorithms and their theory, however some issues related to the construction of mathematical models and to possible applications are also discussed.

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).
Grafi e Reti di flusso (10 ore)
- Introduzione: alberi, cammini e tagli.
- Cammini minimi e alberi di copertura ottimi.
- Flusso massimo.
- Flusso di costo minimo.
- Accoppiamenti su grafi bipartiti.
Programmazione lineare (13 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).

(Le ore indicate non includono le esercitazioni)

Ore lezione:

Ore esercitazione:

Bibliografia

Modalità di esame

Prova scritta seguita da una prova orale. I contenuti dell'esame sono quelli del corso dell'Anno Accademico a cui si riferisce l'appello, anche per gli studenti che avessero seguito il corso in anni precedenti.

Gli studenti di Scienze dell'Informaz