Consideriamo il seguente problema di PL max cx Ax ≤ b x ≥ 0 con regione ammissibile

1 Problemi di PLI e chiusure convesse

Consideriamo il seguente problema di PL max cx Ax ≤ b x ≥ 0 con regione ammissibile

P = {x ∈ R ⁿ : Ax ≤ b, x ≥ 0}. (1)

Se si aggiungono i vincoli di interezza sulle variabili la regione ammissibile diventa

S = P ∩ Z ⁿ

dove Z rappresenta l’insieme degli interi. Il problema di PLI corrispondente ´ e il seguente

max

x ∈S cx (2)

Diamo ora la definizione di chiusura convessa di un insieme.

Definizione 1 Dato un insieme T , la chiusura convessa di T , indicata con conv(T ), ´ e il pi´ u piccolo insieme convesso contenente T .

In Figura 1 ´ e riportato un insieme T e la sua chiusura convessa. Si consideri ora

 

 

  l l l l l l l l

conv(T) T

Figura 1: Un insieme T e la sua chiusura convessa.

la chiusura convessa conv(S) di S. Si pu´ o dimostrare che, se S 6= ∅, conv(S) ´e un poliedro convesso o un troncone, cio´ e esiste una matrice A ⁰ ed un vettore b ⁰ tale che

conv(S) = {x ∈ R ⁿ : A ⁰ x ≤ b ⁰ , x ≥ 0}. (3) Si consideri ora il seguente problema di PL

max

x ∈conv(S) cx (4)

Si pu´ o dimostrare che:

• il problema (2) ammette soluzione se e solo se la ammette il problema (4);

• ogni soluzione ottima del problema (2) ´e soluzione ottima del problema (4);

• esiste almeno una soluzione ottima (di base) del problema (4) che ´e anche soluzione ottima del problema (2).

Questo vuol dire che se conoscessimo la matrice A ⁰ ed il vettore b ⁰ che definiscono conv(S), potremmo risolvere il nostro problema di PLI risolvendo il problema di PL (4). Il problema ´ e che in molti casi conv(S) non ´ e noto. Gli algoritmi di taglio visti rappresentano un tentativo di approssimare in modo sempre pi´ u preciso conv(S) attraverso l’aggiunta di tagli successivi. Citiamo anche il fatto che in alcuni casi conv(S) ´ e noto ma ´ e formato da un numero esponenziale di vincoli, il che rende inefficiente la risoluzione del problema (4).

Esempio 1 Si consideri il seguente problema di PLI, max x 1 + x 2

x 1 + 1 2 x 2 ≤ 7

4 1

2 x 1 + x 2 ≤ 7 4 x 1 , x 2 ≥ 0 interi Si ha P = {(x 1 , x ₂ ) : Ax ≤ b, x 1 , x ₂ ≥ 0}, con

A =

 1 ¹ ₂

1

2 1

 b =

 7 4 7 4

 . L’insieme S = P ∩ Z ² ´ e formato dai quattro punti

(0, 0) (0, 1) (1, 0) (1, 1) Si ha che

conv(S) = {(x 1 , x 2 ) : x 1 ≤ 1, x 2 ≤ 1, x 1 , x 2 ≥ 0}.

(vedi Figura 2). In tal caso A ⁰ =

 1 0 0 1



b ⁰ =

 1 1

 .

Si noti che indipendentemente dalla funzione obiettivo i problemi (2) e (4) han-

no sempre soluzione in questo caso. Con la funzione obiettivo x 1 + x 2 entrambi

i problemi hanno l’unica soluzione (1, 1). Se si considera invece l’obiettivo x 1 ,

si ha che il problema (2) ha soluzioni (1, 0) e (1, 1), mentre il problema (4) ha

come soluzioni l’intero segmento avente come estremi (1, 0) e (1, 1). ´ E comun-

que sempre vero che esiste almeno una soluzione del problema (4) che ´ e anche

H H H

H H H H

H H H H

H H H

H H H H

H H H H

H H H

H H A H

A A A A A A A A A A A A A A A A A A A A A A A A A A

conv(S) P

Figura 2: La chiusura convessa di S per l’esempio considerato.

soluzione del problema (2).

Se si risolve il problema con l’algoritmo di Gomory, si pu´ o vedere che il primo taglio ´ e dato dalla seguente disequazione 3x 1 + 4x 2 ≤ 7. Aggiungendo tale taglio si vede, in Figura 3, come si ottenga un’approssimazione pi´ u precisa rispetto a P di conv(S).

Dopo aver chiarito cosa sia la chiusura convessa di un insieme e l’importanza di tale chiusura per i problemi di PLI, ci concentreremo ora su una speciale classe di problemi di PLI, quelli per cui la chiusura convessa di S = P ∩ Z ⁿ coincide con P , ovvero

conv(S) = conv(P ∩ Z ⁿ ) = P. (5)

Si noti che nell’esempio precedente ci´ o non era vero. I problemi di PLI per cui

si verifica questa condizione sono importanti perch´ e sono molto pi´ u semplici da

risolvere rispetto agli altri problemi di PLI. Infatti, essendo conv(S) = P e viste

le strette relazioni tra le soluzioni dei problemi (2) e (4), possiamo risolvere tali

H H H

H H H H

H H H H

H H H

H H H H

H H H H

H H H

H H A H

A A A A A A A A A A A A A A A A A A A A A A A A A A

conv(S) P

3x1+4x2<=7

Figura 3: L’aggiunta di un taglio fornisce un’approssimazione della chiusura convessa di S migliore di P .

problemi semplicemente eliminando i vincoli di interezza sulle variabili, ovvero risolvendo il problema di PL

max x ∈P cx

Per intenderci, se si applica l’algoritmo di Gomory, ci viene subito restituita una soluzione intera senza bisogno di aggiungere tagli. Inoltre, in molti casi questi problemi hanno strutture particolari che consentono di risolverli attra- verso algoritmi specifici senza dover utilizzare l’algoritmo del simplesso oppure utilizzando questo in una forma adattata al particolare tipo di problema.

Nel seguito mostreremo casi in cui la condizione (5) ´ e soddisfatta.

2 Matrici totalmente unimodulari

Prima di approfondire ulteriormente il discorso sui problemi per cui conv(S) = P , introduciamo il concetto di matrice totalmente unimodulare.

Definizione 2 Una matrice A si dice totalmente unimodulare (TU nel seguito) se ogni sua sottomatrice quadrata ha determinante pari a 0, +1 o -1.

Si noti che una matrice TU pu´ o avere come elementi solo i valori 0, +1 e -1 visto che ogni suo elemento ´ e una particolare sottomatrice quadrata di ordine 1 × 1. Si citano di seguito alcune propriet´a delle matrici TU.

Propriet´ a 1 Se A ´ e una matrice TU si ha che 1. A ^T ´ e TU

2. [A I], dove I ´ e la matrice identica, ´ e TU

3. una matrice ottenuta duplicando righe e/o colonne di A ´ e ancora TU 4. una matrice ottenuta moltiplicando righe e/o colonne di A per -1 ´ e ancora

TU

5. una matrice ottenuta scambiando righe di A (oppure colonne di A) tra loro ´ e ancora TU

6. una matrice ottenuta da A mediante un’operazione di cardine ´ e ancora TU Ci chiediamo ora come sia possibile riconoscere una matrice TU senza dover cal- colare i determinanti di tutte le sottomatrici quadrate. Esistono alcune regole, tra cui la seguente.

Osservazione 1 Sia A una matrice i cui elementi sono tutti uguali a 0, +1 o -1 e lungo ogni colonna non vi sono pi´ u di due elementi diversi da 0. Allora A ´ e TU se e solo se l’insieme delle righe di A pu´ o essere suddiviso in due sottinsiemi Q ₁ e Q ₂ tali che se una colonna contiene due elementi diversi da 0 si ha che:

