Post on 08-Jul-2020
Paolo Detti Dipartimento di Ingegneria dell’Informazione e Scienze
Matematiche Università di Siena
Gestione della produzione e della supply chain
Logistica distributiva
Struttura delle reti logistiche
Sistemi produttivi multistadio Struttura logistica lineare
1 2 3 4
2 3 1
Sist. prod. / Fornitore
Sist. prod. / Fornitore
Sist. prod. / Fornitore
Struttura logistica ad assemblaggio
1
7
3
2
4
5 6
8
Struttura delle reti logistiche
Struttura logistica arborescente (rete di distribuzione)
6
2
7
3
4
8 5
1
Struttura delle reti logistiche
Costi in logistica
• Costo per l’acquisizione dei materiali (soggetto a sconti e incertezze sul valore futuro) • Costi di ordinazione • Costi di mantenimento o perdita del valore delle scorte • Costi fissi e variabili di trasporto • Costi per la realizzazione di impianti e centri di distribuzione • Costi legati alla movimentazione dei materiali nei magazzini
Progetto di reti logistiche e trasporti
• Determinare la struttura di una rete logistica significa dimensionare impianti di produzione, centri di distribuzione, punti vendita, flussi dei materiali. • Il problema si pone ad un livello strategico. Tuttavia, il problema può porsi ad un livello tattico, nel caso in cui sia possibile acquisire risorse (mezzi di trasporto, siti di stoccaggio, ecc…) in affitto da fornitori di servizi logistici.
La Teoria dei Grafi costituisce, al pari della Programmazione Matematica, un corpo metodologico per la modellazione e soluzione di problemi decisionali Molti problemi di ottimizzazione hanno una naturale rappresentazione grafica. Sono note efficienti tecniche risolutive basate sui Grafi.
Teoria dei grafi
Origini
La Teoria dei Grafi è stata introdotta dal matematico svizzero Eulero (1707 - 1783) che formulò utilizzando i grafi il problema dei ponti di Könisberg (città Prussiana): Partendo da una qualsiasi area di terra è possibile tornare al punto di partenza attraversando tutti i ponti una ed una sola volta?
C
A D
B
Fiume Pregel
Se si associano alle zone di terra dei punti (nodi o vertici) e ai ponti dei tratti di linea (archi o spigoli) il problema dei ponti di Könisberg è modellato dal Grafo
D
B
A
C
Eulero si servì di questo grafo per stabilire che era impossibile trovare il percorso richiesto, con i ponti così distribuiti. E’ invece possibile se il numero di archi incidente in ogni nodo è pari.
Definizioni
Un grafo G=(V,E) è definito da: • un insieme V di nodi; • un insieme E di archi. Un grafo si dice orientato se gli archi hanno un orientamento altrimenti si dice non orientato
D
B
A
C
D
B
A
C
Definizioni (grafi non orientati)
Dato l’arco e=(a, b) • a, b sono detti i nodi estremi di e • e è detto arco incidente in a e b • a, b sono detti nodi adiacenti • due archi si dicono adiacenti se hanno un nodo in comune
b
a
Dato il nodo a di G • l’Intorno di a, indicato con N(a), è l’insieme dei nodi adiacenti ad a • la stella di a, indicata con δ(a), è l’insieme degli archi incidenti in a
1
2
3
4
5
N(1) = {2, 3} δ(3) = {(1,3), (3,4), (3,5)}
Definizioni (grafi orientati)
Dato un nodo a di un grafo orientato G • δ+(a) è l’insieme degli archi uscenti da a • δ-(a) è l’insieme degli archi entranti in a • un nodo con soli archi entranti è detto pozzo • un nodo con soli archi uscenti è detto sorgente
1
2
3
4
5
δ+(5) = {(5,3), (5,4)} δ-(2) ={(0,2), (1,2)}
Dato un arco orientato e=(a, b) • e è detto arco uscente da a (nodo coda) • e è detto arco entrante in b (nodo testa) • a si dice predecessore diretto di b • b si dice successore diretto di a
b
a
0
Definizioni
1
2
3
4
5
Dato un Grafo G=(V, E) con V={v1, …, vn} ed E={e1, …, em} un cammino è una sequenza di archi p={eh1, eh2, …, ehq}, tali che ogni due archi consecutivi sono adiacenti
0 1
2
3
4
5
0
Definizioni
Un cammino è detto semplice se gli archi e i nodi del cammino sono tutti distinti altrimenti si dice non semplice
1
2
3
4
5
0 1
2
3
4
5
0
un cammino è orientato se per ogni arco e=(i, j) del cammino, il nodo i è la coda di e ed il nodo j è la testa di e
2
4
5
0
Definizioni
Un cammino è detto chiuso se i nodi estremi del cammino coincidono Un cammino semplice e chiuso è detto ciclo
1
2
3
4
5
0
Un Grafo G si dice connesso se per ogni coppia di nodi a e b esiste un cammino da a a b
1
2
3
4
5
0 1
2
3
4
5
0
Definizioni
Un ciclo orientato
1
2
3
4
5
0
Un ciclo non orientato
1
2
3
4
5
0
Definizioni
Un cammino chiuso in un grafo è detto ciclo Euleriano se passa una ed una sola volta su tutti gli archi del grafo. Un ciclo Euleriano può non esistere in un grafo.
D
B
A
C
1
2
3
4
5
0
Grafo non Euleriano Grafo Euleriano
Definizioni
Un ciclo in un grafo è detto ciclo Hamiltoniano se passa una ed una sola volta su tutti i nodi del grafo. Un ciclo Hamiltoniano può non esistere in un grafo.
D
B
A
C
1
2
3
4
5
0
Grafi Hamiltoniani
Definizioni
Dato un grafo non orientato G=(V,A) e un sottoinsieme S di V Taglio in un grafo Una taglio δ (S) è l’insieme di archi con un estremo in S e l’altro in V\S
1
2
3
4
5
S= {1, 3} δ(S) = {(1,2), (3,4), (3,5)}
Definizioni
Dato un grafo G=(V,A) orientato e un sottoinsieme S di V Taglio in un grafo Il taglio δ+ (S) è l’insieme di archi con coda in S e testa in V\S Il taglio δ- (S) è l’insieme di archi con testa in S e coda in V\S
1
2
3
4
5
S ={0,1,3}δ+(S) = {(0,2),(1,2),(3,4)} δ-(S) ={(5,3)}
0
Definizioni
Grafo bipartito G=(V1, V2, A) L’insieme dei nodi V è divisibile in due sottoinsiemi V1 e V2 Non ci sono archi in A che collegano due nodi di V1 o due nodi di V2
4
3
2
1
5
Definizioni
Una foresta è un grafo senza cicli
1
2
3
4
5
0
1
2
3
4
5
0
Definizioni
Un Albero T=(V,A) è un grafo che soddisfa una delle seguenti definizioni: • è una foresta conessa • è connesso e non contiene cicli • è connesso ed ha |V|-1 archi • per ogni coppia di nodi esiste un solo cammino che li connette • è connesso e la rimozione di un arco lo rende disconnesso
1
2
3
4
5
0
Definizioni
Dato un grafo G=(V,A) una foresta ricoprente F =(V’,A’) di G è una foresta tale che V’=V
1
2
3
4
5
0
1
2
3
4
5
0
1
2
3
4
5
0
Definizioni
Dato un grafo G=(V,A) albero ricoprente T =(V’,A’)di G è un albero tale che V’=V
1
2
3
4
5
0
1
2
3
4
5
0
1
2
3
4
5
0
Il Problema del Flusso su Reti a Costo Minimo (Minimum Cost Network Flow)
Il problema di Flusso su Reti a Costo Minimo consiste nel determinare il modo più conveniente per trasportare una determinata quantità di bene da uno o più punti di produzione o immagazzinamento ad uno o più punti di consumo, attraverso una rete di trasporto data. Esistono algoritmi di soluzione estremamente efficienti per il calcolo della soluzione di Problemi di Flusso su Reti a Costo Minimo (più efficienti dei metodi utilizzati per la soluzione di problemi di PL generici).
Dati • Il grafo G=(V, E) della rete • Un insieme di nodi fornitori S⊂V e la quantità di bene disponibile a(i) per ogni i ∈ S • Un insieme di nodi domanda D⊂V e la quantità di bene richiesta b(i) per ogni i ∈ D • I costi unitari di trasporto cij, le capacità superiori uij e inferiori lij ad ogni arco (i,j) di E
Il Modello del Flusso su Reti a Costo Minimo (Minimum Cost Network Flow)
Il Problema Decidere quanto flusso inviare su ciascun arco in modo tale che • le capacità sugli archi siano rispettate • ad ogni nodo sia soddisfatto il bilanciamento del flusso:
• il costo totale del flusso sulla rete sia minimo
⎪⎩
⎪⎨
⎧
−=−
ltrimenti 0domanda nodo un è se )(
fornitore nodo un è se )( in entrante Flusso da uscente Flusso
aiib
iiaii
Il Modello del Flusso su Reti a Costo Minimo (Minimum Cost Network Flow)
1
2
3
4
5
6
7
Nodi fornitori Nodi domanda
a(1)=10 a(2)=15 a(3)=10
b(6)=20
b(7)=15
Il Modello del Flusso su Reti a Costo Minimo (Minimum Cost Network Flow)
i
j
lij, uij, cij
⎪⎩
⎪⎨⎧
+∞=
=
ij
ij
ul 0
10 10
10
5
10 10
Un esempio ed una soluzione ammissibile (i costi degli archi non sono riportati)
Il Modello del Flusso su Reti a Costo Minimo : Una formulazione di PL
Definizione delle variabili:
xij la quantità di flusso che scorre nell’arco (i,j), per ogni (i,j) ∈ E
Funzione obiettivo:
∑∈Eji
ijij xc),(
min
Upper bound sulle variabili:
E(i,j) ux ijij ∈∀≤
Lower bound sulle variabili:
E(i,j) lx ijij ∈∀≥
Vincolo sul bilanciamento del flusso:
⎪⎩
⎪⎨
⎧
∈∀−
∈∀
=− ∑∑−+ ∈∈ altrimenti 0
)( )(
)(),()(),(
DiibSiia
xxiijji
ijiij
δδ
Condizione: affinché il problema abbia una soluzione ammissibile deve essere:
∑∑∈∈
=DiSiibia )()(
∑∈Eji
ijij xc),(
min
E(i,j) ux ijij ∈∀≤
E(i,j) lx ijij ∈∀≥
⎪⎩
⎪⎨
⎧
∈∀−
∈∀
=− ∑∑−+ ∈∈ altrimenti 0
)( )(
)(),()(),(
DiibSiia
xxiijji
ijiij
δδ
Formulazione complessiva
Proprietà: La matrice dei coefficienti è Totalmente Unimodulare (matrice di incidenza di un grafo diretto e matrici identità) Se le quantità sono intere allora esiste un flusso ottimo x* intero (calcolabile).
ijij ulibia ,),(),(
Il Modello del Flusso su Reti a Costo Minimo (Minimum Cost Network Flow)
Metodi di soluzione: • In pratica, un problema di flusso su reti a costo minimo può
essere risolto con algoritmi combinatori estremamente efficienti (polinomiali), che sfruttano la struttura della rete.
• Inoltre, esiste una versione del metodo del simplesso, nota con il nome di simplesso su reti, messa a punto proprio per la soluzione di problemi di flusso su reti a costo minimo.
Ottimizzazione dei costi di trasporto e dimensionamento della capacità produttiva
Descrizione del problema Un’industria alimentare produce alimenti in 3 diversi impianti. Gli alimenti una volta prodotti possono essere trasportati direttamente a 2 diversi clienti, oppure trasportati e stoccati in 2 magazzini e poi consegnati ai clienti.
Dati Il costo di produzione è lo stesso per ogni impianto. Il costo di stoccaggio è lo stesso per ogni magazzino. Ogni impianto ha una capacità produttiva limitata. E’ nota la domanda di alimenti di ogni cliente. Sono dati i costi di trasporto e produzione/stoccaggio, per tonnellata di alimenti, tra ogni coppia di punti. Possono essere trasportate al più 200 tonnellate di alimenti tra ogni coppia di punti.
Obiettivo L’industria vuole decidere quanto produrre in ogni impianto e quanto stoccare in ogni magazzino, in modo tale che il costo totale di trasporto dagli impianti verso i clienti sia minimo e la domanda dei clienti sia soddisfatta.
Impianti Clienti
Capacità (ton per anno) Domande (ton per anno)
200 300 100
400
180
Magazzino 1 Magazzino 2 Cliente 1 Cliente 2Impianto 1 2,0 1,0 2,0 4,0Impianto 2 1,0 1,0 8,0 9,0Impianto 3 1,0 0,5 10,0 8,0Magazzino 1 - - 5,0 1,0Magazzino 2 - - 2,0 7,0
Costi di trasporto e produzione/stoccaggio (migliaia di Euro per ton)
Ottimizzazione dei costi di trasporto e dimensionamento della capacità produttiva
Il problema può essere modellato con un grafo orientato, associando un nodo ad ogni impianto, magazzino e cliente. Un arco orientato esprime il fatto che può essere trasportata una certa quantità di alimenti tra i due nodi estremi dell’arco.
1
2
3
4
5
6
7
Impianti Magazzini Clienti
Capacità (ton per anno) Domande (ton per anno)
200 300 100
400
180
Ad ogni nodo impianto è associato un valore pari alla capacità produttiva Ad ogni nodo cliente è associato un valore pari alla domanda
Ottimizzazione dei costi di trasporto e dimensionamento della capacità produttiva
Ad ogni arco (i,j) del grafo sono associati una capacità uij, un costo di trasporto e produzione cij per tonnellata (per gli archi uscenti dagli impianti) ed un costo di trasporto e stoccaggio cij per tonnellata (per gli archi uscenti dai magazzini). i
j
uij, cij
uij = 200 per ogni arco
Magazzino 1 Magazzino 2 Cliente 1 Cliente 2Impianto 1 2,0 1,0 2,0 4,0Impianto 2 1,0 1,0 8,0 9,0Impianto 3 1,0 0,5 10,0 8,0Magazzino 1 5,0 1,0Magazzino 2 2,0 7,0
Costi di trasporto e produzione/stoccaggio (migliaia di Euro per ton)
Ottimizzazione dei costi di trasporto e dimensionamento della capacità produttiva
Condizione di ammissibilità La somma delle capacità produttive (600) eccede la somma delle domande (580)
1
2
3
4
5
6
7
Impianti Magazzini Clienti
Capacità (ton per anno) Domande (ton per anno)
200 300 100
400
180
Si introduce un nodo domanda fittizio con valore 600-580=20 connesso ai nodi fornitori con archi di capacità pari a 20 e costo nullo
Ottimizzazione dei costi di trasporto e dimensionamento della capacità produttiva
Condizione di ammissibilità La somma delle capacità produttive (600) eccede la somma delle domande (580)
1
2
3
4
5
6
7
Impianti Magazzini Clienti
Capacità (ton per anno) Domande (ton per anno)
200 300 100
400
180
Si introduce un nodo domanda fittizio con valore 600-580=20 connesso ai nodi fornitori con archi di capacità pari a 20 e costo nullo
8 20
Ottimizzazione dei costi di trasporto e dimensionamento della capacità produttiva
Formulazione con Excel
Soluzione ottima del Problema
1
2
3
4
5
6
7
Impianti Magazzini Clienti
Capacità (ton per anno) Domande (ton per anno)
200 300 100
400
180
8 20
200
180 180
200 20 100
100
Costo di trasporto complessivo: 1310 mila Euro
Siano dati • un grafo orientato G=(V, E) • un costo cij associato ad ogni arco (i, j) • una coppia di nodi s e t il problema consiste nel trovare un cammino semplice orientato da s a t la cui somma dei costi degli archi ha valore minimo.
Il problema del Cammino di costo minimo su grafi
1
3
1 t
3
s
2 2
1
3
Se si associa: • un valore a(s)=1 al nodo s; • un valore b(t)=1 al nodo t; • una capacità inferiore pari a 0 ad ogni arco di E; • una capacità superiore pari a 1 ad ogni arco di E. Il problema di trovare un cammino minimo da s a t può essere visto come caso particolare di problema di Flusso a costo minimo, con un solo nodo fornitore (s) ed un solo nodo domanda (t).
Il problema del Cammino di costo minimo modellato come problema di Flusso su reti a costo minimo
1
3
1 b(t)=1 t
3 a(s)=1 s
2 2
1
3
Siano dati • un grafo orientato bipartito G=(A,B,E) • A, insieme dei nodi fornitori • B, insieme dei nodi domanda • una quantità disponibile bi per ogni nodo fornitore in A • una quantità richiesta di per ogni nodo domanda in B • un costo unitario di trasporto cij associato ad ogni arco (i, j) di E Il problema Il problema consiste nel determinare quanto trasportare su ciascun arco in modo da soddisfare la domanda e minimizzare i costi di trasporto.
Il problema dei trasporti
Definizione delle variabili:
xij la quantità di flusso che scorre nell’arco (i,j), per ogni (i,j) ∈ E
Il problema dei trasporti
∑∈Eji
ijij xc),(
min
E(i,j) xij ∈∀≥ 0
xijj∈B∑ ≤ bi ∀i ∈ A
xiji∈A∑ ≥ d j ∀j ∈ B
1
2
3
4
5
Nodi domanda Nodi fornitore
b1 b2 b3
Il problema dei trasporti
d1 d2
min cij xij( i , j )∈E∑
xijj∈B∑ ≤ bi ∀i ∈ A
xiji∈A∑ ≥ d j ∀j ∈ B
xij ≥ 0 ∀(i, j)∈ EProprietà: La matrice dei coefficienti è Totalmente Unimodulare (matrice di incidenza di un grafo bipartito) Se le quantità bi e dj sono intere allora esiste un flusso ottimo x* intero.
∑∈Eji
ijij xc),(
min
E(i,j) ux ijij ∈∀≤
E(i,j) lx ijij ∈∀≥
⎪⎩
⎪⎨
⎧
∈∀−
∈∀
=− ∑∑−+ ∈∈ altrimenti 0
)( )(
)(),()(),(
DiibSiia
xxiijji
ijiij
δδ
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Flusso lungo un arco: Il flusso di un arco aumenta se esso è percorso in modo concorde al verso dell’arco Il flusso di un arco diminuisce se esso è percorso in modo discorde al verso dell’arco
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Idea: A partire da un flusso ammissibile sulla rete, l’idea alla base del simplesso su reti è quella di migliorare la soluzione di partenza aumentando il flusso in cicli con costo unitario negativo, o diminuendo il flusso in cicli con costo unitario positivo.
2
5
3
4
1 (5,2)
(4,3)
(3,4)
(4,3)
(2,1)
i j (xij, cij)
2
5
3
4
1 (5,5)
(4,3)
(3,4)
(4,3)
(2,1)
i j (xij, cij)
Ciclo con costo negativo: 2-4+1+3-3= -1
Ciclo con costo positivo: 5-4+1+3-3= 2
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Definizioni Dato un flusso ammissibile x sulla rete G, un arco (i,j) è detto • libero se lij < xij < uij • vincolato se xij = lij oppure xij = uij
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Definizioni Dato un flusso ammissibile x sulla rete G, un arco (i,j) è detto • libero se lij < xij < uij • vincolato se xij = lij oppure xij = uij Soluzione senza cicli (cycle free solution): un flusso ammissibile x tale che in ogni ciclo (non orientato) della rete esiste almeno un arco vincolato Soluzione ad albero ricoprente (spanning tree solution): dato un albero ricoprente T di G, un flusso ammissibile x tale che ogni arco che non appartiene a T è vincolato (gli archi di G che appartengono a T possono essere liberi o vincolati)
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
È possibile mostrare che un problema di flusso a costo minimo ammette sempre una soluzione ottima senza cicli e ad albero ricoprente.
Soluzione senza cicli (cycle free solution): un flusso ammissibile x tale che in ogni ciclo della rete esiste almeno un arco vincolato Soluzione ad albero ricoprente (spanning tree solution): dato un albero ricoprente T di G, un flusso ammissibile x tale che ogni arco che non appartiene a T è vincolato (gli archi di G che appartengono a T possono essere liberi o vincolati)
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
E’ sempre possibile trasformare una soluzione ammissible in una soluzione senza cicli
2
5
3
4
1 (5,2)
(4,3)
(3,4)
(4,3)
(2,1)
i j (xij, cij)
Esempio: Ciclo con costo negativo Tutti gli archi con capacità massima infinita e capacità minima 0
Costo del ciclo per flusso unitario D: 2-4+1+3-3= -1
2
5
3
4
1 5+a
4-a
3-a
4+a
2+a
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Aumentando a il costo nel ciclo diminuisce. a può essere aumentato fin quando i flussi sugli archi si mantengono positivi (non negatività del flusso) (e non eccedono la capacità massima):
2
5
3
4
1 5+a
4-a
3-a
4+a
2+a
30403
≤⇒
≥−
≥−
aaa 2
5
3
4
1 8
1
0
7
5
Il flusso è ancora ammissibile, un arco è vincolato (ha ora flusso nullo), ed il costo della soluzione è diminuito
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
2
5
3
4
1 (5,5)
(4,3)
(3,4)
(4,3)
(2,1)
i j (xij, cij)
Esempio: Ciclo con costo positivo Tutti gli archi con capacità massima infinita e minima 0
Costo del ciclo per flusso unitario D: 5-4+1+3-3= 2
2
5
3
4
1 5+a
4-a
3-a
4+a
2+a
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Poiché diminuendo il flusso nel ciclo diminuisce il costo, il valore di a può essere diminuito il più possibile a condizione che i flussi sugli archi non diventino negativi (e che le capacità massime degli archi siano rispettate):
2
5
3
4
1 5+a
4-a
3-a
4+a
2+a
2040205
−≥⇒
≥+
≥+
≥+
aaaa 2
5
3
4
1 3
6
5
2
0
Il flusso è ancora ammissibile, un arco ha ora flusso nullo (è vincolato), ed il costo della soluzione è diminuito
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Dato un flusso ammissibile sulla rete, il procedimento sopra descritto si può applicare a tutti i cicli della rete, anche ai cicli con costo unitario nullo (in questo caso non avremo nessun miglioramento della soluzione), per portare il flusso di un arco del ciclo al valore 0, ottenendo quindi una soluzione ammissibile senza cicli. Se assumiamo lower bound diversi da 0 ed upper bound finiti sulle variabili xij, è possibile con ragionamenti analoghi modificare i flussi sugli archi in modo da non peggiorare la soluzione, mantenere l’ammissibilità e portare il flusso su un arco del ciclo al suo valore minimo (lij) o massimo (uij) Applicando il ragionamento a tutti i cicli della rete si ottiene il seguente risultato. Teorema Se la funzione obiettivo di un problema di flusso a costo minimo non è illimitata inferiormente, esiste sempre una soluzione ottima senza cicli.
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
È possibile convertire una soluzione senza cicli in una soluzione ad albero ricoprente Infatti, data una soluzione senza cicli, possono accadere due cose: 1. Il grafo che si ottiene eliminando tutti gli archi vincolati è connesso: soluzione ad albero ricoprente 2. Il grafo che si ottiene eliminando tutti gli archi vincolati non è connesso: foresta ricoprente Nel caso 2, è possibile aggiungere archi vincolati alla foresta ed ottenere una soluzione ad albero ricoprente
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Nel caso 2, è possibile aggiungere archi vincolati alla foresta ed ottenere un soluzione ad albero ricoprente
2
5
3
4
1 (2,3)
(1,2)
(4,4)
(0,5)
(1,6)
i j
(xij, uij), lij=0
(1,1) (3,3)
2
5
3
4
1
2
5
3
4
1
2
5
3
4
1
Soluzioni ad alberi ricoprenti 2
5
3
4
1
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Si ottiene quindi il seguente risultato. Teorema Se la funzione obiettivo di un problema di flusso a costo minimo non è illimitata inferiormente, esiste sempre una soluzione ottima ad albero ricoprente per il problema.
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Data una soluzione ad albero ricoprente, gli archi in A della rete G possono suddividersi in tre categorie: 1. Gli archi appartenenti all’albero T 2. Gli archi non appartenenti all’albero il cui flusso è pari alla capacità minima (insieme L) 3. Gli archi non appartenenti all’albero il cui flusso è pari alla capacità massima (insieme U)
E’ possibile ottenere una (unica) soluzione ad albero ricoprente conoscendo la struttura T,L,U (ammissibile). Basta porre • xij=lij per ogni (i,j) in L • xij=uij per ogni (i,j) in U • calcolare il flusso sugli altri archi di T attraverso le condizioni di bilanciamento dei nodi
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Diremo che la struttura di un albero ricoprente T,L,U è ammissibile se la relativa soluzione ad albero rispetta i bound di ciascun arco della rete G
Data una soluzione ad albero ricoprente, diremo che l’albero
relativo T è non degenere se tutti gli archi in T sono liberi, altrimenti l’albero si dice degenere
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Data una struttura ad albero ricoprente T,L,U E’ possibile calcolare un flusso ammissibile sugli archi di T Per semplicità, assumiamo che tutti gli archi abbiano upper bound infinito e lower bound 0 (gli archi non in T sono in L e quindi hanno flusso 0). Dato un arco, siano T1 e T2 i due sottoalberi ottenuti eliminando l’arco.
2
5
3
4
1
a(1)=10
a(2)=15 b(3)=5
b(4)=20 2
5
3
4
1
a(1)=10
a(2)=15 b(3)=5
b(4)=20
x53=10 a(i)−b(i)( )i∈T1
∑ + a(i)−b(i)( )i∈T2
∑ = 0
T1
T2
Si noti che deve essere:
a(5)=b(5)=0
a(5)=b(5)=0
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
u25=4
u12=3
In modo simile è possibile calcolare il flusso anche nel caso in cui la capacità massima degli archi sia finita (supponiamo che gli archi (1,2) e (2,5) siano in U)
2
5
3
4
1
a(1)=10
a(2)=15 b(3)=5
b(4)=20 2
5
3
4
1
a(1)=10
a(2)=15
b(3)=5
b(4)=20
x53=11
T1
T2
a(5)=b(5)=0
a(5)=b(5)=0
4 3
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Test di ottimalità per una soluzione ad albero ricoprente Definiamo per ogni arco di G un costo ridotto nel seguente modo: Dove π(i) è detto potenziale al nodo i Teorema La struttura di un albero ricoprente T,L,U è ottima per il problema di flusso a costo minimo se è ammissibile e se esiste una scelta dei potenziali dei nodi π(i) tale che:
Ajijicc ijij ∈∀+−= ),( )()(' ππ
UjicLjicTjic
ij
ij
ij
∈∀≤
∈∀≥
∈∀=
),( 0'),( 0'),( 0'
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
transito di nodo se 0domanda nodo se )()(
fornitore nodo se )()(
iiibiiiai
ππ−
Teorema La struttura di un albero ricoprente T,L,U è ottima per il problema di flusso a costo minimo se è ammissibile e se esiste una scelta dei potenziali dei nodi π(i) tale che:
UjicLjicTjic
ij
ij
ij
∈∀≤
∈∀≥
∈∀=
),( 0' .3),( 0' .2),( 0' .1
Dim Sia x* la soluzione associata alla struttura T,L,U e supponiamo che esistano dei potenziali ai nodi che soddisfano le condizioni 1-3. Si noti che minimizzare cij xij
( i , j )∈A∑ equivale a
minimizzare c 'ij xij( i , j )∈A∑ =
=min (cij −π (i)+π ( j))xij( i , j )∈A∑ =min cij xij +
( i , j )∈A∑ − π (i)xij
( i , j )∈δ ( i )+∑ + π (i)x ji
( j ,i )∈δ ( i )−∑
⎛
⎝⎜⎜
⎞
⎠⎟⎟
i∈V∑
costante
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
UjicLjicTjic
ij
ij
ij
∈∀≤
∈∀≥
∈∀=
),( 0' .3),( 0' .2),( 0' .1
Dim (segue) Dalle condizioni
Si ha
min c 'ij xij( i , j )∈A∑ =min c 'ij xij
( i , j )∈L∑ − | c 'ij | xij
( i , j )∈U∑
Consideriamo una qualsiasi soluzione ammissibile x per il problema. Dalla definizione di x* si ha e quindi:
c.d.d.
Ujiuxx
Ljilxx
ijijij
ijijij
∈∀=≤
∈∀=≥
),(
),( *
*
∑∑∈∈
≥Aji
ijijAji
ijij xcxc),(
*
),(∑∑∈∈
≥Aji
ijijAji
ijij xcxc),(
*
),(''
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Idea dell’algoritmo: • Il simplesso su reti è un algoritmo iterativo che passa da una struttura ad albero ricoprente ad un’altra, e termina quando viene individuata una struttura ottima. • Ad ogni iterazione l’algoritmo sostituisce un arco dell’albero ricoprente con un altro non appartenente all’albero:
• L’arco che entra a far parte dell’albero è un arco che viola la condizione di ottimalità. • Aggiungendo tale arco all’albero, si viene a formare un ciclo con costo unitario negativo (ciclo negativo). • Il flusso lungo il ciclo viene aumentato finché qualche arco non raggiunge la sua capacità minima o massima. • Uno di questi archi con capacità minima o massima è rimosso, producendo una nuova struttura ad albero.
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Data una struttura ad albero ricoprente T,L,U l’algoritmo calcola come prima cosa i potenziali ai nodi in modo da soddisfare la condizione Come? Si noti che aggiungere una costante k a tutti i potenziali non modifica i costi ridotti
Al nodo 1 può essere assegnato un potenziale 0 • I potenziali di tutti gli altri nodi sono calcolati in modo tale che
Tjic ij ∈∀= ),( 0'
])([])([)()(' kjkicjicc ijijij +++−=+−= ππππ
Tjijicc ijij ∈∀=+−= ),( 0)()(' ππ
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
2
5
3
4
1
2
4
5 1
Esempio: calcolo dei potenziali ai nodi a partire da una struttura ad albero ricoprente T,L,U, in modo tale che: Tjijicc ijij ∈∀=+−= ),( 0)()(' ππ
................3)3(0)3(21)3()5(2)5(0)5(02)5()1(
0)1(
53
15
−=⇒=++=+−
−=⇒=+−=+−
=
ππππ
ππππ
π
cc
Teorema Se nel problema di flusso a costo minimo tutti i costi degli archi sono interi allora esiste una soluzione ottima in cui i potenziali dei nodi π(i) sono tutti interi.
i j cij
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Algoritmo: simplesso su reti • calcola una struttura ad albero T,L,U ammissibile
• calcola il relativo potenziale ai nodi π ed il flusso x su ogni arco della rete
• controlla la condizione di ottimalità while (esiste un arco non in T che viola la condizione di ottimalità) begin
• seleziona un arco che viola la condizione di ottimalità, da far entrare nell’albero • determina l’arco da rimuovere dall’albero • aggiorna la struttura T,L,U e calcola il relativo potenziale ai nodi, π, ed il flusso x su ogni arco della rete • controlla la condizione di ottimalità
end
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Calcolo di una struttura ad albero ammissibile iniziale T,L,U (archi tutti con capacità minima 0) Supponiamo che fra ogni coppia di nodi esista un cammino diretto in cui ogni arco ha capacità infinita Data una rete G=(V,A) è sempre possibile rispettare questa condizione aggiungendo degli archi fittizi (1,j) e (j,1) per ogni nodo j di V\{1}, con capacità massima infinita e costo infinito (di fatto non saranno mai scelti in una soluzione ottima) Una struttura ad albero iniziale è ottenibile • aggiungendo in T l’arco (j,1) se il nodo j è un nodo fornitore (a(j)>0) o di transito (a(j)=b(j)=0) con un flusso pari ad a(j) • aggiungendo in T l’arco (1,j) se il nodo j è un nodo domanda (b(j)>0) con un flusso pari a b(j) • tutti gli altri archi sono inseriti nell’insieme L (a flusso nullo) • l’insieme U è vuoto
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Controllo dell’ottimalità della struttura ad albero T,L,U Dopo aver calcolato i potenziali ai nodi π(i) Possiamo controllare le condizioni di ottimalità:
UjicLjicTjic
ij
ij
ij
∈∀≤
∈∀≥
∈∀=
),( 0' .3),( 0' .2),( 0' .1
Se la struttura ad albero non rispetta queste condizioni, gli archi che possono essere scelti per entrare nell’albero sono: Diversi sono i criteri di selezione dell’arco entrante (pivot rule), e.g., Dantzig rule: seleziona l’arco con il massimo |c’ij|
0' con0' con
>∈
<∈
ij
ij
cU (i,j)cL (i,j)
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Calcolo dell’arco uscente dall’albero Sia (k,l) l’arco selezionato per entrare nell’albero Aggiungendo l’arco (k,l) all’albero si viene a creare esattamente un ciclo (pivot cycle) W Definiamo l’orientamento del ciclo W concorde con l’arco se (k,l) è in L e discorde se (k,l) è in U
2
3 4
6 5
7 8
(3,4)
(2,3)
(1,2)
(4,6)
(0,3)
(3,4)
(2,2)
(1,5) 9 1
(3,6) 1
i
j
(xij, uij)
(0,5) l k
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Calcolo dell’arco uscente dall’albero Il flusso del ciclo è aumentato (il flusso aumenta sugli archi concordi con l’orientamento del ciclo e diminuisce sugli archi discordi) fin quando il flusso su uno o più archi raggiunge il relativo lower o upper bound (blocking arcs). L’arco uscente è selezionato tra gli archi blocking. Diversi sono i criteri di selezione dell’arco uscente, e.g., seleziona il primo arco blocking incontrato scandendo la lista degli archi, oppure l’arco con costo max.
Ciclo di pivot archi blocking: (2,3), (7,5) e (6,4)
2
3 4
6 5
7 8
(4,4)
(1,3)
(0,2)
(3,6)
(1,3)
(4,4)
(1,2)
(2,5) 9 1
(3,6) 1
i
j
(xij, uij)
(1,5) l k
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Esempio a(1)=9, b(6)=9, tutti gli altri nodi sono di transito
-3
-2
-8
-5
0
(3,8)
(2,3)
(5,7)
(4,3)
(5,4)
i j
(cij, uij), lij=0
(2,2) (2,3)
-9
(4,6)
(3,5)
2
3
4
1
6 5
π(i) π(j)
1 6
4 5
i j xij
Siano dati T, L, U: calcolo dei potenziali e flussi
L={(2,3), (5,4)} U={(3,5), (4,6)}
3
2
3
4
1 6
5
................8)4(0)4(35)4()2(
2)3(0)3(02)3()1(3)2(0)2(03)2()1(
0)1(
24
13
12
−=⇒=++=+−
−=⇒=+−=+−
−=⇒=+−=+−
=
ππππ
ππππ
ππππ
π
ccc
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Calcolo arco entrante: c’35 =4+2-5=1>0, (3,5) in U , i l massimo incremento sul ciclo è 1, l’arco (2,5) diventa blocking ed esce (entra in U)
-3
-2
-8
-5
0 -9
2
3
4
1
6 5
3
π(i) π(j)
xij
1 6
4 5
i j
-3
-2
-8
-5
0 -9
2
3
4
1
6 5
π(i) π(j)
1 6
4 5
i j xij
3
3
02983)6()4('01524)5()2('
0855)4()5('0232)3()2('
4646
3535
5454
2323
>=−+=+−=
>=−+=+−=
>−+=+−=
>−+=+−=
ππ
ππ
ππ
ππ
cccccccc
L={(2,3), (5,4)} U={(3,5), (4,6)}
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Esempio Nuovo albero ricoprente
-3
-2
-8
-6
0 -10
2
3
4
1
7 5
π(i) π(j)
2 6
4 5
i j xij
2
L={(2,3), (5,4)} U={(2,5), (4,6)}
Calcolo dei potenziali: Tjijicc ijij ∈∀=+−= ),( 0)()(' ππ
10)6(0)6(64)6()5(6)5(0)5(24)5()3(
56
35
−=⇒=++=+−
−=⇒=++=+−
ππππ
ππππ
cc
Test di ottimalità:
01083)6()4('0632)5()2('0865)4()5('0232)3()2('
4646
2525
5454
2323
>−+=+−=
<−+=+−=
>−+=+−=
>−+=+−=
ππ
ππ
ππ
ππ
cccccccc
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
-3
-2
-8
-6
-10
2
3
4
1
7 5
2 π(i) π(j)
xij
5
6 4 5
i j
2
Nuovo arco entrante: c’46=3+8-10=1>0, il massimo incremento sul ciclo è 1, Gli archi (1,3) e (3,5) diventano blocking Scegliamo l’arco (3,5) che esce da T
(3,8)
(2,3)
(5,7)
(4,3)
(5,4)
i j
(cij, uij), lij=0
(2,2) (2,3)
(4,6)
(3,5) 2
3
4
1 6
5
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Esempio Nuovo albero ricoprente
-3
-2
-8
-7
0 -11
2
3
4
1
6 4
4
6 5 5
π(i) π(j)
i j xij
3
Calcolo dei potenziali: Tjijicc ijij ∈∀=+−= ),( 0)()(' ππ
7)5(011)5(4)4()2(11)6(0)6(83)6()4(8)4(0)4(35)4()2(
2)3(0)3(02)3()1(3)2(0)2(03)2()1(
0)1(
56
46
24
13
12
−=⇒=−−=+−
−=⇒=++=+−
−=⇒=++=+−
−=⇒=+−=+−
−=⇒=+−=+−
=
ππππ
ππππ
ππππ
ππππ
ππππ
π
ccccc
Test di ottimalità:
0875)4()5('0724)5()3('0732)5()2('0232)3()2('
5454
3535
2525
2323
>−+=+−=
<−+=+−=
<−+=+−=
>−+=+−=
ππ
ππ
ππ
ππ
cccccccc
L={(2,3), (5,4)} U={(2,5), (3,5)}
Un algoritmo per il problema del flusso su reti a costo minimo: il simplesso su reti
Trovata una soluzione ottima