1. Modelli di programmazione lineare: modelli di allocazione di risorse e modelli di miscelazione. Elementi di programmazione lineare.
2. Modelli di ottimizzazione su rete:
problema di flusso a costo minimo;
problema del percorso ottimo; problema del massimo flusso; problema del minimo albero ricoprente. Algoritmi di risoluzione.
3. Modelli di programmazione mista intera lineare. Elementi di teoria poliedrale. Algoritmi per la programmazione mista intera.
Integer programming (M. Conforti, G. Cornuéjols, G. Zambelli) Springer International Publishing.
Obiettivi Formativi
L’insegnamento vuole introdurre i problemi di programmazione matematica e fornire competenze sulle principali proprietà matematiche di questa classe di problemi. In particolare, vengono affrontati problemi di programmazione lineare, problemi di flusso su rete, problemi di programmazione mista intera lineare, analizzando le loro particolari proprietà geometriche ed analitiche. Vengono quindi introdotti algoritmi e metodologie per la loro soluzione.
Al termine del corso si dovrà essere in grado di classificare i diversi problemi di programmazione matematica e conoscere le più importanti caratterizzazioni matematiche
delle loro soluzioni. [punto A) Conoscenza e capacità di comprensione]. Si dovrà inoltre
dimostrare di saper applicare le conoscenze acquisite nel formulare in termini matematici alcune classi di problemi reali. [punto B) Capacità di applicare conoscenza e comprensione]. In particolare, la verifica del possesso dell’autonomia di giudizio, viene effettuata mediante una prova in cui si deve essere in grado di definire un
modello di programmazione matematica [ punto C) Autonomia di giudizio]. Si dovrà inoltre dimostrare di aver acquisito un linguaggio scientifico appropriato
nella descrizione e interpretazione dei principali problemi di programmazione matematica, acquisizione valutata sulla base di una prova orale [ punto D) Abilità comunicative].
Infine, si dovrà aver acquisito una padronanza delle nozioni e delle metodologie di base, che consenta un eventuale ulteriore approfondimento di argomenti legati alla ricerca operativa e all'ottimizzazione [punto E) Capacità di apprendimento].
Prerequisiti
Sono da considerarsi prerequisiti indispensabili le nozioni di base dell'algebra lineare e della geometria dello spazio reale n dimensionale.
Metodi Didattici
In prevalenza didattica frontale. Sono previste attività seminariali e lezioni in modalità "flipped".
Altre Informazioni
Il corso utilizza in parte materiali e risorse online
Modalità di verifica apprendimento
Esame orale attraverso il quale si verifica mediante quesiti e domande teoriche:
- la capacità di formulare modelli di ottimizzazione;
- la capacità di descrivere e utilizzare gli algoritmi analizzati nel corso;
- la capacità di adattare modelli e algoritmi di ottimizzazione per la soluzione di problemi complessi previa identificazione della loro struttura.
Programma del corso
Parte 1.
Modelli di programmazione lineare: modelli di allocazione di risorse e modelli di miscelazione. Elementi di programmazione lineare. Teoria della dualità. Il metodo del simplesso.
Parte 2. Modelli di ottimizzazione su rete:
Problema di flusso a costo minimo - Algoritmo del simplesso su rete
Problema del percorso ottimo - Algoritmo di Dijkstra;
Problema del massimo flusso - Algoritmo di Ford & Fulkerson;
(Problema del minimo albero ricoprente - Algoritmo di Kruskal.)
Altri modelli di ottimizzazione su rete: problema di abbinamento, problema di trasporto.
Parte 3. Modelli di programmazione mista intera lineare. Uso di variabili binarie per modellare vincoli logici. Elementi di teoria poliedrale: il teorema fondamentale della programmazione intera. Metodo dei piani di taglio, Metodi Branch & Bound e Branch & Cut. Rilassamento Lagrangiano.