Cum enim mundi universi fabrica sit perfectissima atque a Creatore
sapientissimo absoluta, nihil omnino in mundo contingit,
in quo non maximi minimive ratio quaepiam eluceat; quamobrem dubium
prorsus est nullum, quin omnes mundi effectus ex causis finalibus
ope methodi maximorum et minimorum aeque feliciter determinari
queant atque ex ipsis causis efficientibus
Eulero, 1744
Dato che la costruzione dell’universo è perfettissima e interamente compiuta
da un sapientissimo Creatore, nulla accade nel mondo in cui non risplenda
un qualche criterio di massimo o minimo; per questo motivo non c’è alcun dubbio
che tutti gli effetti del mondo possano essere determinati con successo
grazie a metodi di massimo o di minimo
tanto dalle cause finali quanto dalle stesse cause efficienti
rifrazione -> percorso più breve della luce
catenaria -> posizione della corda che minimizza
l’altezza del baricentro
ottimizzare
concetto ampiamente usato in Fisica
- vincoli d’uguaglianza: trattati da Lagrange
- vincoli di diseguaglianza: nuovo problema
modelli matematici:
descrivere
prevedere
controllare (far sì che il fenomeno abbia l’andamento voluto)
prendere una decisione
Operations Research:
The Science of Better
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
Conventional computing is not enough
Cannot enumerate alternatives -> Combinatorial explosion of viable options
m
(
)
m+n
n
paths (without repetitions)
n
•
•
(
Problem: Find shortest path m=8, n=5
– Assume a super-powered computer analyzes, quantifies, and compares a million
alternatives every second
– Answer is found immediately
Now find the shortest path m=80, n=50.
80+50
50
)=
2970917289408636901764901833770052360
9.4 10 22 years !
Conventional computing is not enough
Cannot enumerate alternatives -> Combinatorial explosion of viable options
Construct a 5 stock portfolio out of 100 possible stocks
– Evaluate for risk and return using same computer
– Answer found in 1.25 minutes
Now diversify to 9 stocks
– Answer found in 220 days
Now diversify to 10 stocks
– Answer found in 5.5 years
Conventional computing is not enough
macchine
lavori
macchine
lavori
5
8
1
7
5
2
4
9
2
8
3
6
2
1
3
9
1
4
6
2
5
4
3
8
8
1
9
7
5
1
3
7
5
2
9
6
macchine
lavori
5
8
1
7
5
2
4
9
2
8
3
6
2
1
3
9
1
4
6
2
5
4
3
8
8
1
9
7
5
1
3
7
5
2
9
6
5+9+3+4+5+6=
32
macchine
lavori
5
8
1
7
5
2
4
9
2
8
3
6
2
1
3
9
1
4
6
2
5
4
3
8
8
1
9
7
5
1
3
7
5
2
9
6
1+6+1+4+1+3=
16
macchine
lavori
5
8
1
7
5
2
4
9
2
8
3
6
2
1
3
9
1
4
6
2
5
4
3
8
8
1
9
7
5
1
3
7
5
2
9
6
1+4+1+2+1+2=
11
macchine
lavori
5
8
1
7
5
2
4
9
2
8
3
6
2
1
3
9
1
4
6
2
5
4
3
8
8
1
9
7
5
1
3
7
5
2
9
6
6!=720
soluzioni diverse
si potrebbero esaminare
una ad una
ma se n=50
50!=
30414093201713378043612608166064768844377641568960512000000000000=
65 cifre
non basta l’età dell’universo per esaminare tutte le soluzioni !!
Per alcuni problemi si trova la risposta velocemente
Per altri (la maggior parte) non si riesce a trovare la risposta velocemente
Bisogna accontentarsi di una soluzione ragionevolmente buona
PROGRAMMAZIONE LINEARE (1947)
QuickTime™ and a
decompressor
are needed to see this picture.
George Dantzig (1914-2005)
PROGRAMMAZIONE LINEARE (1947)
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
George Dantzig (1914-2005)
John Von Neumann (1903-1957)
PROGRAMMAZIONE LINEARE (1947)
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
Leonid V. Kantorovich (1912-1986)
QuickTime™ and a
decompressor
are needed to see this picture.
George Dantzig (1914-2005)
John Von Neumann (1903-1957)
PROGRAMMAZIONE LINEARE (1947)
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
Leonid V. Kantorovich (1912-1986)
QuickTime™ and a
decompressor
are needed to see this picture.
George Dantzig (1914-2005)
John Von Neumann (1903-1957)
QuickTime™ and a
decompressor
are needed to see this picture.
Tjalling Koopmans(1910-1985)
PROGRAMMAZIONE LINEARE (1947)
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
Leonid V. Kantorovich (1912-1986)
QuickTime™ and a
decompressor
are needed to see this picture.
George Dantzig (1914-2005)
John Von Neumann (1903-1957)
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
Paul Samuelson (1915- 2009 )
Tjalling Koopmans(1910-1985)
Da allora ad oggi sono stati fatti enormi progressi
- hardware
- software
Le intuizioni degli anni `50 sono diventate realtà negli anni `90
CREW SCHEDULING
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
800 voli al giorno per 30 giorni = 24000 voli
in quanti modi si possono combinare?
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
TURNAZIONI AUTISTI DI AUTOBUS
TURNAZIONI
- personale paramedico negli ospedali
- call center
COMMESSI VIAGGIATORI
Eulero: Solution d'une question curieuse qui ne paraît soumise à aucune
analyse, Mémoire de l'Académie des Sciences de Berlin, 15, 310-337,1759
QuickTime™ and a
decompressor
are needed to see this picture.
ROTTE DI VEICOLI
1
Truck data
volume
(m3)
8
10
11
16
19
24
cost/day
(euro)
170
170
185
185
210
210
available
vehicles
3
1
1
1
1
1
SISTEMI
ELETTORALI
Elezioni politiche 2008
43
10
40
29 20
13
15
24
43
22
16
17
38
14
3
9
44
40
15
33
18
29
26
Elezioni politiche 2008
6
22
28
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
QuickTime™ and a
decompressor
are needed to see this picture.
Elezioni politiche 2008
QuickTime™ and a
decompressor
are needed to see this picture.
272
60
8
211
28
36
2
10 2920
43
40
13
15
24
43
22
16
17
38
14
3
9
44
40
15
33
18
29
26
Elezioni politiche 2008
6
22
28
9 3020
43
40
13
15
24
43
23
16
17
38
14
3
9
44
40
15
33
18
29
25
Elezioni politiche 2008
6
22
28
10 29 20
43
40
13
15
24
43
22
16
17
38
14
3
9
44
40
15
33
18
29
26
Elezioni politiche 2006
6
22
28
11
43
40
29 20
13
ONE MAN-HALF VOTE !
15
Bruno Simeone
24
43
22
16
17
38
14
2
9
44
40
15
33
18
29
26
Elezioni politiche 2006
6
22
28
Trentino-Alto Adige: 85.456 voti per seggio
Molise:
160.300 voti per seggio
TORNEI SPORTIVI
Costruzione del calendario del campionato di calcio
Determinazione delle partite in casa e fuori.
Costruzione del calendario con distanza minima
CALENDARIO GIÀ CALCOLATO - BISOGNA STABILIRE CHI GIOCA IN CASA
AHAHAHAHAHA
AHAHAHAHAHA
incontro
???
devono essere uno in casa e l’altro fuori
CALENDARIO GIÀ CALCOLATO - BISOGNA STABILIRE CHI GIOCA IN CASA
AHAHAHAHAHA
HAHAHAHAHAH
???
avere al massimo due turni consecutivi in casa e fuori casa
in ogni girone avere il numero di partite in casa differire di uno dalle
partite fuori casa
QuickTime™ and a
decompressor
are needed to see this picture.
Distance: 23916 (Easton May 7, 1999)
Slot
ATL
NYM
PHI
MON
0
1
2
3
4
5
6
7
8
9
FLA
NYM
PIT
@PHI
@MON
@PIT
PHI
MON
@NYM
@FLA
@PIT
@ATL
@FLA
MON
FLA
@PHI
@MON
PIT
ATL
PHI
@MON
FLA
MON
ATL
@PIT
NYM
@ATL
@FLA
PIT
@NYM
PHI
@PIT
@PHI
@NYM
ATL
FLA
NYM
@ATL
@FLA
PIT
FLA
@ATL
@PHI
NYM
PIT
@NYM
@MON
@PIT
PHI
MON
ATL
PIT
NYM
MON
@ATL
@FLA
PHI
ATL
FLA
@NYM
@PHI
@MON
BIOLOGIA MOLECOLARE
“Leggere” il DNA
ACGTTACG
TTACGGAT
CGGATTCA
CGGCGATT
AACAAGCTT
CGGAATCG
TTACCGGAT
CGGTTAGG
CGAATTAG
TGGCGAA
GGCCTTAA
ACGACGAT
GCATTCGA
ATATCGAT
CGCGCGAA
TGTGCATA
ACCGGAC
TGTCGCGA
CGCGCGAT
GTGTAGAG
CTTGATCT
CGGATATA
CGCGATAT
TGTGAATA
ACGTTACG
TTACGAAT
CGGATTCA
CGGCGATT
AACCAGCTT
CGGAATCG
TTACCGGAT
CGGTTAGG
CGAATTAG
TGGCGAA
AGCCTTAA
ACGACGAT
GCATTCGA
ATATCGAT
CGCGCGAA
TGTGCATA
ACCGGAC
TGTCGCGA
CGCGCGAT
GTGCAGAG
CTTGATCT
CGGATATA
CGCGATAT
TGTGAATA
ACGTTACG
TTACGGAT
CGGATTTA
CGGCGATT
AACAAGCTT
CGGAATCG
TTACCGGAT
CGGTTAGG
AGAATTAG
TGGCGAA
GGCCTTAA
ACGACGAT
GCATTCGA
ATATCGAT
CGCGCGAA
TGTGCATA
ACCGGAC
TCTCGCGA
CGCGCGAT
GTGTAGAG
CTTGATCT
CGGATATA
CGCGCTAT
TGTGAATA
ACATTACG
TTACGGAT
CGGATTCA
CGGCGACT
AACAAGCTT
CGGAATCG
TTACCGGAT
CGGTTAAG
CGAATTAG
TGGCGAA
GGCCTTAA
ACGACGTT
GCATTCGA
ATATCGAT
CGCGCGAA
TGTGCATA
ACCGGAC
TGTCGCGA
CGCGCGAT
TTGTAGAG
CTTGATCT
CGGATATA
CGCAATAT
TGTGAATA
ACGTTACG
TTACTGAT
CGGATTCA
CGGCGATT
AACAAGCGT
CGGAATCG
TTACCGGAT
CGGTTAGG
AGAATTAG
TGGCGAA
GGCCTTAA
ACGACGAT
GCATTGGA
ATATCGAT
CGCGCGAA
TGTGCATA
AACGGAC
TGTCGCGA
CGCGCGAT
GTGTAGAG
CTTGTTCT
CGGATATA
CGCGATAT
TGTGAATA
ACGTTACG
TTACGGAT
CGGATTCA
CGGCAATT
AACAAGCTT
CGGAATAG
TTACCGGAT
CGGTTAGG
CGAATTAG
TGGCGAA
GGCCTTAA
ACGACGAT
GTATTCGA
ATATCGAT
CGCGCGAA
TGTGCATA
ACCGGAC
TGTCGCGA
CGCTCGAT
GTGTAGAG
CTTGATCT
AGGATATA
CGCGATAT
TGTGAATA
ACGTTACG
TTACGGAT
CGGATTCA
CGGCGATT
AACAAGCTT
CGGAATCG
TTACCGGAT
CGGTTAGG
CGAATTAG
TGGCGAA
GGCCTTAA
ACGACGAT
GCATTCGA
ATATCGAT
CGCGCGAA
TGTGCATA
ACCGGAC
TGTCGCGA
CGCGCGAT
GTGTAGAG
CTTGATCT
CGGATATA
CGCGATAT
TGTGAATA
ACGTTACG
TTACGAAT
CGGATTCA
CGGCGATT
AACCAGCTT
CGGAATCG
TTACCGGAT
CGGTTAGG
CGAATTAG
TGGCGAA
AGCCTTAA
ACGACGAT
GCATTCGA
ATATCGAT
CGCGCGAA
TGTGCATA
ACCGGAC
TGTCGCGA
CGCGCGAT
GTGCAGAG
CTTGATCT
CGGATATA
CGCGATAT
TGTGAATA
ACGTTACG
TTACGGAT
CGGATTTA
CGGCGATT
AACAAGCTT
CGGAATCG
TTACCGGAT
CGGTTAGG
AGAATTAG
TGGCGAA
GGCCTTAA
ACGACGAT
GCATTCGA
ATATCGAT
CGCGCGAA
TGTGCATA
ACCGGAC
TCTCGCGA
CGCGCGAT
GTGTAGAG
CTTGATCT
CGGATATA
CGCGCTAT
TGTGAATA
ACATTACG
TTACGGAT
CGGATTCA
CGGCGACT
AACAAGCTT
CGGAATCG
TTACCGGAT
CGGTTAAG
CGAATTAG
TGGCGAA
GGCCTTAA
ACGACGTT
GCATTCGA
ATATCGAT
CGCGCGAA
TGTGCATA
ACCGGAC
TGTCGCGA
CGCGCGAT
TTGTAGAG
CTTGATCT
CGGATATA
CGCAATAT
TGTGAATA
ACGTTACG
TTACTGAT
CGGATTCA
CGGCGATT
AACAAGCGT
CGGAATCG
TTACCGGAT
CGGTTAGG
AGAATTAG
TGGCGAA
GGCCTTAA
ACGACGAT
GCATTGGA
ATATCGAT
CGCGCGAA
TGTGCATA
AACGGAC
TGTCGCGA
CGCGCGAT
GTGTAGAG
CTTGTTCT
CGGATATA
CGCGATAT
TGTGAATA
ACGTTACG
TTACGGAT
CGGATTCA
CGGCAATT
AACAAGCTT
CGGAATAG
TTACCGGAT
CGGTTAGG
CGAATTAG
TGGCGAA
GGCCTTAA
ACGACGAT
GTATTCGA
ATATCGAT
CGCGCGAA
TGTGCATA
ACCGGAC
TGTCGCGA
CGCTCGAT
GTGTAGAG
CTTGATCT
AGGATATA
CGCGATAT
TGTGAATA
stessa proteina, specie diverse
a:humanafrican cox1
b:humprobeuro cox1
c:gorilla cox1
d:gibbon cox1
e:chimpanzee cox1
f:pigmychimp cox1
g:baboon cox1
h:orangutan cox1
i:sumorang cox1
;----accatccatcaatctgcgatccccctccaataccaaccataccactcctggccttccagtt
;gtacaccatccatcaa--tgcgatccccctccaataccaaccataccactcctggccttccagtt
;acatattacccatcaacttataatctctttccagcatcagtcatgctattcccgaccccttagtt
;gcgtattactcgctggcccatacctcttcctagaccccaactgtgtcgcctctgattccctagtt
;acacactacctatcgacttacaattccctcccaacaccagtcatgctgttcccgacccctcaact
;---cactacccattgacttacaatcccttctcagcactaatcacgctgttcccgatccctcaact
;atgcaccgtttactagctcataccttccccta--ccctgatcgcatcatctttaatcccctaacc
;gcgcgctgtccatcatcccacacttctctcccaacattggctataccgtccttgactccctcatc
;gcgcgccgtccgtcatcccacacctctctcccaacatcaactataccacccctaactccctcgtc
agccccccccctagctgcctcatctccacccgcaccctcttctcccccccccaaacctcctctttac--agccccccccctagctgcctcatctccacccgcaccctcttctcccccccccaaacctcctctttacttt
aatcctccttccaatcgccctacctccacccgcactttctttctctccccccaaattcctttctcacctt
gaccctcctttcggccgttctcccccctctcgcatcccaccttcccccttttaaactctccccttactcc
aacgtcccccctgaccactccattttcacccgcactcccttcctttcctcccgaacttttttcttatctt
aatgtcccccctggccactccactttcacccgcattcccttcctttcctcctgaacttttttctcatctt
ggtccccccctcaaccaccctcccccatttaatatctcaccctctcctttccaagcttccccctcatccc
aactcttacctcaatcgtcttatttcattcaacgcccccctcccccattattatgttccttctccccccc
aactcttaccttaaccatctcatttcatccagtgcccccctccctcaccatcatatcctctttccccccc
ALLINEARE LE SEQUENZE
- at - t - c g a
- at g t - c - a
c - t - t a c g -
SCHEDULAZIONE
in generale i problemi di schedulazione sono difficili,
molto difficili
SCHEDULAZIONE PERIODICA
QuickTime™ and a
decompressor
are needed to see this picture.