1. ( punti 7 ) Siano dati un insieme di localizzazioni potenziali (nodi grandi) ed un insieme di clienti da servire (nodi piccoli). Il costo di afferenza di un cliente ad un impianto è indicato sul corrispondente arco mentre il costo di attivazione è indicato accanto alla localizzazione potenziale. Determinare, utilizzando l’algoritmo di ascesa duale, un “lower bound” del valore della soluzione ottima (che minimizza la somma dei costi di attivazione ed afferenza), una soluzione euristica e il corrispondente “gap”.

Modelli e Algoritmi della Logistica STUDENTE: Prova Scritta del 15/12/2003 B MATRICOLA:

2. ( punti 5 ) Descrivere e dimostrare la correttezza di un oracolo di separazione per le disequazioni “cover” di un problema di “knapsack”.

4. ( punti 4 ) Descrivere la formulazione ottima e l’oracolo di separazione per il problema del minimo grafo connesso s-t.

3. ( punti 7 ) Applicare poi l’oracolo di separazione e verificare se il punto (0,0,2/3,0,2/3) viola una

disequazione associata ad un “cover” del seguente

“knapsack” (indicando l’eventuale cover violato):7464 54321 xxxxx

6. ( punti 3 ) Derivare la formula dell’EOQ e Calcolare l’EOQ per un problema di scorte con i seguenti parametri: Domanda annuale 30; Costo unitario del bene 600; MARR= 4% ; Costo fisso = 40

2A

C

B

D

E

c

b

a

f

e

d

3

1

3

0

1

21

33

1

4

10

1

6

1

23

3

s0

1

0

0

11 2/3

1/3

1

1/3

1/30

1/3

0

0

t

5. (punti 4) Applicare l’oracolo descritto sopra e individuare una disequazione (appartenente alla formulazione ottima) violata dalla soluzione frazionaria mostrata a fianco (accanto ad ogni arco è indicato il valore della corrispondente componente della soluzione frazionaria)

 

1. ( punti 7 ) Siano dati un insieme di localizzazioni potenziali (nodi grandi) ed un insieme di clienti da servire (nodi piccoli). Il costo di afferenza di un cliente ad un impianto è indicato sul corrispondente arco mentre il costo di attivazione è indicato accanto alla localizzazione potenziale. Determinare, utilizzando l’algoritmo di ascesa duale, un “lower bound” del valore della soluzione ottima (che minimizza la somma dei costi di attivazione ed afferenza), una soluzione euristica e il corrispondente “gap”.

Modelli e Algoritmi della Logistica

Prova Scritta del 15/12/2003 B SOLUZIONE ESERCIZIO 1

2A

C

B

D

E

c

b

a

f

e

d

3

1

3

0

1

21

33

1

4

10

1

6

1

23

3

A B C D E

a 3 ∞ 0 ∞ ∞

b 1 0 4 ∞ ∞

c 3 1 ∞ ∞ ∞

d ∞ 3 ∞ ∞ 3

e ∞ 1 ∞ 2 3

f ∞ 1 3 1 ∞

SOLUZIONE 1. Definisco i costi (afferenza e attivazione)

2 6 1 2 1

Costi di afferenza [c]

Costi di attivazione [f]

 

Modelli e Algoritmi della Logistica

Prova Scritta del 15/12/2003 B SOLUZIONE ESERCIZIO 1

A B C D E

a 3 ∞ 0 ∞ ∞

b 1 0 4 ∞ ∞

c 3 1 ∞ ∞ ∞

d ∞ 3 ∞ ∞ 3

e ∞ 1 ∞ 2 3

f ∞ 1 3 1 ∞

2. Calcolo i vettori e

3

1

2

∞

1

2

2 6 1 2 1

3. Calcolo Vk/|m(k)|

1/1=1

1/1=1

2/1=2

1/2

1/1=1

2/2=1

4. Massimo in corrispondenza della riga c. Incremento di Vc le u corrispondenti ai minimi della riga c (uno solo!)

A B C D E

a 3 ∞ 0 ∞ ∞

b 1 0 4 ∞ ∞

c 3 1+2 ∞ ∞ ∞

d ∞ 3 ∞ ∞ 3

