SistemiComplessi.pdf

7/23/2019 SistemiComplessi.pdf

1/40

Appunti delle Lezioni di Ottimizzazione

di Sistemi Complessi

a cura di G. Liuzzi1

Master in Ottimizzazione e Data Mining

[email protected] , http://www.iasi.cnr.it/liuzzi


2/40

Capitolo 1

Programmazione Multiobiettivo

1.1 Introduzione

Un problema matematico di ottimizzazione puo essere definito come la minimizzazione omassimizzazione di una funzione a valori reali su un insieme specificato. Limportanzadi questo modello matematico deriva ovviamente dal fatto che molti problemi reali ven-gono affrontati facendovi ricorso. Tuttavia quasi ogni problema reale di ottimizzazione e

caratterizzato dalla presenza contemporanea di piu obiettivi, cioe funzioni a valori reali damassimizzare e/o minimizzare, tipicamente in contrasto tra loro.Nel seguito considereremo il seguente problema di ottimizzazione multiobiettivo:

min (f1(x)f2(x) . . . f k(x))

x F (MOP)

ovek2 efi: IRn IR, per i = 1, . . . , k.Dora in avanti chiameremo IRk spazio degli obiettivie IRn spazio delle variabili di decisione.Un vettore xIRn sara pertanto unvettore di decisionimentre zIRk unvettore di obiettivi.Indicheremo, inoltre, conf(x) il vettore delle funzioni obiettivo (f1(x)f2(x) . . . f k(x)) e conZ=f(F) limmagine della regione ammissibileFnello spazio degli obiettivi (vedi figura) ecioe Z=f(F) = zIRk : x F, z= f(x).In particolare diremo che un vettore di obiettivi zIRk e ammissibile quando risulti z Z.Definiamo , inoltre, il vettoreidealedegli obiettivi z id come il vettore di componenti Vettore ideale

zidi = min fi(x)

x FQuello che vogliamo fare e minimizzare tutte le funzioni obiettivo simultaneamente. Senon ci fossero conflitti tra le funzioni obiettivo, una soluzione banale al problema sarebbequella ottenibile risolvendo separatamente k problemi di ottimizzazione (uno per ogni fun-zione obiettivo) ottenendo quindi come soluzione proprio il vettore idealez id. Non sarebbepertanto necessario applicare nessuna tecnica specifica di soluzione. Per evitare il sorgeredi tale caso banale, supporremo che zid Z. Questo significa assumere che le funzionif1(x), f2(x), . . . , f k(x) siano, almeno in parte, in contrasto tra loro.ConB(x, ) ={yIRn| x y< }indicheremo la sfera aperta di centroxIRn e raggio >0. Dato un insieme A, indicheremo con Ala frontiera di A, con

Alinterno e con A lachiusura di A.

1


3/40

1z

2z

1x

2x

f

3x

SZ=f(S)

Dati due insiemi A e B definiamo linsieme differenza A\B come quellinsieme costituito datutti e soli gli elementi di A che non appartengono a B , ovvero

A\B= xA : xB.Dato un vettore b IRn ed un insieme A IRn, definiamo traslazione di A rispetto a blinsieme

b + A=

xIRn :x = b + a per ogni aA.In maniera del tutto analoga definiamo linsieme

b A= xIRn :x = b a per ogni aA.SeI e un insieme di indici ev un vettore, convIindicheremo il sottovettore costituito dallecomponenti di v con indici in I. Sia infine IRk+ lortante positivo dello spazio degli obiettivicioe

IRk+ =

zIRk : z0.1.2 Ottimalita secondo Pareto

Prima di procedere, e necessario definire con chiarezza cosa si intende per soluzione ot-tima di un problema di programmazione multiobiettivo. La definizione che adottiamo e

che e riportata nel seguito, e stata proposta per la prima volta da Edgeworth nel 1881 esuccessivamente ripresa da Vilfredo Pareto nel 1896 [4] che la approfond ulteriormente.

Definizione 1.2.1 Dati due vettoriz1, z2 IRk, diciamo chez1 dominaz2 secondo Pareto(z1 P z2) quando risulta

z1i z2i per ogni i = 1, 2, . . . , k ez1j < z

2j per almeno un indice j {1, . . . , k}.

La relazione binaria P e un ordinamento parziale (non riflessivo) nello spazio delle k-uple dinumeri reali. Sfruttando la relazionePpossiamo dare la definizione di ottimalita secondoPareto.

Definizione 1.2.2 Un vettore di decisioni x

F e un ottimo di Pareto se non esiste Ottimo di Paretounaltro vettorex F tale che:

f(x)P f(x).

2


4/40

Ottimi globali

Ottimi locali

Figura 1.1: Ottimi locali e globali di Pareto.

Corrispondentemente diremo che un vettore di obiettivi z Z e ottimo secondo Paretoquando non esiste un altro vettore z Ztale che

zP z.Quindi se ci troviamo in un punto ottimo secondo Pareto e vogliamo ulteriormente diminuireil valore di una o piu funzioni obiettivo dobbiamo essere disposti ad accettare un conseguente

aumento in alcune (o tutte) le rimanenti funzioni del problema. In tal senso possiamoaffermare che, nello spazio degli obiettivi, gli ottimi di Pareto sono punti di equilibrioche sitrovano sulla frontiera dellinsiemeZ.Definizione 1.2.3 Diciamo frontiera efficiente linsieme degli ottimi di Pareto del problema Frontiera

efficiente(MOP)

La definizione di ottimo secondo Pareto e ovviamente, una definizione di ottimoglobaledatoche si richiede la validita di una certa proprieta sututtolinsieme ammissibile del problema(MOP). E evidentemente possibile, pero, dare una definizione di ottimo locale secondoPareto.

Definizione 1.2.4 Un vettore di decisionix F e un ottimo locale di Pareto se esiste un Ottimo localedi Paretonumero >0 tale chex e ottimo secondo Pareto inF B(x, ).

In figura 1.1 si riportano gli ottimi globali e locali di Pareto per un insieme Z.Ovviamente, ogni ottimo globale e anche un ottimo locale di Pareto. Il viceversa e vero solose facciamo alcune ipotesi sulla struttura del problema (MOP). Se (MOP) e convesso cioese

i- linsieme ammissibileF e convesso eii- tutte le funzioni obiettivo fi(x) (coni = 1, 2, . . . , k) sono convesse.

allora si puo dimostrare che ogni ottimo locale di Pareto e anche un ottimo globale.

Teorema 1.2.5 Sia (MOP) un problema di programmazione multiobiettivo convesso. Allo- Equivalenza traottimi locali e

globali

di Pareto

ra, ogni ottimo locale di Pareto e anche un ottimo globale.

La definizione di ottimo secondo Pareto puo essere leggermente indebolita ottenendo cos la

definizione di ottimo debolesecondo Pareto.

Definizione 1.2.6 Un vettorex F e un ottimo di Pareto debole per il problema (MOP) Ottimalita debolesecondo Paretose non esiste un puntox F tale che

f(x)< f(x).

3


5/40

2

Z1

Z

Ottimi deboli di Pareto

Ottimi di Pareto

Figura 1.2: Gli ottimi di Pareto sono individuati dalla linea doppia a tratto continuo. La linea tratteggiataindividua invece gli ottimi deboli che non sono ottimi di Pareto.

Ovviamente, linsieme degli ottimi secondo Pareto e contenuto nellinsieme degli ottimideboli di Pareto.Anche qui, come gia si era fatto per gli ottimi di Pareto, e possibile dare una definizione diottimo locale debole.

Definizione 1.2.7 Un vettore di decisioni x F e un ottimo locale debole (secondo Ottimo localedebole di ParetoPareto) se esiste un numero >0 tale chex e ottimo debole di Pareto inF B(x, ).

In figura 1.2 sono riportati, per maggiore chiarezza, ottimi e ottimi deboli secondo Pareto.

Anche per gli ottimi deboli secondo Pareto vale una proprieta analoga a quelle espressa dalteorema 1.2.5 e cioe se il problema (MOP) e convesso ogni ottimo locale (debole) e ancheottimo globale (debole) di Pareto.

1.2.1 Esercizio

Sia dato il seguente problema di ottimizzazione vettoriale:

min (x1+ x2, x1 x2)

x21+ x222

x21 x20x1

0

(1)

In questo caso, in cui il vettore delle decisioni ha dimensione due, e semplicissimo tracciarela regione ammissibile nello spazio delle variabili di decisione. Inoltre, poiche il vettore degliobiettivi ha dimensione due e le funzioni obiettivo sono lineari, possiamo determinare larappresentazione grafica diZ= f(F). Vediamo nel dettaglio come fare.Le relazioni che dobbiamo prendere in considerazione sono le seguenti due trasformazionilineari:

z1 = f1(x1, x2) =x1+ x2

z2 = f2(x1, x2) =x1 x2(2)

La regione ammissibile degli obiettivi e ottenibile da quella delle decisioni mediante rotazionee scalatura, come messo in evidenza dalla figura 1.3

Sempre per via grafica, e facile risolvere i sottoproblemi ad un solo obiettivo associati al

4


6/40

F

Z

2

z 1

zid

Ottimi di Pareto

x2

x

f

1

2

1 2

-2

-1

1

2

2 3

1

1

z

Figura 1.3: Esempio

problema (1) che sono:

zid1 = min x1+ x2

x21+ x222

x21 x20x10

x1 = (0, 0)

e

zid2 = min x1 x2

x21+ x222

x21 x20x10

x2 = (0,

2)

ricavando, in tal modo, il vettore ideale degli obiettivi z id = (0, 2). Notiamo subito chenon essendo zid contenuto in

Z = f(

F), il problema vettoriale non e risolvibile semplice-

mente minimizzando separatamente le due funzioni obiettivo.E altres facile individuare, in figura 1.3, la frontiera efficiente secondo Pareto dellinsiemeZ. Come ci aspettavamo, essendo il problema (1) convesso, tutti gli ottimi locali di Paretosono anche globali.

1.3 Condizioni di Ottimalita