• se i due elemnti hanno lo stesso segno allora una delle due righe in cui si trovano ´ e in Q ₁ e l’altra in Q ₂ ;

• se hanno segno opposto le righe corrispondenti sono entrambe contenute in Q ₁ od entrambe in Q ₂ .

Esempio 2 Sia A la seguente matrice

A =









1 1 0 0

0 0 1 1

1 0 1 0

0 1 0 1









Prendendo Q ₁ = {1, 2} e Q 2 = {3, 4} si verifica immediatamente che la condi-

zione ´ e soddisfatta e quindi A ´ e TU.

Vale il seguente corollario.

Corollario 1 Sia A una matrice i cui elementi sono tutti uguali a 0, +1 o -1 e lungo ogni colonna non vi sono pi´ u di due elementi diversi da 0. Se nelle colonne con due elementi diversi da 0 la somma di tali elementi ´ e uguale a 0 (ovvero un elemento ´ e uguale a +1 e l’altro a -1), allora A ´ e TU.

Dimostrazione ´ E sufficiente porre

Q 1 = {tutte le righe di A} Q 2 = ∅.

Esempio 3 Sia A la seguente matrice

A =









1 1 0 0

0 −1 1 1

−1 0 0 0

0 0 0 −1









In base al corollario tale matrice ´ e TU.

Ma perch´ e sono importanti le matrici TU? La loro importanza ´ e legata a questo teorema (non dimostrato).

Teorema 1 Sia

P (b) = {x ∈ R ⁿ : Ax ≤ b, x ≥ 0}

e

S(b) = P (b) ∩ Z ⁿ ,

con b vettore di interi. Si dimostra che A ´ e TU se e solo se per ogni vettore di interi b per cui P (b) 6= ∅ si ha che

conv(S(b)) = P (b).

In altre parole questo ci dice che la soluzione di un problema di PLI con matrice dei vincoli TU e vettore dei termini noti intero pu´ o essere ottenuta semplice- mente eliminando i vincoli di interezza. Ci si pu´ o chiedere se fa differenza avere una regione ammissibile definita da vincoli di uguaglianza, ovvero se ´ e ancora vero che essendo

P (b) = {x ∈ R ⁿ : Ax = b, x ≥ 0}

con A TU, b vettore di interi e P (b) 6= ∅, si ha che

conv(S(b)) = P (b).

Possiamo notare che

P (b) = {x ∈ R ⁿ : Ax ≤ b, −Ax ≤ −b, x ≥ 0}

e quindi ricondurci al caso in cui i vincoli sono tutti di ≤. Il problema ´e che in questo modo cambiamo anche la matrice dei vincoli che diventa

 A

−A



mentre il vettore dei termini noti diventa

 b

−b

 .

Il vettore dei termini noti continua ad essere intero (b e −b sono entrambi interi).

Resta solo da verificare se essendo A TU anche la nuova matrice dei vincoli ´ e TU. Ma in base al punto 3 della Propriet´ a 1 se duplico tutte le righe di A ho ancora una matrice TU e quindi

 A A



´

e TU. Inoltre, in base al punto 4 della Propriet´ a 1 se moltiplico per -1 tutte le righe duplicate di A ho ancora una matrice TU e quindi

 A

−A



´

e TU. Quindi il caso con vincoli di uguaglianza si riconduce al caso di vincoli di

≤.

Esempio 4 Si consideri il seguente problema max x ₁ + x ₂ + x ₃ + x ₄ x 1 + x 2 = 2

−x 1 + x ₃ = 4

−x 2 + x 4 = 3

−x 3 − x 4 = 2

x ₁ , x ₂ , x ₃ , x ₄ ≥ 0 interi

Il problema di PL ottenuto eliminando i vincoli di interezza ha regione ammis- sibile

P (b) = {x ∈ R ⁿ : Ax = b, x ≥ 0}

con

A =









1 1 0 0

−1 0 1 0

0 −1 0 1

0 0 −1 −1







 e

b =







 2 4 3 2









Si pu´ o verificare attraverso il Corollario 1 che A ´ e TU. Essendo b un vettore di interi, il problema di PLI pu´ o essere risolto eliminando semplicemente i vincoli di interezza.

3 Alberi di supporto

Diamo la definizione di albero.

Definizione 3 Dato un grafo G = (V, A) con | V |= n, si dice che G ´e un albero se soddisfa le seguenti condizioni (equivalenti tra loro)

1. G ´ e privo di cicli e connesso;

2. G ´ e privo di cicli e | A |= n − 1;

3. G ´ e connesso e | A |= n − 1;

4. esiste un unico cammino che congiunge ogni coppia di nodi.

Si dimostra che vale la seguente propriet´ a.

Propriet´ a 2 Se ad un albero G aggiungo un arco si froma uno ed un solo ciclo.

Esempio 5 Il grafo G = (V, A) con

V = {a, b, c, d, e} A = {(a, b); (b, c); (c, e); (e, d)}

illustrato in Figura 4, ´ e un albero. Se aggiungo l’arco (a, e) si forma l’unico ciclo

a → b → c → e → a

Diamo ora la definizione di albero di supporto di un grafo generico.

Definizione 4 Sia dato un grafo generico G = (V, A). Si definisce albero di

supporto di G un sottografo G ⁰ = (V, A ⁰ ) di G (quindi con A ⁰ ⊆ A) che ´e un

albero.

E E E E E E

, ,

, ,

, ,

,

, XX XX XX















a

b

c

d

e

Figura 4: Un albero e l’unico ciclo che si forma aggiungendo un arco (quello tratteggiato).

Si noti che un albero di supporto di G deve contenere tutti i nodi di G e che in virt´ u del punto 2. (o del punto 3.) della Definizione 3, si dovr´ a avere

| A ⁰ |=| V | −1.

Esempio 6 Sia dato il grafo G = (V, A) con

V = {a, b, c, d} A = {(a, b); (b, c); (b, d); (a, d); (c, d)}

illustrato in Figura 5. Un albero di supporto di G ´ e il sottografo G ⁰ = (V, A ⁰ ) con

A ⁰ = {(b, c); (b, d); (a, d)}

un altro ´ e il sottografo G ⁰⁰ = (V, A ⁰⁰ ) con

A ⁰⁰ = {(a, b); (b, c); (c, d)}

I due alberi di supporto di G sono illustrati in Figura 5.

4 Problemi di flusso a costo minimo

Sia data una rete (grafo orientato e connesso) G = (V, A) come quella mostrata in Figura 6. Si consideri il seguente problema:

min P

(i,j) ∈A c ij x ij

P

j:(i,j) ∈A x ij − P

j:(j,i) ∈A x ji = b i ∀ i ∈ V x _ij ≥ 0 interi ∀ (i, j) ∈ A con b i interi e tali che P

i ∈V b i = 0. Il problema viene interpretato come segue.

Dovete inviare un flusso (di prodotti, di informazione, eccetera) attraverso la

E E E E E E ,

, ,

, ,

, , Z ,

Z Z

Z Z

Z Z

Z Z

Z Z

Z Z

Z ,

, ,

, ,

, ,

,

, E

E E E

E E

#

#

#

#

#

#

#

#

#

# 













a

b

c

d

a

b

c

d

a

b d

c

Figura 5: Un grafo G e i suoi due alberi di supporto G ⁰ e G ⁰⁰ .

rete. Un’unit´ a di flusso inviata lungo l’arco (i, j) ha costo pari a c _ij . La variabile x _ij rappresenta la quantit´ a di flusso inviata lungo l’arco (i, j). La somma

X

j:(j,i) ∈A

x ji

rappresenta il flusso complessivo entrante nel nodo i, la somma X

j:(i,j) ∈A

x ij

rappresenta il flusso complessivo uscente dal nodo i e quindi il vincolo X

j:(i,j) ∈A

x ij − X

j:(j,i) ∈A

x ji = b i