e ∞ 1 ∞ 2 3

f ∞ 1 3 1 ∞

 

Modelli e Algoritmi della Logistica

Prova Scritta del 15/12/2003 B SOLUZIONE ESERCIZIO 1

A B C D E

a 3 ∞ 0 ∞ ∞

b 1 0 4 ∞ ∞

c 3 1+2 ∞ ∞ ∞

d ∞ 3 ∞ ∞ 3

e ∞ 1 ∞ 2 3

f ∞ 1 3 1 ∞

5. Aggiorno i vettori e

3

1

∞

∞

1

2

2 4 1 2 1

6. Aggiorno Vk/|m(k)|

1/1=1

1/1=1

2/2=1

1/2

1/1=1

2/2=1

A B C D E

a 3 ∞ 0+1 ∞ ∞

b 1 0 4 ∞ ∞

c 3 1+2 ∞ ∞ ∞

d ∞ 3 ∞ ∞ 3

e ∞ 1 ∞ 2 3

f ∞ 1 3 1 ∞

7. Massimo in corrispondenza della riga a.

Incremento di Va le u corrispondenti ai minimi della riga a (uno solo)

 

Modelli e Algoritmi della Logistica

Prova Scritta del 15/12/2003 B SOLUZIONE ESERCIZIO 1

A B C D E

a 3 ∞ 0+1 ∞ ∞

b 1 0 4 ∞ ∞

c 3 1+2 ∞ ∞ ∞

d ∞ 3 ∞ ∞ 3

e ∞ 1 ∞ 2 3

f ∞ 1 3 1 ∞

8. Aggiorno i vettori e

2

1

∞

∞

1

2

2 4 0 2 1

9. Aggiorno Vk/|m(k)|

0/1=0

1/1=1

2/2=1

1/2

1/1=1

2/2=1

A B C D E

a 3 ∞ 0+1 ∞ ∞

b 1 0+1 4 ∞ ∞

c 3 1+2 ∞ ∞ ∞

d ∞ 3 ∞ ∞ 3

e ∞ 1 ∞ 2 3

f ∞ 1 3 1 ∞

10. Massimo in corrispondenza della riga b.

Incremento di Vb le u corrispondenti ai minimi della riga b (uno solo)

 

Modelli e Algoritmi della Logistica

Prova Scritta del 15/12/2003 B SOLUZIONE ESERCIZIO 1

A B C D E

a 3 ∞ 0+1 ∞ ∞

b 1 0+1 4 ∞ ∞

c 3 1+2 ∞ ∞ ∞

d ∞ 3 ∞ ∞ 3

e ∞ 1 ∞ 2 3

f ∞ 1 3 1 ∞

11. Aggiorno i vettori e

2

3

∞

∞

1

2

2 3 0 2 1

12. Aggiorno Vk/|m(k)|

0/1=0

2/2=1

2/2=1

1/2

1/1=1

2/2=1

A B C D E

a 3 ∞ 0+1 ∞ ∞

b 1+2 0+1+2 4 ∞ ∞

c 3 1+2 ∞ ∞ ∞

d ∞ 3 ∞ ∞ 3

e ∞ 1 ∞ 2 3

f ∞ 1 3 1 ∞

13. Massimo in corrispondenza della riga b.

Incremento di Vb le u corrispondenti ai minimi della riga b (due)

 

Modelli e Algoritmi della Logistica

Prova Scritta del 15/12/2003 B SOLUZIONE ESERCIZIO 1

14. Aggiorno i vettori e

2

1

∞

∞

1

2

0 1 0 2 1

15. Aggiorno Vk/|m(k)|

0/1=0

0/2=0

0/2=0

1/2

1/1=1

1/2

A B C D E

a 3 ∞ 0+1 ∞ ∞

b 1+2 0+1+2 4 ∞ ∞

c 3 1+2 ∞ ∞ ∞

d ∞ 3 ∞ ∞ 3

e ∞ 1+1 ∞ 2 3

f ∞ 1 3 1 ∞

16. Massimo in corrispondenza della riga e.

Incremento di Ve le u corrispondenti ai minimi della riga e (uno solo)

A B C D E

a 3 ∞ 0+1 ∞ ∞

