Paniere Ricerca operativa 2 - domande aperte

Quali sono i principali strumenti di pianificazioni impiegati per la

pianificazione dei sistemi complessi e distribuiti?

I principali strumenti sono:

1) definizione di un modello di rete

2) definizione delle grandezze che descrivono tutte le componenti del modello di rete

3) definizione di tutte le variabili, le relazioni tra le variabili e i vincoli cui sono soggette le variabili

del modello di rete

Cosa significa costruire un modello?

Costruire un modello significa rappresentare il problema attraverso un modello matematico che ne

astragga gli aspetti essenziali e che schematizzi le interrelazioni esistenti tra i diversi aspetti del fenomeno

che si sta studiando. Costruire un modello significa modellare la famiglia delle soluzioni ammissibili come

insieme di soluzioni di un problema

Cos'è un modello, quali vantaggi offre e come è correlato ai sistemi di

pianificazione dei sistemi complessi e distribuiti?

Un modello, nella Ricerca Operativa, è un modello matematico che si serve del simbolismo dell'algebra per

mettere in evidenza le relazioni principali dell'oggetto che deve essere modellato. L'impiego dei modelli

matematici nella ricerca operativa presenta i seguenti vantaggi:

1) la soluzione può essere trovata matematicamente e quindi in maniera automatica

2) vi è la possibilità di fare diverse simulazioni (e.g., what if)

3) deduzione analitica di proprietà utili per risolvere classi di problemi.

Descrivere gli elementi caratterizzanti il problema di localizzare degli

impianti

Il problema di localizzazione degli impianti è un esempio di problema dove ogni decisione è caratterizzata

da un insieme di siti di produzione da attivare e dalle quantità di risorse da produrre per soddisfare i siti

domanda.

Nella localizzazione degli impianti i siti di produzione sono identificati come impianti di produzione. Ogni

soluzione ammissibile del problema è un sottoinsieme di siti dove attivare un impianto in modo da coprire il

fabbisogno, soddisfare vincoli di bilancio (costo), ottimizzare specifici obiettivi.

Dare la definizione di problema di localizzazione degli impianti

Il problema di localizzazione degli impianti è un esempio di problema dove ogni decisione è caratterizzata

da un insieme di siti di produzione da attivare e dalle quantità di risorse da produrre per soddisfare i siti

domanda.

Nella localizzazione degli impianti i siti di produzione sono identificati come impianti di produzione. Ogni

soluzione ammissibile del problema è un sottoinsieme di siti dove attivare un impianto in modo da coprire il

fabbisogno, soddisfare vincoli di bilancio (costo), ottimizzare specifici obiettivi.

Disegnare il grafo di localizzazione con 4 siti candidati {A, B, C, D} e 2 clienti

{1,2}

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

Costi di afferenza più convenienti per i clienti

● Cliente 1: A ed è uguale a 6

● Cliente 2: B ed è uguale a 7

● Cliente 3: B ed è uguale a 4

● Cliente 4: B ed è uguale a 5

Costi di attivazione di A e B: 3 e 6

Il costo della soluzione ottima è data dalla somma complessiva della somma dei costi di attivazione dei siti

A e B e la somma dei costi di afferenza dei 4 clienti

3+6=9

6+7+4+5=22

22 + 9 = 31

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

Costi di afferenza più convenienti per i clienti

● Cliente 1: A ed è uguale a 6

● Cliente 2: C ed è uguale a 1

● Cliente 3: B ed è uguale a 4

● Cliente 4: C ed è uguale a 4

Costi di attivazione di A, B e C: 3, 6 e 8

Il costo della soluzione ottima è data dalla somma complessiva della somma dei costi di attivazione dei siti

A e B e la somma dei costi di afferenza dei 4 clienti

3+6 + 8=17

6+1+4+4=15

17+15=32

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

Costi di afferenza più convenienti per i clienti

● Cliente 1: A ed è uguale a 6

● Cliente 2: C ed è uguale a 1

● Cliente 3: C ed è uguale a 5

● Cliente 4: C ed è uguale a 4

Costi di attivazione di A e C: 3 + 8