dice che la differenza tra flusso uscente e flusso entrante nel nodo i deve essere

pari a b i . Se b i > 0 il flusso uscente supera quello entrante e quindi il nodo

viene detto nodo sorgente. Se b i < 0 il flusso entrante supera quello uscente ed

il nodo viene detto nodo destinazione. Se b i = 0 i due flussi entrante ed uscente

si equivalgono ed il nodo viene detto di transito. In pratica ci sono nodi in cui il

flusso viene prodotto (i nodi sorgente), altri in cui transita (i nodi transito) ed

altri ancora verso cui viene convogliato (i nodi destinazione). Inviare un flusso

x _ij lungo il generico arco (i, j) ha un costo pari a c _ij x _ij . L’obiettivo ´ e quello di soddisfare le richieste di tutti i nodi (rappresentate dai valori b i ) in modo tale da avere un costo complessivo del flusso inviato lungo i diversi archi che sia il pi´ u piccolo possibile.

Esempio 7 Sia data la rete in Figura 6. I valori b i sono riportati di fianco ai

@

@

@

@

@

@

@

@ c

c c

c c

c c

c c

c





















1

2

3 4

5 b1=2

b2=5

b4=-4

b5=-4 b3=1 5

-2

2

0 -4 6

3 4

Figura 6: Una rete con i relativi valori b i associati ai nodi ed i costi unitari di trasporto lungo gli archi.

nodi mentre lungo gli archi sono riportati i valori c _ij . I nodi 1,2 e 3 sono nodi sorgente mentre i nodi 4 e 5 sono nodi destinazione (non vi sono nodi transito).

Il problema corrispondente ´ e il seguente

min 5x 12 − 4x 23 + 6x 42 − 2x 13 + 0x 34 + 2x 15 + 4x 53 + 3x 45

x 12 + x 13 + x 15 = 2 x ₂₃ − x 12 − x 42 = 5 x 34 − x 13 − x 23 − x 53 = 1

x ₄₂ + x ₄₅ − x 34 = −4 x 53 − x 15 − x 45 = −4

x ₁₂ , x ₂₃ , x ₄₂ , x ₁₃ , x ₃₄ , x ₁₅ , x ₅₃ , x ₄₅ ≥ 0 interi

Analizziamo ora la matrice dei vincoli per questi problemi. In essa avremo tante

righe quanti sono i nodi della rete e tante colonne quanti sono gli archi della

rete. Tale matrice viene detta matrice di incidenza nodo-arco della rete. Essa

avr´ a nella colonna relativa all’arco (i, j) due soli elementi diversi da 0, un +1

nella riga i relativa al nodo da cui l’arco esce e un -1 nella riga j relativa al nodo in cui l’arco entra. Ma allora ci ritroviamo nella situazione di una matrice con elementi tutti uguali a 0, +1 o -1, con non pi´ u di due elementi diversi da 0 lungo ogni colonna e con tali elementi di segno opposto. Il Corollario 1 ci dice che tale matrice ´ e TU e quindi, essendo tutti i b i interi per ipotesi, possiamo eliminare i vincoli di interezza sulle variabili. Quindi, i problemi di flusso a costo minimo, pur essendo problemi di PLI, sono problemi pi´ u semplici dei generici problemi di PLI in quanto risolvibili come se fossero problemi di PL.

Esempio 8 Nel nostro esempio la matrice di incidenza nodo-arco ´ e la seguente:

A =













1 1 1 0 0 0 0 0

−1 0 0 1 −1 0 0 0

0 −1 0 −1 0 1 −1 0

0 0 0 0 1 −1 0 1

0 0 −1 0 0 0 1 −1













(6)

Come gi´ a anticipato, i problemi di PLI risolvibili come problemi di PL elimi- nando i vincoli di interezza hanno tipicamente una struttura tale da consentire di sviluppare tecmiche specifiche per tali problemi pi´ u efficienti del simplesso o quantomeno di applicare il simplesso stesso con tecniche pi´ u legate alla struttu- ra del problema. Ci´ o che vedremo nel seguito ´ e il metodo del simplesso su reti, ovvero il metodo del simplesso adattato a problemi di flusso a costo minimo su reti. Prima per´ o accenniamo brevemente ad un risultato sul rango della matrice di incidenza nodo-arco di una rete.

4.1 Rango della matrice di incidenza nodo-arco di una rete

Se sommiamo tra loro tutte le | V | righe della matrice otteniamo il vettore nullo. Infatti in ogni colonna ci sono esattamente un +1 e un -1 (si faccia la verifica sull’esempio). Quindi le | V | righe sono tra loro linearmente dipendenti ed il rango non potr´ a essere superiore a | V | −1. Si pu´o dimostrare (ma non lo faremo) che il rango ´ e esattamente pari a | V | −1. Il fatto che P

i ∈V b i = 0 (e quindi non solo le righe della matrice sono linearmente dipendenti ma anche le equazioni stesse dei vincoli sono tra loro linearmente dipendenti) ci mostra che uno (ed un solo) vincolo del problema pu´ o essere eliminato in quanto ridondante. Non importa quale vincolo si elimina. Come convenzione si pu´ o fissare di eliminare l’ultima equazione. Nel seguito quindi l’ultimo vincolo si intender´ a soppresso e quando si parler´ a di matrice dei vincoli si intender´ a la matrice di incidenza nodo-arco privata dell’ultima riga. Nel nostro esempio quindi la matrice dei vincoli sar´ a

A =









1 1 1 0 0 0 0 0

−1 0 0 1 −1 0 0 0

0 −1 0 −1 0 1 −1 0

0 0 0 0 1 −1 0 1









ovvero la matrice (6) in cui ´ e stata soppressa l’ultima riga.

5 Il simplesso su rete

Vedremo ora come il simplesso possa essere adattato ai problemi di flusso a costo minimo su reti. Cominceremo con lo stabilire il legame esistente tra basi del simplesso ed alberi di supporto della rete.

NOTA BENE! Per mancanza di uno standard, quando nel seguito si far´ a riferimento a variabili in base e fuori base, si dovr´ a intendere l’opposto di quanto visto nella PL. Quelle che venivano dette variabili in base sono ora da intendersi come variabili fuori base e viceversa. Si noti che, essendo il numero di righe (ed il rango) della matrice dei vincoli pari a | V | −1, le basi sono sempre formate da

| V | −1 variabili. Ma non tutti gli aggregati di | V | −1 variabili danno origine ad una base. Per formare una base devono anche soddisfare la propriet´ a che la matrice ottenuta considerando le sole colonne relative ad esse nella matrice dei vincoli sia invertibile. Nel nostro esempio, se si considera l’albero di supporto in Figura 7 si ha che le colonne ad esso relativo nella matrice dei vincoli formano la seguente matrice









1 0 0 0

0 1 0 0

0 −1 1 0

0 0 −1 1









che ´ e invertibile e quindi le variabili corrispondenti formano una base.

@

@

@

@

@

@

@

@





















1

2

3 4

5 b1=2

b2=5

b4=-4

b5=-4 b3=1

2

0 -4

3

Figura 7: Un albero di supporto per la rete del nostro esempio.

5.1 Relazioni tra basi ed alberi di supporto

Si consideri un generico albero di supporto della rete. Esso sar´ a formato da

| V | −1 archi. Si pu´o dimostrare (ma non lo faremo) che la soluzione ottenuta mettendo le variabili relative agli archi dell’albero di supporto in base e tutte le altre fuori base (si ricordi ancora l’inversione della terminologia rispetto a quanto visto nella PL) si ottiene una soluzione di base (non necessariamente ammissibile e quindi non necessariamente un vertice) del problema. Abbozzeremo invece una dimostrazione del viceversa e cio´ e che data una qualsiasi base, i | V | −1 archi relativi alle variabili in base formano un albero di supporto. Per dimostrarlo ragioniamo per assurdo e supponiamo che gli archi non formino un albero di supporto. Poich´ e gli archi sono | V | −1, se non formano un albero di supporto devono formare almeno un ciclo. Vediamo cosa succede in presenza di un ciclo sul nostro esempio, precisando che quanto vedremo su tale esempio pu´ o essere generalizzato a tutti i casi in cui compaia un ciclo. Supponiamo che le | V |

