- Docente: Marco Antonio Boschetti
- Crediti formativi: 6
- SSD: MAT/09
- Lingua di insegnamento: Italiano
- Modalità didattica: Convenzionale - Lezioni in presenza
- Campus: Cesena
- Corso: Laurea in Ingegneria e scienze informatiche (cod. 8615)
Conoscenze e abilità da conseguire
Al termine del corso, lo studente conosce i principali modelli ed algoritmi per la programmazione lineare e intera.
Contenuti
1. Modelli matematici di problemi di ottimizzazione
Definizione di modello matematico, variabili decisionali, funzione obiettivo e requisiti o vincoli. Tecniche di modellizzazione matematica.
Esempi di modelli matematici tratti da problemi del mondo reale.
2. Programmazione Lineare Continua (PLC) ed intera (PLI).
Modelli matematici a variabili continue. Risoluzione geometrica. Teoria della PLC ed algoritmo del simplesso
Modelli matematici a variabili intere. Interpretazione geometrica. Proprietà dei problemi di PLI. Tecniche di rilassamento. Algoritmi cutting-plane (CP). Metodo branch-and-bound (B&B). Applicazioni della tecnica B&B.
3. Elementi di teoria dei grafi e principali problemi.
Principali definizioni della teoria dei grafi. Alberi di supporto di costo minimo (SST). Cammini minimi (CM). Problemi di flusso in rete (FR), flusso massimo, flusso a costo minimo. Assegnamento lineare.
Testi/Bibliografia
Dispense/slide a cura del docente disponibili online
Testi per sola consultazione:
- Matteo Fischetti, Lezioni di Ricerca Operativa, Libreria Progetto.
- C. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, NY.
- R.K.Ahuja, T.L.Magnanti, J.B.Orlin, "Network flows: theory, algorithms and applications", Prentice Hall.
- M. Gondran, M. Minoux, “Graphs and Algorithms”, John Wiley.
- M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear Programming and Network Flows, Wiley.
Metodi didattici
Lezioni frontali teoriche ed esercitazioni.
Implementazione degli algoritmi mediante linguaggi di programmazione ed uso di risolutori.
Modalità di verifica e valutazione dell'apprendimento
La verifica dell'apprendimento avviene mediante una prova scritta, che ha lo scopo di esaminare l'acquisizione delle conoscenze previste dal programma del corso.
Strumenti a supporto della didattica
Materiale didattico, dispense, slides, esercizi ed esempi disponibili in Virtuale. Uso di linguaggi di programmazione e risolutori.
Orario di ricevimento
Consulta il sito web di Marco Antonio Boschetti