Il costo della soluzione ottima è data dalla somma complessiva della somma dei costi di attivazione dei siti

A e B e la somma dei costi di afferenza dei 4 clienti

3 + 8=11

6+1+5+4=16

11+16=27

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

Costi di afferenza più convenienti per i clienti

● Cliente 1: B ed è uguale a 6

● Cliente 2: C ed è uguale a 1

● Cliente 3: B ed è uguale a 4

● Cliente 4: C ed è uguale a 4

Costi di attivazione di B e C: 6 + 8

Il costo della soluzione ottima è data dalla somma complessiva della somma dei costi di attivazione dei siti

A e B e la somma dei costi di afferenza dei 4 clienti

6 + 8=14

6+1+4+4=15

14+15=29

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

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 a partire da due funzioni:

I costi di attivazione

I costi di afferenza

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

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

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 a partire da due funzioni:

I costi di attivazione

I costi di afferenza

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 a partire da due funzioni:

I costi di attivazione

I costi di afferenza

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 a partire da due funzioni:

I costi di attivazione

I costi di afferenza

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

Applicare l'algoritmo Greedy al problema di Localizzazione degli Impianti

Sito A

Fa = 3

Costo afferenza: 6+8+7+6

Costo finale 3+ 27 = 30

Sito B

6+6+7+4+5 = 28

Sito C

8+10+1+5+4= 28

SITO PARTENZA B

Provo A: 3+6+6+7+4+5=31 no

Provo C: 6+8+6+1+4+4= 29 no

SITO PARTENZA C

Provo A: 8+3+6+1+5+4=27 si

Provo B:8+6+6+1+4+4=29 no

Si attivano i siti C (sito di partenza) ed il sito A →c(T={A+C})=27

Proviamo adesso ad aggiungere il sito rimanente B

C(T={A+B+C}) = 3+6+8+6+1+4+4 = 32 no

I siti che rimangono attivi sono solo i siti A e il sito C

Applicare l'algoritmo Greedy al problema di Localizzazione degli Impianti

Troviamo il sito di partenza

Sito A: 4+2+4+5+1 = 16

Sito B: 3+7+6+2+4=22

Il sito di partenza è il sito A.

Vediamo se possiamo attivare anche il sito B

4+3 +2+4+1+4= 18 no

L’unico sito che si attiva è il sito A

Illustrare attraverso un esempio l'applicazione dell'algoritmo greedy al

problema di localizzazione degli impianti

Sito A

Fa = 3

Costo afferenza: 6+8+7+6

Costo finale 3+ 27 = 30

Sito B

6+6+7+4+5 = 28

Sito C

8+10+1+5+4= 28

SITO PARTENZA B

Provo A: 3+6+6+7+4+5=31 no

Provo C: 6+8+6+1+4+4= 29 no

SITO PARTENZA C

Provo A: 8+3+6+1+5+4=27 si

Provo B:8+6+6+1+4+4=29 no

Si attivano i siti C (sito di partenza) ed il sito A →c(T={A+C})=27

Proviamo adesso ad aggiungere il sito rimanente B

C(T={A+B+C}) = 3+6+8+6+1+4+4 = 32 no

I siti che rimangono attivi sono solo i siti A e il sito C

Applicare l'algoritmo Greedy al problema di Localizzazione degli Impianti

Non essendoci i costi di attivazione dei siti, l’algoritmo greedy non si può applicare.

Se fa=3, fb=6 e fc=8 vedere il procedimento della domanda precedente

Definire la scelta greedy nell'applicazione dell'algoritmo greedy al

problema di localizzazione degli impianti

L’algoritmo greedy è una procedura deterministica. Per arrivare ad una soluzione seleziona un sito

candidato alla volta. Inizialmente l’insieme dei siti candidati è vuoto. Per individuare il primo sito da attivare

viene scelto il sito con un costo di attivazione con il minor costo iniziale. Ad ogni iterazione il sito

selezionato viene aggiunto all’insieme precedentemente selezionati. Un sito, se attivato, rimane attivo fino

alla fine dell’esecuzione dell’algoritmo.