−1 = 4 variabili in base siano quelle relative agli archi (1, 2) (2, 3) (5, 3) (1, 5)

che formano il ciclo mostrato in Figura 8. Fissiamo un arco del ciclo, ad esempio

@

@

@

@

@

@

@

@ ,

, ,

, ,

, ,

, ,

1

2

3 4

5 b1=2

b2=5

b4=-4

b5=-4 b3=1

Figura 8: Un insieme di archi che formano un ciclo non possono dare origine ad una base.

(1, 2) ed imponiamo che il verso di percorrenza del ciclo sia quello dell’arco

(1, 2). Per ogni colonna nella matrice dei vincoli relativa ad un arco del ciclo

la moltiplichiamo per +1 se il ciclo attraversa l’arco nel suo verso, per -1 se lo

attraversa nel verso opposto. Poi sommiamo i vettori ottenuti in questo modo.

Nel nostro caso moltiplicheremo per +1 le colonne relative agli archi (1, 2) e (2, 3) e per -1 quelle relative agli archi (5, 3) e (1, 5). Quindi avremo

+1







 1

−1 0 0







 + 1







 0 1

−1 0









− 1







 0 0

−1 0









− 1







 1 0 0 0









=







 0 0 0 0









Ci´ o dimostra che esiste una combinazione lineare non nulla delle colonne che re- stituisce il vettore nullo. Quindi tali colonne non formano una matrice invertibile e non rappresentano una base. Come detto, ´ e possibile generalizzare questo ri- sultato: ogni qualvolta gli archi relativi ad un insieme di variabili formano un ciclo, le corrispondenti colonne della matrice dei vincoli sono linearmente dipen- denti e quindi le variabili non formano una base. L’unica possibilit´ a per avere una base ´ e che gli archi non formino alcun ciclo. Ma in base alla definizione di albero, in un grafo con | V | nodi, | V | −1 archi che non formano alcun ciclo formano un albero di supporto.

Abbiamo quindi mostrato il seguente importante risultato.

Osservazione 2 In un problema di flusso su rete a costo minimo vi ´ e una corrispondenza uno a uno tra basi ed alberi di supporto, ovvero ad ogni insieme di | V | −1 variabili che formano una base corrisponde un albero di supporto e viceversa.

Quindi, per i problemi di flusso su reti a costo minimo sar´ a indifferente parlare di basi o di alberi di supporto.

5.2 Alberi di supporto e soluzione di base corrispondente

Supponiamo ora di avere un albero di supporto (vedi Figura 7) nel nostro esem- pio e poniamoci la seguente domanda: in corrispondenza di tale albero e quindi di tale soluzione di base, qual ´ e il valore delle variabili? Per prima cosa le va- riabili associate ad archi che non appartengono all’albero di supporto avranno associato un valore pari a 0. Quindi nel nostro esempio:

x ₁₂ = x ₁₃ = x ₄₂ = x ₅₃ = 0.

Partiamo ora dai nodi foglia dell’albero di supporto (in questo caso i nodi 1 e 2).

Essendoci un solo arco dell’albero incidente su di essi c’´ e anche un solo modo di

soddisfare il vincolo relativo a tali nodi e cio´ e inviando lungo quell’unico arco

un flusso pari al valore b i per quel nodo (si ricordi che il flusso lungo gli altri

archi incidenti sul nodo ´ e pari a 0). Ora, per il nodo 1 si ha b 1 = 2 e quindi il

solo modo di soddisfare il vincolo relativo al nodo 1 ´ e porre x ₁₅ = 2; per il nodo

2 si ha b ₂ = 5 e quindi il solo modo di soddisfare il vincolo relativo al nodo 2 ´ e

porre x ₂₃ = 2. Una volta sistemati i nodi foglia marchiamo in modo diverso (ad





















1

2

3 4

5 b1=2

b2=5

b4=-4

b5=-4 b3=1

2

0 -4

3

Figura 9: Il valore del flusso lungo gli archi tratteggiati ´ e gi´ a stato fissato.

esempio tratteggiandoli) gli archi incidenti su di essi (vedi Figura 9). Si noti che il valore del flusso lungo gli archi tratteggiati ´ e gi´ a stato fissato. Avremo quindi il nostro albero di supporto il cui insieme di archi indicheremo con T ed un suo sottoalbero formato dall’insieme di archi T ⁰ ⊆ T che contiene i soli archi di T non trattegiati. Si considerino ora i nodi foglia del sottoalbero T ⁰ . Prendiamo, per esempio, il nodo 3. I soli archi dell’albero di supporto T che incidono sul nodo 3 sono (2, 3), arco tratteggiato e lungo cui quindi il valore del flusso ´ e gi´ a stato fissato (x ₂₃ = 5), e (3, 4). A questo punto per soddisfare il vincolo relativo al nodo 3 (con b ₃ = 1) l’unica possibilit´ a ´ e inviare in uscita dal nodo 3 lungo l’arco (3, 4) un flusso pari a 6 e quindi porre x ₃₄ = 6. Per il nodo 5 abbiamo che i soli archi dell’albero di supporto T che incidono sul nodo 5 sono (1, 5), arco tratteggiato e lungo cui quindi il valore del flusso ´ e gi´ a stato fissato (x ₁₅ = 2), e (4, 5). A questo punto per soddisafare il vincolo relativo al nodo 5 (con b 5 = −4) l’unica possibilit´ a ´ e inviare in entrata al nodo 5 lungo l’arco (4, 5) un flusso pari a 2 e quindi porre x 45 = 2. A questo punto tratteggiamo anche i nuovi archi lungo cui il flusso ´ e stato fissato (vedi Figura 10). Possiamo notare che a questo punto tutti gli archi sono tratteggiati e quindi possiamo arrestarci. Se avessimo avuto altri archi non tratteggiati avremmo proseguito analizzando i nodi foglia dell’albero T ⁰ formato dagli archi non tratteggiati. Quindi la soluzione relativa all’albero di supporto T ´ e data da

x 15 = 2 x 23 = 5 x 34 = 6 x 45 = 2 x 12 = x 13 = x 42 = x 53 = 0

1

2

3 4

5 b1=2

b2=5

b4=-4

b5=-4 b3=1

2

0 -4

3

Figura 10: Il valore del flusso lungo gli archi tratteggiati ´ e gi´ a stato fissato.

Si noti che tutte le variabili sono non negative e quindi in questo caso si parla di soluzione di base o albero di supporto ammissibile ( e quindi si tratta di un vertice della regione ammissibile).

Posiamo ora riassumere la procedura che abbiamo applicato nel nostro esempio nel modo seguente.

Inizializzazione Siano tutti gli archi nell’insieme di archi T dell’albero di supporto a tratto continuo e sia T ⁰ = T .

Passo 1 Se T ⁰ = ∅ allora STOP. Altrimenti per ogni nodo foglia di T ⁰ si fissi nell’unico modo possibile il valore del flusso dell’unico arco in T ⁰ incidente su tale nodo e si tratteggi tale arco. Si indichi con U l’insieme degli archi tratteggiati in questo modo.

Passo 2 Si aggiorni T ⁰ eliminando da esso tutti gli archi che sono stati tratteg- giati, ovvero si ponga T ⁰ = T ⁰ \ U e si ritorni al Passo 1.

NOTA BENE Nel caso in cui una o pi´ u delle variabili relative all’albero di supporto fossero uguali a 0 avremmo una soluzione degenere.

5.3 Calcolo dei coefficienti di costo ridotto