Nelle sezioni precedenti abbiamo dato delle definizioni fondamentali della programmazionemultiobiettivo. In particolare, dato che lo spazio delle k-uple di numeri reali e solo parzial-mente ordinato, abbiamo dovuto definire cosa si intende per minimo di un vettore difunzioni.Quello che dobbiamo fare ora, e dare una caratterizzazione analitica dei punti di ottimo

secondo Pareto. Come vedremo, tutte le condizioni di ottimo per la programmazione multi-obiettivo, comprendono come caso particolare quelle per la programmazione nonlineare (conuna sola funzione obiettivo). Per ulteriori approfondimenti sullargomento di questa sezionesi rimanda al testo [1] citato in bibliografia.

5


7/40

Nel seguito consideriamo un problema in cui F e definito da vincoli di disuguaglianza; cioe:

min f(x)

g(x)0 (P)

ovef : IRn IRk (k2) eg : IRn IRm sono funzioni continuamente differenziabili edFassume la seguente struttura:

F={xIRn : g(x)0}.Indichiamo con

I0(x) ={i: gi(x) = 0}

linsieme degli indici dei vincoli attivi nel punto x. Sia, inoltre, L : IRnkm IR cosdefinita

L(x,,) = f(x) + g(x),

la funzione Lagrangiana associata al problema (P).

1.3.1 Condizioni di Fritz-JohnUna prima condizione necessaria di ottimo per il problema multiobiettivo (P) e data dalseguente teorema.

Teorema 1.3.1 Condizione necessaria affinche x F sia ottimo secondo Pareto e che CN di Fritz-Johnesistano dei vettoriIRk eIRm tali che sia soddisfatto il seguente sistema:

ki=1

ifi(x) +m

j=1

jgj(x) = 0 (3a)

g(x) = 0, (3b)

(, )0, (, )= (0, 0) (3c)

Esempio di punto che soddisfa le condizioni

necessarie di ottimalita.

Esempio di punto che NON soddisfa le condizioni

necessarie di ottimalita.

Corollario 1.3.2 Le condizioni del teorema 1.3.1 sono necessarie anche per lottimalitadebole (secondo Pareto) di un punto x.

6


8/40

Definizione 1.3.3 (tripla di FJ) Una tripla (x,,) IRnkm e una tripla di Fritz-John quando soddisfa il sistema (3) cioe:

xL(x,,) = 0g(x)0g(x) = 0

(, )0 (, )= (0, 0).

Definizione 1.3.4 (punto di FJ) Un vettore di decisioni x IRn e un punto di FJ seesistono dei vettoriIRk eIRm tali che(x,,) e una tripla di FJ.

1.3.2 Condizioni di Karush-Kuhn-Tucker

Si pufacilmente far vedere che esistono casi in cui un punto ammissibile potrebbe essere unpunto di FJ indipendentemente dalle funzioni obiettivo. Motivati da questa considerazioneintroduciamo in questo paragrafo le condizioni di KKT con le quali in pratica forziamo igradienti di alcune funzioni obiettivo ad avere un peso non nullo nellespressione (3a).Preliminarmente introduciamo la seguente definizione.

Definizione 1.3.5 Un punto ammissibile x F e un punto di regolarita per i vincoli del LICQproblema (P) se inx sono linearmente indipendenti i gradienti dei vincoli attivi.

A questo punto possiamo dare la seguente ulteriore condizione necessaria di ottimalitasecondo Pareto.

Teorema 1.3.6 Siax un punto ammissibile per il problema (P) e siano linearmente in- CN di KKTdipendenti i gradienti dei vincoli attivi inx. Allora, condizione necessaria affinchex sia unottimo di Pareto (locale o globale) e che sia ammissibile il seguente sistema:

ki=1

ifi(x) +m

j=1

jgj(x) = 0, (4a)

g(x) = 0, (4b)

(, )

0, = 0. (4c)

Corollario 1.3.7 Le condizioni del teorema 1.3.6 sono necessarie anche per lottimalitadebole (secondo Pareto) di un punto x.

Le condizioni di KKT (come quelle di FJ) sono condizioni solo necessarie di ottimo il chevuol dire che potrebbero essere verificate anche in punti non ottimi secondo Pareto. Etuttavia possibile dare condizioni sufficienti di ottimalita, senza ricorrere alluso delle derivateseconde, a patto pero di fare alcune ipotesi aggiuntive sulla struttura del problema (P).

Teorema 1.3.8 Siano lefi(x) (per ogni i = 1, 2, . . . , k) egj (x) (per ognij = 1, 2, . . . , m) CS di ottimosecondo Paretoconvesse. Condizione sufficiente affinche un punto x F sia ottimo secondo Pareto e che

esistano dei vettori di moltiplicatoriIRk eIRm tali che

xL(x,,) = 0, (5a)g(x) = 0, (5b)

>0, 0. (5c)

7


9/40

Si noti che nelle condizioni sufficienti di KKT appena viste si richiede che tutti i moltiplicatoridelle funzioni obiettivo siano strettamente positivi mentre nelle condizioni necessarie almenoun i e strettamente positivo.Per quanto riguarda i punti di ottimo debole secondo Pareto, e possibile stabilire, sempresotto le ipotesi di convessita, un risultato ancora piu forte. Per tali punti si possono darecondizioni necessarie e sufficienti di ottimo.

Teorema 1.3.9 Siano lefi(x) (per ogni i = 1, 2, . . . , k) egj (x) (per ognij = 1, 2, . . . , m) CNS di KKTconvesse. Condizione necessaria e sufficiente affinche un punto x

F sia ottimo debole

secondo Pareto e che esistano dei moltiplicatoriIRk eIRm tali chexL(x,,) = 0,g(x) = 0,

(, )0, = 0.

1.4 Metodi di Soluzione

Generare le soluzioni ottime secondo Pareto costituisce una parte essenziale della program-mazione vettoriale ed anzi, matematicamente parlando, nella maggior parte dei casi, il prob-lema (P) si considera risolto una volta che sia stato individuato linsieme degli ottimi diPareto. Tuttavia, non sempre ci si puo accontentare semplicemente di aver trovato linsiemedegli ottimi secondo Pareto. Alcune volte e infatti necessario ordinare tutte le soluzionitrovate e quindi selezionare la migliore rispetto a tale ordinamento. Per questo motivo ab-biamo bisogno di un decisorecioe di qualcuno che ci dica, in base alle sue preferenze, comeordinare linsieme degli ottimi di Pareto del problema (P).In base al ruolo svolto dal decisore nella strategia di soluzione del problema, i metodirisolutivi della programmazione multiobiettivo vengono spesso suddivisi in quattro grandicategorie.

Metodi senza preferenzenei quali il decisore non ha nessun ruolo e si considera soddis-facente laver trovato un qualunque ottimo di Pareto.

Metodi a posteriorinei quali si genera linsieme di tutti gli ottimi di Pareto e poi lo sipresenta al decisore che sceglie la soluzione per lui migliore.

Metodi a priorinei quali il decisore specifica le sue preferenze prima che abbia inizioil processo risolutivo. In base alle informazioni avute dal decisore viene direttamentetrovata la soluzione ottima migliore, senza dover dunque generare tutti gli ottimi diPareto.

Metodi interattivinei quali il decisore specifica le sue preferenze mano a mano chelalgoritmo procede, guidando in tal modo il processo risolutivo verso la soluzione perlui piu soddisfacente.

Al di la di questa distinzione, tutti i metodi di soluzione per la programmazione multio-biettivo si basano sulla medesima idea di fondo, ovvero quella di trasformare il problemaoriginario in uno con una sola funzione obiettivo. La tecnica mediante la quale si ottiene il

problema mono obiettivo a partire dal problema (P) e nota come scalarizzazione.

1.4.1 Metodi Senza Preferenze

Nei metodi senza preferenze ci si accontenta di generare una soluzione ottima di Pareto,qualunque essa sia, senza tenere in considerazione le indicazioni del decisore.

8


10/40

Il metodo che presentiamo e noto come metodo GOAL (cfr. [3, sez. 2.1]). Quello chesi fa e cercare la soluzione che minimizza, nello spazio degli obiettivi, la distanza tra laregione ammissibile (Z) e un qualunque punto di riferimento zref Z = f(F). Il vettoredi riferimento sara costituito dai valori auspicabili per le singole funzioni obiettivo. Inparticolare, una possibile scelta di zref e z ref = z id. Il problema che otteniamo e percio ilseguente:

min f(x) zidp

g(x)0(Pp)

ove p indica la norma p di un vettore (con 1p ). In particolare, se p =, ilproblema (Pp) e noto come problema di Tchebycheff. Supponiamo di conoscere il vettoreidealeglobaledegli obiettivi. Sotto tali ipotesi, il problema (Pp) ammette sempre soluzione.Valgono le seguenti proprieta.

