Paniere con risposte aperte - Ricerca operativa 2 (2023/2024)

A B

1

2 D

C

LEZ 4

7. Dato il grafo di localizzazione in figura, determinare il costo della soluzione ottima del

problema di localizzazione degli impianti in cui sono attivati gli impianti A e B

Il costo di attivazione è pari a 3+6=9.

Il costo ottimo di afferenza è 6+7+4+5=22.

Il costo totale è 22+9=31.

8. Dato il grafo di localizzazione in figura, determinare il costo della soluzione ottima del

problema di localizzazione degli impianti in cui sono attivati gli impianti A, B e C

Il costo di attivazione è 3+6+8=17.

Il costo ottimo di afferenza è 6+1+4+4=15.

Il costo totale è 17+15=32.

9. Dato il grafo di localizzazione in figura, determinare il costo della soluzione ottima del

problema di localizzazione degli impianti in cui sono attivati gli impianti A e C

Il costo di attivazione è 3+8=11.

Il costo ottimo di afferenza è 6+1+5+4=16.

Il costo totale è 11+16=27.

10. Dato il grafo di localizzazione in figura, determinare il costo della soluzione ottima del

problema di localizzazione degli impianti in cui sono attivati gli impianti B e C

Il costo di attivazione è 6+8=14.

Il costo ottimo di afferenza è 6+1+4+4=15.

Il costo totale è 14+15=29.

LEZ 5

11. Dato il grafo di localizzazione in figura, definire le variabili del problema e i vincoli che

descrivono la regione ammissibile della formulazione del problema come problema di PLI

{0,1} {0,1}

∈ ∈

x x che rappresentano se attivare(1) o meno(0) il sito di produzione A o B.

A B

Le variabili y indicano se il sito A (oppure B) servono il sito cliente i(con i che può essere 1,2,3,4):se

lo servono varranno 1 altrimenti 0.

{0,1} {0,1} {0,1} {0,1}

∈ ∈ ∈ ∈

y y y y

1A 2A 3A 4A

{0,1} {0,1} {0,1} {0,1}

∈ ∈ ∈ ∈

y y y y

1B 2B 3B 4B

Per i vincoli abbiamo:

y + y = 1

1A 1B

y + y = 1

2A 2B

y + y = 1

3A 3B

y + y = 1

4A 4B

che esprimono il fatto che ogni sito cliente può essere servitor da un solo sito candidato,

e ≤ ≤ ≤ ≤

y x y x y x y x

1A A 2A A 3A A 4A A

≤ ≤ ≤ ≤

y x y x y x y x

1B B 2B B 3B B 4B B

che esprimono il fatto che il sito cliente y è servito dal sito candidato A se il sito è attivo.

Si definisce la funzione obiettivo:

min f x + f x + 6y + 8y + 6y + 7y + 6y + 7y + 4y + 5y

A A B B 1A 2A 3A 4A 1B 2B 3B 4B

con f e f che rappresentano I costi di attivazione dei siti candidati.

A B

12. Dato il grafo di localizzazione in figura, scrivere la funzione obiettivo e il valore che essa

assume nella soluzione della formulazione del problema come problema di PLI in cui

sono attivati gli impianti A e B

Si definisce la funzione obiettivo:

min f x + f x + f x + 6y + 8y + 6y + 7y + 6y + 7y + 4y + 5y + 10y + y + 5y

A A B B C C 1A 2A 3A 4A 1B 2B 3B 4B 1C 2C 3C

+ 4y 4C

il valore che essa assume nel caso siano attivati gli impianti A e B sarà:

min f x + f x + 6y + 8y + 6y + 7y + 6y + 7y + 4y + 5y = f x + f x +6+7+4+5=

A A B B 1A 2A 3A 4A 1B 2B 3B 4B A A B B

f x + f x +22

A A B B

Per essa dovranno valere sempre i vicoli sulle variabili y servite da un solo sito candidato e

che la y deve essere servita da un sito candidato attivo.

13. Dato il grafo di localizzazione in figura, definire le variabili del problema e i vincoli che

descrivono la regione ammissibile della formulazione del problema come problema di PLI

{0,1} {0,1}

∈ ∈

x x che rappresentano se attivare(1) o meno(0) il sito di produzione A o B.

A B

Le variabili y indicano se il sito A (oppure B) servono il sito cliente i(con i che può essere 1,2,3,4):se

lo servono varranno 1 altrimenti 0.