Come avete visto in precedenza, una condizione sufficiente per stabilire se, data

una soluzione di base ammissibile (un vertice), ci troviamo in una soluzione

ottima in un problema di PL, ´ e controllare se tutti i coefficienti di costo ridotto

sono non positivi in un problema di massimo oppure tutti non negativi in un problema di minimo. Nella tabella del simplesso i coefficienti di costo ridotto appaiono nell’ultima riga della tabella. Nel simplesso su rete non abbiamo alcuna tabella e dobbiamo quindi vedere come calcolare tali valori. Per prima cosa ricordiamo che vanno calcolati per le sole variabili fuori base (al solito, si ricordi l’inversione di terminologia rispetto al metodo del simplesso visto in precedenza). Quindi i coefficienti vanno calcolati per le sole variabili associate ad archi che non fanno parte dell’albero di supporto. La procedura per tale calcolo verr´ a illustrata sul nostro esempio. Prendiamo una qualsiasi variabile fuori base e quindi un qualsiasi arco che non faccia parte dell’albero di supporto, ad esempio l’arco (1, 3). Per prima cosa aggiungiamo l’arco all’albero. Si former´ a esattamente un ciclo che verr´ a orientato nel verso dell’arco (1, 3) e quindi il ciclo sar´ a

1 → 3 → 4 → 5 → 1

come si vede da Figura 11. Si noti che il ciclo attraversa gli archi (1, 3), (3, 4)

@

@

@

@

@

@

@

@





















1

2

3 4

5 b1=2

b2=5

b4=-4

b5=-4 b3=1

2

0 -4

3

Figura 11: Il ciclo che si forma aggiungendo l’arco (1, 3).

e (4, 5) nel loro verso, mentre attraversa l’arco (1, 5) nel suo verso opposto. Il coefficiente di costo ridotto relativo all’arco (1, 3), indicato con c 13 verr´ a calco- lato sommando tra loro tutti i costi relativi agli archi attraversati dal ciclo nel loro stesso verso e sottraendo al risultato i costi degli archi attraversati dal ciclo in senso opposto al loro verso. Quindi

c ₁₃ = c ₁₃ + c ₃₄ + c ₄₅ − c 15 = −2 + 0 + 3 − 2 = −1.

Si noti che il coefficiente di costo ridotto ´ e negativo e questo ci dice immediata- mente che non possiamo concludere che la soluzione di base corrente ´ e ottima.

Possiamo ripetere la procedura per tutti gli archi fuori base per calcolare tutti i coefficienti di costo ridotto. Si ottengono i seguenti risultati:

c ₄₂ = 2 c ₁₂ = 2 c ₅₃ = 7.

Come gi´ a osseravto, la presenza di un coefficiente di costo ridotto negativo (c 13 ) ci impedisce di concludere che la soluzione di base corrente ´ e ottima. In questi casi nel metodo del simplesso che avete visto si procede ad un cambio di base attraverso un’operazione di cardine sulla tabella. Vediamo ora come questo viene fatto nel simplesso su rete.

5.4 Cambio di base ovvero l’operazione di cardine nel sim- plesso su rete

Per il cambio di base dovremo dare una regola per stabilire quale variabile fuori base far entrare in base e quale in base dovr´ a uscire dalla base. Per quanto riguarda la variabile fuori base da far entrare in base, la scelta ´ e ristretta alle sole variabili con coefficiente di costo ridotto negativo (le sole incrementando le quali si pu´ o far diminuire il costo complessivo del flusso). Tra queste fisseremo come regola di scegliere quella (o una di quelle, se sono pi´ u di una) con il coefficiente di costo ridotto il pi´ u negativo possibile. Nel nostro esempio non abbiamo alcuna scelta da fare visto che la sola variabile fuori base con coefficiente di costo ridotto negativo ´ e quella relativa all’arco (1, 3). Aggiungiamo tale arco all’albero e riotteniamo la Figura 11. Inizialmente il flusso lungo l’arco (1, 3) ´ e nullo (x 13 = 0). Incrementiamo a ∆ il valore di tale flusso. Quindi avremo un nuovo flusso pari a ∆ in uscita dal nodo 1 ed in entrata al nodo 3. Per poter continuare a rispettare i vincoli relativi al nodo 1 e 3 dovremo diminuire di ∆ il flusso lungo l’arco (1, 5) ed aumentare di ∆ il flusso lungo l’arco (3, 4). A questo punto per soddisfare il vincolo relativo al nodo 4 dobbiamo incrementare di ∆ il flusso lungo l’arco (4, 5). Si noti che il vincolo relativo al nodo 5 ´ e ancora soddisfatto poich´ e nel nodo 5 arriva un flusso pari a ∆ in pi´ u dal nodo 4 ma anche un flusso ancora pari a ∆ in meno dal nodo 1. Gli archi relativi al nodo 2 non subiscono variazioni e quindi il vincolo relativo al nodo 2 continua ad essere soddisfatto. Si pu´ o riassumere quanto visto nel modo seguente. Una volta aggiunto l’arco (1, 3) si forma un ciclo che viene orientato nel verso dell’arco (1, 3) stesso. Il flusso viene incrementato di ∆ lungo ogni arco che il ciclo attraversa nel suo stesso verso e decrementato di ∆ lungo gli archi che vengono attraversati in verso opposto. Quindi nel nostro esempio:

x 13 = ∆ x 34 = 6 + ∆ x 45 = 2 + ∆ x 15 = 2 − ∆.

A questo punto possiamo incrementare il valore di ∆ arrestandoci nel momento

in cui un flusso lungo un arco del ciclo si annulla. Nel nostro caso possiamo

incrementare ∆ fino a 2 ma non oltre in quanto incrementandolo oltre il flusso relativo all’arco (1, 5) diventerebbe negativo. La prima variabile che diventa nulla incrementando ∆ corrisponder´ a alla variabile da far uscire di base. Se pi´ u variabili diventano nulle contemporaneamente incrementando ∆ (caso degenere) se ne seleziona una di esse arbitrariamente. L’albero di supporto corrispondente alla nuova base sar´ a quello ottenuto inserendo l’arco relativo alla variabile fatta entrare in base (l’arco (1, 3) nel nostro esempio) e rimuovendo l’arco della varia- bile fatta uscire di base (l’arco (1, 5) nel nostro esempio). Per il nostro esempio la nuova base ´ e quella riportata in Figura 12 ed i nuovi valori delle variabili sono i seguenti

x ₁₃ = 2 x ₂₃ = 5 x ₃₄ = 8 x ₄₅ = 4 x ₁₂ = x ₁₅ = x ₄₂ = x ₅₃ = 0

NOTA BENE Se il ciclo ottenuto aggiungendo all’albero di supporto l’arco





















1

2

3 4

5 b1=2

b2=5

b4=-4

b5=-4 b3=1

Figura 12: La nuova base (albero di supporto) del problema.

relativo alla variabile fuori base avesse tutti gli archi orientati nello stesso verso del ciclo stesso (vedi Figura 13) allora potrei far crescere ∆ all’infinito senza che nessun flusso si annulli (tutti i flussi lungo il ciclo vengono incrementati). Ci´ o corrisponde al caso di problema illimitato.

Possiamo ora concludere il nostro esempio andando a calcolare i nuovi coefficienti di costo ridotto. I risultati sono i seguenti.

c ₄₂ = 2 c ₁₅ = 1 c ₁₂ = 3 c ₅₃ = 7.



















 l

l l

l l

l l

l

1

2

3 4

5 b1=2

b2=5

b4=-4

b5=-4 b3=1

Figura 13: Tutti gli archi del ciclo hanno lo stesso orientamento: il problema ha obiettivo illimitato.

Essendo tutti non negativi si conclude che la soluzione corrente ´ e ottima. Pi´ u precisamente, essendo tutti non solo non negativi ma anche strettamente posi- tivi, si conclude che la soluzione ´ e anche l’unica soluzione ottima.

