Ricerca Operativa

Claudio Arbib

Università dell’Aquila

Ricerca Operativa

Metodo del simplesso

per problemi di distribuzione

single-commodity

Scenario

• Un insieme di produttori (consumatori) offre (richiede) determinati

quantitativi di un medesimo bene rappresentati da un vettore di domanda d

• Ipotesi single commodity: non ha importanza da quali produttori ciascuno dei consumatori ottenga la quantità richiesta

• La distribuzione avviene mediante una rete conservativa, dove produttori e consumatori sono rappresentati da nodi e la distribuzione avviene

attraverso un insieme di archi che li collega gli uni agli altri (grafo connesso G = (V, E))

• Attraversare l’arco ij comporta un costo c

per unità di bene trasportato (costi lineari)

• Il flusso nel generico arco ijE dev’essere compreso fra una soglia l

e una

capacità u

Problema

• Calcolare una distribuzione di flusso che attribuisca a ciascun arco ij di G un flusso reale x

compreso tra l

e u

e in tal modo soddisfi il vettore di domanda d al costo più basso possibile:

min cx

Ax = d l < x < u

1 2 3 4 5 6 7

–1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0

0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0

0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 –10

0 0 –1 –2 7 6 d =

2 10 8 5 7 6 10 12 4 3 5 0 0 0 0 0 0 1 0 2 0 0 3 9 6 5 10 4 10 9 11 5 9

a b c d e f g h i j k

c l u

7

1

3 2

4

5

7 6

–10

–2

–1 0

6

a b

c d

f e g

h

i

j k

0

Basi

• Una base è un insieme massimale di colonne di A linearmente indipendenti Teorema: k colonne di A sono linearmente indipendenti se e solo se gli archi corrispondenti non formano cicli

Dimostrazione: se C è un ciclo corrispondente a colonne di A, scegliamo un verso di percorrenza e moltiplichiamo per +1

ogni colonna associata a un arco concorde col verso e per –1 ogni colonna associata a un arco discorde. Sommando si ottiene la colonna 0.

1 2 3 4 5 6 7

–1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0

0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0

0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1

a b c d e f g h i j k

1

3 2

4

5

7 6

a b

c d

f e g

h

i

j k

a b

c d

–1 +1 +1 –1

1 –1 0 0 –1 0 0 1 0 1 –1 0 0 0 1 –1 0 0 0 0 0 0 0 0 0 0 0 0

Basi

• Una base è un insieme massimale di colonne di A linearmente indipendenti Teorema: k colonne di A sono linearmente indipendenti se e solo se gli archi corrispondenti non formano cicli

Dimostrazione: Viceversa, sia B un insieme massimale di archi di G che non formano cicli (albero ricoprente T). Si visitino i

nodi e gli archi di di T in post-ordine permutando le righe (nodi) e le colonne (archi) della matrice via via che si visitano. Con una colonna unitaria, la matrice è triangolare e ha determinante 1

1

3 2

4

5

7 6

a b

c d

f e g

h

i

j k

1 b

b

2

c

3 c

d

4

d

i 6

i

j 7

j e

5

e

–1 0 0 0 0 0 0 1 –1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 –1 –1 –1 0 0 0 –1 0 0 1 1

Soluzioni di base

• In una soluzione di base, le variabili in base (archi di T ) assumono valori compresi tra l

e u

• Una variabile fuori base invece è fissata o al valore di soglia l

oppure al valore della capacità u

• Siano B, L, U gli insiemi di archi corrispondenti a variabili in base oppure fuori base dei due tipi. Il problema min cx

Ax = d l < x < u si riscrive (eliminando una riga

in modo che A

sia quadrata)

min c

x

+ c

x

+ c

x

A

x

+ A

x

+ A

x

= d l < x < u

• Sostituendo nella funzione obiettivo x

= A

(d – A

x

– A

x

) questa diventa c

A

d + (c

– A

A

)x

+ (c

– A

A

)x

• Per i costi ridotti fuori base si ha quindi c

’ = (c

– A

A

) c

’ = (c

– A

A

)

• Poiché le variabili fissate alla soglia (alla capacità) possono solo aumentare

(diminuire) il loro valore, la base corrente sarà ottima se c

’ > 0, c

’ < 0

(criterio di ottimalità)

Calcolo di una prima soluzione

1

3 2

4

5

7 6

0 0 0

0

a b

c d

f e g

k

i

j

Trasformare il problema ponendo x’ = x – l > 0 e quindi sostituendo x = x’ + l

h

min cx

Ax = d l < x < u

min cx’ + cl

Ax’ = (d – Al) = d’

0 < x’ < u’ = u – l

1 2 3 4 5 6 7

–1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0

0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0

0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 –10

0 0 0 0 4 6 d’ =

2 10 8 5 7 6 10 12 4 3 5 0 0 0 0 0 0 1 0 2 0 0 3 9 6 5 10 4 9 9 9 5 9

a b c d e f g h i j k

c l u’

–10

6

4

Calcolo di una prima soluzione

1

3 2

4

5

7 6

0 0 0

0

a b

c d

f e g

k

i

j

t

6

4

s

10

Aggiungere i nodi s e t, collegarli alle sorgenti e ai pozzi k con capacità pari a |d

|, trovare il max (s, t)-flusso;

h

10

8 2

2 7

3

4 6

6 1

se è < 

d

non c’è soluzione

1 2 3 4 5 6 7

–1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0

0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0

0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 –10

0 0 0 0 4 6 d’ =

2 10 8 5 7 6 10 12 4 3 5 0 0 0 0 0 0 1 0 2 0 0 3 9 6 5 10 4 9 9 9 5 9

a b c d e f g h i j k

c l u’

Altrimenti, ricavare x = x’ + l (ammissibile)

2 8 1 2 0 0 3 7 0 0 6x’

2 8 1 2 0 0 4 7 2 0 6x

Calcolo di una prima soluzione

1

3 2

4

5

7 6

0

a b

c d

f e g

k

i

j

–10

Aggiungere i nodi s e t, collegarli alle sorgenti e ai pozzi k con capacità pari a |d

|, trovare il max (s, t)-flusso;

h

6

2

8 2

2 7

4 1

se è < 

d

non c’è soluzione

1 2 3 4 5 6 7

–1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0

0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0

0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 –10

0 0 –1 –2 4 6 d =

2 10 8 5 7 6 10 12 4 3 5 0 0 0 0 0 0 1 0 2 0 0 3 8 6 5 10 4 10 9 11 5 9

a b c d e f g h i j k

c l u

Altrimenti, ricavare x = x’ + l (ammissibile)

6 7

2 8 1 2 0 0 4 7 2 0 6x

–2

0 –1

2 8 1 2 0 0 4 7 2 0 6x

Calcolo di una prima base

1

3 2

4

5

7 6

0

a b

c d

f e g

k

i

j

–10

Una soluzione di base ha almeno m – n + 1 variabili fissate ai valori di soglia o capacità (variabili fuori base); se quindi vi sono più di n – 1 variabili con valori strettamente compresi tra l

e u

la x trovata non è di base

h

8 2

2 7

4

6

2 1

1 2 3 4 5 6 7

–1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0

0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0

0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 –10

0 0 –1 –2 4 6 d =

2 10 8 5 7 6 10 12 4 3 5 0 0 0 0 0 0 1 0 2 0 0 3 9 6 5 10 4 10 9 11 5 9

a b c d e f g h i j k

c l u

n = 7, m = 11 l

< x

< u

per 7 > n – 1 variabili

6 7

2 8 1 2x 0 0 4 7 2 0 6

–2 0 –1

8 2

2 7

4

6

1

2 8 1 2x 0 0 4 7 2 0 6

Calcolo di una prima base

1

3 2

4

5

7 6

a b

c d

f e g

k

i

j

Gli archi associati a queste variabili formano 2 cicli, da eliminare con operazioni di pivot. Nella prima,  = min{9 – 8, 6 – 1, 2 – 0, 2 – 0} = 1

h

8 2

2 7

4

6

2 1

1 2 3 4 5 6 7

–1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0

0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0

0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 –10

0 0 –1 –2 4 6 d =

2 10 8 5 7 6 10 12 4 3 5 0 0 0 0 0 0 1 0 2 0 0 3 9 6 5 10 4 10 9 11 5 9

a b c d e f g h i j k

c l u

n = 7, m = 11 l

< x

< u

per 7 > n – 1 variabili

1x 9 2 1 0 0 4 7 2 0 6

8 +  2 – 

2 –  7

4

6

1 + 

1x 9 2 1 0 0 4 7 2 0 6

Calcolo di una prima base

1

3 2

4

5

7 6

a b

c d

f e g

k

i

j

Gli archi associati a queste variabili formano 2 cicli, da eliminare con operazioni di pivot. Nella seconda,  = min{2 – 0, 9 – 7, 4 – 1} = 2

h

8 2

2 7

4

6

2 1

1 2 3 4 5 6 7

–1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0

0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0

0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 –10

0 0 –1 –2 4 6 d =

2 10 8 5 7 6 10 12 4 3 5 0 0 0 0 0 0 1 0 2 0 0 3 9 6 5 10 4 10 9 11 5 9

a b c d e f g h i j k

c l u

n = 7, m = 11 l

< x

< u

per 7 > n – 1 variabili

1x 9 0 1 0 0 2 9 2 0 6

9 1

1 7 + 

4 – 

6

2 – 

1x 9 0 1 0 0 2 9 2 0 6

Calcolo di una prima base

1

3 2

4

5

7 6

a b

c d

f e g

k

i

j

Nella soluzione ottenuta gli archi (viola) associati alle variabili strettamente comprese tra l

e u

non formano cicli, ma sono meno di n – 1 e quindi non ricoprono il grafo.

Un albero ricoprente (base degenere) si ottiene aggiungendo archi associati a variabili fuori base che non formino cicli con gli archi viola

h

8 2

2 7

4

6

2 1

1 2 3 4 5 6 7

–1 –1 0 0 0 0 0 0 0 0 0 1 0 0 –1 1 0 0 0 0 0 0 0 1 –1 0 0 0 0 –1 0 0 0

0 0 1 1 0 –1 –1 0 0 0 0 = A 0 0 0 0 –1 1 0 0 –1 –1 0

0 0 0 0 0 0 1 1 1 0 –1 0 0 0 0 0 0 0 0 0 1 1 –10

0 0 –1 –2 4 6 d =

2 10 8 5 7 6 10 12 4 3 5 0 0 0 0 0 0 1 0 2 0 0 3 9 6 5 10 4 10 9 11 5 9

a b c d e f g h i j k

c l u

9 1

1 9

2

6 0 0

2

Calcolo dei costi ridotti

1

3 2

4

5

7 6

b

e

j

Per ottenere il costo ridotto c’ = (c – c

A

A) non è necessario invertire A

. Sia y = c

A

, cioè y risolve il sistema di n – 1 equazioni in n incognite

– y

+ y

= c

ij  B

Siccome righe e colonne di B possono essere permutate con una visita in post- ordine ricavando una matrice triangolare, il

sistema è di facile risoluzione

7 h 3 1 2 4 6 5

1 0 0 0 0 0 0 –1 0 0 0 0 0 0 –1 0 0 0 0 0 1 –1 0 0 0 1 0 1 –1 0 –1 0 0 0 1 1 0 0 0 0 0 –1

5 8 2 5 10 4 k c a d g i

c_B

a

c d

f g

k

i

y

– y

= 5 y

– y

= 8 y

– y

= 2 y

– y

= 5 y

– y

= 10 y

– y

= 4

Per il potenziale d’ingresso y

si sceglie un valore arbitrario (es., y

= 10)

y

= 19

y

= – 4

y

= – 3

y

= – 1

y

= 4

y

= 14

b

Calcolo dei costi ridotti

1

3 2

4

5

7 6

b

e

j

Servendosi di y si calcola ora il costo ridotto c’ = (c – yA) delle variabili fuori base

c

’ = c

+ y

– y

ij  L  U

h

a

c d

f g

k

i

Per il potenziale d’ingresso y

si sceglie un valore arbitrario (es., y

= 10)

y

= 19 y

= – 4 y

= – 3 y

= – 1 y

= 4 y

= 14

c

’ = c

+ y

– y

= 10 – 3 + 4 = 11 c

’ = c

+ y

– y

= 12 – 4 – 14 = –6 c

’ = c

+ y

– y

= 7 + 10 + 1 = 18 c

’ = c

+ y

– y

= 6 + 4 – 10 = 0 c

’ = c

+ y

– y

= 3 + 10 – 19 = –6 Si ha x

= x

= 9

x

= x

= x

= 0

Quindi x

e x

sono

candidate a entrare

in base: scegliamo x

h

Calcolo della nuova base

1

3 2

4

5

7 6

b

e

j

L’aggiunta dell’arco b genera un ciclo.

Lo si elimina con un pivot cercando di far diminuire il flusso su b

a

c d

f g

k

i

Si ha x

= x

= 9 x

= x

= x

= 0 Quindi x

e x

sono candidate a entrare in base: scegliamo x

1 +  1 +  9 – 

9

6 0 – 

2 2

–1 –10

6

7 –2

2 10 8 5 7 6 10 12 4 3 5 0 0 0 0 0 0 1 0 2 0 0 3 9 6 5 10 4 10 9 11 5 9

a b c d e f g h i j k

c l u

Dalla tabella risulta

 = min{3 – 1, 9 – 0, 0 – 0, 5 – 1} = 0

j h

Calcolo della nuova base

1

3 2

4

5

7 6

b

e

j

L’aggiunta dell’arco b genera un ciclo.

Lo si elimina con un pivot cercando di far diminuire il flusso su b

a

c d

f g

k

i

La variabile x

è entrata in base con valore 9, la variabile x

è uscita dalla base con valore 0 I flussi non sono stati alterati, perché le basi coinvolte nell’operazione sono degeneri

Proviamo allora a far entrare in base x

, il cui flusso può crescere con costo ridotto –16

1 1

2 10 8 5 7 6 10 12 4 3 5 0 0 0 0 0 0 1 0 2 0 0 3 9 6 5 10 4 10 9 11 5 9

a b c d e f g h i j k

c l u

Dalla tabella risulta

 = min{3 – 1, 9 – 0, 0 – 0, 5 – 1} = 0

1

1 9

9

6

2 2

–1 –10

6

7 –2

0

j h

Calcolo della nuova base

1

3 2

4

5

7 6

b

e

Il flusso nell’arco i deve decrescere, e così quello nell’arco k.

a

c d

f g

k

i

L’arco i ha infatti soglia 2, pari al flusso attuale: ancora una volta la distribuzione è inalterata

1 1

2 10 8 5 7 6 10 12 4 3 5 0 0 0 0 0 0 1 0 2 0 0 3 9 6 5 10 4 10 9 11 5 9

a b c d e f g h i j k

c l u

Dalla tabella di soglie e capacità si ha  = min{2 – 2, 5 – 0, 6 – 0} = 0

9

1

1 9

6 – 

2 –  2

–1 –10

6

7 –2

0 + 

j h

Calcolo della nuova base

1

3 2

4

5

7 6

b

e

Il flusso nell’arco i deve decrescere, e così quello nell’arco k.

a

c d

f g

k

i

L’arco i ha infatti soglia 2, pari al flusso attuale: ancora una volta la distribuzione è inalterata

Il calcolo dei costi ridotti offre ora c

’ = –6 con x

fissata alla soglia u

= 0

1 1

2 10 8 5 7 6 10 12 4 3 5 0 0 0 0 0 0 1 0 2 0 0 3 9 6 5 10 4 10 9 11 5 9

a b c d e f g h i j k

c l u

Dalla tabella di soglie e capacità si ha  = min{2 – 2, 5 – 0, 6 – 0} = 0

9

1

1 9

6

2 2

–1 –10

6

7 –2

0

f

j h

Calcolo della nuova base

1

3 2

4

5

7 6

b

e

Il flusso nell’arco i deve decrescere, e così quello nell’arco k.

a

c d

g

k

i

1 1

2 10 8 5 7 6 10 12 4 3 5 0 0 0 0 0 0 1 0 2 0 0 3 9 6 5 10 4 10 9 11 5 9

a b c d e f g h i j k

c l u

Il ciclo introdotto coinvolge f, g, j, k Il flusso in f e j aumenta, quello in g e k diminuisce di

 = min{4 – 0, 2 – 1, 5 – 0, 6 – 0} = 1 ⁹

1

1 9

2

–1 –10

6

7 –2

6 2

6 –  0 2 – 

0 + 

0 + 

f

j h

Calcolo della nuova base

1

3 2

4

5

7 6

b

e

Il flusso nell’arco i deve decrescere, e così quello nell’arco k.

a

c d

g

k

L’arco g esce di base fissando il proprio

flusso al valore di soglia 1

1 1

2 10 8 5 7 6 10 12 4 3 5 0 0 0 0 0 0 1 0 2 0 0 3 9 6 5 10 4 10 9 11 5 9

a b c d e f g h i j k

c l u

Il ciclo introdotto coinvolge f, g, j, k Il flusso in f e j aumenta, quello in g e k diminuisce di

 = min{4 – 0, 2 – 1, 5 – 0, 6 – 0} = 1 ⁹

1

1 9

2

–1 –10

6

7 –2

5 1

1

1