Corso di Laurea in Informatica Analisi Numerica (1° mod., 6...
Transcript of Corso di Laurea in Informatica Analisi Numerica (1° mod., 6...
1
Corso di Laurea in Infomatica
Corso di Laurea in Matematica Matematica Computazionale(6cfu)
Ottimizzazione(8cfu)
(a.a. 2013-14, lez.1)
Docente: Marco Gaviano
(e-mail:[email protected])
2
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.1
Gli argomenti del corso rientrano nell’ambito
più generale della Ricerca Operativa.
Questa ha lo scopo di fornire strumenti
matematici di supporto alle attività decisionali
in cui occorre gestire e coordinare attività e
risorse al fine di effettuare le scelte migliori
per raggiungere un determinato obiettivo.
3
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.1
Storia
La nascita della Ricerca Operativa è dovuta
ad esigenze di tipo militare, durante la
seconda guerra mondiale.
Immediatamente prima e durante la seconda
guerra furono creati alcuni gruppi di ricerca
orientati alla soluzione di importanti
problemi di ordine strategico e tattico
collegati alla difesa nazionale.
4
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.1
Tra questi importante fu il problema (tra il 1935
e il 1937 nel Regno Unito) di ottimizzare la
distribuzione delle apparecchiature radar sul
territorio e di inviare via radio la segnalazione
ad opportune località .
A.P. Rowe, sovrintendente della "Bawdsey
Research Station", nel 1938, utilizzò per la prima
volta l'espressione "Operational Research".
5
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.1
Fasi per la risoluzione di un problema
•esame della situazione reale e raccolta delle informazioni;
•formulazione del problema (individuazione delle variabili
e scelta della funzione obbiettivo da massimizzare o
minimizzare);
•costruzione del modello matematico che rispecchi il più
possibile il problema reale;
•soluzione e verifica del modello matematico;
•verifica delle soluzioni ottenute in rapporto al problema
reale (si verifica se la funzione obbiettivo offre vantaggi e
si verifica la rappresentatività del modello).
6
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.1
definizione
del
problema reale
costruzione
del
modello
verifica che la
soluzione trovata
risolve il problema reale
analisi
della
soluzione trovata
formulazione
del
problema matematico
risoluzione
del
problema matematico
Fasi della Ricerca Operativa
7
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.1
Obiettivo del corso
Dati un problema reale lo studente dovrà
•Individuare una possibile modellizzazione matematica
•conoscere i metodi per la soluzione del modello.
•scrivere ed implementare gli algoritmi conseguenti
• trovare le soluzioni numeriche
•valutare l’affidabilità delle soluzioni
8
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.1
Il modo di operare
• Descrizione di problemi reali
• Presentazione del modello matematico
• Presentazione di risultati teorici relativi al
modello
• Studio di metodi numerici che possono risolvere il
modello e loro implementazione.
• Scrittura degli algoritmi in un linguaggio di
programmazione
• Presentazione del software commerciale
9
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.1
Il corso consiste in
lezioni teoriche integrate da attività di
laboratorio in cui agli studenti sono assegnati
dei problemi da risolvere o con programmi già
disponibili o con codici da mettere a punto.
Ad ogni studente è assegnato un progetto da
valutare nella prova orale
10
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.1
Programma del corso
Programmazione Lineare
•Risultati teorici fondamentali.
•Il metodo del Simplesso .
•Dualità e sensibilità.
•Interpretazione economica della dualità.
•Complessità computazionale.
•Altri algoritmi di risoluzione.
11
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.1
Programmazione NonLineare
•Risultati teorici fondamentali.
•Minimizzazione non vincolata .
12
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.1
Testi di riferimento
Hillier F.S., Lieberman G.J.:Introduction to
Operations Research, McGraw Hill 2005
Ravindran A.,Phillips D.T.Solberg J.: Operations
Research,John Wiley, 1987
13
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.1
Testi di riferimento per il laboratorio
W.J Palm III, Matlab 6, Mc Graw-Hill.
W.H. Press et alii., Numerical Recipes, The art of
Scientific Computing, Cambridge Press.
14
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.1
Modalità dell’esame
prove scritte
1 prova finale
prova orale
1 prova finale per la verifica della conoscenza
della parte teorica, dell’attività di laboratorio
e della valutazione del progetto assegnato.
15
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.1
Informazioni utili
Gli schemi delle lezioni e i problemi assegnati
nel laboratorio saranno disponibili all’indirizzo
informatica.unica.it
16
Corso di Laurea in Infomatica
Corso di Laurea in Matematica
Matematica Computazionale(6cfu)
Ottimizzazione(8cfu)
(a.a. 2013-14, lez.2)
Docente: Marco Gaviano
(e-mail:[email protected])
17
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Esempi di problemi risolvibili mediante l’ottimizzazione
Scelta di una strategia di produzione
Un’azienda deve decidere la strategia per la produzione di un
certo prodotto: si utilizzano operai e materiali vari.
La quantità di materiale disponibile giornalmente è: 200 Kg.
Ugualmente c’è un vincolo per le ore di lavoro disponibili:
150 ore.
Si possono utilizzare 3 linee di produzione ciascuna con
caratteristiche diverse:
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
18
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
linea produzione A B C
n.ore lavoro per unità prodotta 7 3 6
quantità materiale per unità prodotta 4 4 5
profitto 4 2 3
19
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Problema
Si vogliono determinare le quantità prodotte dalle
linea di produzione A, B e C in modo da ottenere il
massimo profitto
Il problema può tradursi in linguaggio matematico nel
modo seguente
20
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
)negativitànon(vincoli0x,0x,0x
e)disponibil materiale(vincolo2005x4x4x
i)disponibilore(vincolo1506x3x7x
condizionilesotto
3x2x4x)x,x,z(xreMassimizza
CBA
CBA
CBA
CBACBA
21
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Gestione di un bacino idroelettrico
Si abbia un bacino d'acqua che rifornisce n centrali
idroelettriche Ei i=1,…,n secondo il seguente schema
c1 c2 … cn
E1 E2 … En
Bacino d’acqua
22
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
• Ogni condotta ha una portata massima ci per ora.
• La quantità di energia prodotta deve essere in un'ora
maggiore o uguale a Pk , k=1,..,24.
• In una giornata può essere consumata al più una
quantità d'acqua Q.
Le centrali devono produrre energia elettrica con
la condizione che vengano rispettati i seguenti
vincoli.
23
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Problema
Si vogliono determinare le portate orarie xi,k di ciascuna
condotta in modo da soddisfare i vincoli.
(si sa che ad un portata xi,k corrisponde una potenza a·xi,k ).
Il problema può tradursi in linguaggio matematico nel
modo seguente
24
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Modellizzazione matematica
k)oranell'erogata(potenzaPax
prelevata)acquad'(quantitàQx
portata)sulla(vincolicx
condizionilesotto
xz(x)eMinimizzar
k
i
ki,
ki,
ki,
iki,
ki,
ki,
25
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Scelta di una Campagna Pubblicitaria
Una azienda di pubblicità deve pianificare una campagna
di spot pubblicitari in televisione, alla radio e sui giornali.
L’azienda ha fissato una spesa totale non superiore a
800.000 Eu. Inoltre richiede che
a) Almeno 2 milioni siano i potenziali utenti donne.
b) La spesa per la televisione non superi 500.000Eu.
c) Almeno 3 spot siano in televisione la mattina.
d) Almeno 2 spot siano in televisione la sera.
e) Il numero di spot su radio e giornali siano tra 5 e 10.
26
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Televisione
mattino
Televisione
sera
Radio Giornali
Costo per una unità
pubblicitaria
40.000 75.000 30.000 15.000
No.potenz. utenti
per una unità pubbl.
400.000 900.000 500.000 200.000
No.potenz. donne
per una unità pubbl.
300.000 400.000 200.000 100.000
Si dispone della seguente tabella
27
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Problema
Si vogliono determinare le unità pubblicitarie per
ciascun media in modo da raggiungere il numero
massimo di potenziali utenti
Il problema può tradursi in linguaggio matematico nel
modo seguente
28
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Modellizzazione matematica
Si denotino con x1, x2, x3 e x4 le unità pubblicitarie da
calcolare per i vari media. Il numero di potenziali utenti
è espresso dalla funzione obbiettivo
Ciascun vincolo può tradursi in una disequazione.
Il problema può descriversi come
4321 200x500x900x400xz(x)
29
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
,10x5,x,10x5,x,2x,3x
telev.)costo(vincolo50075x40x
donne)utenti(vincolo20010x20x40x30x
totale)costo(vincolo80015x30x75x40x
condizionilesotto
200x500x900x400xz(x)eMinimizzar
443321
21
4321
4321
4321
30
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Miscellazione ottimale
Una compagnia petrolifera produce due tipi di benzina
normale e verde che vende alla sua catena di distribuzione
per 12 e 14 euro al barile. Le due benzine provengono da
petrolio nazionale ed importato. Esse devono soddisfare i
requisiti della seguente tabella
Pressione
massima
vapore
numero
minimo
ottani
domanda
massima
barile/sett
consegne
minime
barile/sett
Normale 23 88 100.000 50.000
Verde 23 93 20.000 5.000
31
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
pressione
vapore
numero
ottani
scorte
barili
costo
euro/barile
nazionale 25 87 40.000 8
importato 15 98 60.000 15
Le caratteristiche delle scorte sono
32
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Problema
Quali quantità dei due petroli (nazionale ed importato)
devono essere miscelati nelle due benzine per ottenere il
massimo profitto settimanale?
Il problema può tradursi in linguaggio matematico nel
modo seguente
33
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Modellizzazione matematica
Si pone
x1 barili di petrolio nazionale miscelato nella benzina normale
x2 barili di petrolio estero miscelato nella benzina normale
x3 barili di petrolio nazionale miscelato nella benzina verde
x4 barili di petrolio estero miscelato nella benzina verde
x1+x2 è la quantità di benzina normale prodotta. Essa dà il
ricavo 12(x1+x2 ). La quantità di benzina verde venduta dà il
ricavo 14(x3+x4 ).
34
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Si impiegherà la quantità x1+x3 di petrolio nazionale al costo
di 8(x1+x3 ) e x2+x4 di petrolio importato al costo 15(x2+x4 ).
Dunque si deve massimizzare (funzione obbiettivo)
z = 12(x1+x2 )+14(x2+x4)-8(x1+x3 )-15(x2+x4 )
= 4x1-3x2+6x3-x4
35
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Si devono ora soddisfare i vincoli. Per la domanda si ha
x1+x2 100.000 (massima domanda di benzina normale)
x3+x4 20.000 (massima domanda di benzina verde)
x1+x2 50.000 (fabbisogno minimo di benzina normale)
x3+x4 5.000 (fabbisogno minimo di benzina verde).
Per la disponibilità si ha
x1+x 3 40.000 (nazionale)
x2+x4 60.000 (estero).
36
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
I componenti di una miscela contribuiscono a determinare
il numero complessivo di ottani a seconda della propria
percentuale di peso; lo stesso vale nel caso della pressione
del vapore. Pertanto il numero di ottani della benzina
normale è
ed il requisito richiesto che questo tipo di benzina abbia
almeno 88 ottani è espresso da
x1-10x2 0;
21
2
21
1 9887xx
x
xx
x
37
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Analogamente si ottiene
6x3-5x4< 0 (vincolo relativo agli ottani della verde)
2x1-8x2< 0 (vincolo relativo alla pressione del vapore nella normale)
2x3-8x4< 0 (vincolo relativo alla pressione del vapore nella verde)
Considerando i vincoli di non negatività si ottiene il
problema finale
38
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
estero scorte60.000xx
nazionale scorte40.000xx
verdedomanda massima20.000xx
normale domanda massima100.000xx
condizionilesotto
x-6x3x-4x x)z(reMassimizza
42
31
43
21
4321
39
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
0,,,
verderichiesta5000xx
normale richiesta50.000xx
verdevapore08x2x
normale vapore08x2x
verdeottani05x6x
normale ottani010xx
4321
43
21
43
21
43
21
xxxx
40
Matematica Computazionale, Ottimizzazione, a.a. 2013-14, Lezione, n.2
Criteri di Modellizzazione
• Raccogliere il maggior numero di elementi che
descrivono la situazione reale.
• Costruire un modello il più vicino possibile alla
realtà.
• Condurre rigorosamente la fase di costruzione del
modello.
• Non costruire un modello sofisticato quando uno
semplice è sufficiente.
• Non dimenticare che un modello è un’astrazione
della realtà.