Course Syllabus
Obiettivi
Le Ricerca operativa (OR) riguarda lo studio di metodi analitici di supporto al processo decisionale. È una disciplina della matematica applicata con un ampio spettro di applicazioni tra i quali informatica, ingegneria ed economia. L’obiettivo di questo corso è quello di fornire agli studenti le competenze necessarie per la formulazione di modelli matematici che rappresentino i problemi del mondo reale e per identificare le metodologie più idonee alla soluzione di questi modelli. Verranno affrontati i seguenti argomenti: ottimizzazione di funzioni non lineari, programmazione lineare, programmazione intera, con diversi esempi di applicazione.
In riferimento ai descrittori di Dublino:
Conoscenza e comprensione
Al termine del corso, lo studente sarà in grado di:
Conoscere i fondamenti teorici della programmazione matematica: problemi di programmazione lineare (PL), lineare intera (PLI) e non lineare (PNL), incluse dualità e condizioni di ottimalità (KKT)
Comprendere in profondità algoritmi chiave quali: Metodo grafico, Simplesso e dualità per PL, Branch and Bound per PLI., Tecniche di ottimizzazione non lineare: bisezione, Newton, gradienti, KKT
Assimilare l’uso di Python con la libreria PuLP come strumento per modellazione e soluzione di problemi
Capacità di applicare conoscenza e comprensione
Lo studente sarà capace di:
Tradurre problemi reali (ingegneristici, economici, informatici) in modelli di PL, PLI e PNL.
Eseguire manualmente (grafico, Simplesso, Branch and Bound) e con software (PuLP/Python) la risoluzione dei modelli.
Interpretare e analizzare i risultati (ottimo, costi, analisi di Sensitività), anche attraverso esempi applicativi
Autonomia di giudizio
Competenze critiche sviluppate tramite:
Esercitazioni durane le quali si modellano e risolvono problemi reali, giustificando ipotesi e scelta del metodo .
Prove scritte che richiedono di selezionare il corretto approccio (PL/PLI/PNL), eseguire calcoli e motivare le procedure adottate.
Prova orale (non obbligatoria) in cui gli studenti devono giustificare le scelte metodologiche e discutere criticamente i risultati .
Abilità comunicative
Lo studente svilupperà capacità comunicative mediante:
Assignments (non obbligatori) ed esame scritto con esercizi e domande aperte, in cui espone la formulazione del problema, la strategia di soluzione e le conclusioni.
Discussioni in aula per motivare le decisioni prese e confrontarsi con i docenti e i colleghi sugli esiti
Prova orale facoltativa, in cui viene misurata l’arte di comunicare chiaramente conoscenze, metodi e risultati ottenuti .
Capacità di apprendere autonomamente
Strumenti e metodi per favorire uno studio continuativo:
Materiale didattico supplementare: slide, esempi risolti, oltre a bibliografie e testi (Hillier & Lieberman, Bertsimas & Tsitsiklis, Bazaraa et al.)
Uso della libreria PuLP e Python, che incoraggia l’auto‑formazione e l’estensione degli esercizi a nuove casistiche.
Contenuti sintetici
A. Programmazione lineare
B. Programmazione lineare intera
C. Programmazione non lineare
Programma esteso
Introduzione alla Programmazione Matematica
A. Programmazione lineare
1. Introduzione alla programmazione lineare (PL): proprietà dei problemi di PL, strategie di modellizzazione
2. Soluzione grafica: soluzione grafica per problemi di PL
3. Geometria della Programmazione lineare e metodo del simplesso
4. Dualità
B. Programmazione lineare intera
1. Introduzione alla programmazione lineare intera (PLI)
2. proprietà dei problemi di PLI e strategie di modellizzazione
3. Metodo del Branch and Bound
C. Ottimizzazione non lineare
1. Ottimizzazione di funzioni non lineari ad una variabile: ricerca dicotomia-metodo Bisezione- metodo Newton
2. Ottimizzazione di funzioni non lineari mutivariate: metodo Gradiente-metodo Newton
3. Ottimizzazione non lineare vincolata: condizioni di Karush-Kuhn-Tucker
Prerequisiti
- Algebra lineare; vettori, matrici, sistemi di equazioni lineari, ...
- Funzione; in una variabile, in più variabili, convessa, derivata, gradiente, hessiana, ...
Modalità didattica
Lezioni, esercizi e demo sw.
Il corso verra' erogato in italiano.
- 32 lezioni teoriche di 2 ore l'una in presenza fisica sotto forma di didattica erogativa
- 20 esercitazioni di 2 ore l'una in presenza fisica sotto forma di didattica erogativa
- 24 ore di laboratorio di cui fino ad un massimo di 3 ore erogate in modalità interattiva in presenza e 3 ore erogate in modalità interattiva online
Materiale didattico
Libro di testo principale
- Frederick S. Hillier and Gerald J. Lieberman, Ricerca Operativa, McGraw-Hill, nona edizione, 2010.
Libri di testo addizionali
- Dimitris Bertsimas and John Tsitsiklis, introduzione all’ottimizzazione lineare, Belmont, Massachusetts, 2008.
- Mokhtar S. Bazaraa, John J. Jarvis, Hanif D. Sherali, Linear Programming and Network Flows, Wiley, 4th edition, 2010.
- Mokhtar S. Bazaraa, Hanif D. Sherali, C. M. Shetty, Nonlinear programmazione: teorie e algoritmi, Wiley, 3th edition, 2006.
Software
- Python + Libreria PuLP: https://www.python.org/ + https://pypi.org/project/PuLP/
Materiale aggiuntivo; saranno rese disponibili le slide delle lezioni ed alcuni esercizi risolti.
Periodo di erogazione dell'insegnamento
Primo semestre
Modalità di verifica del profitto e valutazione
Due modalità alternative:
1. Durante l'erogazione delle lezioni - PROVE PARZIALI
- due prove parziali, ogni prova assegna un massimo di 15 punti,
- le date delle due prove parziali saranno comunicate entro la prima settimana di erogazione delle lezioni
- le due prove parziali si svolgono nei laboratori dell'Università di Milano-Bicocca
- si accede alla seconda prova parziale se si merita un voto almeno pari a 6 punti su 15 nel primo parziale, in caso contrario si veda modalità d'esame 2)
- la seconda prova parziale è da considerarsi superata se si ottiene un punteggio almeno pari a 6 punti su 15, in caso contrario si veda modalità d'esame 2)
- il voto assegnato nelle due prove parziali si somma e determina il voto finale (arrotondato per eccesso)
- l'esame si considera superato (verbalizzato) se il voto finale è maggiore o uguale a 18
- la prova orale è facoltativa, a richiesta del candidato che abbia meritato un voto almeno pari a 18, e assegna un massimo di 3 punti che si vanno a sommare al voto delle due prove parziali
- se la prova orale fosse particolarmente negativa è possibile che il voto delle due prove parziali venga diminuito fino ad un massimo di 3 punti
2. Al termine dell'erogazione delle lezioni - PROVA ORDINARIA
- la prova d'esame ordinaria si svolge nei laboratori dell'Università di Milano-Bicocca
- la prova d'esame ordinaria consiste di due fasi
- la prima fase della prova d'esame ordinaria prevede 10 domande a risposta chiusa sui pre-requisiti del corso
- si viene ammessi alla seconda fase della prova d'esame ordinaria se si risponde correttamente ad almeno 6 domande
- la seconda fase della prova d'esame ordinaria assegna un massimo di 30 punti (arrotondamento per eccesso)
- prima e seconda fase della prova d'esame ordinaria hanno luogo sequenzialmente e senza interruzione temporale
- la prova d’esame è superata (verbalizzata) se si ottiene un voto maggiore o uguale a 18
- la prova orale è facoltativa e a richiesta del candidato che abbia meritato un voto almeno pari a 18, e assegna un massimo di 3 punti che si vanno a sommare al voto della prova in laboratorio
- se la prova orale fosse particolarmente negativa è possibile che il voto della prova in laboratorio venga diminuito fino ad un massimo di 3 punti
Orario di ricevimento
Fabio Stella su appuntamento
Guglielmo Lulli su appuntamento
Enza Messina su appuntameento
Mauro Passacantando su appuntamento
Aims
Operations research (OR) is the study of scientific tools that deals with the application of advanced analytical methods to help make better decisions. It is a key branch of applied mathematics with applications in a wide spectrum of areas including computer science, engineering and economics.The goal of this course is to teach students to formulate mathematical models that represent real-world problems and to recognize approaches and tools to solve these models.
Namely, we will cover nonlinear, linear, network flow and integer optimization problems, with applications in planning, economics, business, and engineering.
According to the Dublin Descriptors:
Knowledge and Understanding
By the end of the course, the student will be able to:
Understand the theoretical foundations of mathematical programming: linear programming (LP), integer linear programming (ILP), and nonlinear programming (NLP), including duality and optimality conditions (KKT).
Demonstrate in-depth comprehension of key algorithms such as: graphical method, Simplex and duality for LP, Branch and Bound for ILP, and nonlinear optimization techniques including bisection, Newton's method, gradient methods, and KKT conditions.
Assimilate the use of Python with the PuLP library as a tool for modeling and solving optimization problems.
Applying Knowledge and Understanding
The student will be able to:
Translate real-world problems (engineering, economics, computer science) into LP, ILP, and NLP models.
Solve models manually (graphical method, Simplex, Branch and Bound) and through software tools (PuLP/Python).
Interpret and analyze results (optimal solutions, costs, sensitivity analysis), also through applied examples.
Making Judgements
Critical thinking skills will be developed through:
Practical exercises involving the modeling and solution of real problems, with justification of assumptions and methodological choices.
Written exams requiring the selection of the appropriate approach (LP/ILP/NLP), execution of calculations, and explanation of adopted procedures.
An optional oral exam where students are required to justify methodological choices and critically discuss results.
Communication Skills
The student will develop communication abilities through:
Assignments (optional) and a written exam including exercises and open-ended questions, in which the student presents problem formulation, solution strategy, and conclusions.
Classroom discussions aimed at justifying decisions and comparing outcomes with peers and instructors.
An optional oral exam assessing the ability to clearly communicate knowledge, methods, and obtained results.
Learning Skills
Tools and methods to support continuous learning include:
Supplementary teaching materials: slides, solved examples, along with bibliographies and reference texts (Hillier & Lieberman, Bertsimas & Tsitsiklis, Bazaraa et al.).
Use of the PuLP library and Python, which encourages self-learning and the extension of exercises to new case studies.
Contents
A. Linear programming
B. Linear integer programming
C. Non linear programming
Detailed program
Introduction to Mathematical Programming
A. Linear Programming
1. Introduction to Linear Programming (LP): poperties and modelling strategies
2. Graphical solution method
3. Geometry of LP and the simplex method
4. Duality
B. Integer Linear Programming
1. Introduction to integer linear programming (ILP)
2. Properties and modelling strategies
3. Branch and Bound
C. Non Linear Programming
1. Oprimizing non linear functions of a single variable
2. Oprimizing non linear functions of multiple variables
3. Optimizing constrained non linear functions, Karush-Kuhn-Tucker conditions
Prerequisites
- Linear Algebra; vector, matrix, sistem of linear equations, ...
- Function; of one variable, of more variables, convex, derivative, gradient, hessian, ...
Teaching form
Lectures, exercises and demo using sw
The course will be delivered in Italian.
- 32 lectures of theory of 2 hours each in presence of erogative nature
- 20 excercise lectures of 2 hours each in presence of erogative nature
- 24 laboratory lectures of 2 hours each (of which 3 hours of interactive lectures in presence and a maximum of 3 hours of interactive lectures on line)
Textbook and teaching resource
Main textbook
- Frederick S. Hillier and Gerald J. Lieberman, Ricerca Operativa, McGraw-Hill, 9th edition, 2010.
Additional textbooks
- Dimitris Bertsimas and John Tsitsiklis, Introduction to Linear Optimization, Belmont, Massachusetts, 2008.
- Mokhtar S. Bazaraa, John J. Jarvis, Hanif D. Sherali, Linear Programming and Network Flows, Wiley, 4th edition, 2010.
- Mokhtar S. Bazaraa, Hanif D. Sherali, C. M. Shetty, Nonlinear Programming: Theory and Algorithms, Wiley, 3th edition, 2006.
Software
- Python + Libreria PuLP: https://www.python.org/ + https://pypi.org/project/PuLP/
Additional Material
Slides of the lectures and some solved exercises will also be available
Semester
I semester
Assessment method
Two alternatives
1. During lecturing period - INTERMEDIATE EXAMS
- two intermediate exams, each one awards a maximum of 15 points,
- the dates will be communicated during the first lecturing week
- intermediate exams take place in the Università di Milano-Bicocca laboratories
- the access to the second intermediate exam is allowed to students awarded with at least 6 points in the first intermediate exam, in case this condition is not met refer to exam form 2)
- the second intermediate exam is valid only if the student is awarded at least 6 points, if thi is not the case please refer to exam form 2)
- the final grade is the aritmetinc sum of the grades awarded in the two intermediate exams
- the exam is passed only if the final grade is at least equal to 18
- the oral exam is facoltative and allowed only to a student awarded at least 18 points, it awars a maximum of 3 points tto be added to the base grade
- if the oral exam is particular bad then it may be the case the base grade is lowered of a maximum of 3 points
2. When the lecturing period is over - STANDARD EXAM
- the exam takes place at the Università di Milano-Bicocca laboratories
- the exam consists of two phases
- phase 1 consists of 10 closed-form quizzes about course pre-requisites
- phase 2 happens only if you have been awarded at least 6 points (at least 6 quizzes are corret) at phase 1
- Phase 2 awards a maximum of 30 points
- Phase 1 and Phase 2 happen in strinct sequence, without any temporal lag
- the exam is successful if the student is awarded at least 18 points
- the oral exam is facoltative and allowed only to a student awarded at least 18 points, it awars a maximum of 3 points tto be added to the base grade
- if the oral exam is particular bad then it may be the case the base grade is lowered of a maximum of 3 points
Office hours
Fabio Stella by appointment
Guglielmo Lulli by appointment
Enza Messina by appointment
Mauro Passacantando by appointment