Corso di: RICERCA OPERATIVA I
Laurea in Informatica
Anno accademico: 2002-2003
Docente: Lionello Cantoni
INDICE
Obiettivi del corso
Il corso si propone di rendere familiari agli studenti due importanti classi
di problemi di ottimizzazione, la programmazione lineare e la programmzaione
lineare intera, evidenziandone sia gli aspetti teorici che quelli applicativi,
e dare ad essi alcune nozioni di base sulla teoria dei grafi.
Prerequisiti del corso
Conoscenze di calcolo matriciale.
Modalità d'esame
L'esame sará costituito da una parte scritta con esercizi relativi
al programma svolto. La parte orale sará facoltativa per gli studenti
che supereranno l'esame con votazione non inferiore al 18.
Libri di testo
-
Muracchini, Guidotti, Programmazione Matematica, UTET
-
Dispense del docente
Programma dettagliato del corso
Problemi di programmazione lineare: metodi, modelli e teoria. Algoritmo
del simplesso. Metodo due fasi. Teoria della dualita'. Simplesso duale.
Programmazione lineare intera. Modelli. Algoritmi di taglio: tagli di Gomory
e di Dantzig. Teoria dei grafi. Tipologie di grafi. Grafi connessi, fortemente
connessi e quasi fortemente connesi. Bipartizione. Grafi planari
e topologicamente planari.
Problema del trasporto:algoritmo di Hitchcock.
|