{0,1} {0,1} {0,1} {0,1}

∈ ∈ ∈ ∈

y y y y

1A 2A 3A 4A

{0,1} {0,1} {0,1} {0,1}

∈ ∈ ∈ ∈

y y y y

1B 2B 3B 4B

Per i vincoli abbiamo:

y + y = 1

1A 1B

y + y = 1

2A 2B

y + y = 1

3A 3B

y + y = 1

4A 4B

che rappresentano il fatto che ogni sito cliente i può essere servito soltanto da un sito candidato

e ≤ ≤ ≤ ≤

y x y x y x y x

1A A 2A A 3A A 4A A

≤ ≤ ≤ ≤

y x y x y x y x

1B B 2B B 3B B 4B B

che rappresentano il fatto che ogni sito cliente i può essere servito dal sito candidato x se

quest’ultimo è attivo.

Si definisce la funzione obiettivo:

min f x + f x + 2y + 4y + 1y + 5y + 7y + 6y + 2y + 4y

A A B B 1A 2A 3A 4A 1B 2B 3B 4B

con f e f che rappresentano I costi di attivazione dei siti candidati

A B

14. Dato il grafo di localizzazione in figura, definire le variabili del problema e i vincoli che

descrivono la regione ammissibile della formulazione del problema come problema di PLI

{0,1} {0,1}

∈ ∈

x x che rappresentano se attivare(1) o meno(0) il sito di produzione A o B.

A B

Le variabili y indicano se il sito A (oppure B) servono il sito cliente i(con i che può essere 1,2,3,4):se

lo servono varranno 1 altrimenti 0.

{0,1} {0,1} {0,1} {0,1}

∈ ∈ ∈ ∈

y y y y

1A 2A 3A 4A

{0,1} {0,1} {0,1} {0,1}

∈ ∈ ∈ ∈

y y y y

1B 2B 3B 4B

Per i vincoli abbiamo:

y + y = 1

1A 1B

y + y = 1

2A 2B

y + y = 1

3A 3B

y + y = 1

4A 4B

che rappresentano il fatto che ogni sito cliente i può essere servito soltanto da un sito candidato

e ≤ ≤ ≤ ≤

y x y x y x y x

1A A 2A A 3A A 4A A

≤ ≤ ≤ ≤

y x y x y x y x

1B B 2B B 3B B 4B B

che rappresentano il fatto che ogni sito cliente i può essere servito dal sito candidato x se

quest’ultimo è attivo.

Si definisce la funzione obiettivo:

min f x + f x + 2y + 4y + 1y + 1y + 3y + 6y + 2y + 4y

A A B B 1A 2A 3A 4A 1B 2B 3B 4B

con f e f che rappresentano I costi di attivazione dei siti candidati

A B

15. Dato il grafo di localizzazione in figura, scrivere la funzione obiettivo e il valore che essa

assume nella soluzione della formulazione del problema come problema di PLI in cui

sono attivati gli impianti A e C

Si definisce la funzione obiettivo:

min f x + f x + f x + 6y + 8y + 6y + 7y + 6y + 7y + 4y + 5y + 10y + y + 5y

A A B B C C 1A 2A 3A 4A 1B 2B 3B 4B 1C 2C 3C

+ 4y 4C

il valore che essa assume nel caso siano attivati gli impianti A e C sarà:

min f + f + 6y + 8y + 6y + 7y + 10y + y + 5y + 4y

A C 1A 2A 3A 4A 1C 2C 3C 4C

= f + f +6+1+5+4= f + f +16

A c A C

16. Dato il grafo di localizzazione in figura, scrivere la funzione obiettivo e il valore che essa

assume nella soluzione della formulazione del problema come problema di PLI in cui

sono attivati gli impianti B e C

Si definisce la funzione obiettivo:

min f x + f x + f x + 6y + 8y + 6y + 7y + 6y + 7y + 4y + 5y + 10y + y + 5y

A A B B C C 1A 2A 3A 4A 1B 2B 3B 4B 1C 2C 3C

+ 4y 4C

il valore che essa assume nel caso siano attivati gli impianti B e C sarà:

min f x + f x + 6y + 7y + 4y + 5y + 10y + y + 5y + 4y

B B C C 1B 2B 3B 4B 1C 2C 3C 4C

= f + f +6+1+4+4= f + f +15

B C B C

17. Dato il grafo di localizzazione in figura, scrivere la funzione obiettivo e il valore che essa

