Gestione della produzione e della supply chain Logistica ...detti/MinimumCostFlow1.pdf · Gestione...

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



Struttura logistica ad assemblaggio

1

7

3

2

4

5 6

8


Struttura logistica arborescente (rete di distribuzione)

6

2

7

3

4

8 5

1


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


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


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



⎪⎩

⎪⎨

⎧

∈∀−

∈∀


)( )(

)(),()(),(

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 ,),(),(


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)


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


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


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)


Condizione di ammissibilità La somma delle capacità produttive (600) eccede la somma delle domande (580)

1

2

3

4

5

6

7



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


Condizione di ammissibilità La somma delle capacità produttive (600) eccede la somma delle domande (580)

1

2

3

4

5

6

7



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


Formulazione con Excel

Soluzione ottima del Problema

1

2

3

4

5

6

7



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


∑∈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


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



⎪⎩

⎪⎨

⎧

∈∀−

∈∀


)( )(

)(),()(),(

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


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


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


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)


È 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)


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


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


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


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


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.


È 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


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


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.


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


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


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


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


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'


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


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),(

*

),(''


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.


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)()(' ππ


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


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


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


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)


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


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


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


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)}


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


-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


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)}


Trovata una soluzione ottima

Gestione della produzione e della supply chain Logistica ...detti/MinimumCostFlow1.pdf · Gestione...

Documents

Transcript of Gestione della produzione e della supply chain Logistica ...detti/MinimumCostFlow1.pdf · Gestione...