LA SESTA PROVINCIA PUGLIESE - SUPPLEMENTO DI INFORMAZIONE ON-LINE DELLA RIVISTA ASSODOLAB - ISSN 2280-3874

Ecco i test per gli Addetti antincendio.

www.addettiantincendio.net

SCUOLA..:: La formazione del personale della Scuola continua in questo nuovo anno scolastico con l'Assodolab... www.assodolab.it
Preparati per gli esami del patentino on-line, gratuitamente. www.quizpatentino.net

 

 

 

Il problema della localizzazione di impianti: implementazione di un’euristica greedy.

004..::.06.02.2014

 

..:: Nella foto, Luana Scicchitano.

 

..:: ISCA SULLO IONIO (CZ) - Le origini della Ricerca Operativa vengono fatte risalire al periodo della Seconda Guerra Mondiale, quando la Gran Bretagna usò dei modelli matematici per posizionare strategicamente un certo numero di radar, al fine di ottenere la massima protezione dagli attacchi nemici.
Finita la guerra, e con il boom industriale, sulla scorta dei successi ottenuti in campo bellico, un approccio simile venne utilizzato per allocare in maniera ottimale le risorse all’interno delle attività industriali o per l’organizzazione dei servizi pubblici.
I modelli di localizzazione ed i relativi algoritmi di soluzione iniziano, così, ad essere utilizzati come principali strumenti quantitativi per la pianificazione territoriale di «reti di servizio».
Questi modelli hanno come obiettivo generale quello di definire le localizzazioni di «centri di servizio» (impianti di produzione, centri di distribuzione, sportelli bancari etc.) che soddisfino una domanda dispersa nel territorio (negozi, comunità o singoli clienti). Elemento caratteristico di tutti i modelli di localizzazione è quello di definire «simultaneamente» la localizzazione dei centri di servizio e l’allocazione della domanda a tali centri. Per tale caratteristica i modelli di localizzazione vengono anche detti modelli di «localizzazione/allocazione».
La scelta della localizzazione di un singolo centro di servizio è effettuata solo dopo un’accurata analisi costi/benefici fra tutti i centri a disposizione e, inoltre, condiziona inevitabilmente il distribuirsi complessivo della domanda.
L’enorme successo dei modelli di localizzazione (e allocazione) è dovuto principalmente alla grande varietà degli indici (funzioni obiettivo) di cui si può usufruire per valutare la qualità delle reti di servizio e la possibilità di incorporare facilmente nel modello matematico vincoli ed ipotesi specifiche del problema reale che si vuole rappresentare.
Un’ultima, ma non meno importante, motivazione per il crescente utilizzo di tali modelli è costituita dalla disponibilità di elementari ed efficienti algoritmi di risoluzione, i quali consentono di ottenere soluzioni ottime o sub-ottime anche per problemi di dimensioni notevoli.
A tal proposito, particolare interesse desta lo studio del problema della Localizzazione di Impianti di tipo non capacitivo. Per la risoluzione del problema ho, infatti, implementato un’euristica di tipo “greedy” in grado di fornire una soluzione sub-ottima e la corrispondente stima dell’errore commesso (rispetto al calcolo di una soluzione ottima).
Uno fra i metodi euristici largamente utilizzati per la risoluzione di Problemi di Localizzazione degli Impianti, è l’euristica di scambio, nota anche con il termine di algoritmo “Greedy con scambio”. L’utilizzo di tale metodo, il quale restituisce una soluzione ammissibile , ci permette di calcolare una stima dell’errore relativo effettivo. Tale errore determina il valore di scostamento (espresso in percentuale) della soluzione ammissibile calcolata rispetto alla soluzione ottima del problema analizzato. Ovvero:
 

Errore relativo effettivo


Per istanze di dimensione elevata risulta molto oneroso applicare gli algoritmi in modo manuale, ecco che ritorna utile un’implementazione software che permetta di applicare entrambi gli algoritmi in modo completamente automatico.
Il linguaggio utilizzato a questo proposito è stato Microsoft Visual Basic 6.0.
L’applicazione si compone di un’interfaccia grafica iniziale, all’interno della quale sono presenti diversi pulsanti i quali consentono di accedere a funzionalità differenti dell’applicazione. Alcuni di essi sono stati inseriti in vista di future nuove funzionalità.
 


Il pulsante “Lavora 1 Istanza”, apre una seconda frame tramite la quale è possibile applicare gli algoritmi.
 


Come si può notare, è possibile definire un’istanza generica del problema, intesa in numero di impianti e numero di clienti. È, inoltre, possibile riempire tale istanza in maniera random (utilizzando l’apposito tasto), oppure in modo manuale.
Sia l’inserimento randomatico che manuale, permette di inserire valori sia per la matrice relativa ai costi di afferenza, sia per il vettore dei costi di attivazione degli impianti.
Inoltre l’interfaccia si compone di due distinte appendici laterali nelle quali è possibile visualizzare i vari passi degli algoritmi (Greedy e Greedy con Scambio) e i risultati ottenuti.
Nel caso in cui si prema il pulsante “Calcola Greedy con Scambio”, verrà applicato l’omonimo algoritmo, il quale ad ogni iterazione tenterà:
• di aggiungere un impianto alla soluzione restituita dal passo precedente;
• di eliminare un impianto dalla soluzione restituita dall’iterazione precedente;
• di scambiare due impianti.
L’algoritmo termina se dopo aver valutato tutte le possibili combinazioni non ottiene alcun valore migliorativo per la funzione obiettivo.
Si passa, successivamente per entrambe la soluzioni, al calcolo del valore di Lower Bound.
L’ultimo passo di tale elaborazione provvederà, infine, a restituire il valore relativo al rapporto seguente:

 

 



Luana Scicchitano

 

 

 

 

 

 

 

 

 

Richiedi un preventivo gratuito per il tuo impianto solare fotovoltaico e termico...
SISTEMA SOLARE Srl..:: Sistema Solare Srl si occupa di progettazione, fornitura, installazione, manutenzione di impianti solari fotovoltaici e termici, mini eolico e consulenza nel campo del risparmio energetico.

 

 

Per informazioni e preventivi gratuiti puoi telefonare al numero: 0884.585602 oppure inviare una e-mail a: info@sistemasolaresrl.it e verrete contattati entro 48 ore. 

Vuoi prepararti per il Brevetto di volo?

 

Bene, da oggi lo puoi fare con i test predisposti sul sito www.quizbrevettidivolo.it  

Visita il sito!
Piccoli produttori al femminile...
OLIO DI OLIVA..:: Molte sono le grandi aziende di olio di oliva che resiedono in Puglia, molte sono anche i piccoli produttori... Oggi  presentiamo una piccola realtà aziendale agricola Del Buono Nicolina.

 

 

Preparati per l'esame teorico della Carta di Qualificazione del Conducente.

 

Sul sito www.quizcqc.com puoi prepararti all'esame teorico gratuitamente.

 

Contatore visite

 

 

 

 

www.lasestaprovinciapugliese.it - Supplemento di informazione on-line della rivista Assodolab

Registrata al Tribunale di Foggia al n. 16/2000 - Privacy e Cookies Policy

Editrice: ASSODOLAB - P. IVA 03039870716 - Direttore responsabile: Arcangelo Renzulli