Il criterio greedy di selezione dei siti è trovare il sito la cui attivazione massimizza la diminuzione del costo.

Il costo è dato dalla somma del costo di attivazione dell’impianto e del costo di distribuzione.

L’algoritmo termina quando l’aggiunta di nuovi siti non produce una diminuzione del costo

Fornire alcuni esempi di problema di localizzazione degli impianti

1. Scegliere un gruppo di siti dove installare gli impianti di produzione di energia in modo da

soddisfare determinati vincoli e ottimizzare specifici obiettivi

2. Scegliere un gruppo di siti dove ospitare un centro di assistenza alla produzione in modo da, per

esempio, servire tutti gli impianti che richiedono assistenza o per esempio che abbiano una

distanza vicina con gli impianti

3. Scegliere come dispiegare i mezzi di soccorso in un impianto di produzione

Applicare l'algoritmo Greedy al problema di Localizzazione degli Impianti e

illustrarne il diagramma di flusso

L’algoritmo greedy è una procedura deterministica. Per arrivare ad una soluzione seleziona un sito

candidato alla volta. Inizialmente l’insieme dei siti candidati è vuoto. Per individuare il primo sito da attivare

viene scelto il sito con un costo di attivazione con il minor costo iniziale. Ad ogni iterazione il sito

selezionato viene aggiunto all’insieme precedentemente selezionati. Un sito, se attivato, rimane attivo fino

alla fine dell’esecuzione dell’algoritmo. L’algoritmo termina quando l’aggiunta di nuovi siti non produce una

diminuzione del costo

Spiegare l'algoritmo Greedy illustrandone i passi attraverso il diagramma di

flusso

Spiegare la Ricerca Locale illustrandone i passi attraverso il diagramma di

flusso

Applicare l'algoritmo Ricerca Locale al problema di Localizzazione degli

Impianti

Non essendoci i costi di attivazione dei siti, l’algoritmo greedy non si può applicare.

Applicare la Ricerca Locale al problema di Localizzazione degli Impianti e

illustrarne il diagramma di flusso

Consideriamo il seguente grafo:

L’algoritmo greedy sceglie la soluzione migliore T={A,B} di costo 9

Lo scambio è inutile, l’algoritmo si ferma e restituisce T={B,C}

Applicare l'algoritmo Ricerca Locale al problema di Localizzazione degli

Impianti

L’algoritmo definisce le soluzione selezionando gli impianti uno alla volta

C(T={A}) = 4+2+4+5+1=16

C(T={B})= 3 +7+2+6+4=22

La soluzione migliore è T={A}

Proviamo ad aggiungere il sito B

C(T={A,B}) = 3+4+2+4+1+4=18

Inserire B non diminuisce il costo quindi l’algoritmo greedy si ferma.

Applichiamo la ricerca locale a partire dalla soluzione greedy

Non possiamo rimuovere il sito in quanto è l’unico sito attivo, procediamo allo scambio

Proviamo a scambiare A con B, abbiamo C(T={B})= 3 +7+2+6+4=22

Non abbiamo una diminuzione di costo

L’agoritmo di ricerca locale si ferma e restituisce la soluzione T={A}

Spiegare le principali differenze tra algoritmo Greedy e Ricerca Locale

‐ L’algoritmo Greedy è una procedura deterministica che costruisce una soluzione del problema di

localizzazione selezionando un sito candidato alla volta.

A ogni iterazione, il sito selezionato viene aggiunto all’insieme costituito dai siti candidati precedentemente

selezionati.

Una volta attivato, il sito rimane tale fino alla fine.

Viene selezionato il sito la cui attivazione massimizza la diminuzione del costo.

L’algoritmo termina quando l’aggiunta di un qualunque altro sito non produce diminuzioni del costo.

La Ricerca Locale data una soluzione ammissibile corrente, tenta di migliorare “localmente” la soluzione

corrente.

Le modifiche sono piccole in quanto solitamente si agisce su una o al massimo due componenti della

soluzione corrente.

Vengono considerate anche mosse che implichino la rimozione di un impianto che in qualche iterazione

precedente era stato indicato come candidato