Sillabo dell'insegnamento

• MAT - Crediti di MATEMATICA
MAT/09 - Ricerca Operativa
Problemi combinatorici e di ottimizzazione combinatorica. Definizioni fondamentali.
MAT/09 - Ricerca Operativa
L'algoritmo (enumerativo) universale e la sua complessità. Problemi subclusivi e superclusivi.
MAT/09 - Ricerca Operativa
Esempi: knapsack 0-1, edge-cover, insieme stabile, albero ricoprente, matching (perfetto) etc.
MAT/09 - Ricerca Operativa
L'algoritmo ingordo: pseudocodice per problemi subclusivi e superclusivi. Proprietà di scambio e sue implicazioni sulla cardinalità delle soluzioni massimali.
MAT/09 - Ricerca Operativa
Limiti dell'algoritmo ingordo. Teorema di Rado, matroidi. Esempi: matroide banale, matroide grafico, matroide partizione, matroide vettoriale. .
MAT/09 - Ricerca Operativa
Modelli di programmazione lineare e lineare intera Problemi di programmazione lineare, soluzione ammissibile e soluzione ottima, forma canonica, generale e standard.
MAT/09 - Ricerca Operativa
Esempi: il problema della dieta, ottimizzazione di un processo di produzione, problemi max-min (giochi a somma zero), gestione ottima di un portafoglio titoli etc.
MAT/09 - Ricerca Operativa
Formulazione di problemi di ottimizzazione combinatorica come programmazione lineare 0-1.
MAT/09 - Ricerca Operativa
Esempi: clique, insieme stabile, node-cover, colorazione, (s, t)-cammino minimo, problema del commesso viaggiatore.
MAT/09 - Ricerca Operativa
Programmazione intera: knapsack intero, ottimizzazione di un palinsesto televisivo etc.
MAT/09 - Ricerca Operativa
Teoria della dualità Teorema e metodo di Fourier-Motzkin. Teoremi dell'alternativa: Teorema di Gale, Lemma di Farkas, esempi.
MAT/09 - Ricerca Operativa
Il metodo del simplesso. Applicazioni alla programmazione lineare intera ed esempi.