Tesi, Sviluppo di principi di allocazione della merce all'interno di magazzini automatizzati mediante modelli Multi-Obiettivo

R

n

R : spazio delle variabili decisionali

F n

R : regione ammissibile delle variabili decisionali

⊂ F,

k k

: x z = immagine della regione ammissibile in R

Z = = {z R E ∈ ƒ(x)}:

ƒ(F) ∈

k : vettore degli obiettivi (il vettore è ammissibile quando z Z)

z R ∈

∈

id Utopia Point),

z : vettore ideale degli obiettivi (anche detto definito come

il vettore di componenti:

iid

z = min (x) 1 ≤ i ≤ k

ƒ i

F

con x ∈ 65

Un problema matematico di ottimizzazione può essere definito come la

minimizzazione o la massimizzazione di una funzione a valori reali su un

insieme specificato. L’importanza di questo modello matematico deriva dal fatto

che molti problemi reali sono affrontati facendovi ricorso.

Tuttavia quasi ogni problema reale di ottimizzazione è caratterizzato dalla

presenza contemporanea di più obiettivi, cioè funzioni a valori reali da

massimizzare e/o minimizzare, spesso in contrasto fra loro.

Un problema di ottimizzazione Multi-Obiettivo può essere rappresentato come

segue [8]: T

min (ƒ (x) (x) … (x)) con k ≥ 2

ƒ ƒ

1 2 k

F

x ∈ (x) simultaneamente.

L’obiettivo è minimizzare tutte le f.o. ƒ

i

k

In assenza di conflitti fra le f.o. una soluzione al problema è ottenibile

id

k

minimizzando indipendentemente le funzioni, ottenendo il vettore z (soluzione

banale). In questo modo non sarebbe necessario applicare nessuna tecnica

specifica di soluzione. iid Z.

Siccome le f.o. sono in conflitto fra loro si suppone che z ∉ 1 2 k

Definizione 3.2.1 – Relazione di dominanza: dati due vettori z , z R , si dice

∈

1 2 1 2

che z domina z secondo Pareto (z ≤ z ) quando risulta:

P

1 2

≤ z per ogni i = 1, …, k

z i i

1 2

< z per almeno un indice j {1, …, k}

z ∈

j j

La relazione binaria ≤ è un ordinamento parziale (non riflessivo) nello spazio

P

delle k-uple di numeri reali. Sfruttando questa relazione possiamo dare la

definizione di ottimalità secondo Pareto.

66 Legenda:

Vettori dominati da A ma non da B

Vettori dominati da B ma non da A

Vettori dominati sia da A sia da B

Vettori dominati ma non da A ne da B

Vettori non dominati

Vettore non ammissibile

Vettore ideale

Figura 2 - Relazione di dominanza F

Definizione 3.2.2 – Ottimo di Pareto: un vettore delle variabili decisionali x* ∈

F

è un ottimo di Pareto se non esiste un altro vettore x tale che:

∈

≤

ƒ(x) ƒ(x*)

P

Ossia quando risulta:

(x) ≤ (x*) per ogni i = 1, …, k

ƒ ƒ

i i

(x) < (x*) per almeno un indice j {1, …, k}

ƒ ∈

ƒ

i i

Corrispondentemente si dirà che un vettore di obiettivi z* Z è ottimo secondo

∈

Pareto quando non esiste un altro vettore z Z tale per cui:

∈

z ≤ z*

P

Quindi se ci troviamo in un punto ottimo secondo Pareto e vogliamo

ulteriormente diminuire il valore di una o più f.o. dobbiamo essere disposti ad

accettare un conseguente aumento in alcune (o tutte) le rimanenti funzioni del

problema. In tal senso possiamo affermare che, nello spazio degli obiettivi, gli

67

ottimi di Pareto sono punti di equilibrio che si trovano sulla frontiera

dell’insieme Z.

Definizione 3.2.3 – Frontiera efficiente di Pareto: si definisce frontiera

efficiente di Pareto l’insieme degli ottimi di Pareto del problema Multi-Obiettivo.

Definita anche come l’immagine, nello spazio degli obiettivi, dell’insieme degli

ottimi di Pareto. Figura 3 - Frontiera di Pareto

Figura 4 - Frontiera di Pareto

68

La definizione 3.2.2 (ottimo di Pareto) è ovviamente una definizione di ottimo

globale date che si richiede la validità della proprietà su tutto l’insieme

ammissibile del problema Multi-Obiettivo. È quindi possibile dare una

definizione di ottimo locale secondo Pareto.

Definizione 3.2.4 – Ottimo locale di Pareto: un vettore delle variabili decisionali

F

x* è un ottimo locale di Pareto se esiste un numero δ > 0 tale che x* è

∈ F B

ottimo secondo Pareto in (x*, δ).

∩

Ogni ottimo globale è anche un ottimo locale di Pareto: il viceversa è vero solo

se sono verificate alcune ipotesi sulla struttura del problema di ottimizzazione.

Figura 5 - Ottimi globali e locali di Pareto

Le definizioni di ottimo globale e locale secondo Pareto possono essere

indebolite per ottenere la definizione di ottimo debole secondo Pareto.

Definizione 3.2.5 – Ottimo debole di Pareto: un vettore delle variabili

F F

decisionali x* è un ottimo debole di Pareto se non esiste un punto x tale

∈ ∈

che: <

ƒ(x) ƒ(x*)

L’insieme degli ottimi di Pareto è contenuto nell’insieme degli ottimi deboli di

Pareto (ma non viceversa). 69

3.3. Metodi risolutivi

Nel corso degli anni i ricercatori hanno sviluppato diverse metodologie utili a

risolvere problemi di ottimizzazione Multi-Obiettivo, sia che si impieghi un

approccio tradizionale sia che si preferisca l’approccio di Pareto.

Matematicamente parlando, nella maggior parte dei casi, il problema Multi-

Obiettivo si considera risolto nel momento in cui è stato individuato l’insieme dei

punti ottimi di Pareto: tuttavia, non sempre ci si può accontentare semplicemente

di aver determinato questo insieme di soluzioni.

Alcune volte, infatti, è necessario ordinare tutte le soluzioni trovate e quindi

selezionare la migliore rispetto a tale insieme. Proprio per questo motivo il ruolo

del decisore è fondamentale in quanto c’è la necessità di qualcuno che ci dica, in

base alle proprie preferenze, come ordinare l’insieme degli ottimi di Pareto del

problema. Le preferenze possono essere esplicitate a monte, a valle o durante

l’applicazione dell’algoritmo di risoluzione. In base al ruolo svolto dal decisore

nella strategia di soluzione del problema, i metodi risolutivi per la

programmazione Multi-Obiettivo sono spesso suddivisi in quattro categorie

principali [8]:

Metodi senza preferenze:

1. nei quali il decisore non ha nessun ruolo ed è

considerato soddisfacente aver trovato un qualunque ottimo di Pareto;

Metodi a posteriori:

2. nei quali si genera l’insieme di tutti gli ottimi di

Pareto e poi lo si presenta al decisore che sceglierà la soluzione a lui più

gradita;

Metodi a priori:

3. nei quali il decisore specifica le sue preferenze prima che

abbia inizio il processo risolutivo. In base alle informazioni ottenute dal

decisore viene direttamente trovata la soluzione ottima migliore, senza

dunque dover generare tutti gli ottimi di Pareto;

70

Metodi interattivi:

4. nei quali il decisore specifica le sue preferenze mano a

mano che l’algoritmo procede, guidando il processo risolutivo verso la

soluzione per lui più soddisfacente.

Al di là della distinzione appena introdotta, tutti i metodi di soluzione di un

problema di ottimizzazione Multi-Obiettivo su basano sul medesima idea di

fondo, ovvero quella di trasformare il problema originario in un problema con

una sola funzione obiettivo. La tecnica mediante la quale si ottiene il problema

mono-obiettivo a partire da un problema Multi-Obiettivo è nota come

scalarizzazione.

Saranno ora descritte le caratteristiche principali di ogni categoria di metodi

risolutivi e per ciascuna di queste saranno presentate a grandi linee le tecniche

maggiormente utilizzate. Per fare ciò ci si baserà su [8].

Nel proseguo del capitolo si farà riferimento a un problema di ottimizzazione

F

Multi-Obiettivo (P) in cui la regione ammissibile è definita da m vincoli di

disuguaglianza: (P)

min ƒ(x)

g(x) ≤ 0

Dove:

n k

: R R con k ≥ 2

à

ƒ n m

R

g : R à

Sia che g sono funzioni differenziabili con continuità.

ƒ 71

3.3.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 preferenze del

decisore.

Metodo Goal

Si cerca la soluzione che minimizza, nello spazio degli obiettivi, la

distanza tra la regione ammissibile (Z) e un qualunque punto di

ref

riferimento z Z = Il vettore di riferimento sarà costituito dai

∉ ƒ(F).

valori auspicabili per le singole funzioni obiettivo. In particolare, una

ref ref id

è z = z .

possibile scelta di z

Il problema che si ottiene è perciò il seguente:

id (P )

min || – z ||

ƒ(x) p

p

g(x) ≤ 0 indica la norma p di un vettore (con 1 ≤ p ≤ ∞).

Dove || . || p

In particolare se p = ∞, il problema (P ) è noto come problema di

p

Tchebycheff. Si supponga di conoscere il vettore ideale globale degli

) ammette sempre soluzioni.