b 1+2 0+1+2 4 ∞ ∞

c 3 1+2 ∞ ∞ ∞

d ∞ 3 ∞ ∞ 3

e ∞ 1 ∞ 2 3

f ∞ 1 3 1 ∞

 

Modelli e Algoritmi della Logistica

Prova Scritta del 15/12/2003 B SOLUZIONE ESERCIZIO 1

17. Aggiorno i vettori e

2

1

∞

∞

1

2

0 0 0 2 1

18. Aggiorno Vk/|m(k)|

0/1=0

0/2=0

0/2=0

0/2=0

0/1=0

0/2=0

A B C D E

a 3 ∞ 0+1 ∞ ∞

b 1+2 0+1+2 4 ∞ ∞

c 3 1+2 ∞ ∞ ∞

d ∞ 3 ∞ ∞ 3

e ∞ 1+1 ∞ 2 3

f ∞ 1 3 1 ∞

19. Tutte le righe sono bloccate. L’algoritmo si arresta.

A B C D E

a 3 ∞ 0+1 ∞ ∞

b 1+2 0+1+2 4 ∞ ∞

c 3 1+2 ∞ ∞ ∞

d ∞ 3 ∞ ∞ 3

e ∞ 1+1 ∞ 2 3

f ∞ 1 3 1 ∞

 

Modelli e Algoritmi della Logistica

Prova Scritta del 15/12/2003 B SOLUZIONE ESERCIZIO 1

20. Calcolo del vettore z (minimi di riga della matrice aggiornata)

1

3

3

3

2

1

zA B C D E

a 3 ∞ 0+1 ∞ ∞

b 1+2 0+1+2 4 ∞ ∞

c 3 1+2 ∞ ∞ ∞

d ∞ 3 ∞ ∞ 3

e ∞ 1+1 ∞ 2 3

f ∞ 1 3 1 ∞

0 0 0 2 1

LB=13

UB=Z({A,B,C})=9+6=15

2 6 1 2 1

A B C D E

a 3 ∞ 0 ∞ ∞

b 1 0 4 ∞ ∞

c 3 1 ∞ ∞ ∞

d ∞ 3 ∞ ∞ 3

e ∞ 1 ∞ 2 3

f ∞ 1 3 1 ∞

“gap”=15-13 = 2

Osservazione: A è inutile e può essere eliminato. In tal caso, la Soluzione diviene {B,C}, UB=13 e il “gap”=0

 

Valutazione Esercizio 1: -2 punti: se non viene scritta in modo corretto la matrice dei costi (con ∞ al posto giusto) -2 punti: se non viene calcolato l’UB come nelle pagine precedenti

-2 punti: per errori nell’applicazione dell’algoritmo • Ignorata la soluzione euristica calcolata con il “greedy” o con altro metodo

 

Modelli e Algoritmi della Logistica

Prova Scritta del 15/12/2003 B SOLUZIONE ESERCIZIO 2

2. ( punti 5 ) Descrivere e dimostrare la correttezza di un oracolo di separazione per le disequazioni “cover” di un problema di “knapsack”.

La dimostrazione è quella riportata nelle pagine 7,8 e 9 della Lezione 9

 

Modelli e Algoritmi della Logistica

Prova Scritta del 15/12/2003 B SOLUZIONE ESERCIZIO 3

3. ( punti 7 ) Applicare poi l’oracolo di separazione e verificare se il punto (0,0,2/3,0,2/3) viola una

disequazione associata ad un “cover” del seguente

“knapsack” (indicando l’eventuale cover violato):7464 54321 xxxxx

max (x*1 -1) u1 +(x*2 -1) u2 +(x*3 -1) u3 + (x*4 -1) u4 + (x*5 -1) u5

1. Definire il “knapsack” duale per la separazione approssimata:

u1 + 4u2 + 6u3 + u4 + 4u5 > 8

max (0-1) u1 +(0-1) u2 +(2/3 -1) u3 + (0-1) u4 + (2/3 -1) u5

u1 + 4u2 + 6u3 + u4 + 4u5 > 8

max -u1 -u2 -1/3u3 -u4 -1/3 u5 min u1 + u2 + 1/3u3 + u4 + 1/3 u5