5.5 Calcolo della soluzione del duale

Una volta ottenuta la soluzione ottima per il problema primale possiamo de- terminare la soulzione ottima del problema duale. Prendiamo nella matrice dei vincoli le sole colonne relative agli archi nell’albero di supporto ottimo. Sia B la matrice ottenuta in questo modo. A questo punto dobbiamo semplicemente risolvere il sistema

wB = c B

dove c B ´ e il vettore dei costi di flusso unitario ristretto alle sole variabili associate ad archi dell’albero di supporto ottimo. Nel nostro esempio avremo

[w 1 w 2 w 3 w 4 ]









1 0 0 0

0 1 0 0

−1 −1 1 0

0 0 −1 1









=









−2

−4 0 3









e quindi

w 1 − w 3 = −2 w 2 − w 3 = −4 w 3 − w 4 = 0 w 4 = 3

da cui

w 1 = 1 w 2 = −1 w 3 = 3 w 4 = 3.

5.6 Determinazione di una soluzione di base ammissibile iniziale

Nella descrizione del simplesso su rete siamo partiti assumendo di avere gi´ a a disposizione un albero di supporto ammissibile. Non sempre per´ o questo ´ e vero e non ´ e neppure detto che una soluzione ammissibile esista. Avremo quindi bisogno di una procedura che ci dica se ci sono soluzioni ammissibili e, nel caso esistano, ce ne restituisca una. Utilizzeremo una tecnica due fasi. Nella prima fase aggiungiamo alla nostra rete un nuovo nodo q e congiungiamo tale nodo con ogni nodo i della rete tale che b i < 0 attraverso l’arco (q, i), mentre lo congiungiamo con ogni nodo i della rete tale che b i ≥ 0 attraverso l’arco (i, q).

I valori b i vengono lasciati invariati, mentre si pone b q = 0. I costi dei flussi unitari saranno posti uguali a 1 per tutti gli archi incidenti sul nodo q e 0 per tutti gli archi della rete originaria. Per il nostro esempio la nuova rete sar´ a quella in Figura 14. Per questo problema si ha immediatamente a disposizione

@

@

@

@

@

@

@

@ c

c c

c c

c c

c c

c





















1

2

3 4

5 b1=2

b2=5

b4=-4

b5=-4 b3=1 0 q

bq=0

1 1

1 1

1

0 0 0

0 0 0

0

Figura 14: Il problema di prima fase per determinare una soluzione ammissibile iniziale.

un albero di supporto ammissibile, quello formato da tutti gli archi incidenti su

q, con i seguenti valori delle variabili:

x qi = −b i ∀ i : b i < 0 x _iq = b _i ∀ i : b i ≥ 0

mentre tutte le altre variabili sono nulle. A questo punto risolviamo questo pro- blema con il simplesso su rete nel modo gi´ a visto in precedenza. Se la soluzione ottima di tale problema ´ e maggiore di 0, allora il problema originario ha regione ammissibile vuota. Se invece la soluzione ottima ´ e pari a 0 e l’albero di supporto ottimo contiene solo uno dei nuovi archi (quelli incidenti su q), eliminando tale arco si ottiene un albero di supporto ammissibile per il problema originario. A questo punto possiamo eliminare il nodo q e tutti gli archi incidenti su di esso, ripristinare gli originari costi degli archi e cominciare a risolvere il problema (se- conda fase del metodo). Non illustreremo la prima fase del metodo sul nostro solito esempio in quanto ci sarebbero troppi calcoli da fare. La illustreremo su un esempio di pi´ u piccole dimensioni.

Esempio 9 Si consideri la rete in Figura 15. Nella prima fase aggiungiamo il nodo q e gli archi incidenti su di esso ed aggiorniamo i costi dei flussi come indicato in Figura 16. Per il problema della prima fase un albero di supporto

       H H

H H H H

H H

1

2

3 b1=1

b2=3

b3=-4 2

3

5

Figura 15: Una rete.

ammissibile ´ e quello formato dagli archi incidenti su q, ovvero (1, q), (2, q) e (q, 3). La soluzione iniziale ´ e

x q3 = 4 x 2q = 3 x 1q = 1,

tutte le altre variabili nulle. Il calcolo dei coefficienti di costo ridotto resituisce c 12 = 0 c 13 = −2 c 23 = −2.

La soluzione non ´ e ottima in quanto abbiamo coefficienti di costo ridotto ne-

gativi. Scelgo una delle variabili fuori base con coefficiente di costo ridotto pi´ u

       H H

H H H H

H H

1

2

3 q

b1=1

b2=3

b3=-4 0

0

0

1

1

1

Figura 16: La rete ausiliaria per determinare un flusso ammissibile iniziale per la rete di Figura 15.

negativo, ad esempio quella associata all’arco (1, 3). Applicando la procedura per il cambio di base ottengo il nuovo albero di supporto (1, 3), (2, q) e (q, 3).

La nuova soluzione ´ e

x q3 = 3 x 2q = 3 x 13 = 1,

tutte le altre variabili nulle. Il calcolo dei coefficienti di costo ridotto resituisce c 12 = 2 c 1q = 1 c 23 = −2.

La soluzione non ´ e ottima in quanto abbiamo coefficienti di costo ridotto ne- gativi. Scelgo una delle variabili fuori base con coefficiente di costo ridotto pi´ u negativo, in tal caso c’´ e solo quella associata all’arco (2, 3). Applicando la pro- cedura per il cambio di base ottengo il nuovo albero di supporto (1, 3), (2, 3) e (q, 3). La nuova soluzione ´ e

x _q3 = 0 x ₂₃ = 3 x ₁₃ = 1,

tutte le altre variabili nulle. Il calcolo dei coefficienti di costo ridotto resituisce c 12 = 0 c 1q = 1 c 2q = 1.

La soluzione ´ e ottima ed ´ e pari a 0. Quindi il problema ammette soluzioni

ammissibili. Inoltre, poich´ e la soluzione ottima contiene un solo arco incidente

sul nodo q, eliminando tale arco ottengo immediatamente un albero di supporto

ammissibile per il problema originario (quello formato dagli archi (1, 3) e (2, 3))

e con tale albero di supporto ammissibile sono pronto ad entrare nella seconda

fase e risolvere il problema originario.

6 Casi particolari di problemi di flusso a costo minimo

6.1 Problema del cammino minimo

Data una rete G = (V, A) con costi associati agli archi tutti non negativi, si fissino due nodi s e t. Si vuole determinare il cammino a costo minimo (o distanza minima se i costi corrispondono alle lunghezza degli archi da percorrere) dal nodo s al nodo t. Il problema pu´ o essere formulato come quello di inviare una singola unit´ a di flusso dal nodo s al nodo t cercando di minimizzare il costo per far giungere tale unit´ a dal nodo s al nodo t. Quindi avremo un particolare problema di flusso a costo minimo in cui dal nodo s esce un’unit´ a di flusso (b s = +1), nel nodo t ne entra una (b t = −1), mentre tutti gli altri sono nodi di transito b i = 0 (vedi Figura 17). Il problema ha la formulazione seguente:

min P

(i,j) ∈A c ij x ij

P

j: (s,j) ∈A x sj − P

j: (j,s) ∈A x js = +1 P

j: (t,j) ∈A x _tj − P

j: (j,t) ∈A x _jt = −1 P

j: (i,j) ∈A x ij − P

j: (j,i) ∈A x ji = 0 ∀ i ∈ V \ {s, t}

x ij ∈ {0, 1} ∀ (i, j) ∈ A

