1
UNIVERSITÀ DEGLI STUDI DI GENOVA
Corso di Laurea in Ingegneria Gestionale
Corso di Ricerca Operativa
A.A. 2020/2021
Docente: Mauro Gaggero
___________
PROGRAMMA DEL CORSO
1. Introduzione al corso e definizioni preliminari
1.1. Concetti generali riguardanti i problemi di ottimizzazione: definizioni di funzione obiettivo e variabili decisionali
1.2. Problemi di ottimizzazione lineare e non lineare: definizioni preliminari
1.3. Esempi di problemi formulabili come problemi di programmazione lineare: problema
del trasporto e problema della produzione di vernici
2
2. Programmazione lineare a variabili reali
2.1. Definizione di problema di programmazione lineare a variabili reali
2.2. Geometria della programmazione lineare. Concetto di poliedro dei vincoli e teoremi
fondamentali sui poliedri. Soluzione grafica di un problema di programmazione lineare
2.3. Esempi di risoluzione grafica di problemi di programmazione lineare
2.4. Approccio algebrico per la soluzione di problemi di programmazione lineare
2.5. Forma standard di un problema di programmazione lineare
2.6. Discussione su come riportare un qualunque problema di programmazione lineare alla forma standard: variabili di slack e surplus
2.7. Vettori e matrici di base e non di base. Concetto di soluzione di base e soluzione di
base ammissibile. Equivalenza tra soluzione di base ammissibile e vertici del poliedro dei vincoli. Teorema fondamentale della programmazione lineare
2.8. L’algoritmo del simplesso per la soluzione algebrica di un problema di
programmazione lineare
2.9. Discussione approfondita di tutte le fasi dell’algoritmo del simplesso 2.10. L’algoritmo del simplesso sul Tableau
2.11. Inizializzazione dell’algoritmo del simplesso con le variabili di slack
2.12. Esempi di risoluzione algebrica di semplici problemi di programmazione lineare mediante l’algoritmo del simplesso
2.13. Il metodo delle due fasi e il metodo del Big-M per l’inizializzazione di un problema di programmazione lineare
2.14. Esempi di inizializzazione di problemi di programmazione lineare con i metodi delle due fasi e del Big-M
3. Programmazione lineare a variabili intere
3.1. Definizione di problema di programmazione lineare a numeri interi
3.2. Forma standard di un problema di programmazione lineare a numeri interi e
definizione di problema rilassato
3.3. Esempi di problemi di programmazione lineare a numeri interi: problema dello zaino,
problema dell’assegnamento, problema del costo fisso, problema del sequenziamento
3.4. Soluzione grafica di problemi di programmazione lineare a numeri interi
3.5. Soluzione algebrica di problemi di programmazione lineare a numeri interi
3.6. Metodo del branch and bound
3.7. Esempi di problemi di programmazione lineare a numeri interi risolti con il metodo
del branch and bound. Interpretazione grafica dei problemi rilassati ai vari nodi 3.8. Metodo dei piani di taglio: il taglio di Gomory
3.9. Esempi di problemi di programmazione lineare a numeri interi risolti con il metodo
del taglio di Gomory. Interpretazione grafica dei problemi rilassati ai vari passi
4. Teoria della dualità
4.1. Introduzione alla teoria della dualità: concetti e definizioni preliminari
3
4.3. Teorema della dualità debole e teorema della dualità forte
4.4. Teorema dello scarto complementare
4.5. Esempi di problemi primali, trasformazione nei corrispondenti problemi duali, e risoluzione degli stessi per verificare sperimentalmente la validità della teoria della dualità
5. Programmazione matematica non vincolata
5.1. Definizione di problema di programmazione non lineare
5.2. Differenze e similitudini con i problemi di programmazione lineare
5.3. Esempi di problemi formalizzabili come problemi di programmazione non lineare.
5.4. Condizioni necessarie di ottimalità e condizioni sufficienti di ottimalità 5.5. Utilizzo delle condizioni di ottimalità per la ricerca di soluzioni
5.6. Algoritmi iterativi e algoritmi di discesa
5.7. Proprietà di convergenza finita e asintotica, proprietà di convergenza locale e globale 5.8. Concetti generali circa gli algoritmi di discesa: definizione di direzione di discesa e
algoritmo di discesa
5.9. Discussione dei principali punti che costituiscono un algoritmo di discesa 5.10. Algoritmo del gradiente e algoritmo di Newton
5.11. Approccio Lagrangiano per problemi di programmazione matematica non lineare vincolata: condizioni necessarie e condizioni sufficienti di ottimalità (condizioni di Karush-Kuhn-Tucker)
5.12. Utilizzo delle condizioni di ottimalità per la ricerca di soluzioni
5.13. Metodi delle funzioni di penalità e delle funzioni barriera per la risoluzione approssimata di problemi di programmazione non lineare vncolata
6. Ottimizzazione su grafi
6.1. Introduzione ai grafi e loro importanza per modellare problemi reali 6.2. Definizioni preliminari e rappresentazione dei grafi
6.3. Generalità sul problema dell’albero ricoprente di costo minimo in grafi non orientati 6.4. Algoritmo di Kruskal per la risoluzione di problemi di alberi ricoprenti minimi
6.5. Applicazione dell’algoritmo a grafi di esempio
6.6. Algoritmo di Prim-Dijkstra per la risoluzione di problemi di alberi ricoprenti minimi
6.7. Applicazione dell’algoritmo a grafi di esempio
6.8. Generalità sul problema dei percorsi minimi sui grafi orientati
6.9. Algoritmo di Dijkstra per la risoluzione di problemi di percorso minimo
6.10. Applicazione dell’algoritmo a grafi di esempio
6.11. Algoritmo di Floyd-Wharshall per la risoluzione di problemi di percorso minimo 6.12. Applicazione dell’algoritmo a grafi di esempio
7. Applicativi software per la programmazione lineare
7.1. Presentazione dei principali software per la risoluzione al calcolatore di problemi di programmazione lineare e non lineare
4
7.2. Introduzione generale a Excel, Lingo, Matlab
7.3. Esempi di utilizzo dei software per la risoluzione di problemi di prova
Riferimenti bibliografici
[1] D. Bertsimas, J.N. Tsitsiklis – Introduction to linear optimization. Athena Scientific, 1999. [2] D. Luenberger, Y. Ye – Linear and nonlinear programming. Springer, 2008.
