Paniere Ricerca operativa 2 - domande aperte

Applicazione dell'algoritmo greedy al problema di localizzazione degli impianti

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

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 BC(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:

1. Inizializza l'insieme dei siti candidati come vuoto.
2. Seleziona il primo sito da attivare scegliendo quello con il minor costo iniziale.
3. Aggiungi il sito selezionato all'insieme dei siti precedentemente selezionati.
4. Seleziona il prossimo sito candidato con il minor costo di attivazione.
5. Ripeti i passi 3 e 4 fino a quando l'aggiunta di nuovi siti non produce una diminuzione del costo.
6. Termina l'algoritmo.

Diagramma di flusso:

L'algoritmo Ricerca Locale al problema di Localizzazione degli Impianti:

1. Inizializza una soluzione iniziale casuale.
2. Calcola il costo della soluzione iniziale.
3. Ripeti fino a quando non si raggiunge una soluzione ottima o si supera il numero massimo di iterazioni:
• Genera una soluzione vicina alla soluzione corrente.
• Calcola il costo della soluzione vicina.
• Se il costo della soluzione vicina è migliore del costo della soluzione corrente, accetta la soluzione vicina come nuova soluzione corrente.
4. Termina l'algoritmo restituendo la soluzione corrente.

Diagramma di flusso:

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

Una volta trovata una soluzione iniziale con l'algoritmo greedy possiamo provare a migliorarla operando piccole modifiche. Ogni modifica è detta mossa perché "sposta" la soluzione, modificandone caratteristiche e valore della funzione obiettivo.

Esempi di mosse:

1. rimozione di un sito
2. rimozione + nuovo inserimento (scambio)

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. Viene selezionato il sito la cui attivazione massimizza la diminuzione del costo (criterio greedy). Nella 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 migliore. Viene mitigato il carattere greedy nella scelta del sito candidato. La ricerca termina quando non trovo mosse migliorative (criterio di arresto).

Spiegare le principali caratteristiche dell'algoritmo Greedy:

• 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 (non si prova mai a disattivare, tipico del comportamento greedy).
• Viene selezionato il sito la cui attivazione massimizza la diminuzione del costo (criterio greedy). Alla prima iterazione, l'insieme dei siti selezionati è vuoto e viene scelto il sito la cui attivazione comporta il minimo costo iniziale.

(criterio greedy). L'algoritmo termina quando l'aggiunta di un qualunque altro sito non produce diminuzioni del costo (criterio di arresto dell'algoritmo).

Spiegare le principali differenze tra la formulazione del problema di Localizzazione degli Impianti nel caso capacitato e quello non capacitato

Nella formulazione del problema di Localizzazione degli impianti nel caso capacitato, l'obiettivo è quello di formulare il problema di localizzazione con vincoli di capacità come problema di Programmazione Lineare Intera Mista.

Come nel caso non capacitato, la funzione obiettivo viene definita a partire da due funzioni:

1. Costi di attivazione
2. Costi di afferenza

Tutti e due i costi sono esprimibili come combinazione lineare delle variabili di decisione e quindi sono funzioni lineari.

La formulazione del problema di localizzazione come problema di Programmazione Lineare Intera Mista (PLIM) è ottenuta mettendo a sistema:

1. La funzione obiettivo lineare
2. I
vincoli (equazioni e disequazioni) lineari³. Variabili binarie definite nell'insieme {0,1} e variabili continue definite nell'insieme [0,1]⁴. Definiamo la formulazione come la minimizzazione della funzione obiettivo lineare (6.) soggetta ai vincoli lineari (3., 4. e 5.) che definiscono le relazioni tra le variabili a valori in {0,1} (1.) e le variabili continue (2.)
Nella formulazione del problema di Localizzazione degli impianti nel caso non capacitato, la formulazione del problema di localizzazione è affrontata come problema di Programmazione Lineare Intera (PLI) mettendo a sistema:
1. La funzione obiettivo lineare
2. I vincoli (equazioni e disequazioni) lineari
3. Variabili binarie definite nell'insieme {0,1}
Se le dimensioni di un problema di PLI crescono troppo, allora è impossibile risolverlo all'ottimalità allo stato attuale.