Introduzione ai problemi di Ottimizzazione. Esempi: problemi di pianificazione delle risorse, problemi di scheduling.
Esempi di problemi non lineari. L’approccio modellistico ai problemi di ottimizzazione. Modelli deterministici e modelli stocastici.
Problemi di ottimizzazione continua, discreta e mista. Esempi di definizione di modelli di programmazione matematica.
Programmazione lineare. Esempi classici di problemi di programmazione lineare: il problema della dieta. Problemi in forma standard.
Regione ammissibile. Insiemi convessi. Soluzioni ammissibili e soluzione ottima. Il caso di una regione ammissibile illimitata.
Soluzioni multiple. Il metodo grafico per problemi di programmazione lineare in due dimensioni. Problemi di programmazione lineare in
forma standard. Variabili slack. Il Problema aumentato. Il metodo del simplesso. Struttura tabellare del metodo del simplesso.
Il caso delle funzioni illimitate. Il caso delle soluzioni multiple. Soluzioni degeneri. Regole anticiclo: La regola di Bland.
Problemi in forma non standard. Minimizzazione di funzioni lineari. Il caso di variabili decisionali con valori negativi.
Variabili decisionali limitate. Vincoli di uguaglianza. Vincoli tipo maggiore-uguale. Variabili artificiali e variabili surplus.
Definizione del problema artificiale. Il metodo del simplesso a due fasi. Analisi Postottimale. Prezzi ombra.
Il problema del trasporto: il modello matematico. Condizione di ammissibilità per il problema del trasporto. Il problema della BFS iniziale.
La Regola del Nord-Ovest. Il metodo di Vogel. Il metodo di Russell. Il caso dell BFS degeneri. Il metodo del simplesso per il problema del
trasporto. Proprietà di interezza delle soluzioni. Il problema del trasporto con una sorgente o una destinazione fittizia. Il caso dei costi
indefiniti.
Problemi di programmazione lineare binaria. Il problema dello zaino. Il problema di assegnamento. Il metodo ungherese per il problema di
assegnamento.
Problemi di ottimizzazione su reti. Definizione di Grafo orientato e non orientato. Proprietà e terminologia dei grafi.
Il problema di minimo albero ricoprente. L'algoritmo di Prim. L'algoritmo di Kruskal. Il metodo Reverse-Delete. Lati di diminuazione.
Condizione di ottimalità per un albero ricoprente. Il problema del cammino minimo. L’algoritmo di Dijkstra. Tecniche reticolari di gestione dei
progetti. PERT e CPM. Tecniche AON e AOA. Definizione di cammino critico. Diagrammi di Gantt.
Problemi di programmazione lineare binaria e intera. Il metodo Branch-and-Bound per problemi binari. Definizione dei sottoproblemi.
Soluzione incombente. Criteri di Fathoming. Test di ottimalità. Il metodo Branch-and-Bound per problemi interi o misti.
Criteri di Fathoming per problemi di programmazione intera.
Modalità di svolgimento dell'esame
L'esame consiste in una prova scritta che prevederà sia esercizi che quesiti teorici riguardanti tutto il programma del corso. Il calendario delle prove sarà pubblicato dopo la scadenza dei termini per la prenotazione su Esse3.