Si noti che, rispetto al generico problema di flusso a costo minimo, invece del vincolo di interezza delle variabili x ij , (cio´ e x ij ≥ 0 interi) qui abbiamo vincoli di binariet´ a sulle variabili (x ij ∈ {0, 1} ovvero non solo le variabili devono essere intere ma esse possono assumere i soli valori 0 e 1). In realt´ a si dimostra che anche in questo caso la chiusura convessa della regione ammissibile del problema si ottiene semplicemente sostituendo i vincoli di binariet´ a x _ij ∈ {0, 1} con i vincoli x _ij ≥ 0, cio´e richiedendo soltanto che le variabili siano non negative, esattamente come per i generici problemi di flusso a costo minimo la chiusura convessa della regione ammissibile si ottiene semplicemente eliminando i vincoli di interezza delle variabili.

6.2 Il problema del trasporto

Se nel problema del cammino a costo minimo la rete pu´ o avere una forma qualsiasi ma i nodi possono avere solo valori b i particolari, nel problema del trasporto i nodi possono avere generici valori b _i ma la rete ha una struttura particolare. Pi´ u precisamente, nel problema del trasporto la rete ´ e un grafo bipartito. Siano V ₁ e V ₂ i sottinsiemi in cui ´ e partizionato l’insieme dei nodi.

Dai nodi in V ₁ ci sono solo archi uscenti e nei nodi in V ₂ ci sono solo archi entranti e quindi per ogni (i, j) ∈ A si ha i ∈ V 1 e j ∈ V 2 . Quindi b _i > 0 per ogni i ∈ V 1

e b i < 0 per ogni i ∈ V 2 . I nodi i in V 1 possono essere visti come magazzini

in cui si trovano le quantit´ a b i di un certo prodotto. I nodi j in V 2 possono

! ! ! ! ! ! ! ! ! ! ! hhh hhh hhh h Q

Q Q

Q Q

Q Q

Q Q

Q Q

B B

B B

B " " " " " " "

@

@

@

@

@

@

@

 

 

 

 

 a a

a a a a

a a

s

t bs=1

bt=-1 1

2

3

4

5 b1=0

b2=0

b3=0

b4=0

b5=0 4

4 6

3

2 5

8 6

7

5

Figura 17: La rete per un problema di cammino a costo minimo.

essere visti come negozi che richiedono le quantit´ a b j del prodotto. Il trasporto di un’unit´ a di prodotto dal nodo i al nodo j (se esiste un arco che congiunge i e j) ha un costo pari a c ij . Si tratta di determinare le quantit´ a di prodotto da inviare da ogni magazzino verso ogni negozio in modo tale da rendere minimo il costo complessivo di trasporto. Un caso particolare ´ e illustrato in Figura 18.

Il problema si presenta nella seguente forma:

min P

(i,j) ∈A c _ij x _ij P

j: (i,j) ∈A x ij = b i ∀ i ∈ V 1

− P

i: (i,j) ∈A x ij = b j ∀ j ∈ V 2

x _ij ≥ 0 interi ∀ (i, j) ∈ A

Come si vede, si tratta di un particolare esempio di problema di flusso a costo minimo.

6.3 Il problema dell’assegnamento

Il problema di assegnamento ´ e un caso particolare del problema del trasporto in cui | V 1 |=| V 2 | ed inoltre b i = 1 per ogni i ∈ V 1 e b _j = −1 per ogni j ∈ V 2 . Il problema si pu´ o interpretare come quello di formare coppie di elementi di V ₁ e V ₂ in modo da rendere minimo il costo complessivo di tali accoppiamenti. Un esempio particolare ´ e il caso in cui V 1 ´ e un insieme di compiti, V 2 un insieme di persone ed il costo c ij , i ∈ V 1 e j ∈ V 2 , ´ e il costo di far svolgere il compito i alla persona j (vedi Figura 19). Il problema si presenta nella seguente forma:

min P

(i,j) ∈A c ij x ij

hhhh hhhh hhhh hhh

         H H

H H H H

H H H H

H H H H

H H

! !

! !

! !

! !

! !

! !

! !

!

               

5

6

8 4

3 2 7

9 1

2

3

4

5

6

7 b1=4

b2=6

b3=8

b4=1

b5=-10

b6=-5

b7=-4

Figura 18: Un esempio di problema di trasporto.

P

j: (i,j) ∈A x ij = 1 ∀ i ∈ V 1

P

i: (i,j) ∈A x _ij = 1 ∀ j ∈ V 2

x ij ≥ 0 interi ∀ (i, j) ∈ A

Si pu´ o dimostrare che, per la forma dei vincoli del problema di assegnamento, il richiedere x _ij ≥ 0 interi ´e equivalente a richiedere che le variabili siano binarie, ovvero x _ij ∈ {0, 1}, cio´e i soli valori interi che possono assumere le variabili x ij

in un problema di assegnamento sono i valori 0 e 1. Quindi una formulazione equivalente del problema ´ e la seguente:

min P

(i,j) ∈A c ij x ij

P

j: (i,j) ∈A x _ij = 1 ∀ i ∈ V 1

P

i: (i,j) ∈A x ij = 1 ∀ j ∈ V 2

x ij ∈ {0, 1} ∀ (i, j) ∈ A

I valori 0 e 1 delle variabili vengono interpretati nel modo seguente: se x ij = 0,

allora l’elemento j ∈ V 2 non viene accoppiato con l’elemento i ∈ V 1 ; se x ij = 1,

allora l’elemento j ∈ V 2 viene accoppiato con l’elemento i ∈ V 1 .

hhhh hhhh hhhh hhh

         H H

H H H H

H H H H

H H H H

H H

! !

! !

! !

! !

! !

! !

! !

!

5

6

8 4

3 2 1

2

3

4

5

6 b6=-1 b5=-1

b4=-1 b1=1

b2=1

b3=1

Figura 19: Un esempio di problema di assegnamento.

6.4 Il problema di massimo flusso

Sia data una rete G = (V, A) dove vengono individuati due nodi in V , uno indicato con S e l’altro con D (vedi Figura 20). Vogliamo produrre la massima



 



 

hhhhhh E E E E E J

J J

J J

J J

J Z

Z Z

Z Z

Z Z

! ! ! ! ! ! P P

P P P P

P

       Q

Q Q

Q Q

S Q

D 1

2

3

4

5 8

8 2

5 6

1

4 3

6 2

Figura 20: Un esempio di problema di flusso massimo. Si noti che i numeri al di sopra degli archi non rappresentano costi ma capacit´ a degli archi.

quantit´ a di flusso possibile in S e farlo giungere a D attraverso gli archi della

rete. Ad ogni arco (i, j) della rete ´ e associata una quantit´ a K ij che ´ e la sua

capacit´ a (il flusso massimo trasportabile lungo tale arco). Il flusso pu´ o essere

per esempio un prodotto che, attraverso una rete stradale, deve essere fatto

giungere da una sorgente (il nodo S) ad una destinazione (il nodo D) oppure

dell’informazione da far viaggiare attraverso una rete di comunicazione. I nodi

intermedi (i nodi diversi da S e T ) sono nodi di transito b i = 0. Il problema si

presenta nella seguente forma:

max y P

j:(S,j) ∈A x _Sj − P

j:(j,S) ∈A x _jS = y P

j:(D,j) ∈A x Dj − P

j:(j,D) ∈A x jD = −y P

j:(i,j) ∈A x ij − P

j:(j,i) ∈A x ji = 0 ∀ i ∈ V \ {S, D}

0 ≤ x ij ≤ K ij interi ∀ (i, j) ∈ A y ≥ 0

In questa forma non si presenta come un problema di flusso a costo minimo. Per prima cosa si presenta come problema di massimo invece che come problema di minimo. A questo si rimedia facilmente ricordando che

max y = − min −y

Inoltre, nei problemi di flusso a costo minimo abbiamo che i valori b _i sono fissi mentre qui abbiamo che per S e D essi sono delle variabili (+y per il nodo S e −y per il nodo D). Anche a questo si pu´o ovviare modificando la rete con l’aggiunta di un arco da D verso S con K DS = + ∞ (vedi Figura 21). Avremo quindi una nuova rete G ⁰ = (V, A ⁰ ) dove A ⁰ = A ∪ {(D, S)}. In tal caso si dimostra che il problema di flusso massimo ´ e equivalente al seguente:

− min −x DS

P

j:(i,j) ∈A

x ij − P

j:(j,i) ∈A

x ji = 0 ∀ i ∈ V 0 ≤ x ij ≤ K ij interi ∀ (i, j) ∈ A ⁰

dove tutti i nodi sono di transito (b i = 0 per ogni i ∈ V e i costi unitari di tutti gli archi sono nulli, a parte per l’arco (D, S) per il quale il costo unitario ´ e pari a -1 (osservando questo problema si pu´ o notare che ´ e identico al precedente con la sola differenza che la variabile y ´ e stata sostituita dalla variabile x DS ).

C’´ e ancora una differenza rispetto al generico problema di flusso minimo: oltre al fatto di dover essere non negativi, i flussi lungo gli archi sono anche limitati superiormente dai valori di capacit´ a K _ij . In realt´ a esiste anche per i generici problemi di flusso a costo minimo la possibilit´ a di apportare opportune modifiche (che per´ o non vedremo) al simplesso su rete per trattare il caso in cui esistono anche limiti superiori per i flussi che possono scorrere lungo gli archi oltre al fatto che tali flussi devono essere non negativi.

6.5 Un’importante osservazione

I quattro casi particolari di problemi riconducibili a problemi di flusso a costo

minimo potrebbero essere risolti tutti con il simplesso su rete. In realt´ a per

essi vengono utilizzate procedure di risoluzione specifiche per tali problemi che





 





hhhhhh E E E E E J

J J

J J

J J

J Z

Z Z

Z Z

Z Z

! ! ! ! ! ! P P

P P P P

P

       Q

Q Q

Q Q

S Q

D 1

2

3

4

5

bS=0 bD=0

b1=0

b2=0

b3=0

b4=0

b5=0

-1/infinito

0/8

0/8

0/1

0/4 0/6 0/6

0/2

0/6

0/3 0/2

Figura 21: La riformulazione del di un problema di flusso massimo come pro- blema di flusso a costo minimo con l’aggiunta di un arco dalla destinazione D alla sorgente S. Si noti che i numeri al di sopra degli archi rappresentano i loro costi nel problema di flusso a costo minimo affiancati dalle loro capacit´ a.

sono pi´ u efficienti del simplesso su rete o versioni del simplesso su rete adattate ulteriormente a tali problemi. Questo dimostra un punto importante, di cui si dovrebbe tener conto ogni volta che si affronta un problema: con quanta maggio- re precisione si riesce ad individuare il tipo di problema che si deve affrontare, tanto pi´ u efficientemente possiamo sperare di risolvere il nostro problema. Ad esempio, per quanto sia legittimo risolvere un problema del cammino a costo minimo come un generico problema di flusso a costo minimo e quindi attraverso il simplesso su rete, ignorare la sua particolare struttura vuol dire rinunciare ad avvalersi delle tecniche pi´ u efficienti per la risoluzione di tale problema. Non vedremo procedure alternative e pi´ u efficienti per tutti i quattro casi trattati.

Ci limiteremo, a titolo illustrativo, al solo problema di cammino a costo minimo

(gli altri tre problemi vengono approfonditi nel corso successivo).

6.6 Un algoritmo per il problema del cammino a costo minimo

Proporremo ora una procedura (algoritmo di Dijkstra) che consente di determi- nare il cammino minimo non solo da un nodo s ad un nodo t ma da un nodo s a tutti gli altri nodi della rete. ´ E importante sottolineare che la procedura fornisce garanzie di determinare la soluzione ottima solo se i costi degli archi sono tutti non negativi. La procedura ´ e la seguente.

Inizializzazione Sia U = V \ {s}. Si ponga

d[s] = 0 d[i] = + ∞ ∀ i ∈ U, e

p[i] = − ∀ i ∈ V.

Sia k = s.

Passo 1 Per ogni i ∈ U se

d[k] + c ki < d[i], porre

d[i] = d[k] + c ki p[i] = k.

Passo 2 Sia r ∈ U tale che

d[r] = min

i ∈U d[i].

Porre U = U \ {r} e k = r.

Passo 3 Se U = ∅, allora STOP. Altrimenti si ritorni al Passo 1.

Al termine dell’esecuzione dell’algoritmo il vettore d contiene le distanze minime di tutti i nodi dal nodo s (durante l’esecuzione della procedura il vettore d contiene le distanze minime da s ai nodi in V \ U, mentre per i nodi in U contiene le distanze minime da s a tali nodi passando solo attraverso nodi in V \ U). Se, dato un nodo t si vuole non solo sapere qual ´e la distanza minima da s a t ma anche il cammino lungo il quale si ha questa distanza, si deve utilizzare il vettore p. Il cammino si conclude ovviamente nel nodo t. Il nodo che precede t nel cammino ´ e il nodo h ₁ = p[t]. A sua volta il nodo h ₁ ´ e preceduto dal nodo h ₂ = p[h ₁ ]; procedo in questo modo fino a che il nodo h _i+1 = p[h _i ] coincide con s. Il cammino minimo da s a t sar´ a quindi

s → h i → . . . → h 1 → t.

Per meglio comprendere la procedura la vediamo applicata al problema in Figura

22.

" " " " " " "

Z Z

Z Z

Z Z

Z a a

a a a a

a a a a

        

1

2

3

4 1

4

2

3 4

Figura 22: Un esempio di problema di cammino minimo.

Esempio 10 Il nodo s ´ e, nel nostro caso, il nodo 1. Inizialmente avremo d[1] = 0 d[2] = d[3] = d[4] = + ∞.

e

p[1] = p[2] = p[3] = p[4] = − con U = {2, 3, 4} e k = 1.

ITERAZIONE 1 Alla prima iterazione avremo

d[1] + c ₁₂ = 0 + 1 < d[2] = + ∞ ⇒ d[2] = d[1] + c 12 = 1 p[2] = 1 d[1] + c ₁₃ = 0 + 4 < d[3] = + ∞ ⇒ d[3] = d[1] + c 13 = 4 p[3] = 1

d[1] + c 14 = 0 + ∞ = d[2]

(si noti che se un arco non ´ e presente nella rete si associa ad esso un costo pari a + ∞). Avremo quindi

d[2] = min

i ∈U d[i] = min {d[2], d[3], d[4]}.

Quindi poniamo k = 2 e U = {3, 4}.

ITERAZIONE 2 Alla seconda iterazione avremo

d[2] + c ₂₃ = 1 + 2 < d[3] = 4 ⇒ d[3] = d[2] + c 23 = 3 p[3] = 2 d[2] + c 24 = 1 + 4 < d[4] = + ∞ ⇒ d[4] = d[2] + c 24 = 5 p[4] = 2 Avremo quindi

d[3] = min

i ∈U d[i] = min {d[3], d[4]}.

Quindi poniamo k = 3 e U = {4}.

ITERAZIONE 3 Alla terza iterazione avremo

d[3] + c ₃₄ = 3 + 3 > d[4] = 5

Avremo quindi

d[4] = min

i ∈U d[i] = min {d[4]}.

Quindi poniamo k = 4 e U = ∅. Essendo U = ∅ ci arrestiamo. Notiamo che d[4] = 5 e quindi il cammino minimo dal nodo 1 al nodo 4 ´ e pari a 5. Se vogliamo ricostruire tale cammino minimo, consideriamo il vettore p. Si ha che p[4] = 2 e quindi nel cammino minimo il nodo 4 ´ e preceduto dal nodo 2. Procedendo a ritroso, si ha che p[2] = 1. Dal momento che il nodo 1 ´ e quello di partenza ci arrestiamo ed il cammino minimo dal nodo 1 al nodo 4 sar´ a

1 → 2 → 4