obiettivi: sotto tali ipotesi, il problema (P

p

Valgono le seguenti proprietà (dimostrabili):

- Ogni soluzione globale del problema (P ) (con 1 ≤ p ≤ ∞) è un ottimo

p

globale di Pareto per il problema (P); ) (con 1 ≤ p ≤ ∞) è un ottimo

- Ogni soluzione globale del problema (P p

locale di Pareto per il problema (P); ) è un

- Ogni ottimo locale (globale) del problema di Tchebycheff (P ∞

ottimo locale (globale) debole di Pareto per il problema (P);

) ha almeno una soluzione che è ottima

- Il problema di Tchebycheff (P

∞

secondo Pareto. 72

3.3.2. Metodi a posteriori

I metodi appartenenti a questa classe sono anche noti come le tecniche per

generare l’insieme delle soluzioni di Pareto: si tratta quindi delle tecniche

riconducibili all’approccio di Pareto.

Infatti, siccome le preferenze del decisore sono considerate solo al termine del

processo risolutivo, quello che si fa è generare tutti i punti ottimi secondo Pareto,

per poi presentarli allo stesso decisore che sceglierà la soluzione a lui più

congeniale.

L’inconveniente principale di questa tecnica sta nel fatto che molto spesso il

processo di generazione degli ottimi di Pareto è computazionalmente oneroso.

Inoltre, potrebbe non essere semplice per il decisore scegliere una soluzione fra

gli ottimi che gli vengono presentati, in particolar modo se questi sono numerosi.

Proprio per questo motivo è molto importante la modalità con la quale sono

presentate le soluzioni al decisore.

Una tecnica risolutiva ideale dovrebbe presentare alc