Ricerca operativa
A.A. 2018/2019
Learning objectives
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.
Expected learning outcomes
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.
Course syllabus and organization
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
Professor(s)
Ricevimento:
su appuntamento
stanza 3012 via Celoria 18