assume nella soluzione della formulazione del problema come problema di PLI in cui

sono attivati gli impianti A, B e C

Si definisce la funzione obiettivo:

min f x + f x + f x + 6y + 8y + 6y + 7y + 6y + 7y + 4y + 5y + 10y + y + 5y

A A B B C C 1A 2A 3A 4A 1B 2B 3B 4B 1C 2C 3C

+ 4y 4C

il valore che essa assume nel caso siano attivati gli impianti A ,B e C sarà:

min f x + f x + f x + 6y + 8y + 6y + 7y + 6y + 7y + 4y + 5y + 10y + y + 5y

A A B B C C 1A 2A 3A 4A 1B 2B 3B 4B 1C 2C 3C

+ 4y = f + f ++ f +6+1+4+4= f + f + f +15

4C A B C A B C

18. Dato il grafo di localizzazione in figura, definire le variabili del problema e i vincoli che

descrivono la regione ammissibile della formulazione del problema come problema di PLI

{0,1} {0,1}

∈ ∈

x x che rappresentano se attivare(1) o meno(0) il sito di produzione A o B.

A B

Le variabili y indicano se il sito A (oppure B) servono il sito cliente i(con i che può essere 1,2,3,4):se

lo servono varranno 1 altrimenti 0.

{0,1} {0,1} {0,1} {0,1}

∈ ∈ ∈ ∈

y y y y

1A 2A 3A 4A

{0,1} {0,1} {0,1} {0,1}

∈ ∈ ∈ ∈

y y y y

1B 2B 3B 4B

Per i vincoli abbiamo:

y + y = 1

1A 1B

y + y = 1

2A 2B

y + y = 1

3A 3B

y + y = 1

4A 4B

che rappresentano il fatto che ogni sito cliente i può essere servito soltanto da un sito candidato

e ≤ ≤ ≤ ≤

y x y x y x y x

1A A 2A A 3A A 4A A

≤ ≤ ≤ ≤

y x y x y x y x

1B B 2B B 3B B 4B B

che rappresentano il fatto che ogni sito cliente i può essere servito dal sito candidato x se

quest’ultimo è attivo.

Si definisce la funzione obiettivo:

min f x + f x + 4y + 3y + 2y + 1y + 2y + 4y + 2y + 6y

A A B B 1A 2A 3A 4A 1B 2B 3B 4B

con f e f che rappresentano i costi di attivazione dei siti candidati.

A B

LEZ 6

19. Applicare l'algoritmo Greedy al problema di Localizzazione degli Impianti

Provo il sito A ed ho costi pari a : 3+6+8+6+7=30.

Provo il solo sito B: 6+6+7+4+5=28.

Provo il sito C: 8+10+1+5+4=28.

La scelta greedy è il sito B (o alternativamente il sito C).

Provo B ed aggiungo:

 A ed ottengo: 6+3+6+7+4+5=31>28 allora non posso accettarla.

 C ed ottengo: 6+8+6+1+4+4=29>28 e non posso accettarla.

Provo C ed aggiungo:

 A ed ottengo: 8+3+6+1+5+4=27<28 quindi è una possibile candidata.

 B ed ottengo come prima 29>28 e non posso accettarla.

Ho quindi la soluzione ottima finora che è data dall’attivazione dei siti A e C.

Se aggiungo anche B ottengo: 8+3+6+6+1+4+4=32>27 e quindi la scarto.

La soluzione Greedy quindi è attivare i siti A e C con costo pari a 27.

20. Applicare l'algoritmo Greedy al problema di Localizzazione degli Impianti

Attivo soltanto il sito A ed ho un costo pari a : 4+2+4+1+5=16.

Attivo soltanto B: 3+7+6+2+4=22.

Scelgo di attivare A.

Se ad A aggiungo B ottengo un costo di : 4+3+2+4+1+4=18.

Quindi l’algorimo greedy si interrompe qui e tengo attivo soltanto A.

21. Definire la scelta greedy nell'applicazione dell'algoritmo greedy al problema di

localizzazione degli impianti

L’algoritmo di scelta greedy parte dal presupposto di andare a calcolare in diverse

iterazioni il costo totale di alcune soluzioni andando ad attivare prima i siti candidati

singolarmente e lasciando attivo quello a costo totale(attivazione+afferenza) più

basso(facendo per l’appunto una scelta greedy), successivamente si aggiungono un sito alla

volta i restanti e si ricalcolano i costi totali e se qualche costo è più basso