u1 + 4u2 + 6u3 + u4 + 4u5 > 8

Risposta:

 

Modelli e Algoritmi della Logistica

Prova Scritta del 15/12/2003 B SOLUZIONE ESERCIZIO 3

2. Ordinamento delle variabili (rapporti valore/ingombro crescenti)

max -u1 -u2 -1/3u3 -u4 -1/3 u5 min u1 + u2 + 1/3u3 + u4 + 1/3 u5

u1 + 4u2 + 6u3 + u4 + 4u5 > 8

u1 u2 u3 u4 u5

1 1/4 1/18 1 1/12

u3 u5 u2 u1 u4

1/18 1/12 1/4 1 1

ordinamento

3. Soluzione del “knapsack duale” u3 u5 u2 u1 u4

1 1/2 0 0 0

4. Valore della soluzione (nel problema di massimizzazione!): -1/3-1/6=-1/2>-1

Il vettore dato è esterno alla formulazione “cover”

 

Modelli e Algoritmi della Logistica

Prova Scritta del 15/12/2003 B SOLUZIONE ESERCIZIO 3

5. Arrotondamento della soluzione:

u3 u5 u2 u1 u4

1 1/2 0 0 0

u°3 u°5 u°2 u°1 u°4

1 1 0 0 0

6. Valore della soluzione associata ad u°: (nel problema di massimizzazione!):

-1/3-1/3=-2/3>-1 u° è il vettore di incidenza di un “cover” violato

7. Il “cover” violato è: x3+x5 < 1

Arrotondamento

Valutazione Esercizio 3: -2 punti: se non viene calcolato l’ordinamento -2 punti: per errori nell’applicazione dell’oracolo

 

Modelli e Algoritmi della Logistica

Prova Scritta del 15/12/2003 B SOLUZIONE ESERCIZIO 4

4. ( punti 4 ) Descrivere la formulazione ottima e l’oracolo di separazione per il problema del minimo grafo connesso s-t.

xe 1 K taglio s-t xee E

PS =

e

• Calcola il taglio s-t di peso minimo K*

• Assegna peso ce=xe a ciascun arco e E^

e

• Se ce 1 xe xe 1e e

^^

• Se ce 1 xe e e

^ xPS^

xPS^

x̂Rn

ORACOLO DI SEPARAZIONE

Risposta:

 

Modelli e Algoritmi della Logistica

Prova Scritta del 15/12/2003 B SOLUZIONE ESERCIZIO 5

s0

1

0

0

11 2/3

1/3

1

1/3

1/30

1/3

0

0

t

5. (punti 4) Applicare l’oracolo descritto sopra e individuare una disequazione (appartenente alla formulazione ottima) violata dalla soluzione frazionaria mostrata a fianco (accanto ad ogni arco è indicato il valore della corrispondente componente della soluzione frazionaria)

s0

10

0

11

2/3

1/3

1

1/3

1/3

0

1/3

0

0

t

B

E

D

F

C

G

A

Il taglio ({s,A,B,C,D,E,F} ,{G,t}) è il taglio minimo (1/3)

La disequazione violata è: xCG+xDG+xFG+xFt > 1

Valutazione: punteggio massimo solo a chi ha verificato la minimalità del taglio (applicando Ford e Fulkerson o mostrando un flusso di valore 1/3)

Soluzione: Bisogna trovare il taglio di capacità minima nelgrafo dato. Le capacità sono le componenti della soluzione frazionaria

 

Modelli e Algoritmi della Logistica

Prova Scritta del 15/12/2003 B SOLUZIONE ESERCIZIO 6

vr

ADQ

0

* 2

6. ( punti 3 ) Derivare la formula dell’EOQ e Calcolare l’EOQ per un problema di scorte con i seguenti parametri: Domanda annuale 30; Costo unitario del bene 600; MARR= 4% ; Costo fisso = 40

24030

0.04600

24030

2400

24= = = 10

1. La derivazione è quella descritta nelle pagine 6 e 7 della Lezione 17

2. L’EOQ desiderata è:

Valutazione Esercizio 6: -1 punto: se non viene dimostrata la formula in modo chiaro ed esplicativo