Proposizione 1.4.1 Ogni soluzione globale del problema (Pp) (con1p


11/40

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

x2

F

1

1

1

2

x2

Figura 1.4: Regione ammissibile

Normap=.In questo caso, il problema scalarizzato

min maxi=1,...,k

{|ci x zidi|}Axb

puo essere facilmente trasformato in un problema di PL con laggiunta di una sola variabileausiliaria,, ottenendo:

min |ci x zidi| i= 1, 2, . . . , k

Axb

Esempio

Si consideri il seguente problema di programmazione multiobiettivo:

min (x1, x2)

x21+ x221

0x120x22

(Pes)

In questo esempio, vedi figura 1.4, le regioni ammissibili nello spazio delle variabili didecisione ed in quello degli obiettivi coincidono essendo

z1 = x1z2 = x2

Possiamo inoltre facilmente calcolare il vettore ideale degli obiettivi ottenendo cos: zid =(0, 0). In figura 1.5a sono riportati gli ottimi di Pareto del problema (Pes).A questo punto applichiamo il metodo GOAL con p = 1, 2, .

10


12/40

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 00 0 0 0 0 0 00 0 0 0 0 0 00 0 0 0 0 0 00 0 0 0 0 0 0

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 11 1 1 1 1 1 11 1 1 1 1 1 11 1 1 1 1 1 11 1 1 1 1 1 1

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

1 1 1 1 1 1 1

(c)(b)(a)

(d)

Figura 1.5: Differenti soluzioni in corrispondenza a differenti tipi di norme.

p= 1. Il problema scalarizzato con questo tipo di norma ha due soluzioni (vedi figura1.5b).

p= 2. Il problema che otteniamo usando la norma euclidea ha infinite soluzioni (comesi vede in figura 1.5c) e cioe tutte le soluzioni del problema (Pes).

p=. Il problema di Tchebycheff ha una sola soluzione (vedi figura 1.5d)

1.4.2 Metodi a Posteriori

I metodi appartenenti a questa classe sono anche noti come metodi per generare linsiemedelle soluzioni di Pareto. Infatti, siccome le preferenze del decisore vengono consideratesolo al termine del processo risolutivo, quello che si fa e generare tutti i punti ottimi sec-

ondo Pareto. Una volta che linsieme delle soluzioni di Pareto e stato generato, esso vienepresentato al decisore che seleziona il o i vettori per lui migliori.Linconveniente principale di questa strategia sta nel fatto che il processo di generazione degliottimi di Pareto e, molto spesso, computazionalmente oneroso. Inoltre, potrebbe non esseresemplice, per il decisore, scegliere una soluzione tra gli ottimi che gli vengono presentati, inspecial modo se questi sono numerosi. Per questo motivo, e molto importante il modo conil quale le soluzioni vengono presentate al decisore.

Metodo dei Pesi (cfr. [3, sez. 3.1])

Consideriamo il seguente problema

min

ki=1

wifi(x)

g(x)0(Pw)

11


13/40

ovewIRk+ e i coefficienti wi si intendono normalizzati cioe tali chek

i=1

wi= 1.

Esiste una relazione tra le soluzioni di (Pw) e i punti di Pareto di (P). La seguenteproposizione mette in evidenza proprio questa relazione (cfr. [3]).

Proposizione 1.4.5 Ogni soluzione locale (globale) del problema (Pw) e un ottimo debole

locale (globale) di Pareto per il problema (P).

Nel caso in cui il problema (Pw) ammette una unica soluzione allora si puo stabilire unrisultato un po piu forte del precedente (cfr. [3]).

Proposizione 1.4.6 Se il problema (Pw), fissato il vettore dei pesi w 0, ammette unaunica soluzione allora essa e un ottimo di Pareto per il problema (P).

Allo stesso modo, se i pesi wi sono tutti strettamente positivi e possibile dimostrare laseguente

Proposizione 1.4.7 Sewi > 0 per ogni indicei, ogni soluzione locale (globale) del problema(Pw) e un ottimo locale (globale) di Pareto per il problema (P).

Nellipotesi in cui il problema multiobiettivo (P) e convesso, e possibile stabilire la seguente

proprieta di esistenza (cfr. [3])Proposizione 1.4.8 Sia x un ottimo di Pareto per il problema (P). Se (P) e convessoallora esistono dei pesiwIRk+ con

ki=1

wi= 1

e tali chex e soluzione anche del problema (Pw).

Metodo degli -vincoli (cfr. [3, sez. 3.2])

Si seleziona una funzione obiettivofl(x) tra gli obiettivi di (P) e poi si trasformano tutte lealtre funzioni fi(x) (con i = 1, 2, . . . , k i= l) in vincoli, imponendo degli upper boundsuiloro valori. Il problema che otteniamo e allora il seguente:

min fl(x)

fi(x)i i= 1, 2, . . . , k i=lg(x)0

(P)

ovel {1, 2, . . . , k}.Proposizione 1.4.9 (cfr. [3]) Ogni soluzione di (P) e un ottimo debole secondo Paretoper il problema (P).

La prossima proposizione fornisce condizioni necessarie e sufficienti di ottimalita (secondoPareto) per il problema (P) delle soluzioni di (P).

Proposizione 1.4.10 Un vettore x

F e ottimo secondo Pareto di (P) se e solo se e

soluzione di (P) per ogni scelta dil {1, 2, . . . , k} ed essendo i= fi(x) con i=l.Proposizione 1.4.11 (cfr. [3])Se il punto x F e lunica soluzione del problema (P)per qualchel {1, 2, . . . , k} e conj =fj (x) per ognij=l allora esso e Pareto ottimo peril problema (P).

12


14/40

Capitolo 2

Programmazione con Incertezza

2.1 Nozioni preliminari

E noto che un generico problema di ottimizzazione puo essere posto nella forma [2]

minx f(x)

c.v. x D

,

ovexIRn e detto vettore delle variabili di decisione,f : IRn IR e detta funzione obiettivoeD IRn e detto insieme ammissibile. A seconda delle proprieta della funzione f(x) edellinsiemeDparleremo di ottimizzazione lineare o non lineare, ottimizzazione vincolata onon vincolata, ottimizzazione continua o combinatoria e cos via.Per quanto concerne queste note e comodo introdurre la seguente funzione obiettivo estesaf : IRn IR tale che

f(x) =

f(x) sex D,+ sex D,

per cui e possibile riscrivere il generico problema di ottimizzazione come

minx

f(x).

Dato uno spazio di probabilita (, F, P), sia : (, F)(IRn, Bn) una v.a. e supponiamoche la funzione obiettivo f(x, ) e linsieme ammissibileD() dipendano dalle realizzazionidi . Anche in questo caso possiamo pensare alla funzione obiettivo estesa definita come

f(x, ) =

f(x, ) sex D(),+ sex D().

Nel caso attuale, in cui i dati del problema dipendono esplicitamente dalla v.a. , non e piuimmediato riconoscere un problema di ottimizzazione nel senso che non e ben chiaro cosadobbiamo ottimizzare e con quali vincoli dato che sia la funzione obiettivo che la regione

ammissibile dipendono da un elemento incerto ovvero dalle realizzazioni della v.a. . Inaltri termini, non ha certamente senso considerare il problema

minx

f(x, ) (1)

13


15/40

2.1.1 Formulazione deterministica

Ci sono diversi modi di trattare lincertezza in un problema di ottimizzazione. Un primomodo consiste nello stimare un valore della v.a. (come per esempio il suo valore attesoIE[]), sia esso , e quindi risolvere il problema

minx

f(x,) (2)

In questo caso, la funzione obiettivo f(x,) non dipende piu dalla v.a. che e fissata

al valore e quindi il problema e nuovamente un problema, per cos dire, deterministicoche puo essere risolto come usualmente si farebbe. Questo approccio, benche perfettamentegiustificabile in alcuni ambiti applicativi, potrebbe non avere molto senso e, a volte, portarea soluzioni certamente non ottime come vedremo piu avanti con alcuni esempi.

2.1.2 Osservazione e ottimizzazione

In alcuni casi e possibile posticipare la scelta delle variabili di decisionex ad un momentosuccessivo alla osservazione della v.a. il che corrisponde a quella che viene comunementedefinita strategiawait-and-see. In questo caso, ci troviamo a dover risolvere un problema diottimizzazione in x che dipende da come parametro. Potremmo cos pensare di risolvereil problema (2) solo per il valore corrispondente alla realizzazione della v.a. oppurepotremmo concentraci sulla determinazione del valore ottimo

() = infx

f(x, )

e dellinsieme di soluzioni ottime

() = arg minx

f(x, ),

entrambi funzione della variabile aleatoria .

2.1.3 Ottimizzazione e osservazione

Contrariamente al caso precedente, potrebbe non essere possibile posticipare la scelta di xfin dopo aver osservato la realizzazione della v.a. ovvero e necessario adottare quella che

comunemente viene definita strategia here-and-now. In questo assetto le decisione vannoprese subito avendo a disposizione solo la conoscenza sulla v.a. che ci viene dalla suaf.d. In questo caso e necessario riflettere sul fatto che per ogni scelta delle variabili x nonabbiamo un valore certo f(x) ma, piuttosto, un valore incertof(x, ). In altri termini, perogni realizzazione della v.a. abbiamo una funzionef(x, ) ovvero, potremmo pensaread f(x, ) come ad una v.a. composta.

Il caso peggioreIn questo assetto possiamo pensare di risolvere il problema minx f(x) dove

f(x) = sup

f(x, ).

Ovviamente, questo significa concentrarsi esclusivamente sul peggiore risultato ottenibileavendo fissato le variabili x senza alcun tentativo di distinguere le realizzazioni della v.a. inbase alla sua distribuzione di probabilita.

14


16/40

Programmazione stocasticaQuesto approccio consiste nellinterpretare, per ogni x, f(x, ) a sua volta come una v.a.che eredita la sua f.d. da quella della v.a. . E dunque possibile, per ogni x, calcolare ilvalore atteso f(x) = IE[f(x, )] e quindi risolvere il problema

minx

f(x). (3)

2.1.4 Esempio: il problema del venditore di giornali

Questo problema, meglio noto con il nome di newsvendor problem, e probabilmente il piusemplice esempio di ottimizzazione in presenza di incertezza ed e, pertanto, particolarmenteadatto per familiarizzare con alucni fondamentali concetti della programmazione in presenzadi incertezza. Il problema e il seguente.Il ragazzo che vende i giornali al semaforo deve decidere quanti giornali x acquistare alleprime luci dellalba dalleditore al costo di c euro per giornale. Durante la mattinata potrarivendere i giornali al prezzo di s euro luno e, a fine mattinata, puo rivendere alleditore igiornali non venduti ricavando r euro luno. Ovviamente vale la seguente relazione

0r < c < s.Il grosso problema del venditore e che, al momento in cui deve scegliere quanti giornali (x)acquistare dalleditore, non conosce con esattezza il numero di clienti che acquisteranno ilgiornale da lui al semaforo. In altri termini, la sua domanda giornaliera di quotidiani puo

essere considerata come una variabile aleatoria la cui realizzazione accadr a in un momentosuccessivo a quello in cui deve acquistare i giornali dalleditore.Indichiamo con Dla v.a. che descrive il numero di giornali effettivamente venduti al semaforodurante la mattinata. La tabella che segue riporta i costi, i ricavi e il profitto del venditorenella mattinata in funzione della variabile di decisione x e della v.a. D.

Costi Ricavi

acquisto giornali: cx

vendite al semaforo:

sx se x < D

sD se xD

vendite alleditore: 0 se x < D

r(x

D) se x

D

profitto:f(x, D) =cx + s min{x, D} + r max{0, x D}Il problema da risolvere sarebbe dunque il seguente

minx0

f(x, D),

e cioe un problema della forma di (1) in cui la v.a. = D.Supponiamo ora che il venditore possa decidere quanti giornali acquistare dalleditore dopoaver avuto notizia di quanti giornali potra vendere nella mattinata. Siamo nel caso wait-and-see(cfr. sottosezione 2.1.2) in cui la v.a. D e trattata come un parametro. In questocaso laf(x, D) e funzione della sola variabile x e dipende parametricamente da D.

x

f(x, D)

D

15


17/40

Ovviamente, la soluzione ottima risulta essere x = D e il valore ottimo (cs)D ovvero,coerentemente con la notazione fin qui adottata,

(D) = (c s)D,

e

(D) ={xIR :x = D}.

Ovviamente, questa tecnica risolutiva ha senso solo quando e lecito supporre che ci sia unasorta di oracolo che predice al venditore il numero di giornali che potra vendere al semaforo.In ogni altro caso, questa tecnica risolutiva non ha molto senso.Supponiamo ora che D sia una v.a. discreta cioe abbia la seguente f.d. di probabilita

evento FD()D = 30 1/7

D = 40 2/7

D = 50 2/7

D = 60 1/7

D = 100 1/7

Un altro modo di approcciare il problema consiste, come accennato nella sottosezione 2.1.1,nel risolvere un problema in cui si fissa il valore della v.a., per esempio, al suo valore attesoIE[D] = D= 370/7 e quindi risolvere il problema perD = D. In questo caso la soluzione e,banalmente, (D) cioex = D, y1 = D ey2= 0 con valore ottimo (D) = (c s)D.Come visto nella sottosezione 2.1.3, un ulteriore modo di procedere e quello di risolvere ilproblema

minx0

max30D100

f(x, D).

Considerato il fatto che la funzione f(x, D) e in questo caso non crescente rispetto allavariabile D,

D

f(x, D)

x

risulta max30D100 f(x, D) = f(x, D), con D= 30. Daltra parte, siccome, come si verificafacilmente, la funzione f(x, 30)

x

f(x, 30)

30

16


18/40

e decrescente per 0x30 e crescente per x30, il problema minx0 f(x, 30) ha soluzioneottima x = D = 30 con valore ottimo (c s)x = 30(c s). Questa soluzione corrispondeperfettamente allatteggiamento del venditore che, cautamente, sceglie di acquistare il mag-gior numero di giornali nellipotesi di venderne il minor numero possibile. I limiti di questoapproccio sono evidenti. Nel caso, per esempio, in cui sia possibile anche levento D = 0la strategia che dovremmo adottare sarebbe x = 0 ovvero il venditore non acquista alcungiornale per limitare i danni nel caso peggiore in cui gli dovesse capitare di non vendernenessuno.

Per concludere la rassegna dei vari approcci al problema rimane da analizzare quello dettodi stochastic programming (programmazione stocastica). Secondo quanto visto nella sot-tosezione 2.1.3, questo tipo di approccio consiste nel considerare, per ogni valore x ammis-sibile, la f(x, D) come una nuova v.a. per la quale e possibile calcolare il valore attesoIED[f(x, D)] e quindi risolvere il problema

minx0

IED[f(x, D)]. (4)

Nel caso in esame, in cui D e una v.a. discreta, la funzione che otteniamo e

f(x) =IED[f(x, D)] =1

7f(x, 30) +

2

7f(x, 40) +

2

7f(x, 50) +

1

7f(x, 60) +

1

7f(x, 100)

che e una funzione convessa, lineare a tratti e continua ma non differenziabile. Sia f(x) il

subdifferenzialedi f inx cos definito:

f(x) ={tIR : f(y)f(x) + t(y x) per ogni yIR}.Per la funzione f(x) risulta

f(x)

(c s) se x


19/40

avendo indicato con F1D () = min{x : FD(x)} ovvero l-quantiledella distribuzionedi probabilitaFD(). Notiamo chex

corrisponde al punto in cui la pendenza di f(x) passada negativa (f(x) decrescente) a positiva (f(x) crescente).La figura che segue riporta landamento della funzione f(x), quando r = 0.8, c = 1.6 es= 1.8, da cui e facile riconoscere che il valore ottimo del problema (4) e

x =F1D (0.2) = 40.

x

IED[f(x, D)]

30 40 50 60 100

Supponiamo ora che D sia una v.a. continua, cioe una v.a. con f.d. FD() continua, per

cui risulta

f(x) =IE[f(x, D)] =

0

f(x, )dFD().

Notiamo che, anche in questo caso, essendo la funzione f(x, D) convessa (e lineare a trattirispetto adx), anche la funzione f(x) e convessa rispetto ad x. Allora

f(x) =cx +

x0

[rx (s r)]dFD() sx

x

dFD(),

da cui, mediante integrazione per parti, otteniamo

f(x) = (c s)x + (s r) x

0 FD()d.

Derivando rispetto a x, otteniamo, come nel caso precedente,

f(x) = (c s) + (s r)FD(x).

Percui, ricordando che f(x) e convessa rispetto a x, x e punto di minimo se e solo se

f(x) = (c s) + (s r)FD(x) = 0,

da cui, anche in questo caso, otteniamo

FD(x) =

s cs

r

e quindi, nuovamente,

x =F1D

s cs r

.

18


20/40

2.2 Fondamenti di Programmazione Stocastica

Come gia in parte anticipato nel corso della precedente sezione, le principali caratteristichedella programmazione stocastica sono le seguenti:

1. here-and-now, vale a dire che, non ostante lingente coinvolgimento di accadimentifuturi, ogni cosa e mirata al miglioramento di decisioni che devono essere prese nelpresente ovvero prima che qualunque v.a. possa realizzarsi;

2. ricorsione, ovvero lopportunita che e data al modellista di tenere conto del fattoche le decisioni prese nel presente possano essere, almeno in parte, corrette in tempisuccessivi;

3. informazione e osservazione, le decisioni in tempi successivi possono rispondere a in-formazioni che si sono rese disponibili da quando sono state prese le decisioni iniziali.Questa informazioni e modellata mediante losservazione di v.a.;

4. convessita, teoria e metodi risolutivi di programmazione stocastica sono sviluppatisotto lipotesi restrittiva di convessita;

5. indipendenza delle misure di probabilita dalle decisioni, si assume cioe che le v.a. sianoindipendenti dalle decisioni.

Uno degli aspetti piu caratteristici della programmazione stocastica ed anche quello che mag-

giormente la differenzia dalla programmazione matematica e certamente quello dinamico.Piu precisamente, in un contesto di programmazione stocastica e opportuno familiarizzarecon il cos detto processo ricorsivo nel quale le decisioni si alternano con le osservazioni. Inparticolare possiamo pensare al seguente processo ricorsivo

u0IRn0 decisione iniziale11 osservazione

u1IRn1 decisione di ricorsione22 osservazione

u2IRn2 decisione di ricorsione...

NN osservazioneuNIRnN decisione di ricorsione

In questo processo ricorsivo, abbiamo uno stadio iniziale nel quale viene presa la decisioneu0 IRn0 e successivamente Nstadi di ricorsione ciascuno composto da una osservazione,nella quale una v.a. si realizza, e da una decisione, che dovrebbe essere la risposta al-losservazione appena avvenuta. Alla fine di questo processo ricorsivo, avremo un vettore didecisioni

u= (u0, u1, . . . , uN)IRn con n= n0+ n1+ + nNe un vettore di osservazioni che potremmo definire la storia delle osservazioni e rappresentarecome

= (1, . . . , N) con = 1 N.Un altro ingrediente essenziale e il costo del processo ricorsivo che puo essere pensato comeuna funzione f : IRn IR con

f(u, ) = f(u0, u1, . . . , uN, 1, . . . , N).

19


21/40

Naturalmente la funzionef(u, ) ha valori nello spazio esteso dei reali ovvero puo assumereanche il valore +. Piu precisamente, f(u, ) = +quandouC().A questo punto, potremmo pensare che lo scopo dellottimizzatore sia quello di risolvere ilseguente problema

minu

IE [f(u, )],

ovvero un problema come il problema (3). Ovviamente, questo non e il caso. Infatti sefacessimo cos, ci troveremmo, nuovamente, a dover scegliereu = (u0, u1, . . . , un) prima diconoscere = (1, . . . , N), il che distruggerebbe immediatamente tutti i vantaggi di averedecisioni e osservazioni mescolate le une con le altre. In particolare, nel nostro caso, seci poniamo nello stadio k-esimo possiamo partizionare il vettore = (1, . . . , N) nei duesottovettori

(1, . . . , k) informazione disponibile

(k+1, . . . , N) incertezza residua.

Nel fare questo, bisogna sempre tenere presente che il fine ultimo dellottimizzazione e quellodi produrre una decisione iniziale u0 e che le v.a. i, i = 1, . . . , N , non saranno maiveramente osservate ma, piuttosto, si potra al piu supporre che lo siano state. Per esempio,al generico stadiokci troveremo a dover determinare uksupponendo che siano state osservate1, . . . , k. Questo e il motivo per cui, allo stadio k, siamo interessati a determinare, non

tanto un vettoreukIRnk , quanto piuttosto unafunzione di ricorsionedefinita sullo spazio1 k

uk() : (1, . . . , k)uk(1, . . . , k)IRnk .Nello scegliere una tale funzione uk() stiamo, in sostanza, specificando nel presente (here-and-now) come risponderemo ad ogni possibile realizzazione delle prime k osservazioni.Definiamostrategiauna funzione u : IRn ovvero

u() = (u0, u1(1), u2(1, 2), . . . , uN(1, . . . , N)). (5)

Indichiamo conU linsieme di tutte le possibili funzioni u() di questo tipo. Notiamo chela componente uk() dipende da 1, . . . , k e non da k+1, . . . , N. Questa proprieta, det-ta non anticipo delle strategie, serve a garantire che le decisioni non siano basate sulla

conoscenza di eventi futuri prima che questi accadano. Il problema al quale arriviamo e ilseguente

minu()U

IE[f(u(), )],

dove u() e dato da (5). E importante notare che il precedente e un problema di ottimiz-zazione in cui le variabili di decisione sono particolari funzioni distinte dalla proprieta sopracitata di non anticipo.

2.2.1 Esempio: financial planning and control

Una famiglia americana sta progettando di mandare il proprio figlio al college. I genitorisanno che traY =N v anni, e cioe quando il figlio avra raggiunto leta per potersi iscrivere,

la retta per lintero periodo degli studi sara di G = 80000 euro. Al momento i genitoridispongono di un budget di b = 55000 euro (b < G) e devono decidere come investire questirisparmi. Al termine degliYanni i genitori potranno

1. prendere in prestito (con un interesser = 4%) i soldi che servono per arrivare a coprirela retta di G euro per liscrizione al college; oppure

20


22/40

2. depositare in un libretto di risparmio (con un interesseq= 1%) i soldi avanzati dopoil pagamento della retta di iscrizione.

La famiglia puo investire suItipi diversi di investimento e puo cambiare investimento ogniv anni. I genitori hanno, quindi, N=Y /v differenti periodi di investimento.Supponiamo, per semplicita di trattazione, che I= 2 (due soli tipi di investimento: stocko bond), N= 3 (tre periodi) e v = 5 (5 anni di durata minima di ogni investimento). Aseconda dellandamento dei mercati finanziari, si puo avere un interesse di 1.25 per gli stocke 1.14 per i bond oppure 1.06 per gli stock e 1.12 per i bond con uguali probabilit a (in

condizione di massima incertezza).Il processo decisionale e quella gia visto in precedenza in cui abbiamo N = 3 stadi diricorsione ovvero

u0 = (u10, u

20)

T IR2 decisione iniziale1 osservazione

u1(1) = (u11(1), u

21(1))

T IR2 decisione di ricorsione2 osservazione

u2(1, 2) = (u12, u

22)

T IRn2 decisione di ricorsione3 osservazione

u3(1, 2, 3) = (u13(1, 2, 3), u

23(1, 2, 3))

T IR2 decisione di ricorsione

dove ={up, down} contiene i due soli andamenti possibili per i mercati finanziari a cuicorrispondono i tassi di interesse degli investimenti disponibili.

Stadio iniziale: Le variabili di decisione sono indipendenti dalle v.a. (non anticipo)e rappresentano lammontare degli investimenti in stock e bond, rispettivamente,allinizio degli Y= 15 anni. Esse devono soddisfare il seguente vincolo

u10+ u20 = b,

ovvero, inizialmente, gli investimenti devono essere esattamente uguali al budget dib euro disponibili allinizio del periodo di investimento. Potremmo scrivere questovincolo, sinteticamente, come

iI

ui

0

= b.

Primo stadio: Le variabili di decisione di primo stadio dipendono dalla v.a. 1 manon da 2 e 3 (deve valere la proprieta di non anticipo). Come visto nel corso dellasezione e considerato il fatto che1 e una v.a. discreta, e possibile definire le funzioniu11(1) e u

21(1) in forma tabellare ovvero definendo le variabili u

11(up), u

11(down),

u21(up) e u21(down) che rappresentano le azioni intraprese nei due scenari di primo

stadio possibili (ed equiprobabili), ovvero 1 = up e 1 = down. Queste variabili diprimo stadio devono soddisfare i vincoli

1.25u10+ 1.14u20 = u

11(up) + u

21(up)

1.06u10+ 1.12u20 = u

11(down) + u

21(down),

cioe, qualunque sia la realizzazione della v.a. 1, quello che si investe nel quinto annodeve essere uguale al capitale disponibile nel quinto anno. Sintetizzando, possiamoscrivere questi vincoli come

iI

t1 ,iui0=

iI

ui1(1), 1.

21


23/40

Secondo stadio: Le variabili di decisione di secondo stadio dipendono dalle v.a. 1 e2 ma non (sempre per la proprieta di non anticipo) dalla v.a. 3. Anche in questocaso e possibile definire le funzioniu12(1, 2) e u

22(1, 2) mediante lintroduzione di

tante variabili di decisione quanti sono i possibili scenari di secondo stadio. Dato chei possibili scenari sono dati da tutte le possibili combinazioni di una realizzazione di1 con una realizzazione di 2, dobbiamo introdurre complessivamente 8 variabili eprecisamente:

u12

(up, up), u12

(up, down), u12

(down, up), u12

(down, down),

u22(up, up), u22(up, down), u

22(down, up), u

22(down, down).

Queste variabili devono soddisfare i vincoli

1.25u11(up) + 1.14u21(up) = u

12(up, up) + u

22(up, up)

1.06u11(up) + 1.12u21(up) = u

12(up, down) + u

22(up, down)

1.25u11(down) + 1.14u21(down) = u

12(down, up) + u

22(down, up)

1.06u11(down) + 1.12u21(down) = u

12(down, down) + u

22(down, down)

cioe, qualunque siano le realizzazione delle v.a. 1e 2, quello che si investe nel decimoanno deve essere uguale al capitale disponibile nel decimo anno. Anche qui, possiamo

riscrivere i vincoli di secondo stadio nel modo seguente.iI

t2 ,iui1(1) =

iI

ui2(1, 2), 1, 2.

Ultimo stadio: Anche nellultimo stadio vale un discorso analogo a quello fatto nei duestadi precedenti. Infatti, le variabili di decisione dellultimo stadio sono funzione di1, 2 e 3. La variabileu

13(1, 2, 3) rappresenta quanto denaro deve essere preso

in prestito con interesse di r% per poter avereG euro per pagare la rata di iscrizioneal college. Al contrario, la variabile u23(1, 2, 3) rappresenta lammontare che puoessere versato su un libretto di risparmio con interesse di q%, dopo aver pagato laretta diG euro per il college. Anche in questo ultimo caso, le funzioni u13(1, 2, 3) eu23(1, 2, 3) possono essere definite mediante lintroduzione di tante variabili quantesono le possibili combinazioni delle realizzazioni delle v.a. i, i = 1, 2, 3. Tali variabili

devono soddisfare i seguenti vincoli1.25u

12 (up,up) + 1.14u

22 (up,up) = G u

13(up, up,up) +u

23 (up, up, up)

1.25u12 (up, down) + 1.14u

22 (up,down) = G u

13(up, down, up) + u

23 (up, down, up)

1.25u12 (down, up) + 1.14u

22 (down,up) = G u

13(down,up, up) + u

23 (down,up, up)

1.25u12 (down,down) + 1.14u

22 (down,down) = G u

13(down,down, up) +u

23(down, down,up)

1.06u12 (up,up) + 1.12u

22 (up,up) = G u

13(up, up,down) + u

23 (up, up,down)

1.06u12 (up, down) + 1.12u

22 (up,down) = G u

13(up, down, down) +u

23(up,down, down)

1.06u12 (down, up) + 1.12u

22 (down,up) = G u

13(down,up, down) +u

23(down, up, down)

1.06u12 (down,down) + 1.12u

22 (down,down) = G u

13(down,down, down) +u

23 (down, down, down)

cioe, qualunque siano le realizzazione delle v.a. 1, 2 e 3, quello di cui si disponenel quindicesimo anno deve essere pari allimporto della rettaG, eventualmente pren-

dendo a prestito la quantita u13 oppure depositando i contanti in avanzo u23 in unlibretto di risparmio. Anche questo ultimo gruppo di vincoli possono essere riscrittisinteticamente come

iI

t3 ,iui2(1, 2) + u

13(1, 2, 3) u23(1, 2, 3) =G, 1, 2, 3.

22


24/40

Supponiamo che le tre v.a. siano indipendenti luna dalle altre, cosicche avremo

p(1, 2, 3) = p(1)p(2)p(3) = 0.125,

e, quindi, per la funzione obiettivo (da massimizzare)

f(u, ) =

1

2

3

p(1, 2, 3)(ru13(1, 2, 3) + qu23(1, 2, 3)).

Risolvendo il problema otteniamo la seguente soluzione ottima:

u10= 41479.3, u20= 13520.7

1 2 3 u1

1 u2

1 u1

2 u2

2 u1

3 u2

3

up up up 0 24799.9

up up down 83839.9 0

0 8870.3

up down up 0 1428.57

up down down

65094.6 2168.140 71428.6

0 0

down up up 0 1428.57

down up down 0 71428.6

0 0

down down up 0 0

down down down

36743.2 22368

64000 0 12160 0

2.3 Programmazione Stocastica lineare a due stadi

Consideriamo nuovamente il caso nel venditore ambulante di giornali visto nella sezioneprecedente. E piuttosto facile ravvisare nel problema del venditore un problema di pro-grammazione stocastica a due stadi con una sola v.a. (la domanda D di giornali).

x IR primo stadio: decisione sul numero di giornali da acquistareD osservazione: diventa noto il numero di giornali venduti

u1IR2 secondo stadio: decisioni di ricorsione

il vettore delle decisioni di ricorsione e composto di due elementi e precisamente

u11giornali venduti al semaforo = min{x, D}eu12giornali rivenduti alleditore = max{0, x D}.

Riassumendo, il venditore deve decidere here-and-now quanti giornali x IR acquistaredalleditore non sapendo quanto varra la domanda D nella mattinata. Tuttavia, quale chesia la realizzazione della v.a. D, egli reagira allosservazione della v.a. con una decisionedi secondo stadio o funzione di ricorsione u1(D) : IR2 essendo (u1(D))1 il numero digiornali venduti al semaforo e (u1(D))2 il numero di giornali rivenduti alleditore.Piu on generale, in un modello stocastico a due stadi si indica con

- xIRn1 il vettore delle decisioni di primo stadio;- la v.a. la cui realizzazione fa da margine tra primo e secondo stadio;- y()IRn2 il vettore delle decisioni di secondo stadio.

23


25/40

Il problema e dunque quello di risolvere

minx,y()

IE [f(x, y())],

potendo f(x, y()) essere una generica funzione (non lineare) e a valori sullo spazio estesoIR. Poniamoci ora in un contesto lineare. In questo assetto alla decisione di primo stadio xcorrisponde un costo linearecTx e dei vincoli lineari in forma standard Ax = b, x0. Allosteso modo, alla decisione di secondo stadio y () corrispondera un costo lineare q()Ty()

e dei vincoli lineari W()y() = h() T()x, y()0. Il problema e dunque

min cTx + IE[q()Ty()]

Ax= b, x0W()y() = h() T()x q.c.y()0 q.c.

(6)

ove le matriciW() e T() sono dette, rispettivamente,matrice di ricorsionee matrice dellatecnologia. Se la matriceWnon dipende dalla v.a. si parla di problema con ricorsione

fissa.Notiamo che i vincoli di secondo stadio dipendono dalla realizzazione della v.a. . Nelseguito supporremo che tali vincoli siano soddisfatti q.c. ovvero quasi certamentecioe chesiano soddisfatti per ogni tranne che al piu per ogniA con P(A) = 0 (ovveroAinsieme con probabilita nulla).Se pensiamo ad x e come parametri, ovvero ci poniamo nel secondo stadio quando ladecisione iniziale e stata presa e la v.a. si e realizzata, il problema che ci troviamo adaffrontare e il seguente:

min q()Ty

W()y= h() T()xy0.

Sia ora Q(x, ) = inf{q()Ty : W()y = h()T()x, y 0} eQ(x) = IE [Q(x, )].Definiamoproblema proiettatoil seguente

min cTx + Q(x)Ax= b, x0

ove, in pratica, e stata eliminata la dipendenza esplicita dalla v.a. . Abbiamo ricorsionerelativamente completaquandoQ(x) assume valori finiti per ogni xIRn1 tale che Ax = bex0. Diciamo, invece, che si haricorsione completaquandoQ(x) assume valori finiti perogni xIRn1 .

2.4 Esempi di modelli stocastici lineari a due stadi

2.4.1 Il problema dellazienda agricola

Una azienda agricola europea e specializzata nella coltivazione di grano, frumento e barba-bietole da zucchero e nellallevamento di mucche da latte. In totale lazienda possiede 500acri di terra che possono essere utilizzati per i diversi tipi di coltivazione. E noto che ognianno sono necessari per lallevamento del bestiame almeno 200 Ton. di farina e 240 Ton. difrumento. Naturalmente lazienda puo fare fronte a queste necessita o con il proprio raccolto

24


26/40

oppure acquistando da un grossista della zona. La produzione agricola dellazienda oltre aservire per lallevamento del bestiame puo essere venduta sul mercato ad un prezzo di 170euro per una Ton. di farina e 150 euro per una Ton. di frumento. I prezzi di acquisto difarina e frumento dal grossista sono maggiorati del 40% per via dei costi di trasporto chequestultimo deve sostenere. Per quanto riguarda la barbabietola, il prezzo di vendita e di36 euro/Ton; tuttavia, la commissione europea ha imposto allazienda una quota di pro-duzione per le barbabietole di 6000 Ton. lanno. La quantit a di barbabietola eventualmenteprodotta oltre questa quota potra essere venduta ad un prezzo ribassato e precisamente a

10 euro/Ton.Basandosi sulla propria esperienza passata, lazienda agricola sa che ogni acro di terra colti-vato a frumento, grano o barbabietola frutta rispettivamente 2.5, 3 e 20 Ton. Per finire,per ogni acro di terra lazienda deve sostenere dei costi di semina che sono di 150 euro, 230euro e 260 euro rispettivamente per grano, frumento e barbabietole. La tabella che segueriassume i dati fin qui esposti:

Grano Frumento Barbabietole

Raccolto (Ton./acri) 2.5 3 20

Costo di semina (euro/acri) 150 230 260

Prezzo di vendita (euro/Ton.) 170 150 36 sotto 6000 Ton.

10 sopra 6000 Ton.

Prezzo di acquisto (euro/Ton.) 238 210

Richieste min. (Ton.) 200 240

Per scegliere le migliore strategia di semina, lazienda dovrebbe ricorrere al seguente modellolineare.Siano:

x1 = acri di terra piantati a grano;

x2 = acri di terra piantati a frumento;

x3 = acri di terra piantati a barbabietole;

w1 = ton. di grano venduto;y1 = ton. di grano acquistato;

w2 = ton. di frumento venduto;

y2 = ton. di frumento acquistato;

w3 = ton. di barbabietole vendute a prezzo pieno;

w4 = ton. di barbabietole vendute a prezzo ribassato;

25


27/40

Il problema da risolvere e il seguente:

min 150x1+ 230x2+ 260x3+ 238y1 170w1++210y2 150w2 36w3 10w4

c.v. x1+ x2+ x35002.5x1+ y1 w12003x2+ y2 w224020x3 w3 w40w36000xi, yj , wh0 i= 1, 2, 3, j = 1, 2, h= 1, 2, 3, 4.

Risolvendo il problema precedente otteniamo la seguente soluzione ottima

Coltivazione Grano Frumento Barbabietole

xi 120 80 300

Raccolto (Ton.) 300 240 6000

wi 100 6000 (w4 = 0)

yi Profitto complessivo: 118600 euro

Lazienda agricola pur soddisfatta da questa soluzione ottima sa perfettamente che di annoin anno e a parita di seminato, i raccolti possono variare sensibilmente. in particolare none usuale avere stagioni con raccolti che sono superiori o inferiori del 20% rispetto alle stimeusate nel problema precedente. Piu precisamente, nel caso di una stagione particolarmentebuona ogni acro seminato a grano, frumento e barbabietole fruttera, rispettivamente, 3, 3.6e 24 Ton. di raccolto. Vice versa, nel caso di una stagione sotto la media ogni acro seminatoa grano, frumento e barbabietole fruttera, rispettivamente, 2, 2.4 e 16 Ton. di raccolto.Possiamo a questo punto risolvere due ulteriori problemi di ottimizzazione corrispondentiagli scenari di stagione sopra e sotto la media e ottenere le seguenti soluzioni ottime:

stagione sopra la media: raccolto + 20%


xi 183.33 66.67 250

Raccolto (Ton.) 550 240 6000

wi 350 6000 (w4 = 0)

yi

Profitto complessivo: 167667 euro

26


28/40

stagione sotto la media: raccolto - 20%


xi 100 25 375

Raccolto (Ton.) 200 60 6000

wi 6000 (w4 = 0)

yi 180Profitto complessivo: 59950 euro

Ragionando sul problema in esame e facile convincersi del fatto che la decisione sulle quantitadi terra da seminare con le differenti colture (xi, i = 1, 2, 3) deve essere presa prima diconoscere lesito della stagione (se nella norma, sopra la media o sotto la media). Al contrariole quantita da vendere e comprare dei differenti prodotti (yi, i = 1, 2 e wj , j = 1, 2, 3, 4)dipendono dal raccolto.Supponiamo di assegnare a ciascuno dei tre scenari disponibili (sotto la media, in media esopra la media) un indice s = 1, 2, 3 e definire le variabili wjs, j = 1, 2, 3, 4 e yis, i = 1, 2dove, per esempio, w32 rappresenta la quantita di barbabietole vendute a prezzo pieno nelcaso di un raccolto nella media.Se ipotiziamo che ls-esimo scenario abbia probabilita ps = 1/3 con3s=1ps = 1 allorapossiamo scrivere il seguente problema

min 150x1+ 230x2+ 260x3+

+13 (238y11 170w11+ 210y21 150w21 36w31 10w41)+13 (238y12 170w12+ 210y22 150w22 36w32 10w42)+13 (238y13 170w13+ 210y23 150w23 36w33 10w43)

c.v. x1+ x2+ x35002x1+ y11 w112002.4x2+ y21 w2124016x3

w31

w41

0

w3160002.5x1+ y12 w122003x2+ y22 w2224020x3 w32 w420w3260003x1+ y13 w132003.6x2+ y23 w2324024x3 w33 w430w336000xi, yjs, whs

0 i= 1, 2, 3, j = 1, 2, h= 1, 2, 3, 4, s= 1, 2, 3.

Risolvendo questo problema otteniamo la soluzione seguente:

27


29/40


30/40

Inoltre, data la limitata disponibilita di corsi dacqua utilizzabili per produrre elettricita, uneventuale nuovo impianto idroelettrico non potra avere una capacita superiore a 5 GW.Oltre allinvestimento iniziale per la costruzione, ciascun tipo di impianto comporta anchedei costi di esercizio (espressi in euro/KWh) come riportato nella tabella seguente in cui siriporta anche il costo per lacquisto di un KWh di energia elettrica da un fornitore estero.

Impianto costo di eser. euro/KWh

Gas G

Carbone C

Nucleare 0.0140

Idrico 0.0040

Acquisto 0.1500

I costi per la produzione di un KWh di energia elettrica con impianto a gas e a carbone sonov.a. discrete indipendenti con le seguenti distribuzioni:

G P(G) C P(C)

0.0310 0.1 0.0170 0.1

0.0330 0.2 0.0210 0.20.0390 0.4 0.0240 0.4

0.0450 0.2 0.0290 0.2

0.0490 0.1 0.0310 0.1

Per pianificare al meglio i propri investimenti, lente si basa sulla conoscenza dellandamentodella richiesta di potenza elettrica per il primo anno. In particolare, sono stati individuati5 blocchi di consumo e per ciascuno di essi e nota la durata in ore (nellanno) e la potenzarichiesta (dj in GW) come riportato nella tabella che segue

Blocco j dj (GW) Durata (ore)

# 1 10.0 490# 2 8.4 730

# 3 6.7 2190

# 4 5.4 3260

# 5 4.3 2090

Cos, e noto che, nel corso del primo anno, ci sara una richiesta di 10 GW di potenzaper un ammontare complessivo di 490 ore. La richiesta sara di 8.4 GW per 730 ore, 6.7GW per 2190 e cos via. Basandosi sui dati in suo possesso e grazie a delle approfonditericerche di mercato, lente ha stabilito che nei prossimi 15 anni (periodo di pianificazionedellinvestimento), si potranno verificare i seguenti trend di incremento/decremento dellerichieste di potenza elettrica:

29


31/40

R P(R)

-0.01 0.2

0.01 0.2

0.03 0.2

0.05 0.2

0.07 0.2

E inoltre noto che le tre v.a. G, Ce Rsono indipendenti tra di loro. Quindi, se indichiamocon G, C e R, rispettivamente, lo spazio di tutti i possibili eventi associati alle tre v.a.G, C e R, avremo che = G C R e lo spazio degli scenari possibili che sonocomplessivamente pari a|GC R| = 555 = 125. Pertanto, ogni scenario = (G, C, R) ha una probabilita data dal prodotto delle probabilita dei singolieventi cioe: P() = P(G)P(C)P(R).Indichiamo con:

- xi, i = 1, 2, 3, 4, la capacita (in GW) dei nuovi impianti, rispettivamente, a Gas, aCarbone, Nucleare e Idroelettrico.

- ci, i = 1, 2, 3, 4, i costi di costruzione (in milioni di euro/GW) associati ai 4 differentitipi di impianto.

- yijk (), i = 1, . . . , 5, j = 1, . . . , 5 e k = 1, . . . , 5, la frazione di capacita elettrica(in GW) utilizzata per produrre elettricita con impianto di tipo i, per il blocco dirichiesta j nellanno k. Notiamo che, quando i = 5, y5jk indichera la quantita dielettricita acquistata da un fornitore estero per soddisfare la domanda nel blocco jdellannok . Queste variabili sono, in realta funzioni della v.a. .

- q1(), q2(), q3, q4, q5, i costi di esercizio (in euro/KWh), rispettivamente, di impianti aGas, Carbone, Nucleare, Idroelettrico e per lacquisto da un fornitore estero. Notiamoche i primi due costi dipendono dalle realizzazioni della v.a. .

- hj , j = 1, 2, 3, 4, 5, la durata (in ore) di ciascun blocco di consumo.

- Djk (),j = 1, . . . , 5 ek = 1, . . . , 15, la potenza richiesta (in GW) nel blocco j dellannok. In particolare, vale la relazione Djk () = dj ( 1 + (k

1)R), per ognij = 1, . . . , 5 e

k= 1, . . . , 15, dovedj indica la richiesta nel primo anno per i vari blocchi di domanda.Le informazioni sulle quantita Djk () possono essere cos riassunte:

j R Dj1() Dj2() ... Dj14() Dj15()

1 -0.1 10 9.9 ... 8.7 8.6

1 0.1 10 10.1 ... 11.3 11.4

1 0.3 10 10.3 ... 13.9 14.2

1 0.5 10 10.5 ... 16.5 17.0

1 0.7 10 10.7 ... 19.1 19.8

......

......

......

5 -0.1 4.3 4.257 ... 3.741 3.6985 0.1 4.3 4.343 ... 4.859 4.902

5 0.3 4.3 4.429 ... 5.977 6.106

5 0.5 4.3 4.515 ... 7.095 7.31

5 0.7 4.3 4.601 ... 8.213 8.514

30


32/40

Riassumendo, otteniamo il seguente problema di programmazione stocastica lineare a duestadi.

minx,y

cTx + IE

5

i=1

5j=1

15k=1

qi()hj yijk ()

cTx10000x45.0

x0yijk ()xi, j = 1, . . . , 5, k= 1, . . . , 15, i= 1, . . . , 4,5

i=1

yijk ()Djk (), j = 1, . . . , 5, k= 1, . . . , 15

yijk ()0, j = 1, . . . , 5, k= 1, . . . , 15, i= 1, . . . , 5.Risolvendo il problema, otteniamo il seguente piano di investimenti, in termini di capacitainstallate (variabilixi, i = 1, . . . , 4):

Impianto i Capacita xi

Gas 1 3.366 GW

Carbone 2 3.953 GWNucleare 3 4.313 GW

Idrico 4 5.000 GW

Il costo atteso complessivo del piano di investimento allottimo e pari a 15828.81856 milionidi euro. Il piano di investimenti ottimo prevede, tra laltro, che, date le installazioni ottimedi capacita x come riportate nella tabella che precede, un trend di crescita della domandadel 7% e i costi operativi delle centrali a gas e carbone rispettivamente di 3 .9 e 2.4 eurocentper KWh, le potenze erogate dai singoli impianti nel 15 anno siano pari a ( yij15() peri= 1, . . . , 5,j = 1, . . . , 5 e dove = (G, C, R) conG= 0.039,C= 0.024 eR= 0.07).

Blocco di domandaImpianto

1 2 3 4 5

Gas 3.366 3.366 0.469 0 0

Carbone 3.953 3.953 3.953 1.757 0

Nucleare 4.313 4.313 4.313 4.313 3.815

Idrico 5 5 5 5 5

Fornitore 3.868 0.588 0 0 0

2.5 Programmazione stocastica lineare a due stadi con

ricorsione fissa

Consideriamo nuovamente il problema (6) ove W() = W ovvero

min cTx + IE[q()Ty()]

Ax= b, x0W y() = h() T()x q.c.y()0 q.c.

31


33/40

oppure, equivalentemente, il problema proiettato

min cTx + IE[Q(x, )]

Ax= b, x0 (7)

dove

Q(x, ) = inf qTy

W y= h

T x

y0.(8)

SiaQ(x) = IE[Q(x, )] la cos detta funzione di ricorsionemediante la quale possiamoscrivere, come gia visto, il problema proiettato seguente

min cTx + Q(x)Ax= b, x0. (9)

2.5.1 Esempio: il problema del venditore di giornali

Consideriamo nuovamente lesempio visto in sezione 2.1.4. Come gia abbiamo visto, ilproblema del venditore di giornali puo essere formulato come problema di programmazionestocastica lineare a due stadi con risorsione fissa. La situazione del venditore e infatti la

seguente

xIR primo stadio: decisione sul numero di giornali da acquistareD osservazione: diventa noto il numero di giornali venduti

yIR2 secondo stadio: decisioni di ricorsione

In particolare, una volta acquistati glixgiornali dalleditore e avvenuta la realizzazione dellav.a. D, il venditore adottera le decisioni di secondo stadio ovvero decidera quanti giornalivendere al semaforo e quanti rivenderne alleditore a fine mattinata. Il problema e quindi

minx cTx + Q(x)

x

0,

conQ(x) = IED[Q(x, D)] eQ(x, D) = inf

ysy1 ry2

y1+ y2 = x

y1Dy1, y20.

La regione ammissibile del problema primale, vale a dire linsieme Y(h T x), e sempre nonvuota e anzi il problema primale ammette sempre soluzione ottima (qualunque sia il valoredi x e D) pari a

y1

y2

=

xD x

sexD

D

x D

sex > D

32


34/40

Ricordando che, nellesempio in esame T= (1, 0)T, abbiamo che il subdifferenzialeQ(x, D)contiene il subgradientes sesx=sy1 ry2 er serx D(s r) =sy1 ry2 oentrambi serx D(s r) =sx. Percui, se vogliamo stabilire come e fatto il subdifferen-zialeQ(x, D) quandox = D = 30 e s = 1.8,c = 1.6 er = 0.8, allora dobbiamo confrontareil valoreQ(30, 30) =30scon i valori allottimo della funzione obiettivo duale ovvero30se30r 30(s r) =30s. Pertanto

Q(30, 30) =conv{s, r},

ovvero il subdifferenziale contiene i subgradientis er e tutte le loro combinazioniconvesse.Ovviamente, potranno esistere valori di x e D per cui la funzione Q(x, D) e differenziabileovvero per cui il subdifferenziale si riduce ad un singleton contenente come suo unico ele-mento il gradienteQ(x, D). Per esempio, se consideriamo per D = 30 il punto x = 40,abbiamo cheQ(40, 30) =30s 10r=40r 30(s r), pertanto,

Q(40, 30) ={Q(40, 30)} ={r}.

2.6 Indicatori di validita e attendibilita della Program-

mazione Stocastica

Come gia abbiamo avuto modo di osservare in precedenza, risolvere un problema di pro-grammazione stocastica e, in taluni casi, equivalente alla soluzione di un problema di grandidimensioni cioe con un elevato numero di variabili e/o di vincoli. Pertanto, in generale,determinare la soluzione di un problema di programmazione stocastica lineare e molto cos-toso. Ha quindi senso chiedersi quando e quanto sia conveniente abbandonare il problemastocastico e risolvere, invece, un problema piu semplice. In particolare, e lecito chiedersiin che misura approcci piu semplici al problema, come per esempio quello che prevede disostituire alla v.a. il suo valor medio, forniscano soluzioni che si discostano dallottimo ofine a che punto questi approcci alternativi non siano completamente inaccurati.Una risposta a queste domande puo essere fornita da due importanti indicatori di bont adellapproccio stocastico che sono:

1. lEVPI (Expected Value of Perfect Information) ovvero il valore atteso in condizionidi informazione completa e,

2. lVSS(Value of Stochastic Solution) ovvero il valore della soluzione stocastica.

Al fine di definire chiaramente questi due importanti indicatori, introduciamo brevementealcune definizioni che ci faranno comodo nel seguito.Sia una v.a. discreta ovvero che puo avere solo un numero finito N di realizzazioni1, . . . , N. Sia f(x(i), i) il valore ottimo del problema di programmazione stocasticaquando si fissa la v.a. al valore i, i = 1, . . . , N . Percui, data una realizzazione idella v.a. , associamo ad essa il valore allottimo del corrispondente problema diprogrammazione matematica f(x(i), i). f(x(), ) e pertanto una v.a. composta percui e possibile definire il valore atteso. Infatti, definiamo soluzionewait-and-see

W S= IE [f(x

(), )],

il valore atteso della v.a. f(x(), ). Definiamo, invece, soluzione here-and-now come ilvalore della soluzione del problema di programmazione stocastica

HN= minx

IE[f(x, )].

33


35/40

A questo punto, definiamo lEVPI(valore atteso in condizioni di informazione completa)come

E V P I =H N W S.Nel caso dellesempio del venditore di giornali, abbiamo che, come risulta dalla tebella chesegue, W S=10.57142

i pi Di x

(Di) f(x

(Di), Di)1 1/7 30 30 -6

2 2/7 40 40 -8

3 2/7 50 50 -10

4 1/7 60 60 -12

5 1/7 100 100 -20

Risulta, inoltre, x = 40,

Q(x) =1.8D1 0.8(x D1)

7 6 1.8x

7

e quindi HN = 1.6x

+ Q(x

) =6.57142. Otteniamo cos EV P I = 4. Questo valore epari alla quantita di euro che il venditore sarebbe disposto a pagare ogni mattina pur disapere quanti giornali potra vendere al semaforo.

Quando ci si trova a dover risolvere un problema di ottimizzazione con incertezza, moltospesso si ritiene di poter ottenere una buona approssimazione della soluzione ottima sem-plicemente risolvendo il problema

EV= minx

f(x,),

dove si e sostituita la v.a. con il suo valore atteso = IE []. La soluzione di questoproblema e nota come soluzioneEV(expected value) ovvero soluzione di valor medio. Lindi-catoreVSS e quello che ci dice quanto la soluzioneEV sia lontana dallessere ottima per ilproblema di programmazione stocastica. In particolare, una volta nota la soluzione ottima

x() del problema EV, definiamo

EE V =IE[f(x(), )] = cTx() + Q(x())

ovvero il valore atteso quando si usa la soluzione di valor medio. Il VSS e definito come

V SS= EEV HN.Di nuovo, nel caso del venditore di giornali, abbiamo chex(D) = 370/7 e EV =10.57142.Come risulta dalla tabella che segue abbiamo

i pi Di cx(D) + Q(x(D), Di) f(x(D), Di)

1 1/7 30 1.6x(D)

1.8D1

0.8(x(D)

D1) 12.28571

2 2/7 40 1.6x(D) 1.8D2 0.8(x(D) D2) 2.285713 2/7 50 1.6x(D) 1.8D3 0.8(x(D) D3) -7.714294 1/7 60 1.6x(D) 1.8x(D) -10.571435 1/7 100 1.6x(D) 1.8x(D) -10.57143

34


36/40

EE V = IED[f(x(D), D)] =2.81634 e quindi V SS= 3.75508 che ci dice esattamente di

quanto la soluzione del problemaEVsi discosta dalla soluzione HN.

Consideriamo ora lesempio dellazienda agricola. Come gia abbiamo visto, in questo casoHN =108390. Calcoliamo ora WS. Nel caso in cui = 1 (stagione sotto la media),risulta z(x(1), 1) =59950; quando = 2 (stagione nella media), z(x(2), 2) =118600; quando = 3 (stagione sopra la media), z(x(3), 3) =167667; cosiccheW S= z(x(1), 1)/3 + z(x(2), 2)/3 + z(x(3), 3)/3 =115405.56. Quindi otteniamo

E V P I =H N W S= 7015.6il che significa che lazienda sarebbe disposta a pagare 7015.6 euro ogni anno per poterconoscere quale sara landamento della stagione.Calcoliamo ora lEV dellesempio dellazienda agricola che otteniamo semplicemente risol-vendo il problema in cui si e fissata la v.a. al suo valor medio il che, ovviamente, equivale a ri-solvere il problema nel caso di stagione nella media per cui otteniamox() = (120, 80, 300)T.Possiamo ora calcolare lEEVche risulta E EV =107240 per cui otteniamo

V SS= EEV HN= 1150.

2.7 Richiami sulle funzioni convesse

Indichiamo con IR e IR gli insiemi estesi IR {+}e IR {, +}, rispettivamente. Siaf :S IR conSIRn. Linsieme

{(x, ) :xS, IR, f(x)}

e detto epigrafo di fed e indicato epi f. Diciamo chef e una funzione convessa su S seepi f e un sottoinsieme convesso di IRn+1. Il dominio effettivo della funzione f su S e laproiezione su IRn dellepigrafo di f ovvero

dom f={x:, (x, )epi f}={x: f(x)< +}.

Notiamo che data una funzione f su Sconvessa, e sempre possibile ottenere una funzionef definita su IRn e ancora convessa. Per fare questo e sufficiente considerare la funzione

f(x) =

f(x) sexS,+ sexS.

Dal momento che le funzioni che stiamo calcolando hanno valori nello spazio esteso IR, enecessario fornire delle regole che specifichino il risultato delle operazioni aritmetiche fonda-mentali quando sono coinvolti i simboli + o. In particolare, adotteremo le seguentiregole:

1. + = + =per ogni< ;2. = + =per ogni


37/40

7. inf= +, sup =.Una funzione convessa f e detta propriase f(x)< +per almeno un x e f(x)>perogni x. Una funzione convessa che non e propria e detta impropria. In particolare se f euna funzione convessa finita definita sullinsieme convesso C, la funzionef definita su tuttoIRn

f(x) = f(x) sexC,+

sex

C.

e una funzione convessa e propria.

Proposizione 2.7.1 Siaf :C IR, doveC IRn. f e una funzione convessa suC se esolo se

1. C e un insieme convesso;

2. comunque sceltix, yC risulta

f((1 )x + y)(1 )f(x) + f(y), 0< < 1.

Proposizione 2.7.2 Siaf : IRn IR. f e una funzione convessa se e solo se comunquepresi due punti x, y IR

n

per cui esistono due scalari , < + tali che f(x) < ef(y)< allora

f((1 )x+ y)< (1 )+ , 0< < 1.

Proposizione 2.7.3 (Disuguaglianza di Jensen) Siaf : IRn IR. Alloraf e convessase e solo se

f(1x1+ + mxm)1f(x1) + + mf(xm),

comunque scelti i vettori xi IRn, i = 1, . . . , m, dove gli scalari i sono tali che i 0,i= 1, . . . , me

mi=1

i = 1.

2.8 Definizioni

DatoSIRn, diciamo cheS e uninsieme convesso quando, comunque presi due puntix, yS, risulta, per ogni scalare [0, 1]

x + (1 )yS.

Sia S

IRn un insieme convesso. Diciamo che la funzionef : IRn

IR e convessa su

Squando, comunque presi due punti x, yS, risulta, per ogni scalare [0, 1]f(x + (1 )y)f(x) + (1 )f(y).

36


38/40

Data una funzione f : IRn IR convessa sulinsieme convesso X e un punto xo X,diciamo che un vettoreIRn e un subgradiente di f(x) inxo quando:

f(x)f(xo) + T(x xo), xX.

Data una funzione f : IRn IR convessa sulinsieme convesso X e un punto xo X,definiamo il subdifferenziale di f(x) inxo come segue:

f(xo) = conv{IRn :f(x)f(xo) + T(x xo), xX}.

Una funzionef(x) si dice positivamente omogeneaquando, comunque preso uno scalare0, risultaf(x) =f(x).

Sia S IRn un insieme convesso. Definiamo funzione di supportodellinsieme S lafunzioneS : IR

n IR

S(x) = supyS

xTy.

37


39/40

Indice

1 Programmazione Multiobiettivo 11.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Ottimalita secondo Pareto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2.1 Esercizio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Condizioni di Ottimalita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.1 Condizioni di Fritz-John . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3.2 Condizioni di Karush-Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . 7

1.4 Metodi di Soluzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.4.1 Metodi Senza Preferenze . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4.2 Metodi a Posteriori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Programmazione con Incertezza 132.1 Nozioni preliminari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.1 Formulazione deterministica . . . . . . . . . . . . . . . . . . . . . . . . 142.1.2 Osservazione e ottimizzazione . . . . . . . . . . . . . . . . . . . . . . . 142.1.3 Ottimizzazione e osservazione . . . . . . . . . . . . . . . . . . . . . . . 142.1.4 Esempio: il problema del venditore di giornali . . . . . . . . . . . . . . 15

2.2 Fondamenti di Programmazione Stocastica . . . . . . . . . . . . . . . . . . . 192.2.1 Esempio: financial planning and control . . . . . . . . . . . . . . . . . 20

2.3 Programmazione Stocastica lineare a due stadi . . . . . . . . . . . . . . . . . 232.4 Esempi di modelli stocastici lineari a due stadi . . . . . . . . . . . . . . . . . 24

2.4.1 Il problema dellazienda agricola . . . . . . . . . . . . . . . . . . . . . 24

2.4.2 Gestione degli investimenti per un impianto di distribuzione elettrica . 282.5 Programmazione stocastica lineare a due stadi con ricorsione fissa . . . . . . 31

2.5.1 Esempio: il problema del venditore di giornali . . . . . . . . . . . . . . 322.6 Indicatori di validita e attendibilita della Programmazione Stocastica . . . . . 332.7 Richiami sulle funzioni convesse . . . . . . . . . . . . . . . . . . . . . . . . . . 352.8 Definizioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

38


40/40

Bibliografia

[1] M.S. Bazaraa, H.D. Sherali, C.M. Shetty, Nonlinear Programming: Theory andAlgorithms, Wiley, New York, 1979.

[2] J.R. Birge, F. Louveaux,Introduction to Stochastic Programming, Springer Series inOperations Research and Financial Engineering, Springer, Berlin, 1997.

[3] K. Miettinen, Nonlinear Multiobjective Optimization, Kluwer Academic Publishers,Boston, 1999.

[4] V. Pareto, Cours deconomie Politique, Rouge, Lausanne, Switzerland, 1896.

39

SistemiComplessi.pdf

Documents

Transcript of SistemiComplessi.pdf