Metodo del simplesso per distribuzione single commodity

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 cij per unità di bene trasportato
(costi lineari)
• Il flusso nel generico arco ijE dev’essere compreso fra una soglia lij e una
capacità uij
Problema
• Calcolare una distribuzione di flusso che attribuisca a ciascun arco ij di G
un flusso reale xij compreso tra lij e uij e in tal modo soddisfi il vettore di
domanda d al costo più basso possibile:
min
c
l
u
2
0
3
a
d =
–10
0
0
–1
–2
7
6
1
2
3
4
5
6
7
10 8
0 0
9 6
b
c
cx
Ax = d
l<x<u
–10
1
b
5 7 6 10 12 4 3
0 0 0 1 0 2 0
5 10 4 10 9 11 5
d
e
f
g
h
i
j
5
0
9
0
–1
3
2
c
4
e
g
f
i
6
7
0
d
h
k
–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
5
–2
k
j
7
6
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
1
ogni colonna associata a un arco concorde col
b
a
verso e per –1 ogni colonna associata a un arco
discorde. Sommando si ottiene la colonna 0.
3
2
c
–1
a
1
2
3
4
5
6
7
+1 +1 –1
b
c
d
d
4
h
e
f
g
h
i
j
e
g
k
–11 –1 0 0 0 0 0 0 0 0 0
–1
1 0 0 –1
1 1 0 0 0 0 0 0
0 1 –1 0 0 0 0 –1 0 0 0
0 0 1 –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
f
i
6
k
5
j
7
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
1
nodi e gli archi di di T in post-ordine permutando
a
b
le righe (nodi) e le colonne (archi) della matrice
via via che si visitano. Con una colonna unitaria, 3
2
c
d
la matrice è triangolare e ha determinante 1
4
h
b
1
3
4
6
7
5
2
c
d
i
j
e
g
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
f
i
6
5
j
k
7
Soluzioni di base
• In una soluzione di base, le variabili in base (archi di T ) assumono valori
compresi tra lij e uij
• Una variabile fuori base invece è fissata o al valore di soglia lij oppure al
valore della capacità uij
• Siano B, L, U gli insiemi di archi corrispondenti a variabili in base oppure
fuori base dei due tipi. Il problema min cBxcx
B + cLxL + cUxU
ABxAx
dLxL + AUxU = d
si riscrive (eliminando una riga
B +=A
l < lx<<xu< u
in modo che AB sia quadrata)
•
•
•
Sostituendo nella funzione obiettivo xB = AB–1(d – ALxL – AUxU) questa
diventa cBAB–1d + (cL – AB–1AL)xL + (cU – AB–1AU)xU
Per i costi ridotti fuori base si ha quindi cL’ = (cL – AB–1AL)
cU’ = (cU – AB–1AU)
Poiché le variabili fissate alla soglia (alla capacità) possono solo aumentare
(diminuire) il loro valore, la base corrente sarà ottima se cL’ > 0, cU’ < 0
(criterio di ottimalità)
Calcolo di una prima soluzione
Trasformare il problema ponendo x’ = x – l > 0 e quindi sostituendo x = x’ + l
minmin cx’ +
cxcl
Ax’Ax
= (d= –d Al) = d’
0 < lx’<<x u’
=u–l
<u
c
l
u’
2
0
3
a
–10
0
0
d’ = 0
0
4
6
1
2
3
4
5
6
7
10 8
0 0
9 6
b
c
5 7 6 10 12 4 3
0 0 0 1 0 2 0
5 10 4 9 9 9 5
d
e
f
g
h
i
j
5
0
9
–10
1
b
0
3
0
c
0
d
e
g
f
i
6
4
2
4
h
k
–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
k
5
j
7
6
0
Calcolo di una prima soluzione
Aggiungere i nodi s e t, collegarli alle sorgenti
e ai pozzi k con capacità pari a |dk|, trovare il
max (s, t)-flusso; se è < kP dk non c’è soluzione
s
Altrimenti, ricavare x = x’ + l (ammissibile)
x’
2
8
1
2
0
0 3 7
0 0
6
x
2
8
1
2
0
0 4 7
2 0
6
c
l
u’
2
0
3
10 8
0 0
9 6
5 7 6 10 12 4 3
0 0 0 1 0 2 0
5 10 4 9 9 9 5
5
0
9
a
–10
0
0
d’ = 0
0
4
6
1
2
3
4
5
6
7
b
c
d
e
f
g
h
i
j
10
1
b
8
0
3
1
c
0
0
e
g
3
f
i
6
4
2
2
d
4
7
h
k
–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
2
k6
j
7
t
5
6
0
Calcolo di una prima soluzione
Aggiungere i nodi s e t, collegarli alle sorgenti
e ai pozzi k con capacità pari a |dk|, trovare il
max (s, t)-flusso; se è < kP dk non c’è soluzione
–10
Altrimenti, ricavare x = x’ + l (ammissibile)
1
b8
x
c
l
u
2
2
0
3
a
d=
–10
0
0
–1
–2
4
6
1
2
3
4
5
6
7
8
1
10 8
0 0
8 6
b
c
2 0
0 4
7
2 0
5 7 6 10 12 4 3
0 0 0 1 0 2 0
5 10 4 10 9 11 5
d
e
f
g
h
i
j
a
2
6
5
0
9
0
3
1c
0
e
g
f
4
i2
6
7
2
4
7
h
k
–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
–1
d2
5
–2
6k
j
7
6
Calcolo di una prima base
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 lij e uij la x trovata non è di base
–10
lij < xij < uij per 7 > n – 1 variabili
n = 7, m = 11
1
b8
x
c
l
u
2
2
0
3
a
d=
–10
0
0
–1
–2
4
6
1
2
3
4
5
6
7
8
1
10 8
0 0
9 6
b
c
2 0
0 4
7
2 0
5 7 6 10 12 4 3
0 0 0 1 0 2 0
5 10 4 10 9 11 5
d
e
f
g
h
i
j
a
2
6
5
0
9
0
3
1c
0
e
g
f
4
i2
6
7
2
4
7
h
k
–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
–1
d2
5
–2
6k
j
7
6
Calcolo di una prima base
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
lij < xij < uij per 7 > n – 1 variabili
n = 7, m = 11
b8
x
2
1
8
9
c
l
u
2
0
3
10 8
0 0
9 6
a
d=
–10
0
0
–1
–2
4
6
1
2
3
4
5
6
7
b
1
2
c
2 0
1
2 0
6
5 7 6 10 12 4 3
0 0 0 1 0 2 0
5 10 4 10 9 11 5
5
0
9
d
e
0 4
f
g
7
h
i
j
3
2–
a
2
1c + 
d2 – 
2
4
7
h
e
g
k
–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
+
1
f
4
i2
6
6k
5
j
7
Calcolo di una prima base
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
lij < xij < uij per 7 > n – 1 variabili
n = 7, m = 11
1
b9
8
x
1
9
c
l
u
2
0
3
10 8
0 0
9 6
a
d=
–10
0
0
–1
–2
4
6
1
2
3
4
5
6
7
b
2
0
c
1 0
2 0
6
5 7 6 10 12 4 3
0 0 0 1 0 2 0
5 10 4 10 9 11 5
5
0
9
d
e
0 24
f
g
97
h
i
j
3
1
1c – 
2
2
2
d1
4
h
7 +7
e
g
f
4–
k
–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
2
i2
6
6k
5
j
7
Calcolo di una prima base
Nella soluzione ottenuta gli archi (viola) associati alle variabili strettamente
comprese tra lij e uij 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
1
b9
8
x
1
9
c
l
u
2
0
3
10 8
0 0
9 6
a
d=
–10
0
0
–1
–2
4
6
1
2
3
4
5
6
7
b
0
c
1 0
2 0
6
5 7 6 10 12 4 3
0 0 0 1 0 2 0
5 10 4 10 9 11 5
5
0
9
d
e
0 2
f
g
9
h
i
j
3
1
1
0c
2
2
d1
4
h
97
e
g
k
–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
2
f
4
2
i2
6
6k
5
j
7
Calcolo dei costi ridotti
Per ottenere il costo ridotto c’ = (c – cBAB–1A) non è necessario invertire AB.
Sia y = cBAB–1, cioè y risolve il sistema di n – 1 equazioni in n incognite
– yi + yj = cij
ij  B
Siccome righe e colonne di B possono essere permutate con una visita in postordine ricavando una matrice triangolare, il
1
b
a
sistema è di facile risoluzione
cB
7
3
1
2
4
6
5
5
8
2
5 10 4
k
c
a
d
g
3
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
2
c
i
y7 =
– y19
6= 5
y34 =
– –y34= 8
y12 =
– –y13= 2
y24 =
– –y21= 5
y46 =
– y44= 10
y6 =
– y14
5= 4
d
4
h
e
g
f
i
6
k
5
j
7
Per il potenziale d’ingresso y5 si sceglie un valore arbitrario (es., y5 = 10)
Calcolo dei costi ridotti
Servendosi di y si calcola ora il costo ridotto c’ = (c – yA) delle variabili
fuori base
ij  L  U
cij’ = cij + yi – yj
cb’ =
ch ’ =
ce’ =
cf ’ =
cj ’ =
cb + y1 – y3
ch + y3 – y6
ce + y5 – y2
cf + y4 – y5
cj + y5 – y7
=
=
=
=
=
Si ha xb = xh = 9
xe = xf = xj = 0
Quindi xb e xj sono
candidate a entrare
in base: scegliamo xb
10 – 3 + 4
12 – 4 – 14
7 + 10 + 1
6 + 4 – 10
3 + 10 – 19
y7 = 19
y3 = – 4
y1 = – 3
y2 = – 1
y4 = 4
y6 = 14
=
=
=
=
=
11
–6
18
0
–6
1
bb
a
3
2
c
d
4
h
e
g
f
i
6
k
5
j
7
Per il potenziale d’ingresso y5 si sceglie un valore arbitrario (es., y5 = 10)
Calcolo della nuova base
L’aggiunta dell’arco b genera un ciclo.
Lo si elimina con un pivot cercando di far diminuire il flusso su b
c
l
u
2
0
3
10 8
0 0
9 6
5 7 6 10 12 4 3
0 0 0 1 0 2 0
5 10 4 10 9 11 5
5
0
9
a
b
d
k
c
e
f
g
h
i
j
–10
9b–
Dalla tabella risulta
 = min{3 – 1, 9 – 0, 0 – 0, 5 – 1} = 0
