144
MODELLI DECISIONALI
FORMULAZIONE GENERALE DEL PROBLEMA DECISIONALE (OTTIMIZZAZIONE)
z vettore di n elementi (variabili di decisione) o funzione
J(z) obiettivo (vettoriale) da ottimizzare (max o min)
Z insieme delle soluzioni ammissibili (che soddisfano i vincoli)
CLASSIFICAZIONE DEI MODELLI DECISIONALI
a1) sistema all’equilibrio equazioni algebriche programmazione matematica
)())(),(()1(
)(),(
xgytutxftx
xgyuxfx
u=u= cost.
all’eq. x = (u) e quindi y = g(x)=(u) l’uscita all’equilibrio è solo funzione dell’ingresso
a1.1) obiettivo e vincoli lineari programmazione lineare (PL)
a1.2) obiettivo e/o vincoli non lineare programmazione non lineare
a2) sistema in evoluzione equazioni algebriche o
differenziali controllo ottimo (regolazione)
min J(z) z
z Z
145
b) variabili intere (al limite, binarie) programmazione a numeri interi (PNI)
c) l’obiettivo è un vettore di funzioni ottimizzazione a molti obiettivi
d) obiettivo dipendente anche da variabili esterne ottimizzazione in ambiente incerto
d1) sono possibili esperimenti sull’ambiente teoria delle decisioni
e) esiste più di un decisore ottimizzazione a molti decisori (teoria dei giochi)
f) soluzione non univocamente legata ai coefficienti
del modello ottimizzazione stocastica g) variabili di decisione intere + soluzioni
ammissibili finite ottimizzazione combinatoria
h) obiettivo separabile (somma di componenti) programmazione dinamica
i) non ci sono vincoli (Z illimitato) ottimizzazione non vincolata.
Non conosciamo un algoritmo che risolva il problema generale in tutti i casi, quindi ogni struttura ha uno o più metodi specifici (cercano di ridurre la complessità = numero di operazioni).
146
PROGRAMMAZIONE MATEMATICA
z vettore delle variabili di decisione (z1,z2,…,zn) J(z) obiettivo da ottimizzare (es. min) g(z) = 0 vincoli di uguaglianza (equazioni)
h(z) 0 vincoli di disuguaglianza (disequazioni). In
generale, zi0, i =1,2,…,n
z°, J°=J(z°) soluzione ottima
J(z)
Z
Z
In generale gli algoritmi sono evolutivi e trovano un minimo locale. Quindi è importante da dove si parte o
che esista un solo minimo in Z.
N.B. J(z)/ z = 0 non è applicabile perché la funzione non è nota analiticamente.
minimo di
frontiera
minimo
locale
minimo assoluto
147
PROBLEMI DI PIANIFICAZIONE
Pianificare ≡ prendere decisione riguardante il funzionamento di un
dato sistema per un periodo di tempo molto lungo (al
limite infinito).
Scopo dell’atto pianificatorio: migliorare una certa realtà.
Pianificatore ≡ Decisore è spesso un “gruppo” o un ente; più
raramente una persona o gruppo di
“responsabili”.
Progetto ≡ pianificazione limitata a problemi
esclusivamente tecnici
Pianificare ≈ progettare tenendo conto degli aspetti
economici, sociali, ambientali, …
Pianificazione razionale: cercare la soluzione più conveniente
tra tutte quelle ammissibili modelli
di ottimizzazione
148
Esempio
Costruzione di un serbatoio artificiale per potenziare l’agricoltura in
una regione.
Domande:
Una diga sola o più dighe?
Dove costruirla?
Quanto grande?
A chi darla in gestione?
Come reperire gli stanziamenti?
Come ridistribuire gli utili?
….
Come si vede da questo esempio, in un unico problema pianificatorio
sono coinvolte tematiche fisiche, economiche, sociali, … : il problema
è cioè “complesso”
Problema di pianificazione ≡ Problema complesso
La complessità non è solo concettuale, ma spesso anche
computazionale (grande numero di variabili ed equazioni da
risolvere).
149
Le variabili di decisione
Le decisioni da prendere sono spesso rappresentate da variabili
continue
Altezza della diga
Superficie da coltivare
Quantità di materiale da produrre
Quantità di inquinante da trattare
Altezza della ciminiera
Capitale da investire
…
In questi casi si ha un’infinità di soluzioni possibili, tra cui va scelta
con un opportuno criterio quella “ottima”
In altri casi le variabili di decisione sono discrete
Fare o non fare un canale tra Milano e il Po
Fare o non fare un’autostrada che collega due punti
Depurare, diluire o scaricare in mare
Scegliere tra n tipi di impianto
In questi casi il numero di soluzioni possibili tra cui si deve scegliere
la migliore è comunque finito.
150
I vincoli
Nel risolvere un problema di pianificazione si deve spesso tener
conto di vincoli di natura fisica, tecnologica, economica, normativa,…
Tali vincoli sono di solito esprimibili con relazioni di uguaglianza o
disuguaglianza tra variabili significative che descrivono il problema.
Vincoli di tipo fisico i volumi d’acqua da trasferire da un
bacino A a un bacino B non devono
superare la capacità della rete idrica
che collega i due bacini.
Vincoli di tipo economico il costo dell’autostrada non deve
superare lo stanziamento dei LLPP.
Vincoli di tipo normativo gli impianti di depurazione devono
essere progettati in modo tale che sia
soddisfatta la normativa vigente sugli
scarichi
151
Gli obiettivi
Spesso esiste un ben preciso obiettivo da minimizzare o
massimizzare:
Minimizzazione del costo
scarto
ingombro
rischio
inquinamento
…..
Massimizzazione del ricavo
guadagno (beneficio)
rendimento
affidabilità
qualità
…..
Altre volte però gli obiettivi sono molti e tra loro “conflittuali”
Min ( (costo impianti di trattamento) , (grado di inquinamento
delle acque) )
Min ( (rischio) , (costo strutture) )
Max ( (utile compagnia aerea) , (affidabilità dei voli) )
Max ( (sviluppo industriale) , (conservazione paesaggio) )
Min (piene su lago regolato) + Max (beneficio utenti a valle)
Min (tempo di trasporto) + Max (affidabilità del trasporto)
152
Aspetto modellistica del problema
Vincoli e obiettivi si possono spesso esprimere analiticamente, una
volta che siano state individuate tutte le variabili z1, z2, …, zn
significative. Il risultato è quasi immancabilmente un problema di
programmazione matematica.
max ( ) z
J z z Z
Ad esempio, a questo problema si perviene quando si vuol
determinare l’equilibrio più “produttivo” di un sistema dinamico
( , )x f x u . Infatti in questo caso si ha:
0 ( , ) equilibrio
( )
u f x u
z x Z y x
y x u U y Y
Insieme delle soluzioni ammissibili
(individuate da tutti i vincoli)
max [J(u,y)]
153
Esempio (massimo prodotto sostenibile)
x = biomassa delle trote in una vasca di allevamento
x = tasso di crescita “totale”
( )x f x u dove f(x) tasso di crescita “naturale”
u tasso di rimozione [kg/giorno]
Equilibrio: f(x)=u (si estraggono ogni giorno un numero di kg di
pesce pari all’aumento della biomassa)
Max [u] massima quantità prodotta (plausibilmente max
guadagno)
max
max ( ) (max. non vincolata)( )
u
x
obiettivo uf x
vincolo u f x
Estensione
T
( ) x = vettore n-dim. (n specie)
b = (0 0 .... 1) (si rimuove solo l'ultima specie)
max u all'equilibrio
x f x bu
MSY (maximum sustainable yield)
massimo prodotto sostenibile
Tipica funzione f(x)
(a densità x troppo elevata
l’animale non riproduce (o
meglio non cresce) o si
innescano facilmente
malattie di tipo epidemico)
154
PROBLEMI LINEARI
Programmazione Lineare (PL) (Linear Programming (LP))
1 1 2 2
11 1 12 2 1 1
1 1 2 2
1 2
min ( ) min ... obiettivo lineare
soggetto a
...
m vincoli lineari di uguaglianza
...
0 0 ... 0 vincoli di non nega
n n
n n
m m mn n m
n
J z r z r z r z
p z p z p z q
p z p z p z q
z z z
tività
Vettorialmente
min ( ) min
soggetto a
= matrice (m n)
0
cioè
min z Z
Z= : , 0 insieme di ammissibilità
T
z z
T
z
J z r z
Pz q P x
z
r z
z Pz q z
155
Esempio 1 (dieta ottima)
n sostanze commestibili
zi quantità sostanza i-esima
ci contenuto calorico sostanza i-esima
pi contenuto proteico sostanza i-esima
λ prezzo sostanza i-esima
1
min min min costo dietan
T
i iz z z
i
z z
Soggetto a
*
*
??? slack
??? slack
0
T
T
p z p
c z c
z
Caso di dieta
fatta da due sole
sostanze z1 e z2.
La dieta deve avere un certo contenuto proteico pari a p*
La dieta deve avere un contenuto calorico pari a c*
zi ≥ 0 per ogni i
156
Esempio 2 (modello di produzione)
In conclusione abbiamo:
prezzo di prezzo di costo divendita acquisto trasformazione
max
0 0 0 vincoli di non negatività
conservazione della ma
i i ij ij
i j i
j i ij
ij i
j
p y q u c x
y x x
x u
ssa
vincoli sulle risorse ( prezzi ombra)ij ij ji
a x y
1 1
y
m m
u y
u
u y
Questa operazione di trasformazione ha
un costo ij iji
c x
157
Come ottenere la forma standard
11 1 1 1
) max ( ) min ( )
) ... n n
a J z J z
b p z p z q
si può scrivere anche così:
11 1 1 1 1
1
...
0 (variabile "slack")
n n n
n
p z p z z q
z
c) Se una variabile zi non è vincolata in segno si può sostituirla
ovunque con la differenza di due nuove variabili vincolate.
zi non vincolata (zn+1 – zn+2)
zn+1 ≥ 0
zn+2 ≥ 0
Con questi (od altri) artifici si può sempre ricondursi in LP alla forma
standard (r, P, q)
Top Related