_stan
(320 punti)
11' di lettura
Un gruppo di operatori commerciali ha deciso di installare uno o più supermercati in una media città italiana ed ha stanziato a questo scopo la somma di un miliardo di Lire (1000 ML. Siamo negli anni 70 dello scorso secolo).

Gli esperti di mercato del gruppo hanno dapprima individuato (in base alle dimensioni ed alla estensione dei settori merceologici trattati) cinque diversi possibili tipi di supermercato e ne hanno calcolato il costo di impianto .

Sono poi state prese in esame le quattro zone della città che apparivano più idonee all'iniziativa e, per ciascuna di esse, si è calcolato il profitto annuo sperato per ognuno dei tipi di supermercato individuati.

Gli esperti hanno valutato che, al variare della zona prescelta, non sussistono apprezzabili differenze nei costi d'impianto, ma che evidentemente, non sia possibile installare due supermercati, sia pure diversamente strutturati, in una stessa zona, poiché in tal caso essi entrerebbero in concorrenza tra loro, riducendo i profitti annui sperati.

I risultati degli studi, tendenti a raccogliere i dati essenziali possono essere riepilogati in forma tabellare come appresso indicato:

Si debbano ricercare:

  1. L'investimento ottimale qualora, per considerazioni organizzative, il gruppo decida di limitare in ogni caso a non più di due il numero dei supermercati da installare nella città.
  2. L'investimento cui corrisponde il massimo profitto annuo sperato senza la limitazione precedente (ma mantenendo il vincolo di budget di 1 miliardo di Lit.).

Modello matematico

Ricorrendo a semplici simboli , i dati del problema possono essere formalizzati come appresso. Distinguiamo i possibili investimenti con l'indice (i), dove i può assumere come valori: 1,2,3,4,5. Indichiamo le zone nel quale effettuarli con l'indice (j = 1,2,3,4).

Chiamiamo poi

[math]C_i[/math]
l'ammontare dell'investimento (i) e
[math]P_(ij)[/math]
il profitto annuo sperato dall'investimento (i) nella zona (j). Introduciamo infine una variabile bivalente (X_{ij} (tale che assuma valore 1 quando si faccia l'investimento "i" nella zona "j" e valore 0 nel caso contrario).

La ricerca consisterà nell'individuare il massimo della funzione obiettivo:

(Z = \sum\sum X_{ij}ast P_{ij} ) Sommatoria dei profitti annui sperati in corrispondenza degli investimenti Prescelti (i = 1,…,5; j = 1,…,4).

Con i vincoli:

(\sum\sum X_{ijast C_j le10^9) Lire La somma di tutti gli investimenti effettuati deve essere minore od uguale ad un miliardo di Lire (i = 1,…,5; j = 1,…,4).

(\sum X_{i1} le 1) Non è possibile effettuare più di un investimento nella stessa zona; si
( \sum X_{i2} le 1) tratta di 4 vincoli perché la verifica deve essere fatta per ciascuna zona
( \sum X_{i3} le 1 ) (i = 1,…,5).
( \sum X_{i4} le 1)
( \sum X_{ij} ast C_j le 2) Gli investimenti non debbono essere più di 2 (i = 1,…,5; j = 1,…,4).

Abbiamo una funzione obiettivo da massimizzare e 6 vincoli. Sia la funzione obiettivo che i vincoli sono lineari, ma le variabili (X_{ij}) sono a numeri interi ed in particolare del tipo 0-1. Il risolutore di Excel, in questo caso ci chiede di aggiungere un vincolo che imponga alle 5*4 = 20 variabili di essere bivalenti. Per questo tipo di problemi il Risolutore adotta la combinazione di due tecniche: Il metodo del Simplesso (perché il problema è lineare) ed il Branch&Bound perché il problema è a numeri interi. Il metodo Ramifica&Taglia si basa sullo sviluppo di un albero in cui per ogni ramo si confronta la miglior soluzione fattibile (Lower Bound) con la miglior soluzione potenziale (Upper Bound). Quando Upper Bound e Lower Bound coincidono e non vi sono più rami promettenti da esplorare si è trovata la soluzione ottima.

Tecniche Euristiche di ricerca delle Soluzioni a un Problema

Euristico (dal greco ευρίσκω : trovare, scoprire) si dice di un procedimento approssimativo, intuitivo che attraverso procedure in genere semplici porta ad una soluzione del problema.

Queste soluzioni possono essere più o meno buone e talora anche ottime, ma non si può mai, con esse, avere la certezza di aver trovato la soluzione migliore possibile.

La prima tecnica che vogliamo esporre appartiene alla famiglia delle tecniche chiamate "Greedy" in Italiano "Ingorde". In pratica si tratta, ad ogni singolo passo, di scegliere l'alternativa che consente il massimo guadagno nel rispetto di tutti i vincoli.

Vediamone l'applicazione al nostro problema considerando la matrice, sopra riportata dei profitti Pij per investimento (i) nella zona (j). Al primo passo scegliamo (il metodo è appunto "Ingordo" o "Avido") di porre uguale ad 1 la variabile X52 (Investimento di 1000 nella Zona 2) che garantisce il massimo profitto (105):

A questo punto non è possibile allocare nuovi investimenti perché abbiamo già raggiunto il massimo budget disponibile di un miliardo di lire (1000 Milioni L.). La procedura si arresta perché non sono consentiti dai vincoli ulteriori allocazioni.

Anche se togliessimo, come richiesto dalla ricerca numero 2), il limite di non più di due supermercati nulla cambierebbe perché il vincolo di 1000 milioni è comunque saturato.

Prendiamo ora in esame una tecnica euristica un po' "meno ingorda" e un po' "più ragionevole". Si tratta di tener conto, non solo come sopra dei "guadagni sperati", ma anche delle risorse impiegate per generarli cioè di un indicatore di efficienza del tipo: Risultati/Risorse. Nel nostro caso, ad esempio, appare opportuno scegliere il rapporto Pij/Cj fra i valori del profitto sperato e del corrispondente investimento (nella analisi degli investimenti questo indicatore si chiama rapporto Gamma ed è legato allo Indice di Profittabilità dalla relazione G = PI - 1) . La tabella dei valori numerici dell'indicatore di efficienza (5 righe-investimenti e 4 colonne-zone) è:

La ricerca 1) suggerisce di scegliere i primi due investimenti che hanno l'indice migliore, cioè (X_{13} = 1) e (X_{14} = 1). A queste scelte corrisponde infatti rispettivamente:

(P_{13}/C_1 = 0.16 )
(P_{14}/C_1 = 0.12 )

Non sono possibili ulteriori investimenti in quanto abbiamo già raggiunto il massimo di 2.

La funzione obiettivo vale:

(Z= 32 + 24 = 56 \text{milioni di Lit}).

Questa soluzione è ben poco soddisfacente in quanto già con il metodo Greedy si può trovare un valore di Z pari a 105 milioni di Lit.

Vediamo ora come si comporta questa euristica con la ricerca 2) che prevede di togliere il vincolo di due Supermercati nella città. Esaminando la tabella dell'indicatore di efficienza troviamo che i successivi valori più alti (dopo quelli già assegnati 0.16 e 0.12) sono:

(P_{23}/C_2 = 0.1125 )
(P_{33}/C_3 = 0.1117)
(P_{24}/C_2 = 0.1100)

Queste soluzioni non possono però essere prese in considerazione in quanto implicano di installare i Supermercati in zone già servite (abbiamo detto non più di un investimento per zona). Il Successivo valore in una zona non servita è dunque

(P_{31}/C_3 = 0.1083)

A questo punto il processo deve arrestarsi perché abbiamo fatto investimenti per: 200 + 200 + 600 = 1000 Milioni Lit. che è il massimo consentito dal vincolo di Budget. Ecco la soluzione trovata:

(Z = 32 + 24 + 65 = 121 \text{Milioni di Lit}).

Questa soluzione è migliore di quella trovata con l'euristica "ingorda" (105 Milioni) e, come vedremo nel prossimo paragrafo, coincide anche con quella ottimale.

Soluzioni Ottime

1) Ricerca con il vincolo di solo due investimenti:

Variabili bivalenti per zona/invest. (Xij = 0 o 1)
1 2 3 4
0 0 0 0
0 0 0 1
0 0 1 0
0 0 0 0
0 0 0 0

1 1 1 1 Numero massimo investimenti per zona
0 0 1 1 Scelti 0 investimenti in zone 1 - 2 e 1 in 3 - 4
2 2 Investimenti Totali: Consentiti - Realizzati
1000 1000 Vincolo di Budget - Spesa Realizzata
111 Z = Guadagno totale = 44 + 67 Milioni di Lire
Dunque, in questo caso nessuna delle due tecniche euristiche proposte è riuscita ad individuare la soluzione ottimale (anche se il metodo Greedy è risultato largamente migliore).

2) Ricerca con nessun vincolo sul numero di investimenti

Per effettuare questa ricerca è necessario eliminare il vincolo di due investimenti al massimo. Abbiamo preferito, per comodità, un'altra via che lascia inalterato il modello matematico. Si tratta della tecnica del rilasciamento dei vincoli. In pratica abbiamo posto, invece che pari a 2, pari a 100 il numero massimo di investimenti possibili (si osservi che il massimo teorico è di 5*4 = 20 investimenti). Ecco i risultati:

Variabili bivalenti per zona/invest. (Xij = 0 o 1)
1 2 3 4
0 0 1 1
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0

1 1 1 1 Numero massimo investimenti per zona
1 0 1 1 Scelti 0 investimenti in zone 2 e 1 e 1 in 1,3,4
100 3 Vincolo rilasciato - Scelti 3 investimenti
1000 1000 Vincolo di Budget - Spesa Realizzata
121 Z = Guadagno totale = 32 + 24 + 65 Milioni di Lire

Chi fosse interessato può scaricare il file Excel che consente con facilità di effettuare nuove ricerche: attualizzando i valori ad oggi e computandoli in Euro, variando il Budget totale degli investimenti disponibili oppure aumentando il numero massimo degli investimenti consentiti per zona. Oggi, in una grande città come Milano ad esempio, capita infatti di avere più di un Supermercato con lo stesso marchio nella stessa zona.

Riferimenti

  • U. De Simoni, R. Chiappi, "La decisione motivata", non pubblicato, Ivrea 1976
  • F. Hillier, G. Lieberman, "Introduction to Operations Research", Holden Day, San Francisco 1969
  • F. Hillier, G. Lieberman, "Ricerca Operativa - Fondamenti", Mondadori, Milano 2010. Curatori traduzione italiana: D. Ambrosino, A. Sciomachen
  • R.Chiappi , "Il Foglio Elettronico come strumento per il Problem Solving", Angeli, Milano 2008.