1

Livellamento di oggetti scabrosi - ridistribuzione di risorse-min cost flow

1

6

2

-7

3

3

4

-3

5

5

Piano di livellamento: distribuzione della risorsa al minimo costo

nodi: livelli alti / bassi = offerta / domanda

arco (i,j): possibile collegamento (strade, cavi, canali, carrucole, ecc.)

cij : costo unitario (es. costo a carrucola, a cavo, a mc)

xij : quanta risorsa spostare da i a j

2

0

,...,1

min

ij

iSj iPkikiij

ijij

mni

x

bxx

xcn

1j

Modello matematico

3

IL PROBLEMA

BIBLIOTECA NUOVI LIBRI

LIBRERIA CON NUMERO LIMITATO DI RIPIANI

4

CRITERI DI COLLOCAMENTO

FREQUENZA DI RICHIESTA

LIBRI PIU’ RICHIESTI

RIPIANI PIU’ ACCESSIBILI

LIBRI MENO RICHIESTI

RIPIANI MENO ACCESSIBILI

5

bi

NODI DI OFFERTA>0

<0 NODI DI DOMANDA

LIBRI

RIPIANI

6

I COSTI

• TEMPO

• FATICA• FREQUENZA DI RICHIESTA

PIU’ GETTONATI

COSTO PIU’ BASSO

ALTEZZA DEI RIPIANI

7

UN SOLO COSTO PER OGNI RAMO

COME DETERMINARLO ?

8

LA SCELTA DEI COSTI

Ck= li + rj

COSTO RAMO=FREQUENZA+ACCESSIBILITÀ

i =1….m

j=1….n

k=1….p

m=# classi libri

n=# ripiani

p=# rami

9

ESEMPIO :

i =1

j=1….n

k=i*j

c1=l1+r1

c2=l1+r2

….

ck=l1+rn

10

l6l1 l2 l3 l4 l5

r1 r2 r3 r4 r5

Domanda uguale all’offerta

11

Domanda maggiore dell’offerta (95 posti, 70 libri)

NODO FITTIZIO

7 nodi di domanda 5 nodi di offerta

TUTTI GLI ARCHI CHE PARTONO DAL NODO l7 AVRANNO UN COSTO MOLTO ALTO (1000)

12

l1 l2 l3 l4 l5 l6 l7

r1 r3r2 r4 r5

costo 25102

Costo effettivo 25102 - 25000 = 102

13

Domanda minore dell’offerta (70 posti, 95 libri)

NODO FITTIZIO

6 nodi di domanda 6 nodi di offerta

TUTTI GLI ARCHI CHE ARRIVANO AL NODO r6

AVRANNO UN COSTO MOLTO ALTO (1000)

14

l1 l2 l3 l4 l5 l6

r1 r3r2 r4 r5

costo 25137

Costo effettivo 25137 - 25000 = 137

r6

15

BIBLIOTECA VATICANA (domanda uguale all’offerta)

•2500 LIBRI c=23442

•7000 LIBRI c=61322

•12000 LIBRI c=106413