- Docente: Daniele Vigo
- Crediti formativi: 6
- SSD: MAT/09
- Lingua di insegnamento: Italiano
- Moduli: Daniele Vigo (Modulo 1) Daniele Vigo (Modulo 2)
- Modalità didattica: Convenzionale - Lezioni in presenza (Modulo 1) Convenzionale - Lezioni in presenza (Modulo 2)
- Campus: Cesena
- Corso: Laurea in Ingegneria e scienze informatiche (cod. 8615)
-
Orario delle lezioni (Modulo 1)
dal 19/09/2025 al 24/10/2025
-
Orario delle lezioni (Modulo 2)
dal 27/10/2025 al 19/12/2025
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 ed esercitazioni in aula
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
Dispense/slide a cura del docente disponibili online
Orario di ricevimento
Consulta il sito web di Daniele Vigo
SDGs
L'insegnamento contribuisce al perseguimento degli Obiettivi di Sviluppo Sostenibile dell'Agenda 2030 dell'ONU.