�ݺ�ߣ

Stefano Costanzo
Università degli Studi di Trieste
ESTECO S.p.A.

In computer science, matematica e ricerca operativa
è la selezione del punto migliore (secondo un determinato criterio)
appartenente a un insieme di alternative possibili date.
Esempio:
Trovare il massimo o
il minimo di una funzione.
2

In computer science, matematica e ricerca operativa
è la selezione del punto migliore (secondo un determinato criterio)
appartenente a un insieme di alternative possibili date.
Esempio:
Trovare il massimo o
il minimo di una funzione.
3

4
 DEFINIZIONE
Branca della matematica applicata in cui problemi decisionali
complessi vengono analizzati e risolti mediante
modelli matematici e metodi quantitativi
(ottimizzazione, simulazione, ecc..)
 SCOPO
Fornire un supporto matematico alle attività decisionali in cui
occorre gestire e coordinare attività e risorse limitate al fine di
massimizzare/minimizzare una funzione obiettivo.

5
Esigenze militari (Seconda guerra mondiale)
Problema decisionale
organizzazione strategica della rete di prevenzione
bombardamenti tedeschi
Risorse limitate
radar anti-aerei
Obiettivo
massimizzare la probabilità di intercettazione

6
 Notevole miglioramento dell’efficacia radar
(intercettazione e allerta)
 Numerose altre applicazioni
(logistica, sommergibili, stoccaggio)
 Dopo guerra
Estensione della metodologia ad ambiti civili e alla ricerca

7
Metodo delle 5 fasi:
 Raccolta dati
 Identificazione del problema
 Formulazione del problema
 Soluzione del problema
 Validazione della soluzione

8
 Raccolta dati
In questa fase vengono raccolte
tutte le informazioni ritenute utili alla
migliore soluzione del problema

9
 Identificazione del problema
In questa fase viene descritto il
problema in linguaggio naturale,
identificando l’oggetto della decisione
e gli aspetti rilevanti da tenere in
considerazione.

10
 Formulazione del problema
Il problema viene descritto in termini
matematici costruendo un
modello di ottimizzazione individuando
tre elementi fondamentali:
1. Variabili
2. Vincoli
3. Funzione obiettivo

11
 Soluzione del problema
In questa fase viene determinata una
soluzione ottima del problema,
oppure, si stabilisce che il problema è
inammissibile o illimitato.

12
 Validazione
Un errore nella formulazione
potrebbe portare a una soluzione
ammissibile per il modello ma non
per il problema reale che si vuole
risolvere.

13
 È uno dei casi di studio tipici dell'informatica teorica e della teoria
della complessità.
 Data una rete di città, connesse tramite delle strade, trovare il
percorso di minore distanza che un commesso viaggiatore deve
seguire per visitare tutte le città una ed una sola volta.

16Distanza Totale (HDTPCGH) = 20 + 45 + 67 + 58 + 36 + 32 = 258

17
 Il numero di destinazioni è N = 6, quindi...

18
... il numero di circuiti ammissibili è
5! = 5 * 4 * 3 * 2 * 1 = 120
 È possibile enumerare tutti i possibili circuiti

19
... il numero di circuiti ammissibili è
5! = 5 * 4 * 3 * 2 * 1 = 120
 È possibile enumerare tutti i possibili circuiti...
... trovando così il circuito più corto
Distanza Totale (HPGCDTH) = 229

20
Tale approccio si chiama algoritmo Brute-Force:
 Elencare ogni possibile circuito ammissibile
 Calcolare per ognuno la distanza totale dello stesso
 Scegliere il circuito che presenta la minor distanza

21
Tale approccio si chiama algoritmo Brute-Force:
 Elencare ogni possibile circuito ammissibile
 Calcolare per ognuno la distanza totale dello stesso
 Scegliere il circuito che presenta la minor distanza
L’algoritmo Brute-Force è esaustivo, garantisce di trovare la
soluzione ottima, ma inefficiente.

22
Se il computer elaborasse un milione di circuiti al secondo:
 N = 6, 7, 8, 9: istantaneo
 N = 10: circa 1/3 secondo
 N = 11: circa 4 secondi
 N = 12: circa 40 secondi
 N = 13: circa 8 minuti
 N = 14: circa 2 ore
 N = 15: più di un giorno
 N = 20: decine di migliaia di anni

23
 Idea
ad ogni nuova tratta il commesso sceglierà la prossima
destinazione più vicina non ancora visitata
Comunemente chiamato Nearest-Neighbor Algorithm

24
 Soluzione trovata con il Nearest-Neighbor Algorithm :
H, T, C, P, G, D, H
Distanza Totale NN: 274
Distanza Totale ottima: 229
Distanza media di un circuito: 287,6

25
 L’approccio Brute-Force è ottimo ma inefficiente
 Garantisce di trovare la soluzione ottima, ma può richiedere un tempo
irragionevolmente lungo
 Il Nearest-Neighbor Algorithm è efficiente ma non-ottimale
 È rapido e semplice, ma non garantisce di trovare la soluzione ottima

26
 Risoluzione non basata sulla formulazione matematica del problema
 Tempo di calcolo di una singola assegnazione proibitiva
 Formulazione matematica non lineare
 Mancanza di competenze

27
 Quantitativo enorme di equazioni necessarie alla progettazione
 Calcolo necessario per confermare l’assegnazione
 Costruzione di un prototipo
 Test effettivo

28
 Quantitativo enorme di equazioni necessarie alla progettazione
 Calcolo necessario per confermare l’assegnazione
 Costruzione di un prototipo
 Test effettivo
Tempo Totale?

29
Variabili Decisionali
Black Box
Risposte del
sistema

 Modellizzazione
Dato il sistema si costruisce un modello astratto tramite software
appositi che riproducano le relazioni fra input e output del
sistema.
 Simulazione
Esecuzione che riproduce il comportamento del sistema
impiegando il modello astratto e fornendo gli output.
 Ottimizzazione
Procedura iterativa guidata da un algoritmo che mira a trovare i
minimi/massimi delle risposte del modello indicate come obiettivi.
30

39
È una competizione di progettazione automobilistica
studentesca organizzata ogni anno dalla SAE International

IL MONDO DELL’OTTIMIZZAZIONE
Stefano Costanzo
Università degli Studi di Trieste
ESTECO S.p.A.

�ݺ�ߣ

Il Mondo dell'Ottimizzazione

More Related Content

Il Mondo dell'Ottimizzazione