• Non ci sono risultati.

Program of the course (in Italian)

N/A
N/A
Protected

Academic year: 2021

Condividi "Program of the course (in Italian)"

Copied!
5
0
0

Testo completo

(1)

UNIVERSITÀ DEGLI STUDI DI GENOVA

Corso di Laurea Specialistica in Ingegneria Gestionale

Corso di Ricerca Operativa 2 (CD) – codice 60204

A.A. 2011/2012

     

 

Docente: Mauro Gaggero

___________

PROGRAMMA DEL CORSO

       

1. Introduzione al corso e definizioni preliminari

1.1. Problema di programmazione non lineare in forma standard libero e vincolato 1.2. Definizioni di punti di minimo e massimo locali e globali

1.3. Esempi di problemi formulabili come problemi di programmazione non lineare  

 

2. Condizioni di esistenza della soluzione

(2)

2.2. Forme e funzioni quadratiche

2.3. Gradiente, Hessiana, matrici simmetriche, matrici definite positive e negative

3. Problemi di ottimizzazione convessi

3.1. Definizione e proprietà di funzioni convesse 3.2. Definizione e proprietà di insiemi convessi

3.3. Definizione e proprietà di problemi di programmazione non lineare convessi

4. Programmazione matematica non vincolata

4.1. Condizioni necessarie di ottimalità e condizioni sufficienti di ottimalità 4.2. Condizioni di ottimalità per funzioni quadratiche

4.3. Utilizzo delle condizioni di ottimalità per la ricerca di soluzioni

4.4. Esempi di applicazione delle condizioni di ottimalità per la risoluzione di semplici problemi di ottimizzazione

4.5. Algoritmi iterativi e algoritmi di discesa

4.6. Proprietà di convergenza finita e convergenza asintotica 4.7. Proprietà di convergenza locale e globale

4.8. Concetti generali circa gli algoritmi di discesa: definizione di direzione di discesa e algoritmo di discesa

4.9. Discussione dei principali punti che costituiscono un algoritmo di discesa: scelta del punto iniziale, criteri di arresto, scelta della direzione di discesa, scelta del passo di discesa

4.10. Principali situazioni in cui ci si può trovare durante l’utilizzo di un metodo di discesa: minimi locali e fenomeno dello zig-zag.

5. Algoritmo del gradiente

5.1. Definizione dell’algoritmo e principali proprietà

5.2. Teorema di convergenza dell’algoritmo del gradiente a passo fisso 5.3. Definizione della velocità di convergenza di un algoritmo di discesa 5.4. Esempi di applicazione dell’algoritmo del gradiente a funzioni di prova

5.5. Varianti dell’algoritmo del gradiente: algoritmo del gradiente a passo non costante 5.6. Metodi di ricerca di linea esatta (caso quadratico e non) e inesatta (metodo di Armijo

e del passo decrescente)

5.7. Applicazione del metodo del gradiente per la minimizzazione di funzioni quadratiche

6. Algoritmo di Newton

6.1. Definizione dell’algoritmo e principali proprietà 6.2. Confronto con il metodo del gradiente

(3)

6.3. Confronto con il metodo di Newton per la ricerca degli zeri di una funzione 6.4. Teorema di convergenza dell’algoritmo di Newton

6.5. Esempi di applicazione dell’algoritmo a funzioni di prova 6.6. Convergenza locale e globale dell’algoritmo

6.7. Varianti dell’algoritmo di Newton: metodi quasi-Newton e metodi per ridurre l’onere computazionale

7. Metodi delle direzioni coniugate

7.1. Introduzione ai metodi delle direzioni coniugate 7.2. Concetto di direzioni coniugate

7.3. Metodo del gradiente coniugato per la minimizzazione di funzioni quadratiche 7.4. Proprietà di convergenza finita dell’algoritmo

7.5. Metodo del gradiente coniugato per funzioni non quadratiche: metodi di Polak-Ribiere e Fletcher-Reeves

7.6. Esempi di applicazione dell’algoritmo a funzioni di prova

8. Metodi non derivativi

8.1. Approssimazione delle derivate con differenze finite negli algoritmi di discesa 8.2. Algoritmo delle discese coordinate

8.3. Algoritmo di Powell

8.4. Algoritmo delle tangenti parallele (Partan)

8.5. Algoritmi esplorativi basati su campionamenti dell’insieme ammissibile

9. Metodi di Line Search

9.1. Algoritmo di Fibonacci e della sezione aurea

9.2. Algoritmi basati su interpolazioni quadratiche e cubiche

10. Introduzione alla programmazione matematica non lineare vincolata

10.1. Caso particolare di problemi di ottimizzazione su insiemi convessi 10.2. Condizioni di ottimalità

10.3. Algoritmi delle direzioni ammissibili 10.4. Algoritmo del gradiente proiettato

11. Approccio Lagrangiano per problemi di programmazione matematica non lineare vincolata

(4)

11.2. Condizioni necessarie e condizioni sufficienti di ottimalità per problemi di programmazione non lineare vincolata con soli vincoli di uguaglianza

11.3. Condizioni necessarie e condizioni sufficienti di ottimalità per problemi di programmazione non lineare vincolata con soli vincoli di disuguaglianza: condizioni di Karush-Kuhn-Tucker (KKT)

11.4. Condizioni necessarie e condizioni sufficienti di ottimalità per problemi di programmazione non lineare vincolata con vincoli sia di uguaglianza sia di disuguaglianza

11.5. Utilizzo delle condizioni di ottimalità per la ricerca di soluzioni

11.6. Esempi di applicazione delle condizioni di ottimalità per la risoluzione di semplici problemi

12. Metodi delle funzioni di penalità e funzioni barriera

12.1. Definizione di metodo delle funzioni di penalità 12.2. Illustrazione del metodo e proprietà di convergenza 12.3. Definizione di metodo delle funzioni barriera 12.4. Illustrazione del metodo e proprietà di convergenza

12.5. Metodo del punto interno per la soluzione di problemi di programmazione lineare

13. Attività di laboratorio

13.1. Introduzione all’uso di Matlab. Presentazione dei principali comandi tramite esempi ed esercitazioni guidate al calcolatore.

13.2. Esercitazione: programmazione in Matlab dell’algoritmo del gradiente a passo costante per la risoluzione di semplici problemi di programmazione non lineare libera.

13.3. Esercitazione: utilizzo delle funzioni di libreria di Matlab per la risoluzione di problemi di programmazione non lineare libera.

13.4. Esercitazione: utilizzo delle funzioni di libreria di Matlab per la risoluzione di problemi di programmazione non lineare vincolata.

14. Approfondimenti e seminari

14.1. Esempi di problemi di interesse per un ingegnere gestionale formulabili come problemi di programmazione non lineare.

14.2. Esempio: allocazione ottima delle risorse di movimentazione all’interno di un terminale intermodale portuale.

14.3. Esempio: pianificazione ottima a livello strategico e tattico della movimentazione delle merci all’interno di catene di distribuzione.

(5)

Riferimenti bibliografici

[1] D. Bertsekas – Nonlinear Programming. Athena Scientific, 1999.

[2] D. Luenberger, Y. Ye – Linear and nonlinear programming. Springer, 2008. [3] Materiale fornito dal docente.

Riferimenti

Documenti correlati

• Trova il più grande fra il risultato del problema precedente e l’ultimo numero (n° dato). •

Per l hardness usiamo una riduzione polinomiale dal problema SUBSET- SUM, in modo tale che il problema SET- PARTITION ammette soluzione se e solo se SUBSET- SUM

Le seguenti operazioni tra due vettori dello stesso tipo (riga o colonna) e della stessa dimensione, producono (puntualmente) un vettore dello stesso tipo e dimensione.. abs

Ricorda che devi indicare in modo ordinato tutti i passaggi, svolgi le ultime quattro dietro o in un foglio protocollo.. Punteggio Punteggio Punteggio: mezzo punto per le prime

Ricorda che devi eseguire tutti i passaggi sul foglio protocollo e riportare sul foglio solo le soluzioni delle singole disequazioni, lo schema e le soluzioni del sistema.

Esercizio: creare la funzione areatriangolo(), che calcola l’area di un triangolo ricevendo come input base e altezza.. Creare una funzione che calcola il valore assoluto di un

Metodo esplicito e implicito lineare multistep PECE di Adams-Bashforth-Moulton Utilizza un singolo step per calcolare una soluzione di ordine da 1 a 13.. Usa una formula di ordine

Calcola le funzioni gonio- metriche seno, coseno e tangente degli angoli a adiacenti alla base... Considerato l’angolo in CW come variabile x, determina l’espressione di AB