Ricerca operativa
A.A. 2018/2019
Obiettivi formativi
Il corso si propone di introdurre i fondamenti della programmazione matematica e le relative tecniche algoritmiche, con particolare attenzione ai modelli di programmazione lineare e lineare intera. Vengono inoltre introdotti algoritmi per la programmazione non lineare non vincolata e algoritmi di ottimizzazione su grafo.
Risultati apprendimento attesi
Non definiti
Periodo: Secondo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Linea Milano
Responsabile
Periodo
Secondo semestre
STUDENTI FREQUENTANTI
Programma
Introduzione. Esempi di modelli di Programmazione lineare (PL) e PL intera. PL: risoluzione per via geometrica e descrizione dell'algoritmo del simplesso, prima e seconda fase. Dualità: lemma di Farkas, teoremi di dualità debole e forte, algoritmo del simplesso duale. Analisi di sensitività. PL intera: unimodularità, metodi dei piani di taglio e di Branch & Bound. Ottimizzazione su rete: problemi di albero ricoprente, cammino minimo, flusso massimo e flusso massimo a costo minimo.
Propedeuticità
Algebra lineare
Prerequisiti
L'esame consiste in una prova scritta ed in una prova orale obbligatorie per tutti.
La prova scritta richiede ad esempio:
- la costruzione di modelli di PL o PLI di semplici problemi di ottimizzazione;
- la soluzione per via grafica di modelli di PL in due variabili;
- l'applicazione del metodo di Branch & Bound a problemi di PLI in due variabili o a problemi di "zaino";
- l'individuazione di tagli di Gomory a partire dal tableau ottimo del rilassamento continuo di un problema di PLI;
- l'applicazione di algoritmi di ottimizzazione su rete a piccoli esempi.
Gli esercizi hannoi contenuti e difficolta' analoghi a quelli affrontati nelle esercitazioni svolte in aula.
Per la soluzione degli esercizi non è ammessa la consultazione di testi o appunti.
La prova orale consiste in una breve discussione del compito scritto e di un colloquio volto ad accertare la conoscenza dei prinicipali teoremi (e delle relative dimostrazioni) che sono a fondamento della PL e della PLI.
La prova scritta richiede ad esempio:
- la costruzione di modelli di PL o PLI di semplici problemi di ottimizzazione;
- la soluzione per via grafica di modelli di PL in due variabili;
- l'applicazione del metodo di Branch & Bound a problemi di PLI in due variabili o a problemi di "zaino";
- l'individuazione di tagli di Gomory a partire dal tableau ottimo del rilassamento continuo di un problema di PLI;
- l'applicazione di algoritmi di ottimizzazione su rete a piccoli esempi.
Gli esercizi hannoi contenuti e difficolta' analoghi a quelli affrontati nelle esercitazioni svolte in aula.
Per la soluzione degli esercizi non è ammessa la consultazione di testi o appunti.
La prova orale consiste in una breve discussione del compito scritto e di un colloquio volto ad accertare la conoscenza dei prinicipali teoremi (e delle relative dimostrazioni) che sono a fondamento della PL e della PLI.
Metodi didattici
STUDENTI NON FREQUENTANTI
Il corso si svolge mediante lezioni ed esercitazioni frontali, con l'ausilio o della lavagna tradizionale o di quella elettronica
Prerequisiti
La modalità d'esame è la stessa per frequentanti e non frequentanti
Docente/i
Ricevimento:
su appuntamento
stanza 3012 via Celoria 18