Si ha xb = xh = 9
xe = xf = xj = 0
Quindi xb e xj sono
candidate a entrare
in base: scegliamo xb
3

1
1+
a
–1
0c– 
1d+ 
4
9h
e
g
f
2
i2
6
7
2
5
–2
6k
j
7
6
Calcolo della nuova base
L’aggiunta dell’arco b genera un ciclo.
Lo si elimina con un pivot cercando di far diminuire il flusso su b
c
l
u
2
0
3
10 8
0 0
9 6
5 7 6 10 12 4 3
0 0 0 1 0 2 0
5 10 4 10 9 11 5
5
0
9
a
b
d
k
c
e
f
g
h
i
j
–10
1
9b
Dalla tabella risulta
 = min{3 – 1, 9 – 0, 0 – 0, 5 – 1} = 0
La variabile xb è entrata in base con valore 9,
la variabile xc è uscita dalla base con valore 0
I flussi non sono stati alterati, perché le basi
coinvolte nell’operazione sono degeneri
7
Proviamo allora a far entrare in base xj, il
cui flusso può crescere con costo ridotto –16
a
1
1
–1
3
c0
2
11
d
4
9h
e
g
f
2
i2
6
5
–2
6k
j
7
6
Calcolo della nuova base
Il flusso nell’arco i deve decrescere, e così quello nell’arco k.
c
l
u
2
0
3
10 8
0 0
9 6
5 7 6 10 12 4 3
0 0 0 1 0 2 0
5 10 4 10 9 11 5
5
0
9
a
b
d
k
c
e
f
g
h
i
j
–10
1
9b
Dalla tabella di soglie e capacità si ha
 = min{2 – 2, 5 – 0, 6 – 0} = 0
a
1
1
–1
3
c
11
d
4
9h
L’arco i ha infatti soglia 2, pari al flusso
attuale: ancora una volta la distribuzione
è inalterata
e
g
f
2
i2
6
7
2
6k – 
5
j 
0+
7
6
–
–2
Calcolo della nuova base
Il flusso nell’arco i deve decrescere, e così quello nell’arco k.
c
l
u
2
0
3
10 8
0 0
9 6
5 7 6 10 12 4 3
0 0 0 1 0 2 0
5 10 4 10 9 11 5
5
0
9
a
b
d
k
c
e
f
g
h
i
j
–10
1
9b
Dalla tabella di soglie e capacità si ha
 = min{2 – 2, 5 – 0, 6 – 0} = 0
L’arco i ha infatti soglia 2, pari al flusso
attuale: ancora una volta la distribuzione
è inalterata
Il calcolo dei costi ridotti offre ora cf’ = –6
con xf fissata alla soglia uf = 0
a
1
1
–1
3
c
11
d
4
9h
e
g
f
2
i2
6
7
2
5
–2
6k
0j
7
6
Calcolo della nuova base
Il flusso nell’arco i deve decrescere, e così quello nell’arco k.
c
l
u
2
0
3
10 8
0 0
9 6
5 7 6 10 12 4 3
0 0 0 1 0 2 0
5 10 4 10 9 11 5
5
0
9
a
b
d
k
c
e
f
g
h
i
j
–10
1
9b
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
a
1
1
–1
3
c
11
d
4
9h
e
2 –2
0+
g
f
i2
6
7
2
6 6–k 
5
0 j+ 
7
6
–2
Calcolo della nuova base
Il flusso nell’arco i deve decrescere, e così quello nell’arco k.
c
l
u
2
0
3
10 8
0 0
9 6
5 7 6 10 12 4 3
0 0 0 1 0 2 0
5 10 4 10 9 11 5
5
0
9
a
b
d
k
c
e
f
g
h
i
j
–10
1
9b
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
a
1
1
–1
3
c
11
d
4
9h
i2
6
7
e
1f
1g
L’arco g esce di base fissando il proprio
flusso al valore di soglia 1
2
5
–2
5k
1j
7
6