Obiettivi formativi
<br />Il corso verte principalmente sulla modelizzazione di problemi reali attraverso modelli di Programmazione Lineare e Programmazione Lineare Intera con le relative tecniche di risoluzione. Il corso si pone come obiettivo quello di rendere lo studente capace di costruire almeno modelli semplici, di conoscere i metodi di risoluzione per tali modelli e la teoria che li sottende. L'attenzione è rivolta anche alla capacità di saper interpretare i risultati ottenuti, in particolare cercando di capire quanto questi siano sensibili rispetto a variazioni dei dati (analisi di sensitività). Allo studente vengono anche presentati nozioni basilari sui grafi e alcuni semplici algoritmi, tenuto conto che una larga parte di problemi di problemi di PLI sono problemi su grafi. <br />
Prerequisiti
L'organizzazione del modulo presuppone una buona conoscenza del calcolo vettoriale e matriciale, necessaria per poter comprendere il funzionamento delle tecniche di risoluzione presentate (algoritmo del simplesso per problemi di PL, algoritmi di taglio e branch-and-bound per i problemi di PLI).
Contenuti dell'insegnamento
<br />Introduzione alla Programmazione Matematica. Problemi di Programmazione Lineare: modelli costruiti a partire da problemi reali; risultati della teoria con in particolare il teorema fondamentale che consente di restringere la ricerca delle soluzioni ai vertici del problema; il metodo del simplesso con i suoi passi principali; interpretazione geometrica e algebrica del metodo del simplesso; teoria della dualitá con i teoremi fondamentali che legano le risoluzioni dei due problemi primale e duale; il metodo del simplesso duale; analisi di sensitivitá, ovvero l'analisi di quanto le soluzioni finali siano sensibili a variazioni dei dati dei problemi. Programmazione lineare intera: aspetti teorici ed in particolare i legami tra un problema di PLI ed il suo rilassamento lineare; brevissimi cenni di complessità; metodi di risoluzione; algoritmi di taglio ed in particolare tagli di Gomory; algoritmi di tipo branch-and-bound. Grafi: definizioni di base. Problema di flusso a costo minimo.
Programma esteso
- - -
Bibliografia
<br />- dispense del corso fornite dal docente<br />- R.J. Vanderbei, "Linear Programming", Kluwer Academic Publishers (solo per eventuali approfondimenti )
Metodi didattici
Le lezioni si tengono in aula e sono svolte tipicamente con l'ausilio di lucidi. <br /><br />Il controllo sull'apprendimento è basato sulla risoluzione in classe di alcuni esercizi durante la quale gli studenti possono interevenire e porre domande per dissipare eventuali dubbi. Le risoluzioni di alcuni esercizi sono fornite in anticipo agli studenti in modo da dar loro la possibilità di seguirle più facilmente. <br />La verifica si articolerà in una prova scritta dove verranno proposti esercizi del tipo di quelli risolti in aula e domande più legate alla teoria, attraverso cui si cerca di verificare quanto in profondità è andato lo studio da parte dello studente. Viene anche svolta una prova orale con discussione del compito ed eventuali domande di approfondimento.
Modalità verifica apprendimento
- - -
Altre